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 g^a mod p to Bob
3. Bob chooses a different integer b, and sends g^b mod p to Alice
4. Alice computes (g^b)^a, while Bob computes (g^a)^b

At this point both parties (Alice and Bob) have the same (secret) information (g^a*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 g^a mod p = 28⁵⁸ mod 43 = 17, and sends 17 to Bob
3. Bob chooses his secret number b, let's say 39. Bob sends g^b mod p = 28³⁹ mod 43 = 2 to Alice
4. Alice calculates her version of the secret value g^ab using g^b (the value she received from Bob) : (g^b)^a mod p = 2⁵⁸ mod 43 = 4
5. Bob calculates his version of the secret value g^ab using g^a (the value he received from Alice) : (g^a)^b mod p = 17³⁹ mod 43 = 4

Alice and Bob have agreed on an encryption key, g^ab = 4, and only sent values that can only be used to calculate the key with great difficulty : p = 43, g = 28, g^a = 17 and g^b = 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 g¹, g², g³, g⁴, g⁵, … and compare with the g^a 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 2²⁵⁵ 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” stands for “Rivest&ndash;Shamir&ndash;Adelman”,<ref>''AllAcronyms.com''</ref><ref>Course notes from G6016 “Networks”, at the University of Sussex</ref> 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.”<ref>"The Magic Words Are Squeamish Ossifrage", by Atkins, Graff, Lenstra, and Leyl</ref> Although the challenge was withdrawn in 2007, the RSA algorithm is still widely considered acceptable for business purposes.

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.<ref>https://www.bbc.co.uk/news/uk-england-gloucestershire-11475101</ref>

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.

1. Public key encryption for Dummies
2. http://www2.krellinst.org/UCES/archive/modules/charlie/pke/

Cryptography Privacy