搜索
应用密码学作业姓名：隋鑫学号：03111326班级：031113班学院：计算机学院电话：15109228792任课教师：王超RSA算法原理与实现姓名：隋鑫学号：03111326班级：031113班摘要RSA算法是目前使用最广的公钥密码算法,本文比较全面地从原理到实现介绍了这个得到广泛接受和实现的算法，并简要讨论了RSA的安全性。最后，提出了自己对RSA算法理论和应用发展的一些想法。1.引言公开密钥密码算法的提出是整个密码学历史上最大的而且也是一场真正的变革。从最初一直到现代，几乎所有密码系统都建立在基本的替代和置换工具的基础上。在用了数千年的本质上可以手算完成的算法之后，常规的密码学随着转轮加密/解密机的发展才出现了一个重大进步。机电式变码旋转软件使得极其复杂的密码系统被研制出来。有了计算机后，更加复杂的系统被设计出来。但是不管是转轮机还是后来的DES（数据加密标准），虽然代表了重要的进展，却仍然依赖于替代和置换这样的基本工具。公钥密码学则与以前的所有方法都截然不同。一方面公开密钥算法基于数学函数而不是替代和置换，更重要的是，公开密钥密码学是非对称的，它用到两个不同的密钥，而对称的常规加密则只使用一个密钥。使用两个密钥对于保密通信，密钥分配和鉴别等领域都有着深远的影响。RSA算法是目前应用最广的公钥密码，由Rivest,Shamir和Adleman在1977年提出。它基于一个非常简单的数论难题，很容易将两个素数乘起来，但分解该乘积却非常困难，从而，该乘积可以公开且可作为加密公钥。不能从该乘积恢复这两个素数。解密需要用到这两个素数。从而用很简单的形式实现了非常可靠的密码系统.2.RSA算法描述RSA公钥密码体制描述如下：1.选取两个大素数p,q。2.计算n=pq,Φ(n)=(p-1)(q-1)。3.随机选取正整数e,1eΦ(n),满足gcd(e,Φ(n))=1。4.计算d,满足de≡1(modΦ(n))。p,q,Φ(n),d是保密的，丢弃p,q,Φ(n);只保留d，则n,d为私钥；n,e是公开，为公钥。5.加密变换：对明文m,1mn,加密后的密文为c=me(modn)。6.解密变换：对密文c,1cn,解密后的明文为m=cd(modn)。证明：由于de≡1(modΦ(n)),所以存在正整数t，使得de=1+tΦ(n))。对于任意明文m,1mn。当gcd(m,n)=1时，根据欧拉定理有cd≡(me)d≡(mΦ(n))tm≡1tm≡m(modn);当gcd(m,n)≠1时，因为n=pq且p,q是两个素数，所以gcd(m,n)=p或q。不妨设gcd(m,n)=p,则m=bp,1≤bq。另一方面，由欧拉定理得mq-1≡1(modq),从而mtΦ(n)=(mq-1)t(p-1)≡1(modq),于是存在一个整数s,使得mtΦ(n)=1+sq,此式两端用m=bp同乘，就得到mtΦ(n)+1=m+bsn,从而cd≡mtΦ(n)+1≡m(modn)。证毕。举例：如果p=47,q=71,那么n=pq=3337，Φ(n)=(p-1)(q-1)=3220。加密密钥e满足gcd(e,Φ(n))=1,则随机选取e,如79,那么d=e-1(modΦ(n))=79-1(mod3220)=1019。这时获得：公钥：e,n即79,3337私钥：d,n即1019,3337[加密消息]m=6882326879666683首先将其分为小的分组，在此例中，按三位数字一分组(不够三位的分组在左边添加0)就可以进行加密。这个消息将分成六个分组mi进行加密：m1=688m2=232m3=687m4=966m5=668m6=003第一分组加密为：68879mod3337=1570=c1对后面的分组进行相应的加密计算，最后的密文为：c=15702756209122762423158[解密消息]第一分组解密为：15701019mod3337=688=m1消息的其余部分可用同样的方法恢复出来。3.RSA算法的数论基础知识3.1整除的定义定义3.1.1:设a,b∈如果存在q∈Z使得b=aq,那么就说b可被a整除，记作a|b，a是b的约数.3.2素数与合数定义3.2.1:设p≠0,±1,如果它除了显然约数±1,±p外没有其他的约数，那么，p就称为是素数，否则为合数.定理3.2.2:素数有无穷多个证明:用反证法，假设素数为有穷多个，设有n个，从2开始由小到大我们可以得到一个有限的素数集合{qi|qi是素数且1=i=n},我们考察a=q1q2….qn+1,因为我们知道qn是最大的素数，所以a是一个合数，且a大于所有素数，所以a至少可以被一个素数整除,设为qi,qi|a,因为又qi|q1q2…qn，所以qi|a-q1q2…qn，即qi|1,由于qi2，所以假设是错误的，即素数必有无穷多个.3.3带余除法和Euclid(欧拉)算法定理3.3.1:设a,b是两个给定的整数，a≠0,那么，一定存在唯一的一对整数q与r,满足b=qa+r,0≤r|a|.此外,a|b的充要条件是r=0定理3.3.2:设u0,u1是给定的两个整数，u1≠0,u1不整除u0,则我们一定可以重复应用定理4得到下面k+1个等式:u0=q0u1+u2,0u2|u1|u1=q1u2+u3,0u3u2u2=q2u3+u4,0u4u3……uk-1=qk-1uk+uk+1,0uk+1ukuk=qkuk+1证明:依次这样做，就得到:|u1|u2u3…uj+10对uj,uj+1不断用定理3.3.1,由于小于|u1|的正整数只有有限个以及1整除任一整数，所以这过程不能无限制地做下去，一定会出现某个k,要么1uk+1|uk,要么1=uk+1|uk3.4公约数和最大公约数定义3.4.1:设a1,a2是两个整数.如果d|a1且d|a2,那么，d就称为是a1和a2的公约数,a1,a2的公约数中最大的称为a1和a2的最大公约数，记作(a1,a2).设a1,…,ak是k个不全为零的整数,a1,…,ak的最大公约数,记作(a1,….,ak)最大公约数有以下几条性质:(i)若a1|aj,j=2…,k,则(a1,a2)=(a1,a2,…,ak)=(a1)=|a1|;(ii对任意整数x,(a1,a2)=(a1,a2,a1x)(a1,…,ak)=(a1,…,ak,a1x)(iii)对任意整数x,(a1,a2)=(a1,a2+a1x),(a1,…,ak)=(a1,a2+a1x,a3,…,ak)定义3.4.2:若(a1,a2)=1,则称a1和a2是既约的，也称a1和a2是互素的.定理3.4.4:设m0,我们有(mb1,…,mbk)=m(b1,…,bk)证:设aj=mbj,根据定理3.4.3可以得证定理3.4.5:设(m,a)=1,我们有(m,ab)=(m,b)证:(m,b)=(m,b(m,a))=(m,(bm,ba))=(m,mb,ab)=(m,ab)定理3.4.6:设(m,a)=1,若m|ab,则m|b证:(m,a)=1,所以根据定理3.4.5,(m,b)=(m,ab)，若m|ab,则有(m,ab)=|m|，即(m,b)=|m|,所以m|b.定理2.4.7设a1,a2是两个不全为零的整数，那么，一定存在整数x1,x2，使得(a1,a2)=x1*a1+x2*a24.RSA算法实现的分析实现RSA算法需要涉及以下方面问题挑选加密用的素数如何提高加解密算法的速度加密密次e,解密幂次d的选取考虑4.1素数的选取与测试根据定理3.2.2:素数有无穷多个.所以不必担心素数会用完.根据3.9的Chebyshev不等式100到101位的10进制的素数约有可见素数有很多,如果只检测其中的奇数，单个成功几率大约为进行因子分解很困难，而判定一个数是否素数则简单很多，所以试图分解随机数是不可取的，正确的做法是对产生的随机数测试是否素数.测试素数的原理是Fermat小定理,对于一个待测试的奇数p,如果对于任一个小于p的w,应该有(w,p)=1,并且满足wm-如果找到这个w,可以看成是p是素数的一个证据，如果p和w的关系不满足Fermat小定理，则立刻可以知道p不是素数，找到一个证据我们可以认为p不是素数的几率只有50%,我们找到的证据越多，p是素数的证据越充分，由此可认为如果找到k个证据，p不是素数的几率只有2-k.实际上还有一个非常不幸的例外，Carmichael数是所有小于它的数都可以做它是素数的证据，即满足Fermat小定理的形式，但Carmichael数是奇合数。但Carmichael满足一定条件，一个Carmichael数总是没有平方因子，而且当且仅当所有p是可整除m的素数，而p-1也可整除m-1时,一个没有平方因子的奇合数m是一个Carmichael数.所以我们按照这个条件排除Carmichael数.实际上的做法如下:(1)产生一个n-位的随机数p(2)设高位和低位为1,这样可以确保p有n位且为奇数(3)检查以确保p不能被任何小素数整除:如3,5,7,11等，可以用算法测试p对小于256或2000的所有素数的整除性.(4)对某随机数wp运行Rabin-Miller测试，如果通过测试则另选一个a,做五次.如果失败则可以表明p不是素数,如果通过(3)(4)的测试，不是素数的几率就很低了.4.2如何提高加解密算法的速度RSA算法的加/解密过程其实是一个幂运算和模运算相结合的过程,如果我们计算先计算Me,然后计算Memodn,幂运算的计算量非常巨大，而且如果保存Me也需要很大的存储空间，不失一般性地我们假设M,e均为256位,我们将需要log2(Me)=e.log2(M)=2256.256=2264位来保存中间结果.可见采用直接的模幂运算是不可行的。加解密运算中的幂模运算我们可以乘法运算和求模运算实现，由于模运算对加法，乘法运算可分配，即:(a+b)modn=(amodn)+(bmodn)(a*b)modn=(amodn)*(bmodn)所以可以对幂运算中和加法运算中的中间结果直接使用模运算，降低运算强度，可以说，这是我们进行简化的基础。5.RSA算法的安全性对RSA算法攻击的最直接的想法是分解模数n,因为通过分解n得到p,q就可以知道φ(n)=(p-1)(q-1),由于ed+kφ(n)=1,就可以通过欧拉算法计算出解密幂数d,我们可以把通过分解模数n来攻击RSA为蛮力攻击，因为即使最优秀的分解大整数的算法也没有对RSA的安全性构成威胁.但在许多情况下，如果密钥的设置和使用不当，会带来安全问题。5.1不当选取p,q所带来的安全问题注意到因为p不等于q,所以现在密码攻击者知道n,也就是知道n,根据则我们可以使x从大于n的整数开始,如果(x2-n)的平方根也是一个整数，我们则可以破解n,下面是一个简单的破解算法:procedureBreak_n输入:n输出:p,qBeginx=[sqr(n)]+1Found=FalsewhileFound==Falsey2=x*x-ny=[sqr(y2)]ify*y==y2thenp=x+yq=x-yFound=Trueelsex=x+1endifendwhileReturn(p,q)观察上面的算法，算法中循环的x从[n]+1开始增长，到达(p+q)/2停止,如果p和q比较接近，或p和q都比较小，则根据以上算法很快就可以从n中分解出p,q5.2不要在团体中使用相同的模数n5.2.1团体中的用户有办法分解n根据密钥的生成,对于相同的模数n,选取不同的d满足如d1,....,dk,再用欧拉算法算出e1,...,ek,则可以生成不同的密钥对n,ei,n,di,把密钥分配给不同的成员，这样能导致系统的不安全。因为给定d能分解n,其中一个成员i使用自己的解密幂次di就可以分解n,从而根据其他人j的公开幂次ej算出j的解密幂次dj。5.2.2针对公共模数n的选择密文攻击5.3不要在团体中使用相同的小加密幂数e如果一个团体使用了相同的小加密幂数e,假设Bob想把消息m发