# 5: Malleability of RSA, and Applications

We now discuss several surprising problems that turn out to be equivalent to the problem of inverting RSA. The results in this section rely on the following malleability property of RSA: Suppose you are given c = me for an unknown message m. Assuming e is public, you can easily compute c · xe = (mx)e. In other words, given the RSA function applied to m, it is possible to obtain the RSA function applied to a related message mx.

Inverting RSA on a small subset

Suppose you had a subroutine INVERT(N,e,c) that inverted RSA (i.e., returned cd mod N) but only for, say, 1% of all possible c’s. That is, there exists some subset G ⊆ ℤN with |G| ⩾ N/100, such that for all mG we have m = INVERT(N,e,me).

If you happen to have a value c = me for mG, then it’s not so clear how useful such a subroutine INVERT could be to you. However, it turns out that the subroutine can be used to invert RSA on any input whatsoever. Informally, if inverting RSA is easy on 1% of inputs, then inverting RSA is easy everywhere.

Assuming that we have such an algorithm INVERT, then this is how we can use it to invert RSA on any input:

Suppose the input to REALLYINVERT involves c = (m)e for some unknown m. The goal is to output m.

In the main loop, c’ is constructed to be an RSA encoding of m·r. Since r is uniformly distributed in ℤN , so is m · r. So the probability of m · r being in the “good set” G is 1%. Furthermore, when it is in the good set, INVERT correctly returns m · r. And in that case, REALLYINVERT outputs the correct answer m.

Each time through the main loop incurs a 1% chance of successfully inverting the given c. Therefore the expected running time of REALLYINVERT is 1/0.01 = 100 times through the main loop.

Determining high-order bits of m

Consider the following problem: Given c = me mod N for an unknown m, determine whether m > N/2 or m < N/2. That is, does m live in the top half or bottom half of ℤN?

We show a surprising result that even this limited amount of information is enough to completely invert RSA. Equivalently, if inverting RSA is hard, then it is not possible to tell whether m is in the top half or bottom half of ℤN given me % N.

The main idea is that we can do a kind of binary search in ℤN. Suppose TOPHALF(N,e,c) is a subroutine that can tell whether cd mod N is in {0,. . . ,(N − 1) / 2) or in{(N + 1) / 2,. . . ,N − 1}. Given a candidate c, we can call TOPHALF to reduce the possible range of m from ℤN to either the top or bottom half. Consider the ciphertext c’ = c · 2e which encodes 2m. We can use TOPHALF to now determine whether 2m is in the top half of ℤN. If 2m is in the top half of ℤN , then m is in the top half of its current range. Using this approach, we can repeatedly query TOPHALF to reduce the search space for m by half each time. In only log N queries we can uniquely identify m.