作者:joyjy
 原文:https://gist.github.com/joyjy/5e971c3d6da6459be40d

概述

.Net 平台下 RSA 算法的设计目的仅用于__公钥加密/私钥解密__和__私钥签名/公钥验签__，同时为了增强安全性没有使用标准的填充方式。

根据 RSA 算法的设计原理，公私钥是可以互换加密解密的，因此在和其他平台互通时需要自行开发和标准算法兼容的公钥解密实现。本文提供了在已知公钥的 Exponent 和 Modulus 信息的情况下使用 BigInteger 解密的算法实现。

RSA 算法原理

  1. 若要生成密钥对，可以从创建名为 p 和 q 的两个大的质数开始。
  2. 这两个数相乘，结果称为 n。 因为 p 和 q 都是质数，所以 n 的全部因数为 1、p、q 和 n。
  3. 如果仅考虑小于 n 的数，则与 n 为互质数（即与 n 没有公因数）的数的个数等于 (p - 1)(q - 1)。
  4. 现在，选择一个数 e，它与计算的值为互质数。 则公钥表示为 {e, n}。
  5. 若要创建私钥，则必须计算 d，它是满足 (d)(e) mod (p - 1)(q - 1) = 1 的一个数。 根据 Euclidean 算法，私钥为 {d, n}。
  6. 纯文本 m 到密码文本 c 的加密定义为 c = (m ^ e) mod n。 解密则定义为 m = (c ^ d) mod n。

解密实现

在 PKCS #1: RSA Cryptography Standard（PKCS #1：RSA 加密标准）中，e 即公钥指数被记做 publicExponent；n 被记做 modulus；

由 RSA 非对称密钥的原理，对于原文 m 和密文 c，存在如下等式： 

c = (m ^ publicExponent) mod modulus
m = (c ^ privateExponent) mod modulus

可以看出将 publicExponent 及 privateExponent 互换，等式仍将成立；则以此可证能够使用公钥解密。

___示例代码如下：___ 

var modulus = BigInteger.Parse(modulusString);
var exponent = BigInteger.Parse(exponentString);

var encryptBytes = Convert.FromBase64String(text);
var value = new BigInteger(encryptBytes);

var result = BigInteger.ModPow(value, exponent, modulus);
var resultBytes = result.ToByteArray();

return Encoding.UTF8.GetString(resultBytes);

执行以上代码将无法得到正确结果，是因为 System.Numerics.BigInteger 类和字节数组的转换要求使用 little-endian 字节顺序，___应当进行如下修改：___ 

var modulus = BigInteger.Parse(modulusString);
var exponent = BigInteger.Parse(exponentString);

var encryptBytes = Convert.FromBase64String(text);
Array.Reverse(encryptBytes); // 需要调整字节序，BigIntenger 需要 little-endian
if ((encryptBytes[encryptBytes.Length - 1] & 0x80) > 0) // 如果最后一个字节第一位为1，追加一个 00 避免生成负数
{
    var temp = new byte[encryptBytes.Length];
    Array.Copy(encryptBytes, temp, encryptBytes.Length);
    encryptBytes = new byte[temp.Length + 1];
    Array.Copy(temp, encryptBytes, temp.Length);
}
var value = new BigInteger(encryptBytes);

var result = BigInteger.ModPow(value, exponent, modulus);
var resultBytes = result.ToByteArray();
Array.Reverse(resultBytes); // 调整顺序

int index = Array.FindIndex(resultBytes, b => b == 0) + 1;
return Encoding.UTF8.GetString(resultBytes, index, resultBytes.Length - index); // 排除掉旋转后多余的0

通过 X.509 SubjectPublicKeyInfo 格式的 ASN.1 文本获得公钥的 publicExponent 和 modulus 不在本文讨论范围之内。

注意事项

  1. BigInteger 类是 .Net 4.0 后才提供的；
  2. 不能兼容各种填充模式；
  3. 在不同 CPU 上可能需要注意字节序问题；

参考资料

  1. http://boytnt.blog.51cto.com/966121/1351207
  2. http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
  3. http://msdn.microsoft.com/zh-cn/library/system.security.cryptography.rsaparameters(v=vs.110).aspx
  4. http://msdn.microsoft.com/zh-cn/library/dd268207(v=vs.100).aspx
Comments
Write a Comment