Encrypted Computation using Public Key Encryption — Toy Example

This post builds on Computing on Encrypted Data — What, Why, Toy Example, which explains the idea of computing on encrypted data, why it is useful, and gives a simple toy example of this.

Computing on Encrypted Data (AKA Homomorphic Encryption) typically is done using a form of encryption called Public Key Encryption. Public Key Encryption is what is used to encrypt e.g. many messages on the internet.

PKE allows someone (e.g. a Whatsapp user) to publish some numbers on the internet — called Public Keys — anyone can then use these Public Keys to encrypt a message to this user, and send it to them encrypted.

The public keys are tied to private keys, which the Whatsapp user holds — but does not publish. The private keys can be used to decrypt any message that was encrypted using the public keys.

In this post we are going to develop a toy example of Public Key Encryption — including an encrypted computation, using the original PKE algorithm called RSA, which was discovered in 1978.

The concepts may remind you of the public addresses of Bitcoin and other cryptocurrencies (which can receive money, but the private key is needed to send it). This is because this part of the Blockchain protocol uses the same form of cryptography.

As mentioned above, the system requires a Public Key to be published, so that senders of messages can use it to encrypt those messages. We’re going to use this Public Key:

e =  3
n = 15        

These are the public keys, which anyone can use to encrypt a message that they wish to send to us (without anyone that intercepts the message being able to read it). Note that these are toy numbers, that do not provide actual enrcryption, they are meant to conveny the intuition of how the algorithm works.

In addition to the Public Keys, there are the Private Keys, as the name suggests, we keep those private, we do not publish them. For our Private Key we will use:

d = 11
n = 15        

Now we have Bob. Bob wishes to send us a number, but without anyone that intercepts our communication being able to read it.

The number that Bob has is:

a = 7        

He now performs :

a^e = 7^3 = 7*7*7 = 343        

In other words, he takes his message (7) an the first part of the Public Key (e=3), and he calculates the 7x7x7 (for a total of 3 sevens, since e=3).

Now we’re going to take the outcome: 343, and extract the number 15 out of there as many times as we can, and see what we are left with.

In this case we can take 22 groups of 15 (for a total of 330) out of 343, and are left with 343–330=13. This is the encrypted version of our number a (which was 7).

343 - (22*15) = 343 - 330 = 13        

You can simply use a search engine to calculate this:

This operation is called the modulo (mod), if you want to look at it more closely see the blog post Understanding Modulo using Days of the Week.

Bob can now publicly transmit the numbers 13 to us, since it is "encrypted", nobody that reads the number 13 will be able to find out that the unecrypted message is 7 (our unencrypted number).

When we receive the "encrypted" value 13 we use the Private Key for decryption, which was:

d = 11
n = 15        

Now we take the number 13 that we receive from Bob and we calculate:

m^d modulo n = 13^11 modulo 15        

Again, you can simply type this into a search engine:

So we now, using our decryption obtained the original (pre-encryption) value of a, which was 7!

Encrypted Computation using PKE

At the beginning we said that we’d compute on the encrypted values, so let’s now do that. Just remember that this is a toy example, don’t use this for actual encryption. You follow along in this spreadsheet.

We start with a these two numbers:

a = 3
b = 4        

For this example we will use the following public key:

e =  5
n = 14        

And this will be the private key:

d =  5
n = 14        

We now “encrypt” our two messages (the numbers we wish to send):

3^5 mod (14*14) = 47
4^5 mod (14*14) = 44        

Now we multiply the two “encrypted” values:

(44*47)^5 mod (14*14) = 108        

Finally, we decrypt our “encrypted” result:

108^d mod (n*n) = 108^5 mod (14*14) = 12        

The outcome is 12, which indeed to correct result, as had multiplied the value 3 and 4 (while “encrypted”) and 3x4=12.

Annex: Deriving the Public and Private Keys

In this annex we derive the public and private keys used in the first example.

We start with two prime numbers (simply a number can only be divided by itself, like 2,3, but not 4, which can be divided by 2):

p = 3
q = 5        

Next we compute the product, which we call n, so p times q becomes n:

n = p * q
n = 3 * 5
n = 15        

So n=15.

Now we again compute the product of p times q, but first we substract 1 from p and q. We’re going to call this z:

z = (p-1) * (q-1)
z = (3-1) * (5-1)
z =  2    *  4
z =  8        

So z=8.

Next we have to find a number d that cannot divide our new number z (which is 8) into a whole number.

We set d=3, since 8/3 = 2.67, which is not a whole number, so 3 is a valid value for d.

Finally, for the number e, we need it to fulfill the requirement:

e*d mod z = 1        

For our d and z, this requirement is met if we set e=11.

Final note: the “encrypted” computation uses two modifications, because we are dealing with small numbers (that should never be used for real-world encryption): The values d and e are actually the same, that should not be the case in real life. Modulo is performed using n*n, instead of n.

The next post develops a Fully Homomorphic Encryption schema known as BGV: Fully Homomorphic Encryption and Computation in Python or R.