12
$\begingroup$

The RSA public key encryption requires two very large prime numbers as part of its encryption process that serve as secrets. These are typically generated with cryptographically secure random number generators of some kind.

However, random number generators generate random bits; they don't specifically generate primes; and proving that a number is prime would require attempting to factor it -- the very problem that makes RSA hard.

How are the prime numbers found for use in RSA?

$\endgroup$
2

4 Answers 4

11
$\begingroup$

Very important:

Determining whether an integer is prime is significantly easier than factoring it (at least in the current state of our knowledge). We can easily determine whether integers having thousands of decimal digits are prime, but such integers are far beyond the reach of current factoring algorithms.

Now to answer your question: "plain" RSA does not specify how the prime numbers are to be generated. For any particular implementation, you would need to look at its source code or documentation to see how it does it. A popular method is the "generate-and-test" paradigm:

  1. Generate a random number of appropriate length.
  2. See if it is prime, using either a probabilistic or a deterministic test depending on your level of paranoia. If it is prime, you have your prime. Otherwise, go back to step 1.

A simple application of the prime number theorem can give you an estimate of the probability that the number you picked is prime (depending on its length). This is generally not the same thing as the probability that your primality test will consider it prime, however, if you are using a probabilistic test.

I'll leave it to you as an exercise to implement this in your favourite CAS (e.g., PARI/GP or Sage) and see how it works in practice.

EDIT:

The two "tricks" given in the other answer will not make any difference in most cases.

  • Ensuring that we only give odd numbers to the primality test is useless: any decent primality test will immediately discard even numbers, precisely so as to not waste time on them.
  • Adding $2$ to the previous number instead of generating a new one from scratch also does not make any difference (at least on my machine). I can't see any reason to believe it should, either.
$\endgroup$
2
  • $\begingroup$ Ensuring that the number is odd will not save much time testing it, but it will save you some RNG calls. It's not a huge optimization, but it's trivial to make and does provide some benefit. $\endgroup$ Dec 28, 2014 at 23:17
  • $\begingroup$ Ditto on Ilmari's comment on using odd numbers. Getting entropy might be very expensive (/dev/random on headless servers can hang for days once exhausted). I believe the +2 comment is describing PRIMEINC, which uses minimal entropy and can run faster, though is very non-uniform. How much faster depends mostly on how fast generating n-bit random numbers is for your implementation (also on the isprime and nextprime implementations of course). $\endgroup$
    – DanaJ
    Dec 29, 2014 at 4:50
7
$\begingroup$

You can use the TRIVIAL method, as shown by fkraiem. This generates uniform results, but does use a lot of RNG calls, as Ilmari pointed out. In practice this may be a non-issue or may be very important (e.g. getting results from /dev/random may stall; getting good entropy on an isolated embedded device may be difficult).

You can optimize this slightly by generating the inner $n-2$ bits and setting the first and last bits to one, which saves no time in any sane primality test, but uses less randomness on average.

There are some faster methods, such as Fouque and Tibouchi (2011 and 2014). These no longer generate with perfect uniformity, but bound it to an extremely small value. They use many fewer random bits.

I believe what Begueradj was getting at with his "+2" step is the PRIMEINC method, which is basically saying "generate a random value $t$, if $t$ isn't prime, then return ${\rm nextprime}(t)$." This is fast but very non-uniform. While nobody knows how to exploit this for the sizes of numbers we're talking about, it seems dubious to knowingly use a method which returns some numbers many orders of magnitude more often than others.

There are also the methods of Maurer and Shawe-Taylor. The latter is described in FIPS 186-4. Menezes et al. describes them both. These build up provable random primes -- no primality testing needed (though if you are implementing this I strongly recommend doing tests and assertions throughout the code -- including perhaps having it output a primality proof which is verified by other code). (Added 2017:) As mentioned in a comment, a GMP implementation of Shawe-Taylor is very similar in speed to the trivial method. Maurer's algorithm is perhaps 1.5x slower (it works harder to maintain diversity vs. S-T).

For primality testing, see FIPS 186-4 for some detailed info including detailed algorithms and numbers of tests recommended for given security levels. In practice, random composites of this size are highly unlikely to pass even a single Miller-Rabin test, hence you will almost certainly be doing only 1 test per composite, followed by the full suite for your probable prime.

Details of test performance optimization can be seen in something like this answer. The goal is to reject composites as fast as possible.

As fkraiem points out, primality testing is far, far easier than factoring. Some example times for 2048-bit (616 digit) numbers:

  • a single M-R test takes ~2 milliseconds
  • random primes using BPSW plus some extra M-R tests takes 0.25 seconds on a Macbook.
  • random constructive proven primes takes 0.25 - 1 second.
  • random BPSW prime plus generic proof (APR-CL or ECPP) in about 30 seconds

The last (random prime followed by proof) is almost never used, except perhaps for the smaller DSA primes (proving a 160-bit or 256-bit number is very fast). But this shows even for this size it can be done in a reasonable time.

$\endgroup$
5
  • 1
    $\begingroup$ Actually, in my experience, random constructive proven primes (using Shawe-Taylor) can be done about as fast as random primes validated using a handful of M-R tests. $\endgroup$
    – poncho
    Dec 30, 2014 at 0:36
  • $\begingroup$ @poncho, perhaps implementation dependent. I'm comparing against a modified Fouque/Tibouchi A1 which saves some time. Sounds worth a benchmark with as much in common as possible. $\endgroup$
    – DanaJ
    Dec 30, 2014 at 1:40
  • $\begingroup$ I compared a MR-based approach using a sieve (eliminating numbers with factors up to circa 500,000) to avoid numbers with small factors to a Shawe-Taylor algorithm modified to use a sieve; I believe a large sieve is actually faster than Fouque/Tibouchi (because it allows you to avoid more modular exponentiations). If you tried Shawe-Taylor without anything to avoid testing numbers with small factors, well, yeah, that's going to be slow. $\endgroup$
    – poncho
    Dec 30, 2014 at 4:53
  • $\begingroup$ I'd like to hear more. When you say sieve you mean doing efficient trial division (since you can't sieve the range)? There are a lot of places the implementations differ, making it complicated. My S-T does pretests as well so only does steps 14+ (FIPS 186-4 A.1.2.1.2) for numbers that will pass it. Speed will also depend on the SHA-1 as well. For F/T one can use do some divisibility tests using native ints before constructing the full number, speeding it up a lot. Lots of variables, but regardless, my S-T is ~2x slower than my FT solution, and Maurer is 4x slower. All could be faster. $\endgroup$
    – DanaJ
    Dec 30, 2014 at 7:06
  • 1
    $\begingroup$ Actually, Algorithm A.1.2.1.2 tests primes in the order $2(t_0+j)qp_0+1$ (where $t_0$ is the original value of $t$) for $j = 0,1,2,...$ (except for wraparound, which almost never happens). You can sieve values in that arithmetic order quite well. $\endgroup$
    – poncho
    Dec 30, 2014 at 15:48
4
$\begingroup$

By the end of 2009, RSA-768 has been cracked using the special number field sieve. This exploit forced RSA algorithms to have a key length not inferior to 512 bits (or 154 decimal numbers). This means that the generated prime numbers you are talking about must have at least 154 decimal numbers too. So the question we may ask: does enough prime numbers with 154 decimal numbers exist? This question is important because it is directly relevant to the security of RSA protocol.

The answer is yes. Why? We already know that the density of prime numbers around n is 1/ln(10154). What this does mean? It means if you take randomly 1000 numbers that have 154 decimal numbers, you will surely find at least 3 of them are prime numbers. As you can guess, you can get billions of prime numbers of this length.

This is said, we can summarize how the prime numbers are generated in practice, following these steps:

  • Choose RANDOMLY a number of 154 decimal digits (in terms of processors, understand this by choosing randomly a number of 512 bits length as in coin flopping method). Once this number is picked, we add to its length one last bit that we must set to 1. Why to add this bit? It is simply because it is easier and faster to process odd numbers.

  • This is done, the next steps consists in testing if the number we picked is prime or not using probabilistic tests which have proved to be faster than the algorithms of Fermat and Miller-Rabin.

  • If the probalistic test says this randomly picked number is not prime, then we must add 2 to it. The addition of 2 instead of 1 is used to obtain the following odd number. Then we perform the test of the second step above.

This method proved to be too fast to generate prime numbers for RSA algorithm. We need to test 300 times to get a prime number with the classic method of Miller-Rabin.

To give you a hint about how fast this can generate p and q, when you scroll down this page you will find an application that allows you to get p and q of 512 bits with a simple click.

$\endgroup$
2
  • 1
    $\begingroup$ Adding two to a non-prime to get the next candidate introduces a bias: the smaller of a twin pair is at least twice as likely to be found as the larger. Any bias in the way you generate random candidates is undesirable. $\endgroup$
    – ganbustein
    Dec 29, 2014 at 3:28
  • 2
    $\begingroup$ Which RSA schema? RFC3447 (PKCS #1 2.1) doesn't say this. FIPS 186-4 uses an the trivial method (which doesn't have this bias). RSA Labs initiatives 2.5.1 explicitly describes the trivial method. The 1978 CACM paper doesn't say how to generate them. $\endgroup$
    – DanaJ
    Dec 29, 2014 at 19:06
0
$\begingroup$

Maurer has an algorithm to generate random, almost uniformly distributed, k-bit primes that are provably prime, in contrast to schemes that generate highly probably primes (commonly employing the Miller-Rabin test). See A. J. Menezes et al., Handbook of Applied Cryptography, p.153 (freely available online). I have a Python code of that algorithm in http://s13.zetaboards.com/Crypto/topic/7234475/1/

$\endgroup$

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