Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

migrated from Dec 12 '14 at 10:31

This question came from our site for professional and enthusiast programmers.

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

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
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. – René G Mar 18 at 2:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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