RSA算法设计与实现.docVIP

..... word格式.整理版 武汉大学密码学课程设计报告 武汉大学密码学课程设计报告 题目名称： RSA加密解密的设计与实现 姓 名： 学 号： 专 业： 设计原理（算法工作原理） RSA 原理： RSA 密钥的选取和加解密过程都非常简洁，在算法上主要要实现四个问题： 1、如何处理大数运算 2、如何求解同余方程 XY % M = 1 3、如何快速进行模幂运算 4、如何获取大素数 大数存储 RSA 依赖大数运算，目前主流RSA 算法都建立在1024位的大数运算之上。而大多数的编译器只能支持到64位的整数运算，即我们在运算中所使用的整数必须小于等于64位，即：0xffffffffffffffff，也就是18446744073709551615，这远远达不到RSA 的需要，于是需要专门建立大数运算库来解决这一问题。 一个有效的改进方法是将大数表示为一个n 进制数组，对于目前的32位系统而言n 可以取值为2 的32次方，即 0x100000000，假如将一个二进制为1024位的大数转化成0制，就变成了32位，而每一位的取值范围不再是二进制的0—1或十进制的0—9，而是0-0xffffffff，我们正好可以用一个32位的DWORD （如：无符号长整数，unsigned long） 类型来表示该值。所以1024位的大数就变成一个含有32个元素的 DWORD数组，而针对 DWORD数组进行各种运算所需的循环规模至多32次而已。而且0x100000000 进制与二进制，对于计算机来说，几乎是一回事，转换非常容易。 例如：大数18446744073709551615，等于 0xffffffff ffffffff，就相当于十进制的99：有两位，每位都是0xffffffff。而18446744073709551616等于000000000就相当于十进制的100：有三位，第一位是1 ，其它两位都是0 ，如此等等。在实际应用中，“数字数组”的排列顺序采用低位在前高位在后的方式，这样，大数A 就可以方便地用数学表达式来表示其值：A=Sum[i=0 to n](A*r**i)，r=0x100000000，0=Ar其中Sum 表示求和，A表示用以记录A 的数组的第i 个元素，**表示乘方。任何整数运算最终都能分解成数字与数字之间的运算，在0x100000000 进制下其“数字”最大达到0xffffffff，其数字与数字之间的运算，结果也必然超出了目前32位系统的字长。在VC++中，存在一个__int64 类型可以处理64位的整数，所以不用担心这一问题。 加减乘除 设有大数A、B和C，其中A=B： A=Sum[i=0 to p](A*r**i) B=Sum[i=0 to q](B*r**i) C=Sum[i=0 to n](C*r**i) r=0x100000000，0=A,B,Cr，p=q 则当C=A+B、C=A-B、C=A*B时，我们都可以通过计算出C来获得C：C=A+B，显然C不总是等于A+B，因为A+B可能0xffffffff，而C必须=0xffffffff，这时就需要进位，当然在计算C[i-1]时也可能产生了进位，所以计算C时还要加上上次的进位值。如果用一个64位变量result来记录和，另一个32位变量carry来记录进位，则有： carry=0 FOR i FROM 0 TO p result=A+B+carry C=result%0x100000000 carry=result/0x100000000 IF carry=0 n=p ELSE n=p+1 C=A-B，同理C不总是等于A-B，因为A-B可能0，而C必须=0，这时就需要借位，同样在计算C[i-1]时也可能产生了借位，所以计算C时还要减去上次的借位值： carry=0 FOR i FROM 0 TO p IF A-B-carry=0 C=A-B-carry carry=0 ELSE C=0x100000000+A-B-carry carry=1 n=p WHILE C[n]=0 n=n-1 C=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 C