Homomorphic Multiplication and Division with RSA

Ssh! RSA implements partial homomorphic encryption. With homomorphic encryption, we generate a key pair (a public key and a private key). We can encrypt data with the public key, and then operate on it in a homomorphic way, such as add, subtract, multiply and divide. The result of this can then be decrypted with the private key.

Homomorphic multiplication

So with RSA we cipher with:

is the encryption key, and N is the multiplication of two prime numbers (p and q). The difficuly in this is factorizing N to get two prime numbers. To decrypt, we find the decryption key (d) and then perform:

So if we take two values (a and b), then we can cipher them as:

If we multiply the ciphers we get:

This is then:

When we can then decrypt and determine the value of a times b.

Here is the code to implement this for randomly generated prime numbers [here]:

import sys
import libnum
from Crypto.Util.number import long_to_bytes,bytes_to_long
from Crypto import Random
import Crypto

bits=128

val1=99
val2=3

if (len(sys.argv)>1):
	val1=int(sys.argv[1])
if (len(sys.argv)>2):
	val2=int(sys.argv[2])
if (len(sys.argv)>3):
	bits=int(sys.argv[3])

p =…