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.
Homomorphic Addition with ElGamal using PowerShell |
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 = 0; $i -lt 2000; $i++){ $val = [BigInt]::ModPow($g, $i, $p) if ($val -eq $dec) { "Found it at ",$i } }
The modification for encryption is simply:
function encrypt($g, $p, $n, $message) { $k=getRandom $p $n $a = [BigInt]::ModPow($g, $k, $p) $s = [BigInt]::ModPow($Y, $k, $p) $b = ([BigInt]::Multiply([BigInt]::ModPow($g,$message,$p), $s)) % $p return $a,$b }
Coding
function inverse_mod([BigInt] $a,[BigInt] $p){ # res = a^{-1} (mod p) $val = [BigInt]0 $nt = [BigInt]1 $r = $p $nr = $a while ($nr -ne [BigInt]0) { $q = [BigInt]::Divide($r,$nr) $val_temp = $nt $nt = [BigInt]::Subtract($val,[BigInt]::Multiply($q,$nt)) $val = $val_temp $val_temp = $nr $nr = [BigInt]::Subtract($r, [BigInt]::Multiply($q,$nr)) $r = $val_temp } if ($r -gt 1) {return -1} if ($val -lt 0) {$val = [BigInt]::Add($val,$p)} return $val } function getg([BigInt] $p){ $One = [BigInt] 1 $Two = [BigInt] 2 $etotient = [BigInt]::Subtract($p, $One) $g = 3 $e = [BigInt]::Divide($etotient,$Two) while([BigInt]::ModPow($g, $e, $p) -ne $etotient ){ $g = [BigInt]::Add($g, $Two) } return $g } function getRandom([BigInt]$p, [BigInt]$n) { $rngValue = [System.Security.Cryptography.RNGCryptoServiceProvider]::new() $bytesb = [byte[]]::new($n / 8) $rngValue.GetBytes($bytesb) $r = ([BigInt]::new($bytesb)) % $p if($r -le [BigInt]::Zero ) {$r = [BigInt]::Add($r, $p) } return $r } function encrypt($g, $p, $n, $message) { $k=getRandom $p $n $a = [BigInt]::ModPow($g, $k, $p) $s = [BigInt]::ModPow($Y, $k, $p) $b = ([BigInt]::Multiply([BigInt]::ModPow($g,$message,$p), $s)) % $p return $a,$b } function decrypt($a, $b, $x, $p) { $aval = [BigInt]::ModPow($a, $x, $p) $aval_inv = inverse_mod $aval $p $d = ([BigInt]::Multiply($aval_inv, $b)) % $p return $d } function getPublic($x,$p) { $g = getg $p $Y = [BigInt]::ModPow($g, $x, $p) return $Y,$g } function homomorphic_multiply($a1, $b1, $a2, $b2, $p) { $a=($a1*$a2) % $p $b=($b1*$b2) % $p return ($a,$b) } $val1 = 123 $val2 = 2 try { if ($Args.Count -gt 0) { $val1=[BigInt]::new($Args[0]) } } catch { "Value needs to be an integer" } try { if ($Args.Count -gt 1) { $val2=[BigInt]::new($Args[1]) } } catch { "Value needs to be an integer" } $p = [BigInt]::Pow(2,255)-19 $n = 2048 "Val 1="+$val1 "Val 2="+$val2 $x = getRandom $p $n "`nPrivate key: "+$x "Prime: "+$p $Y,$g= getPublic $x $p "`nPublic key (Y,p,g)=",$Y, $p, $g "`nCiphers:" $a1,$b1=encrypt $g $p $n $val1 $a2,$b2=encrypt $g $p $n $val2 "a1="+$a1 "b1="+$b1 "a2="+$a2 "b2="+$b2 $a,$b = homomorphic_multiply $a1 $b1 $a2 $b2 $p "`na="+$a "b="+$b $dec= decrypt $a $b $x $p "`nDecrypted: "+$dec for($i = 0; $i -lt 2000; $i++){ $val = [BigInt]::ModPow($g, $i, $p) if ($val -eq $dec) { "Found it at ",$i } }
A sample run shows:
Val 1=123 Val 2=2 Private key: 31661214819259807736582945904364190995035214036018771289111795683337531242485 Prime: 57896044618658097711785492504343953926634992332820282019728792003956564819949 Public key (Y,p,g)= 35245898383657226824431766963132275651101208978523287439812541909332869174963 57896044618658097711785492504343953926634992332820282019728792003956564819949 7 Ciphers: a1=46647843661538132662314542086965202637079098194599780815238513363677119126982 b1=29288738144887399198626350047468946941309811495749845396583005724164519812479 a2=3585520469578601868919775782667914572945836972250816755681226260377751315048 b2=19264811762196019370936233993521374000210113781545359911205929221229720311795 a=37061270334995932908141694617615753599167578760684830612228151585794905218756 b=33704662386790229752469573992519761328912431973095640159213111476311432518901 Decrypted: 30197879825391645818316331621553681244838314309861167987286111038376761336908 Found it at 125
It should be noted, that for performance reasons, the prime number I have used is relatively small (\(2^{255}-19\)), and well-known. In real-life, we would use a prime number that had at least 1,024 bits, and that was randomly generated.