题目名
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)