Cで法、D、指数を使用してプライベートRSAキーを作成するには？

Question

私は長さ128バイト、128バイト、3バイトの3バイト配列を持っています。私はそれが何であるか分からないが、彼らはModulus、D、Exponentと期待している。 C＃でこれらの配列を使用して、RSAを使用してバイト配列を復号化するにはどうすればよいですか？ RSAParametersを作成し、3バイト配列をModulus,D,Exponentに割り当て、そのRSAParametersをRSACryptoServiceProvider.ImportParametersに使用しようとすると、復号化で破損したキーが示されません。私は他のエントリも記入する必要があると思いますDQ、DP、...等

どうすればC＃でできますか？私はその値を持っていない、他の言語と同様に、Modulus、D、ExponentをC＃で使用してバイト配列を解読する簡単な方法はありますか？

Answer 1

Mod、D、指数だけでは足りません。 （まあ、あなたが十分かもしれない）PとQは非常にmodから計算するのは難しいです。私はそれをどうやって行うのか分からず、同じ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); 
} 

にコピーへのインデックスを変更しない負として扱われるから数字を防ぐことができます。 （もし必要ならば最後のバイトの符号ビットをテストすることにより、割り当ておよびメモリコピーを回避することができる）。

これで、3つの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; 
} 

、我々はBigIntegerの値を算出することができる（https://stackoverflow.com/a/28299742/6535399で共有されるように）NIST Special Publication 800-56B Recommendation for Pair-Wise August 2009 Key Establishment Schemes Using Integer Factorization Cryptography, Appendix Cからアルゴリズムを使用。しかし、微妙な微妙なことがあります。 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; 
} 

そして、あなたはModInverseを必要とするInverseQコンピューティングのために：オン

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; 
} 

私のコンピュータ私は1024ビットのキーのために〜50msで（n、e、d）からPとQを回復しています。 4096ビットのキーの場合は2〜4秒です。

単体テストが好きな人には注意してください：PとQの定義された順序は本当にありません（Pは常に大きいという規則のように）ので、PとQの値は、あなたが起動したRSAParameters構造体と。したがってDPとDQも逆になります。