# [cryptography] Modern replacement for ANSI X9.31 as far as RSA key generation goes?

Francois Grieu fgrieu at gmail.com
Tue Dec 14 16:51:51 EST 2010

```On 02/12/2010 18:33, I asked
> I'm in search for a current public standard (not
> necessarily free) specifying algorithms for RSA key
> generation, as a replacement for ANSI X9.31:1998;
> something with the range of the modulus and primes, and
> (mostly harmless and pointless) requirements on p-1,
> p+1, |p-q| and such, beside selecting random primes.

Got it: FIPS 186-3 (issued June 2009), appendix B.3
http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf

While not quite the same as ANSI X9.31:1998, it is similar
enough that (unless I err) an RSA key generated according
to FIPS 186-3 should *work* in an ANSI X9.31:1998 context,
subject to only one restriction:  the public modulus n has
the appropriate bit size; in particular, the resulting
bounds on p, q, and |p-q| are then exactly the same.

Among the many differences that I spotted:

FIPS 186-3 requires the public modulus n to be of k = 1024,
2048, or 3072 bits, while X9.31 allows k = 1024+256*s.

FIPS 186-3 requires e to be odd from 17 to 160 bits,
X9.31 allow e (including even) from 2 to k-160 bits.

FIPS 186-3 allows random primes for p and q when k>=2048,
while X9.31 always require safe primes.

X9.31 requires that the auxiliary prime factors p1 of (p-1)
and p2 of (p+1) be from 100 to 120 bits, whereas FIPS 186-3
specifies (when strong primes are used) a lower limit of 100,
140 or 170 bit depending on k, and defines an upper limit
on the sum of the bit size of p1 and p2, depending both on k
and whether p is a probable or provable prime (I wonder what
the rationale for that upper limit is). Same for q.

FIPS 186-3 requires a check that d (defined as the smallest
valid private exponent) is more than k/2 bits, although this
is acknowledged to be the case with high probability (I wonder
what the rationale is).

Francois Grieu

```