February 13, 2023

In this case we generate an RSA key pair. With this we have two prime numbers ($p$ ans $q$), and compute the modulus ($N = pq$). We then pick ans encryption key value ($e = 0x010001$) and than compute $d = e^-1\pmod \phi$, and where $\phi = (p-1)(q-1)$. To encrypt a message($M$), we create a cipher $c = M^e\pmod N$, and than decrypt with $M = cd\pmod N$. The key pair also includes $dQ$, $dP$ and $invQ$, and these can be used with the Chinese remainder theory to optimize the decryption process.

New two prime numbers $p$ and $q$

compute the modules

$$N = p * q$$

then pick an encryption exponent $e$ such that $1 < e < \varphi (N)$ and then compute:

$$ d = e^{-1} \pmod {\varphi (N)} $$

and where:

$$ \varphi (N) = (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 \pmod N $$

and then decrypt with:

$$ M = C^d \pmod N $$

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

$$dQ = d \pmod {q-1}$$

and $dP$ is:

$$dP = d \pmod {p-1}$$

and $InvQ$ is:

$$InvQ = q^{-1} \pmod p$$

We can use the values of $dQ$, $dP$ and $InvQ$ to speed up the decryption process. The decryption process is:

$$ c = M^d \pmod N $$

To decrypt, we use less complex exponents:

$$ m_1 = c^dP \pmod p $$

$$ m_2 = c^dQ \pmod q $$

and then we use the Chinese Remainder Theorem to combine the two values:

$$ h = InvQ (m_1 - m_2) \pmod p $$

The recovered message($m$) is then:

$$ m = m_2 + h \times q \pmod N $$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
from cose.keys.rsa import RSA
from cose.keys.cosekey import CoseKey
import binascii
import Crypto.Util.number

import sys

size=512 # 512-bit keys
msg='hello'
if (len(sys.argv)>1):
	size=int(sys.argv[1]) # ValueError: invalid literal for int() with base 10: '--ip=127.0.0.1'

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

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

cose_key= RSA.generate_key(size)

print ("\ne=",binascii.hexlify(cose_key.e))
print ("n=",binascii.hexlify(cose_key.n))
print ("d=",binascii.hexlify(cose_key.d))
print ("p=",binascii.hexlify(cose_key.p))
print ("q=",binascii.hexlify(cose_key.q))
print ("dp=",binascii.hexlify(cose_key.dp))
print ("dq=",binascii.hexlify(cose_key.dq))
print ("qinv=",binascii.hexlify(cose_key.qinv))

e=int.from_bytes(cose_key.e,byteorder='big')
d=int.from_bytes(cose_key.d,byteorder='big')
p=int.from_bytes(cose_key.p,byteorder='big')
q=int.from_bytes(cose_key.q,byteorder='big')
N=int.from_bytes(cose_key.n,byteorder='big')
dq=int.from_bytes(cose_key.dq,byteorder='big')
dp=int.from_bytes(cose_key.dp,byteorder='big')
qinv=int.from_bytes(cose_key.qinv,byteorder='big')

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)

res=long_to_bytes(m)

print (f"\nc: {c} m1: {m1}, m2: {m2}, h: {h}, m: {m}")

print ("Decrypted: ",res.decode())

#math #crypto

RSA {1} RSA Keys: What are dQ, dP and InvQ?

Chinese remainder theory