Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 17 down vote favorite
4

As I understand it, the RSA algorithm is based on finding two large primes (p and q) and multiplying them. The security aspect is based on the fact that it's difficult to factor it back into p and q. Now, since RSA keys are so large (often 1024 bits and above), the primes have to be at least half that (at least 512 bits then). Such large primes would be difficult to generate (you'd have to check many, many numbers and try to factor each of them), so I understand that the typical approach is to use pre-generated lists of large primes.

But doesn't that make the key very easy to crack? Even if the list container 1,000,000 primes (which I find unlikely), checking all the combinations would only take a couple of hours on a typical desktop computer.

Which part have I misunderstood?

share|improve this question
3  
+1. had the same mental barrier. factoring out two primes from the product is very hard, but finding large primes is quite easy. it's not that intuitive though. – Yoav Aner Mar 1 '12 at 14:23
Hi @Vilx, while this question is on topic here, it still would be even more at home at our brother site - Cryptography. – AviD Mar 2 '12 at 12:46
For more background about why using lists of primes would be bad see this blogentry and the paper "Ron was wrong, Whit is right". How big primes can be found is described in the answers to this question. – Someone Mar 2 '12 at 14:59

migrated from security.stackexchange.com Mar 2 '12 at 12:47

2 Answers

up vote 18 down vote accepted

You don't use a pre-generated list of primes. That would make it easy to crack as you note. The algorithm you want to use would be something like this (see note 4.51 in HAC, see also an answer on crypto.SE):

  1. Generate a random $512$ bit odd number, say $p$
  2. Test to see if $p$ is prime; if it is, return $p$; this is expected to occur after testing about $Log(p)/2 \sim 177$ candidates
  3. Otherwise set $p = p+2$, goto 2

There are other methods to generate primes (e.g., do step 1, if step 2 fails goto step 1). The method I outlined is what OpenSSL uses though.

For an official, public standard on RSA key generation, see FIPS 186-3, section 5.1 and Appendix B.3.1.

share|improve this answer
And it doesn't take 10 weeks to produce a prime? At those magnitudes I'd expect primes to be lightyears apart! Also - how do you test for primality? Last I heard brute-force was the only actual way (with a few optimizations, but still), which means something on the order of O(2^512). – Vilx- Mar 1 '12 at 13:29
3  
@Vilx-, remember, OpenSSL does exactly what I described, so it must be quick. There are plenty of probabilistic primality tests (see the HAC doc I linked to). One is Miller-Rabin, which is very quick. With those tests, you can get arbitrarily close to a probability of 1 that p is prime. Finally, the distribution of primes is dense enough to make the described algorithm fairly quick (see en.wikipedia.org/wiki/Prime_number_theorem). – mikeazo♦ Mar 1 '12 at 13:48
Oh, nice. I didn't know that. Thanks! :) – Vilx- Mar 1 '12 at 13:53
@Vilx Large primes are surprisingly common. You only need to look at a few hundred candidates. – CodesInChaos Mar 1 '12 at 14:15
6  
@Vilx- According to the prime number theorem, the distance between prime numbers near x is approximately ln(x). For a 1024-bit number, this is 1024*ln(2), or approximately 710. Thus, checking every odd number near some large 1024-bit number, we'd expect to have to check about 355 numbers to find a prime. For a computer, this is practically nothing. – BlueRaja - Danny Pflughoeft Mar 1 '12 at 16:50
show 2 more comments
up vote 1 down vote

The key is that the test used by crypto libraries to determine whether a number is prime is probabilistic. That is, if the test uses a randomly-chosen value (the "witness") which serves as the basis for the test. If the test passes, then the number is probably prime, but possibly not. We can repeat the same test with a new "witness", and if the test passes again then we have increased our certainty. We can continue to re-test as many times as we want until we've reached the level of certainty that we need.

It is possible, therefore, that the primes used are not actually prime. But it's unlikely enough that it doesn't significantly affect the security of the key.

share|improve this answer
Fast probabilistic testing is only half the answer, though. It's convenient primes are so dense at density $\frac{1}{\ln{n}}$, otherwise it wouldn't matter that we can check for primality quickly because we'd never actually pick a prime to check and validate. – Thomas Dec 11 '12 at 18:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.