The world we know is going more and more digital. Shopping, meeting with friends, signature recognition, and document management – are just some of the most common activities that are increasingly straying from their traditional ways.

A lot of data used in these processes is sensitive and we do not want just anyone to have access to it. This is why we encrypt more and more data. But what is encryption exactly?

Let’s start our introduction to cryptography with a journey into the distant past, analyzing various examples of cryptography over the course of history.

Early cryptography & one-way function

What is cryptogtaphy? Let’s explain it with an example.

• In the early days of cryptography, it was required for all parties interested in encrypting their messages to know a special number – the key. This key served for both encrypting and decrypting messages. As long as it is kept secret, all communication is safe.
• In 1976, Wilfred Diffi and Martin Hellman came up with a great way to make it work in practice. Since you are still green, let’s explain it with colours 🙂

The trick is based on two simple facts. First of all, it’s easy to mix two colours. Secondly, doing the reverse, that is, arriving at the two primary colours from the secondary one, is difficult.

That’s how the padlock mechanism works – a piece of information can be transformed in one way, but it can’t be easily transformed back into its previous state. In math, they call it a one-way function.

Let’s explain this with a somewhat more descriptive example – of two lovers: Alvaro and Julia.

Alvaro (on the left) wants to send Julia (on the right) a love message in a way so that only she can read it. In our example, this message is a specific colour.

The red individual in the middle is Romeo, who just can’t get over losing Julia and wants to listen in on all of their conversations. He can successfully gain access to each and every message they exchange.

Alvaro and Julia start by picking a common primary colour. Let’s make it yellow.

Next, each of them individually picks a private colour. Alvaro chooses blue, Julia goes with red. Each of them mixes their private colour with the common colour (yellow) in order to mask them. As a result, two different mixtures are created.

Alvaro and Julia send the resulting mixtures to each other. The private colours are still only known to each of them alone.

Here comes the most important part – both Alvaro and Julia mix the mixtures they received with their own private colour. Now, they have a common secret colour.

Romeo is unable to arrive at that colour – in order to do that, he would have to know at least one of the couple’s private colours. That’s the essence of cryptography.

Modular arithmetic in cryptography

Now, all we need to do is to translate all of these findings into proper math formulas and we will be good to go.

This is where we’re going to take advantage of modular arithmetic. In particular, we’re going to use the modulo operation, which finds the remainder after division. For example, 8 mod 5 = 3, since 8 divided by 5 leaves us with the remainder of 3, 46 mod 12 = 10 etc.

Let’s start by finding the primitive root of a prime number (generator). For 17, it would be 3. What it does is that if we exponentiate a generator to any x base (3xmod 17), each integer between 1 and 16 is equally likely to be the result.

The reverse operation is much harder. It’s very difficult to find an exponent of 3, for which the modulo operation results in the remainder of 12. This is also known as the discrete logarithm problem.

One solution would be to search for x on a trial and error basis. It’s not too difficult for smaller numbers. As for gigantic numbers with digits in hundreds, however, even the fastest PC can take thousands (!) of years to find the right answer.

Let’s try to go through our previous example once again, but this time with numbers.

First, Alvaro and Julia agree on a common prime number and a generator – 17 and 3.

Then, Alvaro picks his private number (15) and calculates 315 mod 17. He openly sends the result (6) to Julia. She chooses her own private number (13) and does a similar operation: 313 mod 17. The result (12) is then sent to Alvaro in a similar fashion.

The most important phase of the process takes place now. Alvaro exponentiates Julia’s public result to his own private number – 1215 mod 17 = 10. Julia does the same – 613 mod 17 = 10. That way, they arrive at a common secret number – 10. Even though it may not be obvious at first glance, they did the very same operation.

The number 12 that Alvaro received is the result of 313 mod 17. He followed up with (313)15 mod 17. The number 6 received by Julia was calculated from 315 mod 17, followed by (315)13 mod 17. They exponentiated in a different order, but it is not relevant as far as the final result is concerned.

They both exponentiated their results to the power of their respective private numbers and performed a mod 17 operation. Romeo is unable to arrive at the final result without knowing at least one of the two private numbers (13, 15).

What if it was possible to agree on a common key (encryption method)? What if Alvaro had many lovers and had to communicate with all of them? Creating a separate common key with each of them would be quite troublesome. And what if we replaced Alvaro with a bank? Sending thousands of thousands of unique messages is not an option. Luckily, there is another way.

The birth of asymmetric encryption

Back in 1970, British Mathematician James H. Ellis proposed a method known as non-secret encryption. The basic idea is simple – opening and closing are mutually opposite processes. For example, Alvaro can buy a padlock, keep the key, and send the open device to Julia. She then encloses her message with it and sends it back to Alvaro. There is no exchange of keys here.

Alvaro simply makes his padlock public so that everyone who wants to send him a message can use it. He can then open all of these messages with his private key. This is the basic idea behind asymmetric encryption. From now out, we will focus on asymmetric cryptography, a dominating approach in modern computer security.

Ellis couldn’t come up with a Math-based solution to that problem, but he did understand how it should work. There was a need for both an encryption key and a decryption key.

Let’s make his idea clearer with another example straight from a romance novel.

Julia wants to send her colour to Alvaro and at the same time keep it secret from Romeo’s watchful eyes.

Let’s assume that we can generate a secondary colour for each given colour simply by extracting its components with a special filter. At the beginning, Alvaro generates his private colour (the key) – red – in a completely random fashion. He also has a device that can employ the special filter to generate secondary colours.

He uses it on his red colour, getting cyan. He sends it to Julia. She wants to send a secret shade of yellow (the message) to him. She mixes her colour with the one she received from Alvaro and sends the mixture back to him. In other words – she received an open padlock and sent it back, closed, with her own message safely hidden from Romeo.In order to find out what colours Julia picked, Alvaro uses his private colour (the key) to extract cyan. Now he can identify the shade of yellow Julia chose (the message). He’s simply cancelling the effect of his public colour. Romeo can’t access the yellow message without Alvaro’s private colour.

Asymmetric encryption is pretty neat, but the concept had not been useful for cryptography, until it was found out how to express it with Math.

Asymmetric cryptography & trapdoor one-way function – RSA algorithm explained

Clifford Cox was the one to find a Math solution to this problem. He came up with a special kind of one-way function called a trapdoor one-way function. It’s quite easy to calculate, but it’s next to impossible to find the value of its reverse function unless you have a special piece of information called the trapdoor.

His method takes advantage of modular exponentiation. Ever since Cox proposed it, the trapdoor has become an important tool in computer security. Let’s explain it in detail.

This time, Julia converts her message into a number (let’s call it M). She multiplies it by itself e times, where e is a public exponent. Then, she divides the result by a random N number. We arrive at the remainder of the division – C.

Me mod N = C

It’s relatively easy to calculate. However, if all we know is C, e and N, finding M is really difficult. The only available route is the trial and error approach. In other words, we have found a Math-based way to recreate the padlock mechanism.

• Now let’s try to find our key, that is, the trapdoor that will make it easier to decipher the message. We need to exponentiate our C to another exponent (let’s call it d) in order to reverse the previous operation.

Cd mod N = M

• Both operations boil down to the same:

(Me)d mod N = M

The e number represents encryption, while d is responsible for decryption. Alvaro must find the value of d and e in a way that will not be possible to recreate for Romeo. To make it happen, Cox turned to Euclid.

It was no one else but Euclid who proved that any given number has only one prime number distribution. Let’s make it our secret key.

It turns out that prime number distribution is a complex problem. It’s especially difficult for computers. Multiplying, which essentially comes down to moving bits around, is almost instantaneous, regardless of how big the numbers are. However, prime number distribution requires a trial and error approach – endless attempts at checking if the number can be divided by something without a remainder.

Even the fastest computers in the world can take months or even years to complete a prime number distribution of especially big numbers.

Cox made use of prime number distribution to formulate his trapdoor equation:

Alvaro generates a prime number P1, which has over 150 digits, and then another equally long prime called P2. Their N product has in excess of 300 digits. Performing the multiplication won’t take a computer long. However, finding all prime numbers of P1 and P2 while all you know is N can take ages.

Cox searched for a function that depends on whether prime number distribution of N is known or not. It was an Austrian mathematician Leonhard Euler that eventually provided a helping hand.

In 1760 Euler published a paper that proved more than useful for Cox. It concerned various properties of numbers, including the distribution of primes. He defined what is today known as the Euler’s totient function (also Euler’s phi function or φ), which determines all relatively prime numbers for any given integer.

For any given N, one can find a φ(N) function, which determines the number of integers smaller or equal to N that do not have any common divisors bigger than 1 with it. These are relatively prime numbers of N. For example, φ(8) = 4, because between 1 and 8 there are four integers that do not have a common divisor other than 1 with 8. The numbers 2, 4 and 6 do not qualify.

Calculating φ is difficult, but, what was important for Cox and what is important for us now, there is an exception. The graph below displays the value of the phi function for all integers between 1 and 1000.It’s easy to notice a pattern. The green line represents the value of φ for prime numbers. Since prime numbers themselves cannot be broken into prime numbers, the value of φ for any P prime is φ(P) = P – 1. The only number we leave out is P itself.

For example, for the prime number 7, the value of φ is 6. It works the same with any other prime number, no matter how big (e.g. 21377).

Now we know that it is easy to determine φ for any given prime. What’s more, φ is also multiplicative, which means that φ(A*B)=φ(A)*φ(B).

Let’s go back to our gigantic 300-digit N number. As long as we know that N is the product of two specific prime numbers P1 and P2, the following operation is true:

φ(N) = φ(P1-1)*φ(P2-1)

We finally found our trapdoor! If we know the prime number distribution of N, we can easily calculate φ(N).

What does the phi function have to do with modular exponentiation? The answer to this question is the subject of Euler’s theorem.

Mφ(N)  ≡ 1 mod N

Let’s pick two random relatively prime numbers M and N. If we exponentiate M to the power of the value of φ(N) and then divide it by N, the remainder will always be 1. For M=5 and N=8:

5φ(8)  ≡ 1 mod 8

54  ≡ 1 mod 8

625  ≡ 1 mod 8

1 mod 8 = 1                    625 mod 8 = 1

Let’s modify this equation with a few simple rules.

• First, when we exponentiate 1 to the power of any given k, the result will always be 1. Similarly, when the exponent of φ(N) is multiplied by any k, the result is also bound to be 1. At the same time, when 1 is multiplied by M, the end result is always M.

That means than we can multiply the left side of the equation by M in order to get M on the right side. In doing so, we have multiplied exponents that have a common base, which allows us to shorten the entire equation.We are almost there! Our equation allows us to calculate e*d, which depends on the value of φ and N. Therefore, it is only easy to calculate d when we know the prime number distribution of N.

Me*d ≡ M mod N

e*d = k*φ(N)+1

d = (k*φ(N)+1)/e

The d number is the private key, which Alvaro can use to decrypt Julia’s messages. It can reverse the effects of the encryption key e.

Let’s use another example to see how it works.

Julia turns her M message into a number using the “filter” approach. Alvaro creates both his private and public key by generating two prime numbers (P1 and P2) of similar value. He multiplies them to get N (3127). Since he knows N’s prime number distribution, he can easily calculate φ(N) (3016).

Then, he chooses a small number to be a public exponent. It has to be an odd number and has no common divider with φ(N). In our case, it is 3. Now, Alvaro calculates the value of a private exponent d, using the formula above (arriving at 2011).

Alvaro proceeds to hide everything, except for the values of N and e. Together, they constitute the public key. This is the open padlock, which everyone can use. He sends it to Julia so that she can enclose her message in it. To do it, she calculates M to the power of e mod N and sends the result (1394) – C – to Alvaro.

Alvaro then deciphers the message using his private key d. The result of C to the power of d mod N corresponds with Julia’s original M message.

Even though Romeo has C, e and N, he won’t be able to arrive at d unless he can calculate φ(N). In order to do that, he must know N’s prime number distribution. If N is big, achieving that could take hundreds of thousands of years (with the trial and error approach).

The system had been kept secret until 1977, when it was discovered independently by Ron Rivest, Adi Shamir and Len Adleman. That’s why we call it today the RSA encryption algorithm. What our explanation basically does is go through basic RSA algorithm steps one by one.

The conclusion from this is that

Most security systems use the RSA algorithm. In fact, the RSA algorithm is the most popular public key algorithm in the world as well as the most often copied piece of software in the history. Every person on the web uses it in one way or another. Its efficiency rests solely on the inherent difficulty of calculating the prime number distribution. Even today this issue remains unresolved.

What do you think about our introduction to cryptography? Did you enjoy it? Or perhaps you have some questions? Leave them in the comment section below and we will try our best to get back to you!