【安全课件】第19讲--公钥密码概述

1、量子密码研究室量子密码研究室王王 滨滨2005.4.12 公开密钥算法的提出公开密钥算法的提出公钥密码学是公钥密码学是1976年由年由Diffie和和Hellman在其在其“密码学密码学新方向新方向”一文中提出的，见文献：一文中提出的，见文献： W.Diffie and M.E.Hellman, New Directrions in Cryptography， IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654公开密钥算法公开密钥算法 公开密钥算法是非对称算法，即密钥分为公钥和私公开密钥算法是非对

2、称算法，即密钥分为公钥和私钥，因此称双密钥体制钥，因此称双密钥体制 双钥体制的公钥可以公开，因此也称公钥算法双钥体制的公钥可以公开，因此也称公钥算法 公钥算法的出现，给密码的发展开辟了新的方向。公钥算法的出现，给密码的发展开辟了新的方向。公钥算法虽然已经历了公钥算法虽然已经历了2020多年的发展，但仍具有强劲多年的发展，但仍具有强劲的发展势头，在鉴别系统和密钥交换等安全技术领域的发展势头，在鉴别系统和密钥交换等安全技术领域起着关键的作用起着关键的作用加密与解密由不同的密钥完成加密与解密由不同的密钥完成 加密：加密： 解密：解密：知道加密算法，从加密密钥得到解密密钥在计算上是知道加密算法，从加密

3、密钥得到解密密钥在计算上是不可行的不可行的两个密钥中任何一个都可以作为加密而另一个用作解两个密钥中任何一个都可以作为加密而另一个用作解密（不是必须的）密（不是必须的）公开密钥算法的基本要求公开密钥算法的基本要求:( )KUXY Y EX:( )( )KRKRKUYX XDYDEX基于公开密钥的加密过程基于公开密钥的加密过程用公钥密码实现保密用公钥密码实现保密 用户拥有自己的密钥对用户拥有自己的密钥对(KU,KR) 公钥公钥 KU公开，私钥公开，私钥KR保密保密:( )bKUAB YEX:( )( )bbbKRKRKUB DYDEXX基于公开密钥的鉴别过程基于公开密钥的鉴别过程用公钥密码实现鉴别

4、用公钥密码实现鉴别 条件：两个密钥中任何一个都可以用作加密而另外条件：两个密钥中任何一个都可以用作加密而另外一个用作解密一个用作解密鉴别：鉴别： 鉴别保密鉴别保密 :( ):( )( )aabaKRKUKUKRAALL YEXALL DYDEXX:():( )baabKUKRKUKRAB ZEDXB EDZX公开密钥算法公开密钥算法公钥算法的种类很多，具有代表性的三种密码：公钥算法的种类很多，具有代表性的三种密码： 基于整数分解难题（基于整数分解难题（IFPIFP）的算法体制的算法体制 基于离散对数难题（基于离散对数难题（DLPDLP）算法体制算法体制基于椭圆曲线离散对数难题（基于椭圆曲线离散

5、对数难题（ECDLPECDLP）的算法体制的算法体制Diffie-Hellman密钥交换算法密钥交换算法Diffie-Hellman公钥技术公钥技术人工手动分配密钥人工手动分配密钥: 问题问题 效率低效率低成本高成本高每个用户要存储与所有用户通信的密钥每个用户要存储与所有用户通信的密钥安全性差安全性差机器自动分配密钥机器自动分配密钥: 要求要求任何两个用户能独立计算他们之间的秘密密钥任何两个用户能独立计算他们之间的秘密密钥传输量小传输量小存储量小存储量小任何一个任何一个(或多个或多个)用户不能计算出其他用户之间用户不能计算出其他用户之间的秘密密钥的秘密密钥单向陷门函数函数单向陷门函数函数 满足

6、下列条件的函数满足下列条件的函数f f： (1) 给定给定x，计算计算y=f(x)是容易的是容易的 (2) 给定给定y, 计算计算x使使y=f(x)是困难的是困难的 (3) 存在存在z，已知已知z 时时, 对给定的任何对给定的任何y，若相应的若相应的x存在，则计算存在，则计算x使使y=f(x)是容易的是容易的所谓计算所谓计算x= x= f-1(Y)(Y)困难是指计算上相当复杂，已无困难是指计算上相当复杂，已无实际意义实际意义单向陷门函数说明单向陷门函数说明仅满足仅满足(1)、(2)两条的称为单向函数；第两条的称为单向函数；第(3)条称为陷门性，条称为陷门性，z 称为陷门信息称为陷门信息当用陷门

7、函数当用陷门函数f作为加密函数时，可将作为加密函数时，可将f公开，这相当于公公开，这相当于公开加密密钥，此时加密密钥便称为公开密钥，记为开加密密钥，此时加密密钥便称为公开密钥，记为Pkf函数的设计者将函数的设计者将z保密，用作解密密钥，此时保密，用作解密密钥，此时z称为秘密称为秘密钥匙，记为钥匙，记为Sk。由于设计者拥有由于设计者拥有Sk，他自然可以解出他自然可以解出x=f-1(y)单向陷门函数的第单向陷门函数的第(2)条性质表明窃听者由截获的密文条性质表明窃听者由截获的密文y=f(x)推测推测x是不可行的是不可行的Diffie-Hellman密钥交换算法密钥交换算法Diffie和和Hellm

8、an在其里程碑意义的文章中，虽然给出在其里程碑意义的文章中，虽然给出了密码的思想，但是没有给出真正意义上的公钥密码了密码的思想，但是没有给出真正意义上的公钥密码实例，也既没能找出一个真正带实例，也既没能找出一个真正带陷门陷门的单向函数的单向函数然而，他们给出单向函数的实例，并且基于此提出然而，他们给出单向函数的实例，并且基于此提出Diffie-Hellman密钥交换算法密钥交换算法Diffie-Hellman密钥交换算法的原理密钥交换算法的原理基于有限域中计算离散对数的困难性问题之上：设基于有限域中计算离散对数的困难性问题之上：设F为有限域，为有限域，gF是是F的乘法群的乘法群 F*=F0=，

9、并且对并且对任意正整数任意正整数x，计算计算gx是容易的；但是已知是容易的；但是已知g和和y求求x使使y= gx，是计算上几乎不可能的是计算上几乎不可能的Diffie-Hellman密钥交换协议描述密钥交换协议描述Alice和和Bob协商好一个大素数协商好一个大素数p，和大的整数和大的整数g，1gp，g最好是最好是FP中的本原元，即中的本原元，即FP*p和和g无须保密，可为网络上的所有用户共享无须保密，可为网络上的所有用户共享Diffie-Hellman密钥交换协议描述密钥交换协议描述当当Alice和和Bob要进行保密通信时，他们可以按如下步骤来要进行保密通信时，他们可以按如下步骤来做：做：

10、(1) Alice选取大的随机数选取大的随机数x，并计算并计算 X = gx (mod P) (2) Bob选取大的随机数选取大的随机数y，并计算，并计算 Y = gy (mod P) (3) Alice将将X传送给传送给Bob；Bob将将Y传送给传送给Alice (4) Alice计算计算K= (Y)x(mod P); Bob计算计算K =（X) y(mod P), 易见，易见，K = K =g xy (mod P)由由(4)知，知，Alice和和Bob已获得了相同的秘密值已获得了相同的秘密值K双方以双方以K作为加解密钥以传统对称密钥算法进行保密通信作为加解密钥以传统对称密钥算法进行保密通信

11、DH协议分析协议分析o优点优点:o(1) 任何两个人都可协商出会话密钥任何两个人都可协商出会话密钥,不需事先拥不需事先拥有对方的公开或秘密的信息有对方的公开或秘密的信息.o(2) 每次密钥交换后不必再保留秘密信息每次密钥交换后不必再保留秘密信息,减少了减少了保密的负担保密的负担.o前提条件前提条件:o必须进行身份认证必须进行身份认证,确保不是与假冒的用户进行确保不是与假冒的用户进行密钥交换密钥交换,否则不能抵抗中间人攻击否则不能抵抗中间人攻击.中间人攻击中间人攻击o-攻击者攻击者W在信道中间在信道中间,假冒假冒U与与V进行密进行密钥交换钥交换,同时假冒同时假冒V与与U进行密钥交换进行密钥交换.

12、致使致使看似看似U与与V交换的密钥交换的密钥,实际上都是与攻击实际上都是与攻击者交换的密钥者交换的密钥.具体攻击具体攻击具体方法具体方法o攻击者W在信道上截获 和 后,不将它们送给用户V和用户U,而是随机选取整数 ,并计算出 将它明传给用户U,同时暂时保留;同时随机选取整数 ,并计算出 后,将明传给用户V,同时暂时保留 .puxmodpvxmod21:11pxxwwpwxmod11wx21:22pxxwwpwxmod22wx具体方法具体方法o用户用户U计算出计算出o用户用户V计算出计算出o攻击者攻击者W分别计算出分别计算出o分别作为解密用户分别作为解密用户U发给用户发给用户V的密钥和的密钥和解密用户解密用户V发给用户发给用户U的密钥的密钥.ppkuwxxmod)mod(11ppkvwxxmod)mod(22ppkwuxxumod)mod(1ppkwvxxvmod)mod(2具体方法具体方法o攻击者截获用户攻击者截获用户U发给发给V的密文后的密文后,不传给用户不传给用户V,而是解读出明文后再将明文用而是解读出明文后再将明文用W与与V的密钥加的密钥加