把网友的RSA加密代码转换到C#

本质没做什么工作，想起来也无耻，然而大概有些伙伴比拟懒的话，也会有一点用的。在此先向 duduwolf 表白歉意再说。嘟嘟狼的原文如次：http://dev.csdn.net/develop/article/30/30182.shtm我的无耻功效如次（有些场合作了少许小安排）：#region using directivesusing system;using system.collections.generic;using system.text;using system.diagnostics;#endregionnamespace 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();??????? }??? }}