Cryptography/Public Key Overview

From Wikibooks, the open-content textbooks collection

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 proccess betweeen 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 infromation(private key) either he only indirectly accesed 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 anythin 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.

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

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

• a plain text
• the same text crypted 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.

[edit] Further reading

Wikipedia has related information at public-key cryptography