2
$\begingroup$

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$?

Improve this question
$\endgroup$
3
  • $\begingroup$ Is it homework? What have you tried to answer the question? What properties of RSA do you know? $\endgroup$
    – Dmitry Khovratovich
    Feb 9, 2014 at 11:32
  • 1
    $\begingroup$ This sounds a lot like homework. But it sounds like you might want to check out random self-reducibility. $\endgroup$
    – Maeher
    Feb 9, 2014 at 12:33
  • $\begingroup$ 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? $\endgroup$
    – fgrieu ♦
    Feb 9, 2014 at 17:20

3 Answers 3

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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". $\endgroup$
    – Brock Hansen
    Feb 12, 2014 at 15:48
  • $\begingroup$ 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$ $\endgroup$
    – fgrieu ♦
    Feb 12, 2014 at 16:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – Brock Hansen
    Feb 12, 2014 at 16:13
  • $\begingroup$ 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.. $\endgroup$
    – fgrieu ♦
    Feb 12, 2014 at 16:19
2
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Alan
    Feb 10, 2014 at 9:42
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – tylo
    Feb 10, 2014 at 13:20
  • $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Feb 10, 2014 at 13:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – Alan
    Feb 10, 2014 at 15:35
  • $\begingroup$ 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. $\endgroup$
    – Brock Hansen
    Feb 13, 2014 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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