RSA算法是第一個(gè)既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。它易于理解和操作，也很流行。它的安全性是基于大整數(shù)素因子分解的困難性，而大整數(shù)因子分解問題是數(shù)學(xué)上的著名難題，至今沒有有效的方法予以解決，因此可以確保RSA算法的安全性。

　　到目前Silverlight4 Beta發(fā)布為止，Silverlight中仍然沒有提供非對(duì)稱加密及數(shù)字簽名相關(guān)的算法。而.NET Framework中提供的RSA等算法，都是通過操作系統(tǒng)提供的相關(guān)API實(shí)現(xiàn)的，沒法移植到Silverlight中使用。因此很難實(shí)現(xiàn)一個(gè)健壯點(diǎn)的Silverlight純客戶端的注冊(cè)驗(yàn)證算法。這幾天抽空寫了個(gè)Silverlight下可用的RSA算法，使用非對(duì)稱加密和數(shù)字簽名使Silverlight純客戶端的注冊(cè)驗(yàn)證算法健壯了不少。關(guān)于這個(gè)Silverlight下可用的RSA算法的具體實(shí)現(xiàn)，記錄在下面，歡迎大家拍磚。

　　RSA算法實(shí)現(xiàn)主要分為三部分：包括公鑰和私鑰的產(chǎn)生，非對(duì)稱加密和解密，數(shù)字簽名和驗(yàn)證，下面將逐個(gè)介紹RSA算法的工作原理及我的實(shí)現(xiàn)方法。

　　1、公鑰和私鑰的產(chǎn)生

　　隨意選擇兩個(gè)大素?cái)?shù)p、q，p不等于q，計(jì)算n = p * q。
隨機(jī)選擇一個(gè)整數(shù)e，滿足e和( p – 1 ) * ( q – 1 )互質(zhì)。(注：e很容易選擇，如3, 17, 65537等都可以。.NET Framework中e默認(rèn)選擇的就是65537)
利用Euclid算法計(jì)算解密密鑰d,滿足
e * d ≡ 1 ( mod ( p - 1 ) * ( q - 1 ) )
其中n和d也要互質(zhì)。

　　其中e和n就是公鑰，d和n就是私鑰。P、q銷毀。

　　在.NET Framework的RSA算法中，e對(duì)應(yīng)RSAParameters.Exponent；d對(duì)應(yīng)RSAParameters.D；n對(duì)應(yīng)RSAParameters.ModulusExponent。.NET Framework中的RSA算法默認(rèn)使用1024位長的密鑰。公鑰和私鑰是利用.NET Framework的RSACryptoServiceProvider生成公鑰xml文件和私鑰xml文件來實(shí)現(xiàn)的。生成公鑰和私鑰xml文件的程序本身不是Silverlight程序。

RSACryptoServiceProvider rsa = new RSACryptoServiceProvider();

　　//生成公鑰XML字符串
string publicKeyXmlString = rsa.ToXmlString(false);

　　//生成私鑰XML字符串
string privateKeyXmlString = rsa.ToXmlString(true);

公鑰和私鑰將從生成的公鑰xml文件和私鑰xml文件中導(dǎo)入。

public class RSAPublicKey
{
public byte[] Modulus;
public byte[] Exponent;

　　public static RSAPublicKey FromXmlString(string xmlString)
{
if (string.IsNullOrEmpty(xmlString))
{
return null;
}

　　try
{
using (XmlReader reader = XmlReader.Create(new StringReader(xmlString)))
{
if (!reader.ReadToFollowing("RSAKeyValue"))
{
return null;
}

　　if (reader.LocalName != "Modulus" && !reader.ReadToFollowing("Modulus"))
{
return null;
}
string modulus = reader.ReadElementContentAsString();

　　if (reader.LocalName != "Exponent" && !reader.ReadToFollowing("Exponent"))
{
return null;
}
string exponent = reader.ReadElementContentAsString();

　　RSAPublicKey publicKey = new RSAPublicKey();
publicKey.Modulus = Convert.FromBase64String(modulus);
publicKey.Exponent = Convert.FromBase64String(exponent);

　　return publicKey;
}
}
catch
{
return null;
}
}
}
 

public class RSAPrivateKey
{
public byte[] Modulus;
public byte[] D;

　　public static RSAPrivateKey FromXmlString(string xmlString)
{
if (string.IsNullOrEmpty(xmlString))
{
return null;
}

　　try
{
using (XmlReader reader = XmlReader.Create(new StringReader(xmlString)))
{
if (!reader.ReadToFollowing("RSAKeyValue"))
{
return null;
}

　　if (reader.LocalName != "Modulus" && !reader.ReadToFollowing("Modulus"))
{
return null;
}
string modulus = reader.ReadElementContentAsString();

　　if (reader.LocalName != "D" && !reader.ReadToFollowing("D"))
{
return null;
}
string d = reader.ReadElementContentAsString();

　　RSAPrivateKey privateKey = new RSAPrivateKey();
privateKey.Modulus = Convert.FromBase64String(modulus);
privateKey.D = Convert.FromBase64String(d);

　　return privateKey;
}
}
catch
{
return null;
}
}
}
 

　　2、非對(duì)稱加密和解密

　　私鑰加密m（二進(jìn)制表示）時(shí)，首先把m分成長s的數(shù)據(jù)塊 m1, m2 ... mi，其中 2^s <= n, s 盡可能的大。執(zhí)行如下計(jì)算：
ci = mi ^ d (mod n)
　　公鑰解密c（二進(jìn)制表示）時(shí)，也需要將c分成長s的數(shù)據(jù)塊c1, c2 ... ci，執(zhí)行如下計(jì)算：
mi = ci ^ e (mod n)

　　在某些情況下，也會(huì)使用公鑰加密->私鑰解密。原理和私鑰加密->公鑰解密一樣。下面是私鑰計(jì)算和公鑰計(jì)算的算法。其中利用到了Chew Keong TAN的BigInteger類。.NET Framework 4中提供的BigInteger.ModPow方法好像有問題。

private static byte[] Compute(byte[] data, RSAPublicKey publicKey, int blockSize)
{
//
// 公鑰加密/解密公式為：ci = mi^e ( mod n )
//
// 先將 m（二進(jìn)制表示）分成數(shù)據(jù)塊 m1, m2, ..., mi ，然后進(jìn)行運(yùn)算。
//
BigInteger e = new BigInteger(publicKey.Exponent);
BigInteger n = new BigInteger(publicKey.Modulus);

　　int blockOffset = 0;
using (MemoryStream stream = new MemoryStream())
{
while (blockOffset < data.Length)
{
int blockLen = Math.Min(blockSize, data.Length - blockOffset);
byte[] blockData = new byte[blockLen];
Buffer.BlockCopy(data, blockOffset, blockData, 0, blockLen);

　　BigInteger mi = new BigInteger(blockData);
BigInteger ci = mi.modPow(e, n);//ci = mi^e ( mod n )

　　byte[] block = ci.getBytes();
stream.Write(block, 0, block.Length);
blockOffset += blockLen;
}

　　return stream.ToArray();
}
}

　　private static byte[] Compute(byte[] data, RSAPrivateKey privateKey, int blockSize)
{
//
// 私鑰加密/解密公式為：mi = ci^d ( mod n )
//
// 先將 c（二進(jìn)制表示）分成數(shù)據(jù)塊 c1, c2, ..., ci ，然后進(jìn)行運(yùn)算。
//
BigInteger d = new BigInteger(privateKey.D);
BigInteger n = new BigInteger(privateKey.Modulus);

　　int blockOffset = 0;

　　using (MemoryStream stream = new MemoryStream())
{
while (blockOffset < data.Length)
{
int blockLen = Math.Min(blockSize, data.Length - blockOffset);
byte[] blockData = new byte[blockLen];
Buffer.BlockCopy(data, blockOffset, blockData, 0, blockLen);

　　BigInteger ci = new BigInteger(blockData);
BigInteger mi = ci.modPow(d, n);//mi = ci^d ( mod n )

　　byte[] block = mi.getBytes();
stream.Write(block, 0, block.Length);
blockOffset += blockLen;
}

　　return stream.ToArray();
}
}
 

下面是私鑰加密->公鑰解密的實(shí)現(xiàn)。

public static byte[] Encrypt(byte[] data, RSAPublicKey publicKey)
{
if (data == null)
{
throw new ArgumentNullException("data");
}

　　if (publicKey == null)
{
throw new ArgumentNullException("publicKey");
}

　　int blockSize = publicKey.Modulus.Length - 1;
return Compute(data, publicKey, blockSize);
}

　　public static byte[] Decrypt(byte[] data, RSAPrivateKey privateKey)
{
if (data == null)
{
throw new ArgumentNullException("data");
}

　　if (privateKey == null)
{
throw new ArgumentNullException("privateKey");
}

　　int blockSize = privateKey.Modulus.Length;
return Compute(data, privateKey, blockSize);
}
 

下面是公鑰加密->私鑰解密的實(shí)現(xiàn)。

public static byte[] Encrypt(byte[] data, RSAPrivateKey privateKey)
{
if (data == null)
{
throw new ArgumentNullException("data");
}

　　if (privateKey == null)
{
throw new ArgumentNullException("privateKey");
}

　　int blockSize = privateKey.Modulus.Length - 1;
return Compute(data, privateKey, blockSize);
}

　　public static byte[] Decrypt(byte[] data, RSAPublicKey publicKey)
{
if (data == null)
{
throw new ArgumentNullException("data");
}

　　if (publicKey == null)
{
throw new ArgumentNullException("publicKey");
}

　　int blockSize = publicKey.Modulus.Length;
return Compute(data, publicKey, blockSize);
}
 

　　3、數(shù)字簽名和驗(yàn)證

　　私鑰簽名數(shù)據(jù)m時(shí)，先對(duì)m進(jìn)行hash計(jì)算，得到計(jì)算結(jié)果h。然后將h使用私鑰加密，得到加密后的密文s即為簽名。
公鑰驗(yàn)證簽名s時(shí)，先將m進(jìn)行hash計(jì)算，得到計(jì)算結(jié)果h。然后使用公鑰解密s得到結(jié)果h’。如果h==h’即驗(yàn)證成功，否則驗(yàn)證失敗。

　　在某些情況下，也會(huì)使用公鑰簽名->私鑰驗(yàn)證。原理和私鑰簽名->公鑰驗(yàn)證一樣。

　　下面是私鑰簽名->公鑰驗(yàn)證的實(shí)現(xiàn)。

public static byte[] Sign(byte[] data, RSAPublicKey publicKey, HashAlgorithm hash)
{
if (data == null)
{
throw new ArgumentNullException("data");
}

　　if (publicKey == null)
{
throw new ArgumentNullException("publicKey");
}

　　if (hash == null)
{
throw new ArgumentNullException("hash");
}

　　byte[] hashData = hash.ComputeHash(data);
byte[] signature = Encrypt(hashData, publicKey);
return signature;
}

　　public static bool Verify(byte[] data, RSAPrivateKey privateKey, HashAlgorithm hash, byte[] signature)
{
if (data == null)
{
throw new ArgumentNullException("data");
}

　　if (privateKey == null)
{
throw new ArgumentNullException("privateKey");
}

　　if (hash == null)
{
throw new ArgumentNullException("hash");
}

　　if (signature == null)
{
throw new ArgumentNullException("signature");
}

　　byte[] hashData = hash.ComputeHash(data);
byte[] signatureHashData = Decrypt(signature, privateKey);

　　if (signatureHashData != null && signatureHashData.Length == hashData.Length)
{
for (int i = 0; i < signatureHashData.Length; i++)
{
if (signatureHashData[i] != hashData[i])
{
return false;
}
}
return true;
}

　　return false;
}
 

下面是公鑰簽名->私鑰驗(yàn)證的實(shí)現(xiàn)。

public static byte[] Sign(byte[] data, RSAPrivateKey privateKey, HashAlgorithm hash)
{
if (data == null)
{
throw new ArgumentNullException("data");
}

　　if (privateKey == null)
{
throw new ArgumentNullException("privateKey");
}

　　if (hash == null)
{
throw new ArgumentNullException("hash");
}

　　byte[] hashData = hash.ComputeHash(data);
byte[] signature = Encrypt(hashData, privateKey);
return signature;
}

　　public static bool Verify(byte[] data, RSAPublicKey publicKey, HashAlgorithm hash, byte[] signature)
{
if (data == null)
{
throw new ArgumentNullException("data");
}

　　if (publicKey == null)
{
throw new ArgumentNullException("publicKey");
}

　　if (hash == null)
{
throw new ArgumentNullException("hash");
}

　　if (signature == null)
{
throw new ArgumentNullException("signature");
}

　　byte[] hashData = hash.ComputeHash(data);

　　byte[] signatureHashData = Decrypt(signature, publicKey);

　　if (signatureHashData != null && signatureHashData.Length == hashData.Length)
{
for (int i = 0; i < signatureHashData.Length; i++)
{
if (signatureHashData[i] != hashData[i])
{
return false;
}
}
return true;
}

　　return false;
}