$up$ $previous$
Up: MA479 / CSSE479 Schedule Page

A Brief Summary of Attacks on RSA

Susan Landau, Sun Microsystems

Common Modulus Attack # 1:
Attack: Let Alice use n, e_a, Bob, n, e_b. Then if gcd(e_a, e_b) = 1, Eve can decrypt message as follows:
Eve uses Euclidean Algorithm to compute r and s such that e_ar + e_bs = 1. Assume r is negative (one of r and s must be, so just switch the two if r is positive), then (M^-e_a)^-r(M^-e_b)^s $\equiv$ M(mod n).
Moral: Never share a common modulus.
Encryption Exponent e is less than the number of recipients.
Attack: Suppose Bob sends M^e to e of his friends: Alice, Bill, ..., Ethan. (We will do this for e = 3 but the idea holds in general.)
Eve sees M³(mod n_i) for i = 1, 2, 3. Now M < n_i (otherwise the recipients could not decode M³ uniquely). Thus M³ < n₁n₂n₃. But either the n_i's are relatively prime, in which case by using the Chinese Remainder Theorem, Eve can compute M³(mod n₁n₂n₃) or they are not, in which case Eve can factor some of the n_i's and compute M that way. In the first case, Eve has M³(mod n₁n₂n₃), where M < n_i for each i, so in M³ Eve has a perfect cube over the integers. Eve can compute the cube root, and get M back.
Moral: Never send the same message to as many recipients as your encryption exponent. Another way to say this: Use a large encryption exponent.
Eve asks Alice to sign M. Alice refuses, so Eve asks Alice to sign a seemingly random message. Alice does this, and Eve uses this to obtain Alice's signature on M.
Attack: Eve asks Alice to sign M. Alice refuses, so Eve computes r a random number, and asks Alice to sign C = r^eM. Alice does so, and sends C^d = (r^eM)^d to Eve. Eve observes that C^d = r^edM^d = rM. Since Even knows r she can divide c by r and get M^d.
Moral: Never sign unknown messages, even ones that look random.
Alice chooses a low decryption exponent to save herself work in decrypting. Suppose q < p < 2q and Alice picks d < $\sqrt[4]{{n}}$ /3. Eve can decrypt messages send to Alice.
Attack: Very short description of idea; for full description see Wiener, M.J. ``Cryptanalysis of Short RSA Secret Exponents,'' IEEE Transactions on Information Theory, V. 36, N. 3, May 1990, pp.188-190.
Observe that ed = 1(mod $\phi$ (n)) so there is an integer k such that ed + k $\phi$ (n) = 1. So $\left\vert\vphantom{ \frac{e}{\phi(n)} - \frac{k}{d} }\right.$ ${\frac{{e}}{{\phi(n)}}}$ - ${\frac{{k}}{{d}}}$ $\left.\vphantom{ \frac{e}{\phi(n)} - \frac{k}{d} }\right\vert$ = ${\frac{{1}}{{d\phi(n)}}}$ .
Thus k/d is an approximation of e/ $\phi$ (n). Eve does not know $\phi$ (n) but she knows n which is an approximation of it. Eve knows $\phi$ (n) = n - p - q + 1 and p + q - 1 < 3 $\sqrt{{n}}$ . Then $\left\vert\vphantom{ n - \phi(n)}\right.$ n - $\phi$ (n) $\left.\vphantom{ n - \phi(n)}\right\vert$ < 3 $\sqrt{{n}}$ .
Thus $\left\vert\vphantom{ \frac{e}{n} - \frac{k}{d} }\right.$ ${\frac{{e}}{{n}}}$ - ${\frac{{k}}{{d}}}$ $\left.\vphantom{ \frac{e}{n} - \frac{k}{d} }\right\vert$ = $\left\vert\vphantom{ \frac{ed-k\phi(n)-k n+k\phi(n)}{nd}}\right.$ ${\frac{{ed-k\phi(n)-k n+k\phi(n)}}{{nd}}}$ $\left.\vphantom{ \frac{ed-k\phi(n)-k n+k\phi(n)}{nd}}\right\vert$ = $\left\vert\vphantom{ \frac{1-k(n-\phi(n))}{nd} }\right.$ ${\frac{{1-k(n-\phi(n))}}{{nd}}}$ $\left.\vphantom{ \frac{1-k(n-\phi(n))}{nd} }\right\vert$ $\leq$ ${\frac{{3k\sqrt{n}}}{{nd}}}$ = ${\frac{{3k}}{{d\sqrt{n}}}}$ . Recall ed - k $\phi$ (n) = 1. Since e < $\phi$ (n) and d < ${\frac{{\sqrt[4]{n}}}{{3}}}$ , we get 3k < $\sqrt[4]{{n}}$ . Thus we get $\left\vert\vphantom{ \frac{e}{n} - \frac{k}{d} }\right.$ ${\frac{{e}}{{n}}}$ - ${\frac{{k}}{{d}}}$ $\left.\vphantom{ \frac{e}{n} - \frac{k}{d} }\right\vert$ $\leq$ ${\frac{{3k}}{{\sqrt[4]{n}}}}$ < ${\frac{{1}}{{d\sqrt[4]{n}}}}$ < ${\frac{{1}}{{3d^2}}}$ < ${\frac{{1}}{{2d^2}}}$ .
Thus k/d is an extremely good approximation to e/n (which Eve knows, unlike ${\frac{{e}}{{\phi(n)}}}$ ). It is sufficiently good that there are few candidates for it; it is a theorem (see Hardy and Wright for example) that given $\alpha$ = a/b that there is an efficient algorithm that outputs all a/b satisfying $\left\vert\vphantom{ \alpha-a/b }\right.$ $\alpha$ - a/b $\left.\vphantom{ \alpha-a/b }\right\vert$ < ${\frac{{1}}{{2b^2}}}$ .
Moral: avoid decryption exponents less than ${\frac{{\sqrt[4]{n}}}{{3}}}$ . (Since n is a 1024-bit integer, this means d must be at least 257 bits.)
Small encryption exponent attack. This was shown above, with Bob sending e of the same messages to e friends. But in fact small encryption exponents are insecure even if the message is padded to make it look different.
Suppose Bob sends C_i = f_i(M_i)^e_i(mod n_i), but Eve intercepts, e.g. Bob sends f₁(M) = (a₁M + b₁)³ to Alice, f₂(M) = (a₂M + b₂)³ to Bill, and f₃(M) = (a₃M + b₃)³ to Carol. This is insecure due to:
Theorem (Hastad): Let n₁,..., n_k be pairwise relatively prime integers and let n_min = $\min_{i}^{}$ (n_i). Let P_i be k polynomials of maximum degree e. Let B = $\prod$ n_i. Then if B > (N_min)^e, we can [quickly] find all common solutions to the p_i(x).
Moral: Always use a randomized pad to add to the message rather than an algebraic function.
Short Pad Attack
Alice sends a properly-padded message to Bob. Eve intercepts it. Not having received a reply, Alice resends, changing the padding function. Eve decrypts the message.
This result is due to a theorem of Coppersmith:
Theorem: Let (n, e) be an RSA key. Let m = $\lfloor$ ${\frac{{\log n}}{{e^2}}}$ $\rfloor$ , and let M be a message of log n - m bits. Let r₁, r₂ be secret random numbers with M₁ = 2^mM + r₁ and M₂ = 2^mM + r₂. Then given C₁, C₂ Eve can recover M.
If e = 3 the attack can be mounted so long as the pad is less than ${\frac{{1}}{{9}}}$ of the message length.
Moral: Use the recommended value of e being at least 65337. Thus encryption exponent is fine for standard moduli sizes.
Timing Attack
Eve asks the smart card to sign a number of messages, and measures the amount of time it takes to do so. By carefully measuring this time, and doing statistical correlations, Eve is able to determine, in order, the least significant bit of e, the second-least significant bit, etc.
Moral: Always take a fixed amount of time to sign.