A Bit of RSA and PowerShell, And The Wonder of dP, dQ and InvQ
In RSA, we would hope that many in cybersecurity would know that we generate two prime numbers (p and q), and then compute the modulus:
Then we pick an e value, and compute d from:
and where:
This gives us a private key of (d,N) and a public key of (e,N). We can then encrypt with:
and decrypt with:
But … when we view our key pair, we see three other values: dQ, dP and InvQ. What are these for?
Well, they relate to the Chinese theorem method for faster and less complex decryption. In the method, we do not have to perform the exponent for N, and only have to use exponents for p and q (and which are half the size of N). This makes the computation much faster and requires less complexity in the implementation. To compute the message, rather than computing:
we perform a less complex operation with [here]:
m1=pow(c,dp,p)
m2=pow(c,dq,q)
h=(qinv*(m1-m2))
pm=(m2+h*q) % (N)In PowerShell and with Big Integers, this can be coded with:
$m1=[System.Numerics.BigInteger]::ModPow($C,$DP,$P)
$m2=[System.Numerics.BigInteger]::ModPow($C,$DQ,$Q)
$diff=[System.Numerics.BigInteger]::Subtract($m1,$m2)…
