What are principles of Diffie Hellman key exchange? That's what we will be looking at in this video. The aim is not to present the entirety of the theory, but by working through an example to get a feel for it. There are mathematically simple operations and there are those which are more complex. One example of simple operation, which can be performed by programmable logic devices, is the multiplication of integers. We can also easily carry out modulo p operations, for example, multiplying a number by itself multiple times in a row, that is to say exponentiating is simple. We consider modulo p calculations of g to the power n, Note that p is a prime number. In this example p is 11 and g is seven 7. 7 to the power of zero makes 1 as always. 7 to the power of 1 makes 7, modulo 11, which gives us 7, 7 square is 49. So that's 11 times 4 plus 5. The rest of the division by 11 is 5. So seven squared modulo 11 is five. We could go on 7 cubed, 7 to the power of 4 and so on. We can see, as p and g have been chosen carefully, that with 7 to the power of n modulo 11, we can run through all the values from 1 to 10. One, 2, 3, 4, 5, 6, 7, 8, 9, 10. For every number between one and 10, we can do the operation inversely. In other words, from X in this row, to find n such that g to the power of n is x, and of course mod P, which is in our example modulo 11. This is a logarithmic function. You can see the correspondences here. One corresponds to zero. The log of one is 0. The log of 2 is 3. And why? Because we look back here and see that exponent three gave 2, and so on. It just so happens that this discrete logarithms operation is more complex and to calculate it, we need to run through almost all the cases. To find the logarithm of eight, we have to run through all the trials until we find that seven to the power of 9 mod 11 gives us 8. Here is another example where p is 23 and g is 5. 5 to the power of 6 mod 23 gives us 8. That means that the logarithm of 8 is 6. Let's take a look at how this is used in most cases. Alice and Bob publicly agree on modulo p and base g. Alice draws a secret value, a. Bob draws a secret value, b, which will make up the private key. They then each make g (the base) to the power of their secret value mod p and send this key, which will be the public key, to one another. When they received the key, they just take it's as it is. Here, G to the power of b modulo p was received from Bob. Then it needs to be exponentiated with the secret key. We have g to the power of b mod p... to the power of a mod p, which is equal to g to the power of b to the power of a mod p. And that is equal to g to the power of b times a, which gives us the same result as g to the power of a times b mod p. Bob makes the same calculation but he receives g power a modulo p. and he knows b. He can therefore exponentiate and find the same shared key. Anyone listening to the channel sees g. to the power of a mod p and g to the power of b mod p. There is no way for them to work out a and b in a reasonable time, because all these numbers are huge. It is possible that they might try to multiply the two values, but g to the power of a mod p times g to the power of b mod p mod p, this gives us g to the power of a times g to the power of b mod p, which is g to the power of a plus b mod p, and this is different to g to the power of ba mod p. So, there is no way that someone listening into the channel can calculate it. A quick example in a digital context. Here, we are using small numbers to keep things simple but in practice we use values for p, a and b, which can be on 100 or 200 bits. They will be extremely large numbers. Alice chooses 6. She calculates 5 to the power of 6 mod 23. That gives us 8. She sent that to Bob. Bob chooses 13. He calculates 5 to the power of 13 mod 23, which gives us 21. 21 is sent by Bob to Alice who will calculate 21 to the power of 6 mod 23 and we get 18. In the same way, Bob takes the eight he receives and bring that up to the power of 13, which is his private key. Eight to the power of 13 mod 23 also makes 18. The shared key is 18 and no one in the middle can know that. In the case of 5G and SUCI, We don't use this exact principle. We use elliptic curves, which are represented by equations like this. Here is an example of representation of an elliptic curve and we will define the addition of two points: to add point P and Q, we draw a straight line PQ. This has another intersection with the elliptic curve other than P Q. And we take the symmetry of the point in terms of X axis. That gives us the sum of P and Q. We can see that it's possible to add P by P. We take the tangent. For example, let's consider the point P'. In taking the tangent, we obtain a point by taking the actual symmetry. We obtain R', which is P'+P' represented here. We can repeat this, adding R' and P' and so on. The logarithm operation here consists of determining P from a value of P added n times. Key exchanges work in a similar way. For those who are really interested, they can look at the recommendations here, which specify the elliptic curves, which are used, but they only make sense to specialists.
