With ElGamal encryption, Alice has a public key (\(Y,g,p\)) and a private key of \(x\). The public key is \(Y=g^x \pmod p\). We can use ElGamal encryption for partial homomorphic encryption (PHE), and where we can perform a divison operation the ciphered values. With this we encrypt two integers, and then multiply the ciphered values, and then decrypt the result.
ElGamal Homomorphic Division with Python |
Outline
With homomorphic encryption, we can mathematically operation on values. For example, we can encrypt the value of 5, and the value of 4, and then multiply the encrypted values, and when we decrypt, we will get a value of 20. Thus, we can encrypt two values (\(a\) and \(b\)) with a public key (\(pk\)):
\(A = Enc_{pk}(a)\)
\(B = Enc_{pk}(b)\)
and then multiply the ciphered values to give a result \(C\)):
\(C = Enc_{pk}(a) \times Enc_{pk}(b)\)
Then, when we decrypt \(C\) we should get the multiplication of \(a\) and \(b\):
\(a \times b == Dec_{sk}(C)\)
With ElGamal encryption, initially Bob creates his public key by selecting a \(g\) value and a prime number (\(p\)) and then selecting a private key (\(x\)). He then computes \(Y\) which is:
\(Y=g^x \pmod p\)
His public key is \((Y, g, p)\) and he will send this to Alice. Alice then creates a message (\(M\)) and selects a random value \(k\). She then computes \(a\) and \(b\):
\(a=g^k \pmod p\)
\(b=Y^k.M \pmod p\)
Bob then receives these and decrypts with:
\(M=\frac{b}{a^x} \pmod p\)
his works because \(\frac{b}{a^x} \pmod p = \frac{Y^k M}{ {(g^k)}^x } \pmod p = \frac{{(g^x)}^k M}{ {(g^k)}^x } \pmod p = = \frac{g^{xk} M} { g^{xk} } \pmod p = M \)
To multiply homomorphically, we have:
\(a_1=g^{k_1} \pmod p\)
\(a_2=g^{k_2} \pmod p\)
\(b_1=y^{k_1} M_1 \pmod p\)
\(b_2=y^{k_2} M_2 \pmod p\)
Then we get:
\(a=a_1 \times a_2 = g^{k_1} \times g^{k_2} = g^{k_1+k_2} \pmod p\)
\(b=b_1 \times b_2 = Y^{k_1} M_1 \times Y^{k_2} M_2 = Y^{k_1+k_2} M_1 M_2 \pmod p\)
\(M=\frac{b}{a^x} = \frac{Y^{k_1+k_2} M_1 M_2}{({g^{(k_1+k_2)})}^x} = \frac{Y^{k_1+k_2} M_1 M_2}{g^{(k_1+k_2)x}} = \frac{Y^{k_1+k_2} M_1 M_2} {({g^{x})}^{(k_1+k_2)} } = \frac{Y^{(k_1+k_2)} M_1 M_2} { Y^{(k_1+k_2)} } = M_1 M_2 \pmod p \)
Division
For division, we take the inverse of the values:
\(a=a_1 \times {a_2}^{-1} \pmod p\)
\(b=b_1 \times {b_2}^{-1} \pmod p\)
This is implemented as an inverse mod p operation:
a=a1*libnum.invmod(a2,p) b=b1*libnum.invmod(b2,p)
Coding
One of the great advantages of using Python is that it automatically deals with Big Integers. We thus do not need any special data type and can just operate on them as if they were normal integer types. The coding is here:
from Crypto.Util.number import * from Crypto import Random import Crypto import random import libnum import sys import hashlib def get_generator(p: int): while True: # Find generator which doesn't share factor with p generator = random.randrange(3, p) if pow(generator, 2, p) == 1: continue if pow(generator, p, p) == 1: continue return generator bits=512 v1=10 v2=5 if (len(sys.argv)>1): v1=int(sys.argv[1]) if (len(sys.argv)>2): v2=int(sys.argv[2]) if (len(sys.argv)>3): bits=int(sys.argv[3]) p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes) g = get_generator(p) x = random.randrange(3, p) Y = pow(g,x,p) print (f"v1={v1}\nv2={v2}\nPrime bits={bits}\n") print (f"Public key:\ng={g}\nY={Y}\np={p}\n\nPrivate key\nx={x}") k1=random.randrange(3, p) a1=pow(g,k1,p) b1=(pow(Y,k1,p)*v1) % p k2=random.randrange(3, p) a2=pow(g,k2,p) b2=(pow(Y,k2,p)*v2) % p a=(a1*libnum.invmod(a2,p)) %p b=(b1*libnum.invmod(b2,p)) %p print (f"\nEncrypted (v1)\na={a1}\nb={b1}") print (f"\nEncrypted (v2)\na={a2}\nb={b2}") print (f"\nAfter homomorphic encryption\na={a}\nb={b}") v_r=(b*libnum.invmod(pow(a,x,p),p)) % p print ("\nResult: ",v_r )
A sample run for 60-bit primes:
v1=100 v2=20 Prime bits=60 Public key: g=435057608411669940 Y=557003415518119634 p=757733272242935827 Private key x=707650262260017746 Encrypted (v1) a=337029248383051535 b=9175033130825711 Encrypted (v2) a=294231197444451624 b=680567147051192823 After homomorphic encryption a=719674053967955231 b=32982655701977298 Result: 5
and for 256-bit primes:
v1=100 v2=20 Prime bits=256 Public key: g=41640267227247175515903644127017699932474114107626612459875366791422179202220 Y=77592993381315687857343647614243560618455091976669687600947602371455968598759 p=81362925823705031454850087649509185917128144363389654587626462574862557002337 Private key x=7568855890528009703659695648077420629065220616357481865245044730672396313501 Encrypted (v1) a=27809740622870741822282444736053237159393657659021151160131071713810991933722 b=76981495461762884009741717379802275054574405200746814395601933638262476662079 Encrypted (v2) a=19190229250307904018385770997192941226152735039286233519331974430441215491370 b=48214131550184346044701214469503165621856539039423169362750965237408112931551 After homomorphic encryption a=77957727202657388570332620994896500147165064080366368091378607018277464612673 b=883392235792475841498173455804933673432775208909305643981468173300966745745 Result: 5