How to create private RSA key using modulus, D, exponent in C#?

Question

I have 3 byte arrays of length 128, 128, 3 bytes respectively. I don't know what it is, but I expect them to be Modulus, D, Exponent. Now how can I use these arrays in C# to decrypt a byte array using RSA? When I create an RSAParameters and assign the 3 byte arrays to Modulus, D, Exponent and try to use that RSAParameters in RSACryptoServiceProvider.ImportParameters, decryption fails stating corrupt keys. I guess the other entries also need to be filled DQ,DP,...etc...

How do I do that in C#? I don't have that values, is there an easy way to decrypt a byte array using only Modulus, D, Exponent in C#, as in other languages?

score 3 · Answer 1 · answered Jun 08 '17 at 17:15

The Windows implementations seem to only be willing to do RSA via the CRT parameters, leaving D as a potentially ignored value. At the very least, the CRT parameters are required inputs.

First, we need to turn your arrays into BigInteger values. I'm assuming here that you have Big-Endian encoded values. If they're Little-Endian, don't call Array.Reverse() and change the copy-to index from 1 to 0.

private static BigInteger GetBigInteger(byte[] bytes)
{
    byte[] signPadded = new byte[bytes.Length + 1];
    Buffer.BlockCopy(bytes, 0, signPadded, 1, bytes.Length);
    Array.Reverse(signPadded);
    return new BigInteger(signPadded);
}

Adding the extra byte prevents numbers from being treated as negative. (One could avoid the allocation and memory copy by testing for the sign bit in the last byte, if one wanted).

So now you have three BigInteger values, n, e, d. Not sure which of n and d is which?

// Unless someone tried really hard to make this break it'll work.
if (n < d)
{
    BigInteger tmp = n;
    n = d;
    d = tmp;
}

Now, using the algorithm from NIST Special Publication 800-56B Recommendation for Pair-Wise August 2009 Key Establishment Schemes Using Integer Factorization Cryptography, Appendix C (as shared in https://stackoverflow.com/a/28299742/6535399) we can calculate the BigInteger values. There's a tricky subtlety, though. RSAParameters values have to have a correct amount of padding, and RSACryptoServiceProvider doesn't do it for you.

private static RSAParameters RecoverRSAParameters(BigInteger n, BigInteger e, BigInteger d)
{
    using (RandomNumberGenerator rng = RandomNumberGenerator.Create())
    {
        BigInteger k = d * e - 1;

        if (!k.IsEven)
        {
            throw new InvalidOperationException("d*e - 1 is odd");
        }

        BigInteger two = 2;
        BigInteger t = BigInteger.One;

        BigInteger r = k / two;

        while (r.IsEven)
        {
            t++;
            r /= two;
        }

        byte[] rndBuf = n.ToByteArray();

        if (rndBuf[rndBuf.Length - 1] == 0)
        {
            rndBuf = new byte[rndBuf.Length - 1];
        }

        BigInteger nMinusOne = n - BigInteger.One;

        bool cracked = false;
        BigInteger y = BigInteger.Zero;

        for (int i = 0; i < 100 && !cracked; i++)
        {
            BigInteger g;

            do
            {
                rng.GetBytes(rndBuf);
                g = GetBigInteger(rndBuf);
            }
            while (g >= n);

            y = BigInteger.ModPow(g, r, n);

            if (y.IsOne || y == nMinusOne)
            {
                i--;
                continue;
            }

            for (BigInteger j = BigInteger.One; j < t; j++)
            {
                BigInteger x = BigInteger.ModPow(y, two, n);

                if (x.IsOne)
                {
                    cracked = true;
                    break;
                }

                if (x == nMinusOne)
                {
                    break;
                }

                y = x;
            }
        }

        if (!cracked)
        {
            throw new InvalidOperationException("Prime factors not found");
        }

        BigInteger p = BigInteger.GreatestCommonDivisor(y - BigInteger.One, n);
        BigInteger q = n / p;
        BigInteger dp = d % (p - BigInteger.One);
        BigInteger dq = d % (q - BigInteger.One);
        BigInteger inverseQ = ModInverse(q, p);

        int modLen = rndBuf.Length;
        int halfModLen = (modLen + 1) / 2;

        return new RSAParameters
        {
            Modulus = GetBytes(n, modLen),
            Exponent = GetBytes(e, -1),
            D = GetBytes(d, modLen),
            P = GetBytes(p, halfModLen),
            Q = GetBytes(q, halfModLen),
            DP = GetBytes(dp, halfModLen),
            DQ = GetBytes(dq, halfModLen),
            InverseQ = GetBytes(inverseQ, halfModLen),
        };
    }
}

With the "tricky" BigInteger-to-suitable-for-RSAParameters-byte[] method:

private static byte[] GetBytes(BigInteger value, int size)
{
    byte[] bytes = value.ToByteArray();

    if (size == -1)
    {
        size = bytes.Length;
    }

    if (bytes.Length > size + 1)
    {
        throw new InvalidOperationException($"Cannot squeeze value {value} to {size} bytes from {bytes.Length}.");
    }

    if (bytes.Length == size + 1 && bytes[bytes.Length - 1] != 0)
    {
        throw new InvalidOperationException($"Cannot squeeze value {value} to {size} bytes from {bytes.Length}.");
    }

    Array.Resize(ref bytes, size);
    Array.Reverse(bytes);
    return bytes;
}

And for computing InverseQ you need ModInverse:

private static BigInteger ModInverse(BigInteger e, BigInteger n)
{
    BigInteger r = n;
    BigInteger newR = e;
    BigInteger t = 0;
    BigInteger newT = 1;

    while (newR != 0)
    {
        BigInteger quotient = r / newR;
        BigInteger temp;

        temp = t;
        t = newT;
        newT = temp - quotient * newT;

        temp = r;
        r = newR;
        newR = temp - quotient * newR;
    }

    if (t < 0)
    {
        t = t + n;
    }

    return t;
}

On my computer I'm recovering P and Q from (n, e, d) in ~50ms for a 1024-bit key. ~2-4 seconds for a 4096-bit key.

Note to implementers who like unit tests: There's not really a defined order for P and Q (like a convention that P always be the larger), so your P and Q values may be backwards from an RSAParameters structure that you started with. DP and DQ will thus also be reversed.

score 1 · Answer 2 · answered Jul 16 '09 at 09:08

You don't have enough when you just have Mod, D, and the exponent. (Well you might have enough) P and Q are VERY hard to calculate from the mod. I wouldn't know how to do that and there are almost certainly more primes than the right ones that multiplied end up with the same mod.

You need atleast P, Q and the public exponent.

P, Q and D are the building blocks

DP = D mod (p - 1)
DQ = D mod (q - 1)
InverseQ = Q^-1 mod p
Modulus = P * Q

so now we have 

P Q and D.

and we can calulate DP, DQ, InverseQ and Modulus and Exponent (see below)

long gcd(long a, long b)
{
    long temp;
    while (b != 0)
    {
        temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

Exponent = gcd(1, (P - 1)*(Q - 1));

Why do you need P and Q if you already have D and the Modulus? — Michael Stum, May 25 '11 at 00:10
Your absolutely right one only needs the pubkey consisting of the Modulus the Exponent and D. I focussed to much on the missing values. — albertjan, May 31 '11 at 08:27

How to create private RSA key using modulus, D, exponent in C#?

2 Answers2

Linked