实际没做什么事情，想起来也无耻，不过可能有些朋友比较懒的话，也会有一点用的。在此先向 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;??????? }[page]

??????? /*??????? 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

??????? /*??????? 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();

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

中国.Net俱乐部转载此文。让我们一起进步，共享人类技术资源。[www.chinaaspx.com]