10
$\begingroup$

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?

$\endgroup$
2
  • 30
    $\begingroup$ 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). $\endgroup$ – ruakh Apr 18 at 23:08
  • $\begingroup$ 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? $\endgroup$ – user253751 Apr 19 at 15:11
14
$\begingroup$

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.

$\endgroup$
3
  • 7
    $\begingroup$ 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). $\endgroup$ – Ilmari Karonen Apr 18 at 18:49
  • $\begingroup$ 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. $\endgroup$ – user253751 Apr 19 at 15:12
  • $\begingroup$ 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. $\endgroup$ – TerekC Apr 19 at 17:15
7
$\begingroup$

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”.)

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – MJ713 Apr 19 at 21:40
3
$\begingroup$

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.

$\endgroup$
2
  • 5
    $\begingroup$ 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. $\endgroup$ – kelalaka Apr 18 at 20:00
  • 2
    $\begingroup$ Real-world cryptosystems based on RSA tend to use different keys for signing and encryption anyway, if only to allow for key revocation. $\endgroup$ – Pseudonym Apr 18 at 23:54

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.