4

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

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

4

2 回答 2

3

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，附录 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 位密钥，我在约 50 毫秒内从 (n, e, d) 恢复 P 和 Q。4096 位密钥约 2-4 秒。

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

于 2017-06-08T17:15:48.000 回答
1

当你只有 Mod、D 和指数时，你没有足够的东西。（嗯，你可能有足够的）P 和 Q 很难从 mod 中计算出来。我不知道该怎么做，而且几乎可以肯定有比正确的素数更多的素数最终得到相同的模式。

您至少需要 P、Q 和公共指数。

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));
于 2009-07-16T09:08:12.460 回答