RSA assumption and cryptography

The RSA assumption states that it is hard to find $m$, given $c = m^e \bmod{n}$, $e$, and $n$ (for appropriate choice of $n,e$).

Suppose that there exists an algorithm, $D(c,e,n)$, that finds $m$ in 1% of cases. What could be a pseudocode of an algorithm that can use $D(\cdot,\cdot,\cdot)$ and finds $m$ easily for any $c$?

-
Is it homework? What have you tried to answer the question? What properties of RSA do you know? – Dmitry Khovratovich Feb 9 '14 at 11:32
This sounds a lot like homework. But it sounds like you might want to check out random self-reducibility. – Maeher Feb 9 '14 at 12:33
Hint: if $D(c,e,n)$ does not succeed to find $m$ with $c=m^e\bmod{n}$, can we can reformulate that same question in a variant and submit some internal portion of that variant to that same magic D algorithm? Now, if that new strategy consistently failed, would "D succeeds in 1% of cases" hold? – fgrieu Feb 9 '14 at 17:20

Since it sounds a lot like homework, I will only give a hint, not the actual answer.

• First, you don't want to mess with $e$, since you can not be sure that a different $e$ is actually a valid exponent ($e$ has to be coprime to $\phi(n)$, which contains at least $2$ as prime factor).
• RSA is not IND-CCA. The same attack that works against IND-CCA also works against this.
• This attack utilized the homomorphic property of RSA. If you decrypt $c=(ab)^e=a^eb^e$, you get back $m=ab$

edit: textbook-RSA is not IND-CPA either, but the according security game is trivial for the attacker, since the encryption is deterministic. That doesn't help in this case.

-

You should be able to use D for any c by blinding the query to D. Repeatedly try

r:=uniformly random in 1..n-1
$x:=D(c\cdot r^e\bmod n, e, n)$
$m:=x\cdot r^{-1}\bmod n$

$c\cdot r^e$ is uniform in the range 1..n-1 (with the possible exception of when c is a multiple of a factor of n, which I haven't checked), so no matter which 1% of c values it is that D works on, you're bound to find the correct m within your first couple hundred tries.

Note: I'm assuming that D's "1%" success rate is independent of D's second and third arguments. If, say, D works 100% of the time for 1% of the n values, and 0% for the other 99% of the n values, you're hosed.

-
Hi, Francois. I recognized your name from sci.crypt (which has gone even further down hill in the year I was away). I know you have high standards and won't mind a nitpick on your English: >>even if I get the intend from context<<; "intend" is a verb. The noun is "intent". – Brock Hansen Feb 12 '14 at 15:48
Hi Brock, I've improved my English thanks to you. This site is much nicer than sci.crypt has been since well over a decade; and occasional friendly nitpicks also occur here! PS: try this TeX cheat sheet, and wrapping subexpressions into braces, like this: $m:=x\cdot r^{-1}\bmod n$ to get $m:=x\cdot r^{-1}\bmod n$ – fgrieu Feb 12 '14 at 16:00
Thanks for the tips, but I think ASCII, where it can be made to work, is better. Yes, the MathJax may look good in any browser, but if, say, you Copy it and Paste it somewhere else, you lose the formatting. – Brock Hansen Feb 12 '14 at 16:13
Yes, ASCII has the benefit of universality. Last hint before the no-chat-police spots us: one can examine other's $\TeX$ (or MathML) with a right click. Or remove one's own comments if no longer useful. Or revert to earlier versions of questions and answers. Or.. – fgrieu Feb 12 '14 at 16:19

for i = 1, 3, 5, ... do:

$\quad\, m_i \leftarrow D(c^i, i\cdot{}e, n)$

$\quad$ if $m_i^e = c$ then:

$\quad \quad$ return $m_i$

$\quad$ end if

end for

-
If the algorithm succeeds at step $i$, then we have $c^i = m_i^{ie}$, which is actually very likely to imply $c = m_i^e$. – Alan Sz Feb 10 '14 at 9:42
It might work, but it's not optimal. The reason is, that $D$ might check internally if $e$ is a valid exponent. And for $i=2$, it is not. $e$ has to be coprime to $\phi(n)$. – tylo Feb 10 '14 at 13:20
Oups, I somewhat missed $i\cdot e$ and read $e$, making my earlier comment (now gone) erroneous (fortunately I had not downvoted the answer, and now have upvoted). Even with odd $e$, making it more likely that $e$ is coprime to $\operatorname{lcm}(p-1,q-1)$, that's not the algorithm I had in mind, and I find impossible to prove that it finds $m$ easily for any $c$; but it has some clear merit, and chance of success. – fgrieu Feb 10 '14 at 13:42
tylo, fgrieu: You're right, it's best to make $i$ odd at every iteration. I changed that. Now, let's assume the user is not likely to find an $i$ for which gcd($i$,$\varphi(n)$)$\neq 1$, which is a reasonable assumption if $p$ and $q$ are safe primes. – Alan Sz Feb 10 '14 at 15:35
I like this because it can work with a D(,,) whose 1% success is not independent of D's second argument. However, to ensure success no matter what 1% subset of the second argument's range it is that D works on, i should be random, not sequential. – Brock Hansen Feb 13 '14 at 16:58