Crossed Wires

发表于 分类于 阅读次数：

Crossed Wires

题目描述

Challenge files:

-source.py

-output.txt

解题思路

  1. 利用已知的私钥(N, d)分解N，得到p和q
  2. 计算欧拉函数φ(N) = (p-1)*(q-1)
  3. 对朋友公钥列表进行反向操作，依次解密
  4. 最终得到原始flag

解题过程

步骤1：分析加密过程

从源代码分析加密流程：

  • 原始flag先被转换为大整数
  • 然后依次使用5个朋友的公钥进行RSA加密
  • 每个朋友使用相同的N但不同的e（17位素数）

步骤2：已知d分解N的算法

使用标准的已知d分解N算法：RSA: how to factorize N given d

1
2
3
4
5
6
1. 设 k=e⋅d−1
2. 随机选择 g∈{2,…,N−1}
3. 将 k 表示为 k=2s⋅t，其中 t 为奇数
4. 计算 x=gtmodN
5. 如果 x!=1 且 gcd(x−1,N)>1，则找到因子
6. 否则继续尝试不同的 g

步骤3：实现解密代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
from Crypto.Util.number import long_to_bytes
import math
from sympy import nextprime, gcd

# 从output.txt读取数据
with open('output.txt', 'r') as f:
    data = f.read()

# 解析数据
my_key = eval(data.split("My private key:")[1].split("My Friend's public keys:")[0].strip())
friend_keys = eval(data.split("My Friend's public keys:")[1].split("Encrypted flag:")[0].strip())
encrypted_flag = int(data.split("Encrypted flag:")[1].strip())

N, d = my_key
e = 0x10001  # 65537

# 已知d分解N的算法
def factorize_N(N, e, d):
    k = e * d - 1
    g = 2
    while True:
        # 将k表示为k = 2^s * t，其中t为奇数
        t = k
        while t % 2 == 0:
            t //= 2
            x = pow(g, t, N)
            y = gcd(x - 1, N)
            if y > 1 and y < N:
                p = y
                q = N // y
                return p, q
        g = nextprime(g)

# 分解N得到p和q
p, q = factorize_N(N, e, d)
print(f"Found factors: p={p}, q={q}")

# 计算欧拉函数
phi = (p - 1) * (q - 1)

# 反向解密（从最后一个朋友开始）
friend_keys.reverse()
current = encrypted_flag
for _, friend_e in friend_keys:
    # 计算朋友的私钥指数
    friend_d = pow(friend_e, -1, phi)
    # 解密
    current = pow(current, friend_d, N)

# 转换为字节
flag = long_to_bytes(current)
print(f"Flag: {flag.decode()}")