4 ms·

Does this mean as much as I think it does? Aren't most of our current cryptography schemes based on prime numbers taking time to calculate?

lutusp 13y ago
The fact that mathematicians have refined the theoretical distance between pairs of primes has precisely no effect on the difficulty of factoring large composites. Those are completely unrelated problems.
- fiatmoney 13y ago
  I would imagine that proving they are completely unrelated would be a significant result in and of itself.
  - mden 13y ago
    I think this is a completely fair point. Things in mathematics are astoundingly interconnected and you never know whether a seemingly benign proof will turn out to be the key to unlocking something much more pivotal.
  - lutusp 13y ago
    Proving the absence of something lies in the nether regions of science and mathematics. Consider the problem of proving the absence of Bigfoot -- it can't be done. This is a well-understood logical problem with a storied past: http://en.wikipedia.org/wiki/Russell's_teapot http://en.wikipedia.org/wiki/Russell's_teapot
wglb 13y ago
No. If someone discovers a shortcut in factoring very large numbers, then it will have the attention of cryptographers.
csense 13y ago
No. Finding random primes is easy, especially if you don't mind using methods which allow an extremely tiny probability of error [1] -- this is standard practice in cryptography. Finding random big primes p and q is easy. Multiplying them together into a product r = pq is easy. RSA cryptosystem picks p and q when generating the key, multiplies them, then throws away original p and q values. Only r is stored in the key. Cracking the RSA algorithm itself [2] is basically equivalent to turning r back into p and q. RSA is based on the hardness of factoring an integer into a product of primes. I don't think this conjecture will lead to practical improvements in cryptography / cryptanalysis, at least not with respect to cryptosystems that are currently widely used. [1] http://en.wikipedia.org/wiki/Primality_testing#Probabilistic_tests http://en.wikipedia.org/wiki/Primality_testing#Probabilistic... [2] Of course, there are many more attack vectors on specific implementations of the RSA algorithm, like trying to gain information on the secret key by measuring time taken to encrypt a message, measuring heat/power consumption/electronic noise, taking advantage of implementations that use a poor source of randomness, hacking into the system where the private key is stored, or bribing/threatening a human with legitimate access to the private key (as covered in http://xkcd.com/538/ http://xkcd.com/538/).
- nitrogen 13y ago
  You run into problems, though, if you randomly select one of the same prime factors as someone else: https://www.hnsearch.com/search#request/all&q=gcd+public+key https://www.hnsearch.com/search#request/all&q=gcd+public+key
- gizmo686 13y ago
  > Cracking the RSA algorithm itself is basically equivalent to turning r back into p and q. This has not been proven. RSA encrypts by taking C=m^e (MOD N). The normal way of decrypting is to take C^d (MOD N), where d can be efficiently computed if you know the factors of N. However, all you need to do to decrypt C is to take the e`th root (mod n). It has not been shown that the ability to do so allows you to factor N. In fact, it appears (after a few minutes of research, so someone please correct me if I'm wrong), that their is evidence that breaking RSA is easier than factoring [1] [1]http://crypto.stanford.edu/~dabo/pubs/papers/no_rsa_red.pdf http://crypto.stanford.edu/~dabo/pubs/papers/no_rsa_red.pdf
has2k1 13y ago
What it means is that, although on the whole consecutive prime numbers tend to have larger separations as the magnitude increases, you will still be able to find consecutive primes with smaller separation sizes. The current proof puts that limit at 600. The twin prime conjecture posits that the limit is 2, i.e you can never exhaust pairs of consecutive primes with the smallest possible separation size.
mistercow 13y ago
Some of our current cryptography schemes are based on it taking time to factor large numbers, but this is not the same thing as finding prime numbers. The basic principle is that if I take two large prime numbers, P1 and P2, and give you their product, Q, then it will take you a very long time to learn P1 and P2 unless I give you one of them. It is actually very important that the hardness of that problem does not come from the difficulty of finding prime numbers. Which numbers are prime is a question that is independent of breaking any particular key, which means that if that were the source of hardness, you could reuse the work from breaking one key to break future keys, by storing a list of the prime numbers you calculated. This would be a Bad Thing. There are a lot of misconceptions, in fact, about hardness, prime numbers, and factorization. People often assume that primality testing and factorization are equivalent, and that both are NP complete. In fact, PRIMES is known to be in P, and (the decision version of) integer factorization is probably not NP complete (it is in NP by way of PRIMES being in P), although it is not known if it is in P.

lutusp 13y ago

The fact that mathematicians have refined the theoretical distance between pairs of primes has precisely no effect on the difficulty of factoring large composites. Those are completely unrelated problems.

fiatmoney 13y ago
I would imagine that proving they are completely unrelated would be a significant result in and of itself.
- mden 13y ago
  I think this is a completely fair point. Things in mathematics are astoundingly interconnected and you never know whether a seemingly benign proof will turn out to be the key to unlocking something much more pivotal.
- lutusp 13y ago
  Proving the absence of something lies in the nether regions of science and mathematics. Consider the problem of proving the absence of Bigfoot -- it can't be done. This is a well-understood logical problem with a storied past: http://en.wikipedia.org/wiki/Russell's_teapot http://en.wikipedia.org/wiki/Russell's_teapot

wglb 13y ago

No. If someone discovers a shortcut in factoring very large numbers, then it will have the attention of cryptographers.

csense 13y ago

No. Finding random primes is easy, especially if you don't mind using methods which allow an extremely tiny probability of error [1] -- this is standard practice in cryptography. Finding random big primes p and q is easy. Multiplying them together into a product r = pq is easy. RSA cryptosystem picks p and q when generating the key, multiplies them, then throws away original p and q values. Only r is stored in the key. Cracking the RSA algorithm itself [2] is basically equivalent to turning r back into p and q. RSA is based on the hardness of factoring an integer into a product of primes. I don't think this conjecture will lead to practical improvements in cryptography / cryptanalysis, at least not with respect to cryptosystems that are currently widely used. [1] http://en.wikipedia.org/wiki/Primality_testing#Probabilistic_tests http://en.wikipedia.org/wiki/Primality_testing#Probabilistic... [2] Of course, there are many more attack vectors on specific implementations of the RSA algorithm, like trying to gain information on the secret key by measuring time taken to encrypt a message, measuring heat/power consumption/electronic noise, taking advantage of implementations that use a poor source of randomness, hacking into the system where the private key is stored, or bribing/threatening a human with legitimate access to the private key (as covered in http://xkcd.com/538/ http://xkcd.com/538/).

nitrogen 13y ago
You run into problems, though, if you randomly select one of the same prime factors as someone else: https://www.hnsearch.com/search#request/all&q=gcd+public+key https://www.hnsearch.com/search#request/all&q=gcd+public+key
gizmo686 13y ago
> Cracking the RSA algorithm itself is basically equivalent to turning r back into p and q. This has not been proven. RSA encrypts by taking C=m^e (MOD N). The normal way of decrypting is to take C^d (MOD N), where d can be efficiently computed if you know the factors of N. However, all you need to do to decrypt C is to take the e`th root (mod n). It has not been shown that the ability to do so allows you to factor N. In fact, it appears (after a few minutes of research, so someone please correct me if I'm wrong), that their is evidence that breaking RSA is easier than factoring [1] [1]http://crypto.stanford.edu/~dabo/pubs/papers/no_rsa_red.pdf http://crypto.stanford.edu/~dabo/pubs/papers/no_rsa_red.pdf

has2k1 13y ago

What it means is that, although on the whole consecutive prime numbers tend to have larger separations as the magnitude increases, you will still be able to find consecutive primes with smaller separation sizes. The current proof puts that limit at 600. The twin prime conjecture posits that the limit is 2, i.e you can never exhaust pairs of consecutive primes with the smallest possible separation size.

mistercow 13y ago

Some of our current cryptography schemes are based on it taking time to factor large numbers, but this is not the same thing as finding prime numbers. The basic principle is that if I take two large prime numbers, P1 and P2, and give you their product, Q, then it will take you a very long time to learn P1 and P2 unless I give you one of them. It is actually very important that the hardness of that problem does not come from the difficulty of finding prime numbers. Which numbers are prime is a question that is independent of breaking any particular key, which means that if that were the source of hardness, you could reuse the work from breaking one key to break future keys, by storing a list of the prime numbers you calculated. This would be a Bad Thing. There are a lot of misconceptions, in fact, about hardness, prime numbers, and factorization. People often assume that primality testing and factorization are equivalent, and that both are NP complete. In fact, PRIMES is known to be in P, and (the decision version of) integer factorization is probably not NP complete (it is in NP by way of PRIMES being in P), although it is not known if it is in P.