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

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

　　RSA算法實現主要分為三部分：包括公鑰和私鑰的產生，非對稱加密和解密，數字簽名和驗證，下面將逐個介紹RSA算法的工作原理及我的實現方法。

　　1、公鑰和私鑰的產生

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

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

　　在.NET Framework的RSA算法中，e對應RSAParameters.Exponent；d對應RSAParameters.D；n對應RSAParameters.ModulusExponent。.NET Framework中的RSA算法默認使用1024位長的密鑰。公鑰和私鑰是利用.NET Framework的RSACryptoServiceProvider生成公鑰xml文件和私鑰xml文件來實現的。生成公鑰和私鑰xml文件的程序本身不是Silverlight程序。

RSACryptoServiceProvider rsa = new RSACryptoServiceProvider();

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

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

公鑰和私鑰將從生成的公鑰xml文件和私鑰xml文件中導入。

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、非對稱加密和解密

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

　　在某些情況下，也會使用公鑰加密->私鑰解密。原理和私鑰加密->公鑰解密一樣。下面是私鑰計算和公鑰計算的算法。其中利用到了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（二進制表示）分成數據塊 m1, m2, ..., mi ，然后進行運算。
//
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（二進制表示）分成數據塊 c1, c2, ..., ci ，然后進行運算。
//
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();
}
}
 

下面是私鑰加密->公鑰解密的實現。

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);
}
 

下面是公鑰加密->私鑰解密的實現。

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、數字簽名和驗證

　　私鑰簽名數據m時，先對m進行hash計算，得到計算結果h。然后將h使用私鑰加密，得到加密后的密文s即為簽名。
公鑰驗證簽名s時，先將m進行hash計算，得到計算結果h。然后使用公鑰解密s得到結果h’。如果h==h’即驗證成功，否則驗證失敗。

　　在某些情況下，也會使用公鑰簽名->私鑰驗證。原理和私鑰簽名->公鑰驗證一樣。

　　下面是私鑰簽名->公鑰驗證的實現。

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;
}
 

下面是公鑰簽名->私鑰驗證的實現。

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;
}