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