九章节公钥密码学.ppt
第九讲 公钥密码学,上海交通大学计算机科学与工程系,1.对称密码体制的缺陷：,2.Public-Key Cryptography,public-key/two-key/asymmetric 包括两个密钥:公开密钥(a public-key),可以被任何人知道,用于加密或验证签名私钥(private-key),只能被消息的接收者或签名者知道,用于解密或签名加密或验证签名者不能解密或多或生成签名.是密码学几千年历史中最有意义的结果,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)用于交换秘密信息(依赖于双方主体)常用于对称加密算法的密钥Public Key Encryption(PKE)用于加密任何消息 任何人可以用公钥加密消息 私钥的拥有者可以解密消息 任何公钥加密方案能够用于密钥分配方案PKDS 许多公钥加密方案也是数字签名方案Signature Schemes 用于生成对某消息的数字签名私钥的拥有者生成数字签名任何人可以用公钥验证签名,6.公钥的安全性,依赖于足够大大的困难性差别类似与对称算法,穷搜索在理论上是能够破解公钥密码 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,pp644-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 and Bob 计算他们的公开密钥:yA=axA mod p yB=axB mod p Alice,Bob 分别公开 yA,yB,10.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选取秘密 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 A=SUM ai.bi i=0,16.小结,公钥密码的概念 Diffie-Hellman 公钥分配方案,练习,Illustrate the operation of the Diffie-Hellman public key exchange 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!,
