[Back] The Paillier cryptosystem supports homomorphic encryption, where two encrypted values can be added together, and the decryption of the result gives the addition:
Paillier cryptosystem |
Theory
The following is a screen shot from Wikipedia on the method:
In this case we start with two prime numbers (p and q), and then compute n. Next we get the Lowest Common Multiplier for (p-1) and (q-1), and then we get a random number g:
def gcd(a,b):
while b > 0:
a, b = b, a % b
return a
def lcm(a, b):
return a * b / gcd(a, b)
n = p*q
gLambda = lcm(p-1,q-1)
g = randint(0,100)
The next two steps involve calculating the value of the L function, and then gMu, which is the inverse of l mod n (I will show the inverse function later in the article):
l = (pow(g, gLambda, n*n)-1)//n gMu = inverse_of(l, n)
The public key is then (n,g) and the private key is (gLamda,gMu).
cipher is then computed from the message (the function pow(a,b,n) raises a to the power of b, and then takes a mod of n):
k1 = pow(g, m, n*n) k2 = pow(r, n, n*n) cipher = (k1 * k2) % (n*n)
And is decrypted with:
l = (pow(cipher, gLambda, n*n)-1) // n
mess= (l * gMu) % n
A sample run with p=17, q=19, and m=10 is:
p= 17 q= 19
g= 45 r= 59
================
Mu: 66 gLambda: 144
================
Public key (n,g): 323 45
Private key (lambda,mu): 144 66
================
Message: 10
Cipher: 336
Decrypted: 10
With Pallier we should be able to take values and then encrypt with the public key and then add them together:
m1=2 k3 = pow(g, m1, n*n) cipher2 = (k3 * k2) % (n*n) ciphertotal = (cipher* cipher2) % (n*n) l = (pow(ciphertotal, gLambda, n*n)-1) // n mess2= (l * gMu) % n print "Result:\t\t",mess2
and when we run we get:
p= 17 q= 19
g= 86 r= 91
================
Mu: 40 gLambda: 144
================
Public key (n,g): 323 86
Private key (lambda,mu): 144 40
================
Message: 10
Cipher: 95297
Decrypted: 10
================
Now we will add a ciphered value of 2 to the encrypted value
Result: 12
and so it has computed the right value.
Coding
Here is the Python coding:
from random import randint
import sys
def gcd(a,b):
"""Compute the greatest common divisor of a and b"""
while b > 0:
a, b = b, a % b
return a
def lcm(a, b):
"""Compute the lowest common multiple of a and b"""
return a * b / gcd(a, b)
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 L(x,n):
return ((x-1)//n)
p=17
q=19
m=10
if (len(sys.argv)>1):
m=int(sys.argv[1])
if (len(sys.argv)>2):
p=int(sys.argv[2])
if (len(sys.argv)>3):
q=int(sys.argv[3])
if (p==q):
print "P and Q cannot be the same"
sys.exit()
n = p*q
gLambda = lcm(p-1,q-1)
g = randint(20,150)
if (gcd(g,n*n)==1):
print "g is relatively prime to n*n"
else:
print "WARNING: g is NOT relatively prime to n*n. Will not work!!!"
r = randint(20,150)
l = (pow(g, gLambda, n*n)-1)//n
gMu = inverse_of(l, n)
k1 = pow(g, m, n*n)
k2 = pow(r, n, n*n)
cipher = (k1 * k2) % (n*n)
l = (pow(cipher, gLambda, n*n)-1) // n
mess= (l * gMu) % n
print "p=",p,"\tq=",q
print "g=",g,"\tr=",r
print "================"
print "Mu:\t\t",gMu,"\tgLambda:\t",gLambda
print "================"
print "Public key (n,g):\t\t",n,g
print "Private key (lambda,mu):\t",gLambda,gMu
print "================"
print "Message:\t",mess
print "Cipher:\t\t",cipher
print "Decrypted:\t",mess
print "================"
print "Now we will add a ciphered value of 2 to the encrypted value"
m1=2
k3 = pow(g, m1, n*n)
cipher2 = (k3 * k2) % (n*n)
ciphertotal = (cipher* cipher2) % (n*n)
l = (pow(ciphertotal, gLambda, n*n)-1) // n
mess2= (l * gMu) % n
print "Result:\t\t",mess2
We need to make sure that g only uses \(Z^*_{n^2}\). For p=41 and q=43, we get n=1763 [\(n^2=3108169\)]. The valid \(g\) values are thus [here]:
Value is: 3108169 Multiplicative group for Zn up to 100 is: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 42 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 83 84 85 87 88 89 90 91 92 93 94 95 96 97 98 99 100 The number of values is: 96