I recently started studying again, this time as an attempt of deep-diving into some security concepts for one of my PhD courses. It’s interesting how, as much as you try to escape from it, mathematics will sooner or later catch you somewhere and you will need to learn a bit more of it. At least that happened to me…
In this process I realised that if you go beyond simple security theory and network device configuration all other stuff is pure mathematics.
The reason behind my unplanned course in mathematics is explained through the rest of this text. It will explain what is network security and where is the math needed to get network communication secure. In the end, it was actually fun.
If you want two distant computers to talk with each other so that nobody else can see what they are talking about, you want to make a secure network connection between them. Security in this case means that you need to connect those machines to the network and be able to make the communication a secret communication. Secret communication through public communication system is possible by using encryption.
The get encryption you need to have a shared secret. Shared secret means that is basically a key or password that is known only by sender and receiver. Imagine a treasure chest you will use to send some stuff to your friend. If you want to send it so that nobody on the way can see what’s inside or steal what’s inside, you would need to lick it with the key. But if you want your friend to open it, he will need to have the copy of the same key.
Encryption is enabling to encapsulate our digital messages into envelopes that are scrambled by a complicated mathematical algorithm and which can be easily solved by using the “encryption key”. Encryption key is able to decrypt the message, meaning it will turn back into readable form. Without the “key” there is almost no chance that someone could read the message as all letters will be changed into some other symbols thus they are encrypted.
Key Exchange issue
Encrypting the message, although not trivial, is fairly simple and is enabled by known algorithms. Getting the key to decrypt the message to message receiver is more complicated task.
Imagine, if you wanted to use the treasure chest from above example, you will go and meed your friend before sending the treasure chest and you would give him the copy of the key from the chest.
In digital world it’s not so simple. Imagine, you are encrypting the messages exchanged by you and PayPal when you are checking your account billing info or sending money to someone. Where and how would you meet with PayPal before opening their web page trough an encrypted Internet tunnel?
It’s not really possible.
Key Exchange solution – Diffie-Helman Key Exchange Protocol
You will se in the proceedings of this article that Diffie-Helman process is not actually a key exchange process but a key generating process. The key is only one and is not exchanged, that key is calculated on both sides.
As it turns out Whitfield Diffie and Martin Hellman were very clever fellows and also excellent mathematicians. They soled our problem with key exchange by inventing a method which enabled computers to talk to each other in plain text (which can be seen by anyone on the network) and in the end of the exchange those two computers will know the “key” without the possibility for others to get it.
This process is enabled by using modular arithmetic, raising numbers to a power and successive squaring, and the one and only Diffie-Helman exchange technique.
The name is scary but is really simple actually. In modular mathematics numbers are going until the modulus. They are never bigger than the modulus. Imagine the clock for example, clock in a great example of “mod 12”. There are no numbers after 12. There is no 13, 14, 15. After 12 you will get back to 1.
Calculating the modulus is basically dividing the number with modulus and taking the remainder.
17 mod 3 = (3 * 5 + 2 )mod 3 = 2
The reason to use modular mathematics is to get manageable numbers even if we make really complex stuff like high-end encryption. The thing is that you can always cut the number if it is bigger that the modulus and keep thing manageable.
Look at this one:
22^17 mod 77 = 66249952919459433152512 mod 77 = 22
Successive squaring helps computers to calculate integer powers of a number more quickly. It does that by diminishing the number of steps it takes to calculate it and thus diminishing processing cycles needed to calculate integer to the power of a number.
So if you take a fairly basic example of 3^14 we can see that by normal means we would need 14 multiplication steps to get the result:
3^14 = 4.782.969
3^14 = 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3
Successive squaring is making the process shorter by squaring x so many times until the current power of x exceeds y:
So we take 13 which is 1110 in binary: 1110 = 14 = 8 + 4 + 2 and we make the next steps:
- 3^1 = 3 we don’t use this one as it is 0 in binary number 14 (1110), we take the next three:
- 3^2 = 9
- 3^4 = 9^2 = 81
- 3^8 = 81^2 = 6561
- 9 * 81 * 6561 = 4782969
So we calculated the thing in 4 steps and not in 13, it’s better and faster indeed.
This process is really ingenious. Two computers are exchanging plain text information between them and everyone can see what are they speaking about. After a while, both of the computers share a secret key called shared secret that they could use to encrypt future communication.
We can imagine a publicly known key that is composed of two prime numbers x and y. This key K(x,y) is a public key that everyone on the Internet knows. Sender and receiver are each calculating a secret number which will be used to encrypt the communication between each-other. They are using public key K(x,y) to calculate the shared secret key that needs not to be known to anyone else but them.
- One of them comes up with two prime numbers x and y and tells it to the other. They are send in plain text so everybody can see those numbers crossing the network.
- Sender picks a secret number a and calculates A = x^a mod y. He then sends the result “A” to the receiver on other side.
- Receiver does the same. He picks a secret number b and the computed number B in the same way, B = x^b mod y and sends the result to sender.
- Now, Sender received number B and receiver received number A. They calculate the secret key by doing this:
- Sender calculates secret S = B^a mod y.
- Receiver calculates secret S = A^b mod y.
This math is crazy. It enables both sender and receiver to generate the same secret key S by using values a and b which are newer sent across the network by using modulo exponents rules below:
(g^a mod p)^b mod p = g^a*b mod p
(g^b mod p)^a mod p = g^b*a mod p
So what that means?
Diffie-Helman is a technique that enables two sides to generate a shared secret so that the secret can’t be seen by observing the communication. By using Diffie-Helman process you are not sharing the key across the network, you are actually creating a key together which will be used later to encrypt the communication.
This process is often misinterpreted as asymmetric cryptography. Diffie-Helman is actually not a cryptography mechanism but is only a method for securely generating shared secret keys which are the most important part of cryptography process. After Diffie-Helman generates the same key on both sides of the communication both sides can use that key as a password for AES or Blowfish, or any other algorithm that uses shared secrets.