# An Attack on RSA With Exponent 3

### Learn more about an attack possible on RSA encryption using a very specific exponent — click here for the details!

Join the DZone community and get the full member experience.

Join For FreeAs I noted in this post, RSA encryption is often carried out reusing exponents. Sometimes, the exponent is exponent 3, which is subject to an attack we’ll describe below [1]. (The most common exponent is 65537.)

Suppose the same message *m* is sent to three recipients and all three use exponent *e*= 3. Each recipient has a different modulus *N _{i}*, and each will receive a different encrypted message

*c _{i}* =

*m*³ mod

*N*.

_{i}Someone with access to *c*_{1}, *c*_{2}, and *c*_{3} can recover the message *m* as follows. We can assume each modulus *N _{i}* is relatively prime to the others; otherwise, we can recover the private keys using the method described here. Since the moduli are relatively prime, we can solve the three equations for

*m*³ using the Chinese Remainder Theorem. There is a unique

*x*<

*N*

_{1}

*N*

_{2}

*N*

_{3,}such that:

*x* = *c*_{1} mod *N*_{1}*x* = *c*_{2} mod *N*_{2}*x* = *c*_{3} mod *N*_{3}

And *m* is simply the cube root of *x*. What makes this possible is knowing *m* is a positive integer less than each of the *N*s and that *x* < *N*_{1} *N*_{2} *N*_{3}. It follows that we can simply take the cube root *in the integers* and not the cube root in modular arithmetic.

This is an attack on “textbook” RSA because the weakness in this post could be avoiding by real-world precautions such as adding random padding to each message so that no two recipients are sent the exact same message.

## Python Example

Here, we’ll work out a specific example using realistic RSA moduli.

```
from secrets import randbits, randbelow
from sympy import nextprime
from sympy.ntheory.modular import crt
def modulus():
p = nextprime(randbits(2048))
q = nextprime(randbits(2048))
return p*q
N = [modulus() for _ in range(3)]
m = randbelow(min(N))
c = [pow(m, 3, N[i]) for i in range(3)]
x = crt(N, c)[0]
assert(cbrt(x) == m) # integer cube root
```

Note that `crt`

is the Chinese Remainder Theorem. It returns a pair of numbers, the first being the solution we’re after, hence the `[0]`

after the call.

The script takes a few seconds to run. Nearly all the time goes to finding the 2048-bit (617-digit) primes that go into the moduli. Encrypting and decrypting *m* takes less than a second.

## Related Posts

[1] I don’t know who first discovered this line of attack, but you can find it written up here. At least in the first edition, the link is to the 2nd edition, which I don’t have.

Published at DZone with permission of John Cook, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Comments