LA CTF 2026 - six seven

题目

分类： Crypto | 作者： AVDestroyer

When bro uses RSA encryption to talk crap behind my back but I lowkey genuinely just factor his public key because I know he picked [67]* as his primes

（当某人用 RSA 加密在背后说我坏话，但我真的直接分解了他的公钥，因为我知道他用 [67]* 作为质数）

nc chall.lac.tf 31180

#!/usr/local/bin/python3
import secrets
from Crypto.Util.number import isPrime, bytes_to_long

def generate_67_prime(length: int) -> int:
    while True:
        digits = [secrets.choice("67") for _ in range(length - 1)]
        digits.append("7")
        test = int("".join(digits))
        if isPrime(test, false_positive_prob=1e-12):
            return test

p = generate_67_prime(256)
q = generate_67_prime(256)
n = p * q
e = 65537

FLAG = open("flag.txt", "rb").read()
m = bytes_to_long(FLAG)
c = pow(m, e, n)

print(f"n={n}")
print(f"c={c}")

解法总结

逐位搜索法：从 n 的低位开始，逐步确定 p 和 q 的每一位，利用乘法低位只取决于因子低位的性质进行剪枝。

过程

01 看题目

拿到题目，看到 chall.py，发现是 RSA，但质数生成很特殊：

def generate_67_prime(length: int) -> int:
    while True:
        digits = [secrets.choice("67") for _ in range(length - 1)]
        digits.append("7")
        test = int("".join(digits))
        if isPrime(test):
            return test

每一位只能是 6 或 7，最后一位固定是 7。这是一个 256 位十进制的质数。

02 初步分析

我的第一反应：只有 6 和 7，本质上就是一个二进制的选择。把 6 看作 0，7 看作 1，那么搜索空间是 2^255（因为最后一位固定）。

2^255 还是太大，不能直接暴力。但这个限制一定弱化了什么...

03 尝试的方向（走了弯路）

方向1：把 p 拆成 6R + B

p = 6×(111...1) + B = 6R + B

其中 R = (10^256 - 1)/9，B 是"二进制系数"的数。

算了 n mod R = BB' mod R，得到了一些信息，但不知道怎么直接利用。

方向2：尝试直接求 φ(n)

展开 φ(n) = (p-1)(q-1)，想找到 S = B + B' 的值，但误差太大，不靠谱。

方向3：格攻击？

想用 Coppersmith 方法，但 B 不够"小"，不满足条件。

04 回到基础：逐位搜索

我之前分析过：乘法的低位只取决于因子的低位。

比如 n 的最后一位 = (p 的最后一位) × (q 的最后一位) mod 10。

既然每位只有 6 或 7 两种选择，可以从低位开始，逐步确定 p 和 q 的每一位。

担心：每一步可能分裂成多个候选，256 步后会不会爆炸？

05 实际尝试

写了个简单的搜索：

def search(n):
    candidates = [(7, 7)]  # 最后一位都是 7
    for k in range(2, 257):
        mod = 10 ** k
        n_low = n % mod
        new_candidates = []
        for p_low, q_low in candidates:
            for p_digit in [6, 7]:
                for q_digit in [6, 7]:
                    new_p = p_digit * (10 ** (k-1)) + p_low
                    new_q = q_digit * (10 ** (k-1)) + q_low
                    if (new_p * new_q) % mod == n_low:
                        new_candidates.append((new_p, new_q))
        candidates = new_candidates
    return candidates

结果：候选数量始终保持在 2-4 个！

k=50: 4 个候选
k=100: 2 个候选
k=150: 2 个候选
k=200: 2 个候选
k=250: 2 个候选
最终: 2 个候选

06 为什么没有指数爆炸？

之前担心每步分裂会导致 2^256 个候选，但实际上：

1. 不是每步都分裂：4 种组合中通常只有 1-2 种满足约束
2. 对称性合并：(p, q) 和 (q, p) 是同一个分解
3. 约束越来越强：mod 10^k 的约束会互相限制

类比解数独：虽然每格有多种可能，但约束会互相限制，最终只有唯一解。

07 拿到 flag

找到 p 和 q 后，标准 RSA 解密：

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
flag = long_to_bytes(m)

lactf{wh4t_67s_15_blud_f4ct0r1ng_15_blud_31nst31n}