Why should the RSA private exponent have the same size as the modulus?

Question

Consider the generation of an RSA key pair with a given modulus size $n$ and a known, small public exponent $e$ (typically $e = 3$ or $e = 65537$). A common method is to generate two random primes numbers of size $n/2$ (or very close), and check at least that they are probable primes and that $\mathrm{gcd}(e, (p-1)(q-1)) = 1$. Once $p$ and $q$ have been vetted, from what I've seen, the other parameters (the private exponent $d$, or the CRT parameters if desired) are computed but not subject to any extra check.

I have met an extra requirement whose purpose I don't understand. In the Référentiel Général de Sécurité (something like the French equivalent of FIPS), annex B1 §2.2.1.1, a rule states:

[RègleFact-3] Private exponents must have the same size as the modulus.

What is the purpose of this rule? I know that small private exponents are bad, but here small means something like $d \lt N^{0.5}$. Even allowing for a security margin, this is a far cry from requiring $d \gt N/2$. What can go wrong if the size of $d$ is not verified (so the probability that $d \lt a N$ is close to $a$)?

Answer 1

Well, first off, it appears that these requirements are a bit confused. If the requirement is that for a given modulus $N$ and public exponent $e$, that the corresponding private exponent $d$ satisfies $d > N\!/2$, that rules out all public keys (!). You can see that from the necessary and sufficient relation $de = 1 \mod \operatorname{lcm}( p-1, q-1 )$, and so if $d$ exists (which it will of $e$ is relatively prime to $\operatorname{lcm}(p-1,q-1)$), then there exists a $d > 0$ with

$$d < \operatorname{lcm}(p-1, q-1) = (p-1)(q-1) / \!\operatorname{gcd}(p-1, q-1) \\ \le (p-1)(q-1) / 2 < N\!/2.$$

So, what other interpretation can we give to this rule? Well, one alternative is that you must use a private exponent $d > N\!/2$, even though it is not the smallest possible. However, as such a $d$ always exists, that actually mandates no requirements whatsoever on either $N$ or $e$ or the generated signatures or encrypted messages, and so cannot affect the security of a generated public key. In any case, when you're doing the RSA private operation, you generally use the CRT optimization, and so you don't actually use the value $d$ directly (and a larger than necessary value of $d$ would give you exactly the same CRT parameters).

The bottom line is that if you need to conform to these requirements, you'll need clarification on what the requirements actually are; the literal interpretation doesn't make sense.

Now, for your actual question: what is the purpose of this rule? Well, the document does go on to give this justification (if I remember my French correctly):

"Using specific private exponents (for example, small private exponents) to improve performance is forbidden because of practical published attacks in this area"

It appears that they are indeed worried about the published attacks against $d < N^{0.5}$, and possible refinements on that attack that might work for larger $d$.

As for the probability that a random public key will yield a small value of $d$, well, it turns out to be quite unlikely (if $e$ wasn't chosen specifically to make $d$ small). The easiest way to see this is to assume a modest $e$ (for example, 65537), and note that

$$d \cdot e > \operatorname{lcm}(p-1, q-1)$$

and hence

$$d > \operatorname{lcm}(p-1, q-1)/e \approx \frac{N}{e \cdot \gcd(p-1, q-1)}.$$

Hence, $d$ cannot be small unless $\gcd(p-1, q-1)$ is large; that is, if $p-1$ and $q-1$ share a large common factor. Because the probability of $\gcd(p-1, q-1) > k$ is $O(1/k)$, this means that in practice, a small $d$ never happens by chance.

Lastly, it isn't quite true that with other standards, there's no check on the value of $d$. For example, FIPS 186-3 does have the requirement that $d > 2^{\mathit{nlen}/2}$.

Answer 2

I conjecture that this rule is not being interpreted as requiring $d>N\!/2$ or $\lceil\log_2d\rceil=\lceil\log_2N\rceil$, but rather as a prohibition of any technique purposely shortening $d$.

To comfort that, shortly after the ambiguous prescription, we find under justifications something on the tune of: use of special secret exponents (small ones for example) in order to improve performance shall be avoided because of published attacks.

AFAIK, there is nothing wrong with $d$ being some dozens bits smaller than $N$; this happens more often than not when one selects the smallest $d$ such that $e\cdot d\equiv 1\pmod {\operatorname{LCM}(p-1,q-1)}$, which is the natural implementation of PKCS#1. However I have seen key generators that require $(p-1)/2$ and $(q-1)/2$ to be co-prime, which tends to make $d$ about the size of $N$.

Also: it is easy (and always possible) to make $d$ exactly the size of $N$, just by adding an appropriate multiple of $\operatorname{LCM}(p-1,q-1)$ to any valid private exponent.

Answer 3

The SOG-IS Agreed Cryptographic Mechanisms, which incorporates many elements from the French RGS, states (§4.1):

Note 28-SmallD. The size of $d$ should be close to the size of $n$. Note that this is guaranteed for a small $e$. We should have at least $d > 2^{n/2}$, where $n$ denotes the bitlength of the modulus.

This is the usual advice which has been explained elsewhere in this thread.

I suspect that the “same size” rule in the French document is an editorial error where “close in size” was meant, perhaps involving confusion at some point between $d > 2^{n/2}$ and $d > 2^n / 2$.

Answer 4

In academic mathematical french, numbers do not have a size. They are values. Only the representation of numbers can have a size (e.g. 357 has a size of 3 digits in base-10 representation).

Checking d > N/2 is a check of the value of d. Checking d fills a 256-byte buffer is about the size.

lcm(p-1, q-1) = ((p-1)*(q-1))/gcd(p-1, q-1) and can be much smaller than n=p*q

In practice, p-1 and q-1 could have some common factors, and d is computed mod lcm(...). Then it is usual to have the value of d much smaller than n=p*q.

The size of the binary representation of d could be smaller than the size of the binary representation of n by many bits. | log2(n) - log2(d) | > 20 is very frequent.

It is known that some attacks will succeed if approximately log2(d) < log2(n)/3. Many authors, many bounds.

You can't get d > n/2, even if gcd(p-1, q-1) == 2 (smallest possible common factor)

Unfortunately 1/e mod ((p-1)*(q-1)/2) is always < n/2

The French document you mention is using the word "taille" (size). Later the document is about p and q "la meme taille" (same size). The correct recommendation about values is p*p > 2^2048/2, q*q > 2^2048/2 . "La meme taille", in base 10 representation, can be different for numbers p, q you would accept as valid, reversely, 13 and 17 are the "same size"

Let us not be too picky, and consider "the position of the most significant bit in a base 2 representation" as a synonym for "the same size"?

The bureaucratic paradox in civil servant scripting, you can't solve it : d < n/2 by definition, no way to make them the "same size".

In a "courtelinesque" style, you should ask for a government change, so the author of the document will disappear, and the new prime minister will change the politics and decrees about "d".