Multiplication with Homomorphic Encryption using RSA

[Back] RSA is a partially homomorphonic encryption method, and where we can add and multiply encrypted values. In this case we will use RSA to encrypt two integers and then multiply the ciphered values and then decrypt to find the result of the multiplication:

Theory

Too much of our data world gives away sensitive information, and we thus need to move to a world where we can process data without revealing its actual information. In this way we can process data within systems and even though someone is looking at the data processing, they cannot determine the actual values being used. This is the dream of homomorphic encryption.

Some of the proposed schemes are defined as partially homomorphic — where they can support a number of mathematical operations on encrypted values — and others as fully homomorphic. In this case, I’ll use a simple RSA method to multiply two ciphered values, and gain the result of a multiplication when we decipher them.

So with RSA we cipher with:

\(Cipher = M^e \pmod N\)

and where \(e\) 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:

\(M = Cipher^d \pmod N\)

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

\(Cipher_1 = a^e \pmod N\)

\(Cipher_2 = b^e \pmod N\)

If we multiply the ciphers we get:

\(Cipher_3 = Cipher_1 \times Cipher_2 = a^e \pmod N \times b^e \pmod N = a^e \times b^e \pmod N\)

This is then:

\(Cipher_3= (ab)^e \pmod N\)

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

\(ab= (Cipher_3)^d \pmod N\)

Now let's make a bet for Alice, and make sure that the bookie (Bob) doesn't actually know how much she has bet, and how much she has won.

Here is some simple code:

print "RSA Encryption parameters. Public key: [e,N]."
cipher1=pow(a,e,n)
cipher2=pow(b,e,n)
cipher3=(cipher1 * cipher2) % n
print "a:\t\t",a
print "b:\t\t",b
print "Cipher1:\t",cipher1
print "Cipher2:\t",cipher2
print "Cipher3:\t",cipher3
print "e:\t\t",e
print "N:\t\t",n
val=pow(cipher3,d,n)
print "Result:\t\t",val

Now with a stake of £11 and with odds of 4/1 we get:

a:              11
b:              5
Cipher1:        587594386702964443000198582993090352
Cipher2:        190679432787271388486300698180475703
Cipher3:        313370008825595405710726217490873530
e:              65537
N:              594816299572474213456473242614358287
Result:         55

The following code implements the basic method (using small prime numbers):

# https://asecuritysite.com/encryption/hom_rsa
import sys
import libnum
import Crypto.Util.number


val=0
bits=60

if (len(sys.argv)>1):
	val=int(sys.argv[1])


p=Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
q=Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)

n=p * q

print (p,q,n)
e=65537

PHI=(p-1)*(q-1)

d=libnum.invmod(e,PHI)

a = 11
b = 5

print ("RSA Encryption parameters. Public key: [e,N].")
cipher1=pow(a,e,n)
cipher2=pow(b,e,n)

cipher3=(cipher1 * cipher2) % n

print ("a:\t\t",a)
print ("b:\t\t",b)

print ("Cipher1:\t",cipher1)
print ("Cipher2:\t",cipher2)
print ("Cipher3:\t",cipher3)

print ("e:\t\t",e)
print ("N:\t\t",n)

val=pow(cipher3,d,n)

print ("Result:\t\t",val)

A sample run:

a:              11
b:              5
Cipher1:        587594386702964443000198582993090352
Cipher2:        190679432787271388486300698180475703
Cipher3:        313370008825595405710726217490873530
e:              65537
N:              594816299572474213456473242614358287
Result:         55

Multiplication with Homomorphic Encryption using RSA

Parameters

Theory