Homomorphic Division 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 divide the ciphered values. With this we encrypt two integers, and then divide the ciphered values, and then decrypt the result.
|
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 \)
Division
For division, we take the inverse of the divisor (\(a_2\), \(b_2\)) values:
\(a=a_1 \times {a_2}^{-1} \pmod p\)
\(b=b_1 \times {b_2}^{-1} \pmod p\)
This is implemented as an inverse mod p operation:
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($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) { $a=$a1*$a2 $b=$b1*$b2 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 = 122 $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
A sample run shows:
Val 1: 122 Val 2: 2 Private key: 44415260782954284503216199934190770620867334934924629379926578074732627355667 Prime: 57896044618658097711785492504343953926634992332820282019728792003956564819949 Public key (Y,p,g)= 36870533807593818616068375501840243799134925802276276365083339081341447931491 57896044618658097711785492504343953926634992332820282019728792003956564819949 7 Ciphers: a1=2911341515763668905304853016825667556516543933904594655523095115376475610354 b1=33572020852860820527856041277175994850163754064564637505363577456242102491665 a2=29487611097460687950789131973405913705106104657449398444395520998713261224524 b2=17740712175934135247262311636211343440572809904503165480131067461442481006724 a=18893970600233050537224050222754078035985405605188138169969727023916659758296 b=56570737641176273972056628620601491352663861083687471401979116893115870829836 Decrypted: 61
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.