RSA算法设计与实现

.....word格式.整理版题目名称：RSA加密解密的设计与实现姓名：学号：专业：武汉大学密码学课程设计报告.....word格式.整理版一、设计原理（算法工作原理）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=Ar其中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,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.....word格式.整理版FORiFROM0TOpresult=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=result%0x100000000carry=result/0x100000000IFcarry!=0n=n+1C[n]=carry.....word格式.整理版对于C=A/B，由于无法将B对A“试商”，我们只能转换成B[q]对A[p]的试商来得到一个近似值，所以无法直接通过计算C来获得C，只能一步步逼近C。由于：B*(A[p]/B[q]-1)*0x100000000**(p-q)C，令：X=0，重复A=A-X*B，X=X+(A[p]/B[q]-1)*0x100000000**(p-q)，直到AB则：X=A/B，且此时的A=A%B，注意对于任意大数A*0x100000000**k，都等价于将A的数组中的各元素左移k位，不必计算；同样，A/0x100000000**k则等价于右移。(三)欧几里得方程在RSA算法中，往往要在已知A、N的情况下，求B，使得(A*B)%N=1。即相当于求解B、M都是未知数的二元一次不定方程A*B-N*M=1的最小整数解。而针对不定方程ax-by=c的最小整数解，有著名的欧几里德算法，即辗转相除法。事实上二元一次不定方程有整数解的充要条件是c为a、b的最大公约数。即当c=1时，a、b必须互质。而在RSA算法里由于公钥d为素数，素数与任何正整数互质，所以可以通过欧几里德方程来求解私钥e。欧几里德算法是一种递归算法，比较容易理解：例如：11x-49y=1，求x（a）11x-49y=149%11=5-（b）11x-5y=111%5=1-（c）x-5y=1令y=0代入（c）得x=1令x=1代入（b）得y=2令y=2代入（a）得x=9同理可使用递归算法求得任意ax-by=1（a、b互质）的解。实际上通过分析归纳将递归算法转换成非递归算法就变成了大衍求一术：x=0,y=1WHILEa!=0i=yy=x-y*a/bx=ii=aa=b%ab=iIFx0x=x+bRETURNx(四)模幂运算模幂运算是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%N.....word格式.整理版C6=C5*C%N=C**15%N即：对于E=15的幂模运算可分解为6个乘模运算，归纳分析以上方法可以发现对于任意E，都可采用以下算法计算D=C**E%N：D=1WHILEE=0IFE%2=0C=C*C%NE=E/2ELSED=D*C%NE=E-1RETURND继续分析会发现，要知道E何时能整除2，并不需要反复进行减一或除二的操作，只需验证E的二进制各位是0还是1就可以了，从左至右或从右至左验证都可以，从左至右会更简洁，设E=Sum[i=0ton](E*2**i)，0=E=1，则：D=1FORi=nTO0D=D*D%NIFE=1D=D*C%NRETURND这样，模幂运算就转化成了一系列的模乘运算。(五)蒙哥马利模乘由于RSA的核心算法是模幂运算，模幂运算又相当于模乘运算的循环，要提高RSA算法的效率，首要问题在于提高模乘运算的效率。不难发现，模乘过程中复杂度最高的环节是求模运算，因为一次除法实际上包含了多次加法、减法和乘法，如果在算法中能够尽量减少除法甚至避免除法，则算法的效率会大大提高。设A=Sum[i=0tok](A*2**i)，0=A=1，则：C=A*B=Sum[i=0tok](A*B*2**i)可用循环处理为：C=0FORiFROMkTO0C=C*2C=C+A*BRETURNC若令C'=A*B*2**(-k)，则：C'=Sum[i=0tok](A*B*2**(i-k))用循环处理即：C'=0FORiFROM0TOkC'=C'+A*BC'=C'/2RETURNC'.....word格式.整理版通过这一算法求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'=0FORiFROM0TOkC'=C'+A*BC'=C'+C'[0]*NC'=C'/2IFC'=NC'=C'-NRETURNC'由于在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=Sum[i=0ton](E*2**i)：A'=A*R%NX=A'FORiFROMnTO0X=X*X*R'%NIFE=1X=X*A'*R'%NX=X*1*R'%NRETURNX最初：X=A*R%N，开始循环时：X=X*X*R'%N=A*R*A*R*R'%N=A**2*R%N反复循环之后：X=A**E*R%N最后：X=X*1*R'%N=A**E*R*R'%N=A**E%N.....word格式.整理版如此，我们最终实现了不含除法的模幂算法，这就是著名的蒙哥马利算法，而X*Y*R'%N则被称为“蒙哥马利模乘”。以上讨论的是蒙哥马利模乘最简单，最容易理解的二进制形式。蒙哥马利算法的核心思想在于将求A*B%N转化为不需要反复取模的A*B*R'%N，但是利用二进制算法求1024位的A*B*R'%N，需要循环1024次之多，必然希望找到更有效的计算A*B*R'%N的算法。考虑将A表示为任意的r进制：A=Sum[i=0tok](A*r**i)0=A=r我们需要得到的蒙哥马利乘积为：C'=A*B*R'%NR'=r**(-k)则以下算法只能得到C'的近似值C'=0FORiFROM0TOkC'=C'+A*BC'=C'/rIFC'=NC'=C'-NRETURNC'因为在循环中每次C'=C'/r时，都可能有余数被舍弃。假如我们能够找到一个系数q，使得(C'+A*B+q*N)%r=0，并将算法修改为：C'=0FORiFROM0TOkC'=C'+A*B+q*NC'=C'/rIFC'=NC'=C'-NRETURNC'则C'的最终返回值就是A*B*R'%