2025-SUCTF-wp-crypto

支援了@Zima一道SU_Poly，并且帮忙验了验题+做docker所以没有参赛，不过还是把题目都做了一遍来学习学习。

SU_signin

题目描述：

Just a piece of cake.

题目：

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)

题目基于BLS12-381曲线，先找出上面两个不同的阶为o的点$G_1,G_2$，之后计算：

$$P_1 = \frac{o}{n_1} \cdot G_1$$ $$P_2 = \frac{o}{n_2} \cdot G_2$$

也就是于$P_1,P_2$分别是$n_1,n_2$阶点。

然后对于flag的每一bit，根据是0还是1分别计算出如下点：

$$aG_1 + bP_2$$ $$aP_1 + bG_2$$

由于flag做过padding，所以第一bit的点$K$一定是0，也就是$aG_1 + bP_2$的形式，而由于$P_2$是$n_2$阶点，所以有：

$$n_2K = n_2(aG_1 + bP_2) = n_2a \cdot G_1$$

所以$n_2K$实际上是$G_1$的倍点，这代表他和$P_1$在$n_1$-torsion的同一分支，所以将它与上面两种点分别做配对会得到：

$$e(n_2K, aG_1 + bP_2) = e(n_2K, P_2)^a = e(K, P_2)^{an_2} = e(K, \frac{o}{n_2} \cdot G_2)^{an_2} = e(K, G_2)^{oa} = 1$$ $$e(n_2K, aP_1 + bG_2) = e(n_2K, G_2)^{a} = e(K, G_2)^{an_2}$$

也就是说由于$P_2$是$n_2$阶点，所以$e(K, P_2)$应该是$n_2$次单位根，在乘了$n_2$次之后就会得到1，而第二个则不会，因此可以做出decision。

exp：

from Crypto.Util.number import *

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

points = []

flag = "0"
K = E(points[0])
for i in points[1:]:
    if((n2*K).weil_pairing(E(i), o) == 1):
        flag += "0"
    else:
        flag += "1"
print(long_to_bytes(int(flag, 2)))


#SUCTF{We1come__T0__SUCTF__2025}

直接配对也可以，只需要分步展开，比如直接将第一个点与两种点配对会得到：

$$e(aG_1 + bP_2, cG_1 + dP_2) = e(aG_1, cG_1 + dP_2)\cdot e(bP_2, cG_1 + dP_2) = e(aG_1,dP_2)\cdot e(bP_2, cG_1) = e(aG_1,d\frac{o}{n_2} \cdot G_2) \cdot e(b\frac{o}{n_2} \cdot G_2,c \cdot G_1) = e(G_1, G_2)^{ad\frac{o}{n_2}} \cdot e(G_1, G_2)^{bc\frac{o}{n_2}} = e(G_1, G_2)^{(ad+bc)\frac{o}{n_2}}$$ $$e(aG_1 + bP_2, cP_1 + dG_2) = e(aG_1, cP_1 + dG_2)\cdot e(bP_2, cP_1 + dG_2) = e(aG_1, dG_2) \cdot e(bP_2, cP_1) = e(G_1, G_2)^{ad} \cdot e(G_1, G_2)^{bc\frac{o}{n_1}\frac{o}{n_2}}$$

第一个是$n_2$次单位根而第二个不是，因此可以做出decision。

SU_mathgame

题目描述：

1.95.46.185:10001
1.95.46.185:10006

Let’s play a game!

题目：

import socketserver
import signal
from Crypto.Util.number import *
from random import randint
import time
from sage.geometry.hyperbolic_space.hyperbolic_isometry import moebius_transform
from secret import flag

banner = br'''
 _____ ______   ________  _________  ___  ___          ________  ________  _____ ______   _______      
|\   _ \  _   \|\   __  \|\___   ___\\  \|\  \        |\   ____\|\   __  \|\   _ \  _   \|\  ___ \     
\ \  \\\__\ \  \ \  \|\  \|___ \  \_\ \  \\\  \       \ \  \___|\ \  \|\  \ \  \\\__\ \  \ \   __/|    
 \ \  \\|__| \  \ \   __  \   \ \  \ \ \   __  \       \ \  \  __\ \   __  \ \  \\|__| \  \ \  \_|/__  
  \ \  \    \ \  \ \  \ \  \   \ \  \ \ \  \ \  \       \ \  \|\  \ \  \ \  \ \  \    \ \  \ \  \_|\ \ 
   \ \__\    \ \__\ \__\ \__\   \ \__\ \ \__\ \__\       \ \_______\ \__\ \__\ \__\    \ \__\ \_______\
    \|__|     \|__|\|__|\|__|    \|__|  \|__|\|__|        \|_______|\|__|\|__|\|__|     \|__|\|_______|

'''
welcome = b"\nWelcome to my math game, let's start now!\n"


class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'SERVER <INPUT>: '):
        self.send(prompt, newline=False)
        return self._recvall()

    def game1(self):
        self.send(b"\nLet's play the game1!")
        rounds = 1000
        pseudo_prime = int(self.recv(prompt=b'[+] Plz Tell Me your number: '))
        if isPrime(pseudo_prime):
            self.send(b"\nNo! it's a prime, go away!")
            self.request.close()
        for i in range(rounds):
            if pow(randint(2, pseudo_prime), pseudo_prime - 1, pseudo_prime) != 1:
                self.send(b"\nYou failed in round " + str(i + 1).encode() + b', bye~~')
                self.request.close()
        self.send(b"\nCongratulations, you have won the game1!\n")
        return True

    def game2(self):
        self.send(b"Let's play the game2!")
        res = self.recv(prompt=b'[+] Plz give Me your a, b, c: ')
        a,b,c = [int(x) for x in res.split(b',')]
        try:
            assert (isinstance(a, int) and isinstance(a, int) and isinstance(c, int))
            assert a > 0
            assert b > 0
            assert c > 0
            assert a / (b + c) + b / (a + c) + c / (a + b) == 4
            assert int(a).bit_length() > 900 and int(a).bit_length() < 1000
            assert int(b).bit_length() > 900 and int(b).bit_length() < 1000
            assert int(c).bit_length() > 900 and int(c).bit_length() < 1000
            self.send(b"\nCongratulations, you have won the game2!\n")
            return True
        except:
            self.send(b"\nNo! Game over!")
            self.request.close()

    def final_game(self):
        self.send(b"Let's play the game3!")
        set_random_seed(int(time.time()))
        C = ComplexField(999)
        M = random_matrix(CC, 2, 2)
        Trans = lambda z: moebius_transform(M, z)
        out = []
        for _ in range(3):
            x = C.random_element()
            out.append((x,Trans(x)))
        out = str(out).encode()
        self.send(out)
        kx = C.random_element()
        kx_str = str(kx).encode()
        self.send(kx_str)
        C2 = ComplexField(50)
        ans = C(self.recv(prompt=b'[+] Plz Tell Me your answer: ').decode())
        if C2(ans) == C2(Trans(kx)):
            self.send(b"\nCongratulations, you have won the game3!")
            self.send(flag)
            self.request.close()
        else:
            self.send(b"\nNo! Game over!")
            self.request.close()

    def handle(self):
        signal.alarm(300)
        self.send(banner)
        self.send(welcome)
        step1 = self.game1()
        if not step1:
            self.request.close()
        step2 = self.game2()
        if not step2:
            self.request.close()
        self.final_game()


class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10001
    print("HOST:POST " + HOST+":" + str(PORT))
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

题目分成三个game。

game1

game1要求找到一个伪素数$n$，这个伪素数需要通过1000次费马素性检测，也就是对任意选取的$a$要满足$a^{n-1} = 1 \quad(mod\;n)$。

这实际上就是找一个卡迈克尔数，而由于通过费马素性检测要求$a$与$n$互素，所以要找个大一些的才行。

game2

很经典的钓鱼题，具体原理可以参考：

🍎🍌🍍 | Tover’s Blog

对于本题来说，只需要在迭代过程中加一个900-1000bit的check就可以了。

game3

这个game本身似乎是想考mobius的一个复交比不变性，但是由于@Zima加了个：

set_random_seed(int(time.time()))

所以直接小范围找一下seed然后发回去就可以了。

@Zima说是用socket这个模板的话，fork后的随机数全部是一样的，所以要加个种子才行。但偏偏就加了个能爆的int(time.time())XD

exp：

from Crypto.Util.number import *
from random import getrandbits
from pwn import *

context.log_level = "critical"
sh = remote("1.95.46.185", 10001)
########################################################################## game1
sh.recvuntil(b'[+] Plz Tell Me your number: ')
if(0):
    while(1):
        k = getrandbits(100)
        a = 6 * k + 1
        b = 12 * k + 1
        c = 18 * k + 1
        if isPrime(a) and isPrime(b) and isPrime(c):
            n = a * b * c
            print(n)
            break
n = 782297933841357541176473640284870344877218151900677131070988547902278660193827528728178354969
sh.sendline(str(n).encode())
sh.recvuntil(b"Congratulations, you have won the game1!")


########################################################################## game2
if(0):
    PR.<x, y, z> = QQ[]
    f = (x*(x+z)*(x+y) + y*(y+z)*(y+x) + z*(z+y)*(z+x)) - 4*(x+y)*(x+z)*(y+z)
    tran = EllipticCurve_from_cubic(f, None, True)
    tran_inv = tran.inverse()
    EC = tran.codomain()
    g = EC.gens()[0]
    P = g
    while(1):
        Pinv = tran_inv(P)
        a = Pinv[0].numerator()
        b = Pinv[1].numerator()
        c = Pinv[0].denominator()
        if a>0 and b>0:
            if(int(a).bit_length() > 900 and int(a).bit_length() < 1000 and \
            int(b).bit_length() > 900 and int(b).bit_length() < 1000 and \
            int(c).bit_length() > 900 and int(c).bit_length() < 1000):
                print(a, b, c)
                break
        P = P+g
a, b, c = 1440354387400113353318275132419054375891245413681864837390427511212805748408072838847944629793120889446685643108530381465382074956451566809039119353657601240377236701038904980199109550001860607309184336719930229935342817546146083848277758428344831968440238907935894338978800768226766379, 1054210182683112310528012408530531909717229064191793536540847847817849001214642792626066010344383473173101972948978951703027097154519698536728956323881063669558925110120619283730835864056709609662983759100063333396875182094245046315497525532634764115913236450532733839386139526489824351, 9391500403903773267688655787670246245493629218171544262747638036518222364768797479813561509116827252710188014736501391120827705790025300419608858224262849244058466770043809014864245428958116544162335497194996709759345801074510016208346248254582570123358164225821298549533282498545808644
sh.sendline(str(a).encode() + b"," + str(b).encode() + b"," + str(c).encode())
sh.recvuntil(b"Congratulations, you have won the game2!")


########################################################################## game3
import time
from sage.geometry.hyperbolic_space.hyperbolic_isometry import moebius_transform

sh.recvuntil(b"Let's play the game3!")
sh.recvline()
sh.recvline()
C = ComplexField(999)
KX = sh.recvline().strip().decode()

temp = int(time.time())
for i in range(-10, 10):
    set_random_seed(int(i+temp))
    M = random_matrix(CC, 2, 2)
    Trans = lambda z: moebius_transform(M, z)
    out = []
    for _ in range(3):
        x = C.random_element()
        out.append((x,Trans(x)))
    out = str(out).encode()
    kx = C.random_element()
    kx_str = str(kx).encode()
    C2 = ComplexField(50)
    if(str(kx) == str(KX)):
        break

sh.recvuntil(b'[+] Plz Tell Me your answer: ')
sh.sendline(str(C(Trans(kx))).encode())
sh.recvline()
sh.recvline()
sh.recvline()
print(sh.recvline())


#SUCTF{Hope_Y0u_have_a_NICE_tr1p_in_SUCTF~}

SU_Auth

题目描述：

nc 1.95.46.185 10002
nc 1.95.46.185 10003

open the sυdoor ( ^_^)／

题目：

from Crypto.Cipher import AES
from ast import literal_eval
from hashlib import md5
import subprocess

ells = [*primes(3, 200), 269]
p = 4*prod(ells) - 1
F = GF(p)

SUKEY = [randint(-3, 3) for _ in range(len(ells))]
def SuAuth(A, priv, LIMIT=True):
    if any(priv[i] == SUKEY[i] for i in range(len(ells))) and LIMIT: return "🙅SUKEY"
    E = EllipticCurve(F, [0, A, 0, 1, 0])
    for sgn in [1, -1]:
        for e, ell in zip(priv, ells):
            for i in range(sgn * e):
                while not (P := (p + 1) // ell * E.random_element()) or P.order() != ell:
                    pass
                E = E.isogeny_codomain(P)
        E = E.quadratic_twist()
    return E.montgomery_model().a2()

cipher = lambda key: AES.new(md5(key.encode()).digest(),AES.MODE_ECB)
SUDOOR = cipher(str(SuAuth(0, SUKEY, 0))).encrypt(b"./OPEN_THE_FLAG!")
print("😜", SuAuth(0, SUKEY, 0))

while True:
    AKey = SuAuth(0, literal_eval(input("🔑: ")))
    try: subprocess.run(cipher(str(AKey)).decrypt(SUDOOR))
    except: continue

@hashhash支援@Zima的同源题，题目基于CSIDH，在连接上靶机后会生成一个未知的私钥指数列表，并且用它计算出同源后曲线的a2。

首要任务是要求出私钥来。目前我们对私钥一无所知，虽然知道a2的具体值，但是列表比较长，直接求出私钥不太现实。但是注意到SuAuth里第一行有个对私钥的检测：

if any(priv[i] == SUKEY[i] for i in range(len(ells))) and LIMIT: return "🙅SUKEY"

这个检测的本意看上去是防止直接输入SUKEY，然而他的实际实现用的是any而不是all。也就是说，只要输入的列表中有任意一个和私钥对应值相等，这里就会直接return。而如果所有都不相等的话，他则会计算输入的私钥对应的同源。

虽然说无论怎么输入都没有返回值，但是同源的计算是比较慢的，所以我们能够从交互过程中获得”究竟有没有计算同源“这个信息，相当于有一个时间侧信道的漏洞。所以可以利用any和时间侧信道逐个位置确定下来完整私钥。

确定完整私钥之后，下一个问题就是怎么用任何位置值都不相同的输入列表，去达到和SUKEY完全一样的效果。而CSIDH有一个性质在于，如果用全1的私钥列表，那么最终的效果其实是到了一个4-iso的邻居。

换个角度想，这也就是代表着如果把4-iso也加入私钥列表的话，全1的私钥列表就形成了一个环路，神奇

而测试一下发现4-iso的阶是3，因此只需要在SUKEY的基础上每个值都加3即可。

exp：

from Crypto.Util.number import *
from tqdm import *
from pwn import *
import time

context.log_level = "critical"

ells = [*primes(3, 200), 269]
p = 4*prod(ells) - 1
F = GF(p)

sh = remote("1.95.46.185", 10002)
K = int(sh.recvline().strip().decode()[1:])

sh.recvuntil(b": ")
SUKEY = []
for i in trange(len(ells)):
    for j in range(-3, 3+1):
        temp = [4]*i + [j] + [4]*(len(ells)-i-1)
        sh.sendline(str(temp).encode())
        T1 = time.time()
        sh.recvuntil(b": ")
        T2 = time.time()
        if(T2-T1 < 1):
            SUKEY.append(j)
            break

SUKEY = [i + 3 for i in SUKEY]
sh.sendline(str(SUKEY).encode())
print("Done!")
sh.interactive()


#SUCTF{My_S4fe_CS1DH_Oops!_any?_all!}

SU_Poly

题目描述：

nc 1.95.46.185 10004
nc 1.95.46.185 10005

cyberClier:)

题目：

from Crypto.Util.number import *
from hashlib import md5
from secret import flag
import signal

PR.<x> = PolynomialRing(Zmod(0xfffffffffffffffffffffffffffffffe))
SUPOLY = PR.random_element(10)
gift = []
for i in range(bytes_to_long(b"SU")):
    f = PR.random_element(10)
    gift.append([int((f*SUPOLY)(j)) & 0xff for j in range(10)])
print("🎁 :", gift)

signal.alarm(10)
if(md5(str(SUPOLY.list()).encode()).hexdigest() == input("Show me :)")):
    print("🚩 :", flag)
else:
    print("🏳️ :", "flag")

题目在Zmod(2^128-2)的多项式环生成了一个随机的度为10的多项式SUPOLY，简记为$g$，之后进行21333=bytes_to_long(b"SU")次加密，每次流程为：

• 生成一个随机的随机的度为10的多项式$f$
• 给出$(fg)(i), i \in [0,10)$的低8位

我们需要利用这些信息求解出$g$，从而求解他的md5值发回给靶机，从而拿到flag。

题目乍一看很像某种HNP，但是其实完全不是这样，注意到题目描述为：

cyberClier:)

lier其实暗示题目本身是个骗局XD，漏洞点实际上在于sage10.4版本及其之后的PR.random_element()的实现，dockerfile里有写到sagemath的版本是10.5，因此查看官方文档可以看到他的具体实现：

def random_element(self, degree=(-1, 2), monic=False, *args, **kwds):
    r"""
    Return a random polynomial of given degree (bounds).

    INPUT:

    - ``degree`` -- (default: ``(-1, 2)``) integer for fixing the degree or
        a tuple of minimum and maximum degrees

    - ``monic`` -- boolean (default: ``False``); indicate whether the sampled
        polynomial should be monic

    - ``*args, **kwds`` -- additional keyword parameters passed on to the
        ``random_element`` method for the base ring

    EXAMPLES::

        sage: R.<x> = ZZ[]
        sage: f = R.random_element(10, x=5, y=10)
        sage: f.degree()
        10
        sage: f.parent() is R
        True
        sage: all(a in range(5, 10) for a in f.coefficients())
        True
        sage: R.random_element(6).degree()
        6

    If a tuple of two integers is given for the ``degree`` argument, a
    polynomial is chosen among all polynomials with degree between them. If
    the base ring can be sampled uniformly, then this method also samples
    uniformly::

        sage: R.random_element(degree=(0, 4)).degree() in range(0, 5)
        True
        sage: found = [False]*5
        sage: while not all(found):
        ....:     found[R.random_element(degree=(0, 4)).degree()] = True

    Note that the zero polynomial has degree `-1`, so if you want to
    consider it set the minimum degree to `-1`::

        sage: while R.random_element(degree=(-1,2), x=-1, y=1) != R.zero():
        ....:     pass

    Monic polynomials are chosen among all monic polynomials with degree
    between the given ``degree`` argument::

        sage: all(R.random_element(degree=(-1, 1), monic=True).is_monic() for _ in range(10^3))
        True
        sage: all(R.random_element(degree=(0, 1), monic=True).is_monic() for _ in range(10^3))
        True

    TESTS::

        sage: R.random_element(degree=[5])
        Traceback (most recent call last):
        ...
        ValueError: degree argument must be an integer or a tuple of 2 integers (min_degree, max_degree)

        sage: R.random_element(degree=(5,4))
        Traceback (most recent call last):
        ...
        ValueError: minimum degree must be less or equal than maximum degree

    Check that :issue:`16682` is fixed::

        sage: R = PolynomialRing(GF(2), 'z')
        sage: for _ in range(100):
        ....:     d = randint(-1, 20)
        ....:     P = R.random_element(degree=d)
        ....:     assert P.degree() == d

    In :issue:`37118`, ranges including integers below `-1` no longer raise
    an error::

        sage: R.random_element(degree=(-2, 3))  # random
        z^3 + z^2 + 1

    ::

        sage: 0 in [R.random_element(degree=(-1, 2), monic=True) for _ in range(500)]
        False

    Testing error handling::

        sage: R.random_element(degree=-5)
        Traceback (most recent call last):
        ...
        ValueError: degree (=-5) must be at least -1

        sage: R.random_element(degree=(-3, -2))
        Traceback (most recent call last):
        ...
        ValueError: maximum degree (=-2) must be at least -1

    Testing uniformity::

        sage: from collections import Counter
        sage: R = GF(3)["x"]
        sage: samples = [R.random_element(degree=(-1, 2)) for _ in range(27000)]    # long time
        sage: assert all(750 <= f <= 1250 for f in Counter(samples).values())       # long time

        sage: samples = [R.random_element(degree=(-1, 2), monic=True) for _ in range(13000)] # long time
        sage: assert all(750 <= f <= 1250 for f in Counter(samples).values())       # long time
    """
    R = self.base_ring()

    if isinstance(degree, (list, tuple)):
        if len(degree) != 2:
            raise ValueError("degree argument must be an integer or a tuple of 2 integers (min_degree, max_degree)")
        if degree[0] > degree[1]:
            raise ValueError("minimum degree must be less or equal than maximum degree")
        if degree[1] < -1:
            raise ValueError(f"maximum degree (={degree[1]}) must be at least -1")
    else:
        if degree < -1:
            raise ValueError(f"degree (={degree}) must be at least -1")
        degree = (degree, degree)

    if degree[0] <= -2:
        degree = (-1, degree[1])

    # If the coefficient range only contains 0, then
    # * if the degree range includes -1, return the zero polynomial,
    # * otherwise raise a value error
    if args == (0, 1):
        if degree[0] == -1:
            return self.zero()
        else:
            raise ValueError("No polynomial of degree >= 0 has all coefficients zero")

    if degree == (-1, -1):
        return self.zero()

    # If `monic` is set, zero should be ignored
    if degree[0] == -1 and monic:
        if degree[1] == -1:
            raise ValueError("the maximum degree of monic polynomials needs to be at least 0")
        if degree[1] == 0:
            return self.one()
        degree = (0, degree[1])

    # Pick random coefficients
    end = degree[1]
    if degree[0] == -1:
        return self([R.random_element(*args, **kwds) for _ in range(end + 1)])

    nonzero = False
    coefs = [None] * (end + 1)

    while not nonzero:
        # Pick leading coefficients, if `monic` is set it's handle here.
        if monic:
            for i in range(degree[1] - degree[0] + 1):
                coefs[end - i] = R.random_element(*args, **kwds)
                if not nonzero and not coefs[end - i].is_zero():
                    coefs[end - i] = R.one()
                    nonzero = True
        else:
            # Fast path
            for i in range(degree[1] - degree[0] + 1):
                coefs[end - i] = R.random_element(*args, **kwds)
                nonzero |= not coefs[end - i].is_zero()

    # Now we pick the remaining coefficients.
    for i in range(degree[1] - degree[0] + 1, degree[1] + 1):
        coefs[end - i] = R.random_element(*args, **kwds)

    return self(coefs)

可以看出，多项式环的随机多项式生成完全依赖于其基环的随机系数生成，而在Zmod(2^128-2)下，随机数生成就是基于MT19937的python中randrange(0,2^128-2)的实现，这可以说基本上完全等价于getrandbits(128)。

回到题目中，由于多项式环是模$2^{128}-2$的，他和$2^{8}$有公因子2所以可以reduce到模2下，此时我们会发现每次加密其实最核心的泄露内容在于：

$$(fg)(0) \quad (mod \; 2)$$

也就是说，我们可以从0处的函数值得到$fg$乘积的LSB，此时：

• 当$g$的常数项模2为0时，函数值是全0

• 当$g$的常数项模2为1时，函数值就是$f$的LSB，此时相当于得到了21333个MT19937的不连续泄露比特，因此可以重构初始state进行随机数预测，从而还原$g$和所有$f$

因此我们可以反复重连靶机，检查是否常数项模2下为全0，如果不是的话就可以求解矩阵方程得到初始state了。

最后一个问题在于题目有10s的限制。MT19937的不连续比特泄露的一般思路是建立矩阵方程，并在拿到具体泄露比特后解矩阵方程得到初始state。在泄露位置确定时，这个矩阵是可以预计算的，因此实际交互时花的时间只包含解一次矩阵方程。

但是实际上，普通算力下解这样规模的矩阵方程也需要20s左右才行，10s并不够。而由于MT19937的性质，2-32bit这一段初始state是用不到的，因此矩阵秩最高也就只能达到19937。这也代表着实际上需要的方程数量不需要19968个，只需要19937个，我们也并不需要解矩阵方程，只需要构建出19937x19937的满秩方阵，并预计算它的逆即可。这样在从靶机接收到数据之后，实际的操作就只剩下一个矩阵-向量乘法而已，因此其实一瞬间就可以得到初始state了。

而之所以给10s的alarm，不压缩到更短，是因为给更短的话可能会让大家意识到这不是个hnp问题，因为LLL需要时间(๑¯ω¯๑)

exp：

预计算：

from Crypto.Util.number import *
import random
from tqdm import *

######################################################### part1 recover MT and get seed
RNG = random.Random()

def construct_a_row(RNG):
    row = []
    RNG.getrandbits(128*11)
    for i in range(bytes_to_long(b"SU")):
        RNG.getrandbits(128*10)
        row += [int(int(RNG.getrandbits(128)) & 1)]
    return row

L = []
for i in trange(19968):
    state = [0]*624
    temp = "0"*i + "1"*1 + "0"*(19968-1-i)
    for j in range(624):
        state[j] = int(temp[32*j:32*j+32],2)
    RNG.setstate((3,tuple(state+[624]),None))
    L.append(construct_a_row(RNG))

L = Matrix(GF(2),L)
K = L.T
KK = K[:19937, [0]+list(range(32,19968))]
KK_inv = KK^(-1)

交互：

from pwn import *

context.log_level = "critical"

#sh = process(["sage", "chall.sage"])
sh = remote("1.95.46.185", 10005)
sh.recvuntil(b" :")
points = eval(sh.recvline().strip().decode())
known = [i[0] % 2 for i in points]

print(1 in known)
if(1 not in known):
    sh.close()

R = vector(GF(2), known[:19937])
res = (KK_inv * R).list()
res = [res[0]] + [0]*31 + res[1:]

init = "".join(list(map(str, res)))
state = []
for i in range(624):
    state.append(int(init[32*i:32*i+32],2))

from hashlib import md5
import random
RNG1 = random.Random()
RNG1.setstate((3,tuple(state+[624]),None))

g = [RNG1.getrandbits(128) for i in range(11)][::-1]

sh.recvuntil(b"Show me :)")
sh.sendline(str(md5(str(g).encode()).hexdigest()).encode())

print(sh.recvline().decode())
sh.close()


#SUCTF{bytes_to_long_of_SU_seems_bigger_than_19937_XD_try_random_matrix(GF(2),20000,20000)_and_see_its_rank!}

这样的随机数生成对于矩阵、多项式之类来说显然失去了一定随机性，比如：

• flag给的例子，在sage里是没有办法得到秩大于19937的矩阵的
• 由于624x32个bit就可以往后预测，所以比如模$2^{624}-1$的多项式环下，多项式的度达到31以后，剩下的系数都能预测了，显然也不够随机

SU_rsa

题目描述：

ez_RSA，Let’s Signin

题目：

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]
# d_m =  54846367460362174332079522877510670032871200032162046677317492493462931044216323394426650814743565762481796045534803612751698364585822047676578654787832771646295054609274740117061370718708622855577527177104905114099420613343527343145928755498638387667064228376160623881856439218281811203793522182599504560128
# n =  102371500687797342407596664857291734254917985018214775746292433509077140372871717687125679767929573899320192533126974567980143105445007878861163511159294802350697707435107548927953839625147773016776671583898492755338444338394630801056367836711191009369960379855825277626760709076218114602209903833128735441623
# e =  112238903025225752449505695131644979150784442753977451850362059850426421356123

题目内容很简单，给出RSA的公钥，需要求出n的分解。而本题比较特殊的参数有：

• e为256bit的素数，而不是65537
• 额外给出了d的高512位

做过高校密码挑战赛以及强网杯traditional game的师傅应该会对这类问题比较熟悉，首先仍然是从如下等式出发：

$$ed = 1 + k(n - (p+q) + 1)$$

现在有e、d高位以及n，所以可以求出k来：

$$k = \lfloor \frac{ed_h}{n} \rfloor + 1$$

得到k之后，把已知的dh,k都代入上面的等式，将$p+q$记为$s$：

$$e(d_h + d_l) - 1 - k(n+1 - s) = 0$$

展开整理一下就有：

$$ed_l + ks + [ed_h - 1 - k(n+1)] = 0$$

这是个线性的等式，LLL一下后会发现：

• 第一行的值由$(-k, e)$组成
• 第二行的值不是预期的$(d_l, s)$

这是因为我们的目标向量是512bit的数量级，而e和k都只有256bit的数量级，显然比目标向量要短，因此LLL之后的第二行是与$(-k, e)$做了约减后的结果，也就是：

$$(d_l - tk, s + te)$$

而虽然这里t的具体值我们不知道，但我们可以把e模掉，就得到s模e的值，这也等价于得到了p或q模e的值。而e是256bit的，因此用类似p低256位已知的copper方法，去爆破+多进程copper就可以了。

exp：

from Crypto.Util.number import *

d_m =  54846367460362174332079522877510670032871200032162046677317492493462931044216323394426650814743565762481796045534803612751698364585822047676578654787832771646295054609274740117061370718708622855577527177104905114099420613343527343145928755498638387667064228376160623881856439218281811203793522182599504560128
n =  102371500687797342407596664857291734254917985018214775746292433509077140372871717687125679767929573899320192533126974567980143105445007878861163511159294802350697707435107548927953839625147773016776671583898492755338444338394630801056367836711191009369960379855825277626760709076218114602209903833128735441623
e =  112238903025225752449505695131644979150784442753977451850362059850426421356123

k = e*d_m // n + 1
L = Matrix(ZZ, [
    [1, 0, 0, e],
    [0, 1, 0, k],
    [0, 0, 2^512, e*d_m - k - 1 - k*n],
])
L[:, -1:] *= 2^1000
L = L.LLL()
res = L[1]
t = res[1] % e

PR.<x> = PolynomialRing(Zmod(e))
f = x^2 + n - t*x
res = f.roots()
pl = int(res[0][0])

import multiprocessing
import tqdm
from hashlib import sha256

def copper_attack(i):
    PR.<x> = PolynomialRing(Zmod(n))
    f = e*(2^12*x + i) + pl
    f = f.monic()
    res = f.small_roots(X=2^244, beta=0.499, epsilon=0.02)
    if(res != []):
        t = int(res[0])
        p = e*(2^12*t + i) + pl
        q = n // p
        assert p * q == n and isPrime(p) and isPrime(q)
        print(sha256(str(p).encode()).hexdigest()[:32])
        print(sha256(str(q).encode()).hexdigest()[:32])
        return True

with multiprocessing.Pool(processes=16) as pool:
    for _ in tqdm.tqdm(pool.imap(copper_attack, range(2^12)), total=int(2^12)):
        if(_):
            break


#SUCTF{1c56d344aba19600db3956abebc34425}
#SUCTF{c1864501fab1841178177d4f15af4ad8}

SU_hash

题目描述：

nc 1.95.46.185 10007
nc 1.95.46.185 10008

easy_hash

题目：

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，在连接上靶机后：

• 靶机给出哈希函数的初始state，记为$n_0$
• 输入一段msg，如果fn(msg, n0)的结果等于b'justjusthashhash'，就可以拿到flag。其中fn函数是对msg逐字节的操作

难点在于每一次ret状态的更新不仅与当前字节值有关，也与当前myhash函数的内部state值有关，也就是说对于一个输入串来说，改变其中某一个字节，会导致后面的所有状态跟着改变。

解决思路并不难，我们假设对于初始状态$n_0$，能够找到两段不同的字符串$m_1,m_2$，使他达到相同的状态$n_1$，那么此时：

• 假设后续消息为$t$，那么对于$m_1+t$和$m_2+t$，后面的myhash的内部状态也都相同
• 而$m_1,m_2$对于ret的贡献却不一样

ret是多个myhash做digest的结果的异或，长度为128bit。而一组碰撞的意义在于，可以在确定初始和结束state的情况下给出两组不同的ret值，而只需要找到128组这样的碰撞，就可以解线性方程来确定每一组碰撞究竟取哪一个来得到最终需要的结果b'justjusthashhash'了。而对于myhash来说找到碰撞是容易的，由于state可以看成是线性的迭代，所以用LLL就可以很轻松找到碰撞了。

但是@hashhash做这个题目的思路更简单，注意到myhash的迭代为：

self.n = self.g * (2 * self.n + msg[i])

而这个迭代过程实际上可以看作是模$2^{128}$下的，因此无论初始state是多少，对于b"\x00"*128这样的输入，128次迭代后n前的系数会达到$2^{128}$从而被消掉。而由于msg又都是0，所以此时的n在模$2^{128}$的意义下也就是0了，这就达到了一个非常好处理的终态。

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

不过这个方法的payload会稍微长一点，而比赛的靶机似乎在比较卡的时候还会有socket长度截断之类的bug，这样的话还是要加一点格的优化来缩短payload长度才行

exp：

from Crypto.Util.number import *
from itertools import product
from hashlib import *
import string
from pwn 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 ((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

def proof_of_work():
    table = string.digits + string.ascii_letters
    temp = sh.recvuntil(b"sha256(XXXX+")
    temp = sh.recvline()
    suffix = temp[:16].decode()
    hex1 = temp[20:].strip().decode()
    for i in product(table, repeat=4):
        temp = "".join(i)
        if(sha256((temp+suffix).encode()).hexdigest() == hex1):
            sh.sendline(temp.encode())
            return
        
sh = remote("1.95.46.185", 10007)
proof_of_work()
sh.recvuntil(b"n0 = ")
n0 = int(sh.recvline().strip().decode())

t = (bytes_to_long(fn(b"\x00"*128, n0))) % 2^128
R = vector(GF(2), list(map(int, bin((bytes_to_long(b"justjusthashhash") ^^ t) % 2^128)[2:].zfill(128))))
L = []
for i in range(128):
    temp = long_to_bytes(i, 1) + b"\x00"*128
    L.append(list(map(int, bin(bytes_to_long(fn(temp, 0)))[2:].zfill(128))))
L = Matrix(GF(2), L)
res = L.solve_left(R)

msg = b"\x00"*128
for i, j in enumerate(res):
    if(j == 1):
        msg += (long_to_bytes(i, 1) + b"\x00"*128)
assert fn(msg, n0) == b"justjusthashhash"
sh.sendline(msg.hex().encode())
print(sh.recvline())


#SUCTF{5imple_st4te_Tran3fer_w1th_s1m1lar_to_md5!!!!!}