Photo by Tierra Mallorca on Unsplash

In RSA, we have e, d, N, p and q, but what are dQ, dP 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 the following [here]:

c=pow(M,e,N)
m1=pow(c,dp,p)
m2=pow(c,dq,q)
h=(qinv*(m1-m2)) %p
m=(m2+h*q) % (N)

The following is the full code [here]:

from cose.keys.rsa import RSA
from cose.keys.cosekey import CoseKey
import binascii
from Crypto.Util.number import *