RSA算法是第一个能同时用于加密和数字签名的算法,也易于理解和操作。 RSA是被研究得最广泛的公钥算法,从提出到现在已近二十年,经历了各种攻击的 考验,逐渐为人们接受,普遍认为是目前最优秀的公钥方案之一。RSA的安全性依 赖于大数的因子分解,但并没有从理论上证明破译RSA的难度与大数分解难度等价 。
RSA的安全性依赖于大数分解。公钥和私钥都是两个大素数( 大于 100 个十进制位)的函数。据猜测,从一个密钥和密文推断出明文的难度等同于分解 两个大素数的积。
密钥对的产生。选择两个大素数,p 和q 。计算:
n = p * q
然后随机选择加密密钥e(PS:最常用的e值有3,17和 65537,微软就是使用的65537,采用3个中的任何一个都不存在安全问题),要求 e 和 ( p - 1 ) * ( q - 1 ) 互质。最后,利用Euclid 算法计算解密密钥d, 满 足
e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )
其中n和d也要互质 。数e和n是公钥,d是私钥。两个素数p和q不再需要,应该丢弃,不要让任何人知 道。
加密信息 m(二进制表示)时,首先把m分成等长数据块 m1 ,m2,..., mi ,块长s,其中 2^s <= n, s 尽可能的大。对应的密文是:
ci = mi^e ( mod n ) ( a )
解密时作如下计算:
mi = ci^d ( mod n ) ( b )
.NET提供常用的加密算法类,支持RSA的类是 RSACryptoServiceProvider(命名空间:System.Security.Cryptography),但 只支持公钥加密,私钥解密。RSACryptoServiceProvider类包括:Modulus、 Exponent、P、Q、DP、DQ、InverseQ、D等8个属性,其中Modulus和Exponent就是 公钥,Modulus和D就是私钥,RSACryptoServiceProvider类提供导出公钥的方法 ,也提供导出私钥的方法,但导出的私钥包含上面8个属性,显然要用 RSACryptoServiceProvider实现私钥加密公钥是不可行的。
从RSA的原理 来看,公钥加密私钥解密和私钥加密公钥解密应该是等价的,在某些情况下,比 如共享软件加密,我们需要用私钥加密注册码或注册文件,发给用户,用户用公 钥解密注册码或注册文件进行合法性验证。
本人利用网上找的一个C#版的 大整数类BigInteger(本人认为这是偶发现的效率最高的一个C#版大整数类)来 实现私钥加密公钥加密(事实上也完全支持公租加密私钥解密),但没有使用类 BigInteger的大素数生成函数,而是直接使用类RSACryptoServiceProvider来生 成大素数。其中加密函数和解密函数的实现如下:
/**//*
功能: 用指定的私钥(n,d)加密指定字符串source
*/
private string EncryptString(string source, BigInteger d, BigInteger n)
...{
int len = source.Length;
int len1 = 0;
int blockLen = 0;
if ((len % 128) == 0)
len1 = len / 128;
else
len1 = len / 128 + 1;
string block = "";
string temp = "";
for (int i = 0; i < len1; i++)
...{
if (len >= 128)
blockLen = 128;
else
blockLen = len;
block = source.Substring(i * 128, blockLen);
byte[] oText = System.Text.Encoding.Default.GetBytes(block);
BigInteger biText = new BigInteger(oText);
BigInteger biEnText = biText.modPow(d, n);
string temp1 = biEnText.ToHexString ();
temp += temp1;
len -= blockLen;
}
return temp;
}
/**//*