crypto4c-ch09-公钥密码学和RSA.ppt

《crypto4c-ch09-公钥密码学和RSA.ppt》由会员分享，可在线阅读，更多相关《crypto4c-ch09-公钥密码学和RSA.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、B第9章 公钥密码学和RSA9.1 公钥密码体制的基本原理公钥密码体制的基本原理公钥密码体制的基本概念公钥密码体制的基本概念公钥密码体制的应用公钥密码体制的应用对公钥密码的要求对公钥密码的要求9.2 RSA算法算法B密码学的重要进步密码学的重要进步从Rotor到DES都是基于代换和置换等初等方法都是基于代换和置换等初等方法密码学的新方向密码学的新方向Whitfield Diffie,Hellman 1976提出了公钥密码算法的概念和思路提出了公钥密码算法的概念和思路提出了数字签名问题提出了数字签名问题提出了提出了DH密钥交换协议密钥交换协议B澄清误解澄清误解公钥算法更安全公钥算法更安全不能简单

2、比较不能简单比较传统对称算法已经过时传统对称算法已经过时事实上，现在使用的是混合密码体制事实上，现在使用的是混合密码体制公钥体制避免了传统公钥体制避免了传统KDC带来的麻烦带来的麻烦事实上，证书体制有其优点但绝非简单事实上，证书体制有其优点但绝非简单公钥算法就是公钥算法就是RSARSA只是当前最重要的公钥算法只是当前最重要的公钥算法B9.1 公钥密码体制的基本原理公钥密码体制的基本原理公钥算法的思路的提出本身就是一个进步。公钥算法的思路的提出本身就是一个进步。遵从公钥体制能够简化密钥管理，能够实现遵从公钥体制能够简化密钥管理，能够实现数字签名等安全特性。数字签名等安全特性。和和DES等对称算法

3、不同，公钥体制的形式和等对称算法不同，公钥体制的形式和结构导致公钥算法必须使用某种数学结构，结构导致公钥算法必须使用某种数学结构，而不能再使用代换和置换等初等方法。而不能再使用代换和置换等初等方法。从形式上看，公钥算法将比对称算法更简洁从形式上看，公钥算法将比对称算法更简洁和易于理解。和易于理解。B公钥密码算法的思路公钥密码算法的思路对称算法的缺陷为事先获得密钥，需另外的安全信道或KDC不能满足签名的需求公钥算法（6个组成部分）密钥 K（Kd，Ke），Kd即私钥 Ke即公钥加密：E（P，Ke）C解密：D（C，Kd）P要求从Ke Kd理论上能够 实际上因需要计算量太大因而难以实施实际上因需要计算

4、量太大因而难以实施B公钥算法参数建立每个用户生成密钥对每个用户生成密钥对(Ke、Kd)Ke或Kd是一个数(大数)而不是随机比特（对称算法中）Ke需要公开Kd得自己秘密保留（本地产生，不需要传输）(公钥 public key 私钥private key 密钥 secret key)公钥的发布公钥的发布从Ke推导Kd的困难性使Ke不怕被公开公钥Ke要在专门机构（CA）登记B一个有趣的问题一个有趣的问题有人提出一种方法，可用来确认你的密钥是否与另有人提出一种方法，可用来确认你的密钥是否与另一人的相同。你首先产生一个与密钥等长的随机二一人的相同。你首先产生一个与密钥等长的随机二进制串进制串P，并将其与

5、密钥，并将其与密钥K1异或，然后把结果异或，然后把结果C发给发给另一人。对方将收到的二进制串另一人。对方将收到的二进制串C与自己的密钥与自己的密钥K2异异或，再将结果或，再将结果P发回给你。你将发回给你。你将P与与P进行核对，就进行核对，就可以知道两个密钥可以知道两个密钥K1和和K2是否相同，在整个过程中是否相同，在整个过程中没有发送真正的密钥。没有发送真正的密钥。这种方法中有一个缺点，你看出来了吗？这种方法中有一个缺点，你看出来了吗？攻击者攻击者可以截获传输的信息可以截获传输的信息C和和P，当两个密钥，当两个密钥K1和和K2相同时，相同时，C=PK1，P=CK2=CK1=P，则攻击者得到则攻

6、击者得到 K1=K2=CP。B公钥算法加密加密（如果有人要给用户A发送消息P）他先获得该用户的公钥Ke加密C=E（P，Ke）传输解密D（C，Kd）=P除非拥有Kd，像用户A，否则不能解密*一般用于传输会话密钥用于传输会话密钥（和签名及认证）B公钥算法用来加密概念图示 B公钥算法用来加密图示 公钥私钥B公钥算法用来认证公钥算法用来认证如果你如果你(Bob)已经公布自己的公钥已经公布自己的公钥Ke，则他人，则他人可鉴别你发出的消息（及你的身份）可鉴别你发出的消息（及你的身份）对于消息对于消息P，使用你的私钥加密，使用你的私钥加密C=E（P，Kd）他人可把密文他人可把密文C用你的公钥解密用你的公钥解

7、密D（C，Ke）=P可以确信可以确信P必然是由你加密成必然是由你加密成C的，因为的，因为加密加密需要的私钥只有你有需要的私钥只有你有。B公钥算法用来认证概念图示 B公钥算法用来认证图示 公钥私钥B公钥算法用来认证公钥算法用来认证如果你有用户如果你有用户A的公钥的公钥Ke，则可鉴别，则可鉴别A的身份的身份取随机秘密消息取随机秘密消息P加密加密C=E（P，Ke）把密文把密文C交给所谓的交给所谓的”A”，请，请A来解密来解密除非除非”A”拥有拥有Kd，否则不能解开，否则不能解开D（C，Kd）P比较比较A解出的明文解出的明文P是否正确是否正确如果如果A能正确解密，则能正确解密，则”A”是所声称的是所声

8、称的AB消息来源鉴别和数字签名消息来源鉴别和数字签名假设使用加解密操作对称的算法加解密操作对称的算法如RSA对消息H签名（整条消息或部分）：S=Sig(H，Kd)接收方对消息H验证：Ver(C，Ke)?=H消息H必然是Kd的持有人签署的B结合使用加密和签名结合使用加密和签名有消息要发给对方，要署名且保密传递有消息要发给对方，要署名且保密传递发送方：先用自己的私钥签名发送方：先用自己的私钥签名发送方：再用对方的公钥加密发送方：再用对方的公钥加密发送发送接收方：先用自己的私钥解密接收方：先用自己的私钥解密接收方：再用对方的公钥验证签名是否有效接收方：再用对方的公钥验证签名是否有效有何缺点？有何缺点

9、？B一个有趣的案例兄弟俩为设计简单又安全的协议而争论不休。哥哥提出如下双方通信协议：假设用户A要将消息M发送给用户B，传输的消息形式为（发送方的标识，消息正文，接收方的标识）。1、A将(A,E(PUb,M,A),B)发送给B。2、B发送应答(B,E(PUa,M,B),A)给A。弟弟认为该协议不够简单，存在一些冗余，可简化为：1、A将(A,E(PUb,M),B)发送给B。2、B发送应答(B,E(PUa,M),A)给A。弟弟的协议确实比较简单，但不如哥哥的协议安全，容易受到某种形式的攻击。若攻击者X也是该网络中的用户，有自己的公钥PUx，并能截获A，B之间传输的信息，则攻击者可以通过某个过程得到A

10、发给B的消息M。他是如何做到的？B公钥密码体制的应用公钥密码体制的应用加密/解密：如RSA，椭圆曲线密码数字签名：如RSA，椭圆曲线密码，DSS密钥交换：如RSA，DHB构造公钥算法的考虑构造公钥算法的考虑对称算法对称算法代换代换置换置换基于某些数学特性基于某些数学特性从公钥推导私钥理论可能，但计算困难从公钥推导私钥理论可能，但计算困难(从私钥到公钥容易从私钥到公钥容易)单向函数单向函数(one-way function)B对公钥算法的要求对公钥算法的要求公钥算法应满足以下条件：公钥算法应满足以下条件：产生密钥对在计算上容易产生密钥对在计算上容易使用公钥加密在计算上容易使用公钥加密在计算上容易

11、使用私钥解密在计算上容易使用私钥解密在计算上容易已知公钥确定私钥在计算上不可行已知公钥确定私钥在计算上不可行已知公钥和密文恢复明文在计算上不可行已知公钥和密文恢复明文在计算上不可行加密和解密对称加密和解密对称B单向函数单向函数单向函数单向函数单向陷门函数单向陷门函数单向散列函数单向散列函数B单向函数单向函数单向性单向性单向函数单向函数函数值计算很容易：已知函数值计算很容易：已知x，很容易计算，很容易计算y=f(x)逆计算是不可行的：已知逆计算是不可行的：已知y，很难计算，很难计算x=f-1(y)困难程度困难程度举例举例打碎打碎/拼接、平方拼接、平方/开方、乘法开方、乘法/分解分解*单向函数是否

12、存在单向函数是否存在尚无严格的数学证明尚无严格的数学证明B单向陷门函数单向陷门函数单向陷门函数单向陷门函数如果知道某个陷门如果知道某个陷门(秘诀秘诀)，就能容易恢复，就能容易恢复x（陷门即为私钥陷门即为私钥）举例举例魔方的置乱魔方的置乱/恢复恢复如果有口诀，就能很快恢复如果有口诀，就能很快恢复加密加密/解密解密B单向散列函数单向散列函数单向散列函数单向散列函数h=H(m)，其中，其中 m 任意长度，任意长度，h 定长定长有的散列函数并不满足单向有的散列函数并不满足单向(抗冲突抗冲突)性质性质密码学上用的散列函数都是指单向散列函数密码学上用的散列函数都是指单向散列函数抗冲突性质抗冲突性质给定给定

13、h，找，找 m 满足满足 H(m)=h 很难很难给定给定m，找，找 m 满足满足 H(m)=H(m)很难很难直接找直接找 m1和和m2 满足满足 H(m1)=H(m2)很难很难举例举例MD5、SHA1B9.2 RSA算法算法作者作者1977年，R,S,ARon Rivest Adi ShamirLen Adleman 基本参数基本参数分组密码算法分组密码算法基于整数乘法基于整数乘法明明/密文分组以及公密文分组以及公/私钥被看作小于私钥被看作小于n的整数的整数加加/解密是模幂运算解密是模幂运算BRSA 加解密加解密加密加密明文分组明文分组M作为整数须小于作为整数须小于nC=Me mod n解密解

14、密M=Cd mod n =Med mod n满足条件满足条件存在存在e,d,n，使得使得 M=Med mod n 成立成立；计算计算 Me mod n 和和 Cd mod n 是容易的是容易的；由由 e,n 确定确定 d 是不可行的是不可行的。ed 1 mod(n)BRSA算法参数建立算法参数建立找素数找素数选取两个选取两个大素数大素数p和和q计算模数计算模数n和欧拉函数和欧拉函数(n)n=pq(n)=(p-1)(q-1)找找 ed 1 mod(n)选取数选取数e，用扩展的欧几里德算法求数，用扩展的欧几里德算法求数d发布发布发布发布(e,n)，这是公钥，这是公钥 ked保密，保密，(d,n)是

15、私钥是私钥 kdBRSA 计算实例计算实例选选 p7，q17则则 npq119且且(n)(p-1)(q-1)61696取取 e5则则 d77 (57738549611 mod 96)公钥（公钥（5，119），私钥（私钥（77，119）加密加密 M19则 CMe mod n=195 mod 119=66解密解密 C66MCd mod n=6677 mod 11919Bab mod n 模幂运算模幂运算97221 mod 2003（都在模（都在模2003意义下）意义下）97221=97128+64+16+8+4+1 =97128 9764 9716 978 974 971依次计算依次计算971、9

16、72、974、978、9716 97128B快速模幂算法快速模幂算法计算计算 f=ab mod nf=1;c=0For each bit of b=bkbk-1b0 f=(ff)mod n;c=2cif bi=1 then f=(fa)mod n;c=c+1End ForB快速模幂算法举例快速模幂算法举例计算计算 f=7560 mod 561 560 表示为 1000110000f=(ff)mod n;c=2cif bi=1 then f=(fa)mod n;c=c+1i9876543210bicf117024904157085261171601352410702980140166028067

17、05601B快速模幂算法举例快速模幂算法举例计算计算 f=7560 mod 561 560 表示为 1000110000f=(ff)mod n;c=2cif bi=1 then f=(fa)mod n;c=c+1i9876543210bicf11702490415708526117160135241070298014016602806705601B快速模幂算法举例快速模幂算法举例计算计算 f=7560 mod 561 560 表示为 1000110000f=(ff)mod n;c=2cif bi=1 then f=(fa)mod n;c=c+1i9876543210bicf1170249041

18、5708526117160135241070298014016602806705601B快速模幂算法举例快速模幂算法举例计算计算 f=7560 mod 561 560 表示为 1000110000f=(ff)mod n;c=2cif bi=1 then f=(fa)mod n;c=c+1i9876543210bicf11702490415708526117160135241070298014016602806705601B快速模幂算法举例快速模幂算法举例计算计算 f=7560 mod 561 560 表示为 1000110000f=(ff)mod n;c=2cif bi=1 then f=(f

19、a)mod n;c=c+1i9876543210bicf11702490415708526117160135241070298014016602806705601BRSA 举例举例若攻击者截获发给用户若攻击者截获发给用户B的密文的密文C=10，用户用户B的公钥的公钥 e=5,n=35，那么明文，那么明文M=？猜测猜测 35=57，则则(n)=46=24d=5,(55 mod 24=1)M=105 mod 35=5BRSA 实现考虑实现考虑选取较小的选取较小的e（较大的（较大的d）e：3、17、65537若指数太小，若指数太小，RSA易受攻击。易受攻击。如：如：三个用户均用三个用户均用e=3，则

20、三个公钥则三个公钥(3,n1),(3,n2),(3,n3)。用户用户A分别给这三个用户发送相同的消息分别给这三个用户发送相同的消息M，则三条密文为则三条密文为若若n1,n2,n3两两互素，则利用中国剩余定理可以两两互素，则利用中国剩余定理可以计算出计算出 M3 mod(n1*n2*n3)，从而恢复明文从而恢复明文M。B使用中国剩余定理加快运算使用中国剩余定理加快运算解密时需要计算解密时需要计算 M=Cd mod n定义一些中间结果定义一些中间结果Vp=Cd mod p Vq=Cd mod qXp=q(q-1 mod p)Xq=p(p-1 mod q)利用利用CRT，得得 M=(VpXp+VqX

21、q)mod nVp=Cd mod p=Cd mod p-1 mod pVq=Cd mod q=Cd mod q-1 mod q可加快约可加快约4倍倍B使用使用CRT加快运算举例加快运算举例计算计算 M=120523 mod 18131813=3749Vp=120523 mod 37=14Vq=120523 mod 49=32Xp=49(49-1 mod 37)=4934Xq=37(37-1 mod 49)=374 M=(VpXp+VqXq)mod n=(493414+37432)mod 1813=865BRSA 密钥产生密钥产生通信之前，每个用户产生一个密钥对通信之前，每个用户产生一个密钥对确

22、定两个素数确定两个素数 p 和和 q选择选择 e 计算计算 d，或者选择，或者选择 d 计算计算 e素数素数必须够大必须够大，否则对手可能很快分解，否则对手可能很快分解n判定，试除法不可行判定，试除法不可行判定，采用判定，采用Miller-Rabin概率测试方法概率测试方法判定N可能是素数BRSA 案例案例在在RSA公钥密码体制中，每个用户都有一公钥密码体制中，每个用户都有一个公钥个公钥e，一个私钥一个私钥d。假定用户假定用户B的私钥已的私钥已泄密泄密。B决定产生新的公钥和新的私钥，而决定产生新的公钥和新的私钥，而不是产生新的模数。请问这样安全吗？不是产生新的模数。请问这样安全吗？B攻击攻击

23、RSA 算法算法穷举穷举穷举所有可能明文穷举所有可能明文M，用，用e加密和加密和C比较比较穷举所有可能的私钥穷举所有可能的私钥d数学方法数学方法分解分解n=pq，就可以计算，就可以计算(n)，就可从，就可从e求得求得d不分解不分解n，而直接求，而直接求(n)，再求再求d 不求不求(n)，直接求，直接求d B分解里程碑分解里程碑十/二进制 日期 MIPS年 方法69/1983 二次筛法 106/1989.100/332 April 1991 7.110/365 April 1992 75.120/398 June 1993 830.129/428 April 1994 5000.130/431

24、April 1996 5000 一般数域筛法140 Feb 1999.155Aug 1999 8400.1601 Apr 2003 格筛法174/576Dec 3,2003.200/663 9 May 2005.B因因子子分分解解所所需需的的MIPS年年B抵抗因子分解抵抗因子分解n如果有特殊结构，则较易被分解，因此：如果有特殊结构，则较易被分解，因此：n要尽量大，当前要尽量大，当前1024位位应该是安全的应该是安全的p和和q应该长度接近，比如都应该长度接近，比如都约约512位位gcd(p-1,q-1)应该比较小应该比较小B计时攻击计时攻击攻击者可以统计解密时间来确定攻击者可以统计解密时间来确定

25、d仅依赖密文仅依赖密文可攻击可攻击DH,RSA,DSS及其它密码系统及其它密码系统以模幂算法为例以模幂算法为例f=(ff)mod n;c=2cif bi=1 then f=(fa)mod n;c=c+1计时攻击从高位到低位，一位一位进行。对有些计时攻击从高位到低位，一位一位进行。对有些f和和a的值，模乘运算的值，模乘运算f=(fa)mod n异常慢。通过异常慢。通过观察执行时间，可猜测观察执行时间，可猜测bi的值。的值。B抵抗计时攻击抵抗计时攻击不变的幂运算时间不变的幂运算时间保证所有的幂运算在返回结果之前，执行时间保证所有的幂运算在返回结果之前，执行时间都相同都相同随机延时随机延时在求幂算法

26、中加入随机延时，来迷惑攻击者在求幂算法中加入随机延时，来迷惑攻击者隐蔽隐蔽在执行幂运算之前在执行幂运算之前先将密文乘上一个随机数先将密文乘上一个随机数，使攻击者不知道计算机正在处理的是密文的哪使攻击者不知道计算机正在处理的是密文的哪些位。些位。BRSA公司使用隐蔽方法公司使用隐蔽方法产生秘密随机数产生秘密随机数 r用随机数用随机数 r 把把 C 掩盖为掩盖为 C把把 C 用私钥用私钥 d 解密得到解密得到 M将将 M 乘以乘以 r-1，即得即得 M利用以上隐蔽方法，利用以上隐蔽方法，运算性能降低了运算性能降低了抵抗计时攻击抵抗计时攻击B选择密文攻击与最佳非对称加密填充选择密文攻击与最佳非对称加

27、密填充攻击者选择一些密文，并利用被攻击者的私钥获得攻击者选择一些密文，并利用被攻击者的私钥获得相应的明文相应的明文利用利用RSA的如下性质的如下性质：若要若要解密解密 C=Me mod n，则攻击者则攻击者计算计算 X=(C2e)mod n将将X发给被攻击者，请他解密，获得发给被攻击者，请他解密，获得 Y=Xd mod n由于由于 X=(C2e)mod n=(C mod n)(2e mod n)=(Me mod n)(2e mod n)=(2M)e mod n则攻击者则攻击者由由 Y=2M mod n 求得明文求得明文M。B选择密文攻击举例选择密文攻击举例设用户设用户B截获了一份发给用户截获了

28、一份发给用户A的密文的密文C，该密文是该密文是用用A的公钥的公钥e加密的。加密的。B想获得原始明文想获得原始明文M。B产生一个小于产生一个小于n的随机数的随机数r，并计算并计算：然后请然后请A对对X进行认证，返回进行认证，返回Y=Xd mod n。试给出试给出B利用获得的信息求取利用获得的信息求取M的过程的过程。B对对RSA的主要支持和批评的主要支持和批评 形式简单，易于理解，研究深入，支持广泛形式简单，易于理解，研究深入，支持广泛既能用来加密，又可签名既能用来加密，又可签名安全性的模糊（疑为等价于因子分解的难度）安全性的模糊（疑为等价于因子分解的难度）随机素数产生并不容易随机素数产生并不容易

29、运算量大，速度受限，尤其在嵌入式设备中运算量大，速度受限，尤其在嵌入式设备中B使用公钥传递会话密钥使用公钥传递会话密钥公钥算法太慢公钥算法太慢对称算法一般几十兆字节/秒1024位RSA解密约100多次/秒(加密快10倍以上)只用来传递会话密钥只用来传递会话密钥(假设A已经有B的公钥KeB)A发起和B的通信A产生会话密钥Ks，并用KeB加密后传给BB能用自己的私钥KdB解开他人不会知道KsB对称算法对称算法 vs.公钥算法公钥算法安全性安全性速度速度典型相差典型相差1000倍倍密钥管理密钥管理对称算法需要额外安全信道对称算法需要额外安全信道公钥：证书中心公钥：证书中心CA混合密码体制混合密码体制公钥算法用于签名和认证公钥算法用于签名和认证用公钥算法传输会话密钥用公钥算法传输会话密钥用会话密钥用会话密钥/对称算法加密批量对称算法加密批量(bulk)数据数据B小结上世纪70年代，公钥算法的思想以及其后的RSA算法开启了密码学的新阶段。而互联网在90年代的爆发引导密码学进入了应用时代，以RSA公钥算法为基础的PKI设施是今天网络安全的基石。RSA算法的一个很好的特性是其操作对称性，因此RSA算法可以用来加/解密，同时也可以用来做签名/验证。