Drunk president and the nuclear launch — Shamir and the duel guy, Galois — III

Part 1 — Drunk president and the Nuclear launch — Shamir Secret Sharing — I

Part 2 — Drunk president and the nuclear launch — Lagrange Decomposition of a function

In school, we were taught Natural numbers, Integers, and Real numbers, everyone was stoked by the concept of infinity and infinite numbers being in between any 2 real numbers, there was just no end to the amazement !! Too many numbers to handle. The last one came after a very long time. C , the Complex Numbers. I could never have imagined something like that. I like it though, it’s so unbiased, it won’t even compare 2 numbers.

Let’s take a step back, and discover a Number system that does not have a whole lot of numbers but are devilishly complex, not like our friend C but in its own ways. Let’s look at the simplest ones.

Finite field or Galois Field

Consider a Set of numbers that has q elements (field’s order). It’s a Finite field iff q is a positive power of a prime number. All the elements need to follow the basic rules of addition, subtraction, multiplication and division called the Field Axioms. The result of all operations must lie within the Finite field, which is it should be present in the set of q elements.

Let’s consider the simplest case for our use: GF(p) read as Galois Field of order p and this contains {0, 1, 2,..., p — 1} . To keep all the results within the set we loop back the numbers, like a ring, say p=5 and you add 3 and 4. In a normal world you would see the answer as 7 but in GF(5), since nothing beyond 4 exists, 3 + 4 = 2, why 2? We looped 7 back so our counting is, if you will, 0, 1, 2, 3, 4, 0, 1, 2, … That is how you would map your real world numbers from Integers to GF(5). This operation of mapping is a result of modulo operation, the 5th fundamental arithmetic operation. It’s very similar to taking remainder.

So, now that we are sufficiently pleased, Let’s try out some basic modulo

This defines a modulo operation.

representing in modulo

I think you get the point

Similarly for multiplication

Just for fun

An interesting outcome of this is operation in GF(p) is

No one understood this guy, He LIKES Galois field !!! (source: Imgflip)

Another gold coming through your way: The proof is left as an exercise for the reader

Just kidding !!

Expand the expression using binomial expansion, and you’ll see the following:

Since all numbers x, y, p are integers, all terms in the expression too should be integers. Let’s analyse one.

You can expand the binomial coefficient and write it as a product of p and the remaining part. There is no term in the denominator that divides p as it’s a prime number and r <= p in this case. We know that whole term is an integer. So the remaining part too should be an integer.

This means that all the terms except the first and the last in the binomial expansion are integral multiples of p and will vanish when evaluated modulo p

Addition, and by extension, subtraction are trivial and so is multiplication. But in case of division, this get’s a little tricky. We are talking about getting remainders for potential floating point number say 2/3 mod 5 which does not make sense as, Finite fields are defined as a subset of positive Integers.

Fret not, let’s analyse the above case as the basic definition of modulo.

Nothing wrong in this right, we can write a in whatever representation as it currently belongs to Real numbers.

Suppose we multiple both sides with the denominator. We get good integers both sides and since we did not change the meaning of the equation, it still holds valid and behaves the same as the first one. Now we can safely restrict the number space to Integers.

2/3 is the remainder of a when divided with p which is equivalent to 2 being the remainder of 3a being divided by p .So if we figure out what is a we would know the value of the modulo of 2/3. All we need to solve is 3a = 2 mod 5

Let’s try by hand. 3a = {3, 6, 9, 12, 15, … } , I think we have our solution, for a = 4, 3a = 12 = 2 mod 5 , So 2/3 mod 5 behaves same as 4 in GF(5)

So, we know how to get a multiplicative inverse. But how feasible is this calculation for larger fields say GF(1000000007), how long would you keep multiplying a check if things coincide.

Fermat’s little theorem

The guys is infamous for writing proofs on margins, but thank god we are not dealing with his last theorem, but the little one. It states that,

When a is raised to the power of a prime p, has a remainder of a when divided by p . There is a simple proof to it which is not necessary here.

Assume that a and p do not have any factor in common, which is gcd(a, p) = 1 , we can safely assume

Since, p and a do not have anything in common, p has to divide a^(p-1)-1

We have already seen that we can divide by a number on both sides of modulo, as they would behave in the same way. So, let’s divide both sides by a in the above equation.

compute multiplicative inverse in GF(p)

So, all we need to do is compute a^(p-2) mod p and that will be the inverse or multiply the above term to simulate division in GF(p).

In our computation of our p(0) to find our secret, we saw that we had some division computations too that caused the results to be in floating point. Let’s rectify that by making computations in a prime field.

Code: Shamir in Finite fields

$ python shamir_finite.py gen
850, 619
996, 130
419, 37
345, 69
950, 860
349, 486
310, 938
$ python shamir_finite.py solve
Usage: Enter space separated values for mentioned
type, X or Y. eg:
X: x1 x2 x3 ...
Y: y1 y2 y3 ...
X: 850 996 419 345 950
Y: 619 130 37 69 860
29

Now, we see that we get a concrete integral answer, which is what we expect. So are we done with this. Yes, we have a working solution in finite fields which is perfectly fine and can be used for studying.

What more do we observe

If we start nitpicking and see in the perspective of implementation, 2 things show up.

1. Any prime will work, but we would prefer a power of 2 because, calculations on Extended Galois Fields (of the type GF(p^k), k > 0)are still feasible and it’s easier for a machine with 2 states to work on powers of 2.
2. The Inverse calculation is done as by raising the number to a huge power and then taking modulo which requires O(log P) steps and each step comprises of 1 multiplication, 1 addition and 2 modulo operations.

def pow_mod(a, n, p):
  # calculates a^n (mod p)
  d, s = a, 1
  while n > 0:
    if n & 1: s = (s * d) % p
    d = (d * d) % p
    n >>= 1
  return s

and be advised, all of these numbers are meant to be huge, like for context, the Wikipedia implementation uses the 12th Mersenne prime which is 2^127–1 = 170141183460469231731687303715884105727 to make the search space huge to make brute force infeasible.

Non-Native multiplications (whose word size is greater than CPU word size, i.e. 64-bit processors) take much more time that simple additions and Fermat’s little theorem only works on prime numbers.

Both the problems can be solved by using Extended Galois fields which aren’t primes anymore and using another method to calculate the multiplicative inverse called Extended Euclidean Algorithm.

This brings us to the apparent end (there is always more to everything). Now we can use this cool scheme to share secret keys and not let the drunk president destroy mankind.

A small closing note — the above implementation still requires use of big integer libraries, it is just reducing the number of multiplications. Another way of doing this is, Generate multiple polynomials, say 16 polynomials, and then calculate a distinct key in GF(2⁸), so you get an 8 bit keys. Now combine all the 8-bit keys from all 16 polynomials and there you have a larger key with the 128-bit strength and same purpose, just that each person will have 16 8-bit keys, which makes no difference and is purely on implementation.