2025-SUCTF-crypto

复现一下，学习到了不少东西

SU_signin

题目：

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)

先解释一下双线性配对吧
双线性配对可以理解成一个函数，其输入为椭圆曲线上的两个点，输出为椭圆曲线所在的域上的一个值。如果把这个函数记为e，那么这个概念可以写为

e : E_F \times E_F \rightarrow F

P \in E_F,Q \in E_F

e(P,Q) = a ,a\in F

看到这里，其实可能会疑惑这个e代表的函数具体是什么？可以参考下图

其实不用特别了解这个e的具体实现，更重要的是双线性配对函数的性质：

\begin{aligned} e(P, Q+R) = e(P, Q) \cdot e(P, R) \\ e(P + S, Q) = e(P, Q) \cdot e(S, Q)\end{aligned}

得出两条重要的结论：

e(aP,bQ) = e(P,Q)^{ab}

e(P,P) = 1

我们现在回到题目，我们可以知道 $n_1$ 阶的点 $P_1$ 和 $n_2$ 阶的点 $P_2$
flag的那位bit为0时， $c = aG_1 + bP_2$
flag的那位bit为1时， $c = aP_1 + bG_2$
因为他是填充的所以最后一位一定是0，那我们就可以知道最后一个c(记作K)一定是 $aG_1 + bP_2$

e(n_2K, aG_1 + bP_2) = e(n_2K, P_2)^b = e(K, P_2)^{bn_2} = e(K, \frac{o}{n_2} \cdot G_2)^{bn_2} = e(K, G_2)^{ob} = 1

由于 $e(K, P_2)$ 应该是 $n_2$ 次单位根，所以需要乘上一个 $n_2$
最后一步 $e(K, G_2)^{oa} = 1$ 是因为任何数的o次方(o为阶)都会等于1

e(n_2K, aP_1 + bG_2) = e(n_2K, G_2)^{a} = e(K, G_2)^{an_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)))

SU_rsa

题目：

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

通过下式

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

得到

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

e(d_h + d_l) - 1 - k(n+1 - (p+q)) = 0

设 $s=p+q$

s \equiv k^{-1}+n+1 \mod e

得到了(p+q)的低256位后，通过解多项式 $x^{2} - s*x + n = 0$ 计算出p的低256位，再多线程爆破+copper，exp直接抄的题解
exp：

from tqdm import trange
from Crypto.Util.number import inverse
from multiprocessing import Pool
from hashlib import sha256
import gmpy2


d_m =  54846367460362174332079522877510670032871200032162046677317492493462931044216323394426650814743565762481796045534803612751698364585822047676578654787832771646295054609274740117061370718708622855577527177104905114099420613343527343145928755498638387667064228376160623881856439218281811203793522182599504560128
n =  102371500687797342407596664857291734254917985018214775746292433509077140372871717687125679767929573899320192533126974567980143105445007878861163511159294802350697707435107548927953839625147773016776671583898492755338444338394630801056367836711191009369960379855825277626760709076218114602209903833128735441623
e =  112238903025225752449505695131644979150784442753977451850362059850426421356123

# 计算 k
k = (e*d_m) // n + 1

# 计算p mod e的值
k_inv = inverse(k,e)
s = (n + 1 + k_inv) % e
R.<x> = PolynomialRing(Zmod(e))
f = x^2 - s*x + n
res = f.roots()
may_p_mod_e = [int(res[0][0]),int(res[1][0])]

def attack(range):
    low = range[0]
    up = range[1]
    for pl in may_p_mod_e:
        R.<x> = PolynomialRing(Zmod(n))
        for i in trange(low,up):
            f = (x * 2^14 + i) * e + pl
            res = f.monic().small_roots(X=2^242,beta=0.49,epsilon=0.02)
            if res != []:
                print(f"res = {res}")
                print(f"i = {i}")
            for root in res:
                p = (int(root) * 2^14 + i) * e + pl
                if n % p == 0:
                    flag1 = "SUCTF{" + sha256(str(p).encode()).hexdigest()[:32] + "}"
                    flag2 = "SUCTF{" + sha256(str(n // p).encode()).hexdigest()[:32] + "}"
                    print(flag1)
                    print(flag2)
                    return 
                
ranges = [(i,i + 512) for i in range(0,2^14,512)]

with Pool(32) as pool:  
    r = list(pool.imap(attack,ranges))

SU_mathgame

题目：

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()

game1：
找一个卡迈克尔数

exp：

from Crypto.Util.number import *
from random import getrandbits
if(1):
    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 = 1240182187498725163761792863173103722838185830940091541611038318784715495596946817667298569161

game2：

\frac{x}{y+z}+\frac{y}{x+z}+\frac{z}{x+y} = 4

求x，y，z
参考
exp：

def solve(n, N=1, check=True):  # count N groups
  R.<x, y, z> = QQ[]
  f = x^3+y^3+z^3-(n-1)*x^2*(y+z)-(n-1)*y^2*(x+z)-(n-1)*z^2*(x+y)-(2*n-3)*x*y*z
  tran = EllipticCurve_from_cubic(f, None, true)
  tran_inv = tran.inverse()
  EC = tran.codomain()
  g = EC.gens()[0]
  P = g

  count = 0
  while count<3:
    Pinv = tran_inv(P)
    _x = Pinv[0].numerator()
    _y = Pinv[1].numerator()
    _z = Pinv[0].denominator()
    if _x>0 and _y>0:
      print('x = %d' % _x)
      print('y = %d' % _y)
      print('z = %d' % _z)
      if check: print('check: '+str(f([_x, _y, _z])==0))
      print('')
      count = count+1
    P = P+g

solve(4)#等号右边的数

game3：
time.time()是输出时间戳，那么在运行的时候就可以直接得到了
如果运行时间久的话，可能需要爆破一下
参考糖醋小鸡块的博客
exp：

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

SU_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?")

参考糖醋小鸡块的blog
连接靶机后得到 $n_0$
先看

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

这个n再迭代128次后，其实是和b'/x00'迭代128次后是一样的，因为n的系数肯定有 $2^{128}$ 模 $2^{128}$ 后是0，msg还是0
所以后面的digest函数其实不用管他，因为都是同样的步骤
那么完全可以在0-255之间随便选128个值，然后分别给他们都加上b"\x00"*128的后缀，然后看作128个不同的整体去解线性方程组就可以了。
解释一下：

后缀加上b'\x00'*128的原因就是要使n迭代128次后再和i进行fn函数，这样的话才能使用

fn(temp, 0)

找128组是因为目标向量有128个元素，那么就需要找到一个128x128的矩阵，满秩的话就一定有解

这都是一些我自己的理解，如果有误的话，希望师傅们帮忙指正
exp：

from Crypto.Util.number 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]))
        ret = xor(ret,h.digest())
    return ret



n0 = getRandomNBitInteger(382)  # 当作接收
# 消除n0的影响,作为初始状态
t = (bytes_to_long(fn(b"\x00"*128, n0))) % 2^128

# 用 初始状态 异或 最终状态 得到 fn(输入状态)
R = vector(GF(2), list(map(int, bin((bytes_to_long(b"justjusthashhash") ^^ t) % 2^128)[2:].zfill(128))))

# 因为myhash是线性变化所以可以直接利用矩阵求解
# + b"\x00"*128 也是为了消除n0的影响
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)
print(fn(msg,n0))
print(fn(msg, n0) == b"justjusthashhash")

SU_signin

SU_rsa

SU_mathgame

SU_hash

感谢您的支持，我会继续努力的!