## Limitations of RSA.

RSA, as we saw is a really amazing public key cipher that uses only basic number theory in its description.

However, whenever a new cipher appears there will be many people that test its security and whenever possible will try to break it.

So far RSA has not been broken but certain bad things can happen with it if you are not careful. Here are a few things that can go wrong.

1) Using small primes.

This one is quite obvious, if the primes used are small enough then a computer will make easy work of factorising $N$.

2) Using primes that are very close.

This is quite a serious weakness because it makes a big flaw, even if you do use big enough primes. If $p,q$ are relatively close (I know this is ambiguous but should be well understood) then searching for prime factors in the vicinity of $\sqrt{N}$ will reveal either of the factors in quite a quick time (depending on how close the factors are).

Alternatively, the methods of Fermat factorisation or more general number sieves can be used here to give a quick result in some cases.

3) Message is an observable $e$th power.

Sometimes (especially with very small values of $e$) it is likely that the ciphertext is the $e$th power of an integer. If this is the case then the plaintext can easily be recovered by taking $e$th roots of the corresponding integer equation.

For example suppose the public key of the person I wish to send to is $(e, N) = (3, 15)$, for simplicity, and suppose that my plaintext is $m=2$. I would be sending the ciphertext $c = 8$. But if anyone was to intercept this, they would immediately observe that $8$, as an integer, is a perfect cube already and so could cube root to find the plaintext $m=2$.

4)  Two people using the same $N$, receiving the same message.

Suppose Alice and Bob use the same $N$ and so have public keys of the form $(e_1, N)$ and $(e_2, N)$. If $e_1$ and $e_2$ are coprime then Jane is able to read any message $m$ that is sent to both of them.

By number theory, $e_1, e_2$ coprime guarantees the existence of integers $a,b$ such that $ae_1 + be_2 = 1$. Jane knows the values of $e_1, e_2$ so can use Euclids algorithm to find such $a,b$.

Then $m = m^{ae_1 + be_2} = (p^{e_1})^a (p^{e_2})^b \equiv c_1^a c_2^b \bmod N$, where $c_1, c_2$ are the corresponding intercepted ciphertexts.

Thus Jane can find the plaintext by simply reducing the value of $c_1^a c_2^b$ modulo $N$.

5) Sending the same message to $e$ or more people with the same $e$ (Hastad’s attack).

I will demonstrate this when $e=3$ but the exact same method works for any $e$.

Suppose three people have public keys $(3, N_1), (3, N_2), (3, N_3)$ (so the number of people is the greater than or equal to the value of $e$) and also that the same plaintext $m$ is encrypted and sent to them. If Jane intercepts these messages then she can find the plaintext.

She first works out $gcd(N_1, N_2), gcd(N_1, N_3)$ and $gcd(N_2, N_3)$ using Euclids algorithm. If either of these are bigger than $1$ then she has found one of the prime factors and so can break the message by the usual way (she is able to find one of the private keys then).

If all three of these results turn out to be $1$ then $N_1, N_2, N_3$ are all coprime to each other.

We now note that the intercepted ciphertexts satisfy:

$c_1 \equiv m^3 \bmod N_1$

$c_2 \equiv m^3 \bmod N_2$

$c_3 \equiv m^3 \bmod N_3$

This is essentially a set of linear congruences that we may solve simultaneously for $m^3$ modulo $N = N_1N_2N_3$ (by the chinese remainder theorem along with the fact that $N_1,N_2,N_3$ are coprime).

Suppose the solution is:

$m^3 \equiv n \bmod N$

where $n$ is between $0$ and $N$.

Now, by definition, the plaintext $m$ is less than all three of $N_1,N_2,N_3$, so $m^3 < N_1N_2N_3 = N$. Thus we must have that $m^3 = n$ as integers. Since we know $n$, we may simply find its cube root and hence finding the plaintext $m$.

It is easy to see how this idea generalises to the general case mentioned above (where you have $e$ users or more with the same $e$, all receiving the same message). It is just a matter of using the chinese remainder theorem.

There are more advanced attacks on RSA based on this idea such as Coppersmith’s attack, but this is not so easy to explain. I shall leave that till another time!