c# 从 System.Security.Cryptography 获取具有 public 指数 3 的 RSA 密钥的正确方法是什么？

Question

我有一个使用 System.Security.Cryptography（标准提供程序）的 c# 程序，它需要生成特定位大小和指数的 RSA 密钥，以便与另一个长期存在的系统接口。这段代码对我来说似乎很合理：

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

大多数时候，但并非总是如此，我在 rsa2.ImportParameters 上遇到指数为 3 的 Bad Parameter 异常。有时它会起作用，而且我已经运行 rsa2.ToXmlString 显示 3 的指数：

<Exponent>Aw==</Exponent>

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

测试循环有时会因非零 trix 而失败，所以它有点工作。看截图和this MSDN social network post from 2019

从 System.Security.Cryptography 获取指数为 3 的 1024 位密钥的正确方法是什么？

（编辑添加 MSDN link）

Answer 1

改变public指数后，剩余的相关分量（即P、Q、Modulus、D、DP ,DQ,InverseQ)的key也必须调整。为此，最好使用专门的工具，例如充气城堡.

在纯 C# 中，您可以执行以下操作：

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

这里是 UpdatePublicExponent 和其他辅助函数：

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