Step-by-Step RSA Decryption using dQ, dP and Qinv

In this case we will generate an RSA key pair. With this we have two prime numbers (p and q), and compute the modulus (N):
Photo by Clayton Robbins on Unsplash

Step-by-Step RSA Decryption using dQ, dP and Qinv

In this case we will generate an RSA key pair. With this we have two prime numbers (p and q), and compute the modulus (N):

N=pq

We then pick an encryption key value (e=0x010001) and then compute:

d=e^{−1} (modϕ)

and where:

ϕ=(p−1)(q−1)

The public key is then (e,N) and the private key is (d,N). To encrypt a message (M), we create a cipher:

c=M^e (mod N)

and then decrypt with:

M=c^d (mod N)

The key pair thus contains e,N,d,p and q for a key pair of (e,N) and (d,N). It also has the values of dQ, dP and InvQ, and which make the computation easier. The value of dQ is:

dQ=d (mod q−1)

and dP is:

dP=d (mod p−1)

and we also have:

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

We can use the values of dQ, dP and InvQ to reduce the computational resource for the decrpytion. This uses Chinese remainder theory with:

c=M^e (mod N)

To decrypt, we use less complex exponents:

m1=c^{dQ} (mod q)

m2=c^{dP} (mod p)

and then compute:

h=InvQ×(m1−m2)(modp)

The recovered message (m) is then:

m=m2+h×q (modN)

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:

The following is the full code [here]:

from Crypto.Util.number import *
from Crypto import Random
import Crypto
import libnum
import sys

bits=60
msg="Hello"

if (len(sys.argv)>1):
        msg=str(sys.argv[1])
if (len(sys.argv)>2):
        bits=int(sys.argv[2])

p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
q = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)

n = p*q
PHI=(p-1)*(q-1)

e=65537
d=libnum.invmod(e,PHI)
## d=(gmpy2.invert(e, PHI))

m=  bytes_to_long(msg.encode('utf-8'))

c=pow(m,e, n)
res=pow(c,d ,n)

print ("Message=%s\np=%s\nq=%s\n\nd=%d\ne=%d\nN=%s\n\nPrivate key (d,n)\nPublic key (e,n)\n\ncipher=%s\ndecipher=%s" % (msg,p,q,d,e,n,c,(long_to_bytes(res))))

print ("\n=== Now using dQ, dP and qInv===")
dQ = d % (q-1)
dP = d % (p-1)
qinv = libnum.invmod(q,p)

print (f"\ndQ: {dQ}")
print (f"dP: {dP}")
print (f"Invq: {qinv}")

m1=pow(c,dP,p)
m2=pow(c,dQ,q)

h=(qinv*(m1-m2)) % p

m=(m2+h*q) % n

print ("\nc=%d\nm1=%d\nm2=%d\n\nh=%d\nm=%d\ndecipher=%s" % (c,m1,m2,h,m,(long_to_bytes(m))))

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

Message=hello
p=673297723066793093
q=753603682491344171

d=328973225088815271044202413406807993
e=65537
N=507399643516172518393409455908610903

Private key (d,n)
Public key (e,n)

cipher=354025656853872658534799133367521160
decipher=b'hello'

=== Now using dQ, dP and qInv===

dQ: 190444850838787893
dP: 347924083943116329
Invq: 242736753289875350

Message=hello
p=673297723066793093
q=753603682491344171

d=328973225088815271044202413406807993
e=65537
N=507399643516172518393409455908610903

Private key (d,n)
Public key (e,n)

cipher=354025656853872658534799133367521160
decipher=b'hello'

Notice that Dq, Dq and Qinv are much smaller than d and N. Thus we have less complex computation.

Simple example

Let’s take a simple example for 60-bit prime numbers (and which will give a 120-bit modulus) [here]:

Message=hello
p=673297723066793093
q=753603682491344171

d=328973225088815271044202413406807993
e=65537
N=507399643516172518393409455908610903

Private key (d,n)
Public key (e,n)

cipher=354025656853872658534799133367521160
decipher=b'hello'

=== Now using dQ, dP and qInv===


dQ: 190444850838787893
dP: 347924083943116329
Invq: 242736753289875350

Message=hello
p=673297723066793093
q=753603682491344171

d=328973225088815271044202413406807993
e=65537
N=507399643516172518393409455908610903

Private key (d,n)
Public key (e,n)

cipher=354025656853872658534799133367521160
decipher=b'hello'

Now we have two random 60-bit prime numbers of p=673297723066793093
q=753603682491344171, we can then compute the modulus (N):

N=673297723066793093 x 753603682491344171 = 507399643516172518393409455908610903

and then PHI:

PHI=673297723066793092 x 753603682491344171 = 507399643516172516966508050350473640

If we then compute with Python, we get:

>>> p=673297723066793093
>>> q=753603682491344171
>>> N=p*q
>>> PHI=(p-1)*(q-1)
>>> print (N)
507399643516172518393409455908610903
>>> print (PHI)
507399643516172516966508050350473640

Normally we select e as 65537, and compute d with:

d=e^{-1} (mod PHI) = 63537^{-1} (mod 507399643516172516966508050350473640) = 328973225088815271044202413406807993

in Python we get:

>>> e=65537
>>> d=pow(e,-1,PHI)
>>> print (d)
328973225088815271044202413406807993

So, now we have a public key of (e,N) and a private key of (d,N). Now we compute dQ, dP, Invq. First, qQ:

dQ=d (mod q−1) = 328973225088815271044202413406807993 (mod q-1) = 190444850838787893

and dP is:

dP=d (mod p−1) = 328973225088815271044202413406807993 (mod p-1) = 347924083943116329

For this we have:

>>> dP=d % (p-1)
>>> dQ=d % (q-1)
>>> print (dP)
347924083943116329
>>> print (dQ)
190444850838787893

and we also have:

InvQ=q^{−1} (mod p) = 753603682491344171^{-1} (mod 673297723066793093) = 242736753289875350

In Python:

>>> qinv=pow(q,-1,p)
>>> print (qinv)
242736753289875350

Notice the dQ, dP and invQ are much smaller in length than d. In fact, they are 60 bits values, as apposed to N which is a 120-bit value. If we contrain our decryption to 60 bit values, it will require much less computation.

Now we have a message of “hello” and which can be convered into bytes and then into an integer. This gives m=448,378,203,247. The cipher is then:

c=m^e (mod N) = 448378203247⁶⁵⁵³⁵ (mod 507399643516172518393409455908610903) = 354025656853872658534799133367521160

In Python:

>>> m=448378203247
>>> c=pow(m,e,N)
>>> print (c)
354025656853872658534799133367521160

Normally, we would use M^d (mod N) for the decryption, but can simply it by using dQ, dP and InvQ.

>>> m1=pow(c,dP,p)
>>> m2=pow(c,dQ,q)
>>> h=(qinv*(m1-m2)) % p
>>> m=(m2+h*q) % n
>>> m=(m2+h*q) % N
>>> print (m1)
448378203247
>>> print (m2)
448378203247
>>> print (h)
0
>>> print (m)
448378203247

And you can see we are back with a message integer value of 448,378,203,247, and is simply converted back into a string:

>>> from Crypto.Util.number import *
>>> (long_to_bytes(m))
b'hello'

Conclusions

And, so, for decryption, the dQ, dP and InvQ values significantly simply the decryption. So, that’s why your private key contains these values.

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