现代密码学第七讲：公钥密码学2

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

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

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

3、数是否为素数2以往素检测的算法都是概率性的，即存在一定的错误概率；32003年，印度人发表文章“PrimesisinP”，证明了素判定问题是一个多项式时间问题。1）辗转相除法2）利用欧拉定理求e^{φ(φ(n))}-1思考：分析两种计算方法的效率62.加密加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。然后对每个明文分组m，作加密运算：c≡memodnRSA算法73.解密对密文分组的解密运算为：m≡cdmodn证明RSA算法中解密过程的正确性.证明：由加密过程知c≡memodn，所以cdmodn≡medmodn≡m1modφ(n)modn≡

4、mkφ(n)+1modnRSA算法8下面分两种情况：①m与n互素，则由Euler定理得mφ(n)≡1modn,mkφ(n)≡1modn,mkφ(n)+1≡mmodn即cdmodn≡m。②gcd(m,n)≠1，先看gcd(m,n)=1的含义，由于n=pq，所以gcd(m,n)=1意味着m不是p的倍数也不是q的倍数。因此gcd(m,n)≠1意味着m是p的倍数或q的倍数，不妨设m=tp，其中t为一正整数。此时必有gcd(m,q)=1，否则m也是q的倍数，从而是pq的倍数，与m

5、odq,［mkφ(q)］φ(p)≡1modq,mkφ(n)≡1modq因此存在一整数r，使得mkφ(n)=1+rq，两边同乘以m=tp得mkφ(n)+1=m+rtpq=m+rtn即mkφ(n)+1≡mmodn，所以cdmodn≡m.RSA算法10例：选p=7，q=17.求得n=p×q=119，φ(n)=(p-1)(q-1)=96.取e=5，满足1

6、5mod119≡2476099mod119≡66;解密过程为m≡6677mod119≡19.RSA算法11RSA中的计算问题1.RSA的加密与解密过程RSA的加密、解密过程都为求一个整数的整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。如上例中解密运算6677mod119，先求6677再取模，则中间结果就已远远超出了计算机允许的整数取值范围。而用模运算的性质：(a×b)modn=[(amodn)×(bmodn)]modn就可减小中间结果。RSA算法122.模指数运算的快速算法例如求x16，直接计算的话需做15次乘法。然而如果重复对每

7、个部分结果做平方运算即求x，x2，x4，x8，x16则只需4次乘法。求am可如下进行，其中a，m是正整数：将m表示为二进制形式bkbk-1…b0，即m=bk2k+bk-12k-1+…+b12+b0因此RSA算法13例：求a1919=1×24+0×23+0×22+1×21+1×20所以a19=((((a1)2a0)2a0)2a1)2a1练习：求a7和a8，并统计快速运算法的运算次数.RSA算法14RSA算法RSA的快速实现加密很快，指数小；解密比较慢，指数较大.利用中国剩余定理CR