So What Are dmp1, dmq1 and iqmp With RSA Private Keys?

So What Are dmp1, dmq1 and iqmp With RSA Private Keys?

Say Hello To CRT (Chinese Remainder Theory)

When we generate RSA keys, we get [here]:

== Key details ==
Private key p: 97788552682700715869209516738447253059821264202285988392725653463112813905637 (0xd8325c02c662c0f7886e772e47d69a84030a3263674cbff9b71e1ae1404c06e5)
Private key q: 89430188045794288724766615735736599551962340376375285931735688894611227625447 (0xc5b7b15390e0b5e9ebcaae3dc8e1b066846c90b33673c851c57fb1200ae347e7)
Private key d: 3132767790358445840053354932093026005644087509224832928379992249992497549214608795337704299032146651892487311151094108718957093537118048325035899043953849 (0x3bd0a6657945d485356fd3fde515ffe7073bef4ced0e09f0898c489a8852a8cc17e0844ee9c8abc8f600fa549d917b66d6429cd6770433a33c0a0665d743bcb9)
Private key dmp1: 55297675548482361568471316818390454222759297058710632617214897193081173739153 (0x7a41600ea1a8ce7e2bc46bd8dbfedb39b38e5c98219e2121510fd11b77848691)
Private key dmq1: 38273615122883839817999817479529733497618745485398691118197699042007655407457 (0x549e19363a7af15ffb99f2985eb0b85e27ae8eff23fec96cb5a9c09486145f61)
Private key iqmp: 3254889311453785871164802372720912857961901766416447785355975574380097527106 (0x73233ba89dbe0263eeb22021e10dcbd860893eb5ac746bf13e3972e40fb5d42)
Public key N: 8745248655139986583446638079166019735566578484988195920570752314510299948157013756204932892741519270040466725953785468620308568806892742344098905437944739 (0xa6f9e28f4cf1a89a40697b5b71b83d1e6ca92ccb15da105cdaf7929862faf6ab676bd90e4ee26eed6cb2d7794d50eb6e45665492fff69ff376bde7652992bba3)
Public key e: 65537 (0x10001)

So, hopefully, you know that p and q are the prime numbers for the private key, and N is p.q. e is then the public exponent, and d is the private exponent. But what are dmp1, dmq1 and iqmp?

Overall, we have a public key of (e,N), but there are two possible forms of private keys in RSA: (d,N) and (p, q, dP, dQ, qInv).

Overall dmp1 is typically known as dP, dmq1 is typically known as dQ and iqmp as qInv. These are used simplify the operation with CRT (Chinese Remainder Theory).

With RSA, we create two random prime numbers (p and q ), and determine the modulus:

N=p.q

We encrypt a message with:

C=M^e (modN)

and decrypt with:

M=C^d (modN)

and where (e,N) is the encryption key, and (d,N) is the decryption key. In order to perform the decrypt, we can apply CRT (Chinese Remainder Theory) to solve:

M=C^d (modN)

For this we use CRT to solve for M in:

Mp=M (mod p)

Mq=M (mod q)

and also use Fermat’s Little Theorem:

Mp=M(mod p)=C^d (mod p)=C^d (mod p−1)(mod p)

Mq=M(mod q)=C^d (mod q)=C^d (mod q−1)(mod q)

For this we need:

dP=e^{−1}(mod p−1)

and which is the inverse of e (modp−1). Also:

dQ=e^{−1} (mod q−1)

and:

qInv=q^{−1} (mod p)

The message is then recovered using less complex operations of:

m1=c^{dP} (mod p)

m2=c^{dQ} (modq )

h=qInv.(m1−m2)(mod p)

mrec=m2+h.q

This operation can be up to four times faster than performing:

M=C^d (mod N)

From the example above, now let’s compute inverse q (mod p) :

>>> pow(q,-1,p)
22912084429352545549895539516123883932010399068618835358126059575529436969916

And then dP and dQ:

>>> pow(e,-1,p-1)
42094444337807335610151571139231770555782681936205452762937671608765740719301
>>> pow(e,-1,q-1)
22116830200221211843789030615620095090924232798420504696801798026445237049317

And that works. From RFC8017 [here], the definition of the private key parameters are:

p      the first factor, a positive integer
q      the second factor, a positive integer
dP     the first factor's CRT exponent, a positive integer
dQ     the second factor's CRT exponent, a positive integer
qInv   the (first) CRT coefficient, a positive integer

and:

In a valid RSA private key with the second representation, the two
   factors p and q are the first two prime factors of the RSA modulus n
   (i.e., r_1 and r_2); the CRT exponents dP and dQ are positive
   integers less than p and q, respectively, satisfying

e * dP == 1 (mod (p-1))
e * dQ == 1 (mod (q-1)) ,

and the CRT coefficient qInv is a positive integer less than p
   satisfying

q * qInv == 1 (mod p).