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 '19 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$ – Andrew.Wolphoe Jul 28 '19 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$ – dave_thompson_085 Jul 28 '19 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 '19 at 8:24
  • $\begingroup$ @forest: note also that there is more than one FIPS-approved method. $\endgroup$ – TonyK Jul 28 '19 at 21:19

Browse other questions tagged or ask your own question.