RSA加密算法VC++实现.doc

/经过对大数运算库的算法进行初步优化，生成1024位密钥对所需时间由三分钟降志20秒以下/看来tE!的RsaTools不是高不可攀的神话，何况俺用的是自己的大数运算库！/俺将进一步优化代码，直至RsaDemo比RsaTools还快！/代码变化祥见附件 基于以下原因，俺估计RSA算法会被越来越多的共享软件采用： 1、原理简洁易懂2、加密强度高3、专利限制已过期4、看雪老大三番五次呼吁共享软件采用成熟的非对称加密技术 所以，大家应该对RSA算法进行深入了解。 俺写了一个简单易懂的大数运算库，并使用该库作了一个RSA Demo，大家可以使用这一Demo生成真正随机的、各种长度的RSA 密钥对。其中生成1024位的RSA 密钥耗时不超过五分钟，而对1024位以内的密文进行解密则不超过三秒钟，应该是可以接受的。 有一点需要说明的是，假如类似于这个Demo的RSA 工具被共享软件作者广泛用于注册码的生成与验证，俺认为Cracker 们的日子就会过得很无趣了，唉！ RSA 依赖大数运算，目前主流RSA 算法都建立在512 位到1024位的大数运算之上，所以我们在现阶段首先需要掌握1024位的大数运算原理。 大多数的编译器只能支持到64位的整数运算，即我们在运算中所使用的整数必须小于等于64位，即：0xffffffffffffffff，也就是18446744073709551615，这远远达不到RSA的需要，于是需要专门建立大数运算库来解决这一问题。 最简单的办法是将大数当作字符串进行处理，也就是将大数用10进制字符数组进行表示，然后模拟人们手工进行“竖式计算”的过程编写其加减乘除函数。但是这样做效率很低，因为1024位的大数其10进制数字个数就有数百个，对于任何一种运算，都需要在两个有数百个元素的数组空间上做多重循环，还需要许多额外的空间存放计算的进位退位标志及中间结果。当然其优点是算法符合人们的日常习惯，易于理解。 另一种思路是将大数当作一个二进制流进行处理，使用各种移位和逻辑操作来进行加减乘除运算，但是这样做代码设计非常复杂，可读性很低，难以理解也难以调试。 于是俺琢磨了一种介于两者之间的思路： 将大数看作一个n进制数组，对于目前的32位系统而言n可以取值为2的32次方，即0x10000000，假如将一个1024位的大数转化成0x10000000 进制，它就变成了32位，而每一位的取值范围就不是0-1或0-9，而是0-0xffffffff。我们正好可以用一个无符号长整数来表示这一数值。所以1024位的大数就是一个有32个元素的unsigned long数组。而且0x100000000进制的数组排列与2 进制流对于计算机来说，实际上是一回事，但是我们完全可以针对unsigned long 数组进行“竖式计算”，而循环规模被降低到了32次之内，并且算法很容易理解。 例如大数18446744073709551615，等于“ffffffff ffffffff”，它就相当于10 进制的“99”：有两位，每位都是ffffffff。而大数18446744073709551616，等于“0000000100000000 00000000”，它就相当于10进制的“100”：有三位，第一位是1 ，其它两位是0。如果我们要计算18446744073709551616-18446744073709551615，就类似于100-99：00000001 00000000 00000000- ffffffff ffffffff-= 0 0 1 当然，因为在VC里面存在一个_int64类型可以用来计算进位与借位值，所以将大数当作0x100000000进制进行运算是可能的，而在其他编译系统中如果不存在64位整形，则可以采用0x40000000进制，由于在0x40000000进制中，对任何两个“数字”进行四则运算，结果都在0x3fffffff*03fffffff之间，小于0xffffffff，都可以用一个32位无符号整数来表示。 /*/大数运算库头文件：BigInt.h/作者：/版本：1.1 (2003.5.6)/说明：适用于MFC，1024位RSA运算/*/ /在1024位RSA运算中，最大会产生2048位的中间结果#define BI_MAXLEN 65 #define DEC 10#define HEX 16 class CBigIntpublic:/符号标志，支持负值运算 int m_nSign; int m_nLength;/用32位无符号整数数组记录大数的值 unsigned long m_ulvalueBI_MAXLEN; CBigInt(); CBigInt(); /*/基本操作与运算/Mov，赋值运算，可赋值为大数或普通整数，可重载为运算符“=”/Cmp，比较运算，可重载为运算符“=”、“!=”、“=”、“=”等/Add，加，求大数与大数或大数与普通整数的和，可重载为运算符“+”/Sub，减，求大数与大数或大数与普通整数的差，可重载为运算符“-”/Mul，乘，求大数与大数或大数与普通整数的积，可重载为运算符“*”/Div，除，求大数与大数或大数与普通整数的商，可重载为运算符“/”/Mod，模，求大数与大数或大数与普通整数的模，可重载为运算符“%”/*/ CBigInt& Mov(CBigInt& A); CBigInt& Mov(unsigned _int64 A); int Cmp(CBigInt& A); CBigInt Add(CBigInt& A); CBigInt Add(long A); CBigInt Sub(CBigInt& A); CBigInt Sub(long A); CBigInt Mul(CBigInt& A); CBigInt Mul(long A); CBigInt Div(CBigInt& A); CBigInt Div(long A); CBigInt Mod(CBigInt& A); long Mod(long A); /*/输入输出/InPutFromStr，从10进制或16进制字符串输入大数/OutPutToStr，将大数按10进制或16进制格式输出到字符串/*/ void InPutFromStr(CString& str, unsigned int system=HEX); void OutPutToStr(CString& str, unsigned int system=HEX); /*/RSA相关运算/Rab，拉宾米勒算法进行素数测试/Euc，欧几里德算法求同余方程的最小整数解/Mon，蒙哥马利算法进行幂模运算/GetPrime，产生指定长度的随机素数/*/ int Rab(); CBigInt Euc(CBigInt& A); CBigInt Mon(CBigInt& A, CBigInt& B); CBigInt& GetPrime(int bits); 注意以上函数的声明格式，完全遵循普通整数运算的习惯，例如大数Y=X+Z 相当于 Y.Mov(X.(Add(Z)，这样似乎没有Mov(Y,Add(X,Z)看起来舒服，但是一旦我们重载运算符“=”为“Mov”，“+”为“Add”，则Y.Mov(X.(Add(Z)的形式就等价于 Y=X+Z。俺不知道其他编程语言里是否支持运算浮重载，至少这样定义函数格式在C+里可以带来很大的方便。 /*/大数运算库源文件：BigInt.cpp/作者：/版本：1.1 (2003.5.6)/说明：适用于MFC，1024位大数运算/*/ #include stdafx.h#include BigInt.h /小素数表const static int PrimeTable550= 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001; CBigInt:CBigInt() m_nSign=1; m_nLength=1; for(int i=0;iA.m_nLength)return 1; if(m_nLength=0;i-) if(m_ulvalueiA.m_ulvaluei)return 1; if(m_ulvalueiA.m_ulvaluei)return -1; return 0; CBigInt& CBigInt:Mov(CBigInt& A) m_nLength=A.m_nLength; for(int i=0;i0xffffffff) m_nLength=2; m_ulvalue1=(unsigned long)(A32); m_ulvalue0=(unsigned long)A; else m_nLength=1; m_ulvalue0=(unsigned long)A; for(int i=m_nLength;iBI_MAXLEN;i+)m_ulvaluei=0; return *this; /*/大数相加/调用形式：N.Add(A)/返回值：N+A/若两大数符号相同，其值相加，否则改变参数符号再调用大数相减函数/*例如： A B C+ D E-= S F G H 其中，若C+E0xffffffff，则H=C+E-0x100000000，carry=1 若B+D+carry0xffffffff，则G=B+D+carry-0x100000000，carry=1 若carry=0，则F=A，S=0 若carry=1，A0xffffffff，则F=A+1，S=0 若carry=1，A=0xffffffff，则F=0，S=1*/ /*/CBigInt CBigInt:Add(CBigInt& A) CBigInt X; if(X.m_nSign=A.m_nSign) X.Mov(*this); int carry=0; unsigned _int64 sum=0; if(X.m_nLengthA.m_nLength)X.m_nLength=A.m_nLength; for(int i=0;i0xffffffff)carry=1; else carry=0; if(X.m_nLength=0) X.Mov(*this); unsigned _int64 sum; sum=A+X.m_ulvalue0; X.m_ulvalue0=(unsigned long)sum; if(sum0xffffffff) int i=1; while(X.m_ulvaluei=0xffffffff)X.m_ulvaluei=0;i+; X.m_ulvaluei+; if(i=E，则H=C-E，carry(借位标志)=0 若C=D，则G=B-carry-D，carry=0 若B-carry1，则F=A-1 若carry=1，A=1，则F=0*/*/CBigInt CBigInt:Sub(CBigInt& A) CBigInt X; if(m_nSign=A.m_nSign) X.Mov(*this); int cmp=X.Cmp(A); if(cmp=0)X.Mov(0);return X; int len,carry=0; unsigned _int64 num; unsigned long *s,*d; if(cmp0)s=X.m_ulvalue;d=A.m_ulvalue;len=X.m_nLength; if(cmp0)s=A.m_ulvalue;d=X.m_ulvalue;len=A.m_nLength;X.m_nSign=1-X.m_nSign; for(int i=0;i=di) X.m_ulvaluei=si-carry-di; carry=0; else num=0x100000000+si; X.m_ulvaluei=(unsigned long)(num-carry-di); carry=1; while(X.m_ulvaluelen-1=0)len-; X.m_nLength=len; return X; elseX.Mov(A);X.m_nSign=1-X.m_nSign;return Add(X); CBigInt CBigInt:Sub(long A) CBigInt X; if(m_nSign*A)=0) X.Mov(*this); if(X.m_ulvalue0=(unsigned long)A)X.m_ulvalue0-=A;return X; if(X.m_nLength=1)X.m_ulvalue0=A-X.m_ulvalue0;X.m_nSign=1-X.m_nSign;return X; unsigned _int64 num=0x100000000+X.m_ulvalue0; X.m_ulvalue0=(unsigned long)(num-A); int i=1; while(X.m_ulvaluei=0)X.m_ulvaluei=0xffffffff;i+; if(X.m_ulvaluei=1)X.m_nLength-; X.m_ulvaluei-; return X; else return Add(-A); /*/大数相乘/调用形式：N.Mul(A)/返回值：N*A/*例如： A B C* D E-= S F G H+ T I J K-= U V L M N 其中，SFGH=ABC*E，TIJK=ABC*D 而对于： A B C* E-= S F G H 其中，若C*E0xffffffff，则H=(C*E)&0xffffffff carry=(C*E)/0xffffffff 若B*E+carry0xffffffff，则G=(B*E+carry)&0xffffffff carry=(B*E+carry)/0xffffffff 若A*E+carry0xffffffff，则F=(A*E+carry)&0xffffffff carry=(A*E+carry)/0xffffffff S=carry*/*/CBigInt CBigInt:Mul(CBigInt& A) CBigInt X,Y; unsigned _int64 mul; unsigned long carry; for(int i=0;iA.m_nLength;i+) Y.m_nLength=m_nLength; carry=0; for(int j=0;j32); if(carry&(Y.m_nLengthBI_MAXLEN)Y.m_nLength+;Y.m_ulvalueY.m_nLength-1=carry; if(Y.m_nLength=i;k-)Y.m_ulvaluek=Y.m_ulvaluek-i; for(k=0;ki;k+)Y.m_ulvaluek=0; X.Mov(X.Add(Y); if(m_nSign+A.m_nSign=1)X.m_nSign=0; else X.m_nSign=1; return X; CBigInt CBigInt:Mul(long A) CBigInt X; unsigned _int64 mul; unsigned long carry=0; X.Mov(*this); for(int i=0;i32); if(carry&(X.m_nLengthBI_MAXLEN)X.m_nLength+;X.m_ulvalueX.m_nLength-1=carry; if(A0) if(Y.m_ulvalueY.m_nLength-1A.m_ulvalueA.m_nLength-1) len=Y.m_nLength-A.m_nLength; div=Y.m_ulvalueY.m_nLength-1/(A.m_ulvalueA.m_nLength-1+1); else if(Y.m_nLengthA.m_nLength) len=Y.m_nLength-A.m_nLength-1; num=Y.m_ulvalueY.m_nLength-1; num=(num32); else div=num/(A.m_ulvalueA.m_nLength-1+1); else X.Mov(X.Add(1); break; Z.Mov(div); Z.m_nLength+=len; for(int i=Z.m_nLength-1;i=len;i-)Z.m_ulvaluei=Z.m_ulvaluei-len; for(i=0;i=0;i-) div=carry; div=(div32)+X.m_ulvaluei; X.m_ulvaluei=(unsigned long)(div/A); mul=(div/A)*A; carry=(unsigned long)(div-mul); if(X.m_ulvalueX.m_nLength-1=0)X.m_nLength-; if(A0) if(X.m_ulvalueX.m_nLength-1A.m_ulvalueA.m_nLength-1) len=X.m_nLength-A.m_nLength; div=X.m_ulvalueX.m_nLength-1/(A.m_