78
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 11
    $\begingroup$ +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. $\endgroup$
    – Yoav Aner
    Mar 1, 2012 at 14:23
  • $\begingroup$ Hi @Vilx, while this question is on topic here, it still would be even more at home at our brother site - Cryptography. $\endgroup$
    – AviD
    Mar 2, 2012 at 12:46
  • $\begingroup$ 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. $\endgroup$
    – Someone
    Mar 2, 2012 at 14:59

5 Answers 5

Reset to default
69
$\begingroup$

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-4, section 5.1 and Appendix B.3.1.

Improve this answer
$\endgroup$
10
  • 3
    $\begingroup$ 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). $\endgroup$
    – Vilx-
    Mar 1, 2012 at 13:29
  • 11
    $\begingroup$ @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). $\endgroup$
    – mikeazo
    Mar 1, 2012 at 13:48
  • 2
    $\begingroup$ @Vilx Large primes are surprisingly common. You only need to look at a few hundred candidates. $\endgroup$
    – CodesInChaos
    Mar 1, 2012 at 14:15
  • 16
    $\begingroup$ @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. $\endgroup$
    – BlueRaja - Danny Pflughoeft
    Mar 1, 2012 at 16:50
  • 10
    $\begingroup$ The algorithm (as it stands now) generates primes with significantly biased distribution: primes with a long gap of composites just below them are significantly more likely than other primes. It is common to first choose a moderately large random secret $s$ and replace $p=p+2$ in step 3 by $p=p+2s$. It is enough that $s\approx\log_2(p)$ to mostly avoid that bias. In practice, $s$ is often the product of two much larger secret auxiliary prime $p_1$ and $p_2$ chosen such that we'll end with $p\equiv1\pmod{p_1}$ and $p\equiv-1\pmod{p_2}$. $\endgroup$
    – fgrieu ♦
    Jun 11, 2015 at 8:23
12
$\begingroup$

"I understand that the typical approach is to use pre-generated lists of large primes."

This is what I also thought. But I had not considered how many primes we might choose from. As it turns out you choose from ~2.8x10^147 primes with a 1024 bit RSA key and from about ~7.0x10^613 with a 4096 bit RSA key. Then you have up to 4.9x10^1227 possible pairs of primes. This amount is enormous, you shouldn't be able to just skim through a list then.

The original answer is at Stackoverflow from David Robinson:

As for whether collisions are possible- modern key sizes (depending on your desired security) range from 1024 to 4096, which means the prime numbers range from 512 to 2048. That means that your prime numbers are on the order of 2^512: over 150 digits long.

We can very roughly estimate the density of primes using 1 / ln(n) (see here). That means that among these 10^150 numbers, there are approximately 10^150/ln(10^150) primes, which works out to 2.8x10^147 primes to choose from- certainly more than you could fit into any list!!

So yes- the number of primes in that range is staggeringly enormous, and collisions are effectively impossible. (Even if you generated a trillion possible prime numbers, forming a septillion combinations, the chance of any two of them being the same prime number would be 10^-123).

Improve this answer
$\endgroup$
9
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • 2
    $\begingroup$ 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. $\endgroup$
    – Thomas
    Dec 11, 2012 at 18:22
  • $\begingroup$ @tylerl: On security.SE, I think ECDHE is more common than ECDHA. $\:$ $\endgroup$
    – user991
    Jun 30, 2013 at 10:17
  • 1
    $\begingroup$ @RickyDemer I think you might have attached this comment to the wrong answer (and wrong site). $\endgroup$
    – tylerl
    Jun 30, 2013 at 19:58
  • $\begingroup$ Well, sort of. $\:$ I don't have an account on $\:$ security.SE . $\;\;\;$ $\endgroup$
    – user991
    Jun 30, 2013 at 20:51
  • $\begingroup$ Actually, there are deterministic ways to find large primes that are about as fast as the probabilistic tests. Hence, the fact that probablistic methods are generally used isn't that relevant to why RSA key generate is the speed that it is. $\endgroup$
    – poncho
    Jul 29, 2013 at 20:12
1
$\begingroup$

You can use the next_prime function available in the GMP library, after generating a random large number. Here's the link : https://gmplib.org/manual/Number-Theoretic-Functions.html

Improve this answer
$\endgroup$
5
  • 5
    $\begingroup$ It's better not to do that. You will introduce a bias in the prime numbers that get selected. $\endgroup$
    – SquareRootOfTwentyThree
    Jul 11, 2015 at 19:54
  • $\begingroup$ @SquareRootOfTwentyThree While it does introduce a bias toward primes with a large gap between it and the previous prime, the bias is extremely small and is not thought to be exploitable. $\endgroup$
    – forest
    May 26, 2019 at 23:23
  • $\begingroup$ @forest it can exploited via side channels $\endgroup$
    – SquareRootOfTwentyThree
    May 28, 2019 at 8:35
  • $\begingroup$ @SquareRootOfTwentyThree Skimming the paper at least, it looks like that attack is applicable to both methods of prime generation. $\endgroup$
    – forest
    May 28, 2019 at 9:04
  • $\begingroup$ "The most rigorous [countermeasure is] [...] to generate each prime candidate independent from its predecessors (→Pseudoalgorithm 1)" $\endgroup$
    – SquareRootOfTwentyThree
    May 28, 2019 at 20:46
0
$\begingroup$

I have implemented Maurer's algorithm of generating random provable primes (see Menezes et al., Handbook of Applied Cryptography) in Python, which is, as comparison showed, only moderately slower than via usage of the test of Miller-Rabin (which can deliver only primes that are highly probably prime) for primes of sizes commonly employed for RSA currently in practice. Python is interpreted hence runs not very fast but that doesn't matter much in the present context for the common people who need only to generate a few large primes for RSA etc. My code PROVABLEPRIME is available at: http://s13.zetaboards.com/Crypto/topic/7234475/1/

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ That's great. But... it doesn't really answer the question. :P $\endgroup$
    – Vilx-
    Oct 17, 2015 at 18:48
  • $\begingroup$ @Vilx: You are right. I was rather directly commenting on the post of mikeazo above, which, I presume, somehow answered your OP. $\endgroup$
    – Mok-Kong Shen
    Oct 18, 2015 at 10:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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