Homomorphic Subtraction with ElGamal using PowerShell[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 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 = 0; $i -lt 100000; $i++){ $val = [BigInt]::ModPow($g, $i, $p) if ($val -eq $dec) { "Found it at ",$i } }
The modification for the subtraction is then simply:
function homomorphic_divide($a1, $b1, $a2, $b2, $p) { $aval2_inv = inverse_mod $a2 $p $bval2_inv = inverse_mod $b2 $p $a=($a1*$aval2_inv) % $p $b=($b1*$bval2_inv) % $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) } function homomorphic_divide($a1, $b1, $a2, $b2, $p) { $aval2_inv = inverse_mod $a2 $p $bval2_inv = inverse_mod $b2 $p $a=($a1*$aval2_inv) % $p $b=($b1*$bval2_inv) % $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_divide $a1 $b1 $a2 $b2 $p "`na="+$a "b="+$b $dec= decrypt $a $b $x $p "`nDecrypted: "+$dec for($i = 0; $i -lt 100000; $i++){ $val = [BigInt]::ModPow($g, $i, $p) if ($val -eq $dec) { "Found it at ",$i } }
A sample run for \(122-2\) is:
Val 1=122 Val 2=2 Private key: 11353616101456313527333169798300028091230339861879949392302908496449540202224 Prime: 57896044618658097711785492504343953926634992332820282019728792003956564819949 Public key (Y,p,g)= 47270704775787912070930482634976461983809118022269332068483195146238006957673 57896044618658097711785492504343953926634992332820282019728792003956564819949 7 Ciphers: a1=8893530320853120728645377168462692666004506206533027623831709945936384755149 b1=22955380700856006240768840176288785225224731084141216297133217197407345743913 a2=19132020781455067198487621645166629170236097874525223702362832603954170327136 b2=38622252173758732982019406975268141465204577766385782070002919209522298262657 a=23763986634661315945838227316358738672634273100966780315851975664476492622490 b=39754811522754831025215919581428753136857272232915069869118584206963600864786 Decrypted: 10156942786673972969605637426930893666743904070414949280784659066978183486080 Found it at 120
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.