So What Are dQ, dP, and InvQ Used For In RSA?
If you look at a private key in RSA, you will see p and q — the core prime numbers, and the modulus N (and which is p times q). But you will also see dQ, dP and InvQ. Overall, they make the decryption process faster and use Chinese Remainer Theorem.
Chinese Remainder Theorem (CRT) and RSA
With the Chinese Remainder Theorem (CRT), we can solve:
x (mod 16) = 7
x (mod 14) = 13
x (mod 12) = 7
and which gives a solution of x=55. Overall, CRT is used in many examples of cracking ciphers, but it can also be used to enhance performance. With RSA, we create two random prime numbers (p and q), and determine the modulus:
We then encrypt a message with:
and decrypt with:
and where (e,N) is the encryption key, and (d,N) is the decryption key. Unfortunately, C^d is a fairly complex operation, so can we simplify it?
dP, dQ and InvQ
In order to perform the decrypt, we can apply CRT (Chinese Remainder Theory) to solve:
For this we need:
and which is the inverse of e mod (p-1). Also:
