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?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Is it possible? Sure, if you have a very small modulus. $\endgroup$– forestFeb 19, 2019 at 10:40
-
$\begingroup$ (a) Yes: by running the Wiener–Boneh–Durfee attack! (b) Yes. (c) No. $\endgroup$– Squeamish OssifrageFeb 19, 2019 at 16:07
-
$\begingroup$ Qualification on (b) and (c): large/small relative to the exponent of the group, to fend off the goofy counterexamples of forest and poncho. $\endgroup$– Squeamish OssifrageFeb 19, 2019 at 19:44
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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)}$.
-
1$\begingroup$ This gives a criterion for ruling out the possibility of a low private exponent, but not a criterion for recognizing a low private exponent. $\endgroup$ Feb 19, 2019 at 15:30
-
$\begingroup$ 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$. $\endgroup$– fgrieu ♦Feb 19, 2019 at 18:32
$\begingroup$
$\endgroup$
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".
