车不盖为 一种简单的秘密密钥分配方法 15 o Merkle在1979提出一种简单的方法 ● A产生公/私钥对PUa,PRa},将含有PUa和标识IDA的消息 发给B B产生秘密密钥（会话密钥）Ks,并用A的公钥加密后发给A ·A解密D(PRa,E(PUa,Ks),得到Ks,这样双方即可通信 ·这个协议不安全，因为会受到中间人攻击 ()KU。IDA- B -(2)EKU [K:] 2022/10/9 Figure 10.5 Simple Use of Public-Key Encryption to Establish a Session Key 12/59
2022/10/9 现代密码学理论与实践-10 12/59 一种简单的秘密密钥分配方法 ⚫ Merkle在1979提出一种简单的方法 ⚫ A产生公/私钥对{PUa,PRa}, 将含有PUa和标识IDA的消息 发给B ⚫ B产生秘密密钥(会话密钥)Ks, 并用A的公钥加密后发给A ⚫ A解密D(PRa,E(PUa,Ks), 得到Ks, 这样双方即可通信 ⚫ 这个协议不安全，因为会受到中间人攻击
具有保密性和真实性的密钥分配 105 (EKU INIDAl -(2Exu, [N1 I N2] Initiator Responder A B -(3)EKU [N2] (4)EKU [EKR [K ] Figure 10.6 Public-Key Distribution of Secret Keys 道道量道品 2022/10/9 现代密码学理论与实践-10 13/59
2022/10/9 现代密码学理论与实践-10 13/59 具有保密性和真实性的密钥分配
10.2 Diffie-Hellman密钥交换 105 Diffie和Hellman在1976年首次提出了公钥算法，给 出了公钥密码学的定义，该算法通常被称为Diffie Hellman:密钥交换算法 ·Diffie-Hellman密钥交换算法是一种公钥分发机制 。它不是用来加密消息的 所生成的是通信双方共享的会话密钥，必须保密，其 值取决于通信双方的私钥和公钥信息 ● Diffie-Hellman密钥交换算法是基于有限域GF中的 指数运算的（模一素数或多项式） Diffie-Hellman密钥交换算法的安全性依赖于求解离 散对数问题DLP 平四 2022/10/9 现代密码学理论与实践-10 14/59
2022/10/9 现代密码学理论与实践-10 14/59 10.2 Diffie-Hellman密钥交换 ⚫ Diffie和Hellman在1976年首次提出了公钥算法，给 出了公钥密码学的定义，该算法通常被称为DiffieHellman密钥交换算法 ⚫ Diffie-Hellman密钥交换算法是一种公钥分发机制 ⚫ 它不是用来加密消息的 ⚫ 所生成的是通信双方共享的会话密钥，必须保密，其 值取决于通信双方的私钥和公钥信息 ⚫ Diffie-Hellman密钥交换算法是基于有限域GF中的 指数运算的(模一素数或多项式) ⚫ Diffie-Hellman密钥交换算法的安全性依赖于求解离 散对数问题DLP
离散对数问题Discrete Logarithm Problem 。如果a是素数p的一个原根（本原元素），则 a mod p,a2modp,,aP1modp,生成模p的完全剩余集 1,2,,p-1} 对于所有素数，其原根必定存在，即 对于一个整数b和素数p的一个原根a,可以找到唯一的指数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(In(P)Inln(P)12)次运算。当P是200位时，T= 2.7x101,如果1us解一次，需要2~3天；如果P=664位，则T= 1.2x1023,约1012天或2.739x109年，约2.7亿年.只要P足够大，可 以达到足够安全。 nn量当 2022/10/9 现代密码学理论与实践-10 15/59
2022/10/9 现代密码学理论与实践-10 15/59 离散对数问题Discrete Logarithm Problem ⚫ 如果a是素数p的一个原根(本原元素)，则 a mod p, a2 mod p, ......, ap-1 mod p，生成模p的完全剩余集 {1, 2, ......, p-1} 对于所有素数，其原根必定存在，即 对于一个整数b和素数p的一个原根a，可以找到唯一的指数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足够大,可 以达到足够安全
Diffie-Hellman Key Exchange ·通信双方约定一个大素数（或多项式）p,和模p的一个 素根a 各方产生公开密钥 选择一个秘密钥（数值），如x<P,s<p 0 计算公钥，如ya=amod p,yB=a mod p,并相互交换 双方共享的会话密钥KB可以如下算出 KAB a XA.xB mod p mod p (which B can compute) yA =ye mod p (which A can compute) KB是双方用对称密码通信时共享的密钥 如果双方继续通信，可以继续使用这个密钥，除非他 们要选择新的密钥 攻击者如果想要获得X,则必须解决DLP问题 道道西 2022/10/9 现代密码学理论与实践-10 16/59
2022/10/9 现代密码学理论与实践-10 16/59 Diffie-Hellman Key Exchange ⚫ 通信双方约定一个大素数(或多项式)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是双方用对称密码通信时共享的密钥 ⚫ 如果双方继续通信，可以继续使用这个密钥，除非他 们要选择新的密钥 ⚫ 攻击者如果想要获得x, 则必须解决DLP问题