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.
Homomorphic Multiplication with ElGamal using PowerShell |
Theory
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 (\(a\) and \(b\)), and then uses his private key (\(x\)) to decrypt the values and discover the message:
\(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 \)
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
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($message, $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" } "Val 1: "+$val1 "Val 2: "+$val2 $p = [BigInt]::Pow(2,255)-19 $n = 2048 $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
A sample run shows:
Val 1: 123 Val 2: 2 Private key: 50048876155269220175230373810258447547913383619713828126290269007811510034074 Prime: 57896044618658097711785492504343953926634992332820282019728792003956564819949 Public key (Y,p,g)= 35073991775012042967168207582609061691033794519149082473328567136170872368142 57896044618658097711785492504343953926634992332820282019728792003956564819949 7 Ciphers: a1=23285903972345465345360273303037155269262119320990949128036755535144877327162 b1=54599991409067107992056555395244804998126508061331961572181962136839591218191 a2=31254409150103506441872645994151183818188620492342102421348414421469352401658 b2=3297102123360620564944464710328482629762078170110973763291875491036487695071 a=20769250840569534649200497670826856544851915647755369165757804824134324578604 b=45288348400372031577555065407758497062651767221538287839630982004174834048775 Decrypted: 246
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.