ElGamal Homomorphic Multiplication with Python[ElGamal Home][Home]
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 multiply the ciphered values. With this we encrypt two integers, and then multiply the ciphered values, and then decrypt the result.
|
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 \)
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}\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*a2) %p b=(b1*b2) %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=10 v2=34 Prime bits=60 Public key: g=734346575755555349 Y=367696589006816172 p=787202037707659571 Private key x=466969224259741451 Encrypted (v1) a=171786812841192100 b=205804868040016564 Encrypted (v2) a=386907419641951 b=555231043574564515 After homomorphic encryption a=517494939977277643 b=122169903164151101 Result: 340
and for 512-bit primes:
v1=10 v2=34 Prime bits=512 Public key: g=8143276510945862903726899010946453352368246037588233668858647939048592064448296379316202897800777572011261165184623718638604176725317075197852662427009971 Y=4036066775608911770318535628872852093954186164714891230739728500000442235422764661965454186485169246795597160536201319116895828209213748417456634811496755 p=8276436424627097844279806651535284202794565931984967257652906091651975134147784049024443110703788096521343755165238592060445205116555193791668423955788697 Private key x=3641828277990357129253695677788899199819696409841725267468082793950274408089723651791350897062221540559581908855742232672134142378636151756855993640643953 Encrypted (v1) a=5473512104637383138114214167877113510078121588900413262698073730306083495610466265490125911938322073438921888510888794132358999239891267304838984034891739 b=3901101614138791175915445047296716202421468443144080986953751151719877932795907037622303723387585414650690688773853403818596992448661795913713275607938738 Encrypted (v2) a=6654007609621371566586914715832413587775028592857082401880519204469314724862089741988042575178604059538938068699201974017514269882186122528789679186250736 b=2790367683990053260728224798008463510631092789025408027595512770673017449283772442784289419623194986157305960906953653537533140438011143795670371101036543 After homomorphic encryption a=2034564617453654600203090756818743491290801466060687470205982549419515944685909896063217489472357096360570125165150803657598520017933395641000565048118608 b=7295692488792908890576489938431846190650202029157972650749178323522777654779347960767847709291706628677409522591878620522572453548059415120601121785702462 Result: 340