文档介绍：武汉大学密码学课程设计报告题目名称:RSA加密解密的设计与实现姓名:学号:专业:设计原理(算法工作原理)RSA原理:RSA密钥的选取和加解密过程都非常简洁,在算法上主要要实现四个问题:1、如何处理大数运算2、如何求解同余方程XY%M=13、如何快速进行模幂运算4、如何获取大素数大数存储RSA依赖大数运算,目前主流RSA算法都建立在1024位的大数运算之上。而大多数的编译器只能支持到64位的整数运算,即我们在运算中所使用的整数必须小于等于64位,即:0xffffffffffffffff,也就是18446744073709551615,这远远达不到RSA的需要,于是需要专门建立大数运算库来解决这一问题。一个有效的改进方法是将大数表示为一个n进制数组,对于目前的32位系统而言n可以取值为2的32次方,即0x100000000,假如将一个二进制为1024位的大数转化成0x10000000进制,就变成了32位,而每一位的取值范围不再是二进制的0—1或十进制的0—9,而是0-0xffffffff,我们正好可以用一个32位的DWORD(如:无符号长整数,unsignedlong)类型来表示该值。所以1024位的大数就变成一个含有32个元素的DWORD数组,而针对DWORD数组进行各种运算所需的循环规模至多32次而已。而且0x100000000进制与二进制,对于计算机来说,几乎是一回事,转换非常容易。例如:大数18446744073709551615,等于0xffffffffffffffff,就相当于十进制的99:有两位,每位都是0xffffffff。而18446744073709551616等于0x00000001;0000000000000000,就相当于十进制的100:有三位,第一位是1,其它两位都是0,如此等等。在实际应用中,“数字数组”的排列顺序采用低位在前高位在后的方式,这样,大数A就可以方便地用数学表达式来表示其值:A=Sum[i=0ton](A*r**i),r=0x100000000,0<=A<r其中Sum表示求和,A表示用以记录A的数组的第i个元素,**表示乘方。任何整数运算最终都能分解成数字与数字之间的运算,在0x100000000进制下其“数字”最大达到0xffffffff,其数字与数字之间的运算,结果也必然超出了目前32位系统的字长。在VC++中,存在一个__int64类型可以处理64位的整数,所以不用担心这一问题。加减乘除设有大数A、B和C,其中A>=B:A=Sum[i=0top](A*r**i)B=Sum[i=0toq](B*r**i)C=Sum[i=0ton](C*r**i)r=0x100000000,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可能>0xffffffff,而C必须<=0xffffffff,这时就需要进位,当然在计算C[i-1]时也可能产生了进位,所以计算C时还要加上上次的进位值。如果用一个64位变量result来记录和,另一个32位变量carry来记录进位,则有:carry=0FORiFROM0TOpresult=A+B+carryC=result%0x100000000carry=result/0x100000000IFcarry=0n=pELSEn=p+1C=A-B,同理C不总是等于A-B,因为A-B可能<0,而C必须>=0,这时就需要借位,同样在计算C[i-1]时也可能产生了借位,所以计算C时还要减去上次的借位值:carry=0FORiFROM0TOpIFA-B-carry>=0C=A-B-carrycarry=0ELSEC=0x100000000+A-B-carrycarry=1n=pWHILEC[n]=0n=n-1C=A*B,首先我们需要观察日常做乘法所用的“竖式计算”过程:A3A2A1A0*B2B1B0-------------------------------=A3B0A2B0A1B0A0B0+A3B1A2B1A1B1A0B1+A3B2A2B2A1B2A0B2-------------------------------=C5C4C3C2C1C0可以归纳出:C=Sum[j=0toq](A[i-j]*B[j]),其中i-j必须>=0且<=p。当然这一结论没有考虑进位,虽然计算A[i-j]*B[j]和Sum的时候都可能发生进位,但显然这两种原因产生的进位可以累加成一个进位值。最终可用如下算法完成乘法:n=p+q-1carry=0ForiFROM0TOnresult=carryForjFROM0TOqIF0<=i-j<=presult=result+A[i-j]*B[j]C=res