I don't know what year Diffie and Hellman worked on this. They didn't like this notion of these keys being able to be snatched while they were being exchanged. So Diffie-Hellman is a method to securely establish a known secret, a key, okay? Between two parties over an insecure channel. There's a nice article there, Wikipedia, has more information. So this uses colors to get the point of cross what's have in computationally, okay? So Alice and Bob agree ahead of time on some kind of plain color. So we've got yellow here. And then they each pick a secret color that only they know. And they mix those two colors together to get whatever color that is. I'm color blind, so I'm not very good with colors. What color is that? [LAUGH] It was a tan. Beige, I don't know, okay? So agreed upon or starting common paint. They each pick a secret color and they blend these two together, okay? Alice does this operation on her side and Bob does that operation on his side. And then they, [LAUGH] Getting stay back. Stay away from the screen. They exchange these across, some kind of public and secure transport, okay? So Alice receives this combination from Bob, and Bob receives this combination from Alice. And then they each use their own secret color and combine that to establish a common secret. And they end up with a common secret, which is the key that they can then use for symmetric encryption if they wanted to. The simplest and original implementation of the protocol uses the multiplicative group of integers modulo p, where p is prime, and g is a primitive root modulo p. If you want to understand what a primitive root modulo n is, you can go read about that. But we'll follow the numerical example here. These values are chosen in this way to ensure that the resulting shared secret can take any value from to p minus 1. And here's an example of a protocol a. Non-secret values are in blue and secret values are in red. Alice and Bob agreed to use a modulus. Is that original color, yellow, I guess in the example and they say p=23. And they picked a base g = 5 which is a permanent root modulo of 23. And Alice chooses a secret integer a = 6, and then sends Bob. She computes g to the a mod p as value A and sends A to Bob. So in this example, A = 5 to the sixth mod 23, we get 8. Bob chooses a secret integer b, and then sends Alice g to the b mod p as B. So this can be B is equal to 5 to the 15th minus 23 is equal to 19. And Alice computes the secret key as B to the A minus P, and do the math on that and you get 2. Bob computes s again as A to the B mod P. You do the math and you get 2. So they have now established a shared, secret, common key. And both can use the number 2 for their encryption key in a symmetric AES algorithm, for example. This got converted to PowerPoint. This did not convert very well, but what this said over here is G to the A to the B is equal to G to the B to the A. If it wasn't clear, other equivalent numerically. And this chart looks at what Alice knows is unknown, what Bob knows and what's unknown and what Eve knows and unknown. So all Alice doesn't know is the secret number that Bob picked was b. All Bob doesn't know is the secret that Alice picked which was a. But if Eve picked up the modulus of P and G in these values, but Eve doesn't know a and b because those were private, okay? And Eve can eavesdrop and pick up those computations of a equals a and b equals 19. But given this information and not knowing a and b, cannot compute s. Or is impractical to compute S. That's the notion of Diffie-Hellman. So yeah, as I mentioned a moment ago. So now Alice and Bob can use symmetric encryption over an insecure channels using S as a common encryption and decryption key. As a way to exchange keys securely over some kind of public insecure mechanism. So I'm going to make a comment on that. As I'm not a cryptographer, but I've known cryptographers and I've had interactions with other people in the field who have way more experience with security than I do. I understand that there may be some potential limitations. And Diffie-Hellman may not be as secure as what I've presented here. So when you get out into the working world and the subject of secure key exchange comes up, and it's why I learned about Diffie-Hellman. You need to check with your cryptographer at your company, or somebody that's very knowledgeable about it to see if there are any threat vectors or avenues of attack on Diffie-Hellman. Next encryption algorithm we're going to look at is called PGP, or Pretty Good Privacy. It was created by Phil Zimmerman in 1991, so it's been around for a while. Follows a standard, RFC 4880. And here's how it works. We saw an example of public private key last time. So Bob has Alice's public key wants to send Alice message is the message, hi Alice. So Bob generates a random key and uses Alice's public key to encrypt this random key. So that's this blue key here. So we can get this encrypted random key. And also Bob takes this random key and uses it, feeds it into encryption algorithm to encrypt the actual message. So we get the message here is encrypted and this random key is encrypted. And this is what's sent across to Alice across an insecure channel. So here's Alice over here waiting patiently for this message from Bob. And Alice receives the encrypted data and this encrypted random blue key here. So Alice uses her private key, which is pair of the public key she gave and provided to Bob to decrypt this random key. So Alice can produce this value here. That key is then fed into second decryption operation which decrypts the message and Alice can read the clear text or plain text message. RSA, the names of the gentlemen that put this algorithm together. Who's heard of RSA algorithm before? Yeah, okay, few of you. Okay, good. It involves 4 steps. I took quite a bit of this information from Wikipedia. Key generation, key distribution, encryption, and decryption. So the tenant of RSA is that it is practical to find three very large positive integers E, D, and N such that with modular exponentiation. And there is an example B raised to the Y mod M or M as the modulus. For all integers m at m raised to the e raised to the d is equivalent to m(mod n) and m to the d to the 3 is equivalent to m(mod)n. And even knowing e and m and n, it can be very, very difficult to find d here, computationally expensive. So key generation process starts off by choosing two distinct prime numbers, P and Q, chosen as random and in approximately similar magnitudes. And you compute n as the product of p times q and n is used as the modulus. And this is also the key length you see in RSA key gives some length to all keys, some length associated with them. N is a length of the key and you compute lambda of n which is the least common multiple of p minus 1 and q minus 1 and you keep those values private. And you choose an integer e such that it is greater than 1 and less than the least common multiple of n. Where e and λ(n) are coprime, and that means that they're both only divisible by 1. And determine d to take e to the -1(modλ(n)), that determines the value of d. The public key consists of N and D. So those were given out, those are provided for people two use on their encryption side to say, send me messages. The private key consists of ND and are kept secret. And PQ and lambda N also need to be kept secret. Bob wants to send Alice a message M after receiving N and e from Alice. So Bob reduces his message to an integer m where 0 <= m <= n by using a previously agreed upon reversible protocol known as a padding scheme. I'm not going to go in all padding scheme. But I'll gave you a link to go looked at. Point is that you can take a message and reduce it down to this integer and then you can take that integer and re-expand it into the message. It's a reversible operation. Ciphertext is then computed as m to the e mod n, it becomes your ciphertext, so that's what you would send across the link. On the decryption side, Alice takes the, which letter was it? C? [LAUGH] Ciphertext, raise it to d, which is equivalent of m to e to the d, which equal to m(modn) and then reverses the padding scheme to extract the original using this reversible padding scheme to produce the original message. So that's the gist of the RSA algorithm.
