# Can you recognize a low private exponent from a public key?

In the RSA cryptosystem, Wiener, Boneh and Durfee showed that low private exponents can be efficiently recovered. Is it possible to see from a public key alone whether the private exponent (d) is small? Is the public exponent (e) then necessarily large? Is it possible to have a small private exponent when e=65537?

• Is it possible? Sure, if you have a very small modulus. – forest Feb 19 '19 at 10:40
• (a) Yes: by running the Wiener–Boneh–Durfee attack! (b) Yes. (c) No. – Squeamish Ossifrage Feb 19 '19 at 16:07
• Qualification on (b) and (c): large/small relative to the exponent of the group, to fend off the goofy counterexamples of forest and poncho. – Squeamish Ossifrage Feb 19 '19 at 19:44

When generating keys, $$d$$ and $$e$$ are each others modular inverse:

• $$d \times e \equiv 1 \pmod{ \lambda(n)}$$
• $$d \times e = 1 + k \times \lambda (n)$$

Unless $$d = e = 1$$, this means that $$d \times e$$ is at least $$\lambda(n)$$, otherwise it would not "wrap around" to become $$1$$. So $$k$$ is at least $$1$$:

• $$d \times e \ge 1 + \lambda(n)$$

This means that at least one of $$d$$ and $$e$$ is at least $$\sqrt{1 + \lambda(n)}$$, otherwise they wouldn't multiple to be greater.

• $$d \ge \sqrt{\lambda(n)}$$, or $$e \ge \sqrt{\lambda(n)}$$

If we set $$e = 65537$$, it must be $$d$$ that is large. It is not possible to have a key with a low private exponent that also has a low public exponent. A key with a low private exponent has to have a public exponent that is at least $$\sqrt{\lambda(n)}$$.

• This gives a criterion for ruling out the possibility of a low private exponent, but not a criterion for recognizing a low private exponent. – Squeamish Ossifrage Feb 19 '19 at 15:30
• A different problem w.r.t. the question is: $\lambda(n)$ can't be determined from the public key, as asked. And it is possible to craft $n$ so that $\lambda(n)$ is much smaller than $n$, or even smaller than $\sqrt[k]n$ for sizable $k$. But if $n$ is the product of two distinct primes, we have $\lambda(n)>\sqrt n-1$ and a slight variant of the reasoning leads to $d>\sqrt n/e$. – fgrieu Feb 19 '19 at 18:32

Sjoerd is quite correct in that we always have either $$d \ge \sqrt{\lambda(n)}$$ or $$e \ge \sqrt{\lambda(n)}$$.

I would alternatively express this as $$d > p/e$$, where $$p$$ is the largest prime dividing $$n$$.

And, if we knew we had a normal RSA key, that'd be the answer.

However, there is something called multiprime RSA, where $$n$$ has 3 or more prime factors. And, we are unable to distinguish normal RSA and multiprime RSA from just the public key.

Once we allow that as a possibility, the bound on $$d$$ decreases considerably.

If we take it to the extreme, we find this example:

e = 65537
d = 92056403
m = 3*7*11*23*31*43*47*67*71*79*103*131*139*191*211*239*331*419*443*463*547*571*599*647*691*859*911*
967*1123*1327*1483*1871*2003*2311*2347*2531*2731*2927*3571*3911*4523*4831*6007*6271*7411*7591*
8779*8971*9283*10627*11731*13567*17291*21319*28843*35531*38039*43891*46411*51871*58787*62791*
72931*91771*102103*106591*111827*138139*336491*355811*461891*520031*782783*903211*1193011*
1939939*2348347*2624623*2897311*3233231*5138171*5679031*10546771*13123111*17160991*24609131*
50570411*62469331*83671043*107901571*113201999*130617691*200388631*205256371*232623887*
251013127*353992871*444100147*533666563*657415331*812101291*889444271*960837791*1436794591*
2481736111*3489358291*4035518719*4608938491*4885101607*5773301899*6725864531*9099699071*
13259561503*13805721931*15429924511*15670390867*20177593591*21168773627*27299097211*32262569431*
37472673811*42189513871


This m is a 2228 bit number, yet still has a comparatively small d with the standard e.

Now, such a number must be smooth (as every prime factor must satisfy $$p < de$$), and so is trivial to factor. However, I believe that is does answer the question "must a small e always imply a large d".