So I want to ask is there any rules for choosing the two primes that's used to generaten in RSA? I mean clearly you can't choose 2 and another super big number, so I want to ask is there any restrictions like those two primes must >=2^(key_length-2) or something like that? (Supposing RSA is also using the first but to identify positive/negative.)

Also is there a restriction that requires n be bigger than a number, or otherwise you can also fill 0s at the beginning of a number and let it matches the bit length.

Or is there anything that though isn't consider as restrictions, but are recommended and been used in most situations?

  • 3
    $\begingroup$ The standard reference is FIPS 186-4 appendix B.3. It's an evolution of ANS X9.31:1998 (obsolete). $\endgroup$
    – fgrieu
    Jul 27, 2019 at 19:08
  • $\begingroup$ @fgrieu Is this for RSA? Cause from what I saw, the method they’re using to generate keys isn’t the same as what I found on Wikipedia $\endgroup$ Jul 28, 2019 at 1:29
  • $\begingroup$ In math by convention '(bit/digit) length' of a number is the number of bits/digits representing that number without leading zeros, or more than one sign bit/digit, unlike computing and programming where we often use pre-set sizes e.g. 32 or 64 bits. The original CACM paper actually suggested p,q (decimal) length differ by 'a few', but nearly every standard and implementation since makes each half the desired bit length of n. You definitely can't use 2 as an RSA prime because it makes one of the factor subgroups of $Z_n^*$ trivial thus it doesn't even work much less be secure. $\endgroup$ Jul 28, 2019 at 4:05
  • $\begingroup$ @Andrew.Wolphoe The method they use is a little different because FIPS is a government standard, whereas Wikipedia just provides one way to generate primes, not the "FIPS approved" method. $\endgroup$
    – forest
    Jul 28, 2019 at 8:24
  • $\begingroup$ @forest: note also that there is more than one FIPS-approved method. $\endgroup$
    – TonyK
    Jul 28, 2019 at 21:19


Browse other questions tagged or ask your own question.