This document explains the Diffie-Hellman key exchange method, a cryptographic technique allowing two parties to agree on a shared secret key without an eavesdropper being able to discover it.
Extract
[...] We say that a is congruent to b modulo p if a and b have the same remainder in the Euclidean division by p. We note a ? b For example ? 3 because 5 and 3 have the same remainder in the Euclidean division which is a 1. If b was between 0 and p - then it is the remainder of the Euclidean division of a by p. We can write 5 ? 1 is positive and strictly less than 2. [...]
[...] Well, no, it becomes very complicated to untangle. Mathematically, even knowing ga modulo P and gb modulo it is very difficult to find a or b. The power operation of power with modulo is very difficult to invert. This is what we call a one-way function. This is a function that can be easily calculated, but which is difficult to invert. In other words, given an image, it is difficult to find a predecessor. Example of illustration Let's take P = 17 and g = 5 on which Anna and Brieuc agree publicly so the spy is perfectly aware of these two values. [...]
[...] We can see it on an example with P = 13 for instance. By testing all numbers up to 12, I found that the primitive roots are only and 11. So if we take g = the powers of 6 modulo 13 spread well between 1 and 12. With these precautions, we thus have the essence of the Diffie-Hellman algorithm which therefore solves the problem of determining a common encryption key on a public channel. Thanks to this shared secret, they will then be able to use other cryptographic methods to determine a common encryption in order to communicate in a perfectly encrypted manner. [...]
[...] Discrete Logarithm On the other hand, the spy knows P = 17, and g = but only has 13 and 2 as intermediates. To find, for example, Anna's secret number, he must find a number that when applied to the power of 5 returns 13 modulo 17. This does not seem like it, but it is very difficult as an equation. The operation that must be solved to find the solution is what is called the discrete logarithm problem : Find a tel that ga modulo P = k Unlike the simple logarithm which would be : Find a such that " = It's possible in theory but tedious in practice. [...]
[...] Let's illustrate with an example. Let's take P = 15 and g = 4. Let's look at what the different powers of g modulo P are worth. With my choice of values we have : 41 modulo 15 = 4 42 modulo 15 = 1 43 modulo 15 = = 4 44 modulo 15 = 1 45 modulo 15 = 4 On se rend compte que bien qu'on ait choisi P = 15, the powers of g modulo P always fall on 1 or 4. [...]
