如何在C#中使用模数D来创建私有RSA密钥? [英] How to create private RSA key using modulus, D, exponent in C#?
问题描述
我有3个字节数组，分别为长度128、128、3个字节.我不知道它是什么，但我希望它们是 Modulus ， D ， Exponent .现在如何在C#中使用这些数组使用RSA解密字节数组?当我创建一个 RSAParameters 并将3个字节的数组分配给 Modulus ， D ， Exponent 并尝试使用 RSACryptoServiceProvider.ImportParameters 中的RSAParameter，解密失败，说明密钥已损坏.我想其他条目也需要填写 DQ ， DP ，...等等...
I have 3 byte arrays of length 128, 128, 3 bytes respectively. I don't know what it is, but I expect them to be Modulus, D, Exponent.
Now how can I use these arrays in C# to decrypt a byte array using RSA?
When I create an RSAParameters and assign the 3 byte arrays to Modulus, D, Exponent and try to use that RSAParameters in RSACryptoServiceProvider.ImportParameters, decryption fails stating corrupt keys. I guess the other entries also need to be filled DQ,DP,...etc...
我该如何在C#中做到这一点?我没有这些值，是否有一种简便的方法可以像其他语言一样仅使用C#中的Modulus，D，Exponent来解密字节数组?
How do I do that in C#? I don't have that values, is there an easy way to decrypt a byte array using only Modulus, D, Exponent in C#, as in other languages?
推荐答案
Windows实现似乎只愿意通过CRT参数执行RSA，而D则可能会被忽略.至少，CRT参数是必需的输入.
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.
首先，我们需要将您的数组转换为BigInteger值.我在这里假设您具有Big-Endian编码值.如果它们是Little-Endian，请不要调用 Array.Reverse()并将复制到索引从1更改为0.
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).
因此，现在您有了三个BigInteger值，分别为 n ， e 和 d .不确定 n 和 d 中的哪个?
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),
};
}
}
使用适用于RSAParameters-byte []的棘手" BigInteger方法:
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;
}
要计算InverseQ，您需要ModInverse:
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;
}
在我的计算机上，我将在约50毫秒内从(n，e，d)中恢复一个1024位密钥的P和Q.4096位密钥大约需要2-4秒.
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.
喜欢单元测试的实现者的注意事项:P和Q确实没有定义的顺序(就像约定，P总是更大)，因此您的P和Q值可能会从您开始时使用的RSAParameters结构向后.因此，DP和DQ也将相反.
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.
这篇关于如何在C#中使用模数D来创建私有RSA密钥?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
