THEMCTF_wp

Age_old_problem Writeup

import secrets
from math import gcd
from Crypto.Util.number import isPrime, bytes_to_long


def egcd(a, b):
    old_r, r = a, b
    old_x, x = 1, 0
    old_y, y = 0, 1

    while r != 0:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_x, x = x, old_x - q * x
        old_y, y = y, old_y - q * y

    return old_r, old_x, old_y


def find_c2_d2(c1: int, d1: int):
    """
    Find integers (c2, d2) such that c1*c2 - d1*d2 == 1.
    """
    if gcd(c1, d1) != 1:
        raise ValueError

    g, x, y = egcd(c1, d1)
    assert g == 1

    c2 = x
    d2 = -y

    assert c1 * c2 - d1 * d2 == 1
    return c2, d2


# https://math.stackexchange.com/questions/4653735/given-an-integer-n-how-to-locate-divisors-p-q-such-that-pq-bmod-pq
BITS = 1024

while True:
    c1 = secrets.randbits(BITS) | (1 << (BITS - 1))
    d1 = secrets.randbits(BITS) | (1 << (BITS - 1))

    if gcd(c1, d1) != 1:
        continue

    try:
        c2, d2 = find_c2_d2(c1, d1)
    except ValueError:
        continue

    k = c1 * d2 + c2 * d1
    a = c1 * c1 + d1 * d1
    b = c2 * c2 + d2 * d2

    p = a + k
    q = b + k

    if p <= 0 or q <= 0:
        continue

    if p % 4 != 3 or q % 4 != 3:
        continue

    if not isPrime(p) or not isPrime(q):
        continue

    N = p * q

    e = (1 - (k * b % a)) % a

    phi = (p - 1) * (q - 1)

    if gcd(e, phi) != 1:
        continue

    assert N % (p + q) == 1

    flag = bytes_to_long(open("flag.txt", "rb").read())
    assert flag < N

    ct = pow(flag, e, N)
    print("N =", N)
    print("e =", e)
    print("ct =", ct)
    break

题目概述

题目给了一个带特殊结构的 RSA 构造。脚本先选出 $c_1, d_1$，再找 $c_2, d_2$ 使得：

\[c_1c_2 - d_1d_2 = 1\]

然后定义：

\[a = c_1^2 + d_1^2\] \[b = c_2^2 + d_2^2\] \[k = c_1d_2 + c_2d_1\] \[p = a + k\] \[q = b + k\] \[N = pq\] \[e = \bigl(1 - (kb \bmod a)\bigr) \bmod a\]

最后输出 $N$、$e$ 和 $ct$。

目标是利用这组数之间的额外关系，把 $p$ 和 $q$ 从 $N$ 里拆出来，再按普通 RSA 的方式解密。

证明：$p^2 + 1 \mid (N+e)(N-1)$

有恒等式：

\[(c_1^2 + d_1^2)(c_2^2 + d_2^2) = (c_1c_2 - d_1d_2)^2 + (c_1d_2 + c_2d_1)^2\]

代入

\[c_1c_2 - d_1d_2 = 1\]

以及

\[c_1d_2 + c_2d_1 = k\]

得到：

\[ab = 1 + k^2\]

展开 $N$：

\[N = pq = (a+k)(b+k) = ab + k(a+b) + k^2\]

代入 $ab = k^2 + 1$：

\[N = (k^2 + 1) + k(a+b) + k^2 = 1 + k(a+b+2k)\]

而：

\[p+q = (a+k) + (b+k) = a+b+2k\]

所以：

\[N - 1 = k(p+q)\]

于是立刻得到：

\[p+q \mid (N-1)\]

因为：

\[e = \bigl(1 - (kb \bmod a)\bigr) \bmod a\]

所以模 $a$ 下：

\[e \equiv 1-kb \pmod a\]

再看 $N$：

\[N = (a+k)(b+k) = ab + ak + bk + k^2\]

模 $a$ 下：

\[N \equiv bk + k^2 \pmod a\]

又因为 $ab = k^2 + 1$，模 $a$ 得到：

\[k^2 \equiv -1 \pmod a\]

因此：

\[N \equiv bk - 1 \pmod a\]

与前面的 $e \equiv 1-kb \pmod a$ 相加：

\[N + e \equiv 0 \pmod a\]

所以：

\[a \mid (N+e)\]

先算：

\[a(p+q) = a(a+b+2k) = a^2 + ab + 2ak\]

代入 $ab = k^2 + 1$：

\[a(p+q) = a^2 + 2ak + k^2 + 1 = (a+k)^2 + 1 = p^2 + 1\]

而我们已经知道：

\[a \mid (N+e)\]

以及

\[p+q \mid (N-1)\]

所以：

\[p^2 + 1 = a(p+q) \mid (N+e)(N-1)\]

记：

\[M = (N+e)(N-1)\]

那么就有：

\[p^2 + 1 \mid M\]

这是本题的关键。

攻击思路

现在已知：

• $N = pq$
• 存在一个素因子 $p$，满足 $p^2 + 1$ 整除已知整数 $M$

这很像Pollard $p-1$：

[!note]

1. 我们的目的是分解出整数$n$的因子

2. 如果我们可以找到一个与$n$不互质的整数$s$，则可直接通过求$\gcd(s,n)$求得$n$的一个因子

3. 我们的思路转化成如何求这样的$s$

4. 假设$p$为$n$的一个未知的素数，单独的$p$是难以求出的，我们可以构造出含有因子$p$的数$s$，从而得到$\gcd(s,n)$，即得到$n$的因子

5. 如何求这种$s$?

6. 我们构造$x$，$x$满足$x \equiv 1 \pmod{p}$，那么就有$\gcd(x-1,n)$为$n$的因子

7. 那如何得到这样的$x$?

8. 转化Fermat小定理，则有$2^{p-1} \equiv 1 \pmod{p}$，对比$x \equiv 1 \pmod{p}$，显然只要求出$p-1$，就能得到$x$的值，但$p$未知!!!，但我们可以构造$(p-1)$的倍数，进而达到相同的效果

9. 如何构造$(p-1)$的倍数?

10. 其实$(p-1)$的B-powersmooth数(设为B)的阶乘就是$(p-1)$的倍数

11. 所以，我们只需要找到一个合适大小的$B$，就可以在多项式时间计算出结果

12. 找到$B$后，回溯:

\[x \equiv 2^{B!} \pmod{p}\] \[s = x - 1\] \[d = \gcd(s,n)\]

此时，求出的$d$即为整数$n$的一个因数

只不过，此时p-1变成了$p^2 + 1$ 。而且我们已知了它的倍数，但我们不能再用费马小定理来说明。

如果存在一个模p下的有限群$H_p$，它的阶为$p^2 + 1$ ，那么就可以取群中的元素x来完成类似的过程。

因为 $ p^2 + 1 \mid M $ ,由阶的定义:

\[x^{p^2 + 1}=x^M=1 \ \ mod \ \ p\]

所以$p\mid x^M-1$ ，取$gcd(x^M-1,N)$，很大概率就可以获得p（若还是N，则取其它元素）

群的构造方法

考虑有限域$\mathbb F_{q}$，对它做一次二次扩张，得到：

\[\mathbb F_{q^2}/\mathbb F_{q}\]

其中的元素为：

\[a+bi \ \ mod \ \ q\]

我们可以在其中找到一个阶为$q + 1$ 的子群。

此时我们令$q=p^2$ ，即

\[\mathbb F_{p^4}/\mathbb F_{p^2}\]

其中的元素为：

\[c_0+c_1 i+c_2 u+c_3 iu \ \ mod \ \ p\]

我们可以在其中找到一个阶为$p^{2} + 1$的子群：

\[H_p=\{x\in \mathbb F_{p^4}^\times : N_{\mathbb F_{p^4}/\mathbb F_{p^2}}(x)=1\}\]

即所有范数为1的元素。

证明：该域中所有范数为1的元素构成一个子群，且阶为$p^{2} + 1$

先证明：范数是乘法同态。

在这里，模 $p$ 后我们把元素写成

\[x=A+Bu\]

其中 $A,B \in \mathbb F_{p^2}$，并且 $u^2=D$。

定义共轭：

\[\overline{x}=A-Bu\]

于是范数就是

\[N(x)=x\overline{x}=A^2-DB^2.\]

显然，范数满足乘法同态：

\[N(xy)=N(x)N(y).\]

这就说明 $N:\mathbb F_{p^4}^\times \to \mathbb F_{p^2}^\times$ 是一个群同态。

而“范数为 $1$”的集合就是这个同态的核：

\[\ker N=\{x\in \mathbb F_{p^4}^\times : N(x)=1\}.\]

任何群同态的核都是子群，所以它们构成了一个子群。

下面证明，这个子群的阶为$p^{2} + 1$

第 1 步，$\mathbb F_{p^4}^\times$ 的大小是

\[p^4-1.\]

而且这是一个循环群。 所以可以设 \(\mathbb F_{p^4}^\times=\langle g\rangle\) 其中 $g$ 是一个生成元，任意非零元素都能写成 $g^k$。

第 2 步，在二次扩张 $\mathbb F_{p^4}/\mathbb F_{p^2}$ 里，范数满足

\[N(x)=x^{p^{2}+1}.\]

所以“范数为 1”就等价于

\[x^{p^{2}+1}=1.\]

第 3 步，现在看这个方程有多少解。

因为每个 $x$ 都是 $g^k$，所以

\[x^{p^{2}+1}=1 \iff (g^k)^{p^{2}+1}=1 \iff g^{k(p^{2}+1)}=1.\]

而 $g$ 的阶是 $p^4-1$，所以

\[g^{k(p^{2}+1)}=1 \iff p^4-1 \mid k(p^2+1).\]

又因为

\[p^4-1=(p^2-1)(p^2+1),\]

所以上式等价于

\[(p^2-1)(p^2+1)\mid k(p^2+1) \iff p^2-1\mid k.\]

所以 $k$ 只能取

\[0,\ p^2-1,\ 2(p^2-1),\ \dots,\ p^2(p^2-1),\]

一共正好有$p^2+1$个不同的值。

因此 \(|H|=p^2+1.\)

这样，我们就成功构造出来我们所需要的群。

寻找范数为 1 的元素

我们希望在扩张群中构造一个 $N(x)=1$ 的元素，因为这类元素会落在一个阶为 $p^2 + 1$ 的子群里。

由于我们不已知p，所以以下构造要在 $modN$ 下进行（而不是模p）。实际上，这是无妨的，因为 $p\mid N$ ，所以模N就可以等同于在模p的扩张域中。

取定参数t，可构造

\[A = \frac{1 + Dt^2}{1 - Dt^2}\] \[B = \frac{2t}{1 - Dt^2}\]

这样自动满足：

\[A^2 - DB^2 = 1\]

于是 $x = A + Bu$ 就是一个范数为 1 的元素。

如果分母$1 - Dt^2$在模 $N$ 下不可逆，因为它在第一次扩张域中，所以实际上是一个模 $N$ 下的高斯整数，将其高斯范数与N取gcd，即可得到一个非平凡因子。

应用攻击

根据：

\[x^M-1=0 \ \ mod \ \ p\]

此处的0表示扩张群中的零元，它的各个系数都为0

这意味着$x^M - 1$的各个系数会被 $p$ 整除，但不一定被 $q$ 整除。

因此只要对这些系数和 $N$ 做 $\gcd$，就有大概率获得 $p$ 。

若还是无法获得p，则需要更改选择的参数t，再尝试进行攻击。

脚本实现

代码里主要分成几部分：

• add_k / sub_k / mul_k / inv_k
  • 实现 $\mathbb{Z}_N[i]$ 上的加减乘和求逆
• mul_e / pow_e
  • 实现二次扩张后的乘法和快速幂
• make_norm_one_element
  • 用参数化公式构造范数为 1 的元素
• find_factor
  • 计算 $x^M$，再从系数里通过 $\gcd$ 恢复非平凡因子
• main
  • 拿到 $p$ 之后做标准 RSA 解密

N = 34007909043204233918511768521538548640285113354644978970227842472071783327980770650344910842031696247113164340895982895921775190800750687595604406131563895328340419892955072541196423362735521701392194795367450002156859810520929690614909186257217295877569308349418285032169254539890668486093966343334727341171985645615723175481152632353310053208459506969872725616299625670764039872100996984589329317350182665820960307320725045646264853645968155641232848882991046338159606331658372509409551981437656693672400195900161972834459887094052252944654824842115844692594890951349445570674272838564631364760220344894454122092808410132449720206758180131907748661255548596141260616868638285280516474578786220140360379726359308730141642530858605625239330441593296751127501168895266430714251594703089664716651449407696210995460573432810819641659224126581224207018630520062880947623360612853082887510113067348221125643148803412393220878411829241732556524326555338166271520558742869074004542041744321985282996166654721906390225037529471567150106687146878879727991085851471303118974225902282657310609298008763127886024650505342003963939543526921545276101221128963096517416460985327997822671336609971156490638232886769428822081992463171876351198979853813
E = 23769490659765781899005362128333910972748921860490268458893548037939778104016414055198744583446288543890809334872733911741066870124526246267853563374772166824089169462494748701782866069375550803993393120857287358277133373065775232586025965152721615300954292880674848818587901677259557638397577889931186539869547329557161618468886383729331743762711083759404613256719518934124896061803824159865146083958451682864620606027078591606427378477513789994383444511884103192190119425002830130517372268007300233714337778347250218615165885749771199068661566928570012006729933373924510026941131862129890777251817089772850743681121
CT = 10738167780675740593371494499189650951358912962083774030000759997889927990421251508537922441418320188945665071476006440443850331894820058940276157170792449393459032412392813046255440354268517193666871306897712608348034294117201914677262050270051159448409837270111749243168720411737745047017472390054544357289458263435692505661189754822033960380791832656405510134426146870024786085325636861041235879736607542145843918133224697743962024156317318598645323696041367509761224596243272360752375715143639630195525337436750374205241117606754080527452624345458927674231484748557715333220754058263198738723490397122481297520370094885927214943517758397155472273828415824111145502841210638910116530032646032639027320419963296222486552172494137630303269942584814220221142409388099118802527863728368086965148733893300447988840323697573064480563432074537352046447198513165552842806378853643390956671566832487208612320395867368057529580529373029498764971198282980001970119387375575253313385649781462066134989201857308948489004840187718986841395736953175236054115104374630933495461934285073389423346711731293663994730394243486574282489706197327005765025710669873399277346559112958134611982950044604254943100402020382691422873102242283486207733426012862


def add_k(x, y, mod):
    return ((x[0] + y[0]) % mod, (x[1] + y[1]) % mod)


def sub_k(x, y, mod):
    return ((x[0] - y[0]) % mod, (x[1] - y[1]) % mod)


def mul_k(x, y, mod):
    return ((x[0] * y[0] - x[1] * y[1]) % mod, (x[0] * y[1] + x[1] * y[0]) % mod)


def scale_k(c, x, mod):
    return ((c * x[0]) % mod, (c * x[1]) % mod)


def inv_k(x, mod):
    norm = (x[0] * x[0] + x[1] * x[1]) % mod
    g = __import__("math").gcd(norm, mod)
    if 1 < g < mod:
        return None, g
    inv = pow(norm, -1, mod)
    return ((x[0] * inv) % mod, (-x[1] * inv) % mod), 1


def mul_e(x, y, d, mod):
    a, b = x
    c, e = y
    return (
        add_k(mul_k(a, c, mod), mul_k(mul_k(b, e, mod), d, mod), mod),
        add_k(mul_k(a, e, mod), mul_k(b, c, mod), mod),
    )


def pow_e(base, exp, d, mod):
    acc = ((1, 0), (0, 0))
    while exp:
        if exp & 1:
            acc = mul_e(acc, base, d, mod)
        base = mul_e(base, base, d, mod)
        exp >>= 1
    return acc


def make_norm_one_element(t, d, mod):
    t2 = mul_k(t, t, mod)
    dt2 = mul_k(d, t2, mod)
    den = sub_k((1, 0), dt2, mod)
    inv_den, factor = inv_k(den, mod)
    if inv_den is None:
        return None, factor
    a = mul_k(add_k((1, 0), dt2, mod), inv_den, mod)
    b = mul_k(scale_k(2, t, mod), inv_den, mod)
    return (a, b), 1


def find_factor(n, e):
    m = (n + e) * (n - 1)

    seeds = [
        (
            (
                32669732129632763880838672288784534681637714151315452540700927184620088709293007265605995476401056127986959864080247909431082411294086443697408587591515103796222545516295153937954870689721607102428006175653671872478406300207670620008243833090799752771207833011006398174242051203118945770936778043975392573338789820093415310390616915330975786261343844130861956389428121588220785486165051636348963751862057781525534011539469894671861314738117786546599882245452575951533849215284538944587366240063917981693981916628640543064290015551825090070634939891306205989624123424506043546137246575461897845495335857898757381241876740827803909984192576539636402772121456065382935336921346601606763325084371772679456820516309148561659644846176611521504677247406115218014905868771314332006414406343245825543085381783501653976296384759506728817382000452736542225429673387811161687464199293002359323194201040702227426696112915418103209088421921468929033034500754387524287656242914947989236025234157099413897331989649216065081671622752074956296360775550726978222600653887641341828593394284983667435605663791842614248595532851046411371542965054954967483354569066741111406215867773220954383931373750084850091347054286895608546267293968532214502792501580983,
                1745750517652499458931854392380619927440259439336119600198360105358956816568002655497116990598688599693866412811004102453691893164258042663110188352173661030808090593499951211667027011121049004010172211629710596379134003159193567496887097712071771082232144317479406764715450189384343542049773770728798245914871014326525925347443712840365804565338978470493905235373322639139972809951095191270658302622105259145423394894368006558900582210414333496508902732419485634384036896978820413799862542498732233271741878207368742780800277554252134031498978023987612647821105944726432507852588467466731044541499565677479326075541485908799874493473873567973363637063123754540983614438314445291323900256811429098447862647532304876827748887381505633887822366874465556404403601792466784638268285988189797987816834270536629261109606580584896187233165080075741386115019161809418571526242704335767135549210537478516634504159806646771549722131507702378059842001881294427759621420076924689196326185924366662656975535581427397550776391820014544160482313615424727338609145030372242547823814804591438433140658951971482090948453395213462079325699415117326025461593133716657113252510308748122134312592713678015027433467667755821653793956880061371497204645898023,
            ),
            (
                16850509885818043270484487478150993463581602076573306448805827816079925361112420913946155642503813502832466104657577242147650512797383735134315259994315689743025260629347670568303238056576030425594318725501160263545960830860665976600346962638674010937458591000471470693522102522476845119388553580997336104494443836493907966938730369683726948758136922319297325193415909120742039211084373108042339708658853095210122892837134292753207713671391017926670155144600283653238047182946929549825201188587319508275755519185449671074595780151839260467533314310311507492132266691181639820113564623027930095547097170823347114120893482335523526316025175988467187601983669198822492510064616564138265481853139303420092525454645651184174547172829709338161348459014133764246813708284862575322503468986718650480320286232440669452934762842237360528483491591808318986399135822498938020852969695043504662554267215702806735903019798465046635514785792453572287310885954167689155219047929592219075387243930391711183250363133130008349416693528559283986141569183796884707735268636167709879236739623589501731314306764983471807697970289162487366893262699296046220461991327585170864194976415931538006552958676793514184939885556375526810815672634412582202217554563369,
                4324374553471497170217694731736869642320502110215476110117777341226316573904310212465690509069466623196494502668493125384403705431338201340393580692498868583595276103587194119678844398213289401665532543896420581336984270949237159970943772045944128942740778213557752495232241899513064647899064198541328685198001192830626996929968788612606749008613273853824638644911060707754018019957778157866109612378152039672215115342476354966023319305093339577845300534713814457827304322088408389647266698915653624194231243134087872507664437950438625972452275871392578799056253285065828695132763725328847174818531440695406754187449089847613907229398683399410617795059760103203222358114890314718585028880329944108338117681866015961870112778926825574936459747398410836041915358274701138091546002274596023267143001623461790744769662438095625685921311699028595050483248904117664199234129101026741315844467848942807396829125739661581504900026441251741656835899937139617434486052111731388514416556390071638828815226696537471479415071218436838778278130849582689601219279173225519284928451946500791007486244478505665516140655125593721238999637317020117201497305528128284259274129310890336712302871006626261642649667952668982212131811003865179536091802385817,
            ),
        )
    ]

    for d, t in seeds:
        element, factor = make_norm_one_element(t, d, n)
        if element is None:
            if 1 < factor < n:
                return factor
            continue
        powered = pow_e(element, m, d, n)
        coeffs = [powered[0][0] - 1, powered[0][1], powered[1][0], powered[1][1]]
        g = n
        for value in coeffs:
            g = __import__("math").gcd(g, value)
        if 1 < g < n:
            return g
        for value in coeffs:
            g = __import__("math").gcd(n, value)
            if 1 < g < n:
                return g

    rng = __import__("random").Random(123456789)
    for _ in range(32):
        d = (rng.randrange(0, n), rng.randrange(0, n))
        t = (rng.randrange(2, n - 1), rng.randrange(2, n - 1))
        element, factor = make_norm_one_element(t, d, n)
        if element is None:
            if 1 < factor < n:
                return factor
            continue
        powered = pow_e(element, m, d, n)
        coeffs = [powered[0][0] - 1, powered[0][1], powered[1][0], powered[1][1]]
        g = n
        for value in coeffs:
            g = __import__("math").gcd(g, value)
        if 1 < g < n:
            return g
        for value in coeffs:
            g = __import__("math").gcd(n, value)
            if 1 < g < n:
                return g
    raise RuntimeError("failed to recover a non-trivial factor")


def long_to_bytes(value):
    hex_value = hex(value)[2:]
    if len(hex_value) & 1:
        hex_value = "0" + hex_value
    return bytes.fromhex(hex_value)


def main():
    p = find_factor(N, E)
    q = N // p
    phi = (p - 1) * (q - 1)
    d = pow(E, -1, phi)
    message = pow(CT, d, N)
    print(long_to_bytes(message).decode())


if __name__ == "__main__":
    main()

结果

脚本恢复出的一个素因子是：

\[\begin{aligned} p ={}& 136150908296671697837002304120554609254860025973703009107142696974030383527546682335255282706065565181217452980646224312551395829044711422887768079854720067996275777605522137233617241864667028063365635726949765729463936207570527662002068844517813956206489467333179309477357948407658191762790343996647122219103584441226208376160704226292198163970896035425934407087327399070047293386957302843052008199621208773626497223811568448326868053764529994222625419445440690507989944568169610796390375160166679138793033158925234849858934237840031670122761843226503668017558998639260148544202892204320370131000906673148803705620871 \end{aligned}\]

然后直接计算：

\[q = \left\lfloor \frac{N}{p} \right\rfloor\] \[\varphi(N) = (p-1)(q-1)\] \[d \equiv e^{-1} \pmod{\varphi(N)}\] \[m \equiv ct^d \pmod N\]

就能得到明文。

THEM?!CTF{W0W_kumm3r_5tr1k35_4g41n_1m_0ut_0f_fl4g5_t3xt_239b86bd3e5c43e2c71a0e872baddf76a1cf3ae8e36274b08ecec2aa7a5296df}