The Science Behind Cryptocurrencies Cryptography-What is the Diffie-Hellman key exchange?

Cryptocurrencies like Bitcoin and Ethereum use a peer-to-peer decentralized system to conduct transactions. Since the entire process is online, there are fears that the transactions maybe volatile and hackable. What we are going to see in this guide is how cryptocurrency uses cryptography to make their transactions extremely secure.

What is the Diffie-Hellman key exchange?
Suppose, there are two people Alice and Bob and they want to attack a bank. However, they are on either sides of the bank and they can only communicate with each other via a shared line which is being tapped by the bank.

Something like this.

Keep in mind, everything that Alice and Bob say to each other will be eavesdropped upon by the bank. So, how can they both decide on a date to attack the bank without the bank getting to know about it and without Alice and Bob explicitly exchanging that information?

This conundrum can be answered by the Diffie-Hellman key exchange; it is a concept by which two parties can get hold of secret information without sharing it.

To understand how the Diffie-Hellman works, we need to use one of the most famous applications of this theory, the secret colour exchange.

For this there are 3 things that you need to keep in mind:

Alice and Bob both publicly agree that yellow is going to be the common paint that they are both going to use.
Alice then secretly keeps to herself that she is also going to use orange along with yellow.
Bob secretly decides that he is going to use aqua along with yellow.
Stage One

Since it was publicly declared that yellow is going to be the colour of choice:

Bank: Has Yellow
Alice: Has Yellow
Bob: Has Yellow
Stage Two

Now Alice mixes in her private colour aka orange with yellow and gets a composite colour which we will call CA.

At the same time, Bob mixes his private colour aqua with yellow and creates composite colour CB.

So, at the end of stage two this is what things look like:

Bank: Yellow
Alice: CA
Bob: CB
Stage Three

Now, Alice and Bob will send each other their respective colours, which will promptly get tapped by the bank. However, the bank now faces a problem.

Colour combinations are a trapdoor function.

While it is easy for someone to combine two colours and generate a third colour, it is infeasible for them to determine the first two colours from the given third colour. So, the bank will get hold of CA and CB but will have no idea which are the colours that has gone into its creation.

So, this is what things are looking like right now:

Bank: Yellow, CA, CB.
Alice: CB
Bob: CA.
Stage Four

Now, Alice and Bob are once again going to mix their secret colours into the mix that they have received from the other person, so now both of them are going to have a mix of yellow, orange and aqua which is brown. The bank, however, will only have CA and CB because they have no idea what the secret colours are.

So, this is what things look like now:

Bank: Yellow, CA and CB.
Alice: Brown.
Bob: Brown.
And this is where the trick lies, by not revealing their secret colours, both Bob and Alice have, in their possession, the colour brown, even though they never explicitly exchanged brown with each other.

This is what the diagram of this entire exchange looks like:
The mathematical form of the Diffie-Hellman exchange
Suppose there is a generator g for a finite field of size n. And in that field, we choose two random values a and b. It will be hard for an attacker to determine g^ab given only g, g^a and g^b. This is the condition which activates the trapdoor function. Given this condition, two parties can exchange messages and reach the same conclusion without explicitly communicating it with each other.
So, mathematically this is what happens.
Alice chooses a random value “a” from the field n and determines a message M1 such that:
M1 = g^a mod n.
Similarly, Bob chooses a random value “b” from the field n and creates message M2 such that:
M2 = g^b mod n.
Both Alice and Bob can now relay the message to each other.
Alice now determines special message K by doing the following:

K = M2^a mod n= g^ab mod n.
Bob now determines the same message K by:

K = M1 ^ a mod n = g^ab mod n.
So, both Alice and Bob reached the same conclusion without explicitly sharing this information.

This Diffie-Hellman key exchange was invaluable in the formation of asymmetric cryptography:

What is asymmetric cryptography?
Asymmetric cryptography utilizes two keys, a public key and a private to encrypt and decrypt a particular data. The use of one key cancels out the use of the other.

The diagrammatic representation of it looks like this:
The Rivest-Shamir-Adleman algorithm aka the RSA.
The Elliptical Curve Cryptography.
What is the RSA algorithm?

The RSA algorithm is the most widely used and popular asymmetric cryptographic algorithm in history. It is named after MIT professors Rivest, Shamir and Adleman who discovered this algorithm. Now, how does it work? The idea is derived from the breakthroughs that Diffie-Hellman had.

So, these are the variables that we will work with:

Suppose you have the secret message “m”. “m” raised to the power of a random number e and then the modulus of that with a random number N will give you the cipher text c.

Basically. m^e mod N= c

Take note, it is EASY to perform this function to get the output c BUT given only c, e and N it is difficult to get the message “m”. It will require a lot of trial and error. This is the one-way trapdoor function that we will apply to find “m”.

But now, the idea of the trapdoor function is to have a key which will make the reverse process (the decryption) simple for the recipient. So, for that we will need to find a random variable “d” which will make this process possible:
c^d mod N = m.
Now keep in mind, c = m^e mod N, so on substituting.
m ^ e ^ d mod N = m.
OR
m ^ ed mod N = m
So, in the above equations:

Public key = e and N.
Private key = d.
Now, before we even begin to see the method behind the madness, let’s do a simple calculation to see how the entire process works. (Shout out to Anthony Vance’s youtube channel for this example).

Suppose the message that you have to send is 42. In other words, m=42.
Along with that:
e = 17.
N = 3233.
d = 2753
The encryption process
c = m^e mod N.
Using simple substitution:
c = 42^17 mod 3233 = 2557.
So the cipher text is 2557.
The decryption process
Let’s do c^d mod N.
2557^2753 mod 3233
This gives us the value of m that is 42.

Genius isn’t it?

Now, remember when we talked about trapdoor functions we came to the conclusion that private and public key needs to be mathematical derivatives of each other in a way that:

F(private key) = public key, where F() is another trapdoor function.

It should be difficult for anyone to determine the private key from the public key. In fact, it should be so difficult that it will take the world’s most powerful computer decades upon decades to derive one from the other.

To answer this conundrum, we go back centuries and meet our next genius, Euclid.

Euclid and prime factorization

Euclid found out centuries ago that any number > 1 can be written as a product of prime numbers.

Eg. 15 can be written as 53. 255 can be written as 517*3. C= m^e mod N.

Let’s go back to our two equations

Here, N is the key in the trapdoor function. While N maybe publicly known it should be hard to determine prime factors that make up the number N. If you know the prime factors, then it is child’s play to discover the product N.

Eg. You can use your web browser to multiply two huge numbers and find the product in less than a second:

It took less than a second, 0.22 seconds, to do the calculation. And the bigger the number gets, it will take a little more time, but still, the calculations will be done super fast.
However, if you input a huge number and ask your computer to find its prime factors then it may take days, months and even years to find the prime factors.
This is the trapdoor function that cryptographers used to determine the value of N. This is basically, the heart of the trick.
This is what you have to do to use RSA algorithm:
First, generate a big random prime number P1.
Generate a second big random prime number P2.
Find N by calculating P1 and P2.
Hide the values of P1 and P2 and make N public.
N should be a huge number and it will take the most sophisticated machines in the world decades to find the values of P1 and P2.
So to summarise, N is the trapdoor and its prime factors P1 and P2 are the keys to the trapdoor.
Ok, so now we have determined how N is calculated and the trapdoor that works in it. But we still haven’t determined the value of “e” and “d” and we still haven’t seen how the private key is derived from the public key. In order to generate all these remaining values, we need to find a function that depends on knowing the factorization of N. And for that we need to go and visit our next genius, Leonhard Euler.
Euler and breakability
In 1760, Swiss mathematician Leonhard Euler did some path breaking studies. He studied the nature of numbers and more specifically the breakability of the numbers which he called the phi function.
Basically given phi(N) where N is a random integer, the value of N will be the number of numbers between 1 and N which do not share any common factors with N.
So, if N is 8 then:
The numbers between 1-8 are: 1,2,3,4,5,6,7 and 8.
Among these numbers, only 1,3,5 and 7 don’t share any factors with 8 except 1.
Meaning, phi(8) = 4.
Now, calculating the phi function is difficult except for one case. To know this, check out the following graph. The graph tracks the distribution of phi values over integers upto 1000.

See that straight green line at the top which is conveniently arranged? That is the phi of prime numbers. Since the definition of a prime number is that it is unfactorizable apart from by itself, for any prime number p the phi(p) = p-1.
Let’s see this in practice. Suppose you have a prime number 7.
The numbers between 1 and 7 are: 1,2,3,4,5,6,7.
The only number that shares a factor with 7 in this series is…7!
So the phi(7) = 6.
Similarly, if you were to find the phi of a large prime number say 541 then:
Phi(541) = 541-1 = 540.
It becomes very simple to calculate the phi for a prime number. And this gains, even more, significance when you consider the multiplicative nature of phi functions. What is the multiplicative nature of phi functions?
For any two numbers A and B:Phi(A*B) = phi(A) * phi(B).

Now, let’s go back to algorithms. Alice has determined two large prime numbers P1 and P2 and has determined a number N by doing P1 * P2.

So, using the multiplicative property of phi functions:

Phi(N) = phi(P1) * phi(P2).

OR

Phi(N) = (P1-1)*(P2-1).

And just like that, we have discovered the trapdoor function for phi. If we know the prime factors of N then it is easy to calculate the phi(N).

For eg. the number 77 has prime factors 7 and 11.

So phi(77) = (7-1)*(11-1) = 60.

It becomes very easy when you know the prime factors of N.

Now, one final bit of mathematical wizardry was required. We have the phi function and we have the modular exponentiation functions that we have determined before, we need to bring these two together in one neat equation.

And for this, we turn to Euler for help once again.

The Euler’s theorem
Euler’s theorem states that:

For any two numbers m and n that don’t share a factor:

m ^ phi(n) ≡ 1 mod n

Meaning, for any two numbers m and n, as long as they don’t share a factor, m raised to the phi(n) divided by n will always leave a remainder of 1. Let’s see this in an example.

Suppose, m= 8 and n = 5.

Phi(5) = 4

So, 8 ^ 4 = 4096.

Replacing this in the Euler’s theorem equation:

4096 ≡ 1 mod 5 holds true because 4096 on being divided by 5 leaves a remainder of 1.

Now, the equation: m ^ phi(n) ≡ 1 mod n needs to be modified a little bit before we get our final solution.

Modification #1

1^k = 1 for all k.

So, keeping this in mind, if in m ^ phi(n) ≡ 1 mod n we multiply the exponent phi(n) with any number k, the final solution will be 1^k which is still 1.

Now, this modifies the equation like this:

m ^ k*phi(n) ≡ 1 mod n

Modification #2

For all m, m*1 = m.

So, in our modified equation, if we multiply both sides by m we get:

mm ^ kphi(n) ≡ m*1 mod n

Which becomes:

m ^ k*phi(n)+1 ≡ m mod n

Now, this is the final form of our equation.

Before we proceed, let’s bring back the old equations to refresh our memory:

c = m^e mod N.
m = c^d mod N
m ^ e*d mod N = m
Now, checkout the last equation doesn’t that look similar to our new modified equation:

m ^ k*phi(n)+1 ≡ m mod n

And this is the breakthrough.

On comparing the two equations, we get:

ed = kphi(n) + 1

We FINALLY have an equation where the value of e and d depends on phi(n).

Now, since we already know the value of e, it is easy to calculate d, the private key, ONLY if the factorization of N is known (which is a secret that Alice has kept to herself).
So, d= (kphi(n) + 1)/e.
This is the trapdoor that will undo the encryption done by her private keys e and n.
Example to see how this all works
Suppose Bob and Alice are exchanging messages.
Bob wants to send a message M to Alice where M=89.
Now, Alice needs to generate her keys.
She uses to prime numbers p1 and p2 where:
P1 = 53.
P2 = 59.
N = P1 * P2 = 53 * 59 = 3127.
Phi (N) = Phi(P1) * Phi (P2) = (P1 – 1) * (P2 – 1) = 52 * 58 = 3016
Now, she needs to generate a value e which will have no factors with the value of phi(N).
So, she decides e = 3.
Now, she will generate her private key d:
d = (kphi(N) + 1)/e
Taking k = 2 we get:
d = (2* 3016 + 1) / 3 = 2011.
Now, she will lock up all the values except N and e which are her public key and make the knowledge of these two global.
Bob encrypts the message
Now, Bob needs to send message M, which is 89, and he needs to calculate the cipher text c such that:
c = M^e mod N.
Now, we know that: M = 89, e = 3 and N = 3127.
So: c = 89^3 mod 3127 = 1394.
He then sends it over to Alice.
Alice decrypts the message
Alice gets the cipher text and all that she has to do is to decrypt it using her private key d which we know to be 2011.
So, Alice does this calculation: c^d mod N
1394^2011 mod 3127 which is 89 aka the original message M.
And this, is the RSA algorithm, the most widely used cryptographic algorithm

RSA vs EEC. Why did bitcoin and ethereum go with elliptical curves?

The reason why EEC was chosen over RSA is because it offers the same level of security as RSA by consuming far less bits. Eg. for a 256-bit key in EEC to offer the same level of security RSA will have to provide a 3072-bit key. Similarly, for a 384-bit key in EEC the RSA will have to provide a 7680- bit key to provide the same level of security! As can be seen, EEC is far more efficient than RSA.

Fun Fact: The NSA has declared that a 384-bit key in EEC is strong and secure enough to encrypt top level secret documents.

So how does the signing process work (a simple overview)?
Suppose Alice wants to send 500 BTC to Bob. She will follow the following steps:

She will create transaction and sign it off with her private key.
She will the send the transaction to Bob’s public address.
Bob can then decrypt the message by using Alice’s public key to verify that it was indeed Alice who sent him the bitcoins and the transaction is deemed complete.
If this were to be shown in an image this is what it will look like:

How do the keys work in blockchain?

As mentioned above, bitcoin and ethereum use elliptical curve cryptography. So, what happens when someone sends you money on the blockchain? They send you the money to your public address which is basically the hash of your public key and some additional information. As we have seen above, the public key is derived mathematically from your private key.

Public and private keys are both large integer values and they are represented, for brevity’s sake, via the Wallet Import Format (WIF) which consists of letters and numbers. A sample private key and public address looks like this in WIF:
So how does the signing process work (a simple overview)?
Suppose Alice wants to send 500 BTC to Bob. She will follow the following steps:

She will create transaction and sign it off with her private key.
She will the send the transaction to Bob’s public address.
Bob can then decrypt the message by using Alice’s public key to verify that it was indeed Alice who sent him the bitcoins and the transaction is deemed complete.
If this were to be shown in an image this is what it will look like:

Conclusion
So, as can be seen, public key cryptography aka asymmetric cryptography is one of the backbones of cryptocurrency. It is impossible to even imagine how bitcoin and ethereum would have been secure without it. Every time you make a transaction, be thankful to all the mathematicians and cryptographers who have made this wonderful medium possible.