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 libnum 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 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 = libnum.invmod(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