13.5: Malleability of RSA, and Applications

Last updated
Save as PDF

Page ID: 7401

\( \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 = m^e for an unknown message m. Assuming e is public, you can easily compute c · x^e = (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 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^d 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 · 2^e 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.