1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ If the adversary knows (e1, d1) and if e1 is small (e.g. 65537), he knows very quickly phi(n) = e1 * d1 - 1 and therefore the factorization of n. It does not take long to recompute d2 from e2, and recover m from m^e2. Then you must use large values of e, the benefit of fast RSA encryption fades away. And when you chose e, you must ensure that e*d-1 is not easy to factor knowing e and d. $\endgroup$ – Pierre Feb 16 '15 at 14:11
  • $\begingroup$ @Pierre: actually, knowing $e_1, d_1$ is enough to allow a quick factorization of $N$, even if $e_1$ is large. $\endgroup$ – poncho Feb 16 '15 at 16:39
0
$\begingroup$

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

$\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.