# 13.5: Malleability of RSA, and Applications

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

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.

13.5: Malleability of RSA, and Applications is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek.