Skip to main content
Engineering LibreTexts

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 = 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:

    Figure13-17.jpg

    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.

    Figure13-18.jpg