# Public-key encryption

Public-key encryption is an asymmetric encryption method in which 2 complementary keys are used. What gets encrypted by one of the keys can be decrypted only by the other. Generally one key of the pair (the "private key") is kept safe by an individual and the other key (the "public key") is distributed freely, after which two things can be done.

If a message can be decrypted using the widely distributed ("public") key, it proves that the author of the message is the individual that holds the private key. Conversely, if a message is encrypted by the public key, it can only be decrypted by the key that was kept safe (the "private key"), making it possible to send a confidential message to the holder of the private key knowing only the public key. While this is the general principle of operation, many modifications are made in order to ensure practical and quick encryption.

Well-known public-key encryption algorithms include Diffie-Hellman and RSA. In Diffie-Hellman, the hardness is based on the discrete logarithm; in RSA it is factoring.

## Diffie-Hellman key exchange protocol

This is a method to secure a channel from eavesdroppers, by agreeing on an encryption key. It is used to let 2 parties agree on a key to be used for encrypting their communications, without actually transmitting said key on the channel between them. If somebody is eavesdropping he will not be able to deduce the key agreed upon from listening to the data.

"Diffie-Hellman key exchange", relies on the fundamental difficulty of computing the discrete logarithm of a number in the group G. It was invented by Whitfield Diffie and Martin Hellman in 1976. The protocol proceeds in three steps:

1. Alice decides on a large prime number p which defines a multiplicative group G in which to work, with generator g
2. Alice chooses a secret integer a. She sends ga mod p to Bob
3. Bob chooses a different integer b, and sends gb mod p to Alice
4. Alice computes (gb)a, while Bob computes (ga)b

At this point both parties (Alice and Bob) have the same (secret) information (ga*b mod p), and can use the shared secret as a key for sending encrypted messages back and forth by the usual methods.

An example conversation (in practice much larger prime numbers will be used) :

1. Alice chooses a prime p = 43, which defines a multiplicative group with 43 elements, 0 to 42. Our secret key will be one of the elements in the group, which means it will be a value from 0 to 10. Since p is prime, any element is a generator, so we can pick any number between 0 and 42, let's say we pick 28. Any number between 0 and 42 will do for the generator. In practice the generator needs to be "relatively" prime to p, modulo p. This means g and p must have no common factors, when calculating mod p.
1. Alice then sends p and g to Bob, who now also knows p = 43 and g = 28
2. Alice chooses her secret number a, let's say 58. She calculates ga mod p = 2858 mod 43 = 17, and sends 17 to Bob
3. Bob chooses his secret number b, let's say 39. Bob sends gb mod p = 2839 mod 43 = 2 to Alice
4. Alice calculates her version of the secret value gab using gb (the value she received from Bob) : (gb)a mod p = 258 mod 43 = 4
5. Bob calculates his version of the secret value gab using ga (the value he received from Alice) : (ga)b mod p = 1739 mod 43 = 4

Alice and Bob have agreed on an encryption key, gab = 4, and only sent values that can only be used to calculate the key with great difficulty : p = 43, g = 28, ga = 17 and gb = 39. If you want to find out the key, your only choice is to try and determine either a or b. This can only be done by calculating g1, g2, g3, g4, g5, ... and compare with the ga value, until found.

By increasing p, the procedure of looking for a can be made arbitrarily difficult. These days p is generally chosen to be "relatively large", meaning that it should require "a bit less" than 256 bits to represent. Determining a would take on average 2255 steps (although some algorithms can do it in slightly less steps) to determine a.

The main problem is the "man in the middle attack". Instead of merely eavesdropping, an attacker would place himself between the 2 parties trying to communicate, and he would participate in the key exchange. The spy would agree on one key with the first party, agree on another key with the second party. Then he is able to decrypt (and re-encrypt and retransmit) the data sent over the channel.

However the protocol is useful because it raises the difficulty of eavesdropping. A spy would have to be able to place himself "in between" the two parties he intends to spy on. Also, the spy needs to actively participate in the conversation in order to be able to spy. If he were to put a listening device on the cable, for example, he would not be able to understand the messages sent.

## RSA encryption

"RSA" stands for "RivestShamirAdelman",[1][2] the three MIT researchers who discovered the RSA algorithm in 1977. It is probably the most commonly used public key encryption at this time.

RSA is based on the fundamental difficulty of factoring large integers into primes.

The RSA algorithm was put to the test in 1991, when RSA Laboratories released the "RSA Factoring Challenge". The challenge consisted of a list of progressively larger numbers, which, when fully decrypted, read "The magic words are squeamish ossifrage."[3] Although the challenge was withdrawn in 2007, the RSA algorithm is still widely considered acceptable for business purposes.

## GCHQ

The mathematics of public key cryptography, and specifically RSA, are now generally recognized to have been first developed at the British government signals intelligence department GCHQ (Government Communications Headquarters). In 1975 three mathematicians at GCHQ, James Ellis, Clifford Cocks and Malcolm Williamson devised the mathematics for a public key system. However, due the limited computing power available at the time, the idea was not developed into a practical system, and due to the secret nature of the established, papers on the subject were not released to the general mathematical community. The discoveries of Rivest, Shamir and Adelman, although later, were entirely independent.[4]

## Example

Step 1

Fred needs to send documents to many people. They don't need to be secure, but its important that they know for certain that the message actually came from Fred.

• Fred encrypts the message using his private key. (only fred knows this key)
• Fred sends the encrypted message
• George gets the message (others may as well, but that is not important)
• George decrypts the message using Fred's Public key.
• Only a message coded with the private key can be decoded with the public key so George knows it came from Fred.

Step 2

• George drafts a reply and encrypts it with Fred's Public key.
• Only Fred's private key can decrypt the message, so it is secure
• Fred receives the message and decrypts it
• It's a valid message but Fred can't know who sent it, anyone with the public key could send to him. For this reason, George may encrypt the message with his private key as well as Fred's public key, to prove it came from George while ensuring that only Fred can read it.

## References

1. AllAcronyms.com
2. Course notes from G6016 "Networks", at the University of Sussex
3. "The Magic Words Are Squeamish Ossifrage", by Atkins, Graff, Lenstra, and Leyl
4. https://www.bbc.co.uk/news/uk-england-gloucestershire-11475101