3

When reading an RSA private key blob, which lacks several RSA parameters (DP, DQ, InverseQ, D), how can I calculate these missing parameters from those that are supplied? I've read that it's possible to calculate these from P and Q which are supplied, but I don't know how to calculate them.

When importing this key, I get errors when trying to use the private key claiming the data isn't there (of course P and Q are supplied though).

I need to be able to do this on multiple platforms, so I'm afraid that puts me in the camp of needing to own the actual code to calculate them.

In C#

Artjom B.
  • 61,146
  • 24
  • 125
  • 222
Andrew Arnott
  • 80,040
  • 26
  • 132
  • 171
  • 2
    The [Wikipedia article on RSA](https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29) shows how each of them can be calculated. – Artjom B. Feb 06 '16 at 17:08
  • Thanks. I was hoping for something closer to C# specific as I'm not confident in my BigInteger math skills and would rather not figure it out myself. – Andrew Arnott Feb 06 '16 at 17:27
  • 1
    Here you have an answer if you combine the answers of [this question](http://stackoverflow.com/questions/14229040/how-to-calculate-d-for-rsa-encryption-from-p-q-and-e) with the answers of [this question](http://stackoverflow.com/questions/2921406/calculate-primes-p-and-q-from-private-exponent-d-public-exponent-e-and-the). – Artjom B. Feb 06 '16 at 18:49
  • So you have P, Q, and e, and that's it? – President James K. Polk Feb 06 '16 at 21:22
  • I have P, Q, publicExponent, modulus. I don't have DP, DQ, InverseQ, or D. – Andrew Arnott Feb 06 '16 at 23:09
  • @ArtjomB. Thanks. The answers seem to be in bits and pieces and some with code snippets use custom BigInteger classes that they say have bugs in them. Other answers are just pure equations and don't explain the functions (like Phi). I'm not sure how to act on them. – Andrew Arnott Feb 06 '16 at 23:54
  • Actually I guess your wikipedia article under key generation does a good job of defining the phi function. So I'll study that more closely. – Andrew Arnott Feb 07 '16 at 00:16
  • I'm not having much luck. Even calculating `m = pq` doesn't give me the same modulus that a .NET generated RSA key has. The test I wrote here: https://gist.github.com/AArnott/921fd927fb6582fff387 fails because of the 64-byte number being compared, only the first 32 bytes are equal. The last 32-bytes appear to have no relationship. – Andrew Arnott Feb 07 '16 at 01:18
  • I figured it out. Thanks for your tips: https://gist.github.com/AArnott/c105f9a1c8ebf546a027 – Andrew Arnott Feb 07 '16 at 06:19

1 Answers1

5

Here is the C# code that can construct a full set of RSAParameters from P, Q, and the public key data. We assume that the parameters to this method are big-endian (as is RSAParameters).

private static RSAParameters Create(byte[] p, byte[] q, byte[] exponent, byte[] modulus)
{
    var addlParameters = GetFullPrivateParameters(
        p: new BigInteger(CopyAndReverse(p)),
        q: new BigInteger(CopyAndReverse(q)),
        e: new BigInteger(CopyAndReverse(exponent)),
        modulus: new BigInteger(CopyAndReverse(modulus)));

    return new RSAParameters
    {
        P = p,
        Q = q,
        Exponent = exponent,
        Modulus = modulus,
        D = addlParameters.D,
        DP = addlParameters.DP,
        DQ = addlParameters.DQ,
        InverseQ = addlParameters.InverseQ,
    };
}

private static RSAParameters GetFullPrivateParameters(BigInteger p, BigInteger q, BigInteger e, BigInteger modulus)
{
    var n = p * q;
    var phiOfN = n - p - q + 1; // OR: (p - 1) * (q - 1);

    var d = ModInverse(e, phiOfN);
    Assert.Equal(1, (d * e) % phiOfN);

    var dp = d % (p - 1);
    var dq = d % (q - 1);

    var qInv = ModInverse(q, p);
    //Assert.Equal(1, (qInv * q) % p);

    return new RSAParameters
    {
        D = CopyAndReverse(d.ToByteArray()),
        DP = CopyAndReverse(dp.ToByteArray()),
        DQ = CopyAndReverse(dq.ToByteArray()),
        InverseQ = CopyAndReverse(qInv.ToByteArray()),
    };
}


/// <summary>
/// Calculates the modular multiplicative inverse of <paramref name="a"/> modulo <paramref name="m"/>
/// using the extended Euclidean algorithm.
/// </summary>
/// <remarks>
/// This implementation comes from the pseudocode defining the inverse(a, n) function at
/// https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
/// </remarks>
public static BigInteger ModInverse(BigInteger a, BigInteger n)
{
    BigInteger t = 0, nt = 1, r = n, nr = a;

    if (n < 0)
    {
        n = -n;
    }

    if (a < 0)
    {
        a = n - (-a % n);
    }

    while (nr != 0)
    {
        var quot = r / nr;

        var tmp = nt; nt = t - quot * nt; t = tmp;
        tmp = nr; nr = r - quot * nr; r = tmp;
    }

    if (r > 1) throw new ArgumentException(nameof(a) + " is not convertible.");
    if (t < 0) t = t + n;
    return t;
}

private static byte[] CopyAndReverse(byte[] data)
{
    byte[] reversed = new byte[data.Length];
    Array.Copy(data, 0, reversed, 0, data.Length);
    Array.Reverse(reversed);
    return reversed;
}
Andrew Arnott
  • 80,040
  • 26
  • 132
  • 171
  • This modular inverse method does not work for me. It always returns an incorrect result, and performing an assertion on it of `Assert.AreEqual(1, (iq * q) % p);` always fails. – laptou May 09 '17 at 06:39