RSA算法详解.ppt

RSA算法详解.ppt

《RSA算法详解.ppt》由会员分享，可在线阅读，更多相关《RSA算法详解.ppt（23页珍藏版）》请在冰点文库上搜索。

RSA算法,RSAAlgorithm,概况,MIT三位年青数学家R.L.Rivest，A.Shamir和L.AdlemanRivest等1978,1979发现了一种用数论构造双钥的方法，称作MIT体制，后来被广泛称之为RSA体制。

它既可用于加密、又可用于数字签字。

RSA算法的安全性基于数论中大整数分解的困难性。

迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。

算法原理,RSA算法使用了乘方运算。

要求：

明文M经过加密得到密文C：

C=Memodn密文C经过解密得到明文M：

Cdmodn=（Memodn）dmodn=Medmodn=M即：

必须存在e，d，n，使Medmodn=M成立,如何确定e,d,n,确定n：

独立地选取两大素数p和q（各100200位十进制数字）计算n=pq，其欧拉函数值（n）=（p1）（q1）确定e：

随机选一整数e，1e（n），gcd（n）,e）=1确定d：

根据ed=1mod（n）在模（n）下，计算d,这样确定的e,d,n是否能使Medmodn=M成立呢？

因为ed=1mod（n）即ed=k（n）+1所以：

Med=Mk（n）+1如果M和n互素，即gcd（M,n）=1那么，根据欧拉定理（如果gcd（a,n）=1，则a（n）1modn）：

有：

M（n）1modn所以：

MedMk（n）+1MM（n）kmodnM1kmodnMmodn,如果M和n不互素，即gcd（M,n）1，即M和n有大于1的公约数。

因为n=pq，而p、q都是素数，不可再分解，所以M一定包含了p或q为因子。

又因为Mn，所以M不可能既是p的倍数又是q的倍数。

不妨设M是p的倍数，M=cp。

由于M不是q的倍数，所以gcd（M,q）=1，则M（q）1modq，所以：

M（q）（p）1modq即M（n）1modn，即M（n）=1+kq,M（n）=1+kq两边同乘以M=cp，则：

M（n）+1=M+kqcp=M+kcn把kc看作一个常数，则：

M（n）+1=M+tn即：

M（n）+1Mmodn，即M（n）1modn因为ed=1mod（n），所以：

MedMk（n）+1MM（n）kmodnM1kmodnMmodn综上,这样的e，d，n可以实现加密C=Memodn和解密M=Cdmodn,密钥,以n，e为公钥。

秘密钥为d。

（p,q不再需要，可以销毁。

）,RSA算法在计算上的可行性,加密和解密无论是加密还是解密都需要计算某个整数的模n整数次幂，即C=Memodn、M=Cdmodn。

但不需要先求出整数的幂再对n取模，而可利用模运算的性质：

（amodn）*（bmodn）=（a*b）modn对于Memodn，可先求出M1modn，M2modn，M4modn，再求Memodn,RSA算法在计算上的可行性,产生密钥由于n是公开的，为了避免攻击者用穷举法求出p和q（根据n=pq），应该从足够大的集合中选取p和q，即p和q必须是大素数。

目前还没有有效的方法可以产生任意大素数，通常使用的方法是：

随机挑选一个期望大小的奇数，然后测试它是否是素数，若不是，则挑选下一个随机数直至检测到素数为止。

素性检验,引理：

如果p为大于2的素数，则方程x21modp的解只有和x1和x-1证明:

x21modpx2-10modp（x+1）（x-1）0modp所以,p|（x+1）或p|（x-1）或p|（x+1）且p|（x-1）存在k,j，x+1=kp,x-1=jp2=（k-j）p,这是不可能的。

引理的逆命题：

若方程x21modp有唯一解x不为+1或-1，p不是素数,素性检验,Miller-Rabin素性概率检测法n为待检测数，a为小于n的整数，将n-1表示为二进制形式bkbk-1b0,d赋初值为1，算法核心如下fori=kdownto0doxd;d（dd）modn;ifd=1and（x1）and（xn-1）thenreturnFalseifbi=1thed（da）modnifd1thenreturnFalse;returnTrue若返回False,n不是素数,若返回True,有可能是素数。

素性检测,For循环结束,有dan-1modn.由费尔玛定理,若n为素数,d为1.所以d1，则d不是素数n-1-1modn,所以x1和xn-1指x21modn有非1的根,n不是素数该算法对s个不同的a，重复调用，如果每次都返回true，则n是素数的概率大于等于1-2-s,Miller-Rabin算法可以确定一个整数是合数，但不能确定其一定是素数。

要找到一个2200左右的素数，在找到素数之前大约要进行ln（2200）/2=70次尝试在N附近平均每隔lnN个整数就会有一个素数。

RSA算法在计算上的可行性,确定d和e有了p和q，可计算出（n）=（p1）（q1）根据gcd（n）,e）=1来选择e，这一步计算量也不大，因为两个随机数互素的概率约为0.6有了e，再计算d=e-1mod（n），这里用的是扩展的Euclid算法。

选两个保密的大素数p和q。

计算n=pq，（n）=（p-1）（q-1）,其中（n）是n的欧拉函数值。

选一整数e，满足1e（n），且gcd（n）,e）=1。

计算d，满足de1mod（n）,即d是e在模（n）下的乘法逆元，因e与（n）互素，由模运算可知，它的乘法逆元一定存在。

以e,n为公开钥,d,n为秘密钥。

算法描述,选p=7，q=17。

求n=pq=119，（n）=（p-1）（q-1）=96。

取e=5，满足1e（n），且gcd（n）,e）=1。

确定满足de=1mod96且小于96的d，因为775=385=496+1，所以d为77。

因此公开钥为5，119，秘密钥为77，119。

设明文m=19，则由加密过程得密文为C=195mod1192476099mod119=66解密为6677mod119=19,RSA的安全性,RSA的安全性是基于分解大整数的困难性假定如果分解n=pq，则立即获得（n）=（p1）（q1），从而能够确定e的模（n）乘法逆dRSA-129历时8个月（曾经预言需要4*1016年）被于1996年4月被成功分解，RSA130于1996年4月被成功分解密钥长度应该介于1024bit到2048bit之间由n直接求（n）等价于分解n,RSA-129的故事,鹗鸟（ossifrage），又名髭兀鹰（lammergeier），是阿尔卑斯山上一种稀有的肉食秃鹰。

它的翅膀展开将近十米宽。

鸟名的字面含义是“碎骨”。

顾名思义，其习性令人毛骨悚然。

MirtinGardner在1977年“ScientificAmerican”的专栏文章中介绍了RSA码。

为了显示这一技术的威力，RSA公司的研究人员用一个129位的数N和一个4位数e对这个关于秃鹰的消息作了编码。

Gardner刊登了那个密文，同时给出了N和e。

RSA公司还悬赏100美元，奖给第一个破译这密码的人。

96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154,一批松散组成的因子分解迷，大约有六百多人，分布在二十几个国家。

他们经过八个月的努力最后于1994年4月为RSA-129找到了64位数和65位数两个素数因子。

114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541=3490529510847650949147849619903898133417764638493387843990820577*32769132993266709549961988190834461413177642967992942539798288533“Themagicwordsaresqueamishossifrage”,来自两个方面的威胁,人类计算能力的不断提高分解算法的进一步改进。

分解算法过去都采用二次筛法，如对RSA-129的分解。

而对RSA-130的分解则采用了一个新算法，称为推广的数域筛法，该算法在分解RSA130时所做的计算仅比分解RSA-129多10%。

将来也可能还有更好的分解算法，因此在使用RSA算法时对其密钥的选取要特别注意其大小。

估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是安全的。

几个建议,为了防止可以很容易地分解n，RSA算法的发明者建议p和q还应满足下列限制条件：

P和q的长度应仅相差几位。

对于1024位的密钥而言，p和q都应在1075到10100之间。

（p-1）和（q-1）都应有一个大的素因子。

Gcd（p-1,q-1）应该较小。

其它公钥密码算法,ElGamal密码ElGamal密码是由ElGamal于1985年提出。

该密码系统可应用于加/解密、数字签名等，其安全性是建立于离散对数（discretelogarithm）问题之上的，即给定g，p与y=gxmodp，求x在计算上不可行。

椭圆曲线密码体制（ECC）椭圆曲线在密码学中的使用是在1985年由NealKoblitz和VictorMiller分别独立提出的。

其依据就是定义在椭圆曲线点群上的离散对数问题的难解性。

椭圆曲线在代数学和几何学上已经广泛研究了150多年之久，有丰富而深厚的理论积累。