关于 校内CTF比赛 UCATFLAGS 2024 出的一些题

本次比赛是笔者主导发起的、学校本科的第一场本科部级的CTF比赛，笔者共出了 5 个Welcome题目，1 个 Pwn题（UAF+堆管理），3.5 个 Misc （1 个 AI模型题、1 个音频隐写、1 个文件格式题、0.5 个社会工程题）和 6 个 Crypto。下面给出其中两个 Crypto 题目的解题思路。

Challenge Type Solutions Points Keywords
MyLittlePoly Crypto 12 250 多项式的计算、最大公因数
EzPrime Crypto 11 250 RSA算法+小规模爆破+解二次方程
AfterStory Crypto 8 300 已知明文攻击+LFSR状态泄露
BabyDLog Crypto 6 400 Pohlig-Hellman 算法的深入理解
GoldenYear Crypto 0 500 椭圆曲线点群阶数、LSB搜索、同余方程
Latte Crypto 0 500 AGCD、背包+离散对数
IAmFree! Pwn 3 350 简单的UAF + 堆管理
BigConcert Misc 11 200 简单的音频声道隐写、摩斯电码
backdoor Misc 6 300 简单的DNN模型项目代码理解
easypicture Misc 16 300 简单的文件格式分析

GoldenYear

题干代码

2024年的玉泉路是金黄色的，将满是回忆。

GoldenYear.sage

# sagemath
from Crypto.Util.number import *
from os import urandom
from Flag import FLAG, MAXLEN

New_Year = 2024
FLAG = FLAG + urandom(MAXLEN - len(FLAG))

# Verify the Goldbach's Conjecture
Goldbach_christian = [(p, New_Year - p) for p in sieve_base if p <= New_Year // 2 and isPrime(New_Year - p)]

# 2024 is a Leap Year!
Happy_2024, Haqqy_2024 = getPrime(New_Year // 4), getPrime(New_Year // 4)
while (Happy_2024 % 3 == Haqqy_2024 % 3):
    Happy_2024 = getPrime(New_Year // 4)
Hanny_2024 = Happy_2024 * Haqqy_2024

# The exuberant new year of 2024 will bring us joy and excitement!
p, q = choice(Goldbach_christian)
Exuberant_p = EllipticCurve(GF(Happy_2024), [0, p])
Exuberant_q = EllipticCurve(GF(Haqqy_2024), [0, q])

# Happy New Year!
m = bytes_to_long(FLAG)
with open(r"./output.txt", "w") as f:
    gift1 = bytes_to_long(str(Exuberant_p.order() + q).encode()) * bytes_to_long(str(Haqqy_2024 + p).encode())
    gift2 = bytes_to_long(str(Happy_2024 + q).encode()) * bytes_to_long(str(Exuberant_q.order() + p).encode())
    print(f"I'll give the gifts to U: {Hanny_2024, gift1, gift2}", file = f)
    red_envelope1 = pow(Happy_2024 * m + Exuberant_p.order(), Haqqy_2024, Hanny_2024)
    red_envelope2 = pow(Haqqy_2024 * m + Exuberant_q.order(), Happy_2024, Hanny_2024)
    print(f"OKOK ~ I'll give U both my red envelopes: {(red_envelope1 + red_envelope2) % Hanny_2024}", file = f)

output.txt

I'll give the gifts to U: (20243063012381093065881715376803640816923818203625911640694784993789286636611180835921608390045413835542916314861539938722171842014382670606414163394994894668365164929867556130798284960121925034107155666591563718174618437343159515015854655008175217672889911863891053034708651435516540210570245991063171289, 3082830559038877744539857448969808147340468463825357858541058129026110543191536241000397185264316057842094866363953733054989122356139453391356731191975829726832037786724893103057593038097144042673463810432983923372914638559633536471618619482302004617729891895118724873404754109722821248796445568519005866543646123446178955716385193501431092935028347031054773643129268914254426313530748324498727786408429432156630438289014574042635727761302151785956285737839574363413926555001728577343808599432210101775474025849266347224644582573221902585346919924996022499981173366240328668308502429507808470604746535923016683822196192993568289713072203814997890729262294909812821367061856088587537284075245689333865060423210347243013777511472403383304, 3082830559038877744539857448969808147340468463825357858541058129026110543191536241000397185264316057842094866363953733054989122356139453391356731191975829726832037786724893103057593038216217536027471947135543545371933118755272502325512823354293788008534797452079854008261955881875509964629925233416040952762759456529527642367686423321679563388067512673864367064259939501631392224619750617648481056541218717491489589148264984800793218746131598354744063462469714933567095917446196156778081743234319680672351161560960057307138485005738193883799762282567263840999618884631103691058355449154243356632772447934686630333029322247571260185386757991734700408212263554584499979733547418238195693215881963434496586637612459533424028727466150670988)
OKOK ~ I'll give U both my red envelopes: 2053306399329493484171909216754446971778876338572305861281393386450367892503612914088507585084261917515228499040036138151202134583664706045917520505194094450066544241663702222706889993979023385508314787933724825993887808366549319278298208023774104687051338473854159671013079568527042769852891874689463806

解题思路与解题代码

Point 1：椭圆曲线基本常识

关注到代码片段：

Happy_2024, Haqqy_2024 = getPrime(New_Year // 4), getPrime(New_Year // 4)
while (Happy_2024 % 3 == Haqqy_2024 % 3):
    Happy_2024 = getPrime(New_Year // 4)

p, q = choice(Goldbach_christian)
Exuberant_p = EllipticCurve(GF(Happy_2024), [0, p])
Exuberant_q = EllipticCurve(GF(Haqqy_2024), [0, q])

此处素数模 33 是一个十分重要的提示，根据有限域上椭圆曲线点群的相关结论，如果素数 p≡2(mod3)p \equiv 2 \pmod{3} ，那么 Fp\mathbb{F}_p 上形如 y2=x3+cy^2 = x^3 + c 的椭圆曲线的阶一定满足 ∣E(Fp)∣=p+1\lvert E(\mathbb{F}_p)\rvert = p + 1 。因此上述代码一定满足下列条件：

assert (Exuberant_p.order() == Happy_2024 + 1 and Exuberant_q.order() != Haqqy_2024 + 1) or (Exuberant_p.order() != Happy_2024 + 1 and Exuberant_q.order() == Haqqy_2024 + 1)

证明 p≡2(mod3)p \equiv 2 \pmod{3} 的情况：
根据熟知的有限域上椭圆曲线点的计算公式（公式依据就是遍历每个 xx ，计算 yy 可以开平方的数量）：

#E(Fp)=1+∑k∈Fp((k3+cp)+1)=p+1+∑k∈Fp(k3+cp)=p+1+∑k∈Fp(kp)=p+1\begin{aligned} \#E(\mathbb{F}_p) &= 1 + \sum\limits_{k\in\mathbb{F}_p} \left(\left(\dfrac{k^3+c}{p}\right) + 1\right) \\ &= p + 1 + \sum\limits_{k\in\mathbb{F}_p} \left(\dfrac{k^3+c}{p}\right) \\ &= p + 1 + \sum\limits_{k\in\mathbb{F}_p} \left(\dfrac{k}{p}\right) \\ &= p + 1 \end{aligned}

注：

  1. 考虑 p≡2(mod3)p \equiv 2\pmod{3}，不考虑 k=0k = 0 ，由于 k13+c=k23+ck_1 ^ 3 + c = k_2 ^ 3 + c ⇔\Leftrightarrow k13=k23k_1 ^ 3 = k_2 ^ 3 ，而 p−1≡1(mod3)p - 1 \equiv 1\pmod{3} ，根据费马小定理 k1p−1=k2p−1=1k_1 ^ {p-1} = k_2^{p-1} = 1 ，那么 k13+c=k23+ck_1 ^ 3 + c = k_2 ^ 3 + c ⇔\Leftrightarrow k13⋅p−23=k23⋅p−23k_1^{3\cdot \frac{p-2}{3}} = k_2^{3\cdot \frac{p-2}{3}} ⇔\Leftrightarrow k1=k2k_1 = k_2 。因此 k3+ck^3+c 恰好构成 pp 的一个完全剩余系。（听起来高级一点的说法就是 x↦x3+cx \mapsto x^3 + c 为 Fp∗\mathbb{F}_p^{*} 上的一个内自同构）

  2. 二次剩余和二次非剩余的数量相等；00 的勒让德符号值为 00。

Point 2：广度优先搜索+爆破

记 pHp_H 和 qHq_H 分别表示 Happy_2024 和 Haqqy_2024 ，nHn_H 表示 Hanny_2024 ，另外记 aa 和 bb 分别表示 p 和 q
pH,qHp_H, q_H 在十进制下可以被写成如下形式：

pH=a0+a110+a2102+⋯qH=b0+b110+b2102+⋯\begin{aligned} p_H &= a_0 + a_1 10 + a_2 10^2 + \cdots \\ q_H &= b_0 + b_1 10 + b_2 10^2 + \cdots \end{aligned}

记 f = lambda x: bytes_to_long(str(x).encode()) 为 ff 因此 f(x)f(x) 就可以写成：

f(x)=(48+x0)+(48+x1)256+(48+x2)2562+⋯f(x) = (48 + x_0) + (48 + x_1) 256 + (48 + x_2) 256^2 + \cdots

根据上一条对于有限域上椭圆曲线点群阶的讨论，不妨设 Exuberant_p.order() == Happy_2024 + 1 ，记 ngn_g 表示这里的 gift1 = f(Exuberant_p.order() + q) * f(Haqqy_2024 + p) ，那么就有：

nH=pH⋅qH=(p0+p110+p2102+⋯ )⋅(q0+q110+q2102+⋯ )ng=f(pH+1+b)⋅f(qH+a)=f(pH′)⋅f(qH′)=((48+p0′)+(48+p1′)256+(48+p2′)2562+⋯ )⋅((48+q0′)+(48+q1′)256+(48+q2′)2562+⋯ )\begin{aligned} n_H &= p_H \cdot q_H \\ &= (p_0 + p_1 10 + p_2 10^2 + \cdots)\cdot(q_0 + q_1 10 + q_2 10^2 + \cdots) \\ n_g &= f(p_H + 1 + b)\cdot f(q_H + a) \\ &= f(p_H')\cdot f(q_H') \\ &= \left((48 + p_0') + (48 + p'_1) 256 + (48 + p_2') 256^2 + \cdots\right)\cdot\left((48 + q_0') + (48 + q_1') 256 + (48 + q_2') 256^2 + \cdots\right) \end{aligned}

考虑 nH≡(∑j=0i−1pj10j)⋅(∑j=0i−1qj10j)(mod10i)n_H \equiv \left(\sum\limits_{j=0}^{i-1} p_j 10^j\right) \cdot \left(\sum\limits_{j=0}^{i-1} q_j 10^j\right) \pmod{10^i} 以及 ng≡(∑j=0i−1(48+pj′)256j)⋅(∑j=0i−1(48+qj′)256j)(mod256i)n_g \equiv \left(\sum\limits_{j=0}^{i-1} (48+p_j') 256^j\right) \cdot \left(\sum\limits_{j=0}^{i-1} (48+q_j') 256^j\right) \pmod{256^i} 从低到高逐数位恢复即可。

这里可以使用递推或者递归实现，但是递归实现小心爆栈。

Point 3：小密钥空间

New_Year = 2024
Goldbach_christian = [(p, New_Year - p) for p in sieve_base if p <= New_Year // 2 and isPrime(New_Year - p)]

根据上述代码可知，列表 Goldbach_christian 空间是很小的，因此枚举即可

至此已经可以求出两个素数了，下面先给出一部分代码。

from Crypto.Util.number import *

New_Year = 2024
Goldbach_christian = [(p, New_Year - p) for p in sieve_base if p <= New_Year // 2 and isPrime(New_Year - p)]

def factor(nh, ng, a, b, f = lambda x: bytes_to_long(str(x).encode())):
    nh_p = None
    def test_digits(ps, qs):
        nonlocal nh_p
        if nh_p is not None:
            return False
        p = sum([pi * 10 ** i for i, pi in enumerate(ps)])
        p_with_a = p + a
        new_ps = [int(i) for i in str(p_with_a).zfill(len(ps))[::-1]][:len(ps)]
        pp = sum([(48 + pi) << (i * 8) for i, pi in enumerate(new_ps)])
        q = sum([pi * 10 ** i for i, pi in enumerate(qs)])
        q_with_b = q + b
        new_qs = [int(i) for i in str(q_with_b).zfill(len(qs))[::-1]][:len(qs)]
        qq = sum([(48 + qi) << (i * 8) for i, qi in enumerate(new_qs)])
        if p != 0 and p != 1 and nh % p == 0:
            nh_p = p
            return False
        m1 = 10 ** len(ps)
        m2 = 1 << (len(qs) * 8)
        return (p * q) % m1 == nh % m1 and (pp * qq) % m2 == ng % m2

    stack = [([], [])]
    while stack:
        ps, qs = stack.pop()
        stack += [(ps + [i], qs + [j]) for i in range(10) for j in range(10) if test_digits(ps + [i], qs + [j])]

    ng_p = f(nh_p + a)
    assert ng % ng_p == 0
    return nh_p, nh // nh_p

New_Year = 2024
Goldbach_christian = [(p, New_Year - p) for p in sieve_base if p <= New_Year and isPrime(New_Year - p)]
def get_factors(n, nn, ABlist):
    Hp, Hq, p, q = None, None, None, None
    for a, b in ABlist:
        try:
            Hp, Hq = factor(n, nn, a + 1, b)
            print(Hp, Hq, a, b)
            p, q = a, b
            break
        except: pass
    return Hp, Hq, p, q
pH, qH, p, q = get_factors(n, g1, Goldbach_christian)
if pH is None or qH is None:
    pH, qH, p, q = get_factors(n, g2, Goldbach_christian)

Point 4：数论变换

这一部分是一个简单的数论变换。记 pHp_H 和 qHq_H 分别表示 Happy_2024 和 Haqqy_2024 ，nHn_H 表示 Hanny_2024 ，另外记 ωp\omega_p 和 ωq\omega_q 分别表示 Exuberant_p 和 Exuberant_q ，这些变量现在都已经是已知的了
那么根据代码片段：

red_envelope1 = pow(Happy_2024 * m + Exuberant_p.order(), Haqqy_2024, Hanny_2024)
red_envelope2 = pow(Haqqy_2024 * m + Exuberant_q.order(), Happy_2024, Hanny_2024)
print(f"OKOK ~ I'll give U both my red_envelopes: {(red_envelope1 + red_envelope2) % Hanny_2024}", file = f)

可以整理得到如下表达式：

c≡(pH⋅m+ωp)qH+(qH⋅m+ωq)pH(modnH)c \equiv (p_H \cdot m + \omega_p)^{q_H} + (q_H \cdot m + \omega_q)^{p_H} \pmod{n_H}

注意到 nH=pH⋅qHn_H = p_H \cdot q_H ，那么根据费马小定理可以得到如下方程组：

{c≡ωpqH+qH⋅m+ωq(modpH)c≡pH⋅m+ωp+ωqpH(modqH)\begin{cases} c \equiv \omega_p^{q_H} + q_H \cdot m + \omega_q & \pmod{p_H} \\ c \equiv p_H \cdot m + \omega_p + \omega_q^{p_H} & \pmod{q_H} \\ \end{cases}

从而有：

{mp≡qH−1⋅(c−ωpqH−ωq)(modpH)mq≡pH−1⋅(c−ωp−ωqpH)(modqH)\begin{cases} m_p \equiv q_H ^ {-1} \cdot(c - \omega_p^{q_H} - \omega_q) & \pmod{p_H} \\ m_q \equiv p_H ^ {-1} \cdot(c - \omega_p - \omega_q^{p_H}) & \pmod{q_H} \\ \end{cases}

最后利用中国剩余定理即可恢复 mm 。

这里主要注意一点是前面解出来的小 p 和小 q 可能顺序不对应，调整一下就好了：

# sagemath
Ep = EllipticCurve(GF(pH), [0, p])
Eq = EllipticCurve(GF(qH), [0, q])
omega_p = Ep.order()
omega_q = Eq.order()
mp = inverse(int(qH), int(pH)) * (int(c) - int(pow(omega_p, qH, pH)) - int(omega_q)) % pH
mq = inverse(int(pH), int(qH)) * (int(c) - int(pow(omega_q, pH, qH)) - int(omega_p)) % qH
m = crt([mq, mp], [pH, qH])
print(long_to_bytes(int(m)))

Ep = EllipticCurve(GF(pH), [0, q])
Eq = EllipticCurve(GF(qH), [0, p])
omega_p = Ep.order()
omega_q = Eq.order()
mp = inverse(int(qH), int(pH)) * (int(c) - int(pow(omega_p, qH, pH)) - int(omega_q)) % pH
mq = inverse(int(pH), int(qH)) * (int(c) - int(pow(omega_q, pH, qH)) - int(omega_p)) % qH
m = crt([mp, mq], [pH, qH])
print(long_to_bytes(int(m)))

完整解题代码

# sagemath

n, g1, g2 = 
c = 

from Crypto.Util.number import *

New_Year = 2024
Goldbach_christian = [(p, New_Year - p) for p in sieve_base if p <= New_Year // 2 and isPrime(New_Year - p)]

def factor(nh, ng, a, b, f = lambda x: bytes_to_long(str(x).encode())):
    nh_p = None
    def test_digits(ps, qs):
        nonlocal nh_p
        if nh_p is not None:
            return False
        p = sum([pi * 10 ** i for i, pi in enumerate(ps)])
        p_with_a = p + a
        new_ps = [int(i) for i in str(p_with_a).zfill(len(ps))[::-1]][:len(ps)]
        pp = sum([(48 + pi) << (i * 8) for i, pi in enumerate(new_ps)])
        q = sum([pi * 10 ** i for i, pi in enumerate(qs)])
        q_with_b = q + b
        new_qs = [int(i) for i in str(q_with_b).zfill(len(qs))[::-1]][:len(qs)]
        qq = sum([(48 + qi) << (i * 8) for i, qi in enumerate(new_qs)])
        if p != 0 and p != 1 and nh % p == 0:
            nh_p = p
            return False
        m1 = 10 ** len(ps)
        m2 = 1 << (len(qs) * 8)
        return (p * q) % m1 == nh % m1 and (pp * qq) % m2 == ng % m2

    stack = [([], [])]
    while stack:
        ps, qs = stack.pop()
        stack += [(ps + [i], qs + [j]) for i in range(10) for j in range(10) if test_digits(ps + [i], qs + [j])]

    ng_p = f(nh_p + a)
    assert ng % ng_p == 0
    return nh_p, nh // nh_p

New_Year = 2024
Goldbach_christian = [(p, New_Year - p) for p in sieve_base if p <= New_Year and isPrime(New_Year - p)]
def get_factors(n, nn, ABlist):
    Hp, Hq, p, q = None, None, None, None
    for a, b in ABlist:
        try:
            Hp, Hq = factor(n, nn, a + 1, b)
            print(Hp, Hq, a, b)
            p, q = a, b
            break
        except: pass
    return Hp, Hq, p, q
pH, qH, p, q = get_factors(n, g1, Goldbach_christian)
if pH is None or qH is None:
    pH, qH, p, q = get_factors(n, g2, Goldbach_christian)

Ep = EllipticCurve(GF(pH), [0, p])
Eq = EllipticCurve(GF(qH), [0, q])
omega_p = Ep.order()
omega_q = Eq.order()
mp = inverse(int(qH), int(pH)) * (int(c) - int(pow(omega_p, qH, pH)) - int(omega_q)) % pH
mq = inverse(int(pH), int(qH)) * (int(c) - int(pow(omega_q, pH, qH)) - int(omega_p)) % qH
m = crt([mq, mp], [pH, qH])
print(long_to_bytes(int(m)))

Ep = EllipticCurve(GF(pH), [0, q])
Eq = EllipticCurve(GF(qH), [0, p])
omega_p = Ep.order()
omega_q = Eq.order()
mp = inverse(int(qH), int(pH)) * (int(c) - int(pow(omega_p, qH, pH)) - int(omega_q)) % pH
mq = inverse(int(pH), int(qH)) * (int(c) - int(pow(omega_q, pH, qH)) - int(omega_p)) % qH
m = crt([mp, mq], [pH, qH])
print(long_to_bytes(int(m)))

Latte

题干代码

一杯地道的拿铁咖啡，配制的比例是牛奶占70%、奶沫20%、咖啡10%。不过我也有我自己的拿铁咖啡秘密配方，你能解开它吗？

Latte.py

import os
from Flag import FLAG
from MyLatteRepo import CUP, SPOON
from Crypto.Util.number import bytes_to_long, getRandomNBitInteger as RandBitInt

Amount = 96
Milk = os.urandom(16) * 8
Espresso = FLAG + os.urandom(Amount - len(FLAG))

with open(r"output.txt", "w") as f:
    print(f"Secret Recipe = {[tuple(RandBitInt(Amount) * TableWare + RandBitInt(Amount) for _ in range(2)) for TableWare in (CUP, SPOON)]}", file=f)
    print(f"Thick Latte = {pow(SPOON, bytes_to_long(Espresso + Milk), CUP ** 2)}", file=f)

MyLatteRepo.py

from Crypto.Util.number import getPrime
CUP, SPOON = getPrime(1024), getPrime(1023)

output.txt

Secret Recipe = [(7713728406427216751554669259392564225336715833405752115381741192770705127449580203149702790344362306038809396807649838869061646825414855115281945957936663046654597534205905897175890178111315995254386657057762733095874608001275952979326053898143312737463706959131172849869413280104618789870525444846308811177858689495229895344683454580950, 10768179705714029637486823876049385323286739410640293933059996834750818396728290193643930846035066620748980549564939970460538905794696240546865167074683494614932952147502138271504281179082644890287956486068437561613270593639955518366259238860093126375044566302145336839299698696953932193554693269889774553104747679934421788071379684047915), (2898813132870923822777364992441270262502451755815932783777103680715031737093464555201012481453587077640406026905664044181285477747422049637936736855670910340762277892609290987252636816482044722119626550674047412622124045604541059525595043435592277961925044167418669671070332108592596709889174367812547474906749734439633509985838606222960, 2367559009552417131041378739974356297751002698778465850165050259445912894845076511101152884465249070441230089677370105742148697551267296224211034179040069757613002687259581727661569679606228550112626907697624938047107562660618012512691699375628474791262692117911743763161978380251049593695853607487996373529877746744715681916370876905026)]
Thick Latte = 20253232364768706926657485015049869073760656433294604067483464164523871937032855264502276827180968267948099001484311159380007672576388212344106685365998360069778982260692360184986401704121446642207721387626751348876990232847057047018213774615443495418352798433539096655873616282540001939164316406665677968957728127542212939916975714081533666005788317489175126976192690644215563210089888539431393271742697820031432708144235650686331750559997766949714325602181599668062799960432143171917892374753391669283145013751645161429336541215774184990625832380011450653150508569090082960763279097984362744541280481182272786223879

解题思路与解题代码

Point 1：AGCD问题

首先对于 Secret Recipe：

print(f"Secret Recipe = {[tuple(RandBitInt(Amount) * TableWare + RandBitInt(Amount) for _ in range(2)) for TableWare in (CUP, SPOON)]}", file=f)

设 CUP 为 uu，SPOON 为 ss，那么给到的信息就是：

{a1u+b1=h1a2u+b2=h2\begin{cases} a_1 u + b_1 = h_1\\ a_2 u + b_2 = h_2\\ \end{cases}

以及

{a1′s+b1′=h1′a2′s+b2′=h2′\begin{cases} a_1' s + b_1' = h_1'\\ a_2' s + b_2' = h_2'\\ \end{cases}

其中 aia_i 、 bib_i 、ai′a_i' 和 bi′b_i' 为小的随机数，hih_i 和 hi′h_i' 是已知的。

这是典型的 AGCD 问题，比如我们考虑针对 uu 的这组等式

注意到

a2h1−a1h2=a2b1−b2a1a_2 h_1 - a_1 h_2 = a_2 b_1 - b_2 a_1

等式右边是一个小数据

那么可以构造如下格子：

(a2−a1)⋅(h110h201)=(a2b1−b2a1a2−a1)\begin{pmatrix} a_2 &-a_1 \end{pmatrix} \cdot \begin{pmatrix} h_1 & 1 & 0 \\ h_2 & 0 & 1 \end{pmatrix} = \begin{pmatrix} a_2 b_1 - b_2 a_1 & a_2 & -a_1 \end{pmatrix}

右边是一个短向量，所以对左边的格子 (h110h201)\begin{pmatrix}h_1 & 1 & 0 \\ h_2 & 0 & 1\end{pmatrix} 作 LLL 格基约化即可。

这一层的解题代码如下：


with open("./output.txt", "r") as f:
    s1, s2 = f.readlines()
    sp, sg = eval(s1.split("= ")[1])
    secret = int(s2.split("= ")[1])

def getSec(h1, h2, bits):
    mat = matrix(ZZ, [[h1, 1, 0], [h2, 0, 1]])
    mat = mat.LLL()
    t, a2, a1 = mat[0]
    a2, a1 = abs(a2), abs(a1)
    pre_p = h1 // a1
    for i in range(pre_p >> bits, pre_p >> (bits - 1)):
        q = pre_p // (i + 1)
        for bias in range(-4, 5):
            r = q + bias
            if is_prime(r) and r.bit_length() == bits: return r
    print("Failed")

p, g = getSec(*sp, 1024), getSec(*sg, 1023)
print(p)
print(g)

Point 2： p2p^2 下的离散对数转化为背包问题

由于

Milk = os.urandom(16) * 8

所以可以设
设随机产生的部分为 xx， A = bytes_to_long((b"\x00"*15 + b"\x01") * 8) 则

assert bytes_to_long(Milk) == x * A

简记为数学公式： Milk=A⋅x\text{Milk} = A\cdot x

其中 x∼2128x \sim 2^{128}

进一步观察第二个式子，根据 len(Milk) == 128 ，同时设 y = bytes_to_long(FLAG)，那么有数学关系：

s=Thick Latte=g2128×8y+x⋅A(modp2)s = \text{Thick Latte} = g^{2^{128\times 8}y + x\cdot A}\pmod{p^2}

记 B=2128×8B = 2^{128\times 8} 则化为：

s=gAx+By(modp2)=(gA)x⋅(gB)y(modp2)\begin{aligned} s & = g^{Ax+By}\pmod{p^2} \\ & = \left(g^A\right)^x \cdot \left(g^B\right)^y\pmod{p^2} \end{aligned}

其中 x∼2128x\sim 2^{128} ， y∼2768y\sim 2^{768} ， p∼21024p \sim 2^{1024}

考虑如下推导：

s′=sp−1=(gA(p−1))x⋅(gB(p−1))y(modp2)s' = s^{p-1} = \left(g^{A(p-1)}\right)^x\cdot \left(g^{B(p-1)}\right)^y\pmod{p^2}

注意，根据费马小定理，gA(p−1)≡1(modp)g^{A(p-1)}\equiv 1\pmod{p} ，以及 gB(p−1)≡1(modp)g^{B(p-1)}\equiv 1\pmod{p} ，则说明 gA(p−1)−1g^{A(p-1)} - 1 和 gB(p−1)−1g^{B(p-1)} - 1 均为 pp 的倍数。

设 gA(p−1)−1=apg^{A(p-1)} - 1 = ap ， gB(p−1)−1=bpg^{B(p-1)} - 1 = bp ，则根据二项式定理有：

s′=(ap+1)x⋅(bp+1)y(modp2)=(xap+1)⋅(ybp+1)(modp2)=(ax+by)⋅p+1(modp2)\begin{aligned} s' & = (ap+1)^x\cdot (bp+1)^y &\pmod{p^2} \\ & = (xap+1)\cdot (ybp+1) &\pmod{p^2} \\ & = (ax+by)\cdot p + 1 &\pmod{p^2} \end{aligned}

即：

S′=s′−1p=ax+by(modp)S' = \dfrac{s' - 1}{p} = ax + by \pmod{p}

其中 x∼2128x\sim 2^{128} ， y∼2768y\sim 2^{768} ， p∼21024p \sim 2^{1024}

进一步转化为：

−x=−a−1S′+a−1b⋅y(modp)-x = - a^{-1}S' + a^{-1}b\cdot y\pmod{p}

设 S=a−1S′ mod pS = a^{-1}S'\bmod{p} ， 以及 C=a−1b mod pC = a^{-1}b\bmod{p}

得到 −x=−S+Cy−kp-x = - S + Cy - kp 很小，其中 x∼2128x\sim 2^{128} ， k∼y∼2768k\sim y\sim 2^{768} ， S∼C∼p∼21024S \sim C \sim p \sim 2^{1024}

因此可以构造一个矩阵

M=(12768−1280C02128S00p)M = \begin{pmatrix} \dfrac{1}{2^{768 - 128}} & 0 & C \\ 0 & 2^{128} & S \\ 0 & 0 & p \end{pmatrix}

满足：

(y−1k)⋅M=(y2640−2128−x)\begin{pmatrix} y & -1 & k\end{pmatrix} \cdot M = \begin{pmatrix} \dfrac{y}{2^{640}} \\\\ -2^{128} \\\\ -x \end{pmatrix}

其中 12640\dfrac{1}{2^{640}} 和 21282^{128} 是为了控制最后向量的大小，和矩阵左乘系数恰好是我们想要的，考察选手对于利用格规约解决小未知数方程的手段，对于格子构造的理解。

unit = b"\x00" * 15 + b"\x01"
A = bytes_to_long(unit * 8)

unit = b"\x00" * 16
B = bytes_to_long(b"\01" + unit * 8)

ap = pow(g, A * (p - 1), p ** 2) - 1
bp = pow(g, B * (p - 1), p ** 2) - 1

assert int(ap) % p == 0 
assert int(bp) % p == 0 

a, b = int(ap) // p, int(bp) // p
C = (b * inverse(a, p)) % p
S = int(pow(int(secret), p - 1, p ** 2)) - 1
assert int(S) % p == 0
S = ((int(S) // p) * inverse(a, p)) % p

M = matrix([[1/2**(768 - 128), 0, C], [0, 2**128, S], [0, 0, p]])
ML = M.LLL()
print(ML)
for v in ML:
    the_flag = abs((v * (2 ** (768 - 128)))[0])
    print(long_to_bytes(int(the_flag)))

完整解题代码

from Crypto.Util.number import *

with open("./output.txt", "r") as f:
    s1, s2 = f.readlines()
    sp, sg = eval(s1.split("= ")[1])
    secret = int(s2.split("= ")[1])

def getSec(h1, h2, bits):
    mat = matrix(ZZ, [[h1, 1, 0], [h2, 0, 1]])
    mat = mat.LLL()
    t, a2, a1 = mat[0]
    a2, a1 = abs(a2), abs(a1)
    pre_p = h1 // a1
    for i in range(pre_p >> bits, pre_p >> (bits - 1)):
        q = pre_p // (i + 1)
        for bias in range(-4, 5):
            r = q + bias
            if is_prime(r) and r.bit_length() == bits: return r
    print("Failed")

p, g = getSec(*sp, 1024), getSec(*sg, 1023)
print(p)
print(g)

unit = b"\x00" * 15 + b"\x01"
A = bytes_to_long(unit * 8)

unit = b"\x00" * 16
B = bytes_to_long(b"\01" + unit * 8)

ap = pow(g, A * (p - 1), p ** 2) - 1
bp = pow(g, B * (p - 1), p ** 2) - 1

assert int(ap) % p == 0 
assert int(bp) % p == 0 

a, b = int(ap) // p, int(bp) // p
C = (b * inverse(a, p)) % p
S = int(pow(int(secret), p - 1, p ** 2)) - 1
assert int(S) % p == 0
S = ((int(S) // p) * inverse(a, p)) % p

M = matrix([[1/2**(768 - 128), 0, C], [0, 2**128, S], [0, 0, p]])
ML = M.LLL()
print(ML)
for v in ML:
    the_flag = abs((v * (2 ** (768 - 128)))[0])
    print(long_to_bytes(int(the_flag)))
 2024-12-09   UCATFLAGS   Crypto   CTF  

上一篇  下一篇