# What are the differences between X9.31 RSA operation and PKCS#1 RSA operation?

NIST and other - mainly older - standards often don't just mention PKCS#1 RSA algorithms but also X9.31 RSA algorithms.

What are the differences between X9.31 and PKCS#1 (v2.1) with regards to

1. key pair generation;
2. signature generation;
3. encryption (if applicable)?
• As X9.31 is payware it would be nice if answers do not directly rely on the availability of the standard. Jul 6, 2016 at 15:58
• From a quick look at this discussion it seems that X9.31 requires that $p$ and $q$ (where $pq = N$ the modulus) be strong primes. Jul 6, 2016 at 16:19
• @puzzlepalace: if, by "strong prime", you mean a prime where $(p-1)/2$ is also prime, well, X9.31 forbids such primes. See my answer for the ugly details... Jul 6, 2016 at 22:16

Well, there are indeed differences between the two standards, as you can see below:

1. key pair generation

X9.31 requires that $p-1$, $p+1$, $q-1$, $q+1$ all have prime factors between $2^{100}$ and $2^{120}$, and that $p$ and $q$ differ in at least one of the first 100 bits. These requirements are there to frustrate suboptimal factoring methods, and have been inherited (albeit in an adjusted form) by FIPS 186.

X9.31 requires that $e$ be between 2 (well, 3 for RSA) and $2^{k-160}$ (where the modulus is $k$ bits); that is, it forbids public exponents close to the size of the modulus.

PKCS #1 does not list any specific requirements on key generation.

1. signature generation

X9.31 lists a deterministic signature padding format of the form: 0x6bbbbbb...bbba[hash][hash code], where [hash] is where you insert the hash, [hash code] is a 16 bit value that encodes the hash type, and there are enough b digits to make the value precisely fill the block. BTW: since X9.31 assumes that the key size is one of a specific set of values, all of which are multiples of 4, there's no problem with the leading hex digit being '6'.

PKCS #1 lists rather different signature padding types; RSASSA-PSS (which is a probabilitic signature type), and RSASSA-PKCS1-v1_5 (which is deterministic).

I've never actually seen the X9.31 padding format used in practice.

1. encryption

X9.31 does not address encryption at all.

• PKCS1-v1_5 is 00 01 FF .... 00 [ASN.1 header that identifies hash][hash], which is semantically equivalent although not identical. The leading 00 works for any bitsize of modulus. Jul 7, 2016 at 2:37