如何在C＃中使用模數D指數創建專用RSA密鑰？

Question

我有3個字節的數組長度分別爲128,128,3個字節。我不知道它是什麼，但我希望它們是Modulus，D,Exponent。 現在我該如何在C＃中使用這些數組來解密使用RSA的字節數組？ 當我創建一個RSAParameters並將3個字節的數組分配到Modulus，D,Exponent並嘗試使用RSACryptoServiceProvider.ImportParameters中的RSAParameters時，解密將失敗，說明損壞的密鑰。我猜其他條目也需要填寫DQ,DP，...等...

我該怎麼做在C＃中？我沒有這些值，是否有一種簡單的方法來解密一個字節數組，只使用Modulus，D，C＃中的Exponent，就像其他語言一樣？

Answer 1

當你只有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)); 

Answer 2

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://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也將被撤銷。