DHKE
2023-7-25
| 2023-7-26
0  |  0 分钟
type
status
date
summary
password
category
slug
icon

🗝️Diffie–Hellman 密钥交换

📑协议:

(1) Alice 选取一个大的随机整数x并且发送给Bob。 (2) Bob 选取一个大的随机整数y并且发送给Alice 。 (3) Alice计算 。 (4) Bob计算 。 k’和k都等于 mod n。即使线路上的窃听者也不可能计算出这个值;他们只知道p、 g、A和B。除非他们计算离散对数,恢复x、y,否则无济于事。因此k是Alice和Bob独立 计算的秘密密钥。
🔑
这是基于求解的离散对数难题的加密,必须使用非常大的A, B 以及p,如果 p 是一个至少 300 位的质数,并且A和B至少有100位长, 那么即使使用全人类所有的计算资源和当今最好的算法也不可能从g, p,A,B中计算出 x,y。g则不需要很大, 并且在一般的实践中通常是2或者5.

安全性

迪菲-赫尔曼密钥交换本身并没有提供通讯双方的身份验证服务,因此它很容易受到中间人攻击。一个中间人在信道的中央进行两次迪菲-赫尔曼密钥交换,一次和Alice另一次和Bob,就能够成功的向Alice假装自己是Bob,反之亦然。而攻击者可以解密(读取和存储)任何一个人的信息并重新加密信息,然后传递给另一个人。因此通常都需要一个能够验证通讯双方身份的机制来防止这类攻击。
 

🦈中间人攻击

(1)Alice发了一份加了密的消息M: E(K2, M)。 (2) Darth截获了该密消息,解密,恢复出M。 (3)Darth将E(K, M)或E(K,, M')发给Bob,其中M'是任意的消息。第一种情况, Darth 只 是简单地偷听通信,而不是改变它。第二种情况,Darth想修改给Bob的消息。
notion image

❗❗模数p

离散对数困难性问题(DLP)

notion image
离散对数难题是指:
当已知一个大质数 p 和它的一个原根 a ,如果给定一个b ,要计算 � 的值是相当困难的。
 

p−1为光滑数

  • 因子越小且越多,discrete_log()越容易得出结果
  • 特殊情况下(循环群的阶(p-1)是光滑数,即可以因子分解成较小的数的乘积),使用Pohlig-Hellman能取得好的效果。有些时候,尽管BSGS能够将复杂度降至,但是这个数依然很大,所以不能用。这时可以考虑Pohlig-hellman方法能不能起作用
 

📑三方协议

假设三方为Alice,Bob, Christian 第一轮: Alice广播, Bob广播, Christian广播 第二轮 Alice广播, Bob广播 , Christian广播 最后协商出来的共有密钥就是 参与者如果是3方以上,最多需要n-1轮就可以完成整体的密钥协商。
 

🤔 总结

离散对数的相关算法有时间还要仔细研究,上次过的有点草率
学会了构造p-1光滑数,要记住喽,不能忘喽
例题DASCTF 2023 & 0X401七月ezDHKE
 

📎 参考文章

 
日常学习
Franklin–Reiter相关消息攻击DASCTF 2023 & 0X401七月复现
目录