信息安全必威体育官网网址技术chap23.pptVIP

公开密钥算法 对称密码的最大问题：密钥交换 公开密钥算法 对称密码的第二大问题：密钥管理 N个用户之间相互通信，每人需要保存N-1个密钥，系统需要完成N×(N-1)÷2次密钥的交换 一个5000用户的网络，要保证每个用户能相互加密通信，总共需要完成12,497,500次密钥交换 公开密钥算法 对称密码的第三大问题：抵赖 密钥协商和加密过程是双方行为，无法防止其中一方否认自己曾经发送过某条消息 公开密钥算法 新的思路：加密与解密由不同的密钥完成 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 具有划时代的意义 又被称为非对称密码或双钥密码 公开密钥算法 公开密钥算法的特点 加密: C = EKpub(P) 解密: P = DKprv(C) = DKprv(EKpub(P)) 两个密钥不可相互推导（或推导的难度不亚于密码分析） 其中一个密钥公开Kpub(公钥)，另一个必威体育官网网址Kprv(私钥) 每个用户掌握一个私钥，并把相应的公钥放在公共目录中 公开密钥算法 公钥算法的使用方式 用于加密(公钥加密私钥解密)，不需要交换密钥 公开密钥算法 公钥算法的使用方式 用于鉴别(私钥加密公钥解密)，可防抵赖 公开密钥算法 Diffie-Hellman密钥交换算法 Whitfield Diffie和Martin Hellman发明于1976年 是第一个公开密钥算法，开创了密码学领域新时代 允许两个用户可以安全地交换一个秘密信息，用于后续的通讯过程 算法的安全性依赖于计算离散对数的难度 公开密钥算法 素数和它的原根(原始根) 素数p的原根定义：如果a是素数p(ap)的原根，则数列 a mod p, a2 mod p, … , ap-1 mod p 是不同的并且包含1到p-1的整数的某种排列。 对任意的整数bp，我们可以找到唯一的幂i满足 b=ai mod p 0=i=(p-1) 公开密钥算法 列表法可找出13的原根为2，6，7，11 列出ai mod 13 公开密钥算法 可根据列表发现规律 ap-1 mod p ＝1 或者ap-1 ≡ 1 mod p 费尔马定律 ap mod p ＝a 费尔马定律推论 如果a是原根，则：a(p-1)/2 mod p = p-1 公开密钥算法 计算离散对数的难度 定义：若a是素数p的一个原根,则对任意整数bp, b≠0,存在唯一的整数i,1≤i≤(p-1),使得: b≡ai mod p称i为“b以a为基模p的指数(离散对数)” 例：8是9以2为基模13的离散对数 计算离散对数 已知a、i、p求b是容易的 已知a、b、p求i是困难的 公开密钥算法 Diffie-Hellman算法描述 ① A和B协商一个大的素数n和它的原根g，这两个数可以公开，所以可以通过不安全的途径协商。 ② A选取一个大的随机整数x并且计算X＝gx mod n并把X发送给B ③ B选取一个大的随机整数y并且计算Y＝gy mod n并把Y发送给A ④ A计算k＝Yx mod n＝gxy mod n ⑤ B计算k’＝Xy mod n＝gxy mod n＝k K即为DH算法协商的密钥 公开密钥算法 Diffie-Hellman算法示意 公开密钥算法 Diffie-Hellman算法示例 ① A和B协商一个素数n＝13和它的原根g＝7； ② A选取一个随机整数x＝20，计算X＝gx mod n＝720 mod 13＝3，并把X＝3发送给B ③ B选取一个随机整数y＝30，计算Y＝gy mod n＝730 mod 13＝12并把Y＝12发送给A ④ A计算k＝Yx mod n＝1220 mod 13＝1 ⑤ B计算k’＝Xy mod n＝330 mod 13＝1 DH算法协商的密钥为1 公开密钥算法 指数求模小技巧 am mod n＝a(n-1)+m-n+1mod n＝am-n+1mod n 720 mod 13＝(712×78) mod 13＝78 mod 13 查表可知78 mod 13＝3 730 mod 13＝ 718 mod 13＝ 76 mod 13 查表可知76 mod 13＝12 公开密钥算法 Diffie-Hellman算法练习 A和B协商素数n＝13和它的原根g＝6，A随机选取x＝35，B随机选取y＝31，求密钥交换结果