101
$\begingroup$

What is the currently industry-standard algorithm used to generate large prime numbers to be used in RSA encryption?

I'm aware that I can find any number of articles on the Internet that explain how the RSA algorithm works to encrypt and decrypt messages, but I can't seem to find any article that explains the algorithm used to generate the p and q large and distinct prime numbers that are used in that algorithm.

Improve this question
$\endgroup$
0

6 Answers 6

Reset to default
78
$\begingroup$

The standard way to generate big prime numbers is to take a preselected random number of the desired length, apply a Fermat test (best with the base $2$ as it can be optimized for speed) and then to apply a certain number of Miller-Rabin tests (depending on the length and the allowed error rate like $2^{-100}$) to get a number which is very probably a prime number.

The preselection is done either by test divisions by small prime numbers (up to few hundreds) or by sieving out primes up to 10,000 - 1,000,000 considering many prime candidates of the form $b+2i$ ($b$ big, $i$ up to few thousands).

The deterministic prime number test by AKS is to my knowledge not yet used as it is slower and as the likeliness that an calculation error caused by the hardware is higher than $2^{-100}$.

Most smart cards offer a coprocessor for modular arithmetic with moduli from 1024 up to few thousand bits. The manufacturers often provide also libraries for RSA and RSA key generation using the coprocessor.

Improve this answer
$\endgroup$
6
  • 7
    $\begingroup$ Wow, the failure rate of a probabilistic algorithm is lower than the failure rate of deterministic algorithm - because we're at the scale where calculations errors by hardware matter. Did I get that right? $\endgroup$
    – bkoodaa
    Commented Jul 29, 2016 at 0:05
  • 3
    $\begingroup$ Hard to say, when this happens precisely. As the probabilistic algorithm runs faster than the deterministic one, it is less likely disturbed by cosmic rays. $\endgroup$
    – j.p.
    Commented Jul 29, 2016 at 8:21
  • $\begingroup$ @j.p.: I compared in Python Maurer's algorithm with that of Miller-Rabin and found that they are quite comparable for practical purposes. See s13.zetaboards.com/Crypto/topic/7234475/1/ $\endgroup$
    – Mok-Kong Shen
    Commented Jul 29, 2016 at 10:45
  • $\begingroup$ @Mok-KongShen: "Testing it for primality first via trial division by an appropriate set of small primes and then via the Miller-Rabin test for diverse values of t" is not really a fast way to find primes. Using a sieve and one Fermat test (to the base 2) for what remains in the sieve before applying the Miller-Rabin tests should be at least double as fast. $\endgroup$
    – j.p.
    Commented Jul 30, 2016 at 15:53
  • 2
    $\begingroup$ @j.p. A better algorithm than AKS would probably be ECPP, since it can generate a primality certificate that can be used to rapidly verify that the integer is prime, negating the risk of hardware errors. $\endgroup$
    – forest
    Commented Dec 8, 2018 at 5:30
30
$\begingroup$

FIPS 186-3 tells you how they expect you to generate primes for cryptographic applications. It is essentially Miller-Rabin but it also specify what to do when you need extra properties from your primes.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ +1 for mentioning FIPS, which is different than what most implementations use. $\endgroup$
    – foobarfuzzbizz
    Commented Jul 13, 2011 at 13:26
  • 2
    $\begingroup$ FIPS 186-3 Appendix C , F $\endgroup$
    – ir01
    Commented Jul 13, 2011 at 17:07
  • 3
    $\begingroup$ The new one (July 2013) is FIPS 186-4. $\endgroup$
    – Der Kommissar
    Commented Jun 7, 2015 at 13:29
17
$\begingroup$

The problem of generating prime numbers reduces to one of determining primality (rather than an algorithm specifically designed to generate primes) since primes are pretty common: π(n) ~ n/ln(n).

Probabilistic tests are used (e.g. in java.math.BigInteger.probablePrime()) rather than deterministic tests. See Miller-Rabin.

http://en.literateprograms.org/Miller-Rabin_primality_test_%28Java%29

As far as primes for RSA goes, there are some additional minor requirements, namely that (p-1) and (q-1) should not be easily factorable, and p and q should not be close together.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Minor correction: the requirement isn't that p-1 (and q-1) shouldn't able to be easily factored; they could be twice a prime (and hence easily factorizable) without a problem. What they shouldn't be is smooth; that is, consist only of small (guessable) factors. $\endgroup$
    – poncho
    Commented Aug 27, 2011 at 1:14
  • 2
    $\begingroup$ Also, the "additional minor requirements" are automatically fulfilled by randomly generated primes (risks of hitting "bad primes" are much lower than, say, risks of having your PC munched to death by a crazed raccoon). Also, ECM factorization method can be seen as an extension of Pollard's $p-1$ method, against which you cannot defend with such tests, so you already rely on raccoon-sized low risks. $\endgroup$
    – Thomas Pornin
    Commented Aug 30, 2011 at 12:38
3
$\begingroup$

There are some tests to determines whether a given number is prime, like Miller–Rabin primality test. These algorithms determine whether a given number is prime with probability P.

Improve this answer
$\endgroup$
3
$\begingroup$

Instead of using probabilistic methods to generate large primes, as indicated in the other answers, one can (IMHO better) employ Maurer's algorithm of generating provable primes. I have a Python code implementing that algorithm, available at s13.zetaboards.com/Crypto/topic/7234475/1/

Improve this answer
$\endgroup$
1
$\begingroup$

What you could do, is use a Mill's constant for generation. Then, a test for primarity would be good anyways...(in case that not exact enough constant is chosen, so you could end up with non prime)

Mill's constant is such a number, that if powered to 3, and then powered to any N, where N is an usigned integer, we get value V wich, rounded down, is a prime.

So, let C be constant

C = 1.3063778838630806904686144926 ....

Then let 

L = C^3

Then choose any N from <0, infinite> , N is whole

prime = round down( L^N )

It has several drawbacks, such as the constant must be very accurate, if you do not have accurate enough constant, you will end up with composed number. However, it is proven that this ,,algorithm" always generates prime numbers.

Next drawback I heard about is that as you increase the exponent, more computation power will be needed. However, all you need to do is generate two of them, so it could do...

For further reading, here is what I found as reference. https://en.wikipedia.org/wiki/Mills%27_constant

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ I wasn't aware that this was an industry standard method for generating primes for RSA; for one, it's not really an algorithm (that is, it isn't unless you give a precisely accurate value for Mill's constant), and in addition, it's not great at generating (say) 1024 bit primes (as it can, at best, produce only one prime of that size). $\endgroup$
    – poncho
    Commented Jun 18, 2016 at 18:55

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