SUCTF 2026 Crypto方向部分赛题Write UP
|
235
|
0
|
Write UP

2621 字
|
55 分钟

前言

这次给SUCTF出了SU_Lattice, SU_Isogeny以及SU_Restaurant三道题，就写一下这三道算了=ω=（懒）

SU_Lattice

首先对给出的elf进行逆向可以得到主函数（sub_401E71）：

void __noreturn sub_401E71()
{
  int v0; // edx
  int v1; // ecx
  int v2; // r8d
  int v3; // r9d
  int v4; // edx
  int v5; // ecx
  int v6; // r8d
  int v7; // r9d
  int v8; // edx
  int v9; // ecx
  int v10; // r8d
  int v11; // r9d
  int v12; // edx
  int v13; // ecx
  int v14; // r8d
  int v15; // r9d
  int v16; // esi
  int v17; // edx
  int v18; // ecx
  int v19; // r8d
  int v20; // r9d
  int v21; // [rsp+0h] [rbp-70h] BYREF
  int i; // [rsp+4h] [rbp-6Ch]
  __int64 v23; // [rsp+8h] [rbp-68h] BYREF
  __int64 v24; // [rsp+10h] [rbp-60h]
  __int64 v25; // [rsp+18h] [rbp-58h]
  char v26[72]; // [rsp+20h] [rbp-50h] BYREF
  unsigned __int64 v27; // [rsp+68h] [rbp-8h]

  v27 = __readfsqword(0x28u);
  sub_401CB8();
  sub_401D1D();
  v24 = 0LL;
  for ( i = 0; i <= 23; ++i )
    v24 = (qword_4E82E0[i] + v24) % qword_4E83A0;
  while ( 1 )
  {
    sub_401E16();
    sub_40C050((unsigned int)"%d", (unsigned int)&v21, v0, v1, v2, v3, v21);
    if ( v21 == 3 )
    {
      sub_41AD00("Goodbye!");
      sub_40B390(0LL);
    }
    if ( v21 > 3 )
    {
LABEL_16:
      sub_41AD00("NO!!!");
    }
    else if ( v21 == 1 )
    {
      sub_40BEC0((unsigned int)"Please enter your answer: ", (unsigned int)&v21, v4, v5, v6, v7, 1);
      sub_40C050((unsigned int)"%lld", (unsigned int)&v23, v8, v9, v10, v11, v21);
      if ( v24 != v23 )
      {
        sub_41AD00("Wrong answer!");
        sub_40B390(1LL);
      }
      v25 = sub_41A910("./flag", "r");
      if ( !v25 )
      {
        sub_41AD00("Failed to open file...");
        sub_40B390(1LL);
      }
      sub_41A660(v26, 64LL, v25);
      sub_40BEC0((unsigned int)"Congratulations! Here is your flag: %s\n", (unsigned int)v26, v12, v13, v14, v15, v21);
      sub_41A370(v25);
    }
    else
    {
      if ( v21 != 2 )
        goto LABEL_16;
      v16 = sub_401BAE(40LL);
      sub_40BEC0((unsigned int)"Here is your hint: %lld\n", v16, v17, v18, v19, v20, v21);
    }
  }
}

数据初始化（sub_401D1D）：

__int64 sub_401D1D()
{
  int v0; // r8d
  int v1; // r9d
  __int64 result; // rax
  int v3; // r8d
  int v4; // r9d
  int i; // [rsp+0h] [rbp-10h]
  int j; // [rsp+4h] [rbp-Ch]
  __int64 v7; // [rsp+8h] [rbp-8h]

  v7 = sub_41A910("./data", "r");
  if ( !v7 )
  {
    sub_41AD00("Failed to open file...");
    sub_40B390(1LL);
  }
  result = sub_40C120(v7, (unsigned int)"%lld", (unsigned int)&qword_4E83A0, (unsigned int)"%lld", v0, v1);
  for ( i = 0; i <= 23; ++i )
    result = sub_40C120(v7, (unsigned int)"%lld", (unsigned int)&qword_4E8220[i], (unsigned int)"%lld", v3, v4);
  for ( j = 0; j <= 23; ++j )
    result = sub_40C120(v7, (unsigned int)"%lld", (unsigned int)&qword_4E82E0[j], (unsigned int)"%lld", v3, v4);
  return result;
}

菜单（sub_401E16）：

__int64 sub_401E16()
{
  sub_41AD00("===Flag Management System===");
  sub_41AD00("[1] Get Flag");
  sub_41AD00("[2] Get Hint");
  sub_41AD00("[3] Exit");
  return sub_40BEC0((__int64)">>> ");
}

计算hint的函数（sub_401BAE）：

__int64 __fastcall sub_401BAE(__int64 a1)
{
  int i; // [rsp+10h] [rbp-10h]
  int j; // [rsp+14h] [rbp-Ch]
  __int64 v4; // [rsp+18h] [rbp-8h]

  if ( a1 > 60 )
  {
    sub_41AD00("Something went wrong...");
    sub_40B390(1LL);
  }
  v4 = 0LL;
  for ( i = 0; i <= 23; ++i )
    v4 = (v4 + sub_401B45(qword_4E82E0[i], qword_4E8220[i])) % qword_4E83A0;
  for ( j = 0; j <= 22; ++j )
    qword_4E82E0[j] = qword_4E82E0[j + 1];
  qword_4E8398 = v4;
  return v4 >> (60 - (unsigned __int8)a1);
}

以及龟速乘（sub_401B45）：

__int64 __fastcall sub_401B45(__int64 a1, __int64 a2)
{
  __int64 v5; // [rsp+18h] [rbp-8h]

  v5 = 0LL;
  while ( a2 )
  {
    if ( (a2 & 1) != 0 )
      v5 = (v5 + a1) % qword_4E83A0;
    a1 = 2 * a1 % qword_4E83A0;
    a2 >>= 1;
  }
  return v5;
}

对上述组件进行分析可以知道其实这题实际上是一个一个模数\(m\)以及参数\(c_0,c_1,\cdots,c_{23}\)均未知的截断\(\mathbb{Z}/(m)-\text{LFSR}\)，获取的hint其实是这个截断\(\mathbb{Z}/(m)-\text{LFSR}\)输出的高40位，参考An Improved Method for Predicting Truncated Fibonacci LFSRs over Integer Residue Rings可以知道，这里其实是对应了\(n=24,\alpha=40,\beta=20\)的参数全未知的截断\(\mathbb{Z}/(m)-\text{LFSR}\)，通过文中提到的：

$$
\frac{1}{r}+\frac{1}{t}\le\frac{\alpha}{n\log{m}}
$$

我们令\(r=t\)，则有：

$$
\frac{1}{r}+\frac{1}{t}=\frac{2}{r}\le\frac{\alpha}{n\log{m}}\approx\frac{40}{24\times 60}=\frac{1}{36}
$$

可以求得\(r=t>72\)，在\(72\)的基础上加上\(15%\)的冗余量可以知道我们应该取\(r=t=\lceil 72\times1.15\rceil=83\)，所以保守起见，我们需要至少取\(N=r+t+1=167\)个输出进行求解，设这167个输出分别为\(a_0,a_1,\cdots,a_{166}\)，首先构造格：

$$
\left(\begin{matrix}
2^{\alpha}&&&&&&&&\\
&2^{\alpha}&&&&&&&\\
&&\ddots&&&&&&\\
&&&2^{\alpha}&&&&&\\
a_0&a_1&\cdots&a_{t-1}&1&&&\\
a_1&a_2&\cdots&a_{t}&&1&&\\
\vdots&\vdots&&\vdots&&&\ddots&\\
a_{r-1}&a_{r}&\cdots&a_{166}&&&&1\\
\end{matrix}\right)
$$

进行规约可以得到若干条短向量，取前三条非零短向量的后\(r\)个分量作为参数来组成\(\mathbb{Z}_m\)上的多项式\(F_1(x),F_2(x),F_3(x)\)，对这三个多项式两两组合取结式之后求最大公约数即可得到一个可以被模数\(m\)整除的数，分解并提取即可得到模数\(m\)，在获得模数\(m\)之后问题就变成了已知\(m\)但是参数未知的截断\(\mathbb{Z}/(m)-\text{LFSR}\)了，令\(K=2^{\beta}\)，此时我们构造格：

$$
\left(\begin{matrix}
m&&&&&&&&\\
&m&&&&&&&\\
&&\ddots&&&&&&\\
&&&m&&&&&\\
Ka_0&Ka_1&\cdots&Ka_{t-1}&K&&&\\
Ka_1&Ka_2&\cdots&Ka_{t}&&K&&\\
\vdots&\vdots&&\vdots&&&\ddots&\\
Ka_{r-1}&Ka_{r}&\cdots&Ka_{166}&&&&K\\
\end{matrix}\right)
$$

取前若干条短向量的后\(r\)个分量作为参数来组成\(\mathbb{Z}_m\)上的多项式，对这些多项式求最大公约式就可以得到一个如下形式的度为24的不可约多项式：

$$
f(x)=x^{24}-(c_0+c_1x+c_2x^2+\cdots+c_{23}x^{23})
$$
最后结合递推公式\(x_{s+24}\equiv c_0x_{s}+c_1x_{s+1}+\cdots+c_{23}x_{s+23}\pmod{m}\)，以获得的LFSR输出中未知的低位作为未知量进行多元coppersmith就可以恢复LFSR的状态，从而倒推出种子、获得flag了：

from pwn import *
from sage.all import *
from tqdm import *
from cuso import find_small_roots
from Crypto.Util.number import *

io = remote("1.95.152.117", 10001)

n = 24
alpha = 40
beta = 20
K = 2**beta     

r = 83
t = 83
N = r + t - 1

hints = []

for _ in trange(N):
    io.sendlineafter(b">>> ", b"2")
    io.recvuntil(b"Here is your hint: ")
    hint = int(io.recvline().strip())
    hints.append(hint)

y = []

for i in range(r):
    y.append(hints[i: i+r])

Y = matrix(ZZ, y)

M = block_matrix([[2**alpha, 0], [Y, 1]])
res = M.BKZ(block_size=20)

R = ZZ['x']
polys = []

for i in range(50):
    vec = res[i]
    coeffs = list(vec[t:])
    if all(c == 0 for c in coeffs):
        continue
    F = R(coeffs)
    if F.degree() > 0:
        polys.append(F)

F1, F2, F3 = polys[:3]
F12 = F1.resultant(F2)
F13 = F1.resultant(F3)
F23 = F2.resultant(F3)

# print(F12)
# print(F13)
# print(F23)

tmp = gcd(gcd(F12, F13), F23)
m = list(factor(tmp))[-1][0]

L = block_matrix([[m, 0], [K*Y, K]])

res = L.BKZ(block_size=20)
R = GF(m)['x']
candidates = []

for v in res:
    if v.norm() == 0: 
        continue

    coeffs = []
    is_valid = True
    for k in range(r):
        coeffs.append(v[t + k] // K)

    if is_valid:
        try:
            poly = R(coeffs)
            d = poly.degree()
            if d >= n:
                candidates.append(poly)
        except:
            pass

    if len(candidates) >= 10: 
        break

F = candidates[0]
for p in candidates[1:]:
    tmp = gcd(F, p)
    if tmp.degree() >= n:
        F = tmp

F = F.monic()
print(F)

# assert F.is_primitive() and F.degree() == n

C = [int(c) for c in (-F).coefficients(sparse=False)[:-1]]

l = [var(f'l{i}') for i in range(2*n)]

xs = [2**beta * hints[i] + l[i] for i in range(2*n)]
relations = []

for i in range(n):
    f = 0
    for j in range(n):
        f += C[j] * xs[i + j]
    f -= xs[i + n]
    relations.append(f)

bounds = {l[i]: (0, 2**beta) for i in range(2*n)}

sols = find_small_roots(relations, bounds=bounds, modulus=m)

state = [2**beta * hints[i] + sols[0][l[i]] for i in range(n)]

for i in range(n):
    tmp = state[-1]
    for j in range(n-1):
        tmp = (tmp - C[j+1] * state[j]) % m

    tmp = tmp * inverse(C[0], m) % m
    state = [tmp] + state[:-1]

ans = sum(state)

io.sendlineafter(b'>>> ', b'1')
io.sendlineafter(b'Please enter your answer: ', str(ans % m).encode())

io.interactive()

附：源码

main.sage（附件中未给出）

import os

flag = "SUCTF{b8faea32-9f91-42b5-9355-33865e06270c}"

with open('./flag', 'w') as f:
    f.write(flag)

m = random_prime(2^60+2^16, lbound=2^60-2^16, proof=False)

f = open("./data", "w")
f.write(f"{m}\n")

F = GF(m)
R.<x> = PolynomialRing(F)
while True:
    poly = R.irreducible_element(24, algorithm="random")
    if all(c != 0 for c in poly.coefficients(sparse=False)):
        break

for i in poly.list()[:-1]:
    f.write(f"{m-i}\n")

for i in range(24):
    f.write(f"{randint(0, 2**59)}\n")

f.close()

src.c（编译之后得到附件中的chall）

#include <stdio.h>
#include <stdlib.h>

#define ll long long

ll c[24];
ll state[24];
ll p;

ll mul(ll a, ll b)
{
    ll res = 0;
    while (b)
    {
        if (b & 1)
        {
            res = (res + a) % p;
        }
        a = (a << 1) % p;
        b >>= 1;
    }
    return res;
}

ll RAND(ll n)
{
    if(n > 60)
    {
        printf("Something went wrong...\n");
        exit(1);
    }

    ll tmp = 0;

    for (int i = 0; i < 24; i++)
    {
        tmp = (tmp + mul(state[i], c[i])) % p;
    }

    for (int i = 0; i < 23; i++)
    {
        state[i] = state[i + 1];
    }

    state[23] = tmp;

    return tmp >> (60 - n);

}

void init()
{
    setvbuf(stdin, NULL, _IONBF, 0);
    setvbuf(stdout, NULL, _IONBF, 0);
    setvbuf(stderr, NULL, _IONBF, 0);
}

void init_param()
{
    FILE *file = fopen("./data", "r");
    if (file == NULL)
    {
        printf("Failed to open file...\n");
        exit(1);
    }

    fscanf(file, "%lld", &p);
    for (int i = 0; i < 24; i++)
    {
        fscanf(file, "%lld", &c[i]);
    }

    for (int i = 0; i < 24; i++)
    {
        fscanf(file, "%lld", &state[i]);
    }

}

void menu()
{
    printf("===Flag Management System===\n");
    printf("[1] Get Flag\n");
    printf("[2] Get Hint\n");
    printf("[3] Exit\n");

    printf(">>> ");
}

int main()
{
    init();
    init_param();

    ll ans = 0;
    for (int i = 0; i < 24; i++)
    {
        ans = (ans + state[i]) % p;
    }

    while (1)
    {
        menu();
        int choice;
        scanf("%d", &choice);

        switch (choice)
        {
            case 1:
                printf("Please enter your answer: ");
                ll user_ans;
                scanf("%lld", &user_ans);
                if (user_ans == ans)
                {
                    FILE *file = fopen("./flag", "r");
                    if (file == NULL)
                    {
                        printf("Failed to open file...\n");
                        exit(1);
                    }
                    char flag[64];
                    fgets(flag, sizeof(flag), file);
                    printf("Congratulations! Here is your flag: %s\n", flag);
                    fclose(file);
                }
                else
                {
                    printf("Wrong answer!\n");
                    exit(1);
                }
                break;
            case 2:
                printf("Here is your hint: %lld\n", RAND(40));
                break;
            case 3:
                printf("Goodbye!\n");
                exit(0);
            default:
                printf("NO!!!\n");
                break;
        }
    }

    return 0;
}

SU_Isogeny

from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import *
from hashlib import sha256
from secret import flag
from random import randint
import os

p = 5326738796327623094747867617954605554069371494832722337612446642054009560026576537626892113026381253624626941643949444792662881241621373288942880288065659

F = GF(p)

pl = [x for x in prime_range(3, 374) + [587]]
pvA = [randint(-5, 5) for _ in pl]
pvB = [randint(-5, 5) for _ in pl]

assert len(pl) == len(pvA) == len(pvB)


def cal(A, sk):
    E = EllipticCurve(F, [0, A, 0, 1, 0])
    for sgn in [1, -1]:
        for e, ell in zip(sk, pl):
            for i in range(sgn * e):
                while not (P := (p + 1) // ell * E.random_element()) or ell * P != 0:
                    pass
                E = E.isogeny_codomain(P)
        E = E.quadratic_twist()
    return E.montgomery_model().a2()

menu = """[1] Get public key
[2] Get gift
[3] Get flag
[4] Exit
>>> """

def main():
    while True:
        try:
            op = input(menu)
            if op == "1":
                pkA = cal(0, pvA)
                pkB = cal(0, pvB)
                print(f"pkA: {pkA}")
                print(f"pkB: {pkB}")
            elif op == "2":
                pkA = int(input("pkA >>> "))
                pkB = int(input("pkB >>> "))
                A = cal(pkA, pvB)
                B = cal(pkB, pvA)
                if A != B:
                    print("Illegal public key!")
                print(f"Gift : {int(A) >> 200}")
            elif op == "3":
                key = sha256(str(cal(cal(0, pvB), pvA)).encode()).digest()
                print(f"Here is your flag: {AES.new(key, AES.MODE_ECB).encrypt(pad(flag, 16)).hex()}")
            elif op == "4":
                print("Bye~")
                break
            else:
                print("Invalid option.")
        except:
            print("Something wrong...")
            break

if __name__ == "__main__":
    main()

分解\(p+1\)可以看到它其实是很标准的CSIDH-512所使用的模数，本题是很标准的CI-HNP问题，求解该问题的具体原理可以参考Solving the Hidden Number Problem for CSIDH and CSURF via Automated Coppersmith一文，在获得公钥\(A,B\)之后，对于\(\mathbb{Z}_p\)上的曲线\(E_A:y^2=x^3+Ax^2+x\)，我们可以通过如下方式计算它的两个4-同源曲线：

$$
\begin{aligned} E_{A1}:y^2=x^3+2\frac{A+6}{2-A}x^2+x\\
E_{A2}:y^2=x^3+2\frac{A-6}{A+2}x^2+x\\
\end{aligned}
$$

我们先将\((A,B)\)作为公钥输入可以得到\(E_{AB}\)的参数的高位\(H_1\)，再分别输入\((2\frac{A+6}{2-A},B)\)和\((2\frac{A-6}{A+2},B)\)作为公钥进行一次错误的密钥交换可以得到\(E_{AB}\)的两条4-同源曲线的参数的高位（分别记为\(H_2,H_3\)），设三未知数\(x,y,z\)，则可以得到如下关系：

$$
\begin{cases}
(H_1+x)(H_2+y)+2(H_1+x)-2(H_2+y)+12=0\\
(H_3+z)(H_2+y)+2(H_2+y)-2(H_3+z)+12=0\\
(H_1+x)(H_3+z)-2(H_1+x)+2(H_3+z)+12=0\\
\end{cases}
$$

因为已知位约为\(512-200=312>\frac{13}{24}\times512\)，满足论文中所给出的可求解条件，所以我们可以通过Coppersmith方法进行求解，这里我们使用cuso进行求解，当然，也可以利用论文中给出的代码（juliannowakowski/automated-coppersmith）进行求解：

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from pwn import *
from sage.all import *
from cuso import find_small_roots

p = 5326738796327623094747867617954605554069371494832722337612446642054009560026576537626892113026381253624626941643949444792662881241621373288942880288065659
F = GF(p)

io = remote("110.42.47.116", 10001)

io.sendlineafter(b">>> ", b"1")
io.recvuntil(b"pkA: ")
a = int(io.recvline().strip())
io.recvuntil(b"pkB: ")
pkB = int(io.recvline().strip())

b = 2 * (a + 6) * inverse(2 - a, p) % p
c = 2 * (a - 6) * inverse(a + 2, p) % p


io.sendlineafter(b">>> ", b"2")
io.sendlineafter(b"pkA >>> ", str(a).encode())
io.sendlineafter(b"pkB >>> ", str(pkB).encode())

io.recvuntil(b"Gift : ")
A = int(io.recvline().strip()) << 200

io.sendlineafter(b">>> ", b"2")
io.sendlineafter(b"pkA >>> ", str(b).encode())
io.sendlineafter(b"pkB >>> ", str(pkB).encode())

io.recvuntil(b"Gift : ")
B = int(io.recvline().strip()) << 200

io.sendlineafter(b">>> ", b"2")
io.sendlineafter(b"pkA >>> ", str(c).encode())
io.sendlineafter(b"pkB >>> ", str(pkB).encode())

io.recvuntil(b"Gift : ")
C = int(io.recvline().strip()) << 200

x, y, z = var("x y z")

relations = [
    (A + x) * (B + y) + 2 * (A + x) - 2 * (B + y) + 12,
    (C + z) * (B + y) + 2 * (B + y) - 2 * (C + z) + 12,
    (A + x) * (C + z) - 2 * (A + x) + 2 * (C + z) + 12
]

bounds = {
    x: (0, 2**200),
    y: (0, 2**200),
    z: (0, 2**200)
}

moduli = [p, p, p]

roots = find_small_roots(relations, bounds, moduli)

io.sendlineafter(b">>> ", b"3")
io.recvuntil(b"Here is your flag: ")
ct = bytes.fromhex(io.recvline().strip().decode())

key = sha256(str(A + roots[0][x]).encode()).digest()

flag = AES.new(key, AES.MODE_ECB).decrypt(ct)
print(flag)

SU_Restaurant

from Crypto.Util.number import *
from Crypto.Util.Padding import *
from random import randint, choice, choices
from hashlib import sha3_512
from base64 import b64encode, b64decode
from secret import flag
import numpy as np
import json
import os
# import pty

H = lambda x: [int(y, 16) for y in [sha3_512(x).hexdigest()[i:i+2] for i in range(0, 128, 2)]]
alphabet = "".join([chr(i) for i in range(33, 127)])

class Point:
    def __init__(self, x):
        if isinstance(x, float):
            raise ValueError("...")
        while not isinstance(x, int):
            x = x.x
        self.x = x

    def __add__(self, other):
        if isinstance(other, int):
            return self.x + other
        return Point(min(self.x, other.x))

    def __radd__(self, other):
        if isinstance(other, int):
            return self.x + other
        return Point(min(self.x, other.x))

    def __mul__(self, other):
        return Point(self.x + other.x)

    def __eq__(self, other):
        return self.x == other.x

    def __repr__(self):
        return f"{self.x}"

    def __int__(self):
        return self.x


class Block:
    def __init__(self, n, m, data=None):
        self.n = n
        self.m = m
        if data and (len(data) != n or len(data[0]) != m):
            raise ValueError("...")
        if data:
            if isinstance(data, Point):
                self.data = [[Point(data[i][j].x) for j in range(m)] for i in range(n)]
            else:
                self.data = [[Point(data[i][j]) for j in range(m)] for i in range(n)]
        else:
            self.data = [[Point(randint(0, 255)) for _ in range(m)] for _ in range(n)]

    def __add__(self, other):
        return Block(self.n, self.m, [[self.data[i][j] + other.data[i][j] for j in range(self.m)] for i in range(self.n)])

    def __mul__(self, other):
        assert self.m == other.n, "😭"
        res = [[Point(511) for _ in range(other.m)] for _ in range(self.n)]
        for i in range(self.n):
            for j in range(other.m):
                for k in range(self.m):
                    res[i][j] = res[i][j] + (self.data[i][k] * other.data[k][j])

        return Block(self.n, other.m, res)

    def __eq__(self, other):
        res = True
        for i in range(self.n):
            for j in range(self.m):
                res = res and self.data[i][j] == other.data[i][j]
        return res

    def __getitem__(self, item):
        return self.data[item]

    def __repr__(self):
        return f"{self.data}"

    def legitimacy(self, lb, rb):
        for i in range(self.n):
            for j in range(self.m):
                if not (lb <= int(self.data[i][j].x) <= rb):
                    return False
        return True

class Restaurant:
    def __init__(self, m, n, k):
        self.m, self.n, self.k = m, n, k
        self.chef = Block(m, k)
        self.cooker = Block(k, n)
        self.fork = self.chef * self.cooker

    def cook(self, msg):
        if isinstance(msg, str):
            msg = msg.encode()
        tmp = H(msg)
        M = Block(self.n, self.m, [[tmp[i * self.m + j] for j in range(self.m)] for i in range(self.n)])
        while True:
            U = Block(self.n, self.k)
            V = Block(self.k, self.m)
            P = self.chef * V
            R = U * self.cooker
            S = U * V
            A = (M * self.chef) + U
            B = (self.cooker * M) + V
            if A != U and B != V:
                break
        return A, B, P, R, S

    def eat(self, msg, A, B, P, R, S):
        if isinstance(msg, str):
            msg = msg.encode()
        tmp = H(msg)
        M = Block(self.n, self.m, [[tmp[i * self.m + j] for j in range(self.m)] for i in range(self.n)])
        Z = (M * self.fork * M) + (M * P) + (R * M) + S
        W = A * B
        legal = A.legitimacy(0, 256) and B.legitimacy(0, 256) and P.legitimacy(0, 256) and R.legitimacy(0, 256) and S.legitimacy(0, 256)
        return W == Z and W != S and legal


banner = """=================================================================
 ____  _   _   ____           _                              _   
/ ___|| | | | |  _ \ ___  ___| |_ __ _ _   _ _ __ __ _ _ __ | |_ 
\___ \| | | | | |_) / _ \/ __| __/ _` | | | | '__/ _` | '_ \| __|
 ___) | |_| | |  _ <  __/\__ \ || (_| | |_| | | | (_| | | | | |_ 
|____/ \___/  |_| \_\___||___/\__\__,_|\__,_|_|  \__,_|_| |_|\__|
=================================================================
"""

menu = """Do something...
[1] Say to the waiter: "Please give me some food."
[2] Say to the waiter: "Please give me the FLAG!"
[3] Check out
What do you want to do? 
>>> """

foodlist = ["Spring rolls", "Red Rice Rolls", "Chencun Rice Noodles", "Egg Tart", "Cha siu bao"]
table = []

def main():
    print(banner)
    SU_Restaurant = Restaurant(8, 8, 7)

    havefork = False
    try:
        while True:
            op = int(input(menu))
            if op == 1:
                if len(table) == 2:
                    print("You're full and don't want to order more...")
                    continue
                foodname = choice(foodlist)
                while foodname in table:
                    foodname = choice(foodlist)
                print(f'The waiter says: "Here is your {foodname}!"')
                table.append(foodname)
                A, B, P, R, S = SU_Restaurant.cook(foodname)
                print(f'A = {A}\nB = {B}\nP = {P}\nR = {R}\nS = {S}')

            elif op == 2:
                Fo0dN4mE = "".join(choices(alphabet, k=36))
                print(f'The waiter says: "Please make {Fo0dN4mE} for me!"')
                res = json.loads(input(">>> "))
                r1 = np.linalg.matrix_rank(np.array(res["A"]))
                r2 = np.linalg.matrix_rank(np.array(res["B"]))
                r3 = np.linalg.matrix_rank(np.array(res["P"]))
                r4 = np.linalg.matrix_rank(np.array(res["R"]))
                r5 = np.linalg.matrix_rank(np.array(res["S"]))

                if r1 < 7 or r2 < 7 or r3 < 8 or r4 < 8 or r5 < 8:
                    print('The waiter says: "These are illegal food ingredients"')
                    continue

                A = Block(8, 7, res["A"])
                B = Block(7, 8, res["B"])
                P = Block(8, 8, res["P"])
                R = Block(8, 8, res["R"])
                S = Block(8, 8, res["S"])
                if SU_Restaurant.eat(Fo0dN4mE, A, B, P, R, S):
                    print(f'The waiter says: "Here is the FLAG: {flag}"')
                else:
                    print('The waiter says: "This is not what I wanted!"')
                    exit(0)

            elif op == 3:
                print('The waiter says: "Welcome to our restaurant next time!"')
                break
            else:
                print("Invalid option!")
    except:
        print("Something wrong...")
        exit(0)

if __name__ == "__main__":
    main()

上述代码实现了Tropical cryptography IV: Digital signatures and secret sharing with arbitrary access structure一文中实现的基于热带代数的数字签名算法，该签名算法流程如下：

首先选取一个\(m\times k\)的随机热带矩阵\(X\)以及一个\(k\times n\)的随机热带矩阵\(Y\)，计算\(T=XY\)，并将明文计算为一个\(n\times m\)的哈希矩阵\(M\)，之后选取一个\(n\times k\)的随机热带矩阵\(U\)以及一个\(k\times m\)的随机热带矩阵\(V\)，记\(P=X\otimes V,R=U\otimes Y,S=U\otimes V\)，满足\((M\otimes X)\oplus U\neq U,(Y\otimes M)\oplus V\neq V\)，最后得到签名五元组：\(((M\otimes X)\oplus U,(Y\otimes M)\oplus V,P,R,S)\)

而该算法的验签流程如下：

对于获得的签名五元组：\(((M\otimes X)\oplus U,(Y\otimes M)\oplus V,P,R,S)\)，计算：

$$
Z=(M\otimes T\otimes M)\oplus (M\otimes P)\oplus(R\otimes M)\oplus S
$$

判断\(Z\)是否等于\([(M\otimes X)\oplus U]\otimes[(Y\otimes M)\oplus V]\)，若相等则验证成功，否则验证失败。

对于这个签名，在A Comprehensive Break of the Tropical Matrix-Based Signature Scheme一文（中提到可以通过获取两次签名来构造方程，我们记第\(i(i=1,2)\)次获得的签名为\((A_i,B_i,P_i,R_i,S_i)\)，将\(X,Y,U_i,V_i\)的所有元素作为\([0,255]\)中的未知量可以得到方程：

$$
\begin{cases}
A_i=(M_i\otimes X)\oplus U_i\\
B_i=(Y\otimes M_i)\oplus V_i\\
P_i=X\otimes V_i\\
R_i=U_i\otimes Y\\
S_i=U_i\otimes V_i\\
\end{cases}
$$

对于热带代数中的加法\(a\oplus b=c\)，我们可以用下面的关系进行替代：

$$
[(a\le c)\wedge(b\le c)]\wedge[(a=c)\vee(b=c)]
$$

通过这种方式可以将上述热带矩阵方程改写为z3可以求解的方程，从而求解出私钥，最后对靶机提供的长度为36的字符串进行签名得到flag（以下脚本由AI辅助生成）：

from pwn import *
from z3 import *
from hashlib import sha3_512
import json
import random
import sys

context.log_level = 'info'

M_DIM, N_DIM, K_DIM = 8, 8, 7


def get_M(msg: str):
    h = sha3_512(msg.encode()).hexdigest()
    v = [int(h[i:i + 2], 16) for i in range(0, 128, 2)]
    return [[v[i * M_DIM + j] for j in range(M_DIM)] for i in range(N_DIM)]


def minplus_mul(A, B):
    n, m, p = len(A), len(A[0]), len(B[0])
    return [[min(A[i][k] + B[k][j] for k in range(m)) for j in range(p)] for i in range(n)]


def minplus_add(A, B):
    return [[min(A[i][j], B[i][j]) for j in range(len(A[0]))] for i in range(len(A))]


def parse_matrix(io, name: bytes):
    io.recvuntil(name + b" = ")
    return eval(io.recvline().decode().strip())


def add_minplus_eq_const(s, out_const, left, right):
    n, mid, p = len(left), len(left[0]), len(right[0])
    for i in range(n):
        for j in range(p):
            terms = [left[i][t] + right[t][j] for t in range(mid)]
            for t in terms:
                s.add(out_const[i][j] <= t)
            s.add(Or([out_const[i][j] == t for t in terms]))


def add_minplus_eq_var(s, out_var, left, right):
    n, mid, p = len(left), len(left[0]), len(right[0])
    for i in range(n):
        for j in range(p):
            terms = [left[i][t] + right[t][j] for t in range(mid)]
            for t in terms:
                s.add(out_var[i][j] <= t)
            s.add(Or([out_var[i][j] == t for t in terms]))


def recv_two_signatures(io):
    sigs = []
    for _ in range(2):
        io.sendlineafter(b">>> ", b"1")
        io.recvuntil(b"Here is your ")
        msg = io.recvuntil(b"!")[:-1].decode()
        A = parse_matrix(io, b"A")
        B = parse_matrix(io, b"B")
        P = parse_matrix(io, b"P")
        R = parse_matrix(io, b"R")
        S = parse_matrix(io, b"S")
        sigs.append((msg, A, B, P, R, S))
    return sigs


def recover_keys(sigs):
    s = Solver()
    chef = [[Int(f"chef_{i}_{j}") for j in range(K_DIM)] for i in range(M_DIM)]
    cooker = [[Int(f"cooker_{i}_{j}") for j in range(N_DIM)] for i in range(K_DIM)]

    for i in range(M_DIM):
        for j in range(K_DIM):
            s.add(chef[i][j] >= 0, chef[i][j] <= 255)
    for i in range(K_DIM):
        for j in range(N_DIM):
            s.add(cooker[i][j] >= 0, cooker[i][j] <= 255)

    for idx, (msg, A, B, P, R, S_mat) in enumerate(sigs):
        M = get_M(msg)
        Mz = [[IntVal(M[i][j]) for j in range(M_DIM)] for i in range(N_DIM)]
        U = [[Int(f"U_{idx}_{i}_{j}") for j in range(K_DIM)] for i in range(N_DIM)]
        V = [[Int(f"V_{idx}_{i}_{j}") for j in range(M_DIM)] for i in range(K_DIM)]

        for i in range(N_DIM):
            for j in range(K_DIM):
                s.add(U[i][j] >= 0, U[i][j] <= 255)
        for i in range(K_DIM):
            for j in range(M_DIM):
                s.add(V[i][j] >= 0, V[i][j] <= 255)

        T1 = [[Int(f"T1_{idx}_{i}_{j}") for j in range(K_DIM)] for i in range(N_DIM)]
        add_minplus_eq_var(s, T1, Mz, chef)
        for i in range(N_DIM):
            for j in range(K_DIM):
                s.add(A[i][j] <= T1[i][j], A[i][j] <= U[i][j])
                s.add(Or(A[i][j] == T1[i][j], A[i][j] == U[i][j]))

        T2 = [[Int(f"T2_{idx}_{i}_{j}") for j in range(M_DIM)] for i in range(K_DIM)]
        add_minplus_eq_var(s, T2, cooker, Mz)
        for i in range(K_DIM):
            for j in range(M_DIM):
                s.add(B[i][j] <= T2[i][j], B[i][j] <= V[i][j])
                s.add(Or(B[i][j] == T2[i][j], B[i][j] == V[i][j]))

        add_minplus_eq_const(s, P, chef, V)
        add_minplus_eq_const(s, R, U, cooker)
        add_minplus_eq_const(s, S_mat, U, V)

    if s.check() != sat:
        raise ValueError("UNSAT")
    m = s.model()
    chef_val = [[m[chef[i][j]].as_long() for j in range(K_DIM)] for i in range(M_DIM)]
    print(chef_val)
    cooker_val = [[m[cooker[i][j]].as_long() for j in range(N_DIM)] for i in range(K_DIM)]
    return chef_val, cooker_val


def main():
    io = remote("101.245.107.149", 10020)
    sigs = recv_two_signatures(io)
    log.success("got 2 signatures")

    chef, cooker = recover_keys(sigs)
    log.success("recovered chef/cooker")

    io.sendlineafter(b">>> ", b"2")
    io.recvuntil(b"Please make ")
    target = io.recvuntil(b" for me!")[:-8].decode()
    M = get_M(target)

    while True:
        U = [[random.randint(0, 255) for _ in range(K_DIM)] for _ in range(N_DIM)]
        V = [[random.randint(0, 255) for _ in range(M_DIM)] for _ in range(K_DIM)]
        P = minplus_mul(chef, V)
        R = minplus_mul(U, cooker)
        S = minplus_mul(U, V)
        A = minplus_add(minplus_mul(M, chef), U)
        B = minplus_add(minplus_mul(cooker, M), V)
        if A != U and B != V:
            break

    payload = {"A": A, "B": B, "P": P, "R": R, "S": S}
    io.sendline(json.dumps(payload).encode())
    io.interactive()


if __name__ == "__main__":
    main()

CryptoIsogeny格密码
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇