13
$\begingroup$

Can $n=pq$ be part of two different pairs of RSA keys?

If such keys exist, say $(e_1,n)$ and $(e_2,n)$, how are they related? What will be the security concerns for the two users?

$\endgroup$
  • 2
    $\begingroup$ I edited your comment to have $e_1$ and $e_2$ instead of $e_1$ twice. If that was not your intention, feel free to fix. $\endgroup$ – mikeazo May 2 '12 at 11:40
  • $\begingroup$ Related to your question is whether then moduli of different public keys should be coprime (they should!!), but in real life this is sometimes not the case, see freedom-to-tinker.com/blog/nadiah/… $\endgroup$ – j.p. May 11 '12 at 16:06
14
$\begingroup$

The users will be able to read each other's messages (even though they can have different private keys, say $d_1$ and $d_2$). This is because knowledge of $d_i$ is sufficient to factor $N$, thus allowing that party to compute the other party's private key. This was detailed by Boneh in his analysis of RSA attacks.

$\endgroup$
12
$\begingroup$

Two properties of RSA are important here:

  • If you know $p$ and $q$, you can reverse RSA encryption for arbitrary $e$
  • If you know $e$, $d$ and $n$ you can efficiently factor $n$, and obtain $p$ and $q$.

This means if you know one private key for a given $n$, you know all of them. Thus different persons should not share a modulus.

Such a scheme can be useful if one person needs multiple public keys. This person can use multiple $e$s with a shared $n$. There are few restrictions on the choice of $e$s, for example $ e_3 = e_1 * e_2 $ is broken.

Such key pairs are only useful in very specific scenarios. For example some blind signature schemes use different values of $e$ with shared $n$ to sign different currency denominations.

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