# 5: Malleability of RSA, and Applications

- Page ID
- 7401

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* = *m ^{e}* for an unknown message

*m*. Assuming

*e*is public, you can easily compute

*c*·

*x*= (

^{e}*mx*)

*. In other words, given the RSA function applied to*

^{e}*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 *c ^{d}* 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

*m*∈

*G*we have

*m*= INVERT(

*N,e,me*).

If you happen to have a value *c* = *m ^{e}* for

*m*∉

*G*, 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* = *m ^{e}* 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 *m ^{e} % 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

*c*mod

^{d}*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 ℤ

*to either the top or bottom half. Consider the ciphertext*

_{N}*c’*=

*c*· 2

*which encodes 2*

^{e}*m*. We can use TOPHALF to now determine whether 2

*m*is in the top half of ℤ

_{N}. If 2

*m*is in the top half of ℤ

*, then*

_{N}*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*.