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
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/
