CODEWITHSUNDEEP
c#cryptographyrsa
Andrew Arnott
Andrew Arnott

Reputation: 81801

How to calculate RSA's additional private key parameters from P and Q?

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#

Upvotes: 3

Views: 2176

Answers (1)

Andrew Arnott
Andrew Arnott

Reputation: 81801

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

Upvotes: 5

Related Questions