7
$\begingroup$

I know that there exist some attack when using same modulus.
Can two different pairs of RSA key have the same modulus?
RSA cracking: The same message is sent to two different people problem

But with a little modification,
$m$ is the plain-text
$N$ is the RSA modulus
$r_1, r_2$ is the random padding
$e, s$ is the public exponent
$C_e, C_s$ is the cipher-text

encrypt as follow $$С_e = (m + r_1)^e \bmod N$$ $$С_s = (m + r_2)^s \bmod N$$

If attacker only knows $C_e, C_s, r_1, r_2, e, s, N$.
Is it possible to know $m$?

It seems the RSA cracking: The same message is sent to two different people problem does not work?

Improve this question
$\endgroup$
4
  • $\begingroup$ I've quickly edited your question. Internally I've moved the links to the end of the question (use the link tool to do this) for better code readability and I've made the enumerations not using $a$,$b$,$c$... which looks a bit strange but rather $a,b,c,..$ which looks more consistent. If you don't like my edits or they changed the meaning of the question you can either edit again (lower left corner) or roll my edits back by clicking on the "edited ... ago". $\endgroup$
    – SEJPM
    Aug 30, 2015 at 12:43
  • $\begingroup$ I think the main issue is that the issue in the first link (knowledge of $d_i$ leading to factoring any other $d$) still exists, with or without specific padding. So it doesn't make much sense to have different key pairs with the same modulus if the private key isn't kept private. $\endgroup$
    – Maarten Bodewes ♦
    Aug 30, 2015 at 12:48
  • 1
    $\begingroup$ Why would the attacker know $r_1$ and $r_2$ by the way? Why not use a known padding scheme such as RSAES-OAEP or RSAES-PKCS1-v1_5 that already includes a random value? $\endgroup$
    – Maarten Bodewes ♦
    Aug 30, 2015 at 13:01
  • 1
    $\begingroup$ Well there's an attack if $e=s$ using some fancy polynomial math. Maybe someone (not me) can extend the attack to deal with the different exponents. This is what I'm talking about. $\endgroup$
    – SEJPM
    Aug 30, 2015 at 13:04

1 Answer 1

Reset to default
2
$\begingroup$

Yes, it is possible. Like SEJPM suggested, you can use a variant of the Franklin-Reiter related-message attack to accomplish this. Let $\Delta = r_2 - r_1$. Compute $\gcd(X^{e} - c_e, (X + \Delta)^{s} - c_s)$ over $\mathbb{Z}/n\mathbb{Z}[X]$, which yields the linear polynomial $X - (m + r_1)$. Recovering $m$ is now trivial. This, of course, will only be reasonably efficient for small exponents $e$ and $s$; but it should be quite doable for common exponents below $65537$.

Improve this answer
$\endgroup$

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.