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