Aleer
Aleer
发布于 2026-11-19 / 2 阅读
0
0

CRYPTO - ezRSA

题目名 ezRSA 是反讽:第一段是送分的费马分解,第二段则需要一个相当冷门的特殊分解算法 —— Cheng 的 4p-1 椭圆曲线分解法。flag 的后半段 _40r_f3rmat_a0d_CM} 本身就是提示("for format and CM")。

Flag:

PCTF{30ng4atu1ation_40r_f3rmat_a0d_CM}

题目源码

e = 65537
m1 = bytes_to_long(flag[:19])
m2 = bytes_to_long(flag[19:])
​
p1 = getPrime(512)
q1 = next_prime(p1)
n1 = p1 * q1
c1 = pow(m1, e, n1)
​
while True:
    v = getRandomNBitInteger(256) | 1
    p2 = (3 * v**2 + 1) // 4
    if p2.bit_length() == 512 and isPrime(p2) and gcd(e, p2-1) == 1:
        break
​
q2 = getPrime(512)
while gcd(e, q2-1) != 1 or q2 == p2:
    q2 = getPrime(512)
​
n2 = p2 * q2
c2 = pow(m2, e, n2)

分段加密:m1 = flag[:19]、m2 = flag[19:],两段各自独立解密后拼接。


Part 1:费马分解

q1 = next_prime(p1),两素数相差极小,因此 n1 = p1*q1 紧贴完全平方数:

n1 = ((p1+q1)/2)^2 - ((q1-p1)/2)^2

从 a = ceil(sqrt(n1)) 开始递增,检查 a^2 - n1 是否为完全平方即可。迭代约 4000 次得到 p1, q1,解密:

m1 = b'PCTF{30ng4atu1ation'

Part 2:Cheng 4p-1 分解法(D=3)

为什么 Coppersmith 不行(走过的弯路)

p2 = (3v^2+1)/4 且 v 为 256 位,所以 v ≈ 2^256 = n2^0.25。对 f(x) = 3x^2+1 ≡ 0 (mod p2) 做 Coppersmith,由于 p2 完全未知只能用 n2 代替,根界被锁死为

X < n2^(beta^2 / d) = n2^(0.25/2) = n2^0.125 = 2^128

而 v ≈ 2^256,差 2^128 倍 —— 这是硬界,调 epsilon、加大格维数、换 BKZ 都无济于事(Sage 的 small_roots、PARI 的 zncoppersmith 同理)。双变量形式 4n2 = q2(3v^2+1) 的界 XY ≲ W^(2/3) 同样差 2^84 以上。必须换思路。

关键观察:这是 CM 判别式 -3 的特殊素数

4p2 - 1 = 3v^2 即 p2 = (D·v^2+1)/4 中 D = 3。这正是 Cheng(2002)提出的 4p-1 分解法所针对的形式:当 4p-1 = D·b^2 且 D 属于 {-3, -4, -11, -19, -43, -67, -163, ...}(虚二次域的类数较小的 CM 判别式)时,p 可在多项式时间内被分解出来。

Shirase(2017, ePrint 2017/403)给出了 D=3 的极简版本:

  • D=3 时 Hilbert 类多项式 H_3(j) = j,其根为 j0 = 0;

  • j=0 对应曲线 E: y^2 = x^3 + B(即 a=0);

  • 由 CM 理论,若 p = (3v^2+1)/4,则 E 在 F_p 上是 anomalous curve:#E(F_p) = p + 1 - t,其中迹 t = 1,故 #E(F_p) = p。

分解原理

在 E(Z_N) 上随机取点 P,计算 N·P:

N·P = (p·q)·P = q·(p·P)

由拉格朗日定理,p·P = O 在 E(F_p) 上成立(因为群阶恰为 p),所以

N·P ≡ O   (mod p)

用 Jacobian 射影坐标 (X:Y:Z)(x = X/Z^2, y = Y/Z^3)实现标量乘,N·P = O 意味着 Z ≡ 0 (mod p),于是

g = gcd(Z, N) = p        (非平凡因子)

D=3 时单次成功率约 1/6(取决于曲线是 E 还是它的挠曲线),失败就换随机点重试,期望约 6 次。对 1024 位 N 实测 0.2 秒即可分解。

应用

分解得到:

p2 = 8693837416070908356189393575864841441693844843712311099012891753734039423101031130419774879073665601225779926107251766439099393600520091769179997041410019
q2 = 11380620214786454837979000111340996991315097590163175788510093436164440691148716741119602483680013003963315301743268710069560608267258118577135227889735699

验证 4p2-1 = 3v^2(v 为完全平方根),确认形式成立。随后标准 RSA 解密:

d2 = e^-1 mod (p2-1)(q2-1)
m2 = c2^d2 mod n2 = b'_40r_f3rmat_a0d_CM}'

拼接两段即得完整 flag。


完整 EXP

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
ezRSA 完整解法  (PCTF)
=====================================================================
Part 1: q1 = next_prime(p1)  ->  两素数极近  ->  费马分解
Part 2: p2 = (3*v^2+1)/4      ->  4p2-1 = 3v^2, CM 判别式 -3
        ->  Cheng 4p-1 分解法 (D=3): j=0 曲线 E: y^2=x^3+B 在 F_p 上
            anomalous (#E=p), 故 N*P=O mod p, gcd(Z_{N*P}, N)=p2
=====================================================================
依赖: pycryptodome (Crypto.Util.number)
"""
import math
import random
from math import isqrt
from Crypto.Util.number import long_to_bytes
​
e = 65537
​
n1 = 48574622066244676965235410194951656048391858093851188940475070135515179274646260335508645731054941127017455694181589850631448005933690576236509109357906158501005100106426404677648467234352820220149908495893097527494714498231744650953221603274064633531511457004086865188334487164218254500458362660378142943583
c1 = 44352287639488462165424617738514479773688827969802680585178887351317394106539285567053964316546811241789408708004715640089209417889736801591247634202760972532838901086026883693741170006246975299280655319538692988898452930026925094172672932284084394350095400055925861477391946069692240145079202691870481219289
n2 = 98941261841403418592262339751911969375524549896756276640140105958959901510901730725832501964388830266111803793483930043132434255822037239946049186259542374973686881689165179046939235048017397884327825953336466635430354727609091604954283688514828832761379269654169789137858888365761554433253040096188200568281
c2 = 76163449092355468546113624354066065692121574631154372575743562609890072976310941000089625243267080172093680198190555477193899352858436212815181402948223806018139064841880151043619206074951833038284855323529675836457253286593953615350962135867772323983922522831905394556954697834599614525687418750984269968551
​
​
# ---------------------------------------------------------------------
# Part 1 —— 费马分解: n1 = p1 * next_prime(p1)
# ---------------------------------------------------------------------
def fermat_factor(n):
    a = isqrt(n)
    if a * a < n:
        a += 1
    while True:
        b2 = a * a - n
        b = isqrt(b2)
        if b * b == b2:
            return a - b, a + b
        a += 1
​
​
# ---------------------------------------------------------------------
# Part 2 —— Cheng 4p-1 分解法 (D=3)
#
# E: y^2 = x^3 + B  (a=0, j-invariant = 0, 对应 CM 判别式 -3)
# 若 p = (3v^2+1)/4, 则 4p-1 = 3v^2 => E/F_p 是 anomalous: #E(F_p)=p
# 于是 p*P = O mod p。对 N=pq 计算 N*P:
#   N*P = q*(p*P) = O  (mod p)  =>  射影 Z 坐标 ≡ 0 (mod p)
#   =>  gcd(Z, N) = p
# ---------------------------------------------------------------------
def jacobi_double(P, N):
    """Jacobian 倍点, a=0 曲线"""
    X, Y, Z = P
    if Z == 0 or Y == 0:
        return (0, 1, 0)
    YY = Y * Y % N
    S = 4 * X * YY % N
    M = 3 * X * X % N              # a = 0
    X3 = (M * M - 2 * S) % N
    Y3 = (M * (S - X3) - 8 * YY * YY) % N
    Z3 = 2 * Y * Z % N
    return (X3, Y3, Z3)
​
​
def jacobi_add(P, Q, N):
    """Jacobian 点加, a=0 曲线"""
    X1, Y1, Z1 = P
    X2, Y2, Z2 = Q
    if Z1 == 0:
        return Q
    if Z2 == 0:
        return P
    Z1Z1 = Z1 * Z1 % N
    Z2Z2 = Z2 * Z2 % N
    U1 = X1 * Z2Z2 % N
    U2 = X2 * Z1Z1 % N
    S1 = Y1 * Z2 * Z2Z2 % N
    S2 = Y2 * Z1 * Z1Z1 % N
    if U1 == U2:
        return jacobi_double(P, N) if S1 == S2 else (0, 1, 0)
    H = (U2 - U1) % N
    I = (2 * H) ** 2 % N
    J = H * I % N
    r = 2 * (S2 - S1) % N
    V = U1 * I % N
    X3 = (r * r - J - 2 * V) % N
    Y3 = (r * (V - X3) - 2 * S1 * J) % N
    Z3 = ((Z1 + Z2) ** 2 - Z1Z1 - Z2Z2) * H % N
    return (X3, Y3, Z3)
​
​
def scalar_mul(k, P, N):
    """Jacobian 标量乘, 返回 (X,Y,Z)"""
    R = (0, 1, 0)
    Q = P
    while k > 0:
        if k & 1:
            R = jacobi_add(R, Q, N)
        Q = jacobi_double(Q, N)
        k >>= 1
    return R
​
​
def cheng_factor_d3(N, max_tries=1000):
    """D=3 Cheng 分解; 单次成功率约 1/6, 重试即可"""
    for _ in range(max_tries):
        x0 = random.randrange(1, N)
        y0 = random.randrange(1, N)
        P = (x0, y0, 1)                  # B = y0^2 - x0^3 隐含确定
        X, Y, Z = scalar_mul(N, P, N)
        g = math.gcd(Z, N)
        if 1 < g < N:
            return g
    return None
​
​
def main():
    # ---- Part 1 ----
    p1, q1 = fermat_factor(n1)
    assert p1 * q1 == n1
    d1 = pow(e, -1, (p1 - 1) * (q1 - 1))
    part1 = long_to_bytes(pow(c1, d1, n1))
​
    # ---- Part 2 ----
    p2 = cheng_factor_d3(n2)
    assert p2 and 1 < p2 < n2 and n2 % p2 == 0
    q2 = n2 // p2
    # 校验 p2 的特殊形式 4p-1 = 3v^2
    assert (4 * p2 - 1) % 3 == 0
    assert isqrt((4 * p2 - 1) // 3) ** 2 == (4 * p2 - 1) // 3
    d2 = pow(e, -1, (p2 - 1) * (q2 - 1))
    part2 = long_to_bytes(pow(c2, d2, n2))
​
    flag = (part1 + part2).decode()
    print("flag =", flag)
    return flag
​
​
if __name__ == "__main__":
    random.seed(2026)   # 固定随机种子, 保证结果可复现
    main()

运行输出:

flag = PCTF{30ng4atu1ation_40r_f3rmat_a0d_CM}

参考

  • Qi Cheng, A New Class of Unsafe Primes (2002), ePrint 2002/109

  • Qi Cheng, A New Special-Purpose Factorization Algorithm (2002)

  • K. Shirase, Condition on composite numbers easily factored with elliptic curve method (2017), ePrint 2017/403 —— 本文使用的 D=3 简化算法(Algorithm 1)


评论