[Crypto]maybe_Wiener

题目分析

加密流程

python

from Crypto.Util.number import *

def get_nextprime(n):
    if n < 2: return 2
    n += 1
    if n % 2 == 0:
        n += 1
    while not isPrime(n):
        n += 2
    return n

flag = b'whuctf{???????????????}'
m = bytes_to_long(flag)

mid = getPrime(280) << 744
p = get_nextprime(mid + getPrime(819))
q = get_nextprime(mid + getPrime(819))

n = p * q
d = getPrime(640)

phi = (p - 1) * (q - 1)
e = inverse(d, phi)

c = pow(m, e, n)

print(f'c = {c}')
print(f'e = {e}')
print(f'n = {n}')

'''
n = 17079018232808856067759806896114156006035260880529876703723447659393496283478201040923003333160879323726172516597328180592740445782891248592832973151588182694130186175560504571057050228583199912558095180105547162773821264700567048697544514756031554953114080666328123646020447717075949675481162915086794145966045958528912457586491543973100856504194850697212533276101242655317321400312912530454494436861361594597738601281888659726708408140633053642954347870180416537472211586094132956476514970349225818899404491298095580517329113541701906189838915098526295390186689894462402334584033079700369305245153155714854636740747
e = 8925869711664293536254602790463280743603760308506333949895606365931982218910820552426976256404583292492206546362764711584430317620172342124616467959379575615120554699968276245961341947796097539609348476545129575739108904173024770423677994628015335335992787403958397205188884225599392110494029824568071570836383019857631780702084113807108723220705416286167963132119355463369756779563436048307894171012085117374094657697626086292629116792557083550670652075625174888012628706314609962385870196899561651017020024720067962045007159879342788058332124886006606916982960642980111386769354849304539381622448603860508598998387
c = 4640353323945972405587567333756911962447367346231774125060369865617631840140571335224373411764499376181563371040019628189933647339386564746727914251559717021167190277582537863057377110891810804154231518510379764349164762061682864854987321067834025578639931793733483863144837785008633112246643044094834234641831941199473862132712285063170952456578783023595969472882637161663574813104285665434923026814932593351947088259880944836224237697410438532541941823204304495503816145598398356306083830136080917957371539069236179003305527360968685496469511277872672160542847389344059045667645192804640968565347661098006757847627
'''

关键观察

p 和 q 共享高位：mid = getPrime(280) << 744，p 和 q 的高位 1024 位完全相同
d 较小但不满足标准 Wiener 条件：d = 640 bit，而标准 Wiener 需要 $d < n^{1 / 4} \approx 512 b i t$
p ≈ q： $| p - q | < 2^{820}$ ，p 和 q 非常接近

攻击原理

1. 核心数学关系

RSA 基本公式：

math

e · d ≡ 1 (mod φ(n))  →  e · d - k · φ(n) = 1

变形得到：

math

k/d ≈ e/φ(n)

2. 构造 φ(n) 的近似值

由于 $p \approx q \approx \sqrt{n}$ ：

math

φ(n) = (p-1)(q-1) = n - p - q + 1 ≈ n - 2\sqrt{n} + 1

令：

math

φ_{approx} = n - 2·⌊\sqrt{n}⌋ + 1

3. 误差分析

math


|φ(n) - φ_{approx}| = |(p+q) - 2\sqrt{n}|
                  = |(p+q)² - 4n| / (p+q+2\sqrt{n})
                  = (p-q)² / (p+q+2\sqrt{n})
                  < (p-q)² / (4\sqrt{n})

代入数值：

$| p - q | < 2^{820}$
$\sqrt{n} \approx 2^{1024}$

math

|φ - φ_{approx}| < 2^{1640} / 2^{2050} = 2^{616}

Wiener 攻击条件：

math

|φ - φ_{approx}| < φ(n) / (2·d²)
φ(n) / (2·d²) ≈ 2^{2048} / 2^{1281} = 2^{767}

$2^{616} < 2^{767}$ ✓ 条件满足！

4. 为什么标准 Wiener 不适用？

攻击类型	条件	本题
标准 Wiener	$d < n^{1 / 4} \approx 2^{512}$	$d = 2^{640}$ ❌
扩展 Wiener (p≈q)	$\| φ - φ_{a p p r o x} \| < φ / (2 d ²)$	$2^{616} < 2^{767}$ ✔

解题步骤

第一步：构造 $φ_{a p p r o x}$

python

sqrt_n = gmpy2.isqrt(n)
phi_{approx} = n - 2 * int(sqrt_n) + 1

第二步：连分数展开

对 $e / φ_{a p p r o x}$ 做连分数展开，得到收敛子序列。

python

def continued_fraction_expansion(num, den):
    cf = []
    while den:
        q, r = divmod(num, den)
        cf.append(q)
        num, den = den, r
    return cf

第三步：计算收敛子

python

def get_convergents(cf):
    convs = []
    h_prev, h_curr = 0, 1
    k_prev, k_curr = 1, 0
    for a in cf:
        h_prev, h_curr = h_curr, a * h_curr + h_prev
        k_prev, k_curr = k_curr, a * k_curr + k_prev
        convs.append((h_curr, k_curr))
    return convs

递推公式：

h_{i} = a_{i} \cdot h_{i - 1} + h_{i - 2}

k_{i} = a_{i} \cdot k_{i - 1} + k_{i - 2}

第四步：遍历验证

对每个收敛子 (k, d)：

python

cf = continued_fraction_expansion(e, phi_{approx})
convs = get_convergents(cf)

for k, d in convs:
    if k == 0 or d <= 0:
        continue
    if (e * d - 1) % k != 0:
        continue
    
    phi = (e * d - 1) // k
    s = n - phi + 1
    discriminant = s * s - 4 * n
    if discriminant < 0:
        continue
    
    sqrt_disc = gmpy2.isqrt(discriminant)
    if sqrt_disc * sqrt_disc != discriminant:
        continue
    
    p = (s + int(sqrt_disc)) // 2
    q = (s - int(sqrt_disc)) // 2
    if p * q == n:
        m = pow(c, d, n)
        flag = long_to_bytes(m)
        print(f"flag = {flag}")
        break

完整解题脚本

python

from Crypto.Util.number import *
import gmpy2

n = 17079018232808856067759806896114156006035260880529876703723447659393496283478201040923003333160879323726172516597328180592740445782891248592832973151588182694130186175560504571057050228583199912558095180105547162773821264700567048697544514756031554953114080666328123646020447717075949675481162915086794145966045958528912457586491543973100856504194850697212533276101242655317321400312912530454494436861361594597738601281888659726708408140633053642954347870180416537472211586094132956476514970349225818899404491298095580517329113541701906189838915098526295390186689894462402334584033079700369305245153155714854636740747
e = 8925869711664293536254602790463280743603760308506333949895606365931982218910820552426976256404583292492206546362764711584430317620172342124616467959379575615120554699968276245961341947796097539609348476545129575739108904173024770423677994628015335335992787403958397205188884225599392110494029824568071570836383019857631780702084113807108723220705416286167963132119355463369756779563436048307894171012085117374094657697626086292629116792557083550670652075625174888012628706314609962385870196899561651017020024720067962045007159879342788058332124886006606916982960642980111386769354849304539381622448603860508598998387
c = 4640353323945972405587567333756911962447367346231774125060369865617631840140571335224373411764499376181563371040019628189933647339386564746727914251559717021167190277582537863057377110891810804154231518510379764349164762061682864854987321067834025578639931793733483863144837785008633112246643044094834234641831941199473862132712285063170952456578783023595969472882637161663574813104285665434923026814932593351947088259880944836224237697410438532541941823204304495503816145598398356306083830136080917957371539069236179003305527360968685496469511277872672160542847389344059045667645192804640968565347661098006757847627

sqrt_n = gmpy2.isqrt(n)
phi_{approx} = n - 2 * int(sqrt_n) + 1

def continued_fraction_expansion(num, den):
    cf = []
    while den:
        q, r = divmod(num, den)
        cf.append(q)
        num, den = den, r
    return cf

def get_convergents(cf):
    convs = []
    h_prev, h_curr = 0, 1
    k_prev, k_curr = 1, 0
    for a in cf:
        h_prev, h_curr = h_curr, a * h_curr + h_prev
        k_prev, k_curr = k_curr, a * k_curr + k_prev
        convs.append((h_curr, k_curr))
    return convs

cf = continued_fraction_expansion(e, phi_{approx})
convs = get_convergents(cf)

for k, d in convs:
    if k == 0 or d <= 0:
        continue
    if (e * d - 1) % k != 0:
        continue
    
    phi = (e * d - 1) // k
    s = n - phi + 1
    discriminant = s * s - 4 * n
    if discriminant < 0:
        continue
    
    sqrt_disc = gmpy2.isqrt(discriminant)
    if sqrt_disc * sqrt_disc != discriminant:
        continue
    
    p = (s + int(sqrt_disc)) // 2
    q = (s - int(sqrt_disc)) // 2
    if p * q == n:
        m = pow(c, d, n)
        flag = long_to_bytes(m)
        print(f"d = {d}")
        print(f"flag = {flag}")
        break

总结

本题是扩展 Wiener 攻击的经典案例：

题目设计巧妙：单独看 d 的大小（640 bit）不满足标准 Wiener 攻击条件（需要 < 512 bit），但利用 p≈q 的特殊结构，φ(n) 的近似值误差足够小
核心思想：当 p≈q 时，可以用 $n - 2 \sqrt{n} + 1$ 近似 $φ (n)$ ，使得连分数展开的误差条件得到满足
攻击效果：通过遍历连分数收敛子，成功还原私钥 d 并解密密文

题目名称 "maybe_Wiener" 正是暗示：虽然 d 偏大，但在 p≈q 的辅助条件下，Wiener 攻击依然可行。

[Crypto]maybe_Wiener ​

题目分析 ​

加密流程 ​

关键观察 ​

攻击原理 ​

1. 核心数学关系 ​

2. 构造 φ(n) 的近似值 ​

3. 误差分析 ​

4. 为什么标准 Wiener 不适用？ ​

解题步骤 ​

第一步：构造 φapprox ​

第二步：连分数展开 ​

第三步：计算收敛子 ​

第四步：遍历验证 ​

完整解题脚本 ​

总结 ​

[Crypto]maybe_Wiener

题目分析

加密流程

关键观察

攻击原理

1. 核心数学关系

2. 构造 φ(n) 的近似值

3. 误差分析

4. 为什么标准 Wiener 不适用？

解题步骤

第一步：构造 $φ_{a p p r o x}$

第二步：连分数展开

第三步：计算收敛子

第四步：遍历验证

完整解题脚本

总结