題目連結

https://learn.cylabacademy.org/library/715

加密方式

這題是迪菲-赫爾曼密鑰交換 (Diffie-Hellman Key Exchange) 演算法。
加密邏輯如下：\

  1. 建立兩個公開參數，可以被任何人知道。

    • 大質數 $p$
    • 原根 $g$

  2. 產生私鑰與公鑰雙方各自產生自己的私鑰，並計算出對應的公鑰：

    • Alice：
      • 選擇一個私鑰 $a$（隨機整數）。
      • 計算公鑰 $A = g^a \pmod p$。
      • 將 $A$ 傳送給 Bob。
    • Bob：
      • 選擇一個私鑰 $b$（隨機整數）。
      • 計算公鑰 $B = g^b \pmod p$。
      • 將 $B$ 傳送給 Alice。

  3. 計算共享密鑰
    雙方收到對方的公鑰後，利用自己的私鑰計算出相同的共享密鑰 $s$：

    • Alice 計算：$s = B^a \pmod p$
    • Bob 計算：$s = A^b \pmod p$

    $s = B^a \pmod p = A^b \pmod p = g^{ab} \pmod p$

題目解法

這題的重點在於，雖然伺服器的私鑰 $a$ 是未知的，但題目已經直接給了所需的所有關鍵數值：$A$（伺服器公鑰）、$b$（客戶端私鑰）以及 $p$（大質數）。
使用以下 python 腳本可以解密得到 flag。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

# 從 message.txt 複製過來的數值
g = 2
p = 1653798930689987750372209240014380521131540183716217687164747711336243702962818359267822691525697642105558753651223568056089606926425342081267821725904109431430327153613733358950243154522848602494020618427146508586350079988809469424456886589329449769221123659126892760967096413248127035734431548987006011015808526671
A = 771122236020803078829911570090382183223626843114693013412703353349864301811612864849857638111588507084769437566078749825291937213523446695097948166153379036322108656350710200734137906115055446496743841090323252143278700024424965369059879247648625799137192258413471893876530475007392243768366999108564494255853654467
b = 502087552249276796768894199149546386713173741864561762918671131549146319658647813949433247424965048798816294966029262647803764533595143429273283374211302160540685383641060542870573303301014875733971557824236009184578986290165659257363419797500816452080900496604781986251988455903195756181696996025184087945715324970
enc_hex = "cfd6dcd0fcebf9c4dbd7e0cc8cdccd8ccbe0dddb8c87d98c8889c2"

# 1. 計算共享密鑰 (Shared secret)
shared = pow(A, b, p)

# 2. 取得 XOR 的金鑰
key = shared % 256

# 3. 將 hex 轉回 bytes 並進行解密
enc_bytes = bytes.fromhex(enc_hex)
flag = bytes([x ^ key for x in enc_bytes])

print(key)
print(flag.decode())
不過這題的 key 很小，只有 256，所以直接暴力測試所有可能也可以。

題目檔案

message.txt

1
2
3
4
5

g = 2
p = 1653798930689987750372209240014380521131540183716217687164747711336243702962818359267822691525697642105558753651223568056089606926425342081267821725904109431430327153613733358950243154522848602494020618427146508586350079988809469424456886589329449769221123659126892760967096413248127035734431548987006011015808526671
A = 771122236020803078829911570090382183223626843114693013412703353349864301811612864849857638111588507084769437566078749825291937213523446695097948166153379036322108656350710200734137906115055446496743841090323252143278700024424965369059879247648625799137192258413471893876530475007392243768366999108564494255853654467
b = 502087552249276796768894199149546386713173741864561762918671131549146319658647813949433247424965048798816294966029262647803764533595143429273283374211302160540685383641060542870573303301014875733971557824236009184578986290165659257363419797500816452080900496604781986251988455903195756181696996025184087945715324970
enc = cfd6dcd0fcebf9c4dbd7e0cc8cdccd8ccbe0dddb8c87d98c8889c2

encryption.py

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

from Crypto.Util.number import getPrime
from random import randint

# Public parameters
g = 2
p = getPrime(1048)

# Server's secret
a = randint(2, p-2)
A = pow(g, a, p)

# Client secret
b = '???'  

B = pow(g, b, p)

# Shared key
shared = pow(A, b, p)

# Encrypt flag
flag = b"picoCTF{...}"
enc = bytes([x ^ (shared % 256) for x in flag])

# Write challenge info
with open("file.txt", "w") as f:
    f.write(f"g = {g}\n")
    f.write(f"p = {p}\n")
    f.write(f"A = {A}\n")
    f.write(f"b = {b} \n")
    f.write(f"enc = {enc.hex()}\n")