Peace be upon you all.
Welcome to our first crypto post here!
If you’re interested in cryptography , you’d know that key(s) are required to encrypt and decrypt the messages exchanged between two parties so what if those two parties can’t meet to agree on a shared key for example we are in the middle of a war how can two allied countries exchange the keys safely knowing that their enemies are always eavesdropping on them that’s where the public key exchange came in.
One of the most famous and was the first key exchange algorithm to be introduced is Diffie-Hellman , which later grew to become the base of the famous ElGamal public-key encryption system , which is used in the more famous SSL.
So let’s have a look and see how does it work and how to exchange keys between you and the other end of the communication line without worrying about the eavesdroppers .
Before we get to the algorithm itself , let’s refresh your memories with some mathematics that are needed to fully understand the algorithm itself.
You know that your key will be published publicly so we need to make it difficult to regenerate the private key from the public key so we will use a trap function.
Trap function : is an irreversible function that is easy to compute, but whose inverse is difficult to compute and by difficult we mean that the algorithm you are using to invert the function using the current resources will finish in a reasonable amount of time.
One of the most known difficult mathematical problems is Discrete logarithm problem
in order to understand it and how to use it as a trap function let’s have a look on prime numbers and modular arithmetic
Prime numbers: a number p is called prime if its factors (can be divided by) 1 and itself, Example: 2, 3, 5, 7, 11, 13, 17, 19…
there are several algorithms to check if the number is prime or not maybe we can discuss them later anyway let’s continue our lovely mathematical revision.
Given two primes p and q, you can easily multiply them together
N = pq
But given N it’s difficult to factor to p and q if they are large numbers.
RSA held several factoring Challenges before , check this link if you’re interested .
modular arithmetic : let’s compute some modulos to get the idea (N=13) , Example serves much better than words here.
1 mod 13 = 1
2 mod 13 = 2
3 mod 13 = 3
4 mod 13 = 4
5 mod 13 = 5
6 mod 13 = 6
7 mod 13 = 7
8 mod 13 = 8
9 mod 13 = 9
10 mod 13 = 10
11 mod 13 = 11
12 mod 13 = 12
13 mod 13 = 0
14 mod 13 = 1
so this how modular arithmetic work you have a set of finite integers starts from 0 to N-1.
Discrete logarithm problem: Let’s pick a prime modulus (N) let’s say 17 and find a primitive root for 17 which has a unique property that when raised to different exponents the result will be always within the group of mod 17 (1,2,3….16) in this case it will be 3.
3^2 (mod 17) = 9
3^5 (mod 17) = 5
3^16 (mod 17) = 1
so on and so forth
now let’s reverse it
3^? (mod 17) = 15
difficult ? imagine it with large primes ! now we have our trap function.
Now that you have the mathy fundamentals , lets get to the core of the algorithm.
Diffie-Hellman key exchange
As usual we will have our friends “Alice” and “Bob” who want to share a secret key for using in encryption.
first Alice and Bob will agree on a generator g and large prime p this will be publicly sent on the insecure channel .
Alice will pick another integer a which is secret and only Alice knows it.
Bob will pick another integer b which is secret and only Bob knows it.
now time for computations!
Alice computes A = g^a (mod p)
Bob computes B = g^b (mod p)
then they exchange A and B through the insecure channel so A and B are publicly seen
here comes the effective role of a and b.
Alice now have B she will compute B^a notice that only Alice knows a.
on the other hand Bob will compute A^b also notice that only Bob knows b.
Notice: B^a = (g^b)^a = g^a^b = (g^a)^b = A^b (mod p)
so they both of them now have shared the key B^a=A^b.
I hope you’re not lost in the details , so just in case here’s algorithm summarized:
Alice will pick a secret integer a <— private key
computes A=g^a (mod p) <— public key
sends A to Bob
receives B from Bob
computes B^a (mod p) <—-shared secret key
Bob will pick a secret integer b <—- private key
computes B=g^b (mod p) <—- public key
sends B to Alice
receives A from Alice
computes A^b (mod p) <—-shared secret key
Alice and Bob now will exchange information encrypted using the shared key that only them can compute.
so suppose that Eve saw that entire exchange and she has B and A
her only chance to know Alice’s Bob’s shared key is to compute either
g^a=A (mod p) or g^b=B (mod p)
which is the problem of discrete logarithm we mentioned above
let’s do it in numbers to get a better understanding
g=3 , p=17 ,a=15 ,b=13 ,A=6 ,B=12
A^b(mod 17)=B^a (mod 17)=10
so Eve needs to solve:
3^a (mod 17)=6 or 3^b (mod 17)=12 to get the shared secret
this may looks very simple on small numbers but on large numbers trust me it will be difficult and it will take time more than the age of the universe .
this is the end of my humble post I hope you enjoyed it next time we will talk about RSA or EL-Gamal maybe both 😉