ElGamal Encryption in PowerShell

elgamal.ps1

<#

	ElGamal in PowerShell
	by Casey Smith @subTee
	

The key generator works as follows:
Alice generates an efficient description of a cyclic group G of order q ,with generator g. 
Alice chooses an x randomly from 1 - (q-1)
Alice computes h = g^x.
Alice publishes h along with the description of G, q, g as her public key. Alice retains x as her private key, which must be kept secret.

Encryption:
The encryption algorithm works as follows: to encrypt a message m to Alice under her public key (G,q,g,h),

Bob chooses a random y from (1...q-1), then calculates c_1 = g^y.
Bob calculates the shared secret s = h^y.
Bob maps his secret message m onto an element m' of G. (Inverse Mod)
Bob calculates c_2 = m'(s) 
Bob sends the ciphertext (c_1,c_2) = (g^y, m'(h^y)) = (g^y, m'(g^x)^y) to Alice.
Note that one can easily find h^y if one knows m'. Therefore, a new y is generated for every message to improve security. For this reason, y is also called an ephemeral key.

Decryption:
The decryption algorithm works as follows: to decrypt a ciphertext (c_1,c_2) with her private key x,

Alice calculates the shared secret s = c_1^x
and then computes m' = c_2(s^(-1)) which she then converts back into the plaintext message m, where s^{-1} is the inverse of s in the group G. (E.g. modular multiplicative inverse if G is a subgroup of a multiplicative group of integers modulo n).
The decryption algorithm produces the intended message.
	
//Free Large Known Primes For Testing
//https://primes.utm.edu/lists/small/small.html
#>

[Reflection.Assembly]::LoadWithPartialName("System.Security")

function invmod([System.Numerics.BigInteger] $a,[System.Numerics.BigInteger] $n){	
	
	$exp = $t = $nt = $r = $nr = New-Object System.Numerics.BigInteger
	$exp = [System.Numerics.BigInteger]1
	$t = [System.Numerics.BigInteger]0
	$nt = [System.Numerics.BigInteger]1
	$r = $n
	$nr = $a
	while ($nr -ne [System.Numerics.BigInteger]0) {
		$q = [System.Numerics.BigInteger]::Divide($r,$nr)		
		$tmp = $nt
		$nt = [System.Numerics.BigInteger]::Subtract($t,[System.Numerics.BigInteger]::Multiply($q,$nt))
		$t = $tmp
		$tmp = $nr
		$nr = [System.Numerics.BigInteger]::Subtract($r, [System.Numerics.BigInteger]::Multiply($q,$nr))
		$r = $tmp
	}
	if ($r -gt 1) {return -1}
	if ($t -lt 0) {$t = [System.Numerics.BigInteger]::Add($t,$n)}
	return $t
}

$One = [System.Numerics.BigInteger] 1
$Two =  [System.Numerics.BigInteger] 2
$p = New-Object System.Numerics.BigInteger
$result = [System.Numerics.BigInteger]::TryParse("5371393606024775251256550436773565977406724269152942136415762782810562554131599074907426010737503501", [ref] $p)
$etotient = [System.Numerics.BigInteger]::Subtract($p, $One)
$g = [System.Numerics.BigInteger] 3
$e = [System.Numerics.BigInteger]::Divide($etotient,$Two)
#Find Generator
while([System.Numerics.BigInteger]::ModPow($g, $e, $p) -ne $etotient ){ $g = [System.Numerics.BigInteger]::Add($g, $Two) }
$n = 2048
$rngAlice = New-Object System.Security.Cryptography.RNGCryptoServiceProvider
[byte[]] $bytesa = New-Object Byte[] ($n / 8)
$rngAlice.GetBytes($bytesa)
[System.Numerics.BigInteger] $x = (New-Object System.Numerics.BigInteger -ArgumentList @(,$bytesa)) % $p
if($x -lt [System.Numerics.BigInteger]::Zero) { $x = [System.Numerics.BigInteger]::Add($x, $p) } 
[System.Numerics.BigInteger] $h = [System.Numerics.BigInteger]::ModPow($g, $x, $p)
Write-Host $h, $p, $g -Fore Yellow

#Encrypt Message
$rngBob = New-Object System.Security.Cryptography.RNGCryptoServiceProvider
[byte[]] $bytesb = New-Object Byte[] ($n / 8)
$rngBob.GetBytes($bytesb)
[System.Numerics.BigInteger] $y = (New-Object System.Numerics.BigInteger -ArgumentList @(,$bytesb)) % $p
if($y -le [System.Numerics.BigInteger]::Zero ) {$y = [System.Numerics.BigInteger]::Add($y, $p) } 
#Compute Secret Message
[System.Numerics.BigInteger] $c_1 = [System.Numerics.BigInteger]::ModPow($g, $y, $p)
[System.Numerics.BigInteger] $s = [System.Numerics.BigInteger]::ModPow($h, $y, $p)
[System.Numerics.BigInteger] $message = [System.Numerics.BigInteger] 123
[System.Numerics.BigInteger] $minv = invmod $message $p
[System.Numerics.BigInteger] $c_2 = ([System.Numerics.BigInteger]::Multiply($minv, $s)) % $p
Write-Host $c_1 $c_2 -Fore Magenta

#Decrypt Message
[System.Numerics.BigInteger] $s1 = [System.Numerics.BigInteger]::ModPow($c_1, $x, $p)
[System.Numerics.BigInteger] $sinv = invmod $s1 $p
[System.Numerics.BigInteger] $minv1 = ([System.Numerics.BigInteger]::Multiply($sinv, $c_2)) % $p
[System.Numerics.BigInteger] $decrypt = invmod $minv1 $p
Write-Host $decrypt -Fore Green