CTF BUUOJ [NewStarCTF 公开赛赛道]keyExchange 详细题解 (Diffie-Hellman)

一、题目描述

题目名称：keyExchange
题目分类：Crypto
题目文件：

• keyExchange.py (加密脚本)
• output.txt (输出文件)
  题目提示：我有flag, 你有密钥吗

二、题目分析

首先下载附件，查看加密脚本 keyExchange.py 的逻辑。

from secret import flag, gb, g, p, Diffie_Hellman_KEY_EXCHANGE
from Crypto.Util.number import *
from base64 import b64encode
from Crypto.Cipher import AES
from hashlib import md5
from Crypto.Util.Padding import pad
plaintext = pad(flag, 16)
a = getRandomNBitInteger(1024)
shared = Diffie_Hellman_KEY_EXCHANGE(a) # the original one, not the elliptic curve version!!!!
key = md5(str(shared).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
ciphertext = cipher.encrypt(plaintext)
print(f'师傅给你送了一个flag')
print(f'加密的flag = {b64encode(ciphertext)}')
print(f'p = {p}')
print(f'your secret key {a}')
print(f'g = {g}')
print(f'师傅的公钥 = {gb}')

代码逻辑分析：

1. 密钥生成：脚本生成了一个 1024 位的随机整数 a，这是我们的私钥。
2. 密钥交换：调用了 Diffie_Hellman_KEY_EXCHANGE(a) 函数，注释说明这是原始的 DH 协议，不是椭圆曲线版本。
3. 加密：使用 DH 交换产生的共享密钥 shared，将其转为字符串并计算 MD5 值作为 AES 的密钥，对 flag 进行 ECB 模式加密。
   再来看 output.txt 中的数据：

• p, g：DH 协议的公共参数。
• your secret key a：我们的私钥 $a$。
• 师傅的公钥：对方的公钥 $gb$。
• 加密的flag：待解密的密文。

三、解题思路

这道题的核心考点是 Diffie-Hellman 密钥交换协议 的原理。
在 DH 协议中，双方约定公共参数 $p$（大素数）和 $g$（生成元）。

• 师傅（Server）生成了私钥 $b$，计算公钥 $gb=g^b(\mathrm{mod}p)$。
• 我们生成了私钥 $a$，计算公钥 $ga=g^a(\mathrm{mod}p)$。
  共享密钥的计算方式：
  双方各自使用对方的公钥和自己的私钥计算共享密钥 $S$。
  师傅计算：$S=(ga{)}^b(\mathrm{mod}p)$
  我们计算：$S=(gb{)}^a(\mathrm{mod}p)$
  根据模幂运算性质：
  $S=(g^b{)}^a=g^{ab}=(g^a{)}^b(\mathrm{mod}p)$
  关键点：
  题目已经给出了我们的私钥 $a$ 和师傅的公钥 $gb$。我们不需要去破解离散对数问题求解 $b$，可以直接计算出共享密钥 $S$。
  解密步骤：

1. 利用公式 $S=g{b}^a(\mathrm{mod}p)$ 计算出共享密钥 shared。
2. 模拟脚本中的密钥生成逻辑：key = md5(str(shared).encode()).digest()。
3. 使用 AES 的 ECB 模式解密密文，并去除填充。

四、具体解题脚本

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from hashlib import md5
from base64 import b64decode
# 1. 从 output.txt 中提取数据
p = 133448764119399847876731592238604881175769007976799828874328988761588128500145459082023001027383524831194316266946485380737147372837136403065060245135035225976604193830121124575947440188318348815263642243784574567832213775382081426762862856428888257126982268557543952549848053225651398101391048467656128070913
a = 141940531741414073502483547551457269459744373002985569536254444581939073930343975447649087549033350166772929396986965301002444997704537487577508504709368627174241095027876996113941220579274986994026832534664179333669861059196192190040046004398523932288881838011696679341328520530265002776147308306715042734185
gb = 89434791765835058026108803508194156525355359465406829253856379139334424137549915669535243140614128105195584073112084994777148895681804127886440617684648237403345873311011154293855911891719204975035914932661810961867593769891076834656437254428353814290948181922438812745384577094827728409350756648446941874382
ciphertext_b64 = b'w8OCrexPPqnv2hR+xKeHhXIp0Blp1DYCV4LeZeeLpv5MzUL71raTOeOs4SQBySHH'
# 2. 计算共享密钥
# Diffie-Hellman: shared = (gb)^a mod p
# pow 函数用于大数模幂运算，效率极高
shared = pow(gb, a, p)
# 3. 生成 AES Key
# 注意脚本中的逻辑：先将整数转为字符串，再 encode，再 md5
key = md5(str(shared).encode()).digest()
# 4. AES ECB 解密
ciphertext = b64decode(ciphertext_b64)
cipher = AES.new(key, AES.MODE_ECB)
try:
    decrypted_data = cipher.decrypt(ciphertext)
    # 去除 PKCS7 填充，block_size=16
    flag = unpad(decrypted_data, 16)
    print("="*30)
    print("解密成功!")
    print("Flag:", flag.decode())
    print("="*30)
except Exception as e:
    print(f"解密失败: {e}")

五、运行结果

运行上述脚本，得到 Flag：

==============================
解密成功!
Flag: flag{d1ff1e_h311m4n_is_4_p13c3_0f_c4k3}
==============================

六、总结

这道题主要考察对 Diffie-Hellman 协议原理的理解。很多初学者看到 DH 协议可能会下意识想去爆破私钥或者求解离散对数，但实际上题目已经给出了完整的私钥 $a$，只要理解了 $S=(g^b{)}^a(\mathrm{mod}p)$ 的计算过程，就能直接还原出共享密钥，从而解密 Flag。
这也是 Crypto 题目中比较基础的题型，适合入门学习密钥交换协议。

转载请注明出处！