1

我正在创建一个简单的客户端应用程序来试验Mega，但我无法理解 RSA 的使用方式。让我们以会话 ID 的解密为例——这是登录时必须完成的第一件事。

API 为我提供了以下 RSA 数据：

  • p（1024 位）
  • q（1024 位）
  • d（2044 位）
  • u（1024 位）

首先，我不知道“u”代表什么。我从代码中看到它是通过以下方式计算的modinverse(p, q)- 这就是通常所说的 qInverse 吗？

这比我以前使用的私钥的 RSA 数据要少得多，所以我不太确定该怎么做。但是，我了解到 RSACryptoServiceProvider 使用的一些 RSA 数据只是出于优化目的而预先计算的数据，所以也许不需要其余的？

使用这些数据，站点的 JavaScript 使用以下函数解密会话 ID：

// Compute m**d mod p*q for RSA private key operations.

function RSAdecrypt(m, d, p, q, u)
{
 var xp = bmodexp(bmod(m,p), bmod(d,bsub(p,[1])), p);
 var xq = bmodexp(bmod(m,q), bmod(d,bsub(q,[1])), q);

 var t=bsub(xq,xp);
 if(t.length==0)
 {
  t=bsub(xp,xq);
  t=bmod(bmul(t, u), q);
  t=bsub(q,t);
 }
 else
 {
  t=bmod(bmul(t, u), q);
 } 
 return badd(bmul(t,p), xp);
}

我想在 .NET 中使用 RSACryptoServiceProvider 执行此操作，但如果我给它我拥有的 4 条数据（假设 u == qInverse），则密钥在导入期间被拒绝，并出现“错误数据”异常。

我应该对数据做更多的事情吗？RSACryptoServiceProvider 在这种情况下是否可用？

我正在测试的参数和加密数据示例如下。

 var p = Convert.FromBase64String("1AkMwy3SPbJtL/k2RUPNztBQKow0NX9LVr5/73+zR3cuwgUToYkVefKdzlTgeri9CAVUq/+jU6o+P7sUpPUN+V97quZa00m3GSIdonRMdaMrDDH5aHnkQgOsCjLJDWXU6+TQBqLumR3XMSat3VO09Dps+6NcMc+uMi5atC3tb+0=");
 var q = Convert.FromBase64String("qtnlmPbATJajNdihw1K6cwSormySATp7g75vYfilYx6RXN3xpNCZR/i8zFbx/lDh+n1a2rdHy1nWyuaD3UmE26d1xUkmsPDfBc72WXt88UqWE/gF7NJjtgTxS2Ui+2GGKUCloi5UA/pOI7R5TBvGI8zna00SH78bctyE0dcAcwM=");
 var d = Convert.FromBase64String("CFL4QPQ8zLzrf2bUzCVX8S2/eALzo/P2cvQsW9lft7uelHYfC1CvHP+z4RvQgXABpgT8YTdU+sgdMHrhHT1vxeUaDRkcQv9lV0IP6YtAcD+gk5jDQkXk4ruYztTUF3v4u8rlMuZ8kAKKWKw+JH6grLWD/vXjMv2RybxPqq3fKI6VJaj/Y/ZnDjD5HrQmJopnCbOrZrPysNb/rGrN3ad9ysaZwBvQtIE0/tQvmL+lsI+PfF9oGKeHkciIo0D4N2abOKT2fiazNm1U9LnrQih687ge0aeAlP2OO8c0h/nbEkMbNg83n1GGEt3DNojIWbT5uHaj12M6G81leS77mfLvSQ==");
 var u = Convert.FromBase64String("CNlUzgCf6Ymd/qeWiv3ScCIXYCwjP3SNLHxRgozIbNg2JEKpJn2M3vO72qLI+FT34xckaAGIcKWMkmpoaKy6PYF4jsAz2atLEClLimbMEPvpWxK7b/I5yvXMT7i2r5hr0OjjplL0wFQYL1IS2M8DTrL99rd9zXCoCWg5Tax6zQM=");

 var encryptedData = Convert.FromBase64String("CABt/Qp7ZODvweEk5RY9JNMXoyFfUwMnc53zbP5jB4jnwWXibLLvjc+Dv5CwQAtUYRme+vRd80++178BiWl0YSOKKhQaDQKoeOUONn3KbZVWyCtyWyQZNtASPoQfizay/Dw3yP5BKsJmDpEv47awdEZzh8IqTcTKeQbpHFL+3uL5EjIENpxMh15rJUsY9w+jq6Yax+379tq67EPMUON0aYkRQ3k1Rsp9fOL6qrgoqOPmOc0cIQgx76t6SFB9LmDySkyBhtK+vcEkdn9GwzZqc6n/Jqt9K8a+mbBv3K7eO3Pa37SDncsaxEzlyLwQ2om1+bK2QwauSQl+7QwQS1a9Ejb9");

 var rsa = new RSACryptoServiceProvider();

 // Throws exception saying "Bad data"
 rsa.ImportParameters(new RSAParameters
 {
      D = d,
      P = p,
      Q = q,
      InverseQ = u
  });

附录 2 月 2 日

我已经在链接的 StackOverflow 答案中进行了挖掘，并且已经达到了我认为我已经确定如何生成缺少的组件的地步。但是，现在我得到了一个“坏键”异常，这让我很困惑。

我将编写我用来生成缺失组件的代码——也许你可以在某处发现错误？

我还手动计算了 InverseQ 和 D，并且这些值与我的输入数据中的值匹配。下面是我仅基于 q、p 和 e 生成所需数据的函数。

private static RSAParameters CalculateRsaParameters(BigInteger p, BigInteger q, BigInteger e)
{
    var modulus = BigInteger.Multiply(p, q);

    var phi = BigInteger.Multiply(BigInteger.Subtract(p, BigInteger.One), BigInteger.Subtract(q, BigInteger.One));

    BigInteger x, y;
    // From http://www.codeproject.com/Articles/60108/BigInteger-Library
    // Returns 1 with my test data.
    ExtendedEuclidGcd(e, phi, out x, out y);

    var d = BigInteger.Remainder(x, phi);

    var dp = BigInteger.Remainder(d, BigInteger.Subtract(p, BigInteger.One));
    var dq = BigInteger.Remainder(d, BigInteger.Subtract(q, BigInteger.One));

    BigInteger x2, y2;
    // Returns 1 with my test data.
    ExtendedEuclidGcd(q, p, out x2, out y2);

    // y2 since it matched the pre-generated inverseQ data I had and x2 was some negative value, so it did not seem to fit. I have no idea what the logic behind which to pick really is.
    var qInverse = BigInteger.Remainder(y2, p);

    return new RSAParameters
    {
        D = ToBigEndianByteArray(d, 256),
        DP = ToBigEndianByteArray(dp, 128),
        DQ = ToBigEndianByteArray(dq, 128),
        InverseQ = ToBigEndianByteArray(qInverse, 128),
        Exponent = ToBigEndianByteArray(e, 1),
        Modulus = ToBigEndianByteArray(modulus, 256),
        P = ToBigEndianByteArray(p, 128),
        Q = ToBigEndianByteArray(q, 128)
    };
}

我的输入数据是：

e = 17
p = 148896287039501678969147386479458178246000691707699594019852371996225136011987881033904404601666619814302065310828663028471342954821076961960815187788626496609581811628527023262215778397482476920164511192915070597893567835708908996890192512834283979142025668876250608381744928577381330716218105191496818716653
q = 119975764355551220778509708561576785383941026741388506773912560292606151764383332427604710071170171329268379604135341015979284377183953677973647259809025842247294479469402755370769383988530082830904396657573472653613365794770434467132057189606171325505138499276437937752474437953713231209677228298628994462467

以下是我如何使用生成的结构：

var rsa = new RSACryptoServiceProvider(2048);
rsa.ImportParameters(CalculateRsaParameters(p, q, e));

该ImportParameters调用会引发异常，提示“Bad key”。我究竟做错了什么？

如果我切换 Q 和 P 会发生什么？

显然，它使 RSACryptoServiceProvider 接受数据！但这究竟意味着什么？

ExtendedEuclidGcd我从我必须在我的生成代码中使用的方式得到这个想法。不得不为两个实例使用不同的输出让我很困扰，所以我进行了这个实验。

一件事是u != qInverse- 这是正确的吗？我不了解原始 JavaScript 函数中的数学运算，所以我不确定它的含义是什么。我是否正确猜测原始中的 u 值实际上是一些内部快捷方式而不是 QInverse？

接下来的进一步测试（即数据的实际解密）。一旦有了任何新的发展，我都会编辑这个问题。

使用此参数集解密失败

我拥有的加密测试数据是（base64 编码）：

/TYSvVZLEAztfglJrgZDtrL5tYnaELzI5UzEGsudg7Tf2nM73q7cb7CZvsYrfasm/6lzajbDRn92JMG9vtKGgUxK8mAufVBIeqvvMQghHM055uOoKLiq+uJ8fcpGNXlDEYlpdONQzEPsutr2++3HGqarow/3GEsla16HTJw2BDIS+eLe/lIc6QZ5ysRNKsKHc0Z0sLbjL5EOZsIqQf7INzz8sjaLH4Q+EtA2GSRbcivIVpVtyn02DuV4qAINGhQqiiNhdGmJAb/Xvk/zXfT6nhlhVAtAsJC/g8+N77Js4mXB54gHY/5s851zJwNTXyGjF9MkPRblJOHB7+Bkewr9bQ==
or
bf0Ke2Tg78HhJOUWPSTTF6MhX1MDJ3Od82z+YweI58Fl4myy743Pg7+QsEALVGEZnvr0XfNPvte/AYlpdGEjiioUGg0CqHjlDjZ9ym2VVsgrclskGTbQEj6EH4s2svw8N8j+QSrCZg6RL+O2sHRGc4fCKk3EynkG6RxS/t7i+RIyBDacTIdeayVLGPcPo6umGsft+/bauuxDzFDjdGmJEUN5NUbKfXzi+qq4KKjj5jnNHCEIMe+rekhQfS5g8kpMgYbSvr3BJHZ/RsM2anOp/yarfSvGvpmwb9yu3jtz2t+0g53LGsRM5ci8ENqJtfmytkMGrkkJfu0MEEtWvRI2/Q==

由于我不确定字节顺序，因此给出了两种选择。两个字符串中的数据相同。

这两种情况的解密都失败了，但在第一种情况下会出现“错误数据”和“没有足够的存储空间来处理此命令”的异常。在第二种情况下（MSDN 声称这可能意味着密钥与加密数据不匹配）。我告诉 RSACryptoServiceProvider 使用了 PKCS 填充，尽管我也尝试了 OAEP（它只是给出了一个关于未能解码填充的错误）。

原始的 JavaScript 可以毫无问题地解密数据，尽管它的“p”和“q”是从我的转换过来的。

现在，我的问题是：

  • P 和 Q 切换是有效的操作吗？
  • 我的推理是有效的还是我在某个地方犯了错误？
  • 接下来我应该怎么做才能成功解密我的测试数据？
4

2 回答 2

2

RsaParameters 有八个字段。我认为您需要在创建私钥时初始化所有这些。

看看http://msdn.microsoft.com/en-us/library/system.security.cryptography.rsaparameters.aspx

于 2013-01-29T06:03:05.443 回答
0

在使用 .NET BigIntegers 和 RSA 参数时，可能会遇到许多可能的陷阱。可能影响您的两个是字节顺序和领先的零抑制。

System.Numerics.BigInteger类从 .NET 4.0 开始可用，它的ToByteArray()方法和new BigInteger(byte [])构造函数使用 litte-endian 格式。

不幸的是，该RSAParameters结构期望其字节数组字段为大端顺序。还有另一个必须考虑的不兼容性。ASystem.Numerics.BigInteger可以是正数或负数，该ToByteArray()方法通过使用二进制补码表示的变体来解决此问题。实际上，这意味着其字节数组表示的高位字节 >= 128 的正 BigInteger 将在最高位位置放置一个额外的零字节。但是，RSAParameter假定这些字段都是正数，因此前导零会因“错误数据”CryptographicException 而被无故拒绝。您必须在它们出现的地方删除这些前导零。

以下是显示这些操作的简单示例代码片段：

    static BigInteger ExtGCD(BigInteger a, BigInteger b, out BigInteger lastx, out BigInteger lasty)
    {
        var x = BigInteger.Zero;
        lastx = BigInteger.One;
        var y = BigInteger.One;
        lasty = BigInteger.Zero;
        while (!b.IsZero)
        {
            BigInteger remainder;
            BigInteger q = BigInteger.DivRem(a, b, out remainder);
            a = b;
            b = remainder;
            var t = x;
            x = lastx - q * x;
            lastx = t;
            t = y;
            y = lasty - q * y;
            lasty = t;
        }

        return a;
    }

    static BigInteger inverse(BigInteger a, BigInteger n)
    {
        BigInteger d, x, y;
        d = ExtGCD(a, n, out x, out y);
        if (d.IsOne)
        {
            // Always return the least positive value
            return (x + n) % n;
        }
        else
        {
            throw new ArgumentException("the arguments must be relatively prime, i.e. their gcd must be 1");
        }
    }

    static byte[] ToByteArrayBE(BigInteger b)
    {
        var x = b.ToByteArray(); // x is little-endian
        Array.Reverse(x);        // now it is big-endian
        if (x[0] == 0)
        {
            var newarray = new byte[x.Length - 1];
            Array.Copy(x, 1, newarray, 0, newarray.Length);
            return newarray;
        } else
        {
            return x;
        }
    }
    static RSAParameters CalculateRsaParameters(BigInteger p, BigInteger q, BigInteger e)
    {
        // Given p, q, and e (the RSA encryption exponent) compute the remaining parameters

        var phi = (p - 1) * (q - 1);

        var d = inverse(e, phi);
        var dp = d % (p - 1);
        var dq = d % (q - 1);
        var qInv = inverse(q, p);

        var RsaParams = new RSAParameters
        {
            Modulus = ToByteArrayBE(p * q),
            Exponent = ToByteArrayBE(e),
            P = ToByteArrayBE(p),
            Q = ToByteArrayBE(q),
            D = ToByteArrayBE(d),
            DP = ToByteArrayBE(dp),
            DQ = ToByteArrayBE(dq),
            InverseQ = ToByteArrayBE(qInv)
        };
        return RsaParams;
    }

    static void Main(string[] args)
    {
        BigInteger p = BigInteger.Parse("148896287039501678969147386479458178246000691707699594019852371996225136011987881033904404601666619814302065310828663028471342954821076961960815187788626496609581811628527023262215778397482476920164511192915070597893567835708908996890192512834283979142025668876250608381744928577381330716218105191496818716653");
        BigInteger q = BigInteger.Parse("119975764355551220778509708561576785383941026741388506773912560292606151764383332427604710071170171329268379604135341015979284377183953677973647259809025842247294479469402755370769383988530082830904396657573472653613365794770434467132057189606171325505138499276437937752474437953713231209677228298628994462467");
        BigInteger e = new BigInteger(17);
        RSAParameters RsaParams = CalculateRsaParameters(p, q, e);
        var Rsa = new RSACryptoServiceProvider();
        Rsa.ImportParameters(RsaParams);
    }
}
于 2013-02-03T16:34:34.383 回答