### Homomorphic encryption using RSA

I recently had cause to briefly look into Homomorphic Encryption, the process of carrying out computations on encrypted data. This technique allows for privacy preserving computation. Fully homomorphic encryption (FHE) allows both addition and multiplication, but is (currently) impractically slow.

Partially homomorphic encryption just has to meet one of these criteria and can be much more efficient.
An unintended, but well-known, malleability in the common RSA algorithm means that the multiplication of ciphertexts is equal to the multiplication of the original messages. So unpadded RSA is a partially homomorphic encryption system.

RSA is beautiful in how simple it is. See wikipedia to see how to generate the public (e$e$, m$m$) and private keys (d$d$, m$m$).

Given a message x$x$ it is encrypted with the public keys it to get the ciphertext C(x)${C}(x)$with:

C(x)=xemodm

To decrypt a ciphertext C(x)${C}(x)$ one applies the private key:

m=C(x)dmodm

The homomorphic property is that multiplication is preserved.

C(x1)Ã¢‹…C(x2)=(xe1modm)Ã¢‹…(xe2modm)

Due to the Distributive nature of the modulus operator this is rearranged to:

xe1xe2modm=(x1x2)emodm=E(x1Ã¢‹…x2)

# An example in python

Say these values in hexadecimal format are my public/private keys:
m = 0x1d7777c38863aec21ba2d91ee0faf51
e = 0x5abb
d = 0x1146bd07f0b74c086df00b37c602a0b


I will choose two numbers (273, 101) which I want an untrusted third party to multiply together. First I need to encrypt the two plaintext messages:

Encryption is one call to Python's builtin pow() function, giving a little known third parameter for the modulus:

>>> c_243 = pow(243, e, m)
>>> c_101 = pow(101, e, m)

>>> hex(c_243)
'0x15c713c3db45595b17a5598471c36db'
>>> hex(c_101)
'0x12314f0fe732e421017cf710dd1834c'


We can check that the decryption works as well:

>>> pow(c_101, d, m)
101


At this point we can now ask our untrusted party to carry out the multiplication on the ciphertext:

>>> cipher_multiply = 0x15c713c3db45595b17a5598471c36db * \
0x12314f0fe732e421017cf710dd1834c
>>> cipher_multiply
2734418524132665852913864980612094018180511394708197352750873115983960580
>>> hex(cipher_multiply)
'0x18c3138575668d2753d4acf635bb4d09b4a67df66ac9eb8891e15743d5a04'


Now we can decrypt this new ciphertext that has been created by multiplying two ciphertexts together.

>>> pow(cipher_multiply, d, m)
24543


Which luckily is equal to our two messages multiplied together (101 * 243).

This field of study will be an interesting one to watch over the next few years as several researchers are working on Fully Homomorphic Encryption. A C++ library called HElib comprises computing primitives for fully homomorphic encryption - assembly language for HE. A good introductory tutorial can be found on tommd.github.io

### Driveby contribution to Python Cryptography

While at PyConAU 2016 I attended the Monday sprints and spent some time looking at a proposed feature I hoped would soon be part of cryptography. As most readers of this blog will know, cryptography is a very respected project within the Python ecosystem and it was an interesting experience to see how such a prominent open source project handles contributions and reviews.

The feature in question is the Diffie-Hellman Key Exchange algorithm used in many cryptography applications. Diffie-Helman Key Exchange is a way of generating a shared secret between two parties where the secret can't be determined by an eavesdropper observing the communication. DHE is extremely common - it is one of the primary methods used to provide "perfect forward secrecy" every time you initiate a TLS connection to an HTTPS website. Mathematically it is extremely elegant and the inventors were the recipients of the 2015 Turing award.