Cfrgtkky

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?

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

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