把網友的RSA加密代碼轉換到C#

實際沒做什麼事情，想起來也無恥，不過可能有些朋友比較懶的話，也會有一點用的。在此先向 duduwolf 表示歉意再說。

嘟嘟狼的原文如下：http://dev.csdn.Net/develop/article/30/30182.shtm

我的無恥成果如下（有些地方作了一些小調整）：

#region Using directives

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

#endregion

namespace rsatest
{

/*
??? RSA算法
????? 1978年就出現了這種算法，它是第一個既能用於數據加密也能用於數字簽名的算法。
??? 它易於理解和操作，也很流行。算法的名字以發明者的名字命名：Ron Rivest,
??? AdiShamir 和Leonard Adleman。但RSA的安全性一直未能得到理論上的證明。

????? RSA的安全性依賴於大數難於分解這一特點。公鑰和私鑰都是兩個大素數（大於100個
??? 十進制位）的函數。據猜測，從一個密鑰和密文推斷出明文的難度等同於分解兩個大
??? 素數的積。

????? 密鑰對的產生。選擇兩個大素數，p 和q 。計算：n = p * q 然後隨機選擇加密密鑰e，
??? 要求 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 )

????? RSA 可用於數字簽名，方案是用 ( a ) 式簽名， ( b )式驗證。具體操作時考慮到安全性
??? 和 m信息量較大等因素，一般是先作HASH 運算。RSA 的安全性。RSA的安全性依賴於大數
??? 分解，但是否等同於大數分解一直未能得到理論上的證明，因為沒有證明破解RSA就一定
??? 需要作大數分解。假設存在一種無須分解大數的算法，那它肯定可以修改成為大數分解算法。
??? 目前，RSA的一些變種算法已被證明等價於大數分解。不管怎樣，分解n是最顯然的攻擊方法。
??? 現在，人們已能分解140多個十進制位的大素數。因此，模數n必須選大一些，因具體適用情況而定。
???
??? 由於進行的都是大數計算，使得RSA最快的情況也比DES慢上100倍，無論是軟件還是硬件實現。
??? 速度一直是RSA的缺陷。一般來說只用於少量數據加密。
*/
??? public struct RSA_PARAM
??? {
??????? public UInt64 p, q;?? //兩個素數，不參與加密解密運算
??????? public UInt64 f;????? //f=(p-1)*(q-1)，不參與加密解密運算
??????? public UInt64 n, e;?? //公匙，n=p*q，gcd(e,f)=1
??????? public UInt64 d;????? //私匙，e*d=1 (mod f)，gcd(n,d)=1
??????? public UInt64 s;????? //塊長，滿足2^s<=n的最大的s，即log2(n)
??? };

??? class Program
??? {
??????? //小素數表
??????? #region Prime Table
??????? readonly static long[] g_PrimeTable =
??????? {
??????????? 3,
??????????? 5,
??????????? 7,
??????????? 11,
??????????? 13,
??????????? 17,
??????????? 19,
??????????? 23,
??????????? 29,
??????????? 31,
??????????? 37,
??????????? 41,
??????????? 43,
??????????? 47,
??????????? 53,
??????????? 59,
??????????? 61,
??????????? 67,
??????????? 71,
??????????? 73,
??????????? 79,
??????????? 83,
??????????? 89,
??????????? 97
??????? };
??????? #endregion

??????? readonly long g_PrimeCount = g_PrimeTable.Length;
??????? const UInt64 multiplIEr = 12747293821;
??????? const UInt64 adder = 1343545677842234541;

??????? //隨機數類
??????? public class RandNumber
??????? {
??????????? /* */
??????????? private UInt64 randSeed;/* */
??????????? public RandNumber():this(0) { }

??????????? public RandNumber(UInt64 s)
??????????? {
??????????????? if (0 == s)//(!s)
??????????????? {
??????????????????? randSeed = (UInt64)new Random().Next();//time(NULL);
??????????????? }
??????????????? else
??????????????? {
??????????????????? randSeed = s;
??????????????? }
??????????? }
???????????
??????????? /* */
??????????? public UInt64 Random(UInt64 n)
??????????? {
??????????????? randSeed = multiplIEr * randSeed + adder;
??????????????? return randSeed % n;
??????????? }
??????? }

??????? static RandNumber g_Rnd = new RandNumber();

??????? /* 模乘運算，返回值 x=a*b mod n */
??????? UInt64 MulMod(UInt64 a, UInt64 b, UInt64 n)
??????? {
??????????? return a * b % n;
??????? }

??????? /* 模冪運算，返回值 x=base^pow mod n */
??????? UInt64 PowMod(UInt64 bas, UInt64 pow, UInt64 n)
??????? {
??????????? UInt64 a = bas, b = pow, c = 1;
??????????? while (b != 0)? // (b)
??????????? {
??????????????? while (1 != (b & 1))??? // !(b&1)
??????????????? {
??????????????????? b >>= 1;??????????? //a=a * a % n;??? //函數看起來可以處理64位的整數，但由於這裡a*a在a>=2^32時已經造成了溢出，因此實際處理范圍沒有64位
??????????????????? a = MulMod(a, a, n);
??????????????? } b--;??????? //c=a * c % n;??????? //這裡也會溢出，若把64位整數拆為兩個32位整數不知是否可以解決這個問題。
??????????????? c = MulMod(a, c, n);
??????????? } return c;
??????? }

??????? /*
??????? Rabin-Miller素數測試，通過測試返回1，否則返回0。
??????? n是待測素數。
??????? 注意：通過測試並不一定就是素數，非素數通過測試的概率是1/4
??????? */
??????? long RabinMillerKnl(UInt64 n)
??????? {
??????????? UInt64 b, m, j, v, i;
??????????? m = n - 1;
??????????? j = 0;??? //0、先計算出m、j，使得n-1=m*2^j，其中m是正奇數，j是非負整數
??????????? while (1 != (m&1))??? // (!(m & 1))
??????????? {
??????????????? ++j;
??????????????? m >>= 1;
??????????? }??? //1、隨機取一個b，2<=b??????????? b = 2 + g_Rnd.Random(n - 3);??? //2、計算v=b^m mod n
??????????? v = PowMod( b,? m,? n);??? //3、如果v==1，通過測試
??????????? if (v == 1)
??????????? {
??????????????? return 1;
??????????? }??? //4、令i=1
??????????? i = 1;??? //5、如果v=n-1，通過測試
??????????? while (v != n - 1)
??????????? {
??????????????? //6、如果i==l，非素數，結束
??????????????? if (i == j)
??????????????? {
??????????????????? return 0;
??????????????? }??????? //7、v=v^2 mod n，i=i+1
??????????????? v = PowMod( v, 2,? n);
??????????????? ++i;??????? //8、循環到5
??????????? } return 1;
??????? }

??????? /*
??????? Rabin-Miller素數測試，循環調用核心loop次
??????? 全部通過返回1，否則返回0
??????? */
??????? long RabinMiller(UInt64 n, long loop)
??????? {
??????????? //先用小素數篩選一次，提高效率
??????????? for (long i = 0; i < g_PrimeCount; i++)
??????????? {
??????????????? if ((n % unchecked((ulong)g_PrimeTable[i])) == 0)
??????????????? {
??????????????????? return 0;
??????????????? }
??????????? }

??????????? //循環調用Rabin-Miller測試loop次，使得非素數通過測試的概率降為(1/4)^loop
??????????? for (long i = 0; i < loop; i++)
??????????? {
??????????????? if (0 == RabinMillerKnl(n)) //(! ...)
??????????????? {
??????????????????? return 0;
??????????????? }
??????????? } return 1;
??????? }
??????? /* 隨機生成一個bits位(二進制位)的素數，最多32位 */
??????? UInt64 RandomPrime(char bits)
??????? {
??????????? UInt64 bas;
??????????? do
??????????? {
??????????????? bas = (UInt32)1 << (bits - 1);?? //保證最高位是1
??????????????? bas += g_Rnd.Random(bas);?????????????? //再加上一個隨機數
??????????????? bas |= 1;??? //保證最低位是1，即保證是奇數
??????????? } while (0 == RabinMiller(bas, 30)); // (!RabinMiller(bas,30)) //進行拉賓－米勒測試30次
??????????? return bas;??? //全部通過認為是素數
??????? }

??????? /* 歐幾裡得法求最大公約數 */
??????? UInt64 EuclidGcd(UInt64 p, UInt64 q)
??????? {
??????????? UInt64 a = p > q ? p : q;
??????????? UInt64 b = p < q ? p : q;
??????????? UInt64 t;
??????????? if (p == q)
??????????? {
??????????????? return p;?? //兩數相等，最大公約數就是本身
??????????? }
??????????? else
??????????? {
??????????????? while (0 != b) //(b)??? //輾轉相除法，gcd(a,b)=gcd(b,a-qb)
??????????????? {
??????????????????? a = a % b;
??????????????????? t = a;
??????????????????? a = b;
??????????????????? b = t;
??????????????? } return a;
??????????? }
??????? }
??????? /* Stein法求最大公約數 */
??????? UInt64 SteinGcd( UInt64 p,? UInt64 q)
??????? {
??????????? UInt64 a = p > q ? p : q;
??????????? UInt64 b = p < q ? p : q;
??????????? UInt64 t, r = 1;
??????????? if (p == q)
??????????? {
??????????????? return p;?????????? //兩數相等，最大公約數就是本身
??????????? }
??????????? else
??????????? {
??????????????? //while ((!(a & 1)) && (!(b & 1)))
??????????????? while ((0 ==(a & 1)) && (0 ==(b & 1)))
??????????????? {
??????????????????? r <<= 1;????????? //a、b均為偶數時，gcd(a,b)=2*gcd(a/2,b/2)
??????????????????? a >>= 1;
??????????????????? b >>= 1;
??????????????? }
??????????????? if (0 == (a&1))//(!(a & 1))
??????????????? {
??????????????????? t = a;??????????? //如果a為偶數，交換a，b
??????????????????? a = b;
??????????????????? b = t;
??????????????? } do
??????????????? {
??????????????????? while (0 == (b & 1))//(!(b & 1))
??????????????????? {
??????????????????????? b >>= 1;????? //b為偶數，a為奇數時，gcd(b,a)=gcd(b/2,a)
??????????????????? } if (b < a)
??????????????????? {
??????????????????????? t = a;??????? //如果b小於a，交換a，b
??????????????????????? a = b;
??????????????????????? b = t;
??????????????????? } b = (b - a) >> 1; //b、a都是奇數，gcd(b,a)=gcd((b-a)/2,a)
??????????????? } while (b != 0); //(b);
??????????????? return r * a;
??????????? }
??????? }

??????? /*
??????? 已知a、b，求x，滿足a*x =1 (mod b)
??????? 相當於求解a*x-b*y=1的最小整數解
??????? */
??????? UInt64 Euclid(UInt64 a, UInt64 b)
??????? {
??????????? UInt64 m, e, i, j, x, y;
??????????? long xx, yy;
??????????? m = b;
??????????? e = a;
??????????? x = 0;
??????????? y = 1;
??????????? xx = 1;
??????????? yy = 1;
??????????? while (0 != e)//(e)
??????????? {
??????????????? i = m / e;
??????????????? j = m % e;
??????????????? m = e;
??????????????? e = j;
??????????????? j = y;
??????????????? y *= i;
??????????????? if (xx == yy)
??????????????? {
??????????????????? if (x > y)
??????????????????? {
??????????????????????? y = x - y;
??????????????????? }
??????????????????? else
??????????????????? {
??????????????????????? y -= x;
??????????????????????? yy = 0;
??????????????????? }
??????????????? }
??????????????? else
??????????????? {
??????????????????? y += x;
??????????????????? xx = 1 - xx;
??????????????????? yy = 1 - yy;
??????????????? } x = j;
??????????? }
??????????? if (xx == 0)
??????????? {
??????????????? x = b - x;
??????????? } return x;
??????? }

??????? /* 隨機產生一個RSA加密參數 */
??????? RSA_PARAM RsaGetParam()
??????? {
??????????? RSA_PARAM Rsa =new RSA_PARAM();
??????????? UInt64 t;
??????????? Rsa.p = RandomPrime((char)16);????????? //隨機生成兩個素數
??????????? Rsa.q = RandomPrime((char)16);
??????????? Rsa.n = Rsa.p * Rsa.q;
??????????? Rsa.f = (Rsa.p - 1) * (Rsa.q - 1);
??????????? do
??????????? {
??????????????? Rsa.e = g_Rnd.Random(65536);? //小於2^16，65536=2^16
??????????????? Rsa.e |= 1;?????????????????? //保證最低位是1，即保證是奇數，因f一定是偶數，要互素，只能是奇數
??????????? } while (SteinGcd(Rsa.e, Rsa.f) != 1); Rsa.d = Euclid(Rsa.e, Rsa.f);
??????????? Rsa.s = 0;
??????????? t = Rsa.n >> 1;
??????????? while (0 != t)//(t)
??????????? {
??????????????? Rsa.s++;??????????????????? //s=log2(n)
??????????????? t >>= 1;
??????????? } return Rsa;
??????? }

??????? /* 拉賓－米勒測試 */
??????? void TestRM()
??????? {

UInt32 k = 0;
Console.Write(" - Rabin-Miller prime check.\n\n"); 
for (UInt64 i = 4197900001; i < 4198000000; i += 2)
{ 
if (0 != RabinMiller(i, 30)) 
{ 
k++; 
Console.WriteLine(i);
} 
}
Console.WriteLine("Total: " + k); 
} 

/* RSA加密解密 */ 
void TestRSA() 
{ 
RSA_PARAM r; 
string pSrc = "abcdefghijklmnopqrstuvwxyz"; 
UInt32 n = (uint)pSrc.Length; 
//unsigned char?????? *q, pDec[n]; 
byte[] pDec = new byte[n];
??????????? UInt64[] pEnc = new UInt64[n];
??????????? r = RsaGetParam();
??????????? Console.WriteLine("p=" + r.p);
??????????? Console.WriteLine("q=" + r.q);
??????????? Console.WriteLine("f=(p-1)*(q-1)=" + r.f);
??????????? Console.WriteLine("n=p*q=" + r.n);
??????????? Console.WriteLine("e=" + r.e);
??????????? Console.WriteLine("d=" + r.d);
??????????? Console.WriteLine("s=" + r.s);
??????????? Console.WriteLine("Source:" + pSrc);
??????????? //q= (unsigned char *)pSrc;
??????????? Console.Write("Encode:");
??????????? for (int i = 0; i < (int)n; i++)
??????????? {
??????????????? //pEnc[i]=PowMod(q[i], r.e, r.n);
??????????????? pEnc[i] = PowMod((ulong)pSrc[i], r.e, r.n);
??????????????? Console.Write(pEnc[i].ToString() + " ");
??????????? } Console.WriteLine("");
??????????? Console.Write("Decode:");
??????????? for (int i = 0; i < (int)n; i++)
??????????? {
??????????????? pDec[i] = (byte)PowMod((ulong)pEnc[i], r.d, r.n);
??????????????? Console.Write((UInt32)pDec[i] + " ");
??????????? } Console.WriteLine("");
??????????? Console.WriteLine(Encoding.Default.GetString(pDec));
??????? }/* */


??????? static void Main(string[] args)
??????? {
??????????? new Program().TestRSA();

??????? }
??? }

}