3 ms·

Can anyone say what the security implications of this are? Intuitively, it would seem the less 'random' primes appear to be, the easier it would be to factor t

by valine 11y ago

Can anyone say what the security implications of this are? Intuitively, it would seem the less 'random' primes appear to be, the easier it would be to factor the composite of two prime numbers.

jessaustin 11y ago
Never say "never", but it would seem that this would only help in breaking a procedure that used consecutive primes. Every system of which I'm aware generates the primes it requires without reference to the primes that come before or after.
jerf 11y ago
The hardness of factoring is not in the finding prime numbers. You could hand someone a list of all primes in the security-relevant sizes, and it's not going to help them much. Yeah, in practice it'll affect the total computation time, but generally security people tend to assume extremely generous fudge factors anyhow. A lot of times when you see security papers talking about how something takes "2 to the 50 operations", they're referring to the full process of hashing some string 2 to the 50 times or something like that, rather than 2 to the 50 CPU cycles. When so many security operations involve things getting exponentially harder as you add bits, there's not much point in trying to shave an order of magnitude here or there; you just go ahead and make things that are secure even if the entire universe is converted into computronium and dedicated to brute-forcing your security. (Because so far, that's never been the ultimate security problem.)
stromgo 11y ago
You have it backwards. Their result holds for any set of numbers that behave randomly, so it holds for primes because primes behave somewhat randomly.
- stromgo 11y ago
  Why the downmods? Everyone can easily verify that there are similar biases if you replace "isPrime(n)" with "random() < 0.1" in the various code snippets floating in the thread. The article even admits that the biases are explained by the prime k-tuples conjecture, which is a model of randomness in primes from 1923. So primes are not less random than we thought -- they are still exactly as random as we thought.
czinck 11y ago
On top of what others have said, this actually doesn't apply to RSA at all. There are ways to factor the prime-product used in RSA faster if you believe the 2 primes are close together[1], so any good RSA key generator should be picking primes that are far apart (when I wrote a toy key generator for a class I just tried to make the second prime more than twice the first), and this "conspiracy" only applies to consecutive primes. As you get further away from the original prime, you get less info about what the last digit could be. [1] https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Faulty_key_generation https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Faulty_...

by valine 11y ago

Can anyone say what the security implications of this are? Intuitively, it would seem the less 'random' primes appear to be, the easier it would be to factor the composite of two prime numbers.

jessaustin 11y ago

Never say "never", but it would seem that this would only help in breaking a procedure that used consecutive primes. Every system of which I'm aware generates the primes it requires without reference to the primes that come before or after.

jerf 11y ago

The hardness of factoring is not in the finding prime numbers. You could hand someone a list of all primes in the security-relevant sizes, and it's not going to help them much. Yeah, in practice it'll affect the total computation time, but generally security people tend to assume extremely generous fudge factors anyhow. A lot of times when you see security papers talking about how something takes "2 to the 50 operations", they're referring to the full process of hashing some string 2 to the 50 times or something like that, rather than 2 to the 50 CPU cycles. When so many security operations involve things getting exponentially harder as you add bits, there's not much point in trying to shave an order of magnitude here or there; you just go ahead and make things that are secure even if the entire universe is converted into computronium and dedicated to brute-forcing your security. (Because so far, that's never been the ultimate security problem.)

stromgo 11y ago

You have it backwards. Their result holds for any set of numbers that behave randomly, so it holds for primes because primes behave somewhat randomly.

stromgo 11y ago
Why the downmods? Everyone can easily verify that there are similar biases if you replace "isPrime(n)" with "random() < 0.1" in the various code snippets floating in the thread. The article even admits that the biases are explained by the prime k-tuples conjecture, which is a model of randomness in primes from 1923. So primes are not less random than we thought -- they are still exactly as random as we thought.

czinck 11y ago

On top of what others have said, this actually doesn't apply to RSA at all. There are ways to factor the prime-product used in RSA faster if you believe the 2 primes are close together[1], so any good RSA key generator should be picking primes that are far apart (when I wrote a toy key generator for a class I just tried to make the second prime more than twice the first), and this "conspiracy" only applies to consecutive primes. As you get further away from the original prime, you get less info about what the last digit could be. [1] https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Faulty_key_generation https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Faulty_...