A Bit of RSA and PowerShell, And The Wonder of dP, dQ and InvQ

And a Bit of PowerShell
Photo by Markus Winkler on Unsplash

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)
$h=[System.Numerics.BigInteger]::Multiply($InvQ,$diff)
$hq=[System.Numerics.BigInteger]::Multiply($h,$q)
$mre=[System.Numerics.BigInteger]::Add($m2,$hq)

The following is the full code [here]:

Notice that we now only have multiplication and a modulus of N, rather than an exponential function. This makes the computation much less complex. A sample run gives [here]:

Size: 512
Checking first for encryption and decryption with e, d and N
Message: 12
Cipher: 7707857329360675738733873803223011532082095654740491313628835887921337858864909577989586789241353533892581459049936475635712898847094527528622705830201169
Decipher: 12
== Now with dp, dq, p and q == 
Recovered: 12

The value of dQ is:

and dP is:

and InverseQ is:

And there you go. A simpler decryption process. This is especially useful in IoT applications. The full test code is here:

https://asecuritysite.com/powershell/enc10

If you are interested in this area, have a look at the PowerShell programming for cryptography:

https://asecuritysite.com/powershell/

Subscribe: https://billatnapier.medium.com/membership