# Why do public key systems involve private keys?

I read up the definition of a public key cryptosystem. It mentions there is a public key and a private key. That's confusing. Why is it called a "public key" system if it involves a private key as well?

• This is almost a linguistics question as much as a CS question. Why is a solution of 10% HCl, 90% H₂O called "hydrochloric acid" rather than "water"? When a government has independent legislative and executive branches, why is that called a "presidential system" rather than a "congressional system"? In each case, we name it for the distinctive component. All cryptosystems involve keys that need to be secret; what distinguishes public key cryptosystems is that they also have keys that can be public, allowing parties without the secret keys to participate (in specific ways). Apr 18, 2021 at 23:08
• why does this question&answer system involve comments? isn't it a question&answer&comment&review system? Why does computer science involve maths, not just computers? Apr 19, 2021 at 15:11

Public key cryptography means that the entire communication between both parties is public, including the setup. Contrast this with the case of two parties $$A,B$$ meeting in secret, agreeing on some keyword, and using this keyword to encrypt future communications.

Clearly, if $$A,B$$ decide on the encrpyption scheme in public, something has to be kept private (otherwise you could decipher the messages just like the parties involved). This is the private key, so the flow is something along the following lines: $$A$$ and $$B$$ publicly discuss and share some information with each other and the world, then they do something in private and send each other encrypted messages. Witnesses to the public exchange alone can't recover what is being said.

The child version of such scheme which I like is the following. Suppose $$A$$ and $$B$$ want to agree on some secret color, only known to them, however the entire exchange must be public. Under the assumption that mixing colors is easy, but given a mixture recovering its components is hard, then they could do the following: $$A$$ and $$B$$ each choose a secret (private key) color denoted by $$a,b$$. Then $$A$$ sends $$B$$ the color $$c$$ (public key), and the mixture $$(a,c)$$. $$B$$ now creates the mixture $$(b,c)$$ and sends it to $$A$$, and also mixes $$(a,b,c)$$ and keeps this compound to himself. Finally, $$A$$ adds $$a$$ to $$(b,c)$$ and is now also in the possession of the secret mixture $$(a,b,c)$$, known to $$A,B$$ but unknown to anyone who solely witnessed the interaction between them.

• Your first sentence would be better if you replaced "means that … is" with "allows … to be". Public-key cryptography does not require all communication to be public, and in fact some minimal amount of secret communication may be required to achieve stronger security goals (such as verifying that the public keys you receive actually belong to who you think they belong to). Apr 18, 2021 at 18:49
• Can c really be called a public key? (a,c) should be a public key and a should be the corresponding private key. c is a parameter. Also this is key exchange, not encryption. Apr 19, 2021 at 15:12
• I like to think of the public key as a safe with an open door and the private key as the key that unlocks that safe. I give you or anyone an open safe. You put your message in that safe and close the door. Now no one, including yourself, can get the message back out aside from myself with my private key. You do the same by giving me a safe and I put my message into it. This way the entire exchange can occur in public yet we can still have secret and secure discussions. Apr 19, 2021 at 17:15

Security is about protecting yourself from adversaries: it's about achieving something that adversaries can't achieve. Cryptography is a part of security that's about protecting information, to achieve properties such as confidentiality (not letting adversaries know something you didn't intend them to) and integrity (not letting adversaries trick you into believing something you didn't intend to).

It's not surprising that there are cryptosystems that involve secrets. If you want to prevent adversaries from achieving something that's related to information, a pretty obvious way to do it is to know something they don't: you know a secret. A key in a cryptosystem is a fundamental piece of information upon which the security of the system depends. It's natural that a key would need to remain secret: if the adversary knows the key, what can the defender do that the adversary cannot? So it isn't remarkable that a cryptosystem involves a secret key.

It's more surprising that there are cryptosystems involving public keys: keys that the adversary knows. Public keys are still called keys, partly because they are specific to an instance of the cryptosystem and they are pieces of information that make the cryptosystem work, and partly because they do have an associated secret (which is usually called “private key”). Historically, the invention of cryptography involving public keys was a paradigm change. (By the way, the first public-key cryptosystems were not for encryption, but for key exchange: Merkle puzzles and Diffie-Hellman.)

Cryptosystems that don't involve a secret key at all (such as integrity protection through hashes) aren't called “something-key” because they don't involve a key. Cryptosystems that do involve a secret key, but no public key, are sometimes called “secret-key”, but usually they're called “symmetric”. Cryptosystems that involve both a secret key and an associated public key are called “asymmetric” or “public-key” because the existence of the public key is the remarkable thing about them. (The secret key is usually called “private key” for duality with “public key”.)

• I think the last paragraph really answers OP's question: we call it "public key encryption" instead of "private key encryption" because there are other, older kinds of encryption that use private/secret keys without any public keys. Apr 19, 2021 at 21:40

In a public key cryptosystems, there are operations that everyone in possession of the public key can do, and other operations that only someone possessing the private key can do. For example:

• Suppose Alice wants to send a message to Bob. Alice encrypts the message with Bob's public key, which he makes available publicly. Only Bob can decrypt the message, since he is the only one who has access to Bob's private key.

• Suppose Alice wants to sign a message. Alice encrypts the message with her private key, which only she has. Anybody can verify the signature by decrypting the encrypted message, using Alice's public key, and checking that it matches the actual message.

In contrast, a symmetric cryptosystem uses the same key for encryption and decryption. To demonstrate how these are used, let us see how one actually implements the two scenarios above:

• Suppose Alice wants to send a message to Bob. She chooses a session key at random, and encrypts it using Bob's public key. She then encrypts the message using the session key (and a symmetric cryptosystem). Bob decrypts the session key using his private key, and then decrypts the message using the session key.

• Suppose Alice wants to sign a message. Alice computes a cryptographically secure hash of the message (a third kind of a cryptographic primitive), and encrypts it with her private key. Everybody can decrypt the hash using Alice's public key, and check that it indeed corresponds to the message.

A cryptographically secure hash function is a component of many cryptosystems, and it differs both from public key encryption and from symmetric encryption.

• Please don't use signature as encryption with the private key. This is confusing many people, just use sign a message with the private key. This confusion comes from RSA where we have both signature and encryption. See here RSA Signing is Not RSA Decryption. Also, for signature we first hash the message as a part of the security ( this also helps to sing long messages, too) since the first true signature; Rabin Signature. Apr 18, 2021 at 20:00
• Real-world cryptosystems based on RSA tend to use different keys for signing and encryption anyway, if only to allow for key revocation. Apr 18, 2021 at 23:54

Cryptography and particularly ciphers started out using secret key cryptography. This is cryptography where the participants share a secret key. These systems use symmetric ciphers to encrypt / decrypt and Message Authentication Code to sign / verify messages. For example, AES could be used to encrypt / decrypt messages and HMAC to provide integrity / authenticity for them.

The problem with secret (also called symmetric or private) cryptography is that you need to distribute the secret keys. Furthermore, the parties in the scheme cannot authenticate the messages to come from them, as all participants use the same key. These difficulties mean that key management is hard to do.

Enter asymmetric algorithms such as RSA and DH. These algorithms have both a public key and a private key. Basically these algorithms rely on a mathematical problem where you have two keys. These public key performs a complementary operation to that of the private key:

Initial Operation Key Complementary Operation Key
Encrypt Public Key Decrypt Private Key
Sign Private Key Verify Public Key
Key Establishment at party A Public Key of party B & Private Key of party A Key Establishment at party B Public Key of party A & Private Key of party B

The advantage for these schemes is that you can distribute the public keys publicly. This allows for much easier key management, as encrypting a symmetric key with another symmetric key doesn't solve the key management problem; it is just shifted the problem to the next key in line. Do note that the public key does need to be trusted by the participants, otherwise an adversary might just send their own key. For this a Public Key Infrastructure (PKI) is commonly used. For example the certificate store in your browser to support TLS connections is part of a PKI.

Public key cryptography is named after the public key because the public key is what distinguishes secret key cryptography based on symmetric algorithms from public / private key cryptography based on asymmetric algorithms. For cryptography you always need a secret or private key if you want to make messages confidential - using a cipher - or if you want to authenticate messages - using a MAC or signature algorithm. You are right that it would be more precise to call it a public / private key cryptosystem, but humans like to keep it short... language eh?