LOV3

Chinese remainder theory

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$

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())