понедельник, 13 апреля 2020 г.

RSA алгоритм

Восстанавливаем ключи по двум простым числам.

  1. /*
  2.          
  3.             function inverse(a, n)
  4.     t := 0;     newt := 1
  5.     r := n;     newr := a
  6.     while newr ≠ 0 do
  7.         quotient := r div newr
  8.         (t, newt) := (newt, t − quotient × newt)
  9.         (r, newr) := (newr, r − quotient × newr)
  10.     if r > 1 then
  11.         return "a is not invertible"
  12.     if t < 0 then
  13.         t := t + n
  14.     return t
  15.          */
  16.         static BigInteger modInverse(BigInteger a, BigInteger m)
  17.         {
  18.             BigInteger m0 = m;
  19.             BigInteger y = 0, x = 1;
  20.             if (== 1)
  21.                 return 0;
  22.             while (> 1)
  23.             {
  24.                 // q is quotient
  25.                 BigInteger q = a / m;
  26.                 BigInteger t = m;
  27.                 // m is remainder now, process
  28.                 // same as Euclid's algo
  29.                 m = a % m;
  30.                 a = t;
  31.                 t = y;
  32.                 // Update x and y
  33.                 y = x - q * y;
  34.                 x = t;
  35.             }
  36.             // Make x positive
  37.             if (< 0)
  38.                 x += m0;
  39.             return x;
  40.         }
  41.         static void Main(string[] args)
  42.         {
  43.             for (int i = 0; i < 10000; i++)
  44.             {
  45.                 var rsaKey = RSA.Create(2048);
  46.                 var rsaInboundParam = rsaKey.ExportParameters(true);
  47.                 BigInteger P = new BigInteger(rsaInboundParam.Ptruetrue); ; // p - prime1
  48.                 BigInteger Q = new BigInteger(rsaInboundParam.Qtruetrue); //q - prime2
  49.                 BigInteger E = new BigInteger(rsaInboundParam.Exponenttruetrue); // e - public exponent
  50.                 BigInteger N = P * Q;// n = p * q  <<< modulus, e.g. public key
  51.                 BigInteger PHI_N = (- 1) * (- 1); // phi(n) = (p-1)*(q-1)
  52.                 BigInteger D = modInverse(E, PHI_N); // d - private exponent, d = 1/e mod phi(n)
  53.                 BigInteger DP = D % (- 1); // crt exponent 1 = d mod (p-1)
  54.                 BigInteger DQ = D % (- 1); // crt exponent 2 = d mod (q-1)
  55.                 BigInteger qInv = modInverse(Q, P); // crt coefficient  1/q mod p
  56.                 var rsaManual = new RSAParameters() //todo: в результате операций (н-р, умножение), могут получаться массивы меньшей длины (н-р, D[255], вместо D[256]). Необходимо реализовать соответствующий ресайз перед reverse
  57.                 {
  58.                     P = rsaInboundParam.P,
  59.                     Q = rsaInboundParam.Q,
  60.                     Exponent = rsaInboundParam.Exponent,
  61.                     Modulus = N.ToByteArray(truetrue),
  62.                     D = D.ToByteArray(truetrue),
  63.                     DP = DP.ToByteArray(truetrue),
  64.                     DQ = DQ.ToByteArray(truetrue),
  65.                     InverseQ = qInv.ToByteArray(truetrue)
  66.                 };
  67.                 RSA.Create(rsaManual);
  68.                 Console.WriteLine("D - {0}", rsaInboundParam.D.SequenceEqual(rsaManual.D));
  69.             }
  70.         }

1 комментарий:

M_Y_L_T комментирует...
Этот комментарий был удален автором.