Math against technology

One of the most studied and complex activity in the human history is cryptography, a Jewish invention dated back to 18th century BC (the Atbash code). It was born to hide messages to everyone except the people who had to receive it. This activity grew very quickly especially during 15^th , 16 ^th and 17 ^th century AC, thanks to the studies of Leon Battista Alberti, Giovanni Battista Bellaso and Blaise de Vigenère.

All ciphers created before 20th century had one thing in common: they used the same key for encrypting and decrypting messages, and for this reason they are called “symmetric” encryption systems.

A little diagram of symmetric encryption

However, this characteristic wasn’t a problem before 20 ^th century, because at the time no machines with a sufficient calculation power to threat this security system existed.

Things changed with the invention of the first calculating machines, introduced for the first time in 1944 at the Institute of Advanced Studies of Princeton to solve complex mathematic and logic problems for military purposes.

Year after year these machines increased their efficiency, their speed and potency and a lot of encryption systems became completely inefficient.

A famous example of the power of these machines against symmetric encryption systems is certainly the failure of the Enigma machine. Enigma, which is based on a complex algorithm of symmetric encryption, was invented in 1918 and used by Germans during the Second World War to hide their messages.

Despite its complexity, in 1932 some Polish mathematician as Marian Rejewski, Henryk Zygalski and Jerzy Rozicki succeeded in forcing Enigma and created a copy of it.

A copy of the Enigma machine

The answer was the public key encryption, a system that’s still used nowadays.
After Enigma's defeat, it was absolutely clear that symmetric encryption was too weak against computers, and that it was necessary to create new methods to encrypt messages.The first algorithm of public key encryption is DH algorithm (Diffie-Hellman) and was introduced in 1976.

Diffie and Hellman

This algorithm is very useful for two partners who want to calculate safely a key to use to communicate using symmetric encryption. Its safety is based on the computational complexity of the calculation of the discreet logarithm.

How does it work?

Alfred and Bob want to generate safely a secret key. Alfred generates N, a very high prime number (for example 1024 bit, about 300 decimal ciphers), and he communicates it to Bob. Then Alfred also generates g, a generator number that certainly exists because N is prime.

Then:

1) Alfred generates a random number aa mod N and he communicates A to Bob using a public channel of communication.

2) Bob generates two numbers as Alfred did: b and B=g^b mod N and he communicates B to Alfred.

3) Alfred calculates k=B^a mod N;

4) Bob calculates k=A^b mod N;

We can deduce that the number k calculated by Alfred is the same of Bob’s one. In fact, k=g^ab mod N.

Now Alfred and Bob can communicate with the symmetric encryption and using k as their key.

For example:

Alfred and Bob choice N = 17 and g = 3 (3 is generator of 17).

1. Alfred and Bob choice N = 17 and g = 3 (3 is generator of 17).
2. Alfred choices a = 6 then A = 3⁶ mod 17 = 15.
3. Bob choices b = 11 then B = 3¹¹ mod 17 = 7.
4. Alfred calculates k = 7⁶ mod 17 = 9.
5. Bob calculates k = 15¹¹ mod 17 = 9.
6. So, the secret key is 9.

The great innovation of this technique is that even though someone could intercept the four numbers (N,g,A,B) he can't calculate k=g^ab because he doesn’t know neither a nor b.

Even though a=log_g(A) and b=log_g(B), the discreet logarithm calculation is computationally almost impossible.