51

Can we have multiple public keys associated with a single private key for RSA public-key encryption?

Priyank Bolia
  • 14,077
  • 14
  • 61
  • 82

1 Answers1

43

In practice and with respect to security, no, mathematically, yes. If you have a private key (N, D), there is algebraically an infinite number of solutions to the equation 1 = E*D (mod Phi(N)). However, if you make two such solutions (E, N) and (E', N) that both satisfy the equation public, you will have compromised the secrecy of the private key.

However given one of the usual asymmetric schemes you can easily create such a scheme: To create a private key with n public keys, just generate n public-private keypairs in the normal scheme and define the "private key" to be the collection of the private keys. When signing just sign with all the private keys, when verifying try to verify one of the signatures. Encryption is the usual operation and decrypting should try to decrypt with all the keys (one of them should work).

Such algorithm is well known as "hierarchical deterministic wallets" and well explained here BIP-32

skywinder
  • 21,291
  • 15
  • 93
  • 123
Henrick Hellström
  • 2,556
  • 16
  • 18
  • But in the link given by Rasmus Faber above it appears that you can't have multiple public keys. Also what if I have 100 different public keys, but one private key, but the keys are 2048 length, what is its strength for normal usage. I mean it would still require massive computing power to break the encryption, even with 100-200 public keys? – Priyank Bolia Feb 22 '12 at 04:28
  • 11
    Please do the math in my answer. For instance, if (N,D) is the private key that corresponds to (N,E) where E = 65537, then (N,E') where E' = 65537*k*phi(N) will also be a public key that corresponds to (N,D). If you have both (N,E) and (N,E') you can brute force k just by looking at the size of E' compared to N, calculating M = (E'-E)/k, D' = 1/E mod M and performing a few RSA operations to check. The security is zero of RSA in such case. You can do this computation in a fraction of a second on a modern computer. – Henrick Hellström Feb 22 '12 at 08:18
  • There are more methods and a few more complicated cases, but that rather belongs to crypto.stackexchange.com – Henrick Hellström Oct 21 '15 at 11:00
  • Any links to this, as to be honest nobody is providing evidence, just lip-service relying on the ignorance of most readers – MrMesees Nov 23 '15 at 18:04
  • @MrMesees Please feel free to re-post a similar question to crypto.stackexchange.com and include a link to the answers in a comment here. – Henrick Hellström Nov 23 '15 at 18:26
  • @HenrickHellström so is that a no to the request for links? – MrMesees Nov 24 '15 at 15:20
  • 1
    @MrMesees You are asking the wrong question. If you want evidence, you should be asking for proof and not links. While the proof is not complicated, it would be benefit from the LaTex capabilities of crypto.stackexchange.com, so please repost there. – Henrick Hellström Nov 24 '15 at 16:46
  • I see, sorry, I was not aware other areas of stackexchange operated with different output formatting capacities, apologies, I'll try to look for someone else question first – MrMesees Nov 24 '15 at 16:50
  • is this similar to bitcoin addresses which can have multiple addresses spawned by one private key? – smatthewenglish Sep 03 '16 at 15:33
  • 2
    Here is a detailed answer on the crypto.stackexchange: https://crypto.stackexchange.com/a/10731/70218 – skywinder Sep 09 '19 at 02:14
  • Such algorithm is well known as "hierarchical deterministic wallets" and well explained in BIP-32 https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki – skywinder Sep 09 '19 at 02:23