D-H

Diffie–Hellman key exchange (D–H) is a specific method of exchanging cryptographic keys. It is one of the earliest practical examples of key exchange implemented within the field of cryptography. The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher.

Of course there is a problem at the time encryption require two parties to first share a secret random number know as a “key”, so how could two people who have never met agree on a secret shared key without letting eve who is always listen also obtain a copy of the key?.

In 1976 Whitfield Diffie and Martin Helmand devised an amazing trip to do this, first lets explore how this trick is done using colors, how could Alice and Bob agree on a secret color without Eve finding it out; the trick is based on two facts: 1)it’s easy to mix two colors together and 2) given a mix color it’s hard to reverse it in order to find the exact original colors, this is the basics for a lock, easy in one direction hard in the reverse direction, this is known as a one-way function.

Now the solution works as follows:

First they agree publicly on a starting color, lets says yellow, next Alice and Bob both randomly select private colors and mix them into the public yellow, in order to disguise their private colors, now Alice keeps her private color and sends her mixture to Bob and Bob keeps his private color and sends his mixture to Alice, now the part of the trick, Alice and Bob add their private colors to the other person mixture and arrived on a shared secret color, notice how eve is unable to determine this exact color since she needs one of their private colors to do so.

Now to do this with numbers we needed numerical procedure which is easy in one direction and hard in the other, this brings us to modular arithmetic also known as clock arithmetic, for example to find 46 mod 12, we could take a rope a blank 46 units and wrap it around the clock of 12 units which is called the module, and where the rope ends is the solution, so we say 46 mod 12= 10. 

Now to make this work we use a prime modulus such as 17, then we find a primitive route of 17 in this case 3 which has this important property that, when raise to different exponents the solution distribute uniformly around the clock

, 3 is known as the generator, if we raise 3 to any exponent “x” then the solution Is equally likely to be any integer between 0 and 17; now the reverse procedure is hard: say given 12 find the exponent 3 needs to be raised to (3^(?) mod 17 = 12 ), this is called the discrete logarithm problem, and now we have our one-way function easy to perform but hard to reverse

.

Given 12 we would have to resort to trial and aired to find matching exponents, how hard is this?, 

well with small numbers its easy but if we use a prime modulus of hundreds of digits long, it becomes impractical to solve even if you had access to all computational power on earth, it could take thousands of years to run through all the possibilities, so the strength of a one-way function is based on the time needed to reverse it.

now this is our solution: first Alice and Bob agree publicly on a prime modulus and a generator (in this case 3 mod 17), then Alice select a private random number say 15 and calculates 3^(15) mod 17 = 6

and sends this result publicly to Bob, then Bob selects his private random number say 13 and calculates 3^(13) mod 17 = 12, and sends this result publicly to Alice, and now the heart of the trick, Alice takes Bob’s public result and raise it to the power up her private number (12 ^(15) mod 17 = 10) to obtain the shared secret which in this case is “10”, Bob takes Alice’s public result and raise it to the power of his private number (6^(13) mod 17=10 ) resulting in the same shared secret, notice they did the same calculation though it may not look like it at first 12^(15) mod 17 = 6^(13) mod 17 ), consider Alice equation (12=3^(13) mod 17) so her calculation was the same as (3^(13^15) mod 17 ), now consider Bob equation (6= 3^(15) mod 17) so his calculation was the same as (3^(15^13) mod 17)  notice they did the same calculation with the exponents in a different orders, so they both calculated 3 raised to the power up their private numbers, without one of this private numbers (15 or 13) Eve will not be able to find a solution, and this is how its don

bibligraphy : https://www.youtube.com/watch?v=YEBfamv-_do

khan Academy : https://www.khanacademy.org/