Your On-line Security Is Probably More Dependent on Prime Numbers Than Your Virus Scanner

Your On-line Security Is Probably More Dependent on Prime Numbers Than Your Virus Scanner

You should hopefully know that our core security on the Internet is the usage of symmetric key encryption — AES, ChaCha20 and RC4. These are at the core of our protection, and protect data both at rest and in transit. But this is only part of the story, as this type of encryption doesn’t not really prove anything — it protects, but does not really identify. But this is where public key encryption comes in, and where we have a public key and a private key — a key pair.

If we want to prove our identity, we encrypt something with our private key, and then others can prove this identity with our public key. Normally, too, a trusted entity — Trent — provides proof of our public key. It is thus mechanism that makes our work more trustworthy, and where we can prove our identity, and check the identity of others.

With public key, we can: encrypt data (but not a great deal of it, as it is much slower than AES): provide proof-of-identity; and pass secret keys. For key exchange, Bob can generate a secret key, and then encrypt this with Alice’s public key. Alice then decrypts the secret key with her private, and they will both have the same secret key:

But what makes this magic work? Well, in public key encryption we normally create extremely difficult calculations for those who do not know the private key, but easy if they do. We normally use exponent encryption for this and were we raise a value to the power of another value. As these numbers can be extremely large we must constrain our numbers in some way, and this is done by taking performing:

(mod p)

and where we take the remainder of a divide operation. But how does that help? Well, by the magic of finite fields …

Finite fields

A finite field is just a set with a finite number of elements. In cryptography, we often time a finite field of integers modulo p (where modulo is the remainder of an integer division) and p is a prime number. This is defined as GF(p) — Galois field of p or with 𝔽p. The following are some examples:

• 𝔽2 or GF(2) is [0,1]
• 𝔽11 or GF(11) is [0,1,2,3,4,5,6,7,8,9,10]
• 𝔽23 or GF(23) is [0,1,2,3,4,5,6,7,8,9,10,11,12…22]

In this way we take a prime number (p) and then limit the possible values between zero and that number minus one (p-1). When we perform our mathematical operations we then constrain the outputs to these values. Now let’s look at a prime number of 23, and two values of 5 and 20:

a =  5
b =  20
p =  23
Finite of integers GF(p):  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
a + b mod p= 2
a - b mod p= 8
a * b mod p= 8
Inverse of b mod p is  15
a / b mod p= 6

In this case a+b will equal 25, and then if we take 25 (mod 23) we get 2. For the subtraction, we roll-round so that 5–20 is -15, and so we count back from 23, 15 times. This gives us 8. Now for the multiply operation, we have 5x20 which is 100. If we take 100 (mod 23) we get 8. Finally the division is a bit more difficult and we need to perform a special operation. For:

a / b mod p= 6

we must find the inverse of b and then multiply this value by a. Luckily we have Python to hand to calculate this for us (using the Extended Euclidean algorithm). In this case we determine the inverse of a value mod p, and where p is a prime number:

def extended_euclidean_algorithm(a, b):"""
    Returns a three-tuple (gcd, x, y) such that
    a * x + b * y == gcd, where gcd is the greatest
    common divisor of a and b.

This function implements the extended Euclidean
    algorithm and runs in O(log b) in the worst case.
    """
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = b, a

while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t

return old_r, old_s, old_t

def inverse_of(n, p):"""
    Returns the multiplicative inverse of
    n modulo p.

This function returns an integer m such that
    (n * m) % p == 1.
    """
    gcd, x, y = extended_euclidean_algorithm(n, p)
    assert (n * x + p * y) % p == gcd

if gcd != 1:
        # Either n is 0, or p is not a prime number.raise ValueError('{} has no multiplicative inverse ''modulo {}'.format(n, p))else:return x % p

So if we try the inverse of 20 mod (23), we get 15. Next we multiple a (5) by the inverse of b mod 23 (15) and we get 75. If we now take 75 (23) we get 6. You can try your own here.

So how does this protect your privacy?

Well, in cryptography, many things that we do constrain the values to prime numbers. When you negotiate your secret key for your VPN, there’s a good chance that there’s a key handshaking going on. For this, we both decide on the prime number we are going to use (p) and then decide on another shared value (g — the generator). Next, you take a random number (x) and calculate:

Val1=gˣ (mod p)

and where we have GF(p) or 𝔽p. Let say you have select x = 10, and p is 17 and g is 3. The calculation will then be:

Val1=3¹⁰(mod 17)

We can then use Python to calculate this:

>>> print 3**10 % 17
8

Now the person on the other side decides on a random value of 15. They will calculate:

Val2=3¹⁵(mod 17)

and, again, I will use Python to calculate this:

>>> print 3**15 % 17
6

Now we exchange these values, and Eve will have a difficult time finding the random values that we have chosen. We now take the value received (9) and perform the same calculation:

Key=3⁹(mod 17)

>>> print 6**10 % 17
15

The other side does the same with your value (4), and the value generated show by the same:

>>> print 8**15 % 17
15

And then the two sides have the same shared value. Magical!

A great advantage of using finite fields of prime numbers is that we can operate on values with mod operators and perform arithmetic operations. For example:

a×b(mod p)

is the same as:

a(mod p)×b(mod p) (mod p)

and it works with other operators too, such as with an adding operation:

a+b (mod p)

is the same as:

a(mod p)+b(mod p) (mod p)

and with subtraction:

a−b (mod p)

is the same as:

a(mod p)−b(mod p) (mod p)

For the value raised to the power we have:

(aˣ)ʸ (mod p)

is equivalent to:

(aˣ (mod p))ʸ (mod p)

A sample run illustrates this:

a =  10
b =  20
p =  23
a * b (mod p)=                      16
(a (mod p) x b (mod p)) (mod p)=    16
a + b (mod p)=                      7
(a (mod p) + b (mod p)) (mod p)=    7
a - b (mod p)=                      13
(a (mod p) - b (mod p)) (mod p)=    13

Go try your own here.

So, for key exchange and in proving your identity, prime numbers are at the core of privacy on the Internet.

Conclusions

The day I understood how finite fields worked, and how important prime numbers were, was the day that changed my viewpoint on the world. Prime numbers will build a more trusted world!