Cryptography/Public Key Overview

We briefly mentioned Asymmetric Ciphers earlier in this book. In this and following chapters we will describe how they work in much more detail.

The discovery of public key cryptography revolutionized the practice of cryptography in the 1970s. In public key cryptography, the key used to encrypt a message is not the same as the key used to decrypt it. This requires an asymmetric key algorithm.

(All previous cryptographic algorithms and cryptosystems, now retroactively categorized as "symmetric key cryptography" or "shared key cryptography", always use the same key to encrypt a message and later to decrypt that message).

Public key cryptography is cryptography where the key exchange process between person A and person B must not be kept secret. Private keys actually are never exchanged. In fact Person A sends information (possibly about a session key) to Person B so that it is only interpretable to Person B. An intruder cannot discover the meaning of the exchange because Person B has a piece of information that the intruder does not. Person A didn't access Person B's secret information (private key) either he only indirectly accessed it via a "public" key. The public key is formed from the private key by using a One-Way Function.

The concepts behind public key cryptography are best expressed by a simple puzzle.

Alice wants to send a trinket to Bob without an intruder stealing it. Each person has a lock and a key. A Non-Public Key Solution

1. Alice puts her key in the box and sends to Bob.
2. Bob copies the key and sends it back.
3. Alice sends the trinket in a locked box.
4. Bob opens the box with the copied key.

This solution, although the most intuitive, suffers from a major problem. The intruder could monitor the boxes and copy the key as it sent. If an intruder has Alice's key the trinket or anything else will be stolen in transit. To some the puzzle seems impossible, but those who understand public key cryptography solve it easily. Public Key Solution

1. Alice puts the trinket in a box, locks it and sends it to Bob.
2. Bob locks the box again with his lock and sends the box back.
3. Alice removes her lock and sends it to Bob.
4. Bob removes the final lock and takes the trinket.

The puzzle's trick is double locking the box.

This back-and-forth "double lock" process is used in many asymmetric key algorithms, such as ElGamal encryption and Diffie–Hellman key exchange, but not all of them.

This is the double lock principle, but it is not Public Cryptography as both keys are secret. In public cryptography one key is public, the other is secret. Nobody knowing the public key is able to decipher a message encrypted with a public key. Only the secret key is able to decipher a message encrypted with a public key.

A real-world analogy to public keys would be the padlock. The padlock can be easily closed, but it is much harder to do the reverse, namely opening. It is not impossible, but it requires much more effort to open it than to close it, assuming you don't have the (private) key. Alice could send Bob an open padlock by mail (the equivalent to the public key). Bob then puts a message for Alice into a box and locks the box with the padlock. Now, Bob sends the locked box back to Alice and Alice opens it with her private key.

Note that this approach is susceptible to man-in-the-middle attacks. If Charles intercepts the mail with Alice's padlock and replaces it with his own padlock, Bob will lock the box with the wrong padlock and Charles will be able to intercept the answer. Charles could then even lock the box again with Alice's padlock and forward the box to Alice. That way, she will never notice that the message got intercepted. This illustrates that it is very important to obtain public keys (the padlocks) from a trusted source. That's what certificates are for. They come along with the public keys and basically say something like 'I, Microsoft, hereby confirm that this padlock belongs to Alice', and are signed using secure digital signatures.

So someone (Bob) is able to send securely an encrypted data to Alice, if Alice had made her key public.

Bob is able to prove that he owns a secret key only by providing:

• a plain text
• the same text encrypted with the secret key
• the public key corresponding to the secret key.

Something similar to the double lock principle is Merkle's puzzle, which is the ancestor of the Diffie–Hellman key exchange, which is itself a close cousin to RSA public key system.