Cryptography Fundamentals. Part 1: Groups, Rings and Discrete Logs

Cryptography Fundamentals. Part 1: Groups, Rings and Discrete Logs

The problem with cryptography is that many miss some fundamental knowledge that will allow them to fully understand the key operations that are used. So, in this series of blogs, I try and explain some of the core concepts that secure our online world. Every single time that you connect to the Internet, the privacy and trustworthiness of your connection are dependent on some magical cryptographic operations.

In our world of numbers, we have N (natural numbers — positive or negative integer values), Z (integers), R (real numbers) and C (complex numbers). for this. Natural numbers can go from minus infinity to plus infinity, while integers constrain these into a ring. A ring might be from 0 to 16, and the 17 goes back to 0, and so on. If we go to -1, that is 16, -2 is 15, and so on.

For cryptography we use the Z double-struck or backboard bold symbol, and where we typically define a group of numbers.

For this, we represent Z_n as the numbers from 0 to n-1. So, Z_7 is {1,2,3,4,5,6}. There is another group we use; the multiplicative group of integers modulo n Z_n*. This excludes the values which are a factor of n.

Z_7 will be {1,2,3,4,5,6}

Z_12* will be {1, 5, 7, 11} [here]

So a group is basically a set of integers, and where we map from one group to another one. If we think about two sets A and B, and then create a mapping between the numbers in A to B, and vice-versa. For encryption, we want a 1-to-1 mapping from every value in A to B, and then for us to be able to reverse back from B to A.

So, if we have a set of numbers of A={1,2,3,4} we might map these to B={2,4,3,1}. If we have a value of 1 in A, it will map to a 2 in B. Then in B, we would map back from 2 to 1. In cryptography, we typically want to make it easy to go from A to B (encrypting) but difficult to go from B to A (decrypting) — unless we know a secret.

In this example, I have used a discrete logarithm mapping with a base generator of g and a prime number:

b=g^a (mod p).

For the mapping of {1,2,3,4} to {2,4,3,1}, I have used g=2, and a prime number of 5.

b = 2¹ (mod 5) = 2 (mod 5) = 2
b = 2² (mod 5) = 4 (mod 5) = 4
b = 2³ (mod 5) = 8 (mod 5) = 3
b = 2⁴ (mod 5) = 16 (mod 5) =1

This will be cyclic, and where {1,2,3,4,5,6,7,8} will map to {2,4,3,1,2,4,3,1}. For this, we have constrained within a finite field of between 0 and 4 (or p-1).

We can see that this gives us a 1-to-1 mapping for each of the elements of our first set to the other set. Every value in B can be reversed back to its original value in A.

To reverse, though, we would need to compute the inverse log of the value in B for mod p — this is not so easy:

a =log_g(b) (mod p)

And this is the core difficulty of the discrete logarithm problem. It is this problem that secures the Internet.

To show you the difficulty of this, if I use a prime number of 2²⁵⁵-19 and a g value of 2. You will find it extremely difficult to find the x value I have used for:

b=25446473684081445734643481619349383496577344937808306324243206897292518839288

If you are interested, the answer is a=431342352456346734652345427573451341234132414341365756845234234234523

In Python, here’s the solution:

>>> a=431342352456346734652345427573451341234132414341365756845234234234523
>>> p=2**255-19
>>> g=2
>>> b=pow(g,a,p)
>>> print (b)
25446473684081445734643481619349383496577344937808306324243206897292518839288

So, watch out for the next podcast…