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 eth power.

Sometimes (especially with very small values of e) it is likely that the ciphertext is the eth power of an integer. If this is the case then the plaintext can easily be recovered by taking eth 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!


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: