# RSA with small exponents?

Just to establish notation with respect to the RSA protocol, let $n = pq$ be the product of two large primes and let $e$ and $d$ be the public and private exponents, respectively ($e$ is the inverse of $d \bmod \varphi(n)$). Given a plaintext message $m$, we obtain the ciphertext $c = m^e \bmod n$; we subsequently decrypt the ciphertext by calculating $c^d \bmod n$.

Suppose I'm trying to implement RSA on a device with low computational power, and these exponentiations take too long. I decide to make my implementation run faster by choosing small values for $e$ and $d$ (e.g. in the tens or hundreds).

Are there efficient attacks against such an implementation?

-

First I must state that a secure RSA encryption must use an appropriate padding, which includes some randomness. See PKCS#1 for details.

That being said, $d$ is the "private exponent" and knowledge of $d$ and $n$ is sufficient to decrypt messages. $n$ is public (by construction) so $d$ must be kept private at all costs. If it is very small then an attacker can simply try values for $d$ exhaustively. On a more general basis, if the size of $d$ is lower than 0.29 times the size of $n$ (in bits) then there exists an efficient key recovery attack. The accepted wisdom is that trying to get a $d$ much smaller than $n$ is a bad idea for security.

On the other hand, there is no problem in having a small $e$, down to $e = 3$. Actually, with RSA as you describe, there is a problem with a very small $e$: if you use $e = 3$ and encrypt the very same message $m$ with three distinct public keys, then an attacker can recover $m$. But that's not really due to using a small $e$; rather, it is due to not applying a proper padding.

-
Hi Thomas, I think it is by now more accepted to use the 4th number of Fermat (0x010001 or 65537) as public exponent because of attacks when the number 3 is used. I understood this is less succeptible to attacks, while the number of calculations is limited because only two bits are set. Would you agree? – Maarten Bodewes Jan 20 '12 at 15:19
@owlstead: we use $65537$ mostly out of Tradition. The "attacks" with $e = 3$ are due to the lack of padding, and lack of padding is already a much bigger worry than that: to have an actual weakness due to $e = 3$ (compared to $e = 65537$), you have to thoroughly damage the algorithm (remove the padding step), which creates a bunch of other much bigger weaknesses. With proper padding, no problem with $e = 3$. However, I use $65537$ by default because it avoids questions, and it is not bad either. – Thomas Pornin Jan 20 '12 at 15:32

Are there efficient attacks against such an implementation?

Yes. You need to keep d larger than the 4th root of n=pq. Otherwise Wiener's Attack can be used to compute d.

-
$d>n^{0.25}$ is necessary but not sufficient. Boneh & Durfee prove that $d>n^{0.292}$ is necessary, and suggest this might need to be raised further. Purposely choosing $(p,q)$ or/and $e$ so that a short $d$ exists seems a bad idea. – fgrieu Jan 20 '12 at 15:36

You need to read some recent papers and their references to get up to speed with these attacks. Try "New Weak RSA Keys" by Nitaj and "Revisiting Wiener's Attack – New Weak Keys in RSA" by Maitra and Sarkar

Note that if you're trying to speed things up then there are almost certainly better solutions than trying to keep the exponents small.

-

In addition to the special case analytical attacks for small public exponents, I wouldn't use a low value of e due to Partial Key Exposure. See "Exposing an RSA Private Key Given a Small Fraction of its Bits.":

Our results show that RSA, and particularly low public exponent RSA, are vulnerable to partial key exposure.

-
What? Partial key exposure is an extremely unlikely event, and a large value of $e$ doesn't even completely prevent this attack. This is definitely not a good reason to pick a low value for $e$. Picking a low $d$ is a bad idea for other, more important reasons. – Gilles Apr 25 '13 at 7:43
1. I am arguing against low 'e', not for it. 2. Low 'e' values have lead to PKE successfully in the past, as you can see from the referenced paper. 3. What makes you think I'm arguing for picking a low decryption exponent? – staafl Apr 25 '13 at 11:20
Sorry, I meant this is not a good reason not to pick a low value for $e$. – Gilles Apr 25 '13 at 12:05
It is an additional reason. And PKE is not an 'extremely unlikely event' as you seem to believe. I saw an example of it a few days ago and I stand by my point unless you give me a counter-argument. – staafl Apr 25 '13 at 15:23
My first understanding of the paper was that the value of $e$ didn't make a practically significant difference — but upon rereading I realize I may have missed something. In situations where a side channel leaks some bits of $d$, the reconstruction attack only works for $e$ up to about $\sqrt{N}$, right So does this mean we should always pick a random $e \gt \sqrt{N}$? (That is often difficult in practice as many implementations out there only support small values of $e$…) – Gilles Apr 26 '13 at 17:29

Yes, you can use small public exponents (e.g., 3 is fine), as long as you never encrypt the same plaintext under three or more RSA public keys with exponent 3. Otherwise, there is "Hastad's broadcast attack" that can extract the plaintext, without needing to factor the modulus.

Also, ensure that the private exponent is large enough, as pointed out Jason S (which will usually be the case, if primes are chosen randomly).

-
That's very dangerous advice. Hastad's broadcast attack only applies when there is no random padding, and many other things can go wrong regardless of $e$ when no random padding (or worse no padding at all) is used in RSA encyption. On the contrary, in any application of RSA, if there is something (other than conformance to the diktat of some authority) to worry about with $e=3$, that's a strong indication that something other then $e$ needs to be seriously improved. – fgrieu Feb 26 '14 at 18:32

hrishikeshp19 suggests repeated squaring, which is essential if you aren't doing it already. Also "Montgomory Multiplication" can also be used to speed up these computations. Beware though, as improper implementations give way to a timing attack. Actually, if you are implementing RSA yourself there are a number of intricacies that you need to pay attention to. Such implementations are best not left to an amateur.

-

Even if your computing power is small, you can use larger exponents. There are some algorithms such as repeated squaring method which help you to compute larger exponents a lot faster than brute force.

Repeated squaring method can also be applied in RSA by building up one bit at a time, so we can double the exponent of a number in one go. So the number of multiplication we have to make is log n (where n is an exponent) compared to n multiplications for normal computation of exponent of the number.

-
Why a downvote? – hrishikeshp19 Jan 26 '12 at 4:37
downvote without a comment is lame. – hrishikeshp19 Jul 20 '12 at 17:27

If you're really in a constrained environment, use an exponent of 5, and that will be okay. I raise an eyebrow about being so constrained that you can't use 64K+1 (65537), but I'm not going to debate it. The best answer to your dilemma (assuming you really have it) is to use 5.

Do you have any reasons for specifically $5$ (instead of, for example, $3$)? Also, you should note that this only applies to the public exponent, not the private one. – Paŭlo Ebermann May 16 '12 at 22:08