《RSA算法设计实现分析.doc》由会员分享，可在线阅读，更多相关《RSA算法设计实现分析.doc（16页珍藏版）》请在课桌文档上搜索。
1、题目名称：RSA加密解密的设计与实现一、 设计原理算法工作原理RSA 原理：RSA 密钥的选取和加解密过程都非常简洁，在算法上主要要实现四个问题：1、如何处理大数运算2、如何求解同余方程 *Y % M = 13、如何快速进展模幂运算4、如何获取大素数(一) 大数存储RSA 依赖大数运算，目前主流RSA 算法都建立在1024位的大数运算之上。而大多数的编译器只能支持到64位的整数运算，即我们在运算中所使用的整数必须小于等于64位，即：0*ffffffffffffffff，也就是615，这远远达不到RSA 的需要，于是需要专门建立大数运算库来解决这一问题。一个有效的改进方法是将大数表示为一个n 进
2、制数组，对于目前的32位系统而言n 可以取值为2 的32次方，即 0*100000000，假设将一个二进制为1024位的大数转化成0*10000000进制，就变成了32位，而每一位的取值围不再是二进制的01或十进制的09，而是0-0*ffffffff，我们正好可以用一个32位的DWORD 如：无符号长整数，unsigned long 类型来表示该值。所以1024位的大数就变成一个含有32个元素的 DWORD数组，而针对 DWORD数组进展各种运算所需的循环规模至多32次而已。而且0*100000000 进制与二进制，对于计算机来说，几乎是一回事，转换非常容易。例如：大数615，等于 0*fff
3、fffff ffffffff，就相当于十进制的99：有两位，每位都是0*ffffffff。而616等于0*00000001；00000000 00000000，就相当于十进制的100：有三位，第一位是1 ，其它两位都是0 ，如此等等。在实际应用中，“数字数组的排列顺序采用低位在前高位在后的方式，这样，大数A 就可以方便地用数学表达式来表示其值：A=Sumi=0 to n(A*r*i)，r=0*100000000，0=A=B：A=Sumi=0 to p(A*r*i)B=Sumi=0 to q(B*r*i)C=Sumi=0 to n(C*r*i)r=0*100000000，0=A,B,C=q则当C
4、=A+B、C=A-B、C=A*B时，我们都可以通过计算出C来获得C：C=A+B，显然C不总是等于A+B，因为A+B可能0*ffffffff，而C必须=0*ffffffff，这时就需要进位，当然在计算Ci-1时也可能产生了进位，所以计算C时还要加上上次的进位值。如果用一个64位变量result来记录和，另一个32位变量carry来记录进位，则有：carry=0FOR i FROM 0 TO presult=A+B+carryC=result%0*100000000carry=result/0*100000000IF carry=0 n=pELSE n=p+1C=A-B，同理C不总是等于A-B，因
5、为A-B可能=0，这时就需要借位，同样在计算Ci-1时也可能产生了借位，所以计算C时还要减去上次的借位值：carry=0FOR i FROM 0 TO pIF A-B-carry=0C=A-B-carrycarry=0ELSEC=0*100000000+A-B-carrycarry=1n=pWHILE Cn=0 n=n-1C=A*B，首先我们需要观察日常做乘法所用的“竖式计算过程：A3 A2 A1 A0* B2 B1 B0-= A3B0 A2B0 A1B0 A0B0+ A3B1 A2B1 A1B1 A0B1+ A3B2 A2B2 A1B2 A0B2-= C5 C4 C3 C2 C1 C0可以归
6、纳出：C=Sumj=0 to q(Ai-j*Bj)，其中i-j必须=0且=p。当然这一结论没有考虑进位，虽然计算Ai-j*Bj和Sum的时候都可能发生进位，但显然这两种原因产生的进位可以累加成一个进位值。最终可用如下算法完成乘法：n=p+q-1carry=0For i FROM 0 TO nresult=carryFor j FROM 0 TO qIF 0=i-j=p result=result+Ai-j*BjC=result%0*100000000carry=result/0*100000000IF carry!=0n=n+1Cn=carry对于C=A/B，由于无法将B 对A“试商，我们只能
7、转换成Bq对Ap的试商来得到一个近似值，所以无法直接通过计算C来获得C，只能一步步逼近C。由于：B*(Ap/Bq-1)*0*100000000*(p-q)C，令：*=0，重复A=A-*B，*=*+(Ap/Bq-1)*0*100000000*(p-q)，直到Ab 11 * - 5 y = 1 11%5 =1 -c * - 5 y = 1令y=0 代入c得*=1令*=1 代入b得y=2令y=2 代入a得*=9同理可使用递归算法求得任意 a*-by=1a、b互质的解。实际上通过分析归纳将递归算法转换成非递归算法就变成了大衍求一术：*=0,y=1WHILE a!=0i=yy=*-y*a/b*=ii=a
8、a=b%ab=iIF *=0IF E%2=0C=C*C % NE=E/2ELSED=D*C % NE=E-1RETURN D继续分析会发现，要知道E 何时能整除 2，并不需要反复进展减一或除二的操作，只需验证E 的二进制各位是0 还是1 就可以了，从左至右或从右至左验证都可以，从左至右会更简洁，设E=Sumi=0 to n(E*2*i)，0=E=1，则：D=1FOR i=n TO 0D=D*D % NIF E=1 D=D*C % NRETURN D这样，模幂运算就转化成了一系列的模乘运算。(五) 蒙哥马利模乘由于RSA 的核心算法是模幂运算，模幂运算又相当于模乘运算的循环，要提高RSA 算法的
9、效率，首要问题在于提高模乘运算的效率。不难发现，模乘过程中复杂度最高的环节是求模运算，因为一次除法实际上包含了屡次加法、减法和乘法，如果在算法中能够尽量减少除法甚至防止除法，则算法的效率会大大提高。设A=Sumi=0 to k(A*2*i)，0=A=N C=C-NRETURN C由于在RSA中A、B总是小于N，又0=A,C0=1，所以：C = (C+A*B+C0*N)/2C (C+2N)/22C C+2NC 2N既然C总是小于2N，所以求C %N 就可以很简单地在完毕循环后用一次减法来完成，即在求A*B*2*(-k) %N的过程中不用反复求模，到达了我们防止做除法的目的。当然，这一算法求得的是
10、A*B*2*(-k) %N，而不是我们最初需要的A*B %N。但是利用A*B*2*(-k)我们同样可以求得A*E %N。设R=2*k %N，R=2*(-k) %N，E=Sumi=0 to n(E*2*i)：A=A*R %N*=AFOR i FROM n TO 0*=*R %NIF E=1 *=*A*R %N*=*1*R %NRETURN *最初：* = A*R %N，开场循环时：* = *R %N= A*R*A*R*R %N = A*2*R %N反复循环之后：* = A*E*R %N最后：* = *1*R %N= A*E*R*R %N= A*E %N如此，我们最终实现了不含除法的模幂算法，这就
11、是著名的蒙哥马利算法，而*Y*R %N 则被称为“蒙哥马利模乘。以上讨论的是蒙哥马利模乘最简单，最容易理解的二进制形式。蒙哥马利算法的核心思想在于将求A*B %N转化为不需要反复取模的A*B*R %N，但是利用二进制算法求1024位的A*B*R %N，需要循环1024次之多，必然希望找到更有效的计算A*B*R %N的算法。考虑将A表示为任意的r进制：A = Sumi=0 to k(A*r*i) 0=A=N C=C-NRETURN C因为在循环中每次C=C/r 时，都可能有余数被舍弃。假设我们能够找到一个系数 q，使得(C + A*B + q*N) %r =0，并将算法修改为：C=0FOR i
12、FROM 0 TO kC=C+A*B+q*NC=C/rIF C=N C=C-NRETURN C则C的最终返回值就是A*B*R %N的准确值，所以关键在于求q。由于：(C + A*B + q*N) %r =0= (C %r + A*B %r + q*N %r) %r =0= (C0 + A*B0 + q*N0) %r =0假设令N0*N0 %r =1，q=(C0+A*B0)*(r-N0) %r，则：(C0 + A*B0 + q*N0) %r= (C0+A*B0 - (C0+A*B0)*N0*N0) %r) %r= 0于是我们可以得出r为任何值的蒙哥马利算法：m=r-N0C=0FOR i FROM
13、 0 TO kq=(C0+A*B0)*m %rC=(C+A*B+q*N)/rIF C=N C=C-NRETURN C如果令 r=0*100000000，则 %r 和 /r 运算都会变得非常容易，在1024位的运算中，循环次数k 不大于32，整个运算过程中最大的中间变量C=(C+A*B+q*N) 2*r*N 1057位，算法效率就相当高了。唯一的额外负担是需要计算 N0，使N0*N0 %r =1，而这一问题前面已经用欧几里德算法解决过了，而且在模幂运算转化成反复模乘运算时，N是固定值，所以N0只需要计算一次，负担并不大。(六) 素数测试方法数论学家利用费马小定理研究出了多种素数测试方法，目前最快
14、的算法是拉宾米勒测试算法，其过程如下：1计算奇数M，使得N=(2*r)*M+12选择随机数AN3对于任意ir，假设A*(2*i)*M) % N = N-1，则N通过随机数A的测试4或者，假设A*M % N = 1，则N通过随机数A的测试5让A取不同的值对N进展5次测试，假设全部通过则判定N为素数假设N 通过一次测试，则N 不是素数的概率为 25%，假设N 通过t 次测试，则N 不是素数的概率为1/4*t。事实上取t 为5 时，N 不是素数的概率为 1/128，N 为素数的概率已经大于99.99%。在实际应用中，可首先用300500个小素数对N 进展测试，以提高拉宾米勒测试通过的概率，从而提高整
15、体测试速度。而在生成随机素数时，选取的随机数最好让r=0，则可省去步骤3 的测试，进一步提高测试速度。素数测试是RSA 选取秘钥的第一步，奇妙的是其核心运算与加解密时所需的运算完全一致：都是模幂运算。而模幂运算过程中中所需求解的欧几里德方程又恰恰正是选取密钥第二步所用的运算。二、 系统功能描述与软件模块划分CBIGINT类用以实现大素数的加、减、乘、除CBigInt Add( CBigInt& A); /实现大素数加法CBigInt Sub(CBigInt& A); /实现大素数减法CBigInt Mul(CBigInt& A); /实现大素数乘法CBigInt Div(CBigInt& A)
16、; /实现大素数除法CBigInt Mod( CBigInt& A); /实现大素数模运算CBigInt Add(unsigned long A); CBigInt Sub(unsigned long A); CBigInt Mul(unsigned long A); CBigInt Div(unsigned long A);RSA类用以实现素数检测、生成密钥、加密解密CBigInt Euc(CBigInt& A) ;/素数检测void GetKey(int len,CBigInt &p,CBigInt &q,CBigInt &n,CBigInt &_n,CBigInt &e,CBigInt
17、&d);/获得密钥void RsaJiami(char* m,char *c,CBigInt e,CBigInt n);/加密void RsaJiemi(char* c,char *m,CBigInt d,CBigInt n);/解密三、 设计核心代码*includeBigInt.h*includetime.h*includestring*includeusing namespace std;const static int PrimeTable550= 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 7
18、1, 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, 41
19、9, 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, 81
20、1, 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,
21、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,
22、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,
23、1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2021, 2021, 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,
24、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,
25、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,
26、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,
27、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,
28、3931, 3943, 3947, 3967, 3989, 4001 ; const static long Primecount=sizeof(PrimeTable)/sizeof(long);CBigInt:CBigInt() /构造大数对象并初始化为零 m_nLength=1; for(int i=0;iA返回1，*=A返回0，*A.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; void CB
29、igInt:Mov(CBigInt& A) /把A的值赋给* m_nLength=A.m_nLength; for(int i=0;i0*ffffffff) 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_MA*LEN;i+)m_ulValuei=0; CBigInt CBigInt:Add(CBigInt& A) /加法 CBigInt *; *.Mo
30、v(*this); unsigned carry=0; unsigned _int64 sum=0; if(*.m_nLengthA.m_nLength)*.m_nLength=A.m_nLength; for(unsigned i=0;i32); *.m_ulValue*.m_nLength=carry; *.m_nLength+=carry; return *; CBigInt CBigInt:Add(unsigned long A) CBigInt *; *.Mov(*this); unsigned _int64 sum; sum=*.m_ulValue0; sum+=A; *.m_ul
31、Value0=(unsigned long)sum; if(sum0*ffffffff) unsigned i=1; while(*.m_ulValuei=0*ffffffff)*.m_ulValuei=0;i+; *.m_ulValuei+; if(m_nLength=i)m_nLength+; return *; CBigInt CBigInt:Sub(CBigInt& A) /减法 CBigInt *; *.Mov(*this); if(*.Cmp(A)=0)*.Mov(0);return *; unsigned carry=0; unsigned _int64 num; unsigne
32、d i; for(i=0;iA.m_ulValuei)|(m_ulValuei=A.m_ulValuei)&(carry=0) *.m_ulValuei=m_ulValuei-carry-A.m_ulValuei; carry=0; else num=0*100000000+m_ulValuei; *.m_ulValuei=(unsigned long)(num-carry-A.m_ulValuei); carry=1; while(*.m_ulValue*.m_nLength-1=0)*.m_nLength-; return *; CBigInt CBigInt:Sub(unsigned l
33、ong A) CBigInt *; *.Mov(*this); if(*.m_ulValue0=A)*.m_ulValue0-=A;return *; if(*.m_nLength=1)*.Mov(0);return *; unsigned _int64 num=0*100000000+*.m_ulValue0; *.m_ulValue0=(unsigned long)(num-A); int i=1; while(*.m_ulValuei=0)*.m_ulValuei=0*ffffffff;i+; *.m_ulValuei-; if(*.m_ulValuei=0)*.m_nLength-;
34、return *; CBigInt CBigInt:Mul( CBigInt& A) /乘法 if(A.m_nLength=1)return Mul(A.m_ulValue0); CBigInt *; unsigned _int64 sum,mul=0,carry=0; unsigned i,j; *.m_nLength=m_nLength+A.m_nLength-1; for(i=0;i*.m_nLength;i+) sum=carry; carry=0; for(j=0;j=0)&(i-j)32; mul=mul&0*ffffffff; sum+=mul; carry+=sum32; *.m_ulValuei=(unsigned long)sum; if(carry)*.m_nLength+;*.m_ulValue*.m_nLength-1=(unsigned long)carry; return *; CBigInt CBigInt:Mul(unsigned long A) CBigInt *; unsigned _int64 mul; unsigned long carry=0; *.Mov(*this);
