2020第五空间智能安全大赛Crypto题解：ROS密码系统从入门到实战

1次阅读

共计 1545 个字符，预计需要花费 4 分钟才能阅读完成。

ROS 密码系统是 2020 年第五空间智能安全大赛中的一道密码学挑战题，属于中等难度的非对称加密分析题目。该题目模拟了一个自定义的 RSA-like 加密系统，要求选手通过分析加密逻辑和参数生成方式，找到漏洞并还原明文。这类题目在 CTF 竞赛中具有典型性，能有效训练选手对非标准加密方案的逆向分析能力。

题目提供的加密脚本主要包含三个部分：

密钥生成：
生成两个大素数 p 和q
计算模数 n = p*q 和欧拉函数φ(n) = (p-1)*(q-1)
选择公钥指数 e 满足 1 < e < φ(n) 且gcd(e, φ(n)) = 1
计算私钥 d 满足e*d ≡ 1 mod φ(n)
加密过程：
对明文 m 计算密文c = m^e mod n
题目特性：
使用自定义的 gen_prime() 函数生成素数
提供 (n, e) 和密文 c 作为题目数据

加密过程基于以下数论原理：

欧拉定理：若 a 与n互质，则a^φ(n) ≡ 1 mod n
解密等式：c^d ≡ (m^e)^d ≡ m^(e*d) ≡ m^(k*φ(n)+1) ≡ m mod n

关键漏洞在于 gen_prime() 的实现：

使用 getPrime(256) 生成 256 位素数p
但 q 的计算方式为q = next_prime(p + random.getrandbits(32))

这种生成方式导致：

p和 q 非常接近（相差约 32 位随机数）
可通过 Fermat 分解法快速分解n

利用以下数学性质：

当 p 和q接近时，存在整数 s 使得p = s - t，q = s + t
则 n = s^2 - t^2，且t 很小
通过枚举 s 从⌈√n⌉开始向下搜索，可快速找到因数

import math
import gmpy2
from Crypto.Util.number import long_to_bytes

# 题目数据
n = 0xabcdef123456... # 替换为实际模数
e = 65537
c = 0xdeadbeef... # 替换为实际密文

def fermat_factor(n):
    """Fermat 因数分解实现"""
    a = gmpy2.isqrt(n) + 1
    b2 = a*a - n
    while not gmpy2.is_square(b2):
        a += 1
        b2 = a*a - n
    b = gmpy2.isqrt(b2)
    return int(a + b), int(a - b)

# 分解模数
p, q = fermat_factor(n)
assert p * q == n

# 计算私钥
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)

# 解密
m = pow(c, d, n)
print(long_to_bytes(m))