RSA算法设计实现分析.doc

题目名称：RSA加密解密的设计与实现一、 设计原理算法工作原理RSA 原理：RSA 密钥的选取和加解密过程都非常简洁，在算法上主要要实现四个问题：1、如何处理大数运算2、如何求解同余方程 *Y % M = 13、如何快速进展模幂运算4、如何获取大素数(一) 大数存储RSA 依赖大数运算，目前主流RSA 算法都建立在1024位的大数运算之上。而大多数的编译器只能支持到64位的整数运算，即我们在运算中所使用的整数必须小于等于64位，即：0*ffffffffffffffff，也就是615，这远远达不到RSA 的需要，于是需要专门建立大数运算库来解决这一问题。一个有效的改进方法是将大数表示为一个n 进制数组，对于目前的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*ffffffff 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<r其中Sum 表示求和，A表示用以记录A 的数组的第i 个元素，*表示乘方。任何整数运算最终都能分解成数字与数字之间的运算，在0*100000000 进制下其“数字最大到达0*ffffffff，其数字与数字之间的运算，结果也必然超出了目前32位系统的字长。在VC+中，存在一个_int64 类型可以处理64位的整数，所以不用担忧这一问题。(二) 加减乘除设有大数A、B和C，其中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<r，p>=q则当C=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，因为A-B可能<0，而C必须>=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可以归纳出：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“试商，我们只能转换成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)，直到A<B则：*=A/B，且此时的A=A%B，注意对于任意大数A*0*100000000*k，都等价于将A 的数组中的各元素左移k 位，不必计算；同样，A/0*100000000*k则等价于右移。(三) 欧几里得方程在RSA 算法中，往往要在A、N的情况下，求 B，使得 (A*B)%N=1。即相当于求解B、M都是未知数的二元一次不定方程 A*B-N*M=1 的最小整数解。而针对不定方程a*-by=c 的最小整数解，有著名的欧几里德算法，即辗转相除法。事实上二元一次不定方程有整数解的充要条件是c为a、b的最大公约数。即当c=1时，a、b必须互质。而在RSA算法里由于公钥d为素数，素数与任何正整数互质，所以可以通过欧几里德方程来求解私钥e。欧几里德算法是一种递归算法，比较容易理解：例如：11*-49y=1，求*a 11 * - 49 y = 1 49%11=5 ->b 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=aa=b%ab=iIF *<0 *=*+bRETURN *(四) 模幂运算模幂运算是RSA 的核心算法，最直接地决定了RSA 算法的性能。针对快速模幂运算这一课题，西方现代数学家提出了大量的解决方案，通常都是先将幂模运算转化为乘模运算。例如求D=C*15 % N，由于：a*b % n = (a % n)*(b % n) % n，所以：C1 =C*C % N =C*2 % NC2 =C1*C % N =C*3 % NC3 =C2*C2 % N =C*6 % NC4 =C3*C % N =C*7 % NC5 =C4*C4 % N =C*14 % NC6 =C5*C % N =C*15 % N即：对于E=15的幂模运算可分解为6 个乘模运算，归纳分析以上方法可以发现对于任意E，都可采用以下算法计算D=C*E % N：D=1WHILE E>=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 算法的效率，首要问题在于提高模乘运算的效率。不难发现，模乘过程中复杂度最高的环节是求模运算，因为一次除法实际上包含了屡次加法、减法和乘法，如果在算法中能够尽量减少除法甚至防止除法，则算法的效率会大大提高。设A=Sumi=0 to k(A*2*i)，0<=A<=1，则：C= A*B = Sumi=0 to k(A*B*2*i)可用循环处理为：C=0FOR i FROM k TO 0C=C*2C=C+A*BRETURN C假设令 C'= A*B*2*(-k)，则：C'= Sumi=0 to k(A*B*2*(i-k)用循环处理即：C'=0FOR i FROM 0 TO kC'=C'+A*BC'=C'/2RETURN C'通过这一算法求A*B*2*(-k)是不准确的，因为在循环中每次除以2都可能有余数被舍弃了，但是可以通过这一算法求A*B*2*(-k) %N的准确值，方法是在对C'除2之前，让C'加上C'0*N。由于在RSA中N是两个素数的积，总是奇数，所以当C'是奇数时，C'0=1，C'+C'0*N 就是偶数，而当C'为偶数时C'0=0，C'+C'0*N还是偶数，这样C'/2 就不会有余数被舍弃。又因为C'+N %N = C' %N，所以在计算过程中加假设干次N，并不会影响结果的正确性。可以将算法整理如下：C'=0FOR i FROM 0 TO kC'=C'+A*BC'=C'+C'0*NC'=C'/2IF C'>=N C'=C'-NRETURN C'由于在RSA中A、B总是小于N，又0<=A,C'0<=1，所以：C' = (C'+A*B+C'0*N)/2C' < (C'+2N)/22C' < C'+2NC' < 2N既然C'总是小于2N，所以求C' %N 就可以很简单地在完毕循环后用一次减法来完成，即在求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 %N*=A'FOR 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如此，我们最终实现了不含除法的模幂算法，这就是著名的蒙哥马利算法，而*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<=r我们需要得到的蒙哥马利乘积为：C'= A*B*R' %N R'=r*(-k)则以下算法只能得到C'的近似值C'=0FOR i FROM 0 TO kC'=C'+A*BC'=C'/rIF C'>=N C'=C'-NRETURN C'因为在循环中每次C'=C'/r 时，都可能有余数被舍弃。假设我们能够找到一个系数 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=> (C'0 + A*B0 + q*N0) %r =0假设令N0*N0' %r =1，q=(C'0+A*B0)*(r-N0') %r，则：(C'0 + A*B0 + q*N0) %r= (C'0+A*B0 - (C'0+A*B0)*N0'*N0) %r) %r= 0于是我们可以得出r为任何值的蒙哥马利算法：m=r-N0'C'=0FOR i FROM 0 TO kq=(C'0+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'只需要计算一次，负担并不大。(六) 素数测试方法数论学家利用费马小定理研究出了多种素数测试方法，目前最快的算法是拉宾米勒测试算法，其过程如下：1计算奇数M，使得N=(2*r)*M+12选择随机数A<N3对于任意i<r，假设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 进展测试，以提高拉宾米勒测试通过的概率，从而提高整体测试速度。而在生成随机素数时，选取的随机数最好让r=0，则可省去步骤3 的测试，进一步提高测试速度。素数测试是RSA 选取秘钥的第一步，奇妙的是其核心运算与加解密时所需的运算完全一致：都是模幂运算。而模幂运算过程中中所需求解的欧几里德方程又恰恰正是选取密钥第二步所用的运算。二、 系统功能描述与软件模块划分CBIGINT类用以实现大素数的加、减、乘、除CBigInt Add( CBigInt& A); /实现大素数加法CBigInt Sub(CBigInt& 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 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);/解密三、 设计核心代码*include"BigInt.h"*include"time.h"*include"string"*include<iostream>using namespace std;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, 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, 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 ; const static long Primecount=sizeof(PrimeTable)/sizeof(long);CBigInt:CBigInt() /构造大数对象并初始化为零 m_nLength=1; for(int i=0;i<BI_MA*LEN;i+)m_ulValuei=0; CBigInt:CBigInt() /解构大数对象 int CBigInt:Cmp(CBigInt& A) /大数比较，*>A返回1，*=A返回0，*<A返回-1 if(m_nLength>A.m_nLength)return 1; if(m_nLength<A.m_nLength)return -1; for(int i=m_nLength-1;i>=0;i-) if(m_ulValuei>A.m_ulValuei)return 1; if(m_ulValuei<A.m_ulValuei)return -1; return 0; void CBigInt:Mov(CBigInt& A) /把A的值赋给* m_nLength=A.m_nLength; for(int i=0;i<BI_MA*LEN;i+)m_ulValuei=A.m_ulValuei; void CBigInt:Mov(unsigned _int64 A) if(A>0*ffffffff) m_nLength=2; m_ulValue1=(unsigned long)(A>>32); m_ulValue0=(unsigned long)A; else m_nLength=1; m_ulValue0=(unsigned long)A; for(int i=m_nLength;i<BI_MA*LEN;i+)m_ulValuei=0; CBigInt CBigInt:Add(CBigInt& A) /加法 CBigInt *; *.Mov(*this); unsigned carry=0; unsigned _int64 sum=0; if(*.m_nLength<A.m_nLength)*.m_nLength=A.m_nLength; for(unsigned i=0;i<*.m_nLength;i+) sum=A.m_ulValuei; sum=sum+*.m_ulValuei+carry; *.m_ulValuei=(unsigned long)sum; carry=(unsigned)(sum>>32); *.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_ulValue0=(unsigned long)sum; if(sum>0*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; unsigned i; for(i=0;i<m_nLength;i+) if(m_ulValuei>A.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 long 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-; 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<A.m_nLength;j+) if(i-j)>=0)&&(i-j)<m_nLength) mul=m_ulValuei-j; mul*=A.m_ulValuej; carry+=mul>>32; mul=mul&0*ffffffff; sum+=mul; carry+=sum>>32; *.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);