现代密码学第七讲：公钥密码学2(必修)new

《现代密码学第七讲：公钥密码学2(必修)new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《现代密码学》第七章公钥密码（二）1上节内容回顾¢公钥密码体制的提出及分类¢公钥密码体制的基本概念¢单向陷门函数的概念¢设计公钥加密算法--背包密码体制本节主要内容¢RSA算法及其分析¢ElGmal算法¢椭圆曲线密码体制¢其它公钥密码算法3RSA算法RSA算法是1978年由R.Rivest,A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。它既可用于加密、又可用于数字签字。RSA算法的安全性基于数论中大整数分解的困难性。RLRivest,AShamir,LAdleman,"OnDigitalSi

2、gnaturesandPublicKeyCryptosystems",CommunicationsoftheACM,vol21no2,pp120-126,Feb19784RSA算法1.密钥的产生①选两个安全的大素数p和q。②计算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的欧拉函数值。③选一整数e，满足1

3、特串分组，使得每个分组对应的十进制数小于n，即分组长度小于logn。然后对每个明文分组m，作加密运算：2c≡memodn6RSA算法3.解密对密文分组的解密运算为：m≡cdmodn证明RSA算法中解密过程的正确性.证明：m与n互素，由加密过程知c≡memodn，所以cdmodn≡medmodn≡mkφ(n)+1modn则由Euler定理得mφ(n)≡1modn,mkφ(n)≡1modn,mkφ(n)+1≡mmodn即cdmodn≡m。7RSA算法例：选p=7，q=17.求得n=p×q=119，φ(n)=(p-1)(q-1)=96.取e=5，满足1

4、(n),e)=1，计算满足d·e=1mod96且小于96的d.因为77×5=385=4×96+1，所以d为77，因此公开钥为{5，119}，秘密钥为{77，119}.设明文m=19，则加密过程为c≡195mod119≡2476099mod119≡66;解密过程为m≡6677mod119≡19.8RSA算法的安全性整数分解问题：已知n是两个大素数的乘积，求n的素分解RSA的安全性是基于分解大整数困难的假定如果RSA的模数n被成功地分解为p×q，则获得φ(n)=(p-1)(q-1)，从而攻击者能够从公钥e解出d，即d≡e-1modφ(n)，攻击成功.9RSA算法的安全性¾至今还

5、未能证明分解大整数就是NPC问题，也许有尚未发现的多项式时间分解算法.¾随着人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解.例如RSA-129（即n为129位十进制数，大约428个比特）已在网络上通过分布式计算历时8个月于1994年4月被成功分解，RSA-130已于1996年4月被成功分解.RSA-768has232decimaldigitsandwasfactoredonDecember12,2009byThorstenKleinjung,KazumaroAoki,JensFranke,ArjenK.Lenstra,EmmanuelThomé,Pierr

6、ickGaudry,AlexanderKruppa,PeterMontgomery,JoppeW.Bos,DagArneOsvik,HermanteRiele,AndreyTimofeev,andPaulZimmermann10RSA算法的安全性¾分解算法的进一步改进.过去分解算法都采用二次筛法,如对RSA-129的分解.而对RSA-130的分解则采用了一个新算法，称为推广的数域筛法，该算法在分解RSA-130时所做的计算仅比分解RSA-129多10%.1）在使用RSA算法时对其密钥的选取要特别注意其大小。估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之

7、间的RSA是安全的.11RSA算法的安全性2）

8、p-q

9、要大222()p++−qp()qp()q由，−=np−=q如果

10、p-q

11、小，444则(p-q)2/4也小；因此(p+q)2/4稍大于n,即(p+q)/2稍大于n1/2。那么①顺序检查大于n1/2的每一整数x，直到找到一个x使得x2-n是某一整数（记为y）的平方。②由x2-n=y2，得n=(x+y)(x-y)，可得n的分解.12RSA算法的安全性3）p-1和q-1都应有大素因子设攻击者截获密文c，可如下进行重复加密：e2eeecmm≡≡()()modn223ee