In modern Cryptography, Modular Arithmetic plays a very important role. Everytime you order something over the internet, your data gets encrypted with RSA, an encrypting method which is based on the properties of prime numbers and Modular Arithmetic. An easier example to explain is the solution to the very old problem of distributing keys.

If you want to send an encrypted message to someone, that person has to have some kind of key to be able to read it. Of course you could personally hand over the key to the other person, but that is not always possible. For example banks who comunicate with many people about personal things, can not go and distribute thousands of keys themselves. They could and did have employees who traveled from client to client to distribute the keys, but it's hard to get so many reliable people, and it also gets very expensive.

In 1976, Martin Hellman and his colleagues Whitfield Diffie and Ralph Merkle found out a way to distribute the key by telephone. With their system, they could use a perfectly normal telephone line and anyone could listen to each word said, but only the two people talking knew the key afterwards. This is how their system works:

First we look at the statement

 

When we fill in some numbers, we quickly see that this statemen is true. For example when we fill in x=2, a=2 and b=3 we get: (2²)³=4³=64=8²=(2³)²

Hellman and his colleges used this principle for the key distributing problem. First of all person A and person B agree on a base that they will work with (x). Then both of them choose a secret number, the numbers a and b. Each one calculates x with the exponent of his number. So person A will get x^a and person B will get x^b. They trade their results and take the other's result with the exponent of their own number. So person A will have (x^b)^a and person B will have (x^a)^b. As we saw before, they both have the same result even though A has no idea what number B chose and vice versa.

If A and B did it the above way, it would be pretty easy for a person listening to their conversations to find out the number they got in the end. This is where Modular Arithmetic comes in to save the day.

Instead of only agreeing on a base in the beginnig, A and B also agree on a modulus they are going to use during their calculations. And instead of basing their calculations on the statement above, they take a similar statement which looks a bit more complicated:

 

So now A calculates x^a mod y and B calculates x^b mod y. They exchange their results and A calculates (x^b mod y)^a mod y and B calculates (x^a mod y)^b mod y. Again they get the same result. But this time it doesn't matter if someone sneeky listened to every word A and B said. Let's take a look at what information such a person could get and what he could do with it:

Let's say A and B agreed on the base 6 and on the modulus 11 in the beginning. This they told each other over the telephone which we are tapping. Now they both made their calculations and they tell each other their results. We hear that A got 5 and B got 1. So now we know that A made the calculation 6^a mod 11 = 5 and B made the calculation 6^b mod 11 = 1. How can we find out the value for either a or b? This is harder then it may sound. In fact the only way to find out one of these numbers, is to try out every possible number until we find one that fits the equation. Even though it is easy with such small numbers as A and B used in this example, it becomes practically impossible, when big enough numbers are used. There are just too many possibilities for any computer to calculate.

Functions like modulus y are called one-way functions because even though it is easy for A to calculate 48²³⁴ mod 50 = 34 (with a calculator at least), it is very hard, however, for anyone to find out the value for a in 48^a mod 50 = 34. For a two-way function, on the other hand, there is an inverse operation. Addition, for example, would be the inversion of subtraction, and taking the square root would be the invertion of squaring. If A makes the calculation 5²=25, anyone can find out that in a²=25 a has to be 5 since √25=5.

Previous