I was given a cryptography question during an interview the other day.

Imagine you are given an efficient algorithm which for a given RSA public key (n,e) is able to decrypt 1% of the messages encrypted with that key.

1% means that the algorithm will deterministically decrypt 1% of all possible ciphertexts on the first call, and will never decrypt the other 99% of all possible ciphertexts with any number of invocations.

Figure out an algorithm that uses this one and can decrypt any message. Any ideas?

  • $\begingroup$ Do we have a duplicate of this question? I thought I already read an equivalent question, but couldn't find it. $\endgroup$ – CodesInChaos Dec 12 '14 at 12:15
  • $\begingroup$ I didn't mean your cross-post, but some older question. $\endgroup$ – CodesInChaos Dec 12 '14 at 12:34
  • $\begingroup$ @CodesInChaos I was thinking the same thing when I saw this. I remember answering a similar question, but can't find it. $\endgroup$ – mikeazo Dec 16 '14 at 12:45

The attacker wants to find $m = c^d$ but doesn't know $d$, but they can find $m'=(c')^d$ for a significant fraction of random $c^\prime$s. Assume that $\mathrm{GCD}(c, n)=1$.

The attacker chooses a random $r$ with $\mathrm{GCD}(r, n)=1$ and computes a new ciphertext $c^\prime$:

$c^\prime = c \cdot r^e$

This ciphertext is uniformly distributed among all ciphertexts with $\mathrm{GCD}(c^\prime, n)=1$. So the attacker has a 1% chance that they can compute the corresponding message $m^\prime$. If it doesn't work, the attacker simply chooses a new $r$.

Relate $m'$ to existing variables:

$m^\prime = (c^\prime)^d = c^d \cdot r^{e \cdot d} = c^d \cdot r = m \cdot r$

Solve for $m$:

$m = m' \cdot r^{-1}$

$r^{-1}$ can be efficiently computed using the extended Euclidean algorithm. This means that an attacker who can break a significant fraction of messages can break all of them.

We assumed that GCD(c, n)=1. If it's not, that GCD is a factor of $n$. In the two-prime RSA case this is a complete break. In multi-prime RSA divide out that factor and you're back to the GCD(c, n)=1 case.

  • $\begingroup$ Why can't the attacker simply add a character to the end of the message? There's a 1% chance that the new message will be decipherable. If not, continue adding characters. For each added character, the probability of success increases: after $n$ tries the probability is $1 - (0.99)^n$, and the attacker can add hundreds of thousands of characters per second. $\endgroup$ – Elliot Gorokhovsky Mar 18 '15 at 2:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.