Discrete Log Implementation of Schnorr Signatures in PowerShell

Discrete Log Implementation of Schnorr Signatures in PowerShell

In Feb 1989, Claus Schnorr submitted a patent which was assigned to no one. It has 11 claims and allowed digital signatures to be merged for multiple signers [here]:

This method has the great advantage that we can have multiple signers to a message or a transaction and end up with a single signature for all the signers. It is now being used in Bitcoin transactions so that we have an efficient signature for a transaction that involves multiple entities.

With the Schnorr signature, we create a signature (r,e) for a hash of the message (m). Initially, Peggy (the prover) has a private key x, and her public key will then be:

and where G is the base point on the curve. She then generates random nonce (k) for the signing of a message and defines a commitment to this value:

Next, with a message (M), she computes a challenge (e) with a hash function of:

Next, Peggy computes:

Peggy then sends e and s to Victor (the verifier). Victor then determines:

If e_v is equal to the e value that Peggy sent, the signature has been proven. This works because:

The Schnorr method — using elliptic curve methods — is implemented here:

Coding

Now let’s implement using PowerShell. Overall, PowerShell supports the usage of Big Integers and can deal with the large values that are computed within the signature creation. With this we need to implement the discrete logs of:

We could end up with a negative value for s or e. For this, we must perform an inverse mod operation. This is typically implemented with an Extended Euclidian method. In the following we detect is s is a negative value, and if so, we negate the value, and then perform an inverse mod operation:

if ($s -lt 0) 
{ 
    $val1= ([BigInt]::ModPow($g,-$s,$p))
    [BigInt]$val1=Get-ExtendedEuclide $val1 $p   
}
else  {
    $val1= ([BigInt]::ModPow($g,$s,$p))
}

We can do the same for e with:

if ($e -lt 0) 
{ 
    $val2= [BigInt]::ModPow($Y,-$e,$p)
    [BigInt]$val2=Get-ExtendedEuclide $val2 $p
}
else  {
    $val2= [BigInt]::ModPow($Y,$e,$p)
}

and then finally compute the result as:

$r_v=($val1*$val2) % $p

The full code is [here]:

$g=5

$word=$Args[0]
$hashmethod=$Args[1]
$bytesize=([BigInt]$Args[2])

# Return a random integer with a given number of bytes
function Get-Rand($randBytesSize) {

    $rand = [Security.Cryptography.RandomNumberGenerator]::Create()
    $r = [byte[]]::new($randBytesSize)
    $rand.GetBytes($r)
    return([System.Numerics.BigInteger]::Abs([System.Numerics.BigInteger]::new($r)))
}

# Source: https://social.technet.microsoft.com/wiki/contents/articles/33421.powershell-implementing-the-rsa-algorithm-powerrsa.aspx
function Get-ExtendedEuclide($e, $PHI) {
    $u = @(1,0,$PHI)
    $v = @(0,1,$e)               
    while ($v[2] -ne 0) {       
        $q = $u[2] / $v[2]
        $temp1 = $u[0] - $q * $v[0]
        $temp2 = $u[1] - $q * $v[1]
        $temp3 = $u[2] - $q * $v[2]
        $u[0] = $v[0]
        $u[1] = $v[1]
        $u[2] = $v[2]
        $v[0] = $temp1
        $v[1] = $temp2
        $v[2] = $temp3
    }
    if ($u[1] -lt 0) {return ($u[1] + $PHI)}
    else {return ($u[1])}
} 

[BigInt]$x=Get-Rand $bytesize
[BigInt]$p = [math]::Pow(2,255)-19
[BigInt]$Y = ([BigInt]::ModPow($g,$x,$p)) 

[BigInt]$k=Get-Rand $bytesize
$r=([BigInt]::ModPow($g,$k,$p)) 
$rbytes=$r.ToByteArray($r)

$h=[System.Text.Encoding]::UTF8.GetBytes($word)+$rbytes
$hash1=[System.Security.Cryptography.HashAlgorithm]::Create($hashmethod).ComputeHash($h)

$e=([System.Numerics.BigInteger]::new($hash1)) % $p

"`n=== Bob private key ==="
"x (Private key)= "+$x
"`n=== Bob public key ==="
"g= "+$g
"p= "+$p
"Y= "+$Y

"`nBob generates nonce (k):"
"k= "+$k
"`nBob calculates:"
"r=g^k (mod p)= "+$r

"e=Hash (M || r})= "+[System.Convert]::ToHexString($hash1)

$s=($k-$x*$e) 

"s= "+$s

"`nAlice received public key (Y,g,p) and (s,e):"

if ($s -lt 0) 
{ 
    $val1= ([BigInt]::ModPow($g,-$s,$p))
    [BigInt]$val1=Get-ExtendedEuclide $val1 $p   
}
else  {
    $val1= ([BigInt]::ModPow($g,$s,$p))
}
if ($e -lt 0) 
{ 
    $val2= [BigInt]::ModPow($Y,-$e,$p)
    [BigInt]$val2=Get-ExtendedEuclide $val2 $p
}
else  {
    $val2= [BigInt]::ModPow($Y,$e,$p)
}

$r_v=($val1*$val2) % $p
"r_v is "+$r_v

$r_vbytes=$r_v.ToByteArray($r_v)

$h=[System.Text.Encoding]::UTF8.GetBytes($word)+$r_vbytes
$hash1=[System.Security.Cryptography.HashAlgorithm]::Create($hashmethod).ComputeHash($h)
$e_v=([System.Numerics.BigInteger]::new($hash1)) % $p
"e_v=Hash (M || r})= "+[System.Convert]::ToHexString($hash1)

if ($e -eq $e_v) {
    "Signature verified!"
} else {
    "Signature Not Verified!"
}

A sample test [here]:

=== Bob private key ===
x (Private key)= 1500816580

=== Bob public key ===
g= 5
p= 57896044618658097711785492504343953926634992332820282019728792003956564819968
Y= 8333359242989940778123958381244509518012550826645876676866697812350110302065

Bob generates nonce (k):
k= 1925519553

Bob calculates:
r=g^k (mod p)= 24124040978470198428263581548214263804276322126418742819747772483775855653125
e=Hash (M || r})= 4A0F2EEAD0C786C989C1430A8C6A917B
s= -246509254671351498989454265045139228622649951207

Alice received public key (Y,g,p) and (s,e):
r_v is 24124040978470198428263581548214263804276322126418742819747772483775855653125
e_v=Hash (M || r})= 4A0F2EEAD0C786C989C1430A8C6A917B
Signature verified!

Overall the implementation uses a g value of 5, and a prime number of 2²⁵⁵-19, but could be easily modified to select random values for this. If you are interested, the demo is here:

https://asecuritysite.com/powershell/sch

Conclusions

Schnorr signatures have a few advantages over ECDSA, especially when convered into an elliptic curve form. These advantages include signature aggregation, and which is being increasingly applied into areas of cryptocurrency signing.