Next: About this document ... Up: CS 490-04 Home Page

A Brief Summary of Attacks on RSA

Susan Landau, Sun Microsystems

Common Modulus Attack # 1:
Attack: Let Alice use , , Bob, , . Then if $\gcd(e_a, e_b)=1$ , Eve can decrypt message as follows:
Eve uses Euclidean Algorithm to compute and such that . Assume is negative (one of and must be, so just switch the two if is positive), then $(M^{-e_a})^{-r} (M^{-e_b})^{s}\equiv M \pmod{n}$ .
Moral: Never share a common modulus.
Encryption Exponent is less than the number of recipients.
Attack: Suppose Bob sends to of his friends: Alice, Bill, ..., Ethan. (We will do this for but the idea holds in general.)
Eve sees $M^3 \pmod{n_i}$ for Now (otherwise the recipients could not decode uniquely). Thus . But either the 's are relatively prime, in which case by using the Chinese Remainder Theorem, Eve can compute $M^3 \pmod{ n_1 n_2 n_3}$ or they are not, in which case Eve can factor some of the 's and compute that way. In the first case, Eve has $M^3 \pmod{ n_1 n_2 n_3}$ , where for each , so in Eve has a perfect cube over the integers. Eve can compute the cube root, and get 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 . 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 .
Attack: Eve asks Alice to sign . Alice refuses, so Eve computes a random number, and asks Alice to sign . Alice does so, and sends to Eve. Eve observes that $C^d = r^{ed} M^d = rM.$ Since Even knows she can divide by and get .
Moral: Never sign unknown messages, even ones that look random.
Alice chooses a low decryption exponent to save herself work in decrypting. Suppose 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 \pmod{\phi(n)}$ so there is an integer such that $ed+k\phi(n)=1$ . So $\left\vert \frac{e}{\phi(n)} - \frac{k}{d} \right\vert = \frac{1}{d\phi(n)}$ .
Thus is an approximation of $e/\phi(n)$ . Eve does not know $\phi(n)$ but she knows which is an approximation of it. Eve knows $\phi(n)=n-p-q+1$ and $p+q-1 < 3\sqrt{n}$ . Then $\left\vert n - \phi(n)\right\vert<3\sqrt{n}$ .
Thus $\left\vert \frac{e}{n} - \frac{k}{d} \right\vert = \left\vert \frac{ed-k\phi(n)... ...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 \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 is an extremely good approximation to (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 satisfying $\left\vert \alpha-a/b \right\vert < \frac{1}{2b^2}$ .
Moral: avoid decryption exponents less than $\frac{\sqrt[4]{n}}{3}$ . (Since is a 1024-bit integer, this means must be at least 257 bits.)
Small encryption exponent attack. This was shown above, with Bob sending of the same messages to 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} \pmod{n_i}$ , but Eve intercepts, e.g. Bob sends to Alice, to Bill, and to Carol. This is insecure due to:
Theorem (Hastad): Let $n_1, \ldots, n_k$ be pairwise relatively prime integers and let $n_{min} = \min_i (n_i)$ . Let be polynomials of maximum degree . Let $B=\prod n_i$ . Then if $B>(N_{min})^e$ , we can [quickly] find all common solutions to the .
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 be an RSA key. Let $m = \lfloor \frac{\log n}{e^2} \rfloor$ , and let be a message of $\log n - m$ bits. Let , be secret random numbers with and . Then given , Eve can recover .
If 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 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 , the second-least significant bit, etc.
Moral: Always take a fixed amount of time to sign.

About this document ...

Next: About this document ... Up: CS 490-04 Home Page

Joshua R Holden 2002-04-18