ElGamal Homomorphic Addition 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 add the ciphered values. With this we encrypt two integers, and then multiply the ciphered values, and then decrypt the result. For subtraction, we need to make a modification to the normal ElGamal encryption process.
|
Theory
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\)
This 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 \)
Now with additive homomorphic encryption, we change the encryption to be:
\(a=g^k \pmod p\)
\(b=Y^k g^M \pmod p\)
Notice that instead of \(b=Y^k M \pmod p\) we now have \(b=Y^k g^M \pmod p\).
The result of the decryption then gives:
\(Result = \frac{b_1 b_2}{a_1^x a_2^x} = g^{M_1+M_2} \pmod p\)
Then just need to brute force the resulting value to find a value which matches \(g^i\).
The working out is:
\(a_1=g^{r_1} \pmod p\)
\(b_1=g^{M_1} Y^{r_1} \pmod p\)
\(a_2=g^{r_2} \pmod p\)
\(b_2=g^{M_2} Y^{r_2} \pmod p\)
and then:
\(Result = \frac{b_1 b_2}{a_1^x a_2^x} = \frac{g^{M_1} Y^{r_1} g^{M_2} Y^{r_2}}{ { (g^{r_1})}^x {(g^{r_2})}^x } = \frac{ g^{M_1+M_2} {g^x}^{r_1} {g^x}^{r_2} } { g^{x r_1} g^{x r_2} }= g^{M_1+M_2} \pmod p \)
We then search the result for possible values of \(M_1+M_2\). An example of a search for the solution to \(v_r\) is:
for i in range(1,2**bits): if (pow(g,i,p)==v_r): print("Found: ",i) break
The modification (for values of \(v_1\) and \(v_2\)) is simply:
k1=random.randrange(3, p) a1=pow(g,k1,p) b1=(pow(Y,k1,p)*pow(g,v1,p)) % p k2=random.randrange(3, p) a2=pow(g,k2,p) b2=(pow(Y,k2,p)*pow(g,v2,p)) % 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)*pow(g,v1,p)) % p k2=random.randrange(3, p) a2=pow(g,k2,p) b2=(pow(Y,k2,p)*pow(g,v2,p)) % 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 ) # Now search for g^i for i in range(1,2**64): if (pow(g,i,p)==v_r): print("Found: ",i) break
A sample run for 60-bit primes:
v1=100 v2=20 Public key: g=333374572481292215 Y=146305090762166910 p=1138684483882065691 Private key x=809221028367156131 Encrypted (v1) a=540316846229126590 b=129888478983669631 Encrypted (v2) a=222817853856301123 b=992982807967928979 After homomorphic encryption a=656358368765468669 b=640373011356780991 Result: 675933486940335517 Found: 120
for 256-bit primes:
v1=100 v2=20 Public key: g=21932917402587370965484210497047352360160642144205588937243769373036084385060 Y=43575872687285106028765622551913096701868002337906278336560109523658208211058 p=70672345837817662864213466491782394892407832824892671893927482514525155916607 Private key x=69667729329643900261593281649931555556071155287512591323910379195201719061542 Encrypted (v1) a=38189587203452962708214083685823913529496012187732910898643999369004221054814 b=44662954823292896614685664694449496476318130759988760409129853634101176521933 Encrypted (v2) a=29714788095548264380606967854304801337858539300276513388990998807968759080115 b=10232606564630666021398186431650345071429991669893684556413043418350880761875 After homomorphic encryption a=6779137157514551164862372271062818054112893256450299793650554983106157609704 b=15316768322557571728873550603719557667237565007575088530609925378153721709096 Result: 1320870496772974675701572265575916927909387675826663657556815991154559524700 Found: 120