c# What is the right way to get an RSA key with public exponent 3 from System.Security.Cryptography?

Question

I have a c# program using System.Security.Cryptography (standard provider) that needs to generate RSA keys of a particular bit size and exponent to interface with another long standing system. This code seems reasonable to me:

            for (int trix = 0; trix < 1000; trix++)
            {
                using (var rsa2 = new RSACryptoServiceProvider(1024)) // public key length in bits
                { // PROBLEM: MS seems stuck on the big exponent
                    RSAParameters key2 = rsa2.ExportParameters(true);
                    key2.Exponent = new byte[1] { 3 }; // public key exponent
                    rsa2.ImportParameters(key2);
                    PrintToFeedback(rsa2.ToXmlString(true));
                    byte[] bm0 = Utilities.HexStringToByteArray("1002030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f");
                    byte[] bm1 = rsa2.Encrypt(bm0, false);
                    byte[] bm2 = rsa2.Decrypt(bm1, false);
                    string szbm0 = Utilities.ByteArrayToHexString(bm0);
                    string szbm2 = Utilities.ByteArrayToHexString(bm2);
                    if (szbm0 != szbm2)
                    {
                        PrintToFeedback("RSA module test FAILED with MS RSA keys with small exponent, bm0, bm1, bm2 follow:");
                        PrintToFeedback(szbm0);
                        PrintToFeedback(Utilities.ByteArrayToHexString(bm1));
                        PrintToFeedback(szbm2);
                        ok = false;
                        break;
                    }
                }
            }

Most of the time but not always, I get a Bad Parameter exception on rsa2.ImportParameters with the 3 exponent. Sometimes it works, and I have had runs where rsa2.ToXmlString shows an Exponent of 3:

<Exponent>Aw==</Exponent>

>base64 -d | xxd
Aw==
00000000: 03

The test loop sometimes fails with nonzero trix, so it works a little. See the screenshot and this MSDN social network post from 2019

What is the right way to get a 1024 bit key with exponent 3 from System.Security.Cryptography?

(edited to add MSDN link)

Answer 1

After changing the public exponent, the remaining dependent components (namely P, Q, Modulus, D, DP, DQ, InverseQ) of the key must also be adjusted. To achieve this, it is definitely better to use specialized tools, e.g. BouncyCastle.

In pure C# you can do something like:

public static void Main()
{
    using (var rsa = new RSACryptoServiceProvider(1024))
    {
        RSAParameters key = rsa.ExportParameters(true);

        // new public exponent
        BigInteger e = 3;

        // update public exponent and adjust dependent components
        UpdatePublicExponent(ref key, e);
        
        rsa.ImportParameters(key);

        Console.WriteLine(rsa.ToXmlString(true));
        byte[] bm0 =
            HexStringToByteArray(
                "1002030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f");
        byte[] bm1 = rsa.Encrypt(bm0, false);
        byte[] bm2 = rsa.Decrypt(bm1, false);

        Console.WriteLine(bm0.SequenceEqual(bm2));
    }
}

Here is UpdatePublicExponent with the other helper functions:

private static void UpdatePublicExponent(ref RSAParameters key, BigInteger e)
{
    int keyBytes = key.Modulus?.Length ?? 128;
    int keyBitLength = 8 * keyBytes;

    int pBitLength = (keyBitLength + 1) / 2;
    int qBitLength = keyBitLength - pBitLength;
    int minDiffBits = keyBitLength / 3;

    for (;;)
    {
        BigInteger p = GetRandomPrime(pBitLength, e);
        BigInteger q, n;
        for (;;)
        {
            q = GetRandomPrime(qBitLength, e);

            // p and q should not be too close together (or equal!)
            BigInteger diff = BigInteger.Abs(q - p);
            if (diff.GetBitLength() < minDiffBits)
            {
                continue;
            }

            // calculate the modulus
            n = p * q;

            if (n.GetBitLength() != keyBitLength)
            {
                // if we get here our primes aren't big enough, make the largest
                // of the two p and try again
                p = BigInteger.Max(p, q);
                continue;
            }

            break;
        }

        if (p < q)
        {
            BigInteger tmp = p;
            p = q;
            q = tmp;
        }

        BigInteger pSub1 = p - 1;
        BigInteger qSub1 = q - 1;

        BigInteger gcd = BigInteger.GreatestCommonDivisor(pSub1, qSub1);
        BigInteger lcm = pSub1 / gcd * qSub1;

        // calculate the private exponent
        BigInteger d = ModInverse(e, lcm);

        if (d.GetBitLength() <= qBitLength)
        {
            continue;
        }

        // calculate the CRT factors
        BigInteger dP = d % pSub1;
        BigInteger dQ = d % qSub1;
        BigInteger invQ = ModInverse(p, q);

        int halfBytes = (keyBytes + 1) / 2;

        // update key components
        key.P = GetBytes(p, halfBytes);
        key.Q = GetBytes(q, halfBytes);
        key.Modulus = GetBytes(n, keyBytes);

        key.Exponent = GetBytes(e, -1);

        key.D = GetBytes(d, keyBytes);
        key.DP = GetBytes(dP, halfBytes);
        key.DQ = GetBytes(dQ, halfBytes);
        key.InverseQ = GetBytes(invQ, halfBytes);

        break;
    }
}

private static BigInteger ModInverse(BigInteger a, BigInteger n)
{
    BigInteger i = n, v = 0, d = 1;
    while (a > 0)
    {
        BigInteger t = i / a, x = a;
        a = i % x;
        i = x;
        x = d;
        d = v - t * x;
        v = x;
    }
    v %= n;
    if (v < 0) v = (v + n) % n;
    return v;
}

private static BigInteger GetRandomPrime(int bitCount, BigInteger e)
{
    BigInteger prime;
    RandomNumberGenerator rng = RandomNumberGenerator.Create();
    int byteLength = (bitCount + 7) / 8;
    do
    {
        byte[] bytes = new byte[byteLength];
        rng.GetBytes(bytes);
        prime = new BigInteger(bytes, true);
    } while (prime.GetBitLength() != bitCount || prime % e == BigInteger.One || !IsProbablePrime(prime, 40));

    rng.Dispose();
    return prime;
}

// Miller-Rabin primality test as an extension method on the BigInteger type.
// http://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test#C.23
private static bool IsProbablePrime(BigInteger source, int certainty)
{
    if (source == 2 || source == 3)
        return true;
    if (source < 2 || source % 2 == 0)
        return false;

    BigInteger d = source - 1;
    int s = 0;

    while (d % 2 == 0)
    {
        d /= 2;
        s += 1;
    }

    // There is no built-in method for generating random BigInteger values.
    // Instead, random BigIntegers are constructed from randomly generated
    // byte arrays of the same length as the source.
    RandomNumberGenerator rng = RandomNumberGenerator.Create();
    byte[] bytes = new byte[source.ToByteArray().LongLength];
    BigInteger a;

    for (int i = 0; i < certainty; i++)
    {
        do
        {
            // This may raise an exception in Mono 2.10.8 and earlier.
            // http://bugzilla.xamarin.com/show_bug.cgi?id=2761
            rng.GetBytes(bytes);
            a = new BigInteger(bytes);
        }
        while (a < 2 || a >= source - 2);

        BigInteger x = BigInteger.ModPow(a, d, source);
        if (x == 1 || x == source - 1)
            continue;

        for (int r = 1; r < s; r++)
        {
            x = BigInteger.ModPow(x, 2, source);
            if (x == 1)
                return false;
            if (x == source - 1)
                break;
        }

        if (x != source - 1)
            return false;
    }

    return true;
}

private static byte[] GetBytes(BigInteger value, int size = -1)
{
    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;
}

public static byte[] HexStringToByteArray(string hex)
{
    byte[] bytes = new byte[hex.Length / 2];
    int[] hexValue = new int[] { 0x00, 0x01, 0x02, 0x03, 0x04, 0x05,
        0x06, 0x07, 0x08, 0x09, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F };

    for (int x = 0, i = 0; i < hex.Length; i += 2, x += 1)
    {
        bytes[x] = (byte) (hexValue[char.ToUpper(hex[i + 0]) - '0'] << 4 | hexValue[char.ToUpper(hex[i + 1]) - '0']);
    }

    return bytes;
}