公钥密码体系

1、第3讲 公钥密码体制,王志伟 计算机学院 信息安全系 ,2020/7/10,南京邮电大学,2,本讲内容,公钥密码体制的设计原理,1,Diffie-Hellman密钥交换,2,RSA （椭圆曲线密码体制）,3,公钥密码体制的应用,4,2020/7/10,南京邮电大学,3,1 公钥密码体制,公钥密码体制的引 入 公钥密码体制数学基础,在对称密码体制中，消息的发送方和接收方必须在密文传输之前通过安全信道进行密钥传输。而实际的传输信道安全性并不理想，所以密钥在传输过程中被暴露的风险很大。,公钥密码的最大优点在于针对密钥管理方法的改进。在公钥密码系统中，加密密钥是公开的，任何人都可以采用这些公开的加密密

2、钥对消息进行加密。同时只有正确的接收方才能够用自己所保管的解密密钥对密文进行解密。这些解密密钥需要妥善保存。,提供单向函数的数学难题（NP完全问题- Non-deterministic Polynomial COMPLETE问题）。,对于一个函数f(x),如果对于其定义域上的任意x，f(x)都容易计算，同时，对于其值域中几乎所有的取值y，计算其逆函数f-1(y)都是不可行的。,大整数分解问题 离散对数问题 椭圆曲线离散对数问题,2020/7/10,南京邮电大学,4,1 公钥密码体制,明文,私钥d,公钥e,明文,密文,加密器 Ek,解密器 Dk,2020/7/10,南京邮电大学,5,1 公钥密码

3、体制,公钥密码体制的应用领域,-消息的机密性,-密钥分配 利用通信双方已有的公钥、私钥对计算出一个公有的密钥，用于通信加密。 Diffie-Hellman,-认证消息的来源 和 消息的完整性,参见课本P96页图7.1,参见课本P96页图7.2,双重加解密同时实现认证和机密性，具体参见课本P97页图7.3,2020/7/10,南京邮电大学,6,1.1 公钥算法,Diffie-Hellman密钥分配协议 第一个公开发表的公钥密码算法 只用于密钥分配 并不能完成信息加解密 RSA是目前为止最为成功的非对称密码算法 第一个比较完善的公钥系统 Rivest, Shamir and Adleman,202

4、0/7/10,南京邮电大学,7,本讲内容,公钥密码体制的设计原理,1,Diffie-Hellman密钥交换,2,RSA （椭圆曲线密码体制）,3,公钥密码体制的应用,4,2020/7/10,南京邮电大学,8,2 Diffie-Hellman,Diffie-Hellman是一个简单的公钥算法，用于实现密钥交换。这个协议是的通信的双方利用基于离散对数问题的公钥算法建立秘密钥。 这个协议是安全的，仅当通信双方的真实性能够得到保证。,2020/7/10,南京邮电大学,9,2 Diffie-Hellman,公开: g 和 n 秘密: Alice的指数 a, Bob的指数b,Alice, a,Bob, b

5、,ga mod n,gb mod n,Alice 计算 (gb)a = gba = gab mod n Bob 计算 (ga)b = gab mod n 他们可以使用 K = gab mod n 做为对称密钥,2020/7/10,南京邮电大学,10,2.1 举例,选定n=97,g=5 Alice选择自己的私有密钥 a=36,则她的公钥是 X536 mod 97 50 Bob选择自己的私有密钥 b=58,则他的公钥是 Y558 mod 97 = 44 用户Alice和Bob互换公钥后，都可以计算出 Alice方：k = Ya mod 97 = 4436 mod 97 = 75 Bob方： k =

6、 Xb mod 97 = 5058 mod 97 = 75,2020/7/10,南京邮电大学,11,本讲内容,公钥密码体制的设计原理,1,Diffie-Hellman密钥交换,2,RSA （椭圆曲线密码体制）,3,公钥密码体制的应用,4,2020/7/10,南京邮电大学,12,3 RSA密码体制,安全性是建立在“大数分解和素性检测”这个数论难题的基础上。 既将两个大素数相乘在计算上容易实现，而将该乘积分解的计算量相当大 虽然安全性没有能得到理论证明，但20多年的实践证明其是安全的,2020/7/10,南京邮电大学,13,3.1 RSA算法的密钥,选取两个大素数p 与q，然后算出n=pq，(n)

7、=(p-1)(q-1)， 再选取一个正整数e，使之满足(e，(n)=1，1e(n)，其中( )表示求最大公约数； 再求出正整数d，使之满足1d(n)，且使 de 1 mod (n)。 然后用n，e作为公钥，n，d作为私钥,2020/7/10,南京邮电大学,14,3.2 RSA算法的加解密,加密 C=Me mod n 解密 M=Cd mod n,2020/7/10,南京邮电大学,15,3.3 举例,选取两个“大”素数p11，q3 npq33 (n)=(p-1)(q-1)20 选择e3，因为3与20互质 再求出正整数d，使之满足1d(n)，且使 d3 1 mod 20 所以d7 公钥（n，e）（3

8、3，3） 私钥（n，d）（33，7）,2020/7/10,南京邮电大学,16,3.3 举例,公钥（n，e）（33，3） 私钥（n，d）（33，7） 假设明文是 M8 密文是 C = Me mod n = 83 = 512 = 17 mod 33 明文是 M = Cd mod n = 177 = 410,338,673 = 12,434,505 33 + 8 = 8 mod 33,2020/7/10,南京邮电大学,17,3.4 文本加密,令26个字母对应0-25 设明文为 Mpublic E(p)=153 = 9 mod 33 E(u)=203 = 14 mod 33 E(b)=13 = 1 m

9、od 33 E(l)=113 = 11 mod 33 E(i)=83 = 17 mod 33 E(c)=23 = 8 mod 33 则c E（M） 09 14 01 11 17 28 joblri,2020/7/10,南京邮电大学,18,3.5 文本解密,收到密文后用d=7进行解密 D(j)= 097 = 15 mod 33, 即明文 p D(o)= 147 = 20 mod 33, 即明文 u D(b)= 017 = 1 mod 33, 即明文 b D(l)= 117 = 11 mod 33, 即明文 l D(r)= 177 = 8 mod 33, 即明文 i D(i)= 087 = 2 m

10、od 33, 即明文 c,2020/7/10,南京邮电大学,19,RSA算法中的计算问题,求一个整数的整数次幂 如果按其含义直接计算，则中间结果运算量非常大 如何提高加、解密运算中指数运算的有效性？ 利用模运算的性质 重复对每个部分结果做平方,参见课本P99-100页 不作要求,2020/7/10,南京邮电大学,20,RSA讨论,RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。 RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。 RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RS

11、A的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。,2020/7/10,南京邮电大学,21,RSA算法分析,R. L. Rivest等人证明：攻破RSA加密算法的计算复杂度等同于分解大数n的计算复杂度。 1994年, 一个小组利用因特网上1600台计算机, 经过8个月的计算, 攻破了公钥长度为129位十进制数(约428比特)的RSA(这种攻击意义不大). 现在通常认为, 采用1024比特密钥长度(约300位十进制数)是比较安全的.,2020/7/10,南京邮电大学,22,RSA缺点,A)产生密钥很麻烦，受到素数产

12、生技术的限制，因而难以做到一次一密。 B)分组长度太大，为保证安全性，n 至少也要 600 bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级； 随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。,椭圆曲线算法,DES和RSA性能比较(同等强度）,3.6 椭圆曲线算法,2020/7/10,南京邮电大学,24,1985年，N. Koblitz和V. Miller分别独立提出了椭圆曲线密码体制(ECC)，其依据就是定

13、义在椭圆曲线点群上的离散对数问题得难解性。,椭圆曲线算法可以用来开发许多椭圆曲线密码方案，包括密钥交换、加密和数字签名。,ECC和RSA性能比较,与同等安全性的RSA相比，由于ECC使用的密钥更短，计算速度更快。,2020/7/10,南京邮电大学,26,本讲内容,公钥密码体制的设计原理,1,Diffie-Hellman密钥交换,2,RSA （椭圆曲线密码体制）,3,公钥密码体制的应用,4,2020/7/10,南京邮电大学,27,公钥与以前的密码学不同之处,传统的密码基于混淆和发散，使用替换和置换技术 公钥基于数学函数的求解复杂度 非对称的两个密钥 应用范围更广，消息的保密性、密钥的分配和认证领

14、域,2020/7/10,南京邮电大学,28,公钥vs私钥,公钥体制大大简化了复杂的密钥分配管理问题 公钥要比私钥慢得多 慢约1000倍 公钥用于认证（数字签名、身份识别等）和密钥管理 私钥用于信息加密,2020/7/10,南京邮电大学,29,对于公钥的误解一,公钥密码比传统密码更安全？ 不是！ 任何加密方法安全性依赖于密钥的长度和破译密文所需要的计算量。,2020/7/10,南京邮电大学,30,对于公钥的误解二,公钥是一种通用的方法，传统密码已经过时？ 不是！ 公钥的计算量大，目前不能取代传统密码 “公钥密码学仅限于用在密钥管理和签名此类应用上，这几乎是被广泛接受的事实”,2020/7/10,南京邮电大学,31,对于公钥的误解三,传统密码中与密钥分配中心KDC的握手是一件麻烦的事情 公钥的密钥管理非常简单？ 不！ 也需要某种形式的协议，该协议一般包含一个中心代理，处理并不比传统密码中的那些工程更简单,2020/7/10,南京邮电大学,32,公钥算法应用：加密,2020/7/10,南京邮电大学,33,用公钥密码实现保密,用户拥有自己的密钥对(KU,KR) 公钥KU公开,私钥KR保密 A: