9.1 Diffie- Hellman密钥交换 Dfle和 Hellman在1976年首次提出了公钥算法, 给出了公钥密码学的定义,该算法通常被称为 Dffe- Hellman密钥交换算法 丶 Diffie- Hellman密钥交换算法是一种公钥分发机制 它不是用来加密消息的 所生成的是通信双方共享的会话密钥,必须保密,其 值取决于通信双方的私钥和公钥信息 Diffie- Hellman密钥交换算法是基于有限域GF中 的指数运算的(模一素数或多项式) 丶 Diffie- Hellmanη密钥交换算法的安全性依赖于求解 离散对数问题DLP ash NolL. edu.cn 现代密码學港学理奖践-10
mfy@ustc.edu.cn 2021/1/31 现代密码学理论与实践 现代密码学理论与实践-10 66/54 /57 Diffie和Hellman在1976年首次提出了公钥算法， 给出了公钥密码学的定义，该算法通常被称为 Diffie-Hellman密钥交换算法 Diffie-Hellman密钥交换算法是一种公钥分发机制 ◦ 它不是用来加密消息的 ◦ 所生成的是通信双方共享的会话密钥，必须保密，其 值取决于通信双方的私钥和公钥信息 Diffie-Hellman密钥交换算法是基于有限域GF中 的指数运算的(模一素数或多项式) Diffie-Hellman密钥交换算法的安全性依赖于求解 离散对数问题DLP
9.1.1离散对数问题回顾 如果a是素数p的一个原根(本原元素),则 a mod p,a2modp,……,ap- mod p,生成模p的完全剩余集 {1,2 ·"■··· 对于所有素数,其原根必定存在,即 对于一个整数b和素数p的一个原根,可以找到唯一的指数,使得 b= a' mod p,其中0<=i<=p-1 指数i为b的以a为基数的模p的离散对数或者指数。 〉离散对数密码体制的安全性基于DLP问题,在下式中已知C和P 的情况下,由d求M很容易,由M求d很困难, d= log M in GF(P), 最快的算法需要T=eXp(n(Pnn(P)/2)次运算。当P是200 位时,T=2.7×101,如果1us解一次,需要2~3天;如果P 664位,则T=12×1023,约1012天或2.739X109年,约2.7亿 年只要P是够大可以达到足够安年 mfy@ustc.edu.cn 现代密码学理论与实践 7/54
mfy@ustc.edu.cn 现代密码学理论与实践 7/54 如果a是素数p的一个原根(本原元素)，则 a mod p, a2 mod p, ......, ap-1 mod p，生成模p的完全剩余集 {1, 2, ......, p-1} 对于所有素数，其原根必定存在，即 对于一个整数b和素数p的一个原根，可以找到唯一的指数i, 使得 b = a i mod p, 其中 0<= i <= p-1 指数i称为b的以a为基数的模p的离散对数或者指数。 离散对数密码体制的安全性基于DLP问题, 在下式中已知C和P 的情况下, 由d求M很容易, 由M求d很困难, d = logCM in GF(P), 最快的算法需要T=exp((ln(P)lnln(P)1/2)次运算。当P是200 位时, T = 2.7x1011 , 如果1μs解一次, 需要2~3天；如果P = 664位, 则T = 1.2x1023 , 约1012天或2.739x109年, 约2.7亿 年. 只要P足够大,可以达到足够安全
DLP与DHP DLP Given p, a and b, find x such that b=a- mod p DHP g is the generator of Fp, given g mod p and g modp, find gry moa p DLP→DHP DLP=?DHP 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 8/54
mfy@ustc.edu.cn 现代密码学理论与实践 8/54 DLP ◦ Given p, a and b, find x such that b=ax mod p. DHP ◦ g is the generator of Fp , given g x mod p and g y mod p, find g xy mod p. DLP→DHP, DLP=?DHP
9.1.2 Diffie-Hellman Key Exchanges 通信双方约定一个大素数(或多项式)p,和模p的一个素根 各方产生公开密钥 选择一个秘密钥数值),如ⅹA<p,XB<p 计算公钥,如yA= a a mod p,yg= a mod p,并相互交换 双方共享的会话密钥KA可以如下算出 aB mod yA mod p(which B can compute yB mod p(which A can compute KAB是双方用对称密码通信时共享的密钥 〉如果双方继续通信,可以继续使用这个密钥,除非他们 要选择新的密钥 攻击者如果想要获得KAB=a,则必须解决DHP问题 ash mfy@ustc.edu.cn 现代密码学理论与实践 9/54
mfy@ustc.edu.cn 现代密码学理论与实践 9/54 通信双方约定一个大素数(或多项式)p, 和模p的一个素根 α 各方产生公开密钥 ◦ 选择一个秘密钥(数值)，如xA< p， xB< p ◦ 计算公钥, 如yA = α xA mod p, yB = α xB mod p, 并相互交换 双方共享的会话密钥KAB可以如下算出 KAB = α xA·xB mod p = yA xB mod p (which B can compute) = yB xA mod p (which A can compute) KAB是双方用对称密码通信时共享的密钥 如果双方继续通信，可以继续使用这个密钥，除非他们 要选择新的密钥 攻击者如果想要获得KAB = α xA·xB , 则必须解决DHP问题
Key exchange构造条件 条件 单向性 例如:离散对数的单向性 gx modp-\→X 交换性 例如:离散对数的单向性:(g×)y=(gy) X mod p 复用性 私有密钥可复用(量子计算环境下可能不满足 〉椭圆曲线上的离散对数问题也可以构造 Diffie- Hellmen Key Exchange 尝试其他可交换单向函数构造 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 10/54
mfy@ustc.edu.cn 现代密码学理论与实践 10/54 条件 ◦ 单向性 例如：离散对数的单向性 gx modp-\→x ◦ 交换性 例如：离散对数的单向性: (gx) y=(gy ) x mod p ◦ 复用性 私有密钥可复用（量子计算环境下可能不满足） 椭圆曲线上的离散对数问题也可以构造DiffieHellmen Key Exchange 尝试其他可交换单向函数构造…