2009-06-13 88 views
1

我有3个字节的数组长度分别为128,128,3个字节。我不知道它是什么,但我希望它们是ModulusD,Exponent。 现在我该如何在C#中使用这些数组来解密使用RSA的字节数组? 当我创建一个RSAParameters并将3个字节的数组分配到ModulusD,Exponent并尝试使用RSACryptoServiceProvider.ImportParameters中的RSAParameters时,解密将失败,说明损坏的密钥。我猜其他条目也需要填写DQ,DP,...等...如何在C#中使用模数D指数创建专用RSA密钥?

我该怎么做在C#中?我没有这些值,是否有一种简单的方法来解密一个字节数组,只使用Modulus,D,C#中的Exponent,就像其他语言一样?

回答

0

当你只有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)); 
+0

为什么你需要P和Q,如果你已经有D和模数? – 2011-05-25 00:10:21

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。不知道哪个是nd是哪个?现在

// 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://stackoverflow.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也将被撤销。

相关问题