Let's say we have two generator values (\(g\) and \(h\)), and a secret value (\(x\)). If we have \(Y=g^x \pmod p\) and \(Z=h^x \pmod p\), can we prove that \(Y\) and \(Z\) use the same exponential value (\(x\))? For this, we then use \(g,Y,h,Z\) within a Chaum-Pedersen proof [1] to provide a zero-knowledge proof that \(log_G(Y) == log_M(Z)\). This is defined as DLEQ(Z/M == Y/G) - discrete log equality. With this we can prove that the same private key has been used for \(g^x \pmod p\) and \(h^x \pmod p)\), and use a random oracle (\(k\)) for each proof.
NIZK (Non-interactive Zero Knowledge) proofs of discrete - log equality with PowerShell |
Method
Before we begin, we define a couple of simple operations:
\(A=g^a.g^b =g^{a+b} \pmod p\)
\(A={(g^a)}^b =g^{a.b} \pmod p\)
Let's say we have two generator values (\(g\) and \(h\)), and a secret value (\(x\)). If we have \(Y=g^x \pmod p\) and \(Z=h^x \pmod p\), can we prove that \(Y\) and \(Z\) use the same exponential value (\(x\))? For this, we then use \(g,Y,h,Z\) within a Chaum-Pedersen proof [1] to provide a zero-knowledge proof that \(log_G(Y) == log_M(Z)\). This is defined as DLEQ(Z/M == Y/G) - discrete log equality. With this we can prove that the same private key has been used for \(g^x \pmod p\) and \(h^x \pmod p)\), and use a random oracle (\(k\)) for each proof.
Let say Peggy (the prover) needs to prove that two public keys use the same private key (\(x\)) but with different base points:
\(Y = g^x \pmod p\)
\(Z = h^x \pmod p\)
Peggy will generator a random value (\(k\)) and then computes two values (\(A\) and \(B\)) based on the generators used (\(g\) and \(h\)):
\(A = g^k \pmod p\)
\(B = h^k \pmod p\)
With non-interactive proofs, Peggy then creates a challenge (\(c\)) of:
\(c=Hash(g,Y,h,Z,A,B)\)
And then calculates:
\(s=k - c.x \pmod p\)
As the proof, Peggy then sends the following to Victor:
\((c,s)\)
The verifier (Victor) then computes:
\(A'=g^s.Y^c\)
\(B'=h^s.Z^c\)
\(c'=Hash(G,Y,M,Z,A',B')\)
If \(c==c'\), the proof has been proven.
This works because:
\( A'= g^s . Y^c = g^s . {(g^x)}^c = g^{k-c.x} . {g^x}^{c} = g^{k-c.x+x.c} = g^k = A\pmod p \)
\( B'= h^s . Z^c = h^s . {(h^x)}^c = h^{k-c.x} . {h^x}^{c} = h^{k-c.x+x.c} = h^k = B\pmod p \)
Coding
The full code is:
$hashmethod="SHA1" $hashmethod=$Args[0] $bytesize=([BigInt]$Args[1]) 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])} } $x=Get-Rand 16 $g=5 $h=3 $k=Get-Rand 16 [BigInt]$p = [math]::Pow(2,255)-19 [BigInt]$Y = ([BigInt]::ModPow($g,$x,$p)) [BigInt]$Z = ([BigInt]::ModPow($h,$x,$p)) [BigInt]$A = ([BigInt]::ModPow($g,$k,$p)) [BigInt]$B = ([BigInt]::ModPow($h,$k,$p)) # I appreciate this is a weak way to generate the hash, but it is not so easy to convert a Big Int to a byte array in PowerShell $cval=[string]$Y+[string]$Z+[string]$A+[string]$B $hash1=[System.Security.Cryptography.HashAlgorithm]::Create($hashmethod).ComputeHash([System.Text.Encoding]::UTF8.GetBytes($cval)) $c=[BigInt]::new($hash1) % $p $s=($k-$c*$x) if ($s -lt 0) { $val1= ([BigInt]::ModPow($g,-$s,$p)) $val2= ([BigInt]::ModPow($h,-$s,$p)) [BigInt]$val1=Get-ExtendedEuclide $val1 $p [BigInt]$val2=Get-ExtendedEuclide $val2 $p } else { $val1= ([BigInt]::ModPow($g,$s,$p)) $val2= ([BigInt]::ModPow($h,$s,$p)) } if ($c -lt 0) { $val3= ([BigInt]::ModPow($Y,-$c,$p)) $val4= ([BigInt]::ModPow($Z,-$c,$p)) [BigInt]$val3=Get-ExtendedEuclide $val3 $p [BigInt]$val4=Get-ExtendedEuclide $val4 $p } else { $val3= ([BigInt]::ModPow($Y,$c,$p)) $val4= ([BigInt]::ModPow($Z,$c,$p)) } $A_=($val1 * $val3) % $p $B_=($val2 * $val4) % $p $cval=[string]$Y+[string]$Z+[string]$A_+[string]$B_ $hash1=[System.Security.Cryptography.HashAlgorithm]::Create($hashmethod).ComputeHash([System.Text.Encoding]::UTF8.GetBytes($cval)) $c_=[BigInt]::new($hash1) % $p "== Peggy and Victor agree on some parameters ==" "g="+$g "h="+$h "p="+$p "`n== Peggy generates a secret ==" "x="+$x "`n== Peggy sends to Victor ==" "Y=g^x (mod p)"+$Y "Z=h^x (mod p)"+$Z "`n== To prove proof of x, Peggy generates a random value ==" "k="+$k "`n== To prove Peggy computes ==" "A=g^k (mod p)="+$A "B=h^k (mod p)="+$B "`n== Peggy sends ==" "c=H(Y || Z || A || B)="+$c "s="+$s "`n== Victor computes ==" "A'=g^s*Y^c="+$A_ "B'=h^s*Z^c="+$B_ "c'=H(Y || Z || A' || B')="+$c_ if ($c -eq $c_) { "Proven" } else { "Not Proven!" }
A sample test:
== Peggy and Victor agree on some parameters == g=5 h=3 p=57896044618658097711785492504343953926634992332820282019728792003956564819968 == Peggy generates a secret == x=31857242149463499768103924533633689347124421189904537320593524734445751856942 == Peggy sends to Victor == Y=g^x (mod p)=53578546531817708516746852596687213397007373494324885669615596529570345984361 Z=h^x (mod p)=822913354416546808807344079956116960405590984002493643081867279192728236537 == To prove proof of x, Peggy generates a random value == k=1349769193436066493405969671414829042689223901038466129439327313642347954464 == To prove Peggy computes == A=g^k (mod p)=29080741485237225718760451952739791367591139363156140278535793826182956673921 B=h^k (mod p)=53071284176397633759122779827350719845289924471464097195668587838501048365697 == Peggy sends == c=H(Y || Z || A || B)=38766362274769774212305105852358285196 s=-1234989390241167370232048011328550830769624565149439953134550633710963568858870042682478909364169287866373480476168 == Victor computes == A'=g^s*Y^c=29080741485237225718760451952739791367591139363156140278535793826182956673921 B'=h^s*Z^c=53071284176397633759122779827350719845289924471464097195668587838501048365697 c'=H(Y || Z || A' || B')=38766362274769774212305105852358285196 Proven
References
[1] Chaum, David, and Pedersen, Torben Pryds. "Wallet databases with observers." Annual international cryptology conference. Springer, Berlin, Heidelberg, 1992 [paper].