With Schnorr signatures can use discrete logarithms to produce a digital signature. Overall, we take a hash of a message, and then create a signature using a private (secret) key and a random nonce value (\(k\)). The public key and a hash of the message is then be used to verify the signature. In this case, we will create the signature using a range of key sizes, and a range of hashing methods (such as MD5, SHA-1 and SHA-256).
Schnorr Signature Method with Discrete Logs using PowerShell |
Method
DSA is similar to Schnorr signatures. With Schnorr signatures implemented with discrete logarithms, Peggy generates a secret value of \(x\), and a prime number of \(p\). He then produces a public key of:
\(Y=g^x \pmod p\)
Peggy then creates a random number of \(k\) and computes:
\(r = g^{k} \pmod{p}\)
Next, with a message (\(m\)), she computes a challenge (\(e\)) with a hash function of:
\(e=H(r || M)\)
Next, Peggy computes:
\(s = k - x.e\)
Peggy then sends \(e,s\) to Victor (the verifier). Victor then determines if:
\(r_v = g^s. Y^e\)
\(e_v = H(r_v || M) \)
\(e_v\) should equal \(e\). This works because:
\(r_v = g^s. g^{x.e} = g^{k-x.e}. g^{x.e}=g^{k-x.e+x.e} = g^k = r\)
Coding
The full code is:
$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:
=== 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!