Восстанавливаем ключи по двум простым числам.
- /*
- function inverse(a, n)
- t := 0; newt := 1
- r := n; newr := a
- while newr ≠ 0 do
- quotient := r div newr
- (t, newt) := (newt, t − quotient × newt)
- (r, newr) := (newr, r − quotient × newr)
- if r > 1 then
- return "a is not invertible"
- if t < 0 then
- t := t + n
- return t
- */
- static BigInteger modInverse(BigInteger a, BigInteger m)
- {
- BigInteger m0 = m;
- BigInteger y = 0, x = 1;
- if (m == 1)
- return 0;
- while (a > 1)
- {
- // q is quotient
- BigInteger q = a / m;
- BigInteger t = m;
- // m is remainder now, process
- // same as Euclid's algo
- m = a % m;
- a = t;
- t = y;
- // Update x and y
- y = x - q * y;
- x = t;
- }
- // Make x positive
- if (x < 0)
- x += m0;
- return x;
- }
- static void Main(string[] args)
- {
- for (int i = 0; i < 10000; i++)
- {
- var rsaKey = RSA.Create(2048);
- var rsaInboundParam = rsaKey.ExportParameters(true);
- BigInteger P = new BigInteger(rsaInboundParam.P, true, true); ; // p - prime1
- BigInteger Q = new BigInteger(rsaInboundParam.Q, true, true); //q - prime2
- BigInteger E = new BigInteger(rsaInboundParam.Exponent, true, true); // e - public exponent
- BigInteger N = P * Q;// n = p * q <<< modulus, e.g. public key
- BigInteger PHI_N = (P - 1) * (Q - 1); // phi(n) = (p-1)*(q-1)
- BigInteger D = modInverse(E, PHI_N); // d - private exponent, d = 1/e mod phi(n)
- BigInteger DP = D % (P - 1); // crt exponent 1 = d mod (p-1)
- BigInteger DQ = D % (Q - 1); // crt exponent 2 = d mod (q-1)
- BigInteger qInv = modInverse(Q, P); // crt coefficient 1/q mod p
- var rsaManual = new RSAParameters() //todo: в результате операций (н-р, умножение), могут получаться массивы меньшей длины (н-р, D[255], вместо D[256]). Необходимо реализовать соответствующий ресайз перед reverse
- {
- P = rsaInboundParam.P,
- Q = rsaInboundParam.Q,
- Exponent = rsaInboundParam.Exponent,
- Modulus = N.ToByteArray(true, true),
- D = D.ToByteArray(true, true),
- DP = DP.ToByteArray(true, true),
- DQ = DQ.ToByteArray(true, true),
- InverseQ = qInv.ToByteArray(true, true)
- };
- RSA.Create(rsaManual);
- Console.WriteLine("D - {0}", rsaInboundParam.D.SequenceEqual(rsaManual.D));
- }
- }