Questions about updating the secret key of RSA?

Question

I want to update the secret key of RSA.

I understand there exists a common modular attack on RSA. Precisely, if adversary knows $(e_1, m^{e_1})$ and $(e_2, m^{e_2})$, where $e_1$ and $e_2$ are the RSA exponents under the same module $N$. Then it can compute $\lambda_1, \lambda_2$ such that $\lambda_1e_1 + \lambda_2e_2 = {\sf gcd}(e_1, e_2)$, where ${\sf gcd}(\cdot)$ is the greatest common divisor. Thus the plain message can be recovered by computing $(m^{e_1})^{\lambda_1/{\sf gcd}(e_1, e_2)}\cdot (m^{e_2})^{\lambda_2/{\sf gcd}(e_1, e_2)}=m$ (if I am wrong, please correct me).

In my implementation, I want to use the RSA like a private-key encryption. Instead of publishing the public RSA exponent $e$, I keep it secret. Then, the secret key is $(e, d)$ where $ed = 1 \mod \phi(N)$ (I do not consider to update the prime $p$ and $q$). Initially, I compute the RSA ciphertext $m^{e_1}$ and store the secret key $(e_1, d_1)$. At some time, I update the secret key to $(e_2, d_2)$ and give $d_1e_2$ for re-encrypting the ciphertext from $m^{e_1}$ to $m^{e_2}$.

My question is, 1) In my implementation of using RSA like a private-key encryption, the key-update is still vulnerable to common modular attack (or is it secure)? In other words, if the adversary knows $m^{e_1}, m^{e_2}$ and $d_1e_2$, is it able to guess $m$? 2) If 1) is secure, the key-update is resistant against leaking old secret keys? In other words, if the adversary knows $m^{e_2}, d_1e_2$ and $(e_1, d_1)$, is it able to guess $m$?

Waiting for your answers. Thanks a lot.

Answer 1

if the adversary knows $m^{e_1}$, $m^{e_2}$ and $d_1e_2$, is it able to guess m?

Obviously not; if he could, then they could break RSA.

Here's the RSA problem, given $m^e$, $e$ (and the modulus $N$), recover $m$.

Suppose that we can solve your problem, that is, we had a black box that, given $m^{e_1}$, $m^{e_2}$ and $d_1e_2$, could recover $m$.

Then, given the RSA problem parameters $m^e$ and $e$, we would pick a value $\lambda$ which is relatively prime to $\phi(N)$ (and this can be done simply by picking $\lambda$ prime), and compute $(m^e)^\lambda$. If we assume $e_1 = e$ and $e_2 = e \cdot \lambda \pmod{\phi(N)}$, we then have $e_2 \cdot d_1 = \lambda \pmod{\phi(N)}$ (as $d_1 = e_1^{-1}$)

We then have $m^{e_1} = m^e$, $m^{e_2} = (m^e)^\lambda$ and $d_1e_2 = \lambda$, we then give these parameters to the black box, and recover $m$, solving the RSA problem.

On the other hand, this argument assumes that (at least) $e_2$ is large (because the above procedure effectively selects a random $e_2$). If you selected $e_1$, $e_2$ small (say, 16 bits or so), then what the attacker could do is go through the possible $e_1, e_2$ combinations, and recover a billion possible $m$ values, one of which is correct.

Is the key-update is resistant against leaking old secret keys? If the adversary knows $m^{e_2}, d_1e_2$ and $(e_1,d_1)$, is it able to guess $m$?

No, the key-update is not resistant; the adversary can recover $m$. The values $e_1$, $d_1$ are sufficient to allow him to factor $N$ efficiently, with the knowledge of $d_1e_2$ and $d_1$ and $\phi(N)$, he can recover $e_2$, and with that and $m^{e_2}$ (and again, the factorization of $N$), he can recover $m$.