25Jan2

huangx607087 1月的切题2

0.Introduction

是时候补一下最近错过的题了。

写完NTRU那个笔记，和外面的师傅们讨论了一下SUCTF的几个题，顺便补了两个SCTF的题目。因为是和外面师傅一起讨论做的题，就当玩玩，所以没有交flag（当然，正式比赛，肯定还是得自己做的！）。

很有意思的一道题目：

from Crypto.Util.number import *
from secret import flag

bit_length = len(flag) * 8

p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
K = GF(p)
E = EllipticCurve(K, (0, 4))
o = 793479390729215512516507951283169066088130679960393952059283337873017453583023682367384822284289
n1, n2 = 859267, 52437899

while(1):
    G1, G2 = E.random_element(), E.random_element()
    if(G1.order() == o and G2.order() == o):
        P1, P2 = (o//n1)*G1, (o//n2)*G2
        break

cs = [(randrange(0, o) * P1 + randrange(0, o) * G2).xy() if i == "1" else (randrange(0, o) * G1 + randrange(0, o) * P2).xy() for i in bin(bytes_to_long(flag))[2:].zfill(bit_length)]
print(cs)

题目给出了一个椭圆曲线 $y^2\equiv x^3+4 \pmod p$，在椭圆曲线上找到两个阶为 $o$ 的点 $G_1,G_2$，并构造 $P_1=k_1G_1,P_2=k_2G_2$，使得 $P_1,P_2$ 的阶数分别为 $n_1,n_2$。要求区分每个点的表达式是 $xG_2+yP_1$ 还是 $xG_1+yP_2$。

这么奇怪的表达式，肯定得往pairing去想。随便写个代码测一下：

while(1):
    G1, G2 = E.random_element(), E.random_element()
    if(G1.order() == o and G2.order() == o):
        P1, P2 = (o//n1)*G1, (o//n2)*G2
        break
G1.weil_pairing(G2,o)
#2043960270847413570808455484853990840286568693988679265167903455579011705465705419705469862656455560563791378579381

发现随机按照题目要求生成的参数 $G_1,G_2$，其配对 $e(G_1,G_2)\not =1$，说明 $G_1=kG_2$ 的概率很小。

那么以 $xG_1+yP_2$ 为例：若计算 $n_2(xG_1+yP_2)$，就会得到 $n_2xG_1$ 的值。若此时与另一组 $n_2(uG_1+vP_2)=n_2uG_1$ 配对，那么你会发现 $n_2xG_1=k\cdot n_2uG_1$，这个配对值肯定为 $1$。而如果和 $n_2(rG_2+sP_1)$ 配对，由于这里乘了 $n_2$，且 $G_1\not=kG_2$，因此这个配对不等于 $1$。

好家伙，原来这个双线性对是这样用的，知识又长了！

由于flag一般都是可见字符，因此 $C_0$ 一定具有 $xG_1+yP_2$ 的形式，那就以 $C_0$ 为基点，每个配对去吧！

p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
K = GF(p)
E = EllipticCurve(K, (0, 4))
o = 793479390729215512516507951283169066088130679960393952059283337873017453583023682367384822284289
n1, n2 = 859267, 52437899
Cxy = [......]
C = [E(xi,yi) for xi,yi in Cxy]

H=C[0]*n2
s=0
for i in range(0,len(C)):
    k=(H.weil_pairing(C[i]*n2,o))
    s<<=1
    s|=bool(k-1)
from Crypto.Util.number import *
print(long_to_bytes(s))
#SUCTF{We1come__T0__SUCTF__2025}

2.[SUCTF2025]SU_RSA

题面很简单，给出了 $d$ 的高 $512$ 位，要求分解 $n$。

from Crypto.Util.number import *
from hashlib import sha256
flag = open("flag.txt").read()
p = getPrime(512)
q = getPrime(512)
e = getPrime(256)
n = p*q
d = inverse(e,(p-1)*(q-1))
d_m = ((d >> 512) << 512)
print("d_m = ",d_m)
print("n = ",n)
print("e = ",e)
assert flag[6:-1] == sha256(str(p).encode()).hexdigest()[:32]

重新推式子可以得到，其中 $k=\left\lfloor\dfrac{ed_m}{n}\right\rfloor$。
$$
ed=kn-k(p+q)+1+k
$$
然后，两边对 $e$ 取模：
$$
0\equiv kn-k(p+q)+1+k\pmod e
$$
分离出 $p+q$：
$$
p+q\equiv n+1+k^{-1} \pmod e
$$
那么我们就得到了 $p+q \mod e$ 的值，根据 $n \mod e$ 的值，可以解出 $p\mod e,q\mod e$ 的值。

from Crypto.Util.number import *
dm =  54846367460362174332079522877510670032871200032162046677317492493462931044216323394426650814743565762481796045534803612751698364585822047676578654787832771646295054609274740117061370718708622855577527177104905114099420613343527343145928755498638387667064228376160623881856439218281811203793522182599504560128
n =  102371500687797342407596664857291734254917985018214775746292433509077140372871717687125679767929573899320192533126974567980143105445007878861163511159294802350697707435107548927953839625147773016776671583898492755338444338394630801056367836711191009369960379855825277626760709076218114602209903833128735441623
e =  112238903025225752449505695131644979150784442753977451850362059850426421356123

k=1+(e*dm)//n
s=(n+1+inverse(k,e))%e
assert e%4==3
pbar=(s+pow(s*s-4*n,(e+1)//4,e))*inverse(2,e)%e
qbar=(s-pow(s*s-4*n,(e+1)//4,e))*inverse(2,e)%e
print(pbar)
# 56220299912083199824680953877514275031991586299490111910943821482768735249418

由于这里 $e$ 是 $256$ 位，也相当于我们知道了 $p$ 的 $256$ 位内容，只不过这里是模 $e$ 意义下的 $256$ 位内容。

我们回顾一下之前测 flatter 的式子，$f\equiv 2^{u}h+x\pmod n$，其中 $h$ 是 $p$ 的高位比特。

PR = PolynomialRing(Zmod(N), 'x')
x = PR.gen()
f = (h << ubit) + x
tstart=datetime.now()
roots = Small_Roots_Univariate(f, 2 ** ubit, 0.49, 0.007)
tend=datetime.now()
p=Integer(h<<ubit)|Integer(roots[0])
print(hex(p),Integer(N)%Integer(p)==0,str(tend-tstart))

那么这里，构造的式子就应该是：$f\equiv xe+p_L\pmod n$，但这里 $x$ 的上限达到了 $e$，也就是 $256$ 位，因此需要爆破几位。于是我这里构造的是 $f\equiv 2^6xe+ie+p_L\pmod n$，其中枚举 $i$ 从 $0$ 到 $63$，$x$ 的上限为 $\dfrac {e} {64}$。至于其余参数的取值，可以参见 LatticeNotes8 中的参数取值。

exp：

from subprocess import check_output
from re import findall
from sage.all import *

def flatter(M):  # flatter
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))

def matrix_overview(BB):  # see the shape of matrix
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii, jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        print(a)

def Small_Roots_Univariate(f, X=None, beta=1.0, epsilon=None):  # 多项式f,X,beta,epsilon

    delta = f.degree()  # 度delta
    N = f.parent().characteristic()  # 模数N
    PR = PolynomialRing(ZZ, 'x')
    x = PR.gen()

    Zm = f.base_ring()  # Zmod(N)
    f = f.change_ring(ZZ)  # ZZ下f(x)
    if not f.is_monic():  # 首一
        f = f.monic()  # f = f * f[delta].inverse_mod(N)

    m = ceil(max(beta * beta / (delta * epsilon), 7 * beta / delta))  # m
    t = floor(delta * m * (1 / beta - 1))  # t
    #print('m={}, t={}'.format(m, t))

    f_ij = []
    for i in range(m):
        for j in range(delta):
            f_ij.append(x ** j * N ** (m - i) * f ** i)  # shift g_ij(x)
    for i in range(t):
        f_ij.append(x ** i * f ** m)  # shift h_i(x)

    monomials = []
    for g in f_ij:
        monomials += g.monomials()  # 统计所有出现的单项 x^i
    monomials = sorted(set(monomials))  # 去重并排序

    M = Matrix(ZZ, len(f_ij), len(monomials))  # 行数为多项式个数，列数为所有单项可能个数
    for i in range(M.nrows()):
        for j, monomial in enumerate(monomials):
            M[i, j] = f_ij[i].monomial_coefficient(monomial) * monomial.subs(x=X)  # g_ij(xX)和h_i(xX)
    #matrix_overview(M)  # see
    assert M.nrows() == M.ncols()  # 方阵 nrows()=ncols()
    B = flatter(M)  # flater加速
    #print('end LLL')
    for j in range(M.nrows()):  # 得到f(xX)，构建f(x)，求根检验
        Cx = sum(ZZ(B[j, i] // monomials[i](X)) * monomials[i] for i in range(M.ncols()))  # construct polynomial,
        R = Cx.roots()  # get roots
        roots = [Zm(r[0]) for r in R if abs(r[0]) <= X]  # check x0<=X
        roots = [r for r in roots if gcd(N, ZZ(f(r))) >= ZZ(floor(N ** beta))]  # check gcd(f(x_0),N)>N^beta
        if roots:
            return roots  # 返回root


from Crypto.Util.number import *
N=102371500687797342407596664857291734254917985018214775746292433509077140372871717687125679767929573899320192533126974567980143105445007878861163511159294802350697707435107548927953839625147773016776671583898492755338444338394630801056367836711191009369960379855825277626760709076218114602209903833128735441623
h=56220299912083199824680953877514275031991586299490111910943821482768735249418
PR=PolynomialRing(Zmod(N),'x')
x=PR.gen()
e=112238903025225752449505695131644979150784442753977451850362059850426421356123
from tqdm import *
for i in tqdm_notebook(range(64)): 
    f=(2**6*x*e+i*e+h).monic()
    roots=Small_Roots_Univariate(f,e>>6,0.49,0.0085)
    if(roots):
        print(roots,i)
        break
#[1579733723890583379944346027928995285091232963803321176752930674794829848032] 13

那么我们有：

p=(1579733723890583379944346027928995285091232963803321176752930674794829848032<<6)*e+13*e+h
assert(N%p==0)
q=N//p
print(p)
print(q)
#11347685135451772316799055128658844076558937002070169522376774233969211713689222327103200800438106374510397161974671925195478541934100406041896292545674921
#9021355410009950348639875237199118006505512170606972234278412660410503971242219008091386834585426483874880261151641622040094401795529954768919085685089663

$n$ 分解成功了，那么答案也就出来了。。。

看一眼题目：

from sage.all import *
from Crypto.Util.number import *
from hashlib import md5

class RSA():
    def __init__(self, nbits):
        self.nbits = nbits
        self.p, self.q = self.getPrimes()
        self.n = self.p*self.q
        self.Gift = self.Gift()
        self.priv, self.pub = self.keyGen()
        
    
    def getPrimes(self):
        nbits = self.nbits
        p = random_prime(2^(nbits-1),lbound=2^(nbits-2))
        q = random_prime(2^(nbits-1),lbound=2^(nbits-2))
        while p == q:
            q = random_prime(2^(nbits-1),lbound=2^(nbits-2))
        return p,q
    
    def Gift(self):
        p,q = self.p, self.q
        return (p^2 + p + 1)*(q^2 + q + 1)
    
    def keyGen(self):
        nbits = self.nbits
        while True:
            d = randint(2^(nbits//4),2^(nbits//2))
            if gcd(d,self.Gift) != 1:
                d = randint(2^(nbits//4),2^(nbits//2))
            e = pow(d,-1,self.phi)
            return (self.p,self.q,self.n,e,d),(self.n,e)
RRR = RSA(512)
bp = long_to_bytes(int(RRR.p))
FLAG = 'SCTF{'+md5(bp).hexdigest()+'}'
print(f'N = {RRR.n}')
print(f'e = {RRR.pub[1]}')

题目给出了 $n,e$，以及 $ed\equiv 1 \pmod g $ 和 $g=(p^2+p+1)(q^2+q+1)$ 的条件，然后条件是分解 $n$。这里有 $g\sim n^2$，且 $d<n^{1/2}$，也就是 $d<g^{1/4}$。

这个条件和wiener attack类似，那个是 $e/n$ 可以精确覆盖 $k/d$，这个可以猜测是 $e/n^2$ 里面有玄机，因此可以盲猜：
$$
ed-1=kg
$$
然后用Sage中的连分数展开就OK了：

n = 32261421478213846055712670966502489204755328170115455046538351164751104619671102517649635534043658087736634695616391757439732095084483689790126957681118278054587893972547230081514687941476504846573346232349396528794022902849402462140720882761797608629678538971832857107919821058604542569600500431547986211951
e = 334450817132213889699916301332076676907807495738301743367532551341259554597455532787632746522806063413194057583998858669641413549469205803510032623432057274574904024415310727712701532706683404590321555542304471243731711502894688623443411522742837178384157350652336133957839779184278283984964616921311020965540513988059163842300284809747927188585982778365798558959611785248767075169464495691092816641600277394649073668575637386621433598176627864284154484501969887686377152288296838258930293614942020655916701799531971307171423974651394156780269830631029915305188230547099840604668445612429756706738202411074392821840
cf=continued_fraction(e/n**2)
for i in range(4,20000):
    k,d=cf.numerator(i),cf.denominator(i)
    if(e*d%k==1):
        print(d)
        break
g=(e*d-1)//k
print(g)

求出了 $g$ 还要求 $n$ 的分解。我们可以先对 $g$ 的表达式进行展开：
$$
g=p^2q^2+p^2q+pq^2+pq+p^2+q^2+p+q+1
$$
然后代入 $n=pq$：
$$
g=n^2+n(p+q)+n+p^2+q^2+(p+q)+1
$$
这个在外面的 $p^2+q^2$ ，可以化成 $(p+q)^2-2n$，得到最终表达式：
$$
g=n^2-n+n(p+q)+(p+q)^2+(p+q)+1
$$
令 $x=p+q$：
$$
0=x^2+(n+1)x+n^2-n+1-g
$$

直接放sage中解出 $p+q$ （负值舍去）。

solve(x**2+(n+1)*x+n**2-n-g+1,x)
"""
output:
[
x == -32261421478213846055712670966502489204755328170115455046538351164751104619671102517649635534043658087736634695616391757439732095084483689790126957681118289429943388851693149399740590663288610471650910670306567179355758613300549681123982851259417107072281489085039743066732289373012356978449638761920384845504,
x == 11375355494879145919318225902721812105625077564437957170650561735710451147218983261968497619498442602950113206885958812468314407814408849138330372398633552
]
"""

然后有了 $p+q$，就可以有 $p,q$ 了

s=11375355494879145919318225902721812105625077564437957170650561735710451147218983261968497619498442602950113206885958812468314407814408849138330372398633552
solve(x**2-s*x+n,x)
"""
[x == 5984758006806378809956519900535567746479053908385004504598524889746027259134602871258417614666511624425382102292754198444334667792470478919346145707972191, x == 5390597488072767109361706002186244359146023656052952666052036845964423888084380390710080004831930978524731104593204614023979740021938370218984226690661361]
"""

测一下：

p=5984758006806378809956519900535567746479053908385004504598524889746027259134602871258417614666511624425382102292754198444334667792470478919346145707972191
q=5390597488072767109361706002186244359146023656052952666052036845964423888084380390710080004831930978524731104593204614023979740021938370218984226690661361
n%p,n%q
#(0,0)

总结：感觉这个题，用wiener attack的思路，确实不好想，得注意到 $e/n^2$ 的连分数展开（为啥一个个的注意力都那么集中！可恶！）。

4.[SCTF2024] 不完全阻塞干扰

先看看题目：

# The ship crashed into the sun, causing a massive magnetic storm
#part of script
msg = bytes_to_long(FLAG)
n = p^5*q^2
phi = p^4*(p-1)*q*(q-1)
e = 65537
d = inverse(d,phi)
c = pow(m,e,n)
print(c)

除了这个代码之外，题目还给出了一个pem文件，这个pem文件的末尾是一堆 A。。。

然后来手撕一下，参考这里：手撕PEM密钥（RSA） | Tover’s Blog

3082 #begin sequence 82表示附加2字节长度
0815 #len=0x0815

0282 #n: 02:整数开始标志，82:8表示附加，2表示2字节
0380 #长度:0x380字节
067f0aa4e974a63a1ffe8d5c23e5d3c431653ae41cc746f305f62a9f193f22486cb7ef1b275634818f46d0752a5139e19918271fa0d7d27bc660d2b72414d08ea52c8837f949c7baecc3029ba31727ef3bf120d9926c02d7412f187e98dc56dd07b987d2cc191ad56164a144f28b2f70a15d105588a4f27fbb2891fc527bd6890a5f795b5c48476a6bf9dfb67b7e1ebc7b1b086cd28b58c68955bfdf44ecce11ffacdf654551b159b7832040cc28ee8ebea48f8672d53e3de88fcfbb5fb276b503880dd34d5993335ddf8ccb96c1b4d79f502d72104765ad9c2b1858a17af3d5be44fa3cbf4b8eeb942aa3942a3871d2c65ac70289123fc2e9f9b25cbfcbd7841096060fa504c3a07b591493c64c88d0bb45285a85b5f7d59db98faa00c2cd3fbb63da599205f1cab0df52cf7b431a0ee4a7e35696546ce9d03ef595ecee92d2142c92e97d2744939703455b4c70dec27c321ec6b83c029622e83a9e0d55d0b258d95d4e61291865dda76dc619fce9577990429c6e77e9d40781e3b2f449701b83e8b0c6c66eb380f96473e5d422efee8b2b0e88b716b00a79c9d514ca3ad9d2dee526609ff9541732a4198d11b9dbfbb2e55c24d80ea522d0786e3355f23606a5d38a72de4eefc8b6bfc482248a2862cb69d8e0e3d316597da9d80828be85054faf15fc369caacafb815c6973c171940683d56a1a1967b09b7ffa3fbe5b2e08699759d84d71603f516447696bb27322a69f39f6ca253e00dc9555d5f97328070c467f3663cc489aad130f28c42f35bf88c571920ab92acb8f75d03e35a75103c5bd96f061c96bd02af6e1d191b0dd164bc721377003edbf5d3ef65a5e9046385356b521623bee37f164850a0a7afb0ed4e7e8bd9afe1298f7d532bc9ad941812d332aece75d1cccb1ff69fd42b31f248ae579d9e0d6a14b0546e784ba940e32bd01c395df8ff4584040462b5479fa07336d503dc332e70fc06d9463297fc042b623d56f87efaa525a9b580e314d90d1211893ed407a26508deaa0a13c9ee8c902b9e1c3a02fe9a51452c02ee7bdcc85c0eff63891e24703bd265d9c9dbf456e2af9409538bce0fecc7ebab20266aaab06c766c3ea6cda9cb9ba5e1d024b7dc3d73e76f6a333197bad87c4fb34d565a0014aac72825e41adcfeadadc87acef40ad84b7c55691abad561be0550ea0a988470c427432acb8feb2b9d2d2598fb2089bb91bbd9cb199e892d36164d8bf3ecd54576a97134047a12da84207485bb4e5
0203 #e: 02: 整数开始标志 03:整数长度3字节，这里是03表示不附加长度，如果是83表示附加长度字段。
010001 
0282 #d: 02:整数开始标志 82:长度附加2字节
0380 #d: 长度0x380字节
0400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0281 #p: 02: 整数开始标志 81:整数长度附加1字节
81   #整数长度0x81字节
008063d0a21876e5ce1e2101c20015529066ed9976882d1002a29efe0f2fdfcc2743fc9a4b5b651cc97108699eca2fb1f3d93175bae343e7c92e4a41c72d05e57019400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0281 #q: 02: 整数开始标志 81:整数长度附加1字节
81   #整数长度0x81字节
00e4f0fe49f9ae1492c097a0a988fa71876625fe4fce05b0204f1fdf43ec64b4dac699d28e166efdfc7562d19e58c3493d9100365cf2840b46c0f6ee8d964807170ff2c13c4eb8012ecab37862a3900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

于是我们就得到了RSA参数，其中 $n=p^5q^2$，但 $p$ 的低 $502$ 位和 $q$ 的低 $404$ 位被隐藏了，又是一个RSA-HNP问题。

n=0x067f0aa4e974a63a1ffe8d5c23e5d3c431653ae41cc746f305f62a9f193f22486cb7ef1b275634818f46d0752a5139e19918271fa0d7d27bc660d2b72414d08ea52c8837f949c7baecc3029ba31727ef3bf120d9926c02d7412f187e98dc56dd07b987d2cc191ad56164a144f28b2f70a15d105588a4f27fbb2891fc527bd6890a5f795b5c48476a6bf9dfb67b7e1ebc7b1b086cd28b58c68955bfdf44ecce11ffacdf654551b159b7832040cc28ee8ebea48f8672d53e3de88fcfbb5fb276b503880dd34d5993335ddf8ccb96c1b4d79f502d72104765ad9c2b1858a17af3d5be44fa3cbf4b8eeb942aa3942a3871d2c65ac70289123fc2e9f9b25cbfcbd7841096060fa504c3a07b591493c64c88d0bb45285a85b5f7d59db98faa00c2cd3fbb63da599205f1cab0df52cf7b431a0ee4a7e35696546ce9d03ef595ecee92d2142c92e97d2744939703455b4c70dec27c321ec6b83c029622e83a9e0d55d0b258d95d4e61291865dda76dc619fce9577990429c6e77e9d40781e3b2f449701b83e8b0c6c66eb380f96473e5d422efee8b2b0e88b716b00a79c9d514ca3ad9d2dee526609ff9541732a4198d11b9dbfbb2e55c24d80ea522d0786e3355f23606a5d38a72de4eefc8b6bfc482248a2862cb69d8e0e3d316597da9d80828be85054faf15fc369caacafb815c6973c171940683d56a1a1967b09b7ffa3fbe5b2e08699759d84d71603f516447696bb27322a69f39f6ca253e00dc9555d5f97328070c467f3663cc489aad130f28c42f35bf88c571920ab92acb8f75d03e35a75103c5bd96f061c96bd02af6e1d191b0dd164bc721377003edbf5d3ef65a5e9046385356b521623bee37f164850a0a7afb0ed4e7e8bd9afe1298f7d532bc9ad941812d332aece75d1cccb1ff69fd42b31f248ae579d9e0d6a14b0546e784ba940e32bd01c395df8ff4584040462b5479fa07336d503dc332e70fc06d9463297fc042b623d56f87efaa525a9b580e314d90d1211893ed407a26508deaa0a13c9ee8c902b9e1c3a02fe9a51452c02ee7bdcc85c0eff63891e24703bd265d9c9dbf456e2af9409538bce0fecc7ebab20266aaab06c766c3ea6cda9cb9ba5e1d024b7dc3d73e76f6a333197bad87c4fb34d565a0014aac72825e41adcfeadadc87acef40ad84b7c55691abad561be0550ea0a988470c427432acb8feb2b9d2d2598fb2089bb91bbd9cb199e892d36164d8bf3ecd54576a97134047a12da84207485bb4e5
e=0x10001
p=0x008063d0a21876e5ce1e2101c20015529066ed9976882d1002a29efe0f2fdfcc2743fc9a4b5b651cc97108699eca2fb1f3d93175bae343e7c92e4a41c72d05e57019400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
q=0x00e4f0fe49f9ae1492c097a0a988fa71876625fe4fce05b0204f1fdf43ec64b4dac699d28e166efdfc7562d19e58c3493d9100365cf2840b46c0f6ee8d964807170ff2c13c4eb8012ecab37862a3900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

用第二题的Flatter解决：

from Crypto.Util.number import *
N=from Crypto.Util.number import *
N=0x067f0aa4e974a63a1ffe8d5c23e5d3c431653ae41cc746f305f62a9f193f22486cb7ef1b275634818f46d0752a5139e19918271fa0d7d27bc660d2b72414d08ea52c8837f949c7baecc3029ba31727ef3bf120d9926c02d7412f187e98dc56dd07b987d2cc191ad56164a144f28b2f70a15d105588a4f27fbb2891fc527bd6890a5f795b5c48476a6bf9dfb67b7e1ebc7b1b086cd28b58c68955bfdf44ecce11ffacdf654551b159b7832040cc28ee8ebea48f8672d53e3de88fcfbb5fb276b503880dd34d5993335ddf8ccb96c1b4d79f502d72104765ad9c2b1858a17af3d5be44fa3cbf4b8eeb942aa3942a3871d2c65ac70289123fc2e9f9b25cbfcbd7841096060fa504c3a07b591493c64c88d0bb45285a85b5f7d59db98faa00c2cd3fbb63da599205f1cab0df52cf7b431a0ee4a7e35696546ce9d03ef595ecee92d2142c92e97d2744939703455b4c70dec27c321ec6b83c029622e83a9e0d55d0b258d95d4e61291865dda76dc619fce9577990429c6e77e9d40781e3b2f449701b83e8b0c6c66eb380f96473e5d422efee8b2b0e88b716b00a79c9d514ca3ad9d2dee526609ff9541732a4198d11b9dbfbb2e55c24d80ea522d0786e3355f23606a5d38a72de4eefc8b6bfc482248a2862cb69d8e0e3d316597da9d80828be85054faf15fc369caacafb815c6973c171940683d56a1a1967b09b7ffa3fbe5b2e08699759d84d71603f516447696bb27322a69f39f6ca253e00dc9555d5f97328070c467f3663cc489aad130f28c42f35bf88c571920ab92acb8f75d03e35a75103c5bd96f061c96bd02af6e1d191b0dd164bc721377003edbf5d3ef65a5e9046385356b521623bee37f164850a0a7afb0ed4e7e8bd9afe1298f7d532bc9ad941812d332aece75d1cccb1ff69fd42b31f248ae579d9e0d6a14b0546e784ba940e32bd01c395df8ff4584040462b5479fa07336d503dc332e70fc06d9463297fc042b623d56f87efaa525a9b580e314d90d1211893ed407a26508deaa0a13c9ee8c902b9e1c3a02fe9a51452c02ee7bdcc85c0eff63891e24703bd265d9c9dbf456e2af9409538bce0fecc7ebab20266aaab06c766c3ea6cda9cb9ba5e1d024b7dc3d73e76f6a333197bad87c4fb34d565a0014aac72825e41adcfeadadc87acef40ad84b7c55691abad561be0550ea0a988470c427432acb8feb2b9d2d2598fb2089bb91bbd9cb199e892d36164d8bf3ecd54576a97134047a12da84207485bb4e5
h=0x008063d0a21876e5ce1e2101c20015529066ed9976882d1002a29efe0f2fdfcc2743fc9a4b5b651cc97108699eca2fb1f3d93175bae343e7c92e4a41c72d05e57019400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
PR=PolynomialRing(Zmod(N),'x')
x=PR.gen()
f=(h+x)**5
roots=Small_Roots_Univariate(f,2**503,0.4,0.007)
print(roots)
h=0x008063d0a21876e5ce1e2101c20015529066ed9976882d1002a29efe0f2fdfcc2743fc9a4b5b651cc97108699eca2fb1f3d93175bae343e7c92e4a41c72d05e57019400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
PR=PolynomialRing(Zmod(N),'x')
x=PR.gen()
f=(h+x)**5
roots=Small_Roots_Univariate(f,2**503,0.4,0.007)
print(roots)
#6708022338172260347899030626323676022100749598842650911015897443511894444627151436951734224984454180375617062494685670914830207366629067809127120853621

最后就可以得到flag了：

#上面是调用flatter的内容
p=h+roots
q=(N//Integer(p**5)).nth_root(2)
c=145554802564989933772666853449758467748433820771006616874558211691441588216921262672588167631397770260815821197485462873358280668164496459053150659240485200305314288108259163251006446515109018138298662011636423264380170119025895000021651886702521266669653335874489612060473962259596489445807308673497717101487224092493721535129391781431853820808463529747944795809850314965769365750993208968116864575686200409653590102945619744853690854644813177444995458528447525184291487005845375945194236352007426925987404637468097524735905540030962884807790630389799495153548300450435815577962308635103143187386444035094151992129110267595908492217520416633466787688326809639286703608138336958958449724993250735997663382433125872982238289419769011271925043792124263306262445811864346081207309546599603914842331643196984128658943528999381048833301951569809038023921101787071345517702911344900151843968213911899353962451480195808768038035044446206153179737023140055693141790385662942050774439391111437140968754546526191031278186881116757268998843581015398070043778631790328583529667194481319953424389090869226474999123124532354330671462280959215310810005231660418399403337476289138527331553267291013945347058144254374287422377547369897793812634181778309679601143245890494670013019155942690562552431527149178906855998534415120428884098317318129659099377634006938812654262148522236268027388683027513663867042278407716812565374141362015467076472409873946275500942547114202939578755575249750674734066843408758067001891408572444119999801055605577737379889503505649865554353749621313679734666376467890526136184241450593948838055612677564667946098308716892133196862716086041690426537245252116765796203427832657608512488619438752378624483485364908432609100523022628791451171084583484294929190998796485805496852608557456380717623462846198636093701726099310737244471075079541022111303662778829695340275795782631315412134758717966727565043332335558077486037869874106819581519353856396937832498623662166446395755447101393825864584024239951058366713573567250863658531585064635727070458886746791722270803893438211751165831616861912569513431821959562450032831904268205845224077709362068478
phi = p**4*(p-1)*q*(q-1)
from Crypto.Util.number import *
d=inverse(0x10001,Integer(phi))
long_to_bytes(pow(c,d,N))
#SCTF{0ne_4rgum3nt_1s_r0tt3n_0r4ng3s,_th3_wh0le_cert1fic4t3_1s_r0tt3n_0r4ng3s:XD}

感觉这个题，不好搞的就是手撕pem。。。

5.[SUCTF2025] ez_Hash

5x01 看题

from Crypto.Util.number import *

flag = b'SUCTF{??????????????????????????????}'

class myhash:
    def __init__(self,n):
        self.g = 91289086035117540959154051117940771730039965839291520308840839624996039016929
        self.n = n

    def update(self,msg: bytes):
        for i in range(len(msg)):
            self.n = self.g * (2 * self.n + msg[i])
            self.n = self.n & ((1 << 383) - 1)

    def digest(self) -> bytes:
        return ((self.n - 0xd1ef3ad53f187cc5488d19045) % (1 << 128)).to_bytes(16,"big")

def xor(x, y):
    x = b'\x00'*(16-len(x)) + x
    y = b'\x00'*(16-len(y)) + y
    return long_to_bytes(bytes_to_long(bytes([a ^ b for a, b in zip(x, y)])))

def fn(msg, n0):
    h = myhash(n0)
    ret = bytes([0] * 16)
    for b in msg:
        h.update(bytes([b]))
        ret = xor(ret,h.digest())
    return ret

n0 = getRandomNBitInteger(382)
print("n0 = ",n0)
your_input = bytes.fromhex(input("give me your msg ->").strip())
if fn(your_input, n0) == b'justjusthashhash':
    print(flag)
else:
    print("try again?")

题目先给出了 myhash 类，其表达式为 $n_{i+1}=g(2n_{i}+m_i)$。然后取digest的时候，是对 $n-B$ 的 long_to_bytes 的值。最终的hash结果为每一步 digest 的异或和。

5x02 初步思路(1.13 3pm)

推式子（以长度为 3 的字符串为例）
$$
n_3=2^3g^3n_0+2^2g^3m_0+2^1g^2m_1+gm_2
$$
注意到模数是 $2^{128}$，并且每个元素都会被乘上一个 $2g$，说明每个元素对最终结果的影响是有限的，测一下：

print(fn(b'1'*10000,666).hex())
print(fn(b'1'*12000,666).hex())
#fd31a968bcce1f25079b64f099e1c72e
#fd31a968bcce1f25079b64f099e1c72e

测一下x2：

print(fn(b'1'*1000,666).hex())
print(fn(b'1'*1001,666).hex())
print(fn(b'1'*1002,666).hex())
print(fn(b'1'*1003,666).hex())
#fd31a968bcce1f25079b64f099e1c72e
#1ee0d0ff837f4f3c0f711066867bc444
#fd31a968bcce1f25079b64f099e1c72e
#1ee0d0ff837f4f3c0f711066867bc444

继续测，果然从 $127$ 开始，结果就收敛了。

for i in range(120,135):
    print(i,fn(b'1'*i,666).hex())
"""
120 4331a968bcce1f25079b64f099e1c72e
121 bae0d0ff837f4f3c0f711066867bc444
122 3531a968bcce1f25079b64f099e1c72e
123 0ee0d0ff837f4f3c0f711066867bc444
124 9d31a968bcce1f25079b64f099e1c72e
125 dee0d0ff837f4f3c0f711066867bc444
126 7d31a968bcce1f25079b64f099e1c72e
127 1ee0d0ff837f4f3c0f711066867bc444
128 fd31a968bcce1f25079b64f099e1c72e
129 1ee0d0ff837f4f3c0f711066867bc444
130 fd31a968bcce1f25079b64f099e1c72e
131 1ee0d0ff837f4f3c0f711066867bc444
132 fd31a968bcce1f25079b64f099e1c72e
133 1ee0d0ff837f4f3c0f711066867bc444
134 fd31a968bcce1f25079b64f099e1c72e
"""

然后呢？搞比特追踪吗，感觉，不太行的样子？因为这里是每一步的异或，前面字符到了最后才不再影响后面字符的。把上面的 $\mathtt{31H}$ 字符换成 $\mathtt{00H}$ 字符，解出来的本质也是一样的吧，基本上到了后期，就是两个值的跳跃，只是式子更加简化了：
$$
n_{128}=0
$$

加一组调试验证一下：

def fn(msg, n0):
    h = myhash(n0)
    ret = bytes([0] * 16)
    for b in msg:
        h.update(bytes([b]))
        print('{:032x}'.format(h.n%(2**128)),end=',')
        ret = xor(ret,h.digest())
    return ret
fn(b'\x00'*128,666).hex()

然后就被卡住了。。

5x03 瞄一眼wp发现没想到的点！

结果看了鸡块的博客，发现自己前面的思路，竟然是对的。。。但下面这一步自己没注意到，来学习一下思路！

REF：2025-SUCTF-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

所以完全可以在0-255之间随便选128个值，然后分别给他们都加上b"\x00"*128的后缀，然后看作128个不同的整体去解线性方程组就可以了。

Why？

重新分析一下刚才做的实验：如果总是输入仅包含一个字符 $C$ 的字符串，那么到最后， $n$ 的值一定会收敛于一个固定值为
$$
n_{∞}=C\sum_{i=0}^{127} 2^{i}g^{i+1} \pmod {2^{128}}
$$
如果 $C=0$，那么这个值是 $0$，如果 $C\not =0$，那么这个值也固定，并且这个值，和 $n_0$ 无关。

而为何会收敛到两个值，是因为每次异或的内容为 $n_{∞}$。由于 $n_{∞}$ 收敛，因此 $n_{∞}-B$ 也收敛，也就是相当于到后期，每次在前一次的基础上，异或一个固定值。一个数不停地异或一个固定值，得到的结果当然是这个数在两个值上反复横跳了 :)。

但，由于是累积异或，$n_0$ 会在前面发挥作用，所以最终结果仍然会受到 $n_0$ 影响和前面的字符影响。

print(fn(b'1'*190,666).hex())
print(fn(b'2'+b'1'*189,666).hex())
#fd31a968bcce1f25079b64f099e1c72e
#bb6d4e71bbc7ac8e1240f6b96b0dddcd

既然这样，就可以得到下面的步骤：

消除 $n_0$ 影响，在最前面填 $128$ 个 $\mathtt{00H}$ 字节，使得系统中 $h.n$ 的值总是 $0$。
构造 $128$ 个前缀不同，后缀为 $128$ 个 $\mathtt{00H}$ 的字符串 $m_1\sim m_{128}$，计算 $f_n(m_i,0)$，这 $128$ 个结果大概率线性无关。
既然最后结果是 $128$ 个线性无关的结果，最后hash也是 $128$ 位，那一定存在一种组合，使得这些 hash 的自由组合可以得到目标值。并且这个是组合，不是排列，也就是，除了最前面 $128$ 个 $\mathtt{00H}$ 外，假设解出来 $m_1,m_2,m_3$ 可以组合成目标值，那么 $m_3,m_1,m_2$ 也可以组合成目标值。（证明见后面）

那么我们继续分析：

既然一开始是 $128$ 个 $\mathtt{00H}$ 字节，那么最终我们会得到 $f_n(\mathtt{00H}\times128,n_0)$ 的结果为初值 $A$，此时处理后， $h.n$ 的值为 $0$。而我们需要的目标值为 $T$，那么最终的变化量就是 $A\oplus T$，将 $A\oplus T$ 单比特构造一个向量 $\vec y$。
然后，我们计算$128$ 个线性无关的 $f_n(m_i,0)$ 的值，每一行按单比特，构建一个矩阵 $M$。
既然最终结果是 $n$ 个线性无关的 $f_n(m_i,0)$ 组合的结果，那么就可以得到：

$$
\vec y=\bigoplus_{i=0}^{127} b_i f_n(m_i,0)
$$

那么我们解 $b_i$ 就是了，如果 $b_i$ 为 $1$，那么我们就异或上 $f_n(m_i,0)$。

Correctness Proof：这样做的正确性就在于，由于 $m_i$ 后面跟了一大堆 $00$，那么当一组 $f_n(m_i,0)$ 做完之后，下一组开始前，$h.n$ 的结果仍然是 $0$，因此可以直接开始异或下一组的 $f_n(m_{i+1},0)$。并且异或具有交换律，因此，只要对应的 $b_i$ 是 $1$，那么除了必须以 $128$ 个 $\mathtt{00H}$ 开头的要求外，实际异或顺序无所谓！

测试代码：

#python 3.12.1
from Crypto.Util.number import *
from os import urandom
from random import *
from sage.all import *
flag = b'SUCTF{??????????????????????????????}'

class myhash:
    def __init__(self,n):
        self.g = 91289086035117540959154051117940771730039965839291520308840839624996039016929
        self.n = n

    def update(self,msg: bytes):
        for i in range(len(msg)):
            self.n = self.g * (2 * self.n + msg[i])
            self.n = self.n & ((1 << 383) - 1)

    def digest(self) -> bytes:
        return ((self.n - 0xd1ef3ad53f187cc5488d19045) % (1 << 128)).to_bytes(16,"big")

def xor(x, y):
    x = b'\x00'*(16-len(x)) + x
    y = b'\x00'*(16-len(y)) + y
    return long_to_bytes(bytes_to_long(bytes([a ^ b for a, b in zip(x, y)])))

def fn(msg, n0):
    h = myhash(n0)
    ret = bytes([0] * 16)
    for b in msg:
        h.update(bytes([b]))
        #print('{:032x}'.format(h.n%(2**128)),end=',')
        ret = xor(ret,h.digest())
    return ret

n0=getrandbits(128)
print('n0={:032x}'.format(n0))
msgarr=[bytes([1+i]+[0]*128) for i in range(128)]
resarr=[bytes_to_long(fn(msg1,0)) for msg1 in msgarr]
M=[[bool(i&(1<<j)) for j in range(128)]for i in resarr]
val0=bytes_to_long(fn(bytes(128),n0))
target=bytes_to_long(b'justjusthashhash')
target=val0^target
y=[bool((target)&(1<<i)) for i in range(128)]
M=matrix(GF(2),M)
y=vector(GF(2),y)
ans=M.solve_left(y)
msga=bytes(128)
for i in range(len(ans)):
    if(ans[i]):
        msga+=bytes([1+i]+[0]*128)
print(fn(msga,n0)) #b'justjusthashhash'
print(len(msga)*2) #16000+

5x04 和之前的fnv关联？

你不觉得，这个 $16000+$ 的长度，有点太长了吗，万一题目限制了长度呢？能不能考虑用SUSCTF那个的LLL做来攻击呢？

那个myhash，不就是fnv吗，能不能从这里入手呢？

赛后和星盟的 DexterJie 师傅交流了一下，发现可以正常做，参考了星盟的WP，感觉那个代码写得有点繁琐了，我理了理思路，算是彻底搞懂了这个题：

参考：SUCTF2024 Writeup - 星盟安全团队 (xmcve.com)

我们考察hash碰撞（以三位为例）
$$
2^3g^3n+2^2g^3m_0+2^1g^2m_1+gm_2\equiv 2^3g^3n+2^2g^3r_0+2^1g^2r_1+gr_2 \pmod {2^{128}}
$$
可消去 $2^3g^3n$ 项：
$$
2^2g^3\delta_0+2^1g^2\delta_1+g\delta_2\equiv 0\pmod{2^{128}}
$$
显然，$\delta $ 很小，可以构造这个矩阵去求解，甚至最后扩张系数 $K=1$ 也能求！

为了方便调试，给他增加了一个函数，返回两个值：一个是 ret 的数值，还有一个是 $h.n$ 内部的值。

def fnTest(msg, n0):
    h = myhash(n0)
    ret = bytes([0] * 16)
    for b in msg:
        h.update(bytes([b]))
        d = h.digest()
        ret = xor(ret, d)
    return bytes_to_long(ret),h.n%(2**128)

测一下，最后两个 $h.n$ 的状态果然一样。

n0=0xf3ad24a59d00d329a56273d2154d51f3
g=60836803250181415307496727382007595489
n=64
M=[[i==j for j in range(n+1)]for i in range(n+1)]
M[-1][-1]=2**128
for i in range(n):
    M[i][-1]=2**(n-i)*Integer(pow(g,n-i,2**128))%(2**128)
M=matrix(ZZ,M)#*diagonal_matrix([1]*(n+1)+[2**2000])
M3L=M.LLL()
for v in M3L:
    if(v[-1]==0):
        break
s1=[110]*64
s2=[110+v[i] for i in range(64)]
print(bytes(s1))
print(bytes(s2))
d1,h1=fnTest(bytes(s1),n0)
print(d1.hex(),h1%(2**128))
d2,h2=fnTest(bytes(s2),n0)
print(d2.hex(),h2%(2**128))
"""
b'nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn'
b'kooopjknnmoomnnoopklnmnmhnlronpqnmlnmopnnnnnnnnnnnnnnnnnnnnnnnnn'
af3bb53e332f1723690e9b8631f69e76 228056009380557728235158378943134817746
188ae78e8e8cf3752e5b3a3493c21909 228056009380557728235158378943134817746
"""

那如何去找 $128$ 组，使这 $128$ 组均做到线性无关呢？当然是两个方法：一是改变长度，二是同一长度下多保存几组数据。。。并且，你会发现，我保存下来的数据，是与初值无关的！

根据上面构造的格和实验结果，先给他封装一下：

def CheckVec(v):
    s1=[80]*(len(v)-1)
    s2=[80+v[i] for i in range(len(v)-1)]
    for _ in range(25):
        tmp=getrandbits(128)
        if(fnTest(bytes(s1),tmp)[1]!=fnTest(bytes(s2),tmp)[1]):
            return False
    return True
def getcollision(n):
    g=60836803250181415307496727382007595489
    M=[[i==j for j in range(n+1)]for i in range(n+1)]
    M[-1][-1]=2**128
    for i in range(n):
        M[i][-1]=2**(n-i)*Integer(pow(g,n-i,2**128))%(2**128)
    M=matrix(ZZ,M)
    M3L=M.LLL()
    vec=[]
    for v in M3L:
        if(v[-1]==0):
            vec.append(v)
    ret=[]
    for v in vec:
        if(CheckVec(v)):
            ret.append(v[:-1])
    return ret

由于上面的代码显示：我们可以构造hash结果不同，但操作后 $h.n$ 的结果相同的两个字符串 $s,t$，并利用这些性质：

每次操作后，$h.n$ 的结果相同，说明这一步，无论是对 $s$ 操作还是对 $t$ 操作，都不会影响对下一字符串 $r$ 的操作。因为对下一字符串 $r$ 的操作等价于 $f_n(r,h.n’)$，其中 $h.n’$ 是这一步操作后的 $h.n$ 的值。
由于 $s$ 和 $t$ 的操作结果不同，因此这一步里 $d=f_n(s)\oplus f_n(t)$ 不为 $0$。
我们假设最后我们的目标为 $T$，然后我们计算 $D=f_n(S,n_0)$ ，其中 $S$ 为所有 $s_i$ 按顺序连接的结果。那么我们最终就可以根据 $128$ 个不同的 $d$ 去组合 $T\oplus D$ 的值，回到了解方程上面去

本地测试代码：

#python 3.12.1
from random import *
from Crypto.Util.number import *
from sage.all import *
#------原题文件-------#
class myhash:
    def __init__(self, n):
        self.g = 91289086035117540959154051117940771730039965839291520308840839624996039016929
        self.n = n

    def update(self, msg: bytes):
        for i in range(len(msg)):
            self.n = self.g * (2 * self.n + msg[i])
            self.n = self.n & ((1 << 383) - 1)

    def digest(self) -> bytes:
        return int((self.n - 0xd1ef3ad53f187cc5488d19045) % (1 << 128)).to_bytes(16, "big")
        
def xor(x, y):
    x = b'\x00' * (16 - len(x)) + x
    y = b'\x00' * (16 - len(y)) + y
    return long_to_bytes(bytes_to_long(bytes([a ^ b for a, b in zip(x, y)])))

def fn(msg, n0):
    h = myhash(n0)
    ret = bytes([0] * 16)
    for b in msg:
        h.update(bytes([b]))
        d = h.digest()
        ret = xor(ret, d)
    return ret
#------测试函数-------#
def fnTest(msg, n0):
    h = myhash(n0)
    ret = bytes([0] * 16)
    for b in msg:
        h.update(bytes([b]))
        d = h.digest()
        ret = xor(ret, d)
    return bytes_to_long(ret),h.n%(2**128)
#------寻找碰撞-------#
def CheckVec(v):  #检查是否满足Test通过
    s1=[80]*(len(v)-1)
    s2=[80+v[i] for i in range(len(v)-1)]
    for _ in range(25):
        tmp=getrandbits(128)
        if(fnTest(bytes(s1),tmp)[1]!=fnTest(bytes(s2),tmp)[1]):
            return False
    return True
def getcollision(n):
    g=60836803250181415307496727382007595489
    M=[[i==j for j in range(n+1)]for i in range(n+1)]
    M[-1][-1]=2**128
    for i in range(n):
        M[i][-1]=2**(n-i)*Integer(pow(g,n-i,2**128))%(2**128)
    M=matrix(ZZ,M)
    M3L=M.LLL()
    vec=[]
    for v in M3L:
        if(v[-1]==0):
            vec.append(v)
    #return vec
    ret=[]
    for v in vec:
        if(CheckVec(v)):
            ret.append(v[:-1])
    return ret
#------产生测试数据-------#
s=[]
lens=35
while(len(s)<128):
    s+=getcollision(lens)
    lens+=1
s=s[:128]
n0=getrandbits(128)
print('0x{:032x}'.format(n0))
#------寻找128组碰撞并构建随机字符串-------#
msG,msH=[],[]s
Gall=b''
def myRandString(lens):
    ret=''
    Table=('456GHIJKLMNOPQRSTghijklmnopqrst')
    for i in range(lens):
        ret+=choice(Table)
    return ret
for i in range(128):
    v=s[i]
    si=myRandString(len(v)).encode()
    msG.append(si)
    Gall+=si
    msH.append(bytes([si[i]+v[i] for i in range(len(v))]))

#------计算全G的hash结果，并和目标异或得到差分值-------#
HashGall=bytes_to_long(fn(Gall,n0))
D=bytes_to_long(b'justjusthashhash')
D=D^HashGall
diffGH=[]
curstat=n0
#------构建每一步g和h的差分-------#
for i in range(128):
    tG,tH=msG[i],msH[i]
    tgf,nxtstat,thf,nxtstatChk=fnTest(tG,curstat)+fnTest(tH,curstat)
    assert nxtstat==nxtstatChk
    diffGH.append(tgf^thf)
    curstat=nxtstat
#------构建矩阵求解方程，判断每一步异或msg还是异或msh-------#
M=[[bool(diffGH[i]&(1<<j)) for j in range(128)]for i in range(128)]
y=[bool(D&(1<<j)) for j in range(128)]
M=Matrix(GF(2),M)
y=vector(GF(2),y)
ans=M.solve_left(y)
#------构造最后字符串-------#
finalMsg=b''
for i in range(128):
    if(ans[i]):
        finalMsg+=msH[i]
    else:
        finalMsg+=msG[i]
print(fn(finalMsg,n0))
print(len(finalMsg))
print(finalMsg)
#可能的输出结果：
#n0=0x0c4db02b41aa032cf28ac84dc7908f1e
#b'justjusthashhash'
#5432
#均为可见字符

可以发现，由于每次LLL后的值很小，因此我最后构建出来的字符串内均为可见字符，且字符串长度也只剩下 $5000$ 位了。官方WP其实也是这个思路，保持每次处理后 $n$ 的状态相同，通过解 $GF(2)$ 上的方程，每次选不同的状态来线性组合成最终结果，这个题，也算是搞懂了，用了我一天:(

9.总结

不知不觉又是 1 月了，4 年，好快。

2021 年的那个寒假，当时确实自己好好打了 1 个月的 CTF，水平提升了很多！那就 2021 Once More，用好这段时间，也许能再来一次水平突破呢！

重新接触了更多的师傅~，后面得多关注关注外面的比赛了，确实能够感觉到，还是打比赛然后打完交流，比直接补题，效果要好多了:)

当然，第 2 题也需要让我注意到以前的一些题目也得带着去复盘一下:)，免得下次看到熟悉的题目又不会

CTFSeason4

#ExpLog

25Jan2

http://example.com/2025/01/15/25Jan2/

作者

huangx607087

发布于

2025年1月15日

许可协议

25Jan1 下一篇

25Jan2

huangx607087 1月的切题2

0.Introduction

1.[SUCTF2025] SU_Signin

2.[SUCTF2025]SU_RSA

3.[SCTF2024] Signin

4.[SCTF2024] 不完全阻塞干扰

5.[SUCTF2025] ez_Hash

5x01 看题

5x02 初步思路(1.13 3pm)

5x03 瞄一眼wp发现没想到的点！

5x04 和之前的fnv关联？

9.总结