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.
ElGamal Homomorphic Subtraction with Python |
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 subtractive 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\)
We then perform:
\(a=a_1 \times {a_2}^{-1}\)
\(b=b_1 \times {b_2}^{-1}\)
and then:
\(Result = \frac{b_1 {b_2}^{-1}}{a_1^x {(a_2^x)}^{-1}} = \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**64): 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 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}\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*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 ) # Now search for g^i for int (64-bits) 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=634511071151074732 Y=434161624779614506 p=1070720106522838511 Private key x=428318313562927178 Encrypted (v1) a=465035622695225653 b=544621951622213680 Encrypted (v2) a=576370787357568805 b=383463212221472783 After homomorphic encryption a=692027927087440367 b=290529954123484250 Result: 708140448979635969 Found: 80
and for 256-bit primes:
v1=100 v2=20 Public key: g=83449192520293666514778780462605182518660703224144000454239339382028794997199 Y=63870451191338047970784984403246191824243096758057197342851470840098588728445 p=107029989304192529808234258162561311967016884889317008359082575046559472185647 Private key x=62625193049329969827107265991975654770059927190722686656606278566992235857040 Encrypted (v1) a=102907308167966215731053613262540765705136077015778635255948251904278649708646 b=31291550565407040706867190769007179211763474172717018514679878352788841842158 Encrypted (v2) a=18635469092921796118607886776993572709816794300696285179383659751148246330253 b=103374215460962606832503845759315149828787381738982544459397291807551892805901 After homomorphic encryption a=45180462140478230209637879494975286750308269918273177785947178608600691082509 b=27696238873641147131219407493018825554553482921208337256711284596490121168301 Result: 19995672774926724939388976755643150333110209022908298763385226204930987405389 Found: 80