0

Suppose the decryption key $d$ of a RSA cryptosystem is hacked and instead of choosing a new $n$ if encryption and decryption keys are changed with same $n$,then is this safe ?

My attempt: Previous encryption key $e$ and decryption key $d$ are known. Then $ed \equiv 1$(mod $\varphi(n)$)

i.e, $\;ed-1 = k \cdot \varphi(n)$, for some natural number $k$.

$\implies \varphi(n) =\frac{ed-1}{k}$

So we get $\varphi(n)$ and could get prime factors of n.

Is this right?

ビキ マンダル
  • 342
  • 1
  • 2
  • 12
  • But you need to get $k$ and $\varphi(n)$ to make this work. How do you do that? In other words, you can't get $\varphi(n)$ without knowing $k$, and you can't get $k$ without knowing $\varphi(n)$. And clearly, if you know $\varphi(n)$ you know everything. – Randall Nov 03 '22 at 18:02
  • Also, if you get $\varphi(n)$, you don't need to factor $n$ anymore. – Randall Nov 03 '22 at 18:09
  • Anyway, you can consider what happens when the same plaintext is encrypted under the two distinct keys (same $n$). There is a vulnerability there. – Randall Nov 03 '22 at 18:14
  • Yes, if the new and old encryption keys are coprime then finding integers $u,v$ such that $e_1u+e_2v=1$ ,ciphertext can be decrypted. – ビキ マンダル Nov 04 '22 at 14:44
  • But if they are not coprime then is there any vulnerability? – ビキ マンダル Nov 04 '22 at 14:45
  • The probability that they are coprime is VERY high. – Randall Nov 04 '22 at 15:23

1 Answers1

0

The vulnerability as mentioned by @Randall, here is additional detail.

From the paper, "Solving Systems of Modular Equations in One Variable: How Many RSA-Encrypted Messages Does Eve Need to Know?" by Alexander May and Maike Ritzenhofen:

G. Simmons [16] has presented a neat attack for this special setting with running time polynomial in the bitlength of $(e_1, e_2)$. Namely, one computes integers $u_1, u_2$ such that $u_1e_1+u_2e_2 = 1$ with the help of the Extended Euclidean Algorithm. This gives us $m = (m^{e_1})^{u_1} (m^{e_2})^{u_2} \pmod{N}$.

...

References

[16]: Simmons, G.: A “Weak” Privacy Protocol Using the RSA Crypto Algorithm. Cryptologia 7(2), 180–182 (1983)

The original Simmons paper is here.

vvg
  • 3,311