So What’s A Finite Field and Why Is It So Important to your Privacy?
So What’s A Finite Field and Why Is It So Important to your Privacy?
The demonstration of the methods defined in this article are here.
Sometimes when you read research papers your head can spin a little, but you should try and stick with it, as the learning of new knowledge often involves breaking down the barriers to that knowledge.
For one you may not have the background that prepares you for the subject, but, with the Internet, there are very few barriers to learning new subjects. All you need is an enquiring mind, and to not take “No” for an answer. At one time knowledge was passed through privileged sources … through physical libraries and seats of learning … but now it is freely available.
The second thing is the terminology that is used, and which can be an even create a barrier. So let’s break down a few barriers by talking about finite fields.
A finite field and a Galois field
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 where 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]
- 𝔽11or 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 we take a prime number and then limit the possible values between zero and that number. When we perform our mathematical operations we then constrain the outputs to these values. Now let’s look at a prime number of 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 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 15 times. This gives us 8. Now for the multiply operation, we have 5𝗑20 which is 100. If we take 100 (mod 23) we get 8. 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 then multiply this value by a. Luckily we have Python to hand to calculate this for us (using the Extended Euclidean algorithm). In this 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 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 ˣ try 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 — here is safe values for G). 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)
I am going to 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!
If you are into Python (and I love it), here is some simple code:
a=10
b=13
p=23
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
print "a = ",a
print "b = ",b
print "p = ",p
print "Finite of integers GF(p): ",
for x in range(p):
print x,
print "a + b mod p=",(a+b) % p
print "a - b mod p=",(a-b) % p
print "a * b mod p=",(a*b) % p
inv_b = inverse_of(b,p)
print "Inverse of b mod p is ",inv_b
print "a / b mod p=",(a*inv_b) % p
Here is a presentation on the methods:
Conclusions
Go learn about the beauty of cryptography. When politicians say that the laws of mathematics are over-ruled by the law of a land, you can see that there’s maybe a debate to be had:
The demonstration of the methods defined in this article are here.