异或的密件 - Writeup by AI

题目信息

• 来源: BugKu
• 类别: Crypto (RSA)
• 考点: RSA、数论、位运算、逐位恢复攻击

题目分析

给定信息

题目提供了以下代码和数据：

from Crypto.Util.number import *
from secret import flag
p, q, e = getPrime(512), getPrime(512), 65537
n = p * q
print(n)
print(pow(bytes_to_long(flag) , e , n))
print(p^q)

输出数据：

• n: 1024 位 RSA 模数
• c: 加密后的密文
• p ^ q: p 和 q 的异或值（关键泄露）

问题难点

标准的 RSA 加密，但额外泄露了 p ^ q。通常 RSA 的安全性依赖于大整数分解的困难性，但这里泄露了 p 和 q 的异或值，这足以让我们分解 n。

解题思路

方法一：代数方法（效率较低）

利用以下关系：

1. $n=p\times q$
2. $p\oplus q=k$ (已知)
3. $p+q=(p\oplus q)+2(p\wedge q)=k+2t$

通过二次方程判别式搜索，但计算量巨大。

方法二：逐位恢复攻击（本题解法）⭐

核心思想

从最低位到最高位逐位确定 p 和 q 的每一位。

数学原理

对于第 i 位：

• 设 $p_i$ 和 $q_i$ 分别为 p 和 q 的第 i 位
• 已知 $(p\oplus q{)}_i=k_i$，则 $q_i=p_i\oplus k_i$
• 因此对于每一位，只有 2 种可能：$(p_i,q_i)\in \{(0,k_i),(1,1-k_i)\}$

利用乘法的低位性质：
$$n\mathrm{mod}{2}^{i+1}=(p\times q)\mathrm{mod}{2}^{i+1}$$

如果已知 p 和 q 的低 i 位，可以验证第 i 位的哪种选择满足上述等式。

算法步骤

1. 初始化: 候选对列表 candidates = [(0, 0)]
2. 逐位迭代 (i 从 0 到 n.bit_length()-1):
   • 读取 $k_i=(p\oplus q)>>i\&1$
   • 对于每个候选对 $(p_{low},q_{low})$:
     • 尝试 $p_i=0$ 和 $p_i=1$
     • 计算对应的 $q_i=p_i\oplus k_i$
     • 构建新的低位值并验证乘法
     • 保留满足条件的候选对
   • 去重
3. 最终验证: 检查找到的候选对是否满足 $p\times q=n$ 和 $p\oplus q=k$

复杂度分析

• 理论上每增加一位，候选数可能翻倍
• 但实际上由于乘法约束，候选数增长缓慢（通常保持在几百个）
• 总复杂度约为 $O(\text{bits}\times \text{avg\_candidates})$，远优于暴力分解

完整代码

from Crypto.Util.number import *
import gmpy2

# 题目数据
n = 95562862201427823336067582946015664592322094165595564734633544688981046852555011419775655956374062008786746746891813021004709042123448569672651054374497117781385077761604798008040559786965945283482187568723860843102761550095675462113034490834106391146206127719571788775471987423072874061061356320902761206747
c = 58018864342175249049694134001884226579642875631182782878281354592254157977954421579318472108713919321974874420722899431290670929852819379385452970688029168700791027405141925684477493483887731431031816527384418626561771300298831874904373607310738053244602209907791201121366196248860844889191791822466040121521
pxorq = 222698508797767721110391484298656215822060469539734106657369897669776822548641301202460186331633383845935831146767129439812408208215003896191936416553098
e = 65537

def solve_bit_by_bit(n, pxorq):
    """逐位恢复 p 和 q"""
    print("[*] 使用逐位恢复方法求解...")
    
    candidates = [(0, 0)]
    
    for i in range(n.bit_length()):
        new_candidates = []
        pxorq_bit = (pxorq >> i) & 1
        n_low = n & ((1 << (i + 1)) - 1)
        
        for p_low, q_low in candidates:
            for p_bit in [0, 1]:
                q_bit = p_bit ^ pxorq_bit
                
                new_p = p_low | (p_bit << i)
                new_q = q_low | (q_bit << i)
                
                if (new_p * new_q) & ((1 << (i + 1)) - 1) == n_low:
                    new_candidates.append((new_p, new_q))
        
        new_candidates = list(set(new_candidates))
        candidates = new_candidates
        
        if i % 50 == 0:
            print(f"[*] 处理到第 {i} 位，候选数：{len(candidates)}")
    
    # 验证
    for p_low, q_low in candidates:
        if p_low * q_low == n and (p_low ^ q_low) == pxorq:
            return p_low, q_low
    
    return None

# 主程序
p, q = solve_bit_by_bit(n, pxorq)
print(f"[+] p = {p}")
print(f"[+] q = {q}")

# RSA 解密
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
flag = long_to_bytes(m)

print(f"\n[+] Flag: {flag.decode()}")

运行结果

[*] 使用逐位恢复方法求解...
[*] n 的位数：1024
[*] 处理到第 0 位，候选数：1
[*] 处理到第 50 位，候选数：240
...
[*] 处理到第 1000 位，候选数：848
[+] 找到因子！
[*] p = 9887505052686473792161003994931717181923561259381054161766485392846667186932172561131205613433805623242663298666671415728947348813673255436356622476741456377
[*] q = 9665012729926547034857639298119117556730083767461462520975993442411138448829909219957347658311550667318937998931339938018539711143025090110126244259916605811
[+] 验证：p * q = True
[+] 验证：p ^ q = True

[+] Flag: NUAACTF{XXX}