ElGamal with PowerShell[ElGamal Home][Home]
ElGamal is a public key encryption method, and which has a public key (\(P,G,Y\)) and a private key (\(x\)). The following will encrypt a value using ElGamal:
|
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 \)
Coding
In finite fields, the operation of \(\frac{1}{x} \pmod p\) is performed as an inverse of \(x\) mod p. The first thing we need is a random number generator for our values of x and k. For this we can generate a prime number with \(n\) bits, but ranges between 0 and p-1:
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 }
Next we need to select a generator value (g) that will work with our prime number:
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 }
and then finally an inverse mod function:
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 }
And, that’s the basic foundation. The computation then follows the maths defined above. To generate the keys:
$p = [BigInt]::Pow(2,255)-19$g = getg($p) $n = 2048$x = getRandom $p $n "`nPrivate key: "+$x "Prime: "+$p$Y = [BigInt]::ModPow($g, $x, $p) "`nPublic key (Y,p,g)=",$Y, $p, $g
To encrypt:
$k=getRandom $p $n$a = [BigInt]::ModPow($g, $k, $p) $s = [BigInt]::ModPow($Y, $k, $p)$b = ([BigInt]::Multiply($message, $s)) % $p "`nCiphers:\n" "`na="+$a "`nb="+$b
and then to decrypt:
$aval = [BigInt]::ModPow($a, $x, $p) $aval_inv = inverse_mod $aval $p $decrypt = ([BigInt]::Multiply($aval_inv, $b)) % $p"`nDecrypted: "+$decrypt
The whole program is here:
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) { $rngBob = [System.Security.Cryptography.RNGCryptoServiceProvider]::new() $bytesb = [byte[]]::new($n / 8) $rngBob.GetBytes($bytesb) $r = ([BigInt]::new($bytesb)) % $p if($r -le [BigInt]::Zero ) {$r = [BigInt]::Add($r, $p) } return $r } $message = 123 try { if ($Args.Count -gt 0) { $message=[BigInt]::new($Args[0]) } } catch { "Value neees to be an integer" } "Message (m)="+$message $p = [BigInt]::Pow(2,255)-19 $g = getg($p) $n = 2048 $x = getRandom $p $n "`nPrivate key: "+$x "Prime: "+$p $Y = [BigInt]::ModPow($g, $x, $p) "`nPublic key (Y,p,g)=",$Y, $p, $g $k=getRandom $p $n $a = [BigInt]::ModPow($g, $k, $p) $s = [BigInt]::ModPow($Y, $k, $p) $b = ([BigInt]::Multiply($message, $s)) % $p "`nCiphers:\n" "`na="+$a "`nb="+$b $aval = [BigInt]::ModPow($a, $x, $p) $aval_inv = inverse_mod $aval $p $decrypt = ([BigInt]::Multiply($aval_inv, $b)) % $p "`nDecrypted: "+$decrypt
A sample run shows:
Message (m)=123 Private key: 40681332542682508556044397693085552632818215432492888979348789881074313011321 Prime: 57896044618658097711785492504343953926634992332820282019728792003956564819949 Public key (Y,p,g)= 30371710708851180643075565661825609732685467630973818178826123397094941821360 57896044618658097711785492504343953926634992332820282019728792003956564819949 7 Ciphers:\n a=14264038268698873369992814534630046301084393045816892727735948003166873227949 b=50047878151129483743586542092552366427960979159301879067240463470176904168631 Decrypted: 123
Enhanced coding
We can enhance the code by adding functions for encrypt and decrypt:
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 } $val1 = 123 try { if ($Args.Count -gt 0) { $val1=[BigInt]::new($Args[0]) } } catch { "Value neees to be an integer" } $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 "a=",$a1 "b=",$b1 $dec= decrypt $a1 $b1 $x $p "`nDecrypted: "+$dec