Alice Bob Dave - Writeup by AI

kang0x0

375人浏览 · 2026-04-23 15:15:56

kang0x0 · 2026-04-23 15:15:56 发布

Alice Bob Dave - Writeup by AI

一、题目信息

题目来源: bugku Crypto
题目名称: Alice Bob Dave
题目类别: RSA 密码分析

二、考点分析

核心知识点

RSA 共享素数攻击：两个 RSA 模数共享同一个素数因子
已知私钥和公钥恢复模数：利用 $\times d - 1 = k \times \phi(n)$ 的关系
GCD 攻击：通过计算最大公约数提取公共因子
大整数分解：从小因子组合中搜索目标素数

权重分布

考点	权重	说明
RSA 共享素数攻击	40%	识别 n_a 和 n_b 共享素数 p
已知 d,e 恢复 n	35%	利用 ed-1 = k*φ(n) 关系
GCD 因子提取	15%	计算 GCD(ed_a-1, ed_b-1)
因子组合搜索	10%	从小因子组合中构造 p-1

三、题目描述

题目代码 (chall.py)

from Crypto.Util.number import *
from secret import msg_a,msg_b

e=65537
p,q,r=[getStrongPrime(1024,e) for _ in range(3)]
pt_a=bytes_to_long(msg_a)
pt_b=bytes_to_long(msg_b)

n_a=p*q
n_b=p*r
phin_a=(p-1)*(q-1)
phin_b=(p-1)*(r-1)
d_a=inverse(e,phin_a)
d_b=inverse(e,phin_b)

ct_a=pow(pt_a,e,n_a)
ct_b=pow(pt_b,e,n_b)

print(f"{ct_a=}\n{ct_b=}\n{d_a=}\n{d_b=}\n{e=}")

输出数据 (out.txt)

ct_a: Alice 的密文
ct_b: Bob 的密文
d_a: Alice 的私钥
d_b: Bob 的私钥
e: 公钥指数 (65537)

四、解题思路

1. 题目分析

观察代码发现关键信息：

n_a = p * q
n_b = p * r

重要特征：Alice 和 Bob 的 RSA 模数共享同一个素数 p！

2. 攻击原理

RSA 基本关系

$\times d - 1 = k \times \phi(n)$
$ϕ(n)=(p−1)(q−1)=n−p−q+1\phi(n) = (p-1)(q-1) = n - p - q + 1$

对于 Alice 和 Bob：

$\times d_a - 1 = k_a \times (p-1) \times (q-1)$
$\times d_b - 1 = k_b \times (p-1) \times (r-1)$

GCD 攻击

$gcd⁡(e×da−1,e×db−1)=(p−1)×gcd⁡(ka(q−1),kb(r−1))\gcd(e \times d_a - 1, e \times d_b - 1) = (p-1) \times \gcd(k_a(q-1), k_b(r-1))$

由于 $q$ 和 $r$ 是不同的素数， $gcd(k_a(q-1), k_b(r-1))$ 应该只包含小因子。

3. 攻击步骤

计算 GCD：求 $gcd⁡(e×da−1,e×db−1)\gcd(e \times d_a - 1, e \times d_b - 1)$
因子分解：提取 GCD 中的小素因子
构造 p-1：通过因子组合找到 $(p - 1)$
恢复 p： $p = (p - 1) + 1$ ，并验证是否为素数
求解 q 和 r：利用 $k_a$ 和 $k_b$ 恢复完整的 $q$ 和 $r$
解密消息：构造 $na=p×qn_a = p \times q$ 和 $nb=p×rn_b = p \times r$ 进行解密

五、详细解题步骤

步骤 1: 计算 GCD

ed_a_minus_1 = e * d_a - 1
ed_b_minus_1 = e * d_b - 1
g = GCD(ed_a_minus_1, ed_b_minus_1)

结果：g 的位数为 310 位（而预期的 $p$ 应该是 1024 位）

步骤 2: 因子分解

def factor_small(n, limit=100000):
    factors = []
    d = 2
    while d <= limit and n > 1:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    return factors, n

small_factors, remaining = factor_small(g)

结果：

小因子：[2, 2, 3, 3, 1543, 36097]
剩余部分：300 位的大数

步骤 3: 因子组合搜索 p-1

from itertools import combinations

for i in range(len(small_factors) + 1):
    for combo in combinations(small_factors, i):
        product = 1
        for f in combo:
            product *= f
        
        candidate = remaining * product + 1
        if 300 <= len(str(candidate)) <= 320:
            if gmpy2.is_prime(candidate):
                p = candidate
                break

成功找到：使用 4 个额外因子 (2, 2, 3, 3) 时找到素数 $p$

$p$ 位数：309 位
验证：gmpy2.is_prime(p) 返回 True

步骤 4: 恢复 q 和 r

p_minus_1 = p - 1

# 找 q
for k_a in range(1, 100000):
    if ed_a_minus_1 % (k_a * p_minus_1) == 0:
        q_minus_1 = ed_a_minus_1 // (k_a * p_minus_1)
        q = q_minus_1 + 1
        if gmpy2.is_prime(q):
            print(f"找到 k_a = {k_a}, q 位数：{len(str(q))}")
            break

# 找 r
for k_b in range(1, 100000):
    if ed_b_minus_1 % (k_b * p_minus_1) == 0:
        r_minus_1 = ed_b_minus_1 // (k_b * p_minus_1)
        r = r_minus_1 + 1
        if gmpy2.is_prime(r):
            print(f"找到 k_b = {k_b}, r 位数：{len(str(r))}")
            break

结果：

$k_a = 28477$ , $q$ 位数：309
$k_b = 37135$ , $r$ 位数：309

步骤 5: 解密消息

n_a = p * q
n_b = p * r

# 解密 Alice 的消息
pt_a_long = pow(ct_a, d_a, n_a)
msg_a = long_to_bytes(pt_a_long)

# 解密 Bob 的消息
pt_b_long = pow(ct_b, d_b, n_b)
msg_b = long_to_bytes(pt_b_long)

解密结果：

Alice: Hey Dave its Alice here.My flag is zh3r0{GCD_c0m3s_
Bob: Hey Dave its Bob here.My flag is 70_R3sCue_3742986}

步骤 6: 合并 Flag

将两部分 flag 拼接：

zh3r0{GCD_c0m3s_70_R3sCue_3742986}

六、完整解题脚本

# CTF Challenge: Alice Bob Dave - RSA Shared Prime Attack 解题脚本
from Crypto.Util.number import long_to_bytes, GCD
import gmpy2
from itertools import combinations
import os
import re

# 自动切换到脚本所在目录
os.chdir(os.path.dirname(os.path.abspath(__file__)))

# 题目给出的数据
ct_a = 1991374644522844726604723395302447678829362766488998002689642863876589167224123634868869407586265887639572846618361378190717796457675877867002990630200549839187693737176043693114429036857443618075597595356236777647214186597416429862630588853297534066191784060030827904725960955181749644590885127762513958644117342351741609981560458367036971039921421548984093411630930209440031060634872093143755813835906517674672118355461511837533783279547447855290393938723966500874359457216314821548439555245649159786182924722770460929014017979622168454175758261065999271764594369618940918533185330319317089809708951104047147411596
ct_b = 11560415492145861207516424108577715664730529386805857287246533744961821151018194362544284902991666685182413092786353089517543091603274250128250910669110530206320138191614471688310529571895441809729559056935543845898702106837033971935287923495445981173899073238286288875669342754013550227359718814123485311705960547980778357375585882146296937739196745327987012437076826111202650212821723168353665944362122152786549834258495316372518691633486765982945106049194892430437710982481105051765183397588927444843790029563399175420351710322220501327577415113508236805750358567711052779340011355629159610689505604941700815518380
d_a = 12007894588345817095001901772235818535532128075248502006167506715501613386280619988757005912270381074208611126718938214462213079931302423653355153363846803336576965899104058007549509604040316897464770127372797630135493394807353800174267249408200186888724103432412296802728616667116382243738519746110159825921676647202689661952040602841752466515868580858475210918168761862255041985423595605698941150797550252491451770611246462256935118062094973933183288422900540413805923476283359196218128607678993284504582128505198491110084905108072190837781925478455984417366202863689318005069821086805269764308054632708127147397685
d_b = 15309121030008789112453654624398278092026139678301334759817236349957760197277968332173160272007689043235997494440248487531238644015060915059836861728115118555482791561589562225055947155368216166612774271639118879220806859714069050410034235487298164832205885978355955618431606156727831992132535894020870312453902803351757466444078059503362362343138846985263572980446344678973847354860739168547872456538618897496981232096868408852088578700314051200160980186449222946973789039336701174360592471866811887750298968395798446811465432587371913161943176018766518394820191044593922558127924048562996714970537749736086175516533
e = 65537

print("[*] CTF Challenge: Alice Bob Dave - RSA 共享素数攻击")
print("="*60)

ed_a_minus_1 = e * d_a - 1
ed_b_minus_1 = e * d_b - 1

g = GCD(ed_a_minus_1, ed_b_minus_1)

def factor_small(n, limit=100000):
    """提取小素因子"""
    factors = []
    d = 2
    while d <= limit and n > 1:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    return factors, n

small_factors, remaining = factor_small(g)

# 搜索 p
p = None
for i in range(len(small_factors) + 1):
    if p:
        break
    for combo in combinations(small_factors, i):
        product = 1
        for f in combo:
            product *= f
        
        candidate = remaining * product + 1
        if len(str(candidate)) >= 300 and len(str(candidate)) <= 320:
            if gmpy2.is_prime(candidate):
                p = candidate
                print(f"[+] 找到共享素数 p (使用 {i} 个额外因子)")
                break

if p is None:
    print("[-] 未找到合适的 p")
    exit(1)

p_minus_1 = p - 1

# 恢复 q 并解密 Alice 的消息
print("\n[*] 恢复 Alice 的密钥...")
for k_a in range(1, 100000):
    if ed_a_minus_1 % (k_a * p_minus_1) == 0:
        q_minus_1 = ed_a_minus_1 // (k_a * p_minus_1)
        q = q_minus_1 + 1
        
        if gmpy2.is_prime(q):
            print(f"[+] 找到 k_a = {k_a}, q 位数：{len(str(q))}")
            n_a = p * q
            
            # 解密
            pt_a_long = pow(ct_a, d_a, n_a)
            msg_a = long_to_bytes(pt_a_long).decode('utf-8', errors='ignore')
            print(f"[+] Alice: {msg_a}")
            break

# 恢复 r 并解密 Bob 的消息
print("\n[*] 恢复 Bob 的密钥...")
for k_b in range(1, 100000):
    if ed_b_minus_1 % (k_b * p_minus_1) == 0:
        r_minus_1 = ed_b_minus_1 // (k_b * p_minus_1)
        r = r_minus_1 + 1
        
        if gmpy2.is_prime(r):
            print(f"[+] 找到 k_b = {k_b}, r 位数：{len(str(r))}")
            n_b = p * r
            
            # 解密
            pt_b_long = pow(ct_b, d_b, n_b)
            msg_b = long_to_bytes(pt_b_long).decode('utf-8')
            print(f"[+] Bob: {msg_b}")
            break

print("\n" + "="*60)
print("[*] Flag 提取")
print("="*60)

# 提取并合并 flag
flag_part_a_match = re.search(r'zh3r0\{.*$', msg_a)
flag_part_b_match = re.search(r'flag is (\S+)$', msg_b)

if flag_part_a_match and flag_part_b_match:
    flag_part_a = flag_part_a_match.group()
    flag_part_b = flag_part_b_match.group(1)
    
    full_flag = flag_part_a + flag_part_b
    print(f"\n[+] 完整 Flag: {full_flag}")
else:
    print("[-] Flag 提取失败")

print("="*60)

七、运行结果

$ python solve.py

[*] CTF Challenge: Alice Bob Dave - RSA 共享素数攻击
============================================================
[+] 找到共享素数 p (使用 4 个额外因子)

[*] 恢复 Alice 的密钥...
[+] 找到 k_a = 28477, q 位数：309
[+] Alice: Hey Dave its Alice here.My flag is zh3r0{GCD_c0m3s_

[*] 恢复 Bob 的密钥...
[+] 找到 k_b = 37135, r 位数：309
[+] Bob: Hey Dave its Bob here.My flag is 70_R3sCue_3742986}

============================================================
[*] Flag 提取
============================================================
[+] 完整 Flag: zh3r0{GCD_c0m3s_70_R3sCue_3742986}
============================================================