31
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ $e$ and $d$ can't both be small. $\endgroup$
    – Jason S
    Commented Dec 28, 2018 at 13:21

9 Answers 9

Reset to default
30
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Maarten Bodewes ♦
    Commented Jan 20, 2012 at 15:19
  • 8
    $\begingroup$ @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. $\endgroup$
    – Thomas Pornin
    Commented Jan 20, 2012 at 15:32
  • 1
    $\begingroup$ To cite Don Coppersmith's 1997 paper "Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities": "RSA encryption with exponent 3 is vulnerable if the opponent knows two-thirds of the message." While this may not be a problem if RSA-OAEP padding scheme is used, the PKCS#1 padding scheme is vulnerable if public exponent e=3 is used. $\endgroup$
    – FaST4
    Commented Feb 1, 2018 at 9:41
18
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 10
    $\begingroup$ $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. $\endgroup$
    – fgrieu ♦
    Commented Jan 20, 2012 at 15:36
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Edit: added quote

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Apr 25, 2013 at 7:43
  • $\begingroup$ 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? $\endgroup$
    – staafl
    Commented Apr 25, 2013 at 11:20
  • $\begingroup$ Sorry, I meant this is not a good reason not to pick a low value for $e$. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Apr 25, 2013 at 12:05
  • $\begingroup$ 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. $\endgroup$
    – staafl
    Commented Apr 25, 2013 at 15:23
  • 1
    $\begingroup$ 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$…) $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Apr 26, 2013 at 17:29
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Commented Feb 26, 2014 at 18:32
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Why a downvote? $\endgroup$
    – hrishikeshp19
    Commented Jan 26, 2012 at 4:37
  • 1
    $\begingroup$ downvote without a comment is lame. $\endgroup$
    – hrishikeshp19
    Commented Jul 20, 2012 at 17:27
  • $\begingroup$ Even with the repeated squaring, I think computation of x^65535 requires 17 multiplies, as compared with two multiplies to compute x^3. That's more than a 5:1 speed difference, which I'd regard as pretty significant. $\endgroup$
    – supercat
    Commented Oct 12, 2018 at 19:56
0
$\begingroup$

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.

(adding in)

An exponent of 17 is not bad, either and is also a common compromise made.

Jon

Improve this answer
$\endgroup$
1
  • 6
    $\begingroup$ 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. $\endgroup$
    – Paŭlo Ebermann
    Commented May 16, 2012 at 22:08
-1
$\begingroup$

$e$ and $d$ cannot both be small, because $ed$ must equal at least $(p-1)(q-1)+1$, which is very large if the scheme is to provide any security against factoring algorithms.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Actually, $ed$ must be equal to at least $lcm(p-1,q-1)+1$, which is potentially much smaller (if $gcd(p-1, q-1)$ is large). That said, deliberately selecting a $p, q$ with a large $gcd(p-1, q-1)$ appears to be a Bad Idea. In any case, if you care about the computational cost of the private operation, you ought to be using the CRT optimization; in which case the relative values are $ed_p > p$ and $ed_q > q$, however (again) deliberately selecting an $e$ with small $d_p, d_q$ values is a Bad Idea $\endgroup$
    – poncho
    Commented May 22, 2016 at 19:28
  • $\begingroup$ @poncho The question does not mention any optimisations, however. $\endgroup$
    – fkraiem
    Commented May 22, 2016 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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