Requirements for RSA key parameters

Question

Recently I'm working with a chinese vendor for POS devices and their devices use 2048bit RSA keys for signing binaries. I had to generate a public/private pair (so I can sign my own binaries) and I did some research about this.

During the research I came across a recomendation from vendor's documentation: please, check if the very first byte of the Modulus (N) of the private key is greater than 0x80. If not, please, generate another key and do the same check.

Well, if you think about it, if it is less than 0x80 the key won't actually have 2048 bits but less than that. After all, RSA keys parameters are essentially big integers and zeros to the left in integers doesn't play any role into calculations. I even found that OpenSSL has code to test this condition (I guess at least).

Now, question: shouldn't the other parameters have exactly the same requirements? I mean, they are all integers and will be used in calculations like so. Why doesn't e.g. the private exponent is subject to the same checking?

Answer 1

Shouldn't the other parameters have exactly the same requirements?

Certainly not all other parameters. The vendor could set requirements for $e$, but they would be different. For the other key parameters, extra requirements would be unusual, and there could be a valid technical reason for them only if you are using gear (software or hardware) that the vendor supplied or prescribed for use when signing binaries or preparing a Certificate Signing Request.

The key parameters given to the vendor or which will get into the POS are those in the public part of the RSA key: $(N,e)$. There are legitimate interoperability requirements for these. However, the requirement "very first byte of the Modulus ($N$) of the private key is greater than 0x80" is not standard: it should be "..is not lower than 0x80", or it is there to work around some nasty bug, or it is a non-standard flag for something (e.g. allowing loading unsigned code when the first byte of $N$ is 0x80). The standard (FIPS 186-4 appendix B.3) requirement on $N$ for 2048-bit RSA key is $2^{2047}\le N<2^{2048}$ (and $N$ odd), not $2^{2047}+2^{2040}\le N<2^{2048}$, and I would not let that deviation unexplained.

The standard for $e$ is $2^{16}<e<2^{256}$ (and $e$ odd), with the upper limit often lower, but there's nothing common or reasonable that would require the first byte to be over a limit close to 0x80. $e=2^{16}+1$ is sometime required. $e=3$ was formerly popular in POS applications, for it speeds up card authentication and is perfectly fine when used with proper signature padding.

A private key should remain known by its legitimate holder only, and (for RSA and secure keys) there is no way to assess the value of its parameters from what should get known to the vendor or manipulated by the POS devices. Even the fact that $N$ has two rather than three prime factors is not testable by the vendor or POS. Thus a requirement on the private key is technically justifiable only for gear that uses the private key (in the application: to sign software or CSR). Starting with the more commonly enforced (list not limitative):

• The private key is expressed as $(N,e,d,p,q,d_p,d_q,q_\text{inv})$ per RSAPrivateKey in PKCS#1 v2.2 without the optional otherPrimeInfos, and thus $N$ has exactly two prime factors, rather than more.
• $N$ has exactly $k$ bits with $k$ in a discrete set (typically: multiples of some power of two in some range).
• $d<(p-1)(q-1)/\gcd(p-1,q-1)$ (limit in FIPS 186-4). That's often relaxed to $d<N$ (limit in PKCS#1v2.2), $d<2^k$, or other.
• $p$ and $q$ are odd and in range $(2^\frac{k-1}2,2^\frac k2)$. When enforced, the lower limit may vary, e.g. be relaxed to $\mathtt{B5_h}\,2^{\frac k2-8}$ or $2^{\frac k2-1}$. But even if such limits are standard, many hardware devices and most software are perfectly happy with $p$ and $q$ not of the same bit size.
• $q<p$ or vice versa (a requirement indicative of lousy practice).