Multiplication with Homomorphic Encryption using RSA

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):

import pyprimes
import sys

import random
import math

def extended_euclidean_algorithm(a, b):
    """
    Returns a three-tuple (gcd, x, y) such that
    a * x + b * y == gcd, where gcd is the greatest
    common divisor of a and b.

    This function implements the extended Euclidean
    algorithm and runs in O(log b) in the worst case.
    """
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = b, a

    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t

    return old_r, old_s, old_t


def inverse_of(n, p):
    """
    Returns the multiplicative inverse of
    n modulo p.

    This function returns an integer m such that
    (n * m) % p == 1.
    """
    gcd, x, y = extended_euclidean_algorithm(n, p)
    assert (n * x + p * y) % p == gcd

    if gcd != 1:
        # Either n is 0, or p is not a prime number.
        raise ValueError(
            '{} has no multiplicative inverse '
            'modulo {}'.format(n, p))
    else:
        return x % p
def rabinMiller(n):
     s = n-1
     t = 0
     while s&1 == 0:
         s = s/2
         t +=1
     k = 0
     while k<128:
         a = random.randrange(2,n-1)
         #a^s is computationally infeasible.  we need a more intelligent approach
         #v = (a**s)%n
         #python's core math module can do modular exponentiation
         v = pow(a,s,n) #where values are (num,exp,mod)
         if v != 1:
             i=0
             while v != (n-1):
                 if i == t-1:
                     return False
                 else:
                     i = i+1
                     v = (v**2)%n
         k+=2
     return True

def isPrime(n):
     #lowPrimes is all primes (sans 2, which is covered by the bitwise and operator)
     #under 1000. taking n modulo each lowPrime allows us to remove a huge chunk
     #of composite numbers from our potential pool without resorting to Rabin-Miller
     lowPrimes =   [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
                   ,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179
                   ,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269
                   ,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367
                   ,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461
                   ,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571
                   ,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661
                   ,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773
                   ,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883
                   ,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997]
     if (n >= 3):
         if (n&1 != 0):
             for p in lowPrimes:
                 if (n == p):
                    return True
                 if (n % p == 0):
                     return False
             return rabinMiller(n)
     return False

def generateLargePrime(k):
     #k is the desired bit length
     r=100*(math.log(k,2)+1) #number of attempts max
     r_ = r
     while r>0:
        #randrange is mersenne twister and is completely deterministic
        #unusable for serious crypto purposes
         n = random.randrange(2**(k-1),2**(k))
         r-=1
         if isPrime(n) == True:
             return n
     return "Failure after "+`r_` + " tries."


import random



val=0
bits=60

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



p= generateLargePrime(bits)
q= generateLargePrime(bits)


n=p*q

e=65537

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

d=inverse_of(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