《RSA算法设计与实现.doc》由会员分享，可在线阅读，更多相关《RSA算法设计与实现.doc（19页珍藏版）》请在课桌文档上搜索。
1、word某某大学密码学课程设计报告题目名称：RSA加密解密的设计与实现姓 名：学 号：专 业：一、 设计原理算法工作原理RSA 原理：RSA 密钥的选取和加解密过程都非常简洁，在算法上主要要实现四个问题：1、如何处理大数运算2、如何求解同余方程 XY % M = 13、如何快速进展模幂运算4、如何获取大素数(一) 大数存储一个有效的改良方法是将大数表示为一个n 进制数组，对于目前的32位系统而言n 可以取值为2 的32次方，即 0x100000000，假设将一个二进制为1024位的大数转化成0x10000000进制，就变成了32位，而每一位的取值X围不再是二进制的01或十进制的09，而是0-0
2、xffffffff，我们正好可以用一个32位的DWORD 如：无符号长整数，unsigned long 类型来表示该值。所以1024位的大数就变成一个含有32个元素的 DWORD数组，而针对 DWORD数组进展各种运算所需的循环规模至多32次而已。而且0x100000000 进制与二进制，对于计算机来说，几乎是一回事，转换非常容易。“数字数组的排列顺序采用低位在前高位在后的方式，这样，大数A 就可以方便地用数学表达式来表示其值：A=Sumi=0 to n(A*r*i)，r=0x100000000，0=A=B：A=Sumi=0 to p(A*r*i)B=Sumi=0 to q(B*r*i)C=S
3、umi=0 to n(C*r*i)r=0x100000000，0=A,B,C=q如此当C=A+B、C=A-B、C=A*B时，我们都可以通过计算出C来获得C：C=A+B，显然C不总是等于A+B，因为A+B可能0xffffffff，而C必须=0xffffffff，这时就需要进位，当然在计算Ci-1时也可能产生了进位，所以计算C时还要加上上次的进位值。如果用一个64位变量result来记录和，另一个32位变量carry来记录进位，如此有： carry=0FOR i FROM 0 TO presult=A+B+carryC=result%0x100000000carry=result/0x100000
4、000IF carry=0 n=pELSE n=p+1C=A-B，同理C不总是等于A-B，因为A-B可能=0，这时就需要借位，同样在计算Ci-1时也可能产生了借位，所以计算C时还要减去上次的借位值：carry=0FOR i FROM 0 TO pIF A-B-carry=0C=A-B-carrycarry=0ELSEC=0x100000000+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 A0
5、B1+ A3B2 A2B2 A1B2 A0B2-= C5 C4 C3 C2 C1 C0可以归纳出：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%0x100000000carry=result/0x100000000IF
6、carry!=0n=n+1Cn=carry对于C=A/B，由于无法将B 对A“试商，我们只能转换成Bq对Ap的试商来得到一个近似值，所以无法直接通过计算C来获得C，只能一步步逼近C。由于：B*(Ap/Bq-1)*0x100000000*(p-q)C，令：X=0，重复A=A-X*B，X=X+(Ap/Bq-1)*0x100000000*(p-q)，直到Ab 11 x - 5 y = 1 11%5 =1 -c x - 5 y = 1令y=0 代入c得x=1令x=1 代入b得y=2令y=2 代入a得x=9同理可使用递归算法求得任意 ax-by=1a、b互质的解。实际上通过分析归纳将递归算法转换成非递归
7、算法就变成了大衍求一术：x=0,y=1WHILE a!=0i=yy=x-y*a/bx=ii=aa=b%ab=iIF x=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这样，模幂运算就转化成了一系列的模乘运算。(五) 蒙
8、哥马利模乘由于RSA 的核心算法是模幂运算，模幂运算又相当于模乘运算的循环，要提高RSA 算法的效率，首要问题在于提高模乘运算的效率。不难发现，模乘过程中复杂度最高的环节是求模运算，因为一次除法实际上包含了屡次加法、减法和乘法，如果在算法中能够尽量减少除法甚至防止除法，如此算法的效率会大大提高。设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 就可以很简单地在完毕循环后用一次减法来完成，即在求
9、A*B*2*(-k) %N的过程中不用反复求模，达到了我们防止做除法的目的。当然，这一算法求得的是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 %NX=AFOR i FROM n TO 0X=X*X*R %NIF E=1 X=X*A*R %NX=X*1*R %NRETURN X最初：X = A*R %N，开始循环时：X = X*X*R %N= A*R*A*R*R %N = A*2*R %N反复循环之后：X = A*E*R %
10、N最后：X = X*1*R %N= A*E*R*R %N= A*E %N如此，我们最终实现了不含除法的模幂算法，这就是著名的蒙哥马利算法，而X*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 时，都可能有余数
11、被舍弃。假设我们能够找到一个系数 q，使得(C + A*B + q*N) %r =0，并将算法修改为：C=0FOR i 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+
12、A*B0)*N0*N0) %r) %r= 0于是我们可以得出r为任何值的蒙哥马利算法：m=r-N0C=0FOR i FROM 0 TO kq=(C0+A*B0)*m %rC=(C+A*B+q*N)/rIF C=N C=C-NRETURN C如果令 r=0x100000000，如此 %r 和 /r 运算都会变得非常容易，在1024位的运算中，循环次数k 不大于32，整个运算过程中最大的中间变量C=(C+A*B+q*N) 2*r*N 1057位，算法效率就相当高了。唯一的额外负担是需要计算 N0，使N0*N0 %r =1，而这一问题前面已经用欧几里德算法解决过了，而且在模幂运算转化成反复模乘运算时
13、，N是固定值，所以N0只需要计算一次，负担并不大。(六) 素数测试方法数论学家利用费马小定理研究出了多种素数测试方法，目前最快的算法是拉宾米勒测试算法，其过程如下：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，
14、N 为素数的概率已经大于99.99%。在实际应用中，可首先用300500个小素数对N 进展测试，以提高拉宾米勒测试通过的概率，从而提高整体测试速度。而在生成随机素数时，选取的随机数最好让r=0，如此可省去步骤3 的测试，进一步提高测试速度。素数测试是RSA 选取秘钥的第一步，奇妙的是其核心运算与加解密时所需的运算完全一致：都是模幂运算。而模幂运算过程中中所需求解的欧几里德方程又恰恰正是选取密钥第二步所用的运算。二、 系统功能描述与软件模块划分CBIGINT类用以实现大素数的加、减、乘、除CBigInt Add( CBigInt& A); /实现大素数加法CBigInt Sub(CBigInt&
15、 A); /实现大素数减法CBigInt Mul(CBigInt& A); /实现大素数乘法CBigInt Div(CBigInt& A); /实现大素数除法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
16、 len,CBigInt &p,CBigInt &q,CBigInt &n,CBigInt &_n,CBigInt &e,CBigInt &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
17、, 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
18、, 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
19、, 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, 109
20、7, 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, 148
21、1, 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, 186
22、1, 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, 224
23、3, 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, 265
24、7, 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, 302
25、3, 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, 346
26、1, 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, 385
27、1, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 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，X=A返回0，XA.m_nLength)return 1; if(m_nLength=0;i-) if(m_ulValueiA.m_ulVa
28、luei)return 1; if(m_ulValueiA.m_ulValuei)return -1; return 0; void CBigInt:Mov(CBigInt& A) /把A的值赋给X 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
29、;i+)m_ulValuei=0; CBigInt CBigInt:Add(CBigInt& A) /加法 CBigInt X; X.Mov(*this); unsigned carry=0; unsigned _int64 sum=0; if(X.m_nLengthA.m_nLength)X.m_nLength=A.m_nLength; for(unsigned i=0;i32); X.m_ulValueX.m_nLength=carry; X.m_nLength+=carry; return X; CBigInt CBigInt:Add(unsigned long A) CBigInt X
30、; X.Mov(*this); unsigned _int64 sum; sum=X.m_ulValue0; sum+=A; X.m_ulValue0=(unsigned long)sum; if(sum0xffffffff) unsigned i=1; while(X.m_ulValuei=0xffffffff)X.m_ulValuei=0;i+; X.m_ulValuei+; if(m_nLength=i)m_nLength+; return X; CBigInt CBigInt:Sub(CBigInt& A) /减法 CBigInt X; X.Mov(*this); if(X.Cmp(A
31、)=0)X.Mov(0);return X; unsigned carry=0; unsigned _int64 num; unsigned i; for(i=0;iA.m_ulValuei)|(m_ulValuei=A.m_ulValuei)&(carry=0) X.m_ulValuei=m_ulValuei-carry-A.m_ulValuei; carry=0; else num=0x100000000+m_ulValuei; X.m_ulValuei=(unsigned long)(num-carry-A.m_ulValuei); carry=1; while(X.m_ulValueX
32、.m_nLength-1=0)X.m_nLength-; return X; CBigInt CBigInt:Sub(unsigned long A) CBigInt X; X.Mov(*this); if(X.m_ulValue0=A)X.m_ulValue0-=A;return X; if(X.m_nLength=1)X.Mov(0);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_ul
33、Valuei=0xffffffff;i+; X.m_ulValuei-; if(X.m_ulValuei=0)X.m_nLength-; return X; CBigInt CBigInt:Mul( CBigInt& A) /乘法 if(A.m_nLength=1)return Mul(A.m_ulValue0); CBigInt X; unsigned _int64 sum,mul=0,carry=0; unsigned i,j; X.m_nLength=m_nLength+A.m_nLength-1; for(i=0;iX.m_nLength;i+) sum=carry; carry=0;
34、 for(j=0;j=0)&(i-j)32; mul=mul&0xffffffff; sum+=mul; carry+=sum32; X.m_ulValuei=(unsigned long)sum; if(carry)X.m_nLength+;X.m_ulValueX.m_nLength-1=(unsigned long)carry; return X; CBigInt CBigInt:Mul(unsigned long A) CBigInt X; unsigned _int64 mul; unsigned long carry=0; X.Mov(*this); for(unsigned i=0;im_nLength;i+) mul=m_ulValuei; mul=mul*A+carry; X.m_ulValuei=(unsigned long)mul; carry=(unsigne
