How to calculate D for RSA encryption from P,Q and

问题:

I am trying to find D using P,Q and E (Dp, Dq and (p-1mod q) are available too).

According to this answer and this answer and update for this question using following method I should get D.

To test this I generated Key pair and tried to calculate components from existing ones and compare the result with originals. All the results are good except for D. there is something wrong with my calculation which I copied from above answers. it would be great if someone can tell me what I'm doing wrong.

Test Code

using System;
using System.Numerics;
using System.Security.Cryptography;
using System.Text;

class Program {

    static RSAParameters key = new RSAParameters() {
        P = new byte[]{
                0xDE, 0xA6, 0x35, 0x0B, 0x0A, 0xA5, 0xD7, 0xA0, 0x5C, 0x49, 0xEA, 0xD1, 0x3F, 0xA6, 0xF5, 0x12, 
                0x19, 0x06, 0x25, 0x8A, 0xD9, 0xA7, 0x07, 0xE7, 0x0D, 0x8A, 0x7C, 0xB1, 0xD4, 0x81, 0x64, 0xFD, 
                0x04, 0xEC, 0x47, 0x33, 0x42, 0x0B, 0x22, 0xF2, 0x60, 0xBB, 0x75, 0x62, 0x53, 0x3E, 0x1A, 0x97, 
                0x9D, 0xEF, 0x25, 0xA7, 0xE5, 0x24, 0x3A, 0x30, 0x36, 0xA5, 0xF9, 0x8A, 0xF5, 0xFF, 0x1D, 0x1B
            },

        Q = new byte[]{
                0xBE, 0xB9, 0x60, 0x12, 0x05, 0xB1, 0x61, 0xD9, 0x22, 0xD8, 0x84, 0x6E, 0x9A, 0x7B, 0xD1, 0x9B, 
                0x17, 0xA5, 0xDD, 0x02, 0x5E, 0x9D, 0xD8, 0x24, 0x06, 0x1B, 0xF3, 0xD8, 0x2F, 0x79, 0xFE, 0x78, 
                0x74, 0x3D, 0xC4, 0xE6, 0x17, 0xD2, 0xB7, 0x68, 0x78, 0x6F, 0x53, 0xE0, 0x38, 0x00, 0x86, 0xFB, 
                0x20, 0x2A, 0x1B, 0xBD, 0x91, 0x76, 0x3E, 0x33, 0x85, 0x9A, 0x31, 0xE6, 0x88, 0x60, 0x91, 0x81
            },

        DP = new byte[]{
                0xAC, 0x28, 0x92, 0x6D, 0x46, 0x3F, 0x74, 0x1A, 0xA0, 0x21, 0xDB, 0xBB, 0x0E, 0xDF, 0xD7, 0x31, 
                0xB6, 0x3D, 0xC5, 0x7B, 0xB6, 0xCE, 0x6B, 0xD2, 0xE1, 0xEA, 0x8A, 0x7E, 0xAA, 0xD5, 0x9E, 0xB3, 
                0xF2, 0x41, 0x8C, 0xD0, 0x7A, 0xA9, 0xC7, 0xCC, 0xE8, 0xB5, 0x2A, 0x8F, 0xEB, 0xD3, 0xE2, 0x96, 
                0x07, 0xDD, 0xEA, 0x1D, 0x07, 0x96, 0x5A, 0x93, 0xFB, 0x3D, 0x9D, 0x56, 0x30, 0xDE, 0xA1, 0xAF
            },

        DQ = new byte[]{
                0xA6, 0x9C, 0x44, 0x1B, 0x9A, 0x53, 0x89, 0xD9, 0xE8, 0xC1, 0xE2, 0x76, 0xC8, 0x87, 0x6F, 0xE5, 
                0x1F, 0x74, 0x6A, 0xAC, 0x5E, 0x41, 0x5F, 0x86, 0xA0, 0xBB, 0x9C, 0x79, 0xF7, 0x87, 0x87, 0xD0, 
                0x6C, 0x23, 0x65, 0xB5, 0x67, 0x8C, 0x51, 0x62, 0x77, 0x0B, 0x31, 0xE7, 0x86, 0xA4, 0x97, 0x46, 
                0x1B, 0xA4, 0x0D, 0x55, 0xBE, 0x13, 0xE0, 0x64, 0x9B, 0xCA, 0xC6, 0xDA, 0xCF, 0xBA, 0x24, 0x81
            },

        InverseQ = new byte[]{
                0x02, 0x42, 0x90, 0xAE, 0xFF, 0xFE, 0xB6, 0xCB, 0x53, 0xFF, 0x96, 0x17, 0xC6, 0xE4, 0x3F, 0xE6, 
                0xC7, 0xBC, 0xB2, 0xEB, 0x53, 0xA9, 0x47, 0xEE, 0x10, 0x36, 0x98, 0xEF, 0xA8, 0x3E, 0x9C, 0xF7, 
                0xF9, 0xCF, 0x24, 0xE5, 0xD7, 0x9A, 0xAF, 0x09, 0xCF, 0x28, 0xAA, 0x5D, 0x2A, 0xB7, 0x27, 0x73, 
                0x47, 0x2D, 0x54, 0x54, 0x61, 0xC5, 0xCE, 0x3E, 0xA4, 0x91, 0xF6, 0x9D, 0xF4, 0x65, 0x08, 0xDD
            },

        Exponent = new byte[]{
                0x00, 0x01, 0x00, 0x01, 
            },

        Modulus = new byte[]{
                0xA5, 0xE0, 0x95, 0x08, 0x87, 0x69, 0x2B, 0xB4, 0x7F, 0x08, 0xFB, 0x4F, 0x66, 0x85, 0xD9, 0x95, 
                0x53, 0x0F, 0x7C, 0x99, 0x95, 0x16, 0xF4, 0x0D, 0xAD, 0x9E, 0x31, 0xD8, 0x20, 0xF4, 0x88, 0x63, 
                0xAE, 0x51, 0x04, 0xC2, 0xE9, 0x92, 0x3C, 0x1C, 0x90, 0xF8, 0xF4, 0x38, 0x6A, 0x86, 0xFD, 0x8F, 
                0xDE, 0x85, 0x22, 0xDD, 0xE8, 0x7E, 0x8D, 0xF2, 0xC5, 0xC9, 0x4E, 0x71, 0x2B, 0x56, 0x25, 0x1A, 
                0xEA, 0x66, 0x15, 0x19, 0x63, 0x70, 0x53, 0x79, 0xDF, 0x38, 0x49, 0x30, 0x74, 0x45, 0xBE, 0xA3, 
                0x28, 0x0D, 0x0E, 0x7A, 0x7D, 0xB6, 0x8B, 0xCA, 0x09, 0x56, 0x21, 0xE7, 0x98, 0x3E, 0x4B, 0x8B, 
                0xD0, 0x31, 0x27, 0x8E, 0x6F, 0x10, 0xA6, 0x6C, 0x1C, 0x48, 0xB5, 0x5E, 0x89, 0x7B, 0x74, 0x74, 
                0xB2, 0x57, 0x72, 0x6D, 0x18, 0xEB, 0xF3, 0xF5, 0x53, 0xCA, 0x8C, 0xBE, 0xB7, 0x29, 0xF5, 0x9B
            },

        D = new byte[]{
                0x9F, 0x86, 0xE1, 0x4D, 0x96, 0x8C, 0xFA, 0xCF, 0x57, 0xED, 0x17, 0x64, 0x41, 0x41, 0x31, 0x04, 
                0x7F, 0x21, 0x41, 0xBF, 0xA2, 0xB6, 0xB4, 0x78, 0x03, 0x25, 0x44, 0xE2, 0x8A, 0xAF, 0x22, 0x0C, 
                0x5B, 0xB4, 0xE7, 0x53, 0x5C, 0xB6, 0x9A, 0xC1, 0x0E, 0x5B, 0x9E, 0xE4, 0x32, 0xEF, 0x28, 0x24, 
                0x98, 0xE8, 0x89, 0xA3, 0xC8, 0xD9, 0x0D, 0x43, 0x12, 0x1C, 0x8C, 0x28, 0x22, 0x79, 0x72, 0xAC, 
                0x66, 0x7B, 0x7D, 0xD2, 0xF9, 0x48, 0x06, 0xCD, 0x9D, 0x9A, 0xE6, 0x42, 0x92, 0xBA, 0x56, 0xA6, 
                0x63, 0x07, 0x1E, 0x25, 0x4E, 0xC8, 0x07, 0x58, 0x5B, 0x88, 0x60, 0x97, 0x92, 0xE2, 0xD5, 0xB9, 
                0xC6, 0x70, 0xBB, 0x63, 0x5A, 0xC3, 0xC3, 0xA6, 0x46, 0x5A, 0x1C, 0x9C, 0xBF, 0x61, 0x57, 0x9E, 
                0x9E, 0xFA, 0xC0, 0xC4, 0x8A, 0xC2, 0xBA, 0x88, 0x46, 0xA9, 0x7A, 0xF2, 0x7D, 0x4F, 0x6C, 0x01
            }
    };

    public static BigInteger FromBigEndian(byte[] p) {
        Array.Reverse(p);
        if (p[p.Length - 1] > 127) {
            Array.Resize(ref p, p.Length + 1);
            p[p.Length - 1] = 0;
        }
        return new BigInteger(p);
    }

    static void Main(string[] args) {

        using (RSACryptoServiceProvider rsa = new RSACryptoServiceProvider() { PersistKeyInCsp = false }) {
            rsa.ImportParameters(key);

            Console.Write("Testing Encrypt/Decrypt ... ");
            string message = "Testing Some Data to Encrypt";
            byte[] buffer = Encoding.ASCII.GetBytes(message);
            byte[] encoded = rsa.Encrypt(buffer, true);
            byte[] decoded = rsa.Decrypt(encoded, true);
            string message1 = ASCIIEncoding.ASCII.GetString(decoded);

            if (message == message1) {
                Console.WriteLine("Ok :)");
            } else {
                Console.WriteLine("Bad Encryption :(");
                Console.ReadKey();
                return;
            }
        }

        //Convert Key to BigIntegers
        BigInteger P = FromBigEndian(key.P);
        BigInteger Q = FromBigEndian(key.Q);
        BigInteger DP = FromBigEndian(key.DP);
        BigInteger DQ = FromBigEndian(key.DQ);
        BigInteger InverseQ = FromBigEndian(key.InverseQ);
        BigInteger E = FromBigEndian(key.Exponent);
        BigInteger M = FromBigEndian(key.Modulus);
        BigInteger D = FromBigEndian(key.D);


        Console.WriteLine("Testing Numbers ... ");
        BigInteger M1 = BigInteger.Multiply(P, Q); // M = P*Q
        if (M1.CompareTo(M) == 0) {
            Console.WriteLine("  M Ok :)");
        } else {
            Console.WriteLine("  Bad M:(");
            Console.ReadKey();
            return;
        }

        BigInteger PMinus1 = BigInteger.Subtract(P, BigInteger.One); // M = P*Q
        BigInteger DP1 = BigInteger.Remainder(D, PMinus1); // M = P*Q
        if (DP1.CompareTo(DP) == 0) {
            Console.WriteLine("  DP Ok :)");
        } else {
            Console.WriteLine("  Bad DP :(");
            Console.ReadKey();
            return;
        }

        BigInteger QMinus1 = BigInteger.Subtract(Q, BigInteger.One); // M = P*Q
        BigInteger DQ1 = BigInteger.Remainder(D, QMinus1); // M = P*Q
        if (DQ1.CompareTo(DQ) == 0) {
            Console.WriteLine("  DQ Ok :)");
        } else {
            Console.WriteLine("  Bad DQ :(");
            Console.ReadKey();
            return;
        }

        BigInteger Phi = BigInteger.Multiply(PMinus1, QMinus1);
        BigInteger PhiMinus1 = BigInteger.Subtract(Phi, BigInteger.One);
        BigInteger D1 = BigInteger.ModPow(E, PhiMinus1, Phi);
        if (D1.CompareTo(D) == 0) {
            Console.WriteLine("  D Ok :)");
        } else {
            Console.WriteLine("  Bad D :(");
            Console.ReadKey();
            return;
        }

        Console.ReadKey();
    }
}

Test Result

Testing Encrypt/Decrypt ... Ok :)
Testing Numbers ...
  M Ok :)
  DP Ok :)
  DQ Ok :)
  Bad D :(

回答1:

First you need to verify that GCD(e, φ) = 1 because d only exists if that property holds. Then calculate the modular multiplicative inverse of e modulo phi which I describe in my answer to "1/BigInteger in C#".

Your code seems to assume that e^(φ(n)-1) mod φ(n) is that inverse, but that's incorrect. I think the correct formula would be e^(φ(φ(n))-1) mod φ(n), but that's inconvenient to use since you only know φ(n) but not φ(φ(n)).

I recommend using the Extended Euclidean algorithm by porting the wikipedia pseudocode to C#.

---

As a side-note: There are often multiple equivalent values for d since you don't need e*d mod φ(n)=1 but just e*d mod λ(n)=1 where λ is the Carmichael function see "Why RSA encryption key is based on modulo(phi(n)) rather than modulo n" on crypto.SE

回答2:

Extended Euclidean algorithm can be used to compute the modular inverse, use this link: http://www.di-mgt.com.au/euclidean.html#extendedeuclidean to get the detail, I tested the source code in C# as below, and the result is matching,

public static BigInteger modinv(BigInteger u, BigInteger v)
{
   BigInteger inv, u1, u3, v1, v3, t1, t3, q;
   BigInteger iter;
   /* Step X1. Initialise */
   u1 = 1;
   u3 = u;
   v1 = 0;
   v3 = v;
   /* Remember odd/even iterations */
   iter = 1;
   /* Step X2. Loop while v3 != 0 */
   while (v3 != 0)
   {
       /* Step X3. Divide and "Subtract" */
       q = u3 / v3;
       t3 = u3 % v3;
       t1 = u1 + q * v1;
       /* Swap */
       u1 = v1; v1 = t1; u3 = v3; v3 = t3;
       iter = -iter;
   }
   /* Make sure u3 = gcd(u,v) == 1 */
   if (u3 != 1)
       return 0;   /* Error: No inverse exists */
       /* Ensure a positive result */
       if (iter < 0)
           inv = v - u1;
       else
           inv = u1;
       return inv;
}

回答3:

D Can be calculated by:

    var qq = BigInteger.Multiply(totient, n);
    var qw = BigInteger.Multiply(totient, qq);
    BigInteger d = BigInteger.ModPow(e, (qw - 1), totient);

回答4:

 Console.Write("Testing Encrypt/Decrypt using BigInteger ");
        string message2 = "Testing Some Data to Encrypt";
        byte[] buffer2 = Encoding.ASCII.GetBytes(message2);
        BigInteger m = new BigInteger(buffer2);
        BigInteger c = BigInteger.ModPow(m, E, M); //encrypt
        BigInteger m2 = BigInteger.ModPow(c, D, M); //decrypt, m2 also equals m
        byte[] decoded2 = m2.ToByteArray();

        if (decoded2[0] == 0) 
        {
            decoded2 = decoded2.Where(b => b != 0).ToArray();
        }
        string message3 = ASCIIEncoding.ASCII.GetString(decoded2);

        if (message2 == message3)
        {
            Console.WriteLine("Ok :)");
        }
        else
        {
            Console.WriteLine("Bad Encryption :(");
            Console.ReadKey();
            return;
        }

I tried it with your parametrs and it works, so E, D and M must be valid.