2
$\begingroup$

I want to make an end-to-end messaging platform where everyone is identified with a unique random private key. Everyone uses other peers' public keys to identify and send encrypted messages and verify received messages signed by the public keys. Now I want to use multiple public keys for each peer and maybe give peers access to two or more public keys of a private key.

Can other peers find out if some known public keys belong to the same private key or not? And if they found out, does it put the private key at risk of being cracked or create other security issue?

$\endgroup$

1 Answer 1

7
$\begingroup$

You can't have two different public keys for the same RSA private key. That's just not how RSA works.

Well, almost. There's a minor technical loophole, and it's the fact that RSA has equivalent keys. In particular, the public keys $(n, e)$ and $(n, e + \lambda(n))$ are equivalent, in the sense of producing the same ciphertext for the same (padded) plaintext. But there are two reasons why you never want to publish two such equivalent keys:

  1. It's useless, since they're literally equivalent. You might as well just send the same public key to both peers. Encrypting a message (or verifying a signature) using a large public exponent is slower anyway, so it's best to just do things the usual way and use one of the standard small public exponents like $e=3$ or $e=2^{16}+1=65537$.

  2. It completely breaks the security of the system. Knowing two equivalent public keys with different exponents $e$ and $e'$ lets anyone learn their difference $\delta_e = |e - e'|$, which must be a multiple of $\lambda(n)$. Knowing a non-zero multiple of $\lambda(n)$ is enough to solve the modular congruence $ed \equiv 1 \pmod{\delta_e}$ and obtain the private decryption exponent $d$ (or something equivalent to it — RSA private keys can also be equivalent but not identical in exactly the same way as public keys).

So, you know, don't do that. Just generate your RSA key pairs the usual way, with one public key for each private key and vice versa. And remember that the public key is supposed to be public, so you can always share the same public key with any number of people.


Ps. While copyediting your question, I noticed that you mentioned signing messages. With RSA signatures (and digital signatures in general), you cannot (usefully) sign messages with public keys, but only with the private key. So e.g. if Bob wants to send a message to Alice, he should sign the message with his private key, and then encrypt the signed message with Alice's public key (and make sure before signing that the message says it's for Alice, so that she can't just re-encrypt it with Charlie's public key and make it look like Bob sent it to Charlie).

Also, it's generally not a good idea to use the same key pair for signing and encryption, even if algorithms like RSA technically allow it. So in practice, every peer should really have two private RSA keys (one for signing, one for decryption) and every other peer should know the public keys corresponding to both of them (so that they can both encrypt and verify signatures).


Pps. For a simpler and more practical solution, ditch RSA entirely and replace it with e.g. NaCl / libsodium crypto_box. It's simpler and faster, the keys and signatures are smaller, you only need one keypair for each peer, and since it's an all-in-one integrated solution, it's a lot harder to use it wrong and end up with a security hole than it would be if you insisted on rolling your own signing and encryption scheme with RSA.

Or, perhaps even better yet, don't try to design your own messaging protocol at all, but just use an open source implementation of some published and well studied protocol such as Signal. Designing a good and secure messaging protocol is not easy, with all sorts of non-trivial details like protecting past conversations from the possibility of a later key compromise. It's much easier to just use an existing protocol designed by smart people who have already considered those details and found ways to handle them.

(Even if you do insist on making your own messaging protocol, it's at least a good idea to review some widely used and studied existing protocols like Signal and see what issues their designers have considered and how they've dealt with them. That way, you get a chance to learn from other people's mistakes instead of your own.)

$\endgroup$
1
  • 2
    $\begingroup$ Nit: The author may have been considering two public keys that share a common modulus but have different public and private exponents. Which, of course, is also a bad idea but may warrant addressing specifically. $\endgroup$ Commented May 18, 2019 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.