As 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 avoided by real-world precautions such as adding random padding to each message so that no two recipients are sent the exact same message.

By the way, a similar trick works even if you only have access to one encrypted message. Suppose you’re using a 2048-bit modulus *N* and exchanging a 256-bit key. If your message *m* is simply the key without padding, then *m*³ is less than *N*, and so you can simply take the cube root of the encrypted message in the integers.

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

Is it an attack on e=65537 RSA if you recover the identical message encrypted to 65,537 unique moduli? It seems like it.

+ from sympy import cbrt