4
$\begingroup$

Is there an encryption algorithm that will produce a public key and a private key such that the public key cannot be generated using the private key.

For example, if the private key is compromised but the public key is not then messages can only be decrypted and not encrypted.

$\endgroup$
  • 5
    $\begingroup$ "if the private key is compromised but the public key is not" - What do you mean by compromise? A public key is supposed to be public. $\endgroup$ – Artjom B. Jan 3 '16 at 17:04
2
$\begingroup$

This is, by definition, impossible using public-key encryption alone: the public key is assumed to be public, so that everybody knows (or can, if they wish, learn) it and can encrypt messages using it. If you change that assumption, what you have is no longer public-key encryption but something else with different security assumptions and definitions.

That said, you can get something like what you're asking for by combining public-key encryption and digital signatures. Basically, let's assume that Alice wants to allow Bob and Charlie to send her encrypted messages, such that:

  • Only Alice can read the messages.

  • Only Bob and Charlie can generate messages that Alice will accept as valid.

  • Even if Bob's and/or Charlie's full key material is leaked, others will not be able to read the messages they've sent (or will send) using those keys.

  • Even if Alice's key material is leaked, others will not be able to use it to generate valid messages that Alice would accept.

To achieve this, Alice can:

  1. Generate an encryption key pair and a signature key pair.

  2. Keep the private (i.e. decryption) half of the encryption key pair, and the public (i.e. verification) half of the public key pair.

  3. Send the other halves of the keys (i.e. the public encryption key and the private signing key) to Bob and Charlie, and erase them (or at least the signature key; there's no need to erase public keys, since they're public) locally.

    (Alternatively, Bob and Charlie can each generate their own signature key pairs, and send the public verification keys to Alice. This avoid having to transmit private keys between parties and erase them, and also prevents Bob and Charlie from impersonating each other.)

Now, to send a message, Bob (or Charlie) should encrypt it using Alice's public key, and sign it using the signature key,* and send both the encrypted message and the signature to Alice. Alice can then decrypt the message using her private decryption key, and verify the signature to prove that it came from Bob or Charlie.

*) It may or may not matter whether Bob first encrypts the message and then signs the ciphertext, or first signs the message and then encrypts the message and the signature. See this question for more details.

$\endgroup$
2
$\begingroup$

RSA could do what you want: just put only the private exponent and the modulus in the private key, and not the prime factors of the modulus. Since the factors are not needed to decrypt, this will not hurt functionality.

This assumes, of course, that the party generating the keys has a reliable way to destroy the factors when they are not needed, but this seems to be implicit in what you are asking: since the key generation algorithm outputs both keys, if no reliable way to destroy data exists and the generating party is compromised, the attacker can both encrypt and decrypt.

$\endgroup$
  • 2
    $\begingroup$ Doesn't knowing both the encryption and the decryption exponent allow factoring the modulus? $\endgroup$ – Ilmari Karonen Jan 3 '16 at 17:06
  • $\begingroup$ @IlmariKaronen As I understand the answer, $e$ would not be part of the private key. Only Paŭlo says that $d$ is sufficient to factor $N$ without any further reasoning. The other answers seem to require $e$. The idea would probably be that $e$ is also randomly generated and not some common value like 0x010001. $\endgroup$ – Artjom B. Jan 3 '16 at 17:10
  • 3
    $\begingroup$ Hmm, yes, that might work. You'd presumably need a non-standard way of generating $e$ and $d$ (since simply setting e.g. $e = 65537$ is obviously a non-starter here), but just picking a random $e$ coprime to $\lambda(n)$ might work. I've never seen any actual security analysis for this RSA variant, though; in particular, I wonder just what kind of message padding it would need to be secure both as an encryption scheme and as an authentication scheme at the same time. $\endgroup$ – Ilmari Karonen Jan 3 '16 at 17:17
  • $\begingroup$ @IlmariKaronen, here's a related question from Maarten, specifically asking whether you can find the public exponent given only the private one and the modulus. $\endgroup$ – SEJPM Jan 3 '16 at 19:19
  • $\begingroup$ I just posted a question about the security of this scheme. $\endgroup$ – Ilmari Karonen Jan 3 '16 at 19:24

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.