【Crypto-CTF】Diffie-Hellman(DH)密钥交换

本文主要内容：简要介绍Diffie-Hellman密钥交换基本原理，所存在的中间人攻击，以及UCTF2021比赛中关于DH的Small p Problems暴力破解题

简要介绍

Diffie-Hellman密钥交换是一种在公共通道上安全交换加密密钥的方法，该公共通道相较传统意义两方加密通信需先通过物理安全通道有较大不同，也即此通道运行通过不安全通道共同建立共享密钥。

DH可广泛应用于保护各种Internet服务，比如DH-RSA算法组合应用于TLS协议中。

基本原理

采用wiki上一张图形象解释：

• step1：Alice和Bob共同选择公开的颜色(图中黄色)
• step2：Alice和Bob各自选择自己的秘密颜色（黄色：蓝绿色）
• step3：Alice和Bob各自将公开颜色和自己秘密颜色混合形成各自即将交换的颜色（橙色棕褐色：浅蓝色）
• step4：最后，Alice和Bob再将从对方收到颜色和自己秘密颜色混合，得到最终配色（黄棕色），此配色也即共享的密钥

如果第三方监听到，交换信息，由于不知道各自的秘密颜色，无法获取共享密钥

密码学解释

选择素数p及其本原根g，是为了确保共享密钥在1到p-1之间

安全性

DH密钥交换的安全性建立在以下事实：

• 计算素数模幂相对容易（$g^a mod p$称为模幂）
• 对于大素数p，求其离散对数被认为是困难的

当p为600位以上的质数时，不知私钥a和b时是很难解出a的。

中间人攻击

由于DH密钥交换本身不提供通信方的身份验证，因此容易受到中间人攻击。

也即中间人分别和Alice和Bob构建共享密钥K1和K2

• 中间人可以查看消息并转发两者消息
• 中间人可以修改消息转发给另一人

更多信息可参考：https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

UCTF2021-Small p Problems

示例通过一道CTF题，来反映在DH密钥交换中，p选择素数较小，使用暴力破解便可获取共享密钥的过程

题目

My buddies Whitfield and Martin were trying to share a secret key between themselves, and I was able to eavesdrop on their conversation. I bet I could probably figure out their shared secret with a little math…

p = 69691
g = 1001

A = 17016
B = 47643

Note: submit either the shared secret or the shared secret wrapped in utflag{}

题解

根据题目，无法得知各自私钥

1
2
3
4
5
6
7
8
9

p=69691
g=1001
A=17016
B=47643
# 暴力破解a或者b ,范围从1-p-1
for i in range(1,p):
    if pow(g,i,p)==A: # 若满足g^i mod p = A，则说明i为A的私钥a
        print("a:",i,"\nK:",pow(B,i,p))
        break

a: 12552 
K: 53919

1
2
3
4
5
6
7
8
9

p=69691
g=1001
A=17016
B=47643
# 暴力破解a或者b ,范围从1-p-1
for i in range(1,p):
    if pow(g,i,p)==B: # 若满足g^i mod p = B，则说明i为B的私钥b
        print("b:",i,"\nK:",pow(A,i,p))
        break

b: 7919 
K: 53919

所以，当p选取较小时，可以使用暴力破解方式得当各自私钥