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.
RSA Key Pair Generation with dP, dQ and InvQ with 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:
$size=[int]$Args[0] $rsa1=[System.Security.Cryptography.RSA]::Create($size) "`nSize: "+$Args[0] $a=$rsa1.ExportParameters($true) # Set $false for only public parameters "`n== RSA Parameters ==" "E: "+[System.Convert]::ToHexString($a.Exponent) [Convert]::ToUInt64([System.Convert]::ToHexString($a.Exponent)) "Modulus: "+[System.Convert]::ToHexString($a.Modulus) "D: "+[System.Convert]::ToHexString($a.D) "P: "+[System.Convert]::ToHexString($a.P) "Q: "+[System.Convert]::ToHexString($a.Q) "DP: "+[System.Convert]::ToHexString($a.DP) "DQ: "+[System.Convert]::ToHexString($a.DQ) "InvQ: "+[System.Convert]::ToHexString($a.InverseQ) "`n=== As integer values === " "E: "+ [System.Numerics.BigInteger]::Parse("0"+[System.Convert]::ToHexString($a.Exponent),'AllowHexSpecifier') "P: "+ [System.Numerics.BigInteger]::Parse("0"+[System.Convert]::ToHexString($a.P),'AllowHexSpecifier') "Q: "+ [System.Numerics.BigInteger]::Parse("0"+[System.Convert]::ToHexString($a.Modulus),'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.InverseQ),'AllowHexSpecifier')
A sample run for a 512 bit RSA key pair:
Size: 512 == RSA Parameters == E: 010001 10001 Modulus: D0DD81E2D73EA7ACF4309C7D9AB8CDFBE1645C8D39765456804FE42E9381848C7FD1E517EB3FE41D6C525B6D4F4A5BD4668BF02846F8EF7E690D7D1D9D47E3C5 D: A748E260D6D8BDDF4E6D28C989047F26402DEBDAC8AD377B58A5A43291BDE8745438B4FAF55BF4A8A282D8FAAEF47C5E3FE577807EB46698387DA081CEBA1979 P: F68947FBBDD165CE065D6DD72008B125671109223E38BF23179828E8160815FB Q: D8E208431362227B19EF4AE862467598F13D831EEF8D197FDF2DAB602FF5813F DP: E4572A50C3F2DA3404392CAEFF808D72730F98421B173C11289D49E60BE1D959 DQ: B39D05E09EF5DFBE792CFEA953722CC3DBCDE8803F3D6887C8C9A6AB032CDBBB InvQ: D17ABFACCA8FE81F42AC8048EF880651356D213B48F58B88D378A572803B21A3 === As integer values === E: 65537 P: 111511515610285570110288988741159826219781468926911537450061927922015161292283 Q: 10939161451613989132661698575733202328050634655939873074438778711643318881414357841464314020933362738846984001445168539674331107786653321926453092386595781 DP: 103281337222398555101614990258760722210976016049918829412679235010243378403673 DQ: 81241435450075166033704233417511035332801234263944646871680012683031599700923 InvQ: 94750263587800984516651400822953488495882394699955557099317857846228816699811
A sample run for a 1,024 bit RSA key pair:
Size: 1024 == RSA Parameters == E: 010001 10001 Modulus: CE716E5375143EBAFFDD45D2F1028F004AEA6B429AF367EA86B90D730BEB9F9287759A0541164FC352E9E31F8EA55AE388863FA01B4D36E3BB4C1D1A8D58054567CDF9466C7B8BF671DCAA68F24CA45AF70219D7874B8FF100C69E30ECF13A2485933D7EBE4CD5E43F62F7D159D101C31C6F087B7C720BCAE40869F8B002B081 D: BA7F44A0C6830C8C98BB07EA216A234FAB5E0C99F62B70343193197056537D2BBD8DE31F5E064EF6707FF47BBCBCEAD7E4AD0AEB93DE7478D4EA54DC78D60CA35F6AE3D62A63563954BF39C722AEDEDE6111CDDD3C4CA50DDB52758A08D069E804CE77DE107BB66A691051779728E8C5F17BA4DD362D481E748D5734323589A5 P: D6D24460E1D0716EB17598DACD76EF72C9C6C8C85DF09563B341CE9E27CF9D0DD1DF8C52331F9E9544DF077A9EA5B8D2CEBF1BA342698C88E3EC0D0BA19CFF0B Q: F604065B0044ED036E0E02923829B15F8917EAAAEE74766D495DCE1454E58CFC00B48847AF029F04A4B0B727A2DCA8888DA3EDD3A910E5B3C2CA0EB75AEEB623 DP: 727834EB9328A9691CB2D732B08D91E68ED29826FCB7B8431A4014C37DDF498715B0936B31C6C59030D4CF7D6D904D3E37E0E9EF42F24F6A9A592C526859EA25 DQ: 627C61FEF430A3A187E15BEE2545AB984F4D9FC82605C1932697C2F428B86CA445B4000A92693E37A1A68CEBF52AD8DD31B6BA72CD6FD2451069CB5263B8C479 InvQ: 3794CDC2DC02A8668A55D59E242F8C8052F96EA2C72127F95F7B0399FAD1A2138A8A94E163B3B5B13F3F23614075335247CB13E31EFDA01E98DE98D696970052