[ Log On ]
  • Home
  • Tst
  • Cha
  • Enc
  • Code
  • IP
  • Fun
  • Sub
  • DigF
  • Cis
  • Com
  • Db
  • About
  • Netsim

Paillier cryptosystem

[Back] The Paillier cryptosystem supports homomorphic encryption, where two encrypted values can be added together, and the decryption of the result gives the addition:

Parameters

Value:

P:

Q:

Note: If a value of g is generated which shares a factor with \(n^2\), the calculation will fail. More details on this [here]. We could easily test for this, but I've kept it in the code so that you can see that the caclculation will not work.

The valid g values (up to 100) for p=41, q=43 [\(n^2=3108169\)] is [here]

The valid g values (up to 100) for p=17, q=19 [\(n^2=104329\)] is [here]

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

Presentation