2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Is it possible? Sure, if you have a very small modulus. $\endgroup$ – forest Feb 19 at 10:40
  • $\begingroup$ (a) Yes: by running the Wiener–Boneh–Durfee attack! (b) Yes. (c) No. $\endgroup$ – Squeamish Ossifrage Feb 19 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 Ossifrage Feb 19 at 19:44
6
$\begingroup$

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)}$.

$\endgroup$
  • 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$ – Squeamish Ossifrage Feb 19 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 at 18:32
1
$\begingroup$

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".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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