In this case we generate an RSA key pair. With this we have two prime numbers (\(p\) and \(q\)), and compute the modulus (\(N=pq\)). We then pick an encryption key value (\(e=0x010001\)) and then 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 then decrypt with \(M=c^d \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.
COSE and CBOR - RSA Keys: What are dQ, dP and InvQ? |
Outline
In this case we will generate an RSA key pair and encode the key pair into the CBOR representation. 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} \pmod \phi\))
and where:
\(\phi=(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\) and \(q\) for a key pair of \((e,N)\) and \((d,N)\). It also has the values of \(dQ\), \(dP\) and \(InvQ\). The value of \(dQ\) is:
\(dQ = d \pmod {p-1}\)
and \(dP\) is:
\(dP = d \pmod {q-1}\)
and we also have:
\(InvQ = q^{-1} \pmod 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 \pmod N\)
To decrypt, we use less complex exponents:
\(m_1=c^{dQ} \pmod {q}\)
\(m_2=c^{dP} \pmod {p}\)
and then compute:
\(h=InvQ \times (m_1-m_2) \pmod p\)
The recovered message (\(m\)) is then:
\(m=m_2+h \times q \pmod N\)
The code is:
from cose.keys.rsa import RSA from cose.keys.cosekey import CoseKey import binascii from Crypto.Util.number import * import sys size=512 msg='hello' if (len(sys.argv)>1): size=int(sys.argv[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())
These values are used with a Chinese remainder algorithm in order to optimize the processing of the decryption. The following is a test run with 512-bit keys:
e= b'010001' n= b'ce08f9ba53f5bc63616228e304383fda71c14ff7d078873b4fea375206e1a4530638d324abc1218f93abcd97391b8952b911afab8d5ff2384ed993107cd4dcd9' d= b'6df116291a42479b944c87dad3d69c24198d78f998d1a7ffbb5e14d4fd7d0c6c980ba2ceafbdccf3e873bb97f70881c499a58a24fadf19449deb85f5d4d396f1' p= b'e66ef97a40114062b25e1ad3009b64120ef9855423ac39185987146281205dfd' q= b'e4e50284aa63bc4c2a1027e13287f1721881983933a2237ddae50e74bf38a30d' dp= b'c8f0cad2251e26142ad04ef9e2d49e5df4faf79e18816d4463859c6c0d87e90d' dq= b'5a4fc97892ca1b4769e949f2debf2892bdfc94152dbc3188bccf57aed4ac0219' qinv= b'074884f1cd78223a419374099e175b8e22ab5e44061def48ee1ccff80e913fd1' c: 166659603275943007449706906716436414404395497926806430319568854757211101101880965132461124265039138578464845393225653242907515760825306369305390655527891 m1: 448378203247, m2: 448378203247, h: 0, m: 448378203247 Decrypted: hello
References
[1] Bormann, C., & Hoffman, P. (2020). RFC 8949 Concise Binary Object Representation (CBOR). [here].
[2] Schaad, J. (2017), RFC 8152 – CBOR Object Signing and Encryption (COSE), 2017. [here]