九章节公钥密码学.ppt

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

1、九章节公钥密码学 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望1.对称密码体制的缺陷：2.Public-Key Cryptography public-key/two-key/asymmetricpublic-key/two-key/asymmetric 包括两个密钥:公开密钥(a public-key)public-key),可以被任何人知道,用于加密或验证签名私钥(private-key)private-key),只能被消息的接收者或签名者知道,用于解密或签

2、名加密或验证签名者不能解密或多或生成签名.是密码学几千年历史中最有意义的结果3.公钥加密方案4.公钥密码理论由私钥及其他密码信息容易计算出公开密钥(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)w用于交换秘

3、密信息(依赖于双方主体)w常用于对称加密算法的密钥Public Key Encryption(PKE)w用于加密任何消息 w任何人可以用公钥加密消息 w私钥的拥有者可以解密消息 w任何公钥加密方案能够用于密钥分配方案PKDS w许多公钥加密方案也是数字签名方案Signature Schemes w用于生成对某消息的数字签名w私钥的拥有者生成数字签名w任何人可以用公钥验证签名 6.公钥的安全性依赖于足够大大的困难性差别类似与对称算法,穷搜索在理论上是能够破解公钥密码 exhaustive searchexhaustive search 但实际上,密钥足够长(512bits)一般情况下,有一些已知

4、的困难问题(hardhard 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,pp644-654,Nov 1976 James Ellis(UK CESG)在案970年曾提出此概念8.公钥分配方案不能用于交换任意消息 可以建立共享密钥(

5、双方共享)依赖于双方的公、私钥值 基于有限域上的指数问题 安全性是基于计算离散对数的困难性 9.Diffie-Hellman Setup 两个通信主体Alice&Bob,希望在公开信道上建立密钥初始化:选择一个大素数p(200 digits)一个生成元 Alice 选择一个秘密钥(secret key(number)xA p)Bob)选择一个秘密钥(secret key(number)xB p Alice and Bob 计算他们的公开密钥:yA=axA mod p yB=axB mod p Alice,Bob 分别公开 yA,yB10.Diffie-Hellman 密钥交换密钥交换计算共享密

6、钥:KAB=axA.xB mod p =yAxB mod p(which B B can compute)=yBxA mod p(which A A can compute)KAB 可以用于对称加密密钥11.Diffie-Hellman 举例举例 选取素数 p=97,及本根 a=5 Alice 选取秘密 xA=36&计算公钥 yA=536=50 mod 97 Bob选取秘密 xB=58&计算公钥 yB=558=44 mod 97 Alice and Bob 交换公钥(50&44 respectively)Alice 计算公享秘密 K=4436=75 mod 97 Bob计算公享秘密 K=505

7、8=75 mod 97 12.Diffie-Hellman in Practise两个主体每次可以选择新的秘密密钥(私钥),并计算及交换新的公钥可以抵抗被动攻击,但不能抵抗主动攻击每次可以给出新的密钥 为抵抗主动攻击,需要其它新的协议也可以建立长期公钥,13.快速模运算Chivers(1984)快速运算:given an integer A n-1 A=SUM ai.bi i=0 16.小结小结 公钥密码的概念 Diffie-Hellman 公钥分配方案练习1.Illustrate the operation of the Diffie-Hellman public key exchange

8、scheme,given the following public parameters:prime p=37 prim root a=5 Compute suitable public keys for users Alice and Bob,and illustrate the key exchange,verifying that the same shared session key is obtained.2.Illustrate the operation of the Diffie-Hellman public key exchange scheme,given the following public parameters:prime p=59 prim root a=6 As above.END!