5

So What Have Prime Numbers and Galois Fields To Do With Your Privacy?

 3 years ago
source link: https://medium.com/asecuritysite-when-bob-met-alice/so-what-have-prime-numbers-and-galois-fields-to-do-with-your-privacy-2dff9881361e
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Image for post
Image for post

So What Have Prime Numbers and Galois Fields To Do With Your Privacy?

Remember at school they told you that 17 divided by 5 doesn’t go? Then they told you that there’s a remainder from the division, and that the answer is 3 remainder 2.

In this operation, we might be only interested that the result of the division is 3 (an integer division), and that there’s a remainder of 2. In cryptography, though, we would throw away the 3, and concentrate on the 2. For this we define the operation as a modulus (or mod). And so 17 (mod 5) is 2. If you are into Python, this is 17 % 5.

In cryptography, we are basically not interested in all those negative numbers, and those decimal point values, as we only deal with positive integers (Z).

And something magical happens when we use prime numbers for our mod operations, and where we can constrain the numbers that we use, but still our math operations still work. This is called Finite Fields (Zp), and they protect your privacy like nothing else.

Prime numbers and you

Prime numbers are protecting your identity virtually every time that you connect to a Web site. With symmetric key methods, such as AES and 3DES, we often use a scrambling function with the key added, and where we take blocks of input data and then swap rows and columns. This is then fed into a scrambler — an S-box — and we do this over a number of rounds. On the other side, we just do the reverse. This provides us with a fast way to scramble and unscramble, but will only reveal the correct output if we have the same key. If you are interested in how this works, click here. Symmetric key methods are thus good at protecting the privacy of a message.

But how do we create the key? And how do we prove our identity?

Well, this is where public key — or asymmetric encryption — comes in, and where we generate a public key and a private key, and they work together, where one can encrypt and the other is then used to decrypt. In this way, we can sign something — encrypt it — with our private key and then show everyone our public key. To prove our identity, a recipient of a signature just decrypts our signed content, and if it makes sense, we must know the private key.

The methods we use in public key encryption often make use of prime numbers, either in creating the keys or to limit the sizes of the numbers involves. And so meet the wonderful world of prime numbers …

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 — 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)

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.


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK