6
$\begingroup$

What is the current standard of random bit generators? RSA relies on two large prime numbers, and I am wondering what is the algorithm used to generate such numbers?

$\endgroup$
4
  • $\begingroup$ There is no single standard for random number generators. That said, the random numbers normally need to be tested against NIST test specifications before they are considered secure. More information here $\endgroup$
    – Maarten Bodewes
    Aug 21, 2013 at 21:38
  • 2
    $\begingroup$ Are you asking how to take low-entropy numbers, like timing from a hard drive or network connection and turn it to a random bitstream, or are you asking how to take a random bitstream and turn it into two primes? $\endgroup$
    – Nick ODell
    Aug 21, 2013 at 23:25
  • 1
    $\begingroup$ The appropriate number of random bits is obtained from a cryptographically secure pseudo-random number generator, then is tested for primality. If it's not prime, it's discarded and another set of bits is obtained. See en.wikipedia.org/wiki/Primality_test for more details. $\endgroup$ Aug 22, 2013 at 3:44
  • $\begingroup$ Thanks. Is there a specific pseudo-random number generator that cryptographic community believe to best fit for RSA or any other cryptosystems? $\endgroup$
    – Faith
    Aug 22, 2013 at 3:50

1 Answer 1

10
$\begingroup$

I'm not sure whether you'd prefer a good academic intro, some practical guides on implementation, or some breaking research in this area, so here are my recommendations for each:

As Loebenberger and Nüsken note, several different approaches to RSA key generation are scattered throughout several standards, including IEEE 1363-2000, FIPS 186-3/4, ANSI X9.44, and ISO/IEC 18033-2.

Below is an overview of some of the standards out there, though most readers will be better off stopping here and just reading one of the above three links.

I. PKCS#1 (aka RFC 3447) (historical note)

PKCS#1--developed by RSA before submission as RFC 3447--is maybe the canonical certification defining RSA implementation, and provides absolutely no guidance on the generation of random primes.

II. IEEE 1363-2000

I'm reluctant to say too much about 1363-2000 (aka P1363) since the IEEE standard is not free. If you have a copy, key generation for RSA is detailed in Sec. A.16.11, with references to subsections of A.15 for primality testing. Generation of provable primes, probable primes, and recursive construction of primes with an implicit proof of primality are each mentioned, the last of these citing Maurer ("Maurer, U. M. “Fast Generation of Prime Numbers and Secure Public-key Cryptographic Parameters,” Journal of Cryptology 8 (1995), pp. 123-155.") and Mihailescu (Mihailescu, P. “Fast Generation of Provable Primes Using Search in Arithmetic Progressions,” Yvo G. Desmedt, Ed., Advances in Cryptology, CRYPTO ‘94, Lecture Notes in Computer Science 839 (1994), Springer-Verlag, pp. 282-293.) from the mid-90s, as well as Shawe-Taylor (Shawe-Taylor, J. “Generating Strong Primes,” Electronics Letters 22, July 1986, pp. 875-877.), who may also warrant a read for the exhaustive study of the topic.

Most notably, the document recommends a fantastic academic primer to this subject, Chapter 4 of Menezes, van Oorschot, and Vanstone's Handbook of Applied Cryptography (Menezes, A., van Oorschot, P., and Vanstone, S. Handbook of Applied Cryptography, CRC Press, Boca Raton, Florida, 1996.). The HAC, by generosity of the authors and publisher, is available completely free online, and is the best conceptual overview of the issue raised in this question.

Now that I've danced around it enough, the general idea in 1363 is to generate numbers of the form $2k + 1$ for some random $k$ before testing the result for primality. There's a longer algorithm for generating "strong" primes, where a strong prime $p$ satisfies:

  • $p ≡ 1\ ($mod$\ r)$ for some large prime $r$,
  • $p ≡{}–1\ ($mod$\ s)$ for some large prime $s$, and
  • $r ≡ 1\ ($mod$\ t)$ for some large prime $t$.

This maybe begs the question a bit, since you asked about random bit generation, and some random k is required for the basic algorithm here. That part of the algorithm isn't specified likely because it's no longer a component of RSA, we're assuming you have some method to generate random numbers, maybe through a hardware random number generator. This is going to come up in all the methods, generating random bits is prerequisite and separate from generating random primes.

(If you intended to ask primarily about how random bits are generated rather than how random primes are derived from those bits, then at this point you may want to look at hardware random number generators (or more likely your OS, ie, /dev/urandom/ on Unix-like systems or CryptGenRandom in Windows).)

IEEE 1363 also points readers to ANSI X9.31-1998 for "an auditable method of generating primes by incremental search." X9.44 may include the updated version you'd be looking for.

III. FIPS 186-4

(Note: You may see references to 186-3, but this standard was updated in July 2013 to 186-4.)

RSA key generation is introduced in Sec. 5.1 (pp. 22-3), which was updated in -4 to guide the retention (or preferably, destruction) of seeds used to generate random primes. The real meat you're looking for is in Appendix B.3.2-6 (pp. 53-61) though. And while this section is too large to fully detail here, this appendix is probably your best resource for practical implementation guidelines on this question, as it is freely available, clearly written, and very comprehensive as to different methods based on which types of primes you wish to generate (provably prime? probably prime? even... probable primes with conditions based on auxiliary provable primes? et al.). All methods include readable algorithms.

NIST also references ANSI X9.31 and ANSI X9.80, as well as Special Publication (SP) 800-90A, Recommendation for Random Number Generation Using Deterministic Random Bit Generators (RBGs), and, SP 800-57, Recommendation for Key Management, further detailing the specifications for suitable RBGs.

In a nutshell, RBGs are rated by security strength, and different applications will require different security strengths. Non-deterministic is better than deterministic? You asked for "state of the art," which could mean the RBGs with the highest security strength, but actually, the real art is allocating the appropriate security strength to the task at hand without going overboard, and in auditing. Auditing isn't sexy, but it's really the important bit.

IV. ANSI X9.44, X9.31, and X9.80, ISO/IEC 18033-2, etc.

Like IEEE 1363-2000, also not free. I think NIST incorporated the relevant ANSI material into FIPS 186-4, though.

NIST's pubs are free, and arguably more straightforward than the publications from the other shops anyway.

V. Other Recent Research

I believe the consensus developed over the last couple decades that the primes should be selected of roughly equal size, as it allows some simplicity in implementation, and the drawbacks have been found insignificant. (I'll dredge up a cite for the comments if there's interest.)

Loebenberger and Nüsken's "Notions for RSA integers" from late 2012 compares some of the methods listed in the standards. It provides a solid baseline for analysis in an area that's easily neglected, and provides through its citations a great review of current literature. It's where I'd head next if I wanted to read every recent piece of research on the topic. Tracked on arXiv as arXiv:1104.4356 [cs.CR].

$\endgroup$

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.