Posted by Jason Polak on 06. May 2018 · Write a comment · Categories: number-theory · Tags:

Alice wants her friends to send her stuff only she can read. RSA public-key encryption allows her to do that: she chooses huge primes $p$ and $q$ and releases $N = pq$ along with an encryption exponent $e$ such that ${\rm gcd}(e,(p-1)(q-1)) = 1$. If Bob wants to send Alice a message $m$, he sends $c = m^e$ modulo $N$ to Alice.

Computing $m$ from $m^e$ is hard if you only know $N$, but becomes easy with the prime factors $p$ and $q$. And, only Alice knows $p$ and $q$. The word “hard” is relative, and maybe someone will find an easy way to do it in the future, perhaps with quantum computers.

However, if you know $p$ and $q$, then you can compute $d$ such that $de = 1$ modulo $(p-1)(q-1)$. That is, you’re computing the inverse of $e$ in the multiplicative group $(\mathbb{Z}/N)^\times$. You can use Fermat’s little theorem: $x^{p-1} = 1$ in $\mathbb{Z}/p^\times$ for an $x\in (\mathbb{Z}/p)^\times$ to compute that $c^d = m^{ed} = m$ modulo $N$. Therefore, $c^d$ in $\mathbb{Z}/N$ is the decrypted message.

The knowledge of the factors $p$ and $q$ allow you to quickly compute $d$ via the Euclidean algorithm to decrypt $c = m^e$ to find $m$. However, without the knowledge of $p$ and $q$, the current best practical algorithms are so slow that this system is currently secure.

In practice, RSA is used to exchange a private key that in turn is used to send encrypted messages using a symmetric encryption algorithm like AES. One reason is that symmetric encryption is faster. There are other reasons, and in the early days of cryptography G. Davida found a simple but amusing attack that gives us another reason to use RSA only to exchange a private key for symmetric encryption.

Davida’s Attack

How does the attack work? Suppose the encrypted message $c = m^e$ is sent on an open channel. If an attacker Eve can intercept $c$ before Alice gets it, then she can choose a random number $x$, compute $x^e$ and give Alice the message $cx^e = (xm)^e$. Then, when Alice decrypts the message she finds the message $xm$ instead of $m$.

Why is this a bad?

Consider the following scenario: Bob has a storage locker sealed with a good lock. He’s out of the country and wants to give Alice his diamond collection, which he stored in his storage locker. So, he sends Alice the encrypted combination $c = m^e$ using RSA. Eve intercepts the message and sends Alice $cx^e = (xm)^e$. Eve installs a hidden camera above the lock and observes Alice entering the wrong combination $xm$. She solves for $m$, and uses the correct combination to steal the diamonds.

Of course, this situation is artificial. The modified encrypted message $(xm)^e$ might not look like a valid combination. But if it did and Alice uses it, then Eve could escape with the diamonds to Ecuador and Alice would probably think Bob sent her the wrong combination. If Eve instead steals the diamonds outright by mugging Alice, the police will catch her before she can escape.

On the other hand, if Bob and Alice first exchange a private key to send further messages, Bob can send Alice the combination for the lock with symmetric encryption. Eve can still intercept the message and replace it with something else, but if Alice attempts to decode this ‘something else’, even if it looks like a valid lock combination, it’s knowledge won’t help Eve.

Leave a Reply

Your email address will not be published. Required fields are marked *