c# - 如何在 C# 中使用模数、D、指数创建私有(private) RSA key ？

Question

我有 3 个长度分别为 128、128、3 个字节的字节数组。我不知道它是什么，但我希望它们是 Modulus , D , Exponent .
现在如何在 C# 中使用这些数组来解密使用 RSA 的字节数组？
当我创建一个 RSAParameters并将 3 字节数组分配给 Modulus , D , Exponent并尝试在 RSACryptoServiceProvider.ImportParameters 中使用该 RSAParameters , 解密失败说明损坏的 key 。我猜其他条目也需要填写 DQ , DP ，...等等...

我如何在 C# 中做到这一点？我没有那个值，是否有一种简单的方法可以像在其他语言中一样仅使用 C# 中的 Modulus、D、Exponent 来解密字节数组？

Answer 1

Windows 实现似乎只愿意通过 CRT 参数执行 RSA，而将 D 作为可能被忽略的值。至少，CRT 参数是必需的输入。

首先，我们需要将您的数组转换为 BigInteger 值。我在这里假设您有 Big-Endian 编码值。如果他们是 Little-Endian，请不要调用 Array.Reverse()并将复制到索引从 1 更改为 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);
}

添加额外的字节可防止数字被视为负数。 (如果需要，可以通过测试最后一个字节中的符号位来避免分配和内存复制)。

所以现在你有三个 BigInteger 值， n , e , d .不确定是哪个 n和 d是哪个？

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

现在，使用来自 NIST Special Publication 800-56B Recommendation for Pair-Wise August 2009 Key Establishment Schemes Using Integer Factorization Cryptography, Appendix C 的算法(在 https://stackoverflow.com/a/28299742/6535399 中共享)我们可以计算 BigInteger 值。不过，有一个棘手的微妙之处。 RSAParameters 值必须具有正确的填充量，而 RSACryptoServiceProvider 不适合您。

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

使用“棘手”的 BigInteger-to-suitable-for-RSAParameters-byte[] 方法:

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

为了计算 InverseQ，您需要 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;
}

在我的计算机上，对于 1024 位 key ，我在大约 50 毫秒内从 (n, e, d) 恢复 P 和 Q。 4096 位 key 约 2-4 秒。

喜欢单元测试的实现者请注意: P 和 Q 并没有真正定义的顺序(就像 P 总是较大的约定)，因此您的 P 和 Q 值可能与您开始使用的 RSAParameters 结构相反。 DP 和 DQ 因此也将被颠倒。