Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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$)?

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

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 lcm( p-1, q-1 )$, and so if $d$ exists (which it will of $e$ is relatively prime to $lcm(p-1,q-1)$), then there exists a $d > 0$ with

$d < \mathrm{lcm}(p-1, q-1) = (p-1)(q-1) / \mathrm{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 > \mathrm{lcm}(p-1, q-1)$

and hence

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

Hence, $d$ cannot be small unless $\mathrm{gcd}(p-1, q-1)$ is large; that is, if $p-1$ and $q-1$ share a large common factor. Because the probability of $\mathrm{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^{nlen/2}$.

share|improve this answer
add comment

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 {\text{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 $\text{LCM}(p-1,q-1)$ to any valid private exponent.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.