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.
Using dP, dQ and InvQ with RSA in PowerShell |
Method
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 coding is:
$M=[System.Numerics.BigInteger]$Args[0] $size=[int]$Args[1] $rsa1=[System.Security.Cryptography.RSA]::Create($size) "`nSize: "+$Args[1] $a=$rsa1.ExportParameters($true) # Set $false for only public parameters # Some test parameters, if required # $e=[System.Numerics.BigInteger]::Parse("010001",'AllowHexSpecifier') # $N= [System.Numerics.BigInteger]::Parse("0EA58640C04712FDC57E18853212851A24D2965250EC09995D3757888DCCB56F94CE7828B58225B2CECF7684C7556813DBDCCB665DF2EB35142BD8F50302D09BD",'AllowHexSpecifier') # $D= [System.Numerics.BigInteger]::Parse("07AD3E56C5F0FAC544343949E6DACA24CFD408B2107406FBF95DBE65765D2B63C680D2B01A49946935EFCFDC3F184648D5813D8DC5A4B350730AA0AB830C9D549",'AllowHexSpecifier') # $P= [System.Numerics.BigInteger]::Parse("0F6714B7B2A93D7ECD5066CF4CFD40DF88BAD4DDF36B6FE8629235C58AF87779F",'AllowHexSpecifier') # $Q= [System.Numerics.BigInteger]::Parse("0F36EFE354026DA15962C1EEA20893F221A940563884A4797F26FCC408715F123",'AllowHexSpecifier') # $DP= [System.Numerics.BigInteger]::Parse("0EF8DB79A950BBB73BAAB1154738524C37A3ACF1C701A37957FFDA07190C674EF",'AllowHexSpecifier') # $DQ= [System.Numerics.BigInteger]::Parse("03CED93DC9A20DF46B5DE77225C605D97D89521C026B588B3C42F2D2D1D626587",'AllowHexSpecifier') # $InvQ=[System.Numerics.BigInteger]::Parse("01CC8EC94F9E38060455E717E70B638E82CDD03B762B906871AF82649E305ED19",'AllowHexSpecifier') $E=[System.Numerics.BigInteger]::Parse("0"+[System.Convert]::ToHexString($a.Exponent),'AllowHexSpecifier') $D=[System.Numerics.BigInteger]::Parse("0"+[System.Convert]::ToHexString($a.D),'AllowHexSpecifier') $N=[System.Numerics.BigInteger]::Parse("0"+[System.Convert]::ToHexString($a.Modulus),'AllowHexSpecifier') $P=[System.Numerics.BigInteger]::Parse("0"+[System.Convert]::ToHexString($a.P),'AllowHexSpecifier') $Q=[System.Numerics.BigInteger]::Parse("0"+[System.Convert]::ToHexString($a.Q),'AllowHexSpecifier') $DP=[System.Numerics.BigInteger]::Parse("0"+[System.Convert]::ToHexString($a.DP),'AllowHexSpecifier') $DQ=[System.Numerics.BigInteger]::Parse("0"+[System.Convert]::ToHexString($a.DQ),'AllowHexSpecifier') $InvQ=[System.Numerics.BigInteger]::Parse("0"+[System.Convert]::ToHexString($a.P),'AllowHexSpecifier') "`nChecking first for encryption and decryption with e, d and N" "Message: "+$M $C=[System.Numerics.BigInteger]::ModPow($M,$E,$N) "Cipher: "+$C $Plain=[System.Numerics.BigInteger]::ModPow($C,$D,$N) "Decipher: "+$Plain "`n== Now with dp, dq, p and q == " $m1=[System.Numerics.BigInteger]::ModPow($C,$DP,$P) $m2=[System.Numerics.BigInteger]::ModPow($C,$DQ,$Q) $diff=[System.Numerics.BigInteger]::Subtract($m1,$m2) $h=[System.Numerics.BigInteger]::Multiply($InvQ,$diff) $hq=[System.Numerics.BigInteger]::Multiply($h,$q) $mre=[System.Numerics.BigInteger]::Add($m2,$hq) $mre=$mre % $N "Recovered: "+$mre # Computation # m1=pow(c,dp,p) # m2=pow(c,dq,q) # h=(qinv*(m1-m2)) # %pm=(m2+h*q) % (N)
A sample run for a 512 bit RSA key pair:
Size: 512 Checking first for encryption and decryption with e, d and N Message: 12 Cipher: 1010754950130020917232809240656130663598064052331643708399389556441143747982242933751041295339251995825875521367015058283033570812223228962622474985784075 Decipher: 12 == Now with dp, dq, p and q == Recovered: 12
A sample run for a 1,024 bit RSA key pair:
Size: 1024 Checking first for encryption and decryption with e, d and N Message: 12 Cipher: 15497415323177534354672318994408340493703280527328797915476129879046837253876656713946387529539732833672204286273550487224280790654754390982096209844773563101592079226147661719763505684312773275403360584158752657095453085772313809140156139426534453255643350060960491952753552990161514331011868694737622410194 Decipher: 12 == Now with dp, dq, p and q == Recovered: 12