九章节公钥密码学ppt课件

1、第九讲 公钥密码学上海交通大学计算机科学与工程系 1） 密钥分配问题密钥分配问题 通信双方要进行加密通信， 需要通过秘密的安全信道协商加密密钥，而这种安全信道可能很难实现； 2） 密钥管理问题密钥管理问题 在有多个用户的网络中， 任何两个用户之间都需要有共享的秘密钥，当网络中的用户 n 很大时，需要管理的密钥数目是非常大 2/ ) 1( nn。 3） 没有签名功能：没有签名功能：当主体 A 收到主体 B 的电子文挡（电子数据）时，无法向第三方证明此电子文档确实来源于 B。 1. 对称密码体制的缺陷： 2.Public-Key Cryptography public-key/two-key/as

2、ymmetric public-key/two-key/asymmetric 包括两个密钥包括两个密钥: :公开密钥公开密钥(a public-key), (a public-key), 可以被任何人知道可以被任何人知道, , 用于加密或验证签名用于加密或验证签名私钥私钥( private-key), ( private-key), 只能被音讯的接纳者或签只能被音讯的接纳者或签名者知道名者知道, ,用于解密或签名用于解密或签名加密或验证签名者不能解密或多或生成签名加密或验证签名者不能解密或多或生成签名. .是密码学几千年历史中最有意义的结果是密码学几千年历史中最有意义的结果3.公钥加密方案4.

3、公钥密码实际由私钥及其他密码信息容易计算出公开密钥 (a polynomial time (P-time) problem) 由公钥及算法描画,计算私钥是难的 (an NP-time problem) 因此,公钥可以发布给其他人(wishing to communicate securely with its owner )密钥分配问题不是一个容易的问题(the key distribution problem )5.公钥算法分类Public-Key Distribution Schemes (PKDS) 用于交换信息用于交换信息(依赖于双方主体依赖于双方主体) 常用于对称加密算法的密钥常用于

4、对称加密算法的密钥Public Key Encryption (PKE) 用于加密任何音讯用于加密任何音讯 任何人可以用公钥加密音讯任何人可以用公钥加密音讯 私钥的拥有者可以解密音讯私钥的拥有者可以解密音讯 任何公钥加密方案可以用于密钥分配方案任何公钥加密方案可以用于密钥分配方案PKDS 许多公钥加密方案也是数字签名方案许多公钥加密方案也是数字签名方案Signature Schemes 用于生成对某音讯的数字签名用于生成对某音讯的数字签名私钥的拥有者生成数字签名私钥的拥有者生成数字签名任何人可以用公钥验证签名任何人可以用公钥验证签名 6.公钥的平安性依赖于足够大大的困难性差别类似与对称算法,穷

5、搜索在实际上是可以破解公钥密码 exhaustive search 但实践上,密钥足够长 (512bits) 普通情况下,有一些知的困难问题(hard problem 要求足够大的密钥长度 (512 bits) 导致加密速度比对称算法慢7.Diffie-Hellman 密钥分配方密钥分配方案案公钥密码问世 Diffie & Hellman in 1976: 密钥交换的实践方法 公钥方案概念的提出W Diffie, M E Hellman, New directions in Cryptography, IEEE Trans. Information Theory, IT-22, pp6

6、44-654, Nov 1976 James Ellis (UK CESG) 在案970年曾提出此概念8.公钥分配方案不能用于交换恣意音讯 可以建立共享密钥 (双方共享)依赖于双方的公、私钥值 基于有限域上的指数问题 平安性是基于计算离散对数的困难性 9. Diffie-Hellman Setup 两个通讯主体Alice & Bob ,希望在公开信道上建立密钥初始化: 选择一个大素数p (200 digits) 一个生成元 Alice 选择一个钥( secret key (number) xA p )Bob)选择一个钥( secret key (number) xB p Alice a

7、nd Bob 计算他们的公开密钥: yA = axA mod p yB = axB mod p Alice , Bob 分别公开 yA , yB10. Diffie-Hellman 密钥交换密钥交换计算共享密钥: KAB = axA.xB mod p = yAxB mod p (which B can compute) = yBxA mod p (which A can compute) KAB 可以用于对称加密密钥11. Diffie-Hellman 举例举例 选取素数 p=97 ,及本根 a=5 Alice 选取 xA=36 & 计算公钥 yA=536=50 mod 97 Bob选

8、取 xB=58 &计算公钥 yB=558=44 mod 97 Alice and Bob 交换公钥 (50 & 44 respectively) Alice 计算公享 K=4436=75 mod 97 Bob计算公享 K=5058=75 mod 97 12. Diffie-Hellman in Practise两个主体每次可以选择新的密钥(私钥),并计算及交换新的公钥可以抵抗被动攻击,但不能抵抗自动攻击每次可以给出新的密钥 为抵抗自动攻击,需求其它新的协议也可以建立长期公钥,13.快速模运算Chivers (1984) 快速运算: given an integer A n-1

9、A = SUM ai.bi i=0 16. 小结小结 公钥密码的概念 Diffie-Hellman 公钥分配方案练习wIllustrate the operation of the Diffie-Hellman public key exchange scheme, given the following public parameters:w prime p=37 w prim root a=5 w Compute suitable public keys for users Alice and Bob, and illustrate the key exchange, verifying that the same shared session key is obtained. w2. Illustrate the operation of the Diffie-Hellman public key exchange scheme, given the following public parameters:wprime p=59 wprim root a=6w As above. END!交换协议描述如下：1) A 和 B 公开选择一个有限群 G 及一个群元素 G。2）A 生成一个随机整数 a， ，在群 G 中计算a，并把计算结果在公开信