The Moment I Finally Got Public Key Encryption: The Inverse Mod

The Moment I Finally Got Public Key Encryption: The Inverse Mod

The moment I got public-key encryption was when I understood a finite field, and that it was fairly simple. Even the words of “finite field” sounded grand. And when research papers started talking about a “Galois field”, I lost it a bit more. But it was really simple. The numbers were just groups of numbers, and where one group of numbers mapped to another group, and that these groups were just a collection of the number that were constrained to be finite.

A finite field of 12, is the values of 0, 1 … 11, and a Galois field of 2 (GF(2)) is the values of 0 and 1. In fact, finite fields are actually Galois fields by another name! And so a symbol of 𝔽𝑞 was just the values from 0 to q, and GF(q) was also the values of 0 to q.

Let’s say I have a finite field of 5, and so we have A={0,1,2,3,4}, and then multiply them all by 3, and take (mod 5), we get B={0,3,1,4,2}. We have one group (A) and then multiply each by 3 and take (mod 5) to get B. Every value from A now maps to a single value in B. By looking at any of the values in B you might not be able to map them back unless you knew the multiplier and reverse the operation. In public-key encryption, we must find a method that makes it easy to reverse back if we know a secret, but difficult if we do not.

I had stared at all those complex squiggles on research papers, and I finally realised that it was all quite simple … we were actually just making sure that our numbers did not get too large, and that we could still use our normal arithmetic operators (add, subtract, multiply and divide). We could even use logs, and it all worked out.

The magic of all of this was the (mod) operation of a prime!!!!!

The magic of (mod p)

So, I take a prime number, say 97, and then all my operations are done (mod 97). Thus I have a finite field, and where all my values are between 0 and 96, as the mod operation returns the remainder of an integer division.

And so I can add, subtract and multiply using the mod operation and it all comes out the same:

>> a=5
>> b=10
>> (a+b)%p
4
>>> ((a%p) + (b%p)) %p
4
>>> ((a%p) * (b%p)) %p
6
>>> (a*b)%p
6

Thus, no matter where I add the (mod p) operation, it always allows me to get the same result, including when I use a power of:

>> a=5
>> b=10
>>> (a**b)%p
1
>>> ((a%p) ** (b%p)) %p
1

But, divide was different! And, so, if I had an operation of ab (mod p), how could I divide by a, and get the value of b? Well, the answer is inverse mod, and which can be implemented with Fermat [here] or the Euclidean algorithm [here].

Basically, to find the inverse of a (mod p), we need to find the value of x, given a, that makes this true:

(x)a (mod p) = 1

It is like saying “a” divided by “a” is equal to 1.

So let’s take an example. If we have a of 64 and p of 97:

a^{-1}=64^{−1} (mod 97)=47 [here]

Now we try to multiply a and the inverse of a together (all done mod p):

64×47 (mod 97)=1

and you see that 47 is the inverse of 64 (mod 97).

Our secret code

So we can now use this to create a simple public key method. Well let’s say I have a secret of 100, and I want to send you a message of 106. We then select a prime number of 997. Now I will multiply the message with my secret and take a mod p to get:

>>> s=100
>>> m=106
>>> p=997
>>> (s*m)%p
630

We have a cipher value of 630. Now it is not possible to determine the message unless you know the secret (s). To decode, we find the inverse of s (mod 997), such as:

Inverse 100 (mod 997) = 668 [here]

Now, we take this inverse mod and multiply it with the cipher:

>>> (630*668)%997
106

and we have recovered our message. This is basically doing:

(s * m) / s (mod p) = m (mod p)

And so, if you are into Python, here’s some code which implements this:

And if you are into Go, here some code:

The demo is here:

And so we have a trap door function, and where, if we know a secret we break into the method. Whitfield Diffie proposed that it would be possible to have two values — one to create the trap door function (the public key) and one to release it (the private key). The first one to be found was RSA, and where we have an encryption public key (e) and a decryption key (d), along with a modulus made up of two prime numbers (p and q). Overall, we create N from the multiplication of the two prime numbers, and then with a message of M we create the cipher of:

Cipher = M^e (mod N)

and then decrypt with:

Decipher = Cipher ^ d (mod N)

Conclusions

And that was it! I understood a whole lot more about the basics of public key, and it wasn’t actually that difficult. Often simplifying things, and coming up with your own examples is a great way to learn. For this Python and Go are your friends.

Puzzle … I have a secret value of 51, and have a cipher of 88 and a prime of 997. What is my secret message value?