具有保密性和真实性的密钥分配 ()Eki [N1 Da (2)Exr,[N1‖N2] Initiator Responder A B (3)Ex7n[N2 (4)EKUBLEKR [K II Schoal as Cauter igure 10.6 Public-Key Distribution of Secret Keys fy@ustc.edu.cn 现代密码学理论与实践 11/59
mfy@ustc.edu.cn 现代密码学理论与实践 11/59
10.2基于离散对数的公钥体制 Dfie和 Hellman在1976年首次提出了公钥算法, 给出了公钥密码学的定义,该算法通常被称为 Dfte- Hellman密钥交换算法 丶 Diffie- Hellman密钥交换算法是一种公钥分发机制 它不是用来加密消息的 所生成的是通信双方共享的会话密钥,必须保密,其 值取决于通信双方的私钥和公钥信息 Diffie- Hellman密钥交换算法是基于有限域GF中 的指数运算的(模一素数或多项式) 丶 Diffie- Hellman密钥交换算法的安全性依赖于求解 DHP问题 fy@ustc.edu.cn 现代密码学理论与实践 12/59
mfy@ustc.edu.cn 现代密码学理论与实践 12/59 Diffie和Hellman在1976年首次提出了公钥算法， 给出了公钥密码学的定义，该算法通常被称为 Diffie-Hellman密钥交换算法 Diffie-Hellman密钥交换算法是一种公钥分发机制 ◦ 它不是用来加密消息的 ◦ 所生成的是通信双方共享的会话密钥，必须保密，其 值取决于通信双方的私钥和公钥信息 Diffie-Hellman密钥交换算法是基于有限域GF中 的指数运算的(模一素数或多项式) Diffie-Hellman密钥交换算法的安全性依赖于求解 DHP问题
10.2.1离散对数问题回顾 如果a是素数p的一个原根(本原元素),则 a mod p,a2modp,……,ap1modp,生成模p的完全 剩余集{1,2,…,.p-1 对于所有素数,其原根必定存在,即 对于一个整数b和素数p的一个原根,可以找到唯一的指数i, 使得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(nP)nnP)1/2)次运算。 当P是200位时,T=2.7×1011,如果1us解一次,需要 2~3天;如果P=664位,则T=1.2×1023,约1012天或 2.739×109年,约2.7亿年.只要P足够大,可以达到足够安 全 fy@ustc.edu.cn 现代密码学理论与实践 13/59
mfy@ustc.edu.cn 现代密码学理论与实践 13/59 如果a是素数p的一个原根(本原元素)，则 a mod p, a2 mod p, ......, ap-1 mod p，生成模p的完全 剩余集{1, 2, ......, p-1} 对于所有素数，其原根必定存在，即 对于一个整数b和素数p的一个原根，可以找到唯一的指数i, 使得 b = ai 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 Fm, given g mod p and gy mod p, find gry mod p DLP→DHP DLP=?DHP ad Cau huten science& technolo fy@ustc.edu.cn 现代密码学理论与实践 14/59
mfy@ustc.edu.cn 现代密码学理论与实践 14/59 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
102 Diffie-HellmanT钥交换协 本协议不能抵抗中间人攻击 User A User B Generate random XA<q: Calculate YA=CA mod q Generate random XB<q: Calculate YB=aB mod q: B Calculate Calculate K=(YA B mod q K=(YBYA mod q Figure 10.8 Diffie-Hellman Key exchange fy@ustc.edu.cn 现代密码学理论与实践 15/59
mfy@ustc.edu.cn 现代密码学理论与实践 15/59 本协议不能抵抗中间人攻击