4 ms·

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 practi

by 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
Someone 13y ago
"Finding random big primes p and q is easy" For those wondering why then, it is news when a new largest prime is found: there are gradations of 'big'. The big primes used in cryptography have fewer than 1000 bits, or about 300 digits. That is not what one (nowadays) calls 'large' in the field of finding the largest prime. There, one laughs at numbers of a million digits (the largest known prime has 17,425,170 digits)
- csense 13y ago
  Also, for a practical engineering problem, like writing an RSA implementation which will be used in an SSL implementation which will encrypt credit card numbers on an e-commerce website, it is okay to use probabilistic tests which have a tiny chance of a false positive (the test claims a number is prime when it is actually composite). You can generally repeat a probabilistic test with different parameters to make the probability of a "false positive" prime number very tiny -- like .000 000 000 001 -- while still staying within the computational budget manageable on an ordinary computer (obviously, a practical Internet security scheme should be able to complete its computations in a second or two on a typical desktop, laptop, server, and smartphone). So probabilistic tests are good enough for practical purposes, but you need a non-probabilistic test to get the false positive probability all the way down to zero. And you need to use a method that has zero percent false positive chance to claim a world record. The EFF-administered monetary prize for a record-breaking prime number, for example, requires "the primality proof must be a deterministic proof..." [1] So you can't use probabilistic methods. [1] https://www.eff.org/awards/coop/rules https://www.eff.org/awards/coop/rules
  - mistercow 13y ago
    I know (or think) that most record primes these days are Mersenne primes due to the relative ease of testing their primality. What I wonder is if probablistic tests could be used to find candidates for very large non-Mersenne primes before testing them using AKS. Or is o̅(log⁷·⁵(n)) just infeasible for those sizes of numbers?

by csense 13y ago

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

Someone 13y ago

"Finding random big primes p and q is easy" For those wondering why then, it is news when a new largest prime is found: there are gradations of 'big'. The big primes used in cryptography have fewer than 1000 bits, or about 300 digits. That is not what one (nowadays) calls 'large' in the field of finding the largest prime. There, one laughs at numbers of a million digits (the largest known prime has 17,425,170 digits)

csense 13y ago
Also, for a practical engineering problem, like writing an RSA implementation which will be used in an SSL implementation which will encrypt credit card numbers on an e-commerce website, it is okay to use probabilistic tests which have a tiny chance of a false positive (the test claims a number is prime when it is actually composite). You can generally repeat a probabilistic test with different parameters to make the probability of a "false positive" prime number very tiny -- like .000 000 000 001 -- while still staying within the computational budget manageable on an ordinary computer (obviously, a practical Internet security scheme should be able to complete its computations in a second or two on a typical desktop, laptop, server, and smartphone). So probabilistic tests are good enough for practical purposes, but you need a non-probabilistic test to get the false positive probability all the way down to zero. And you need to use a method that has zero percent false positive chance to claim a world record. The EFF-administered monetary prize for a record-breaking prime number, for example, requires "the primality proof must be a deterministic proof..." [1] So you can't use probabilistic methods. [1] https://www.eff.org/awards/coop/rules https://www.eff.org/awards/coop/rules
- mistercow 13y ago
  I know (or think) that most record primes these days are Mersenne primes due to the relative ease of testing their primality. What I wonder is if probablistic tests could be used to find candidates for very large non-Mersenne primes before testing them using AKS. Or is o̅(log⁷·⁵(n)) just infeasible for those sizes of numbers?