如何在C#中使用模数D指数创建专用RSA密钥?
我有3个字节的数组长度分别为128,128,3个字节。我不知道它是什么,但我希望它们是Modulus
,D
,Exponent
。 现在我该如何在C#中使用这些数组来解密使用RSA的字节数组? 当我创建一个RSAParameters
并将3个字节的数组分配到Modulus
,D
,Exponent
并尝试使用RSACryptoServiceProvider.ImportParameters
中的RSAParameters时,解密将失败,说明损坏的密钥。我猜其他条目也需要填写DQ
,DP
,...等...如何在C#中使用模数D指数创建专用RSA密钥?
我该怎么做在C#中?我没有这些值,是否有一种简单的方法来解密一个字节数组,只使用Modulus,D,C#中的Exponent,就像其他语言一样?
当你只有Mod,D和指数时,你没有足够的空间。 (你可能有足够的)P和Q很难从mod中计算出来。我不知道该怎么做,并且几乎肯定会有更多的素数,而不是最终以相同的模数乘以最后的数。
您需要至少P,Q和公共指数。
P, Q and D are the building blocks
DP = D mod (p - 1)
DQ = D mod (q - 1)
InverseQ = Q^-1 mod p
Modulus = P * Q
so now we have
P Q and D.
and we can calulate DP, DQ, InverseQ and Modulus and Exponent (see below)
long gcd(long a, long b)
{
long temp;
while (b != 0)
{
temp = b;
b = a % b;
a = temp;
}
return a;
}
Exponent = gcd(1, (P - 1)*(Q - 1));
Windows的实现似乎只愿意通过CRT参数进行RSA,将D作为潜在的忽略值。至少,CRT参数是必需的输入。
首先,我们需要将您的数组变成BigInteger值。我假设你有Big-Endian编码值。如果他们是小端,不叫Array.Reverse()
和复制到指数从1更改为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);
}
添加额外的字节数阻止被视为负。 (如果需要,可以通过测试最后一个字节中的符号位来避免分配和内存复制)。
所以现在你有三个BigInteger值,n
,e
, d
。不知道哪个是n
和d
是哪个?现在
// Unless someone tried really hard to make this break it'll work.
if (n < d)
{
BigInteger tmp = n;
n = d;
d = tmp;
}
,使用从NIST Special Publication 800-56B Recommendation for Pair-Wise August 2009 Key Establishment Schemes Using Integer Factorization Cryptography, Appendix C算法(如在https://*.com/a/28299742/6535399共享),我们可以计算出的BigInteger值。虽然有一个棘手的微妙之处。 RSAParameters值必须具有正确的填充量,并且RSACryptoServiceProvider不会为您执行此操作。
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),
};
}
}
随着 “棘手” 的BigInteger到合适的换RSAParameters字节[]方法:
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:
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;
}
在我的电脑我正在从(n,e,d)在〜50ms内为1024位密钥恢复P和Q.对于4096位密钥〜2-4秒。
对于喜欢单元测试的实现者的注意事项:对于P和Q并没有真正的定义顺序(就像一个P总是更大的约定),所以你的P和Q值可能是从你开始的RSAParameters结构向后用。因此DP和DQ也将被撤销。
为什么你需要P和Q,如果你已经有D和模数? – 2011-05-25 00:10:21