The Windows implementations seem to only be willing to do RSA via the CRT parameters, leaving D as a potentially ignored value. At the very least, the CRT parameters are required inputs.
First, we need to turn your arrays into BigInteger values. I'm assuming here that you have Big-Endian encoded values. If they're Little-Endian, don't call Array.Reverse()
and change the copy-to index from 1 to 0.
private static BigInteger GetBigInteger(byte[] bytes)
{
byte[] signPadded = new byte[bytes.Length + 1];
Buffer.BlockCopy(bytes, 0, signPadded, 1, bytes.Length);
Array.Reverse(signPadded);
return new BigInteger(signPadded);
}
Adding the extra byte prevents numbers from being treated as negative. (One could avoid the allocation and memory copy by testing for the sign bit in the last byte, if one wanted).
So now you have three BigInteger values, n
, e
, d
. Not sure which of n
and d
is which?
// Unless someone tried really hard to make this break it'll work.
if (n < d)
{
BigInteger tmp = n;
n = d;
d = tmp;
}
Now, using the algorithm from NIST Special Publication 800-56B Recommendation for Pair-Wise August 2009 Key Establishment Schemes Using Integer Factorization Cryptography, Appendix C (as shared in https://stackoverflow.com/a/28299742/6535399) we can calculate the BigInteger values. There's a tricky subtlety, though. RSAParameters values have to have a correct amount of padding, and RSACryptoServiceProvider doesn't do it for you.
private static RSAParameters RecoverRSAParameters(BigInteger n, BigInteger e, BigInteger d)
{
using (RandomNumberGenerator rng = RandomNumberGenerator.Create())
{
BigInteger k = d * e - 1;
if (!k.IsEven)
{
throw new InvalidOperationException("d*e - 1 is odd");
}
BigInteger two = 2;
BigInteger t = BigInteger.One;
BigInteger r = k / two;
while (r.IsEven)
{
t++;
r /= two;
}
byte[] rndBuf = n.ToByteArray();
if (rndBuf[rndBuf.Length - 1] == 0)
{
rndBuf = new byte[rndBuf.Length - 1];
}
BigInteger nMinusOne = n - BigInteger.One;
bool cracked = false;
BigInteger y = BigInteger.Zero;
for (int i = 0; i < 100 && !cracked; i++)
{
BigInteger g;
do
{
rng.GetBytes(rndBuf);
g = GetBigInteger(rndBuf);
}
while (g >= n);
y = BigInteger.ModPow(g, r, n);
if (y.IsOne || y == nMinusOne)
{
i--;
continue;
}
for (BigInteger j = BigInteger.One; j < t; j++)
{
BigInteger x = BigInteger.ModPow(y, two, n);
if (x.IsOne)
{
cracked = true;
break;
}
if (x == nMinusOne)
{
break;
}
y = x;
}
}
if (!cracked)
{
throw new InvalidOperationException("Prime factors not found");
}
BigInteger p = BigInteger.GreatestCommonDivisor(y - BigInteger.One, n);
BigInteger q = n / p;
BigInteger dp = d % (p - BigInteger.One);
BigInteger dq = d % (q - BigInteger.One);
BigInteger inverseQ = ModInverse(q, p);
int modLen = rndBuf.Length;
int halfModLen = (modLen + 1) / 2;
return new RSAParameters
{
Modulus = GetBytes(n, modLen),
Exponent = GetBytes(e, -1),
D = GetBytes(d, modLen),
P = GetBytes(p, halfModLen),
Q = GetBytes(q, halfModLen),
DP = GetBytes(dp, halfModLen),
DQ = GetBytes(dq, halfModLen),
InverseQ = GetBytes(inverseQ, halfModLen),
};
}
}
With the "tricky" BigInteger-to-suitable-for-RSAParameters-byte[] method:
private static byte[] GetBytes(BigInteger value, int size)
{
byte[] bytes = value.ToByteArray();
if (size == -1)
{
size = bytes.Length;
}
if (bytes.Length > size + 1)
{
throw new InvalidOperationException($"Cannot squeeze value {value} to {size} bytes from {bytes.Length}.");
}
if (bytes.Length == size + 1 && bytes[bytes.Length - 1] != 0)
{
throw new InvalidOperationException($"Cannot squeeze value {value} to {size} bytes from {bytes.Length}.");
}
Array.Resize(ref bytes, size);
Array.Reverse(bytes);
return bytes;
}
And for computing InverseQ you need ModInverse:
private static BigInteger ModInverse(BigInteger e, BigInteger n)
{
BigInteger r = n;
BigInteger newR = e;
BigInteger t = 0;
BigInteger newT = 1;
while (newR != 0)
{
BigInteger quotient = r / newR;
BigInteger temp;
temp = t;
t = newT;
newT = temp - quotient * newT;
temp = r;
r = newR;
newR = temp - quotient * newR;
}
if (t < 0)
{
t = t + n;
}
return t;
}
On my computer I'm recovering P and Q from (n, e, d) in ~50ms for a 1024-bit key. ~2-4 seconds for a 4096-bit key.
Note to implementers who like unit tests: There's not really a defined order for P and Q (like a convention that P always be the larger), so your P and Q values may be backwards from an RSAParameters structure that you started with. DP and DQ will thus also be reversed.
It depends on the tools you can use. I doubt there is a JavaScript too that could do it directly within the browser. It also depends if it's a one-off (always the same key) or whether you need to script it.
Command-line / OpenSSL
If you want to use something like OpenSSL on a unix command line, you can do something as follows.
I'm assuming you public.key file contains something like this:
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAmBAjFv+29CaiQqYZIw4P
J0q5Qz2gS7kbGleS3ai8Xbhu5n8PLomldxbRz0RpdCuxqd1yvaicqpDKe/TT09sR
mL1h8Sx3Qa3EQmqI0TcEEqk27Ak0DTFxuVrq7c5hHB5fbJ4o7iEq5MYfdSl4pZax
UxdNv4jRElymdap8/iOo3SU1RsaK6y7kox1/tm2cfWZZhMlRFYJnpoXpyNYrp+Yo
CNKxmZJnMsS698kaFjDlyznLlihwMroY0mQvdD7dCeBoVlfPUGPAlamwWyqtIU+9
5xVkSp3kxcNcNb/mePSKQIPafQ1sAmBKPwycA/1I5nLzDVuQa95ZWMn0JkphtFIh
HQIDAQAB
-----END PUBLIC KEY-----
Then, the commands would be:
PUBKEY=`grep -v -- ----- public.key | tr -d '\n'`
Then, you can look into the ASN.1 structure:
echo $PUBKEY | base64 -d | openssl asn1parse -inform DER -i
This should give you something like this:
0:d=0 hl=4 l= 290 cons: SEQUENCE
4:d=1 hl=2 l= 13 cons: SEQUENCE
6:d=2 hl=2 l= 9 prim: OBJECT :rsaEncryption
17:d=2 hl=2 l= 0 prim: NULL
19:d=1 hl=4 l= 271 prim: BIT STRING
The modulus and public exponent are in the last BIT STRING, offset 19, so use -strparse
:
echo $PUBKEY | base64 -d | openssl asn1parse -inform DER -i -strparse 19
This will give you the modulus and the public exponent, in hexadecimal (the two INTEGERs):
0:d=0 hl=4 l= 266 cons: SEQUENCE
4:d=1 hl=4 l= 257 prim: INTEGER :98102316FFB6F426A242A619230E0F274AB9433DA04BB91B1A5792DDA8BC5DB86EE67F0F2E89A57716D1CF4469742BB1A9DD72BDA89CAA90CA7BF4D3D3DB1198BD61F12C7741ADC4426A88D1370412A936EC09340D3171B95AEAEDCE611C1E5F6C9E28EE212AE4C61F752978A596B153174DBF88D1125CA675AA7CFE23A8DD253546C68AEB2EE4A31D7FB66D9C7D665984C951158267A685E9C8D62BA7E62808D2B199926732C4BAF7C91A1630E5CB39CB96287032BA18D2642F743EDD09E0685657CF5063C095A9B05B2AAD214FBDE715644A9DE4C5C35C35BFE678F48A4083DA7D0D6C02604A3F0C9C03FD48E672F30D5B906BDE5958C9F4264A61B452211D
265:d=1 hl=2 l= 3 prim: INTEGER :010001
That's probably fine if it's always the same key, but this is probably not very convenient to put in a script.
Alternatively (and this might be easier to put into a script),
openssl rsa -pubin -inform PEM -text -noout < public.key
will return this:
Modulus (2048 bit):
00:98:10:23:16:ff:b6:f4:26:a2:42:a6:19:23:0e:
0f:27:4a:b9:43:3d:a0:4b:b9:1b:1a:57:92:dd:a8:
bc:5d:b8:6e:e6:7f:0f:2e:89:a5:77:16:d1:cf:44:
69:74:2b:b1:a9:dd:72:bd:a8:9c:aa:90:ca:7b:f4:
d3:d3:db:11:98:bd:61:f1:2c:77:41:ad:c4:42:6a:
88:d1:37:04:12:a9:36:ec:09:34:0d:31:71:b9:5a:
ea:ed:ce:61:1c:1e:5f:6c:9e:28:ee:21:2a:e4:c6:
1f:75:29:78:a5:96:b1:53:17:4d:bf:88:d1:12:5c:
a6:75:aa:7c:fe:23:a8:dd:25:35:46:c6:8a:eb:2e:
e4:a3:1d:7f:b6:6d:9c:7d:66:59:84:c9:51:15:82:
67:a6:85:e9:c8:d6:2b:a7:e6:28:08:d2:b1:99:92:
67:32:c4:ba:f7:c9:1a:16:30:e5:cb:39:cb:96:28:
70:32:ba:18:d2:64:2f:74:3e:dd:09:e0:68:56:57:
cf:50:63:c0:95:a9:b0:5b:2a:ad:21:4f:bd:e7:15:
64:4a:9d:e4:c5:c3:5c:35:bf:e6:78:f4:8a:40:83:
da:7d:0d:6c:02:60:4a:3f:0c:9c:03:fd:48:e6:72:
f3:0d:5b:90:6b:de:59:58:c9:f4:26:4a:61:b4:52:
21:1d
Exponent: 65537 (0x10001)
Java
It depends on the input format. If it's an X.509 certificate in a keystore, use (RSAPublicKey)cert.getPublicKey()
: this object has two getters for the modulus and the exponent.
If it's in the format as above, you might want to use BouncyCastle and its PEMReader
to read it. I haven't tried the following code, but this would look more or less like this:
PEMReader pemReader = new PEMReader(new FileReader("file.pem"));
Object obj = pemReader.readObject();
pemReader.close();
if (obj instanceof X509Certificate) {
// Just in case your file contains in fact an X.509 certificate,
// useless otherwise.
obj = ((X509Certificate)obj).getPublicKey();
}
if (obj instanceof RSAPublicKey) {
// ... use the getters to get the BigIntegers.
}
(You can use BouncyCastle similarly in C# too.)
Best Answer
Using RSACryptoServiceProvider
So what you need are the RSAParameters but all you need to set are the Modulus and the Exponent to encrypt.