GHCTF2025 WriteUp

摘要

本文是GHCTF2025的WriteUp，三人组队，Crypto和Reverse已经全部复现。

赛时 WriteUp

GHCTF2025 WriteUp

Reverse

Room0 | REVIEW

如果直接分析得到的flag是NSSCTF{FAKE_FAKE_FAKE_FAKE_FAKE}，看看汇编会发现这里有个异常处理机制，不难定位到检测key的函数中，可能触发除零异常。

为了反编译异常处理的代码，直接把中间的这部分代码nop掉，这样原来程序的结尾就能接上异常处理的代码。

我把第一个函数重命名为unhex，例如把字符串"12345678"变成0x12345678返回。

第二个函数（SMC）手动去掉3个花指令，第三个函数是等待解密的函数。

注意到SMC函数需要key作为参数。如果这时候回头利用除零异常直接爆破会得到大量解。

看看SMC函数，将key逆序后对代码段异或解密，注意到 KEY = 加密代码 XOR 解密代码，加密代码有现成的，如果我猜出来代码段部分字节，就能推导出部分KEY。

如果了解函数调用的堆栈原理的话可能会想到，正常的函数一开始都有这两行汇编。

55      push    ebp
8B EC   mov     ebp, esp

这样KEY的三个字节都有了，因为SMC有个KEY逆序，未知字节是原来KEY第一个字节，即KEY个位。

20 D4 1C XOR 55 8B EC == 75 5F F0

那就爆破 0x755FF000 ~ 0x755FF0FF 即可，改一下检测密钥函数，去掉unhex直接接受int。

int __cdecl sub_402000(int v2)
{
    int i;           // [esp+4h] [ebp-18h]
    int v4;          // [esp+8h] [ebp-14h]
    int v5;          // [esp+Ch] [ebp-10h]
    int v6;          // [esp+10h] [ebp-Ch]
    int v7;          // [esp+10h] [ebp-Ch]
    unsigned int v8; // [esp+14h] [ebp-8h]
    int v9;          // [esp+18h] [ebp-4h]

    v6 = 0;
    v9 = v2;
    v8 = HIBYTE(v2);
    v5 = BYTE2(v2);
    v4 = BYTE1(v2);
    for (i = 0; i < 32; ++i)
    {
        v7 = v6 * (v8 + 1415881080) * (v9 - 1467486175) * ((v8 - v9) ^ (v8 >> 4));
        v5 = (v9 + v5) ^ (8 * v4);
        v4 = (v9 + v8) ^ (8 * v5);
        v8 = (v9 + v4) ^ (8 * v5);
        v9 -= v4 + v5 + v8;
        if (v9 == 1415881080)
        {
            printf("key found: %x\n", v2);
            return 0;
        }
        v6 = v7 + (v8 + 1467486175) * (((v8 - v9) ^ (unsigned __int64)(v8 >> 4)) / (unsigned int)(v9 - 1415881080));
    }
    return v9 ^ v6;
}

得到密钥755FF0D3，接下来就输入密钥，在SMC函数结束后的地方下断点，动态调试直到解密完成。

Welcome to the hostel!
Please input your informatioin to enter your room.
Input your flag:1111111111111111111111111111111111111111111111111
Input your Key:755FF0D3

把这几个花指令处理一下

去除后就能看到代码了，又是异或，那可真是太棒了，到这里读一下a2的值0xF86D35D4，直接照抄代码，Str替换成密文，异或出来就是明文了。

NSSCTF{Int3r3st1ng_5MC_Pr0gr@m?}

ezObfus | REVIEW

进去先去除一大堆的花指令，把main反编译出来。

代码中有很多混淆手段：

1. 每个字符串常量如"Password"都被加密了，只能动态调试。
2. 有很多关于小数的判断，实际上都是里面的核心代码都能正常运行。
3. 许多条件判断、整数都被复杂化，0~9等常量需要重命名，条件、循环的判断语句加入了函数、三元运算符复杂化代码。
   例如 i += sub_9E4190(1)，函数返回 0 * (2 * 1 - 6) + a1 * 1，还是1本身。

提取核心代码就是：

int main()
{
    // 00 00 00 00 54 55 79 9E  A8 E1 1C DA 04 1D C1 6E
    // 80 82 0D 8A 4C 65 E1 46  71 31 ED D2 14 C5 39 B5
    // 49 E2 04 A9 00 00 00 00  00 00 00 00 00 00 00 00
    unsigned char enc_flag[33] = {
        0x54, 0x55, 0x79, 0x9E, 0xA8, 0xE1, 0x1C, 0xDA,
        0x04, 0x1D, 0xC1, 0x6E, 0x80, 0x82, 0x0D, 0x8A,
        0x4C, 0x65, 0xE1, 0x46, 0x71, 0x31, 0xED, 0xD2,
        0x14, 0xC5, 0x39, 0xB5, 0x49, 0xE2, 0x04, 0xA9, 0x00};
    unsigned char flag[0x100];
    unsigned int key;
    unsigned char v76;

    printf("Password:");
    scanf("%d", &key);
    printf("%d\n", key);

    unsigned int key_hash = 0x811C9DC5;
    for (int i = 0; i < 4; i++)
    {
        v76 = key >> (i * 8);
        if (v76 % 2)
            key_hash ^= v76;
        else
            key_hash *= 0x1000193;

        key_hash = (key_hash >> 25) | (key_hash << 7);
        key_hash -= v76;
    }

    if (key_hash != 1172912374) // 0x45E938F6
    {
        printf("Wrong Password!");
        return 0;
    }

    memset(flag, 0, 0x100u);
    printf("Flag:");
    scanf("%s", flag);

    for (i = 0; i < 32; i++)
    {
        flag[i] ^= 0x48;
    }

    for (i = 0; i < 32; i++)
    {
        flag[i] ^= i ^ (key >> ((3 - i % 4) * 8));
        flag[i] = (flag[i] >> 5) | (flag[i] << 3);
        flag[i] += i;
    }

    if (!strcmp(enc_flag, flag))
    {
        printf("Correct Flag");
    }
    else
    {
        printf("Wrong Flag");
    }

    return 0;
}

把key先爆破出来，0x8c90f77b，%d格式就是-1936656517。

直接逆向：

int main()
{

    unsigned char flag[33] = {
        0x54, 0x55, 0x79, 0x9E, 0xA8, 0xE1, 0x1C, 0xDA,
        0x04, 0x1D, 0xC1, 0x6E, 0x80, 0x82, 0x0D, 0x8A,
        0x4C, 0x65, 0xE1, 0x46, 0x71, 0x31, 0xED, 0xD2,
        0x14, 0xC5, 0x39, 0xB5, 0x49, 0xE2, 0x04, 0xA9, 0x00};

    unsigned int key = 0x8c90f77b;

    // key = 0x8c90f77b; // -1936656517
    for (i = 0; i < 32; i++)
    {
        flag[i] -= i;
        flag[i] = (flag[i] >> 3) | (flag[i] << 5);
        flag[i] ^= i ^ (key >> ((3 - i % 4) * 8));
        flag[i] ^= 0x48;
    }
    printf("%s\n", flag);

    return 0;
}

腐蚀 | REVIEW

加密图片的题目，程序还是比较麻烦的。

从后面反向追踪变量，这个带v44 v45 v47的应该就是加密函数了，v44是输出，v45是key，v47是输入的图片。

v33在之前虽然多次出现，但看代码不像是做了加密，key需要动态调试获得。

在函数调试里面得到 60 82 AE 42 4E 44 49 45 1A 0A 0D 0A 4E 47 89 50

rust的内存分配机制可能跟C语言不太一样，有的变量找起来挺麻烦的。

这个加密函数是RC4加密，这是初始化S盒。

后面的是加密部分，还异或了0x1f。

这个加密函数后面还有个东西

查看细节发现，是逆向字节

解密脚本：

// 60 E3 22 D8 2A 73 C2 0E  30 B7 95 04 15 DA AD 56
// 7C D5 CF 76 86 DF 1A 83  E7 EF AE 3B DC 58 A0 11
// 89 32 29 61 9D 2E D9 0F  A1 81 92 6B 45 D3 10 EB
// 53 44 0C 34 72 A2 98 C0  0A C5 9F FA BB D4 FB 69
// DD D1 4C 21 A3 41 68 47  A9 FC 23 9E 28 2C 87 3D
// 4D C3 82 39 0D F4 9B AB  F9 36 CD DB A6 08 1B E0
// 4E 67 55 8D 8A 62 E2 5D  F0 88 B6 C7 5B 49 51 2F
// 16 70 75 BC 7E 37 C1 59  D6 C4 8E D0 6C F2 19 BE
// AF 93 6E 9A 05 B2 25 26  BD B3 17 B4 2B 99 F5 1F
// 57 96 6F 1E 5C 5A 84 14  EA 03 B1 8C 00 AA 7A BF
// 06 E5 4A 46 0B 1D 85 DE  8F EC C8 FE F8 01 3E E1
// FD CE 5E 64 2D 97 1C 43  91 13 A4 CA E9 F7 3C 27
// 38 D2 C6 33 77 80 54 20  A5 E4 94 5F 90 F6 4B 24
// EE 78 E8 50 BA 09 B5 B9  66 4F 6A 7D 42 ED 31 FF
// 7F 7B C9 AC 63 40 48 74  B0 35 B8 07 E6 9C CC 79
// 18 F3 6D 12 71 A8 8B 02  3F D7 65 52 A7 F1 CB 3A
unsigned char S_box[256] = {
    0x60, 0xE3, 0x22, 0xD8, 0x2A, 0x73, 0xC2, 0x0E,
    0x30, 0xB7, 0x95, 0x04, 0x15, 0xDA, 0xAD, 0x56,
    0x7C, 0xD5, 0xCF, 0x76, 0x86, 0xDF, 0x1A, 0x83,
    0xE7, 0xEF, 0xAE, 0x3B, 0xDC, 0x58, 0xA0, 0x11,
    0x89, 0x32, 0x29, 0x61, 0x9D, 0x2E, 0xD9, 0x0F,
    0xA1, 0x81, 0x92, 0x6B, 0x45, 0xD3, 0x10, 0xEB,
    0x53, 0x44, 0x0C, 0x34, 0x72, 0xA2, 0x98, 0xC0,
    0x0A, 0xC5, 0x9F, 0xFA, 0xBB, 0xD4, 0xFB, 0x69,
    0xDD, 0xD1, 0x4C, 0x21, 0xA3, 0x41, 0x68, 0x47,
    0xA9, 0xFC, 0x23, 0x9E, 0x28, 0x2C, 0x87, 0x3D,
    0x4D, 0xC3, 0x82, 0x39, 0x0D, 0xF4, 0x9B, 0xAB,
    0xF9, 0x36, 0xCD, 0xDB, 0xA6, 0x08, 0x1B, 0xE0,
    0x4E, 0x67, 0x55, 0x8D, 0x8A, 0x62, 0xE2, 0x5D,
    0xF0, 0x88, 0xB6, 0xC7, 0x5B, 0x49, 0x51, 0x2F,
    0x16, 0x70, 0x75, 0xBC, 0x7E, 0x37, 0xC1, 0x59,
    0xD6, 0xC4, 0x8E, 0xD0, 0x6C, 0xF2, 0x19, 0xBE,
    0xAF, 0x93, 0x6E, 0x9A, 0x05, 0xB2, 0x25, 0x26,
    0xBD, 0xB3, 0x17, 0xB4, 0x2B, 0x99, 0xF5, 0x1F,
    0x57, 0x96, 0x6F, 0x1E, 0x5C, 0x5A, 0x84, 0x14,
    0xEA, 0x03, 0xB1, 0x8C, 0x00, 0xAA, 0x7A, 0xBF,
    0x06, 0xE5, 0x4A, 0x46, 0x0B, 0x1D, 0x85, 0xDE,
    0x8F, 0xEC, 0xC8, 0xFE, 0xF8, 0x01, 0x3E, 0xE1,
    0xFD, 0xCE, 0x5E, 0x64, 0x2D, 0x97, 0x1C, 0x43,
    0x91, 0x13, 0xA4, 0xCA, 0xE9, 0xF7, 0x3C, 0x27,
    0x38, 0xD2, 0xC6, 0x33, 0x77, 0x80, 0x54, 0x20,
    0xA5, 0xE4, 0x94, 0x5F, 0x90, 0xF6, 0x4B, 0x24,
    0xEE, 0x78, 0xE8, 0x50, 0xBA, 0x09, 0xB5, 0xB9,
    0x66, 0x4F, 0x6A, 0x7D, 0x42, 0xED, 0x31, 0xFF,
    0x7F, 0x7B, 0xC9, 0xAC, 0x63, 0x40, 0x48, 0x74,
    0xB0, 0x35, 0xB8, 0x07, 0xE6, 0x9C, 0xCC, 0x79,
    0x18, 0xF3, 0x6D, 0x12, 0x71, 0xA8, 0x8B, 0x02,
    0x3F, 0xD7, 0x65, 0x52, 0xA7, 0xF1, 0xCB, 0x3A};
#include 
#include 

int main()
{
    FILE *input_file, *output_file;
    long file_size; // 文件大小
    unsigned char byte;

    input_file = fopen("enc", "rb");
    output_file = fopen("Input.png", "wb");

    // 获取文件大小
    fseek(input_file, 0, SEEK_END); // 移动到文件末尾
    file_size = ftell(input_file);  // 获取文件指针的位置（即文件大小）

    int i = 0, j = 0, i0, j0, t = 0;
    for (i0 = 0xC695; i0 >= 0; i0--)
    {
        fseek(input_file, i0, SEEK_SET);
        fread(&byte, 1, 1, input_file);

        i = (i + 1) % 256;
        j = (j + S_box[i]) % 256;
        unsigned char temp = S_box[i];
        S_box[i] = S_box[j];
        S_box[j] = temp;
        byte ^= S_box[(S_box[i] + S_box[j]) % 256] ^ 0x1F;
        fwrite(&byte, 1, 1, output_file);
    }

    fclose(input_file);
    fclose(output_file);

    printf("处理完成！结果已保存到 %s\n", "Input.png");
    return 0;
}

看出题人的WP，学了一手CyberChef。

Crypto | REVIEW

baby_signin

e = 4 跟 phi 不互素，那就直接开根了。

from Crypto.Util.number import *
from sympy.ntheory.residue_ntheory import sqrt_mod
from sympy.ntheory.modular import crt

p = 182756071972245688517047475576147877841
q = 305364532854935080710443995362714630091
c = 14745090428909283741632702934793176175157287000845660394920203837824364163635
n = 55807222544207698804941555841826949089076269327839468775219849408812970713531
e = 4
n = p * q
phi = (p - 1) * (q - 1)
M4 = c

for M2_p in sqrt_mod(M4, p, all_roots=True):
    for m1 in sqrt_mod(M2_p, p, all_roots=True):
        for M2_q in sqrt_mod(M4, q, all_roots=True):
            for m2 in sqrt_mod(M2_q, q, all_roots=True):
                m = crt([p, q], [m1, m2])[0]
                m = long_to_bytes(m)
                if m.startswith(b"NSSCTF{"):
                    print(m)
# b'NSSCTF{4MM_1s_so_e4s7!}'

baby_factor

信息都透完了，直接算。

from Crypto.Util.number import *

n = ...
phi = ...
c = ...
e = 65537
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
# b'NSSCTF{W0W!!_Y0u_4r3_g00d_G03!!!}'

EZ_Fermat

根据题意 $w \equiv 2^{f(p)} \mod N$ ，那如果我能根据 $f(p)$ ，找到一个常数C，使得 $w \equiv 2^c \mod p$ 取最大公因数就能解出p了。

根据欧拉定理：$f(p)-C=k(p-1)$ ，设 $C=f(x)$ 就，$f(p)-f(x)= \sum a_n(p^n-x)$，不难发现 $x=1$ 时因式分解就是p-1的倍数，所以 $C=f(1)$ 是符合要求的。

from Crypto.Util.number import *
n = ...
e = 65537
c = ...
w = ...

# 定义多项式环
f = ...

R. = ZZ[]
f = R(str(f))
C = f(1)
print(C)

p = gcd(pow(2,int(C),n)-w, n)
q = n // int(p)
assert p*q==n
phi = (p-1)*(q-1)
d = inverse(e, int(phi))
m = pow(c, d, n)
print(long_to_bytes(int(m)))
# b'NSSCTF{8d1e3405044a79b23a44a43084bd994b}'

baby_factor_revenge

参考了博客：https://blog.csdn.net/AxuAxuA123/article/details/141454579

二元的pq和phi解方程就行，那怎么解三元的呢？根据欧拉定理 $a^{\phi(N)} - 1 \equiv 0 \mod N \\$ ，我们尝试对 $a^{\phi(N)} - 1$因式分解，这些因式一定包括了p、q、r，而且很有可能p、q、r不同时出现在同一因式，这就意味着如果其中存在一个因式仅包含了r不包括pq，只要把这个因式和N取GCD就解出r了。$\phi(N)=2^t \cdot s$，s为奇数，利用平方差公式就可以将其分解为多个因式。

from Crypto.Util.number import *
import random
from math import gcd, isqrt
from sympy import symbols, Eq, solve


def factor_n_with_phi(n: int, phi_n: int, max_attempts=10):
    t = 0
    s = phi_n
    while s % 2 == 0:
        s = s // 2
        t += 1
    for _ in range(max_attempts):
        a = random.randint(0, n - 1)
        current = pow(a, s, n)
        for n_exp in range(t):
            exponent = s * (2 ** (t - n_exp))
            current = pow(a, exponent, n)
            r = gcd(current + 1, n)
            if r == 1:
                continue
            elif r >= n:
                break
            else:
                return r
    return None


n = ...
phi = ...
c = ...

r = factor_n_with_phi(n, phi, 10)
assert n % r == 0
n //= r
phi //= r - 1

x, y = symbols("p q")
solutions = solve((Eq(x + y, n - phi + 1), Eq(x * y, n)), (x, y))
p, q = solutions[0]
p, q = int(p), int(q)

p, q, r = sorted([p, q, r])
n = p * q
phi = (p - 1) * (q - 1)
e = 65537
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
# b'NSSCTF{D0_Y0u_knnn0www_p71!!!}'

RSA_and_DSA

先用低解密指数攻击（wiener攻击或BD攻击 ）获取ink，再破掉DSA的私钥。

from random import getrandbits, randint
from secrets import randbelow
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
import hashlib
import random
import gmpy2

c_ink = ...
e = ...
N = ...
(r1, s1) = ...
(r2, s2) = ...
g = ...
q = ...
p = ...
y = ...

d = 1051176891915773585468122074232642482031663118639646043742447
ink = pow(c_ink, d, N)
print(pow(ink, e, N) == c_ink)

msg = b"GHCTF-2025"
h = int(hashlib.sha256(msg).digest().hex(), 16)
pri = (h * s1 - h * s2 - ink * s1 * s2) * inverse(r1 * s2 - r2 * s1, q) % q

ciphertext = (
    b"\xb0\ra\x9c\xeb9y\xd5k\xfde\xdfJ\xba\n\xce^u\xae\x81J8\xe4\x8da\xdf;H@WV5"
)
key = hashlib.sha1(str(pri).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_ECB)
flag = "NSSCTF{xxxxxxxxx}"
plaintext = cipher.decrypt(ciphertext)
print(plaintext)
# b'NSSCTF{n0_RRRrs4_or_DDDS4????}\x02\x02'

baby_lattice

LHNP问题，脚本直接抄https://hasegawaazusa.github.io/hidden-number-problem.html

from Crypto.Util.number import *
from Crypto.Cipher import AES

p = ...
ts = ...
gs = ...

p = p
rs = ts
cs = gs
t = len(rs)
kbits = 400
K = 2 ** kbits

P = identity_matrix(t) * p
RC = matrix([[-1, 0], [0, 1]]) * matrix([rs, cs])
KP = matrix([[K / p, 0], [0, K]])
M = block_matrix([[P, 0], [RC, KP]], subdivide=False)
shortest_vector = M.LLL()
x = shortest_vector[1, -2] / K * p % p

iv=b'\x88\x0c\x7f\x92\xd7\xb7\xaf4\xe4\xfb\xd1_\xab\xff)\xb8'
ciphertext=b'\x94\x198\xd6\xa2mK\x00\x06\x7f\xad\xa0M\xf7\xadV;EO$\xee\xcdB0)\xfb!&8%,M'
cipher = AES.new(str(x).encode()[:16], AES.MODE_CBC,iv)
plaintext=cipher.decrypt(ciphertext)
print(plaintext)
# b'NSSCTF{F@@@un7_L4444t1c3333!!}\x02\x02'

MIMT_RSA

题目名字打错了，应该是MITM中间攻击的思路，就是对于 $f(m)=c$ 爆破m很困难，如果能把m分成两段，令 $m=m_1\cdot m_2$，并且能把问题转化为 $g(m_1)=h(m_2)$ 的形式，那么只需要先爆破m₁，把所有可能的 $g(m_1)$ 存起来，再爆破m₂，看看 $h(m_1)$ 是不是在里面。时间复杂度缩减为 $O(\sqrt n)$ 。

KEY虽然小，但e大，也没法用小明文攻击。这道题提示很明显，KEY不是质数，那不就是分解KEY吗

$m_1^e \equiv ck\cdot m_2^{-e} \mod n$

from Crypto.Util.number import *
import time
from hashlib import md5

n = 26563847822899403123579768059987758748518109506340688366937229057385768563897579939399589878779201509595131302887212371556759550226965583832707699167542469352676806103999861576255689028708092007726895892953065618536676788020023461249303717579266840903337614272894749021562443472322941868357046500507962652585875038973455411548683247853955371839865042918531636085668780924020410159272977805762814306445393524647460775620243065858710021030314398928537847762167177417552351157872682037902372485985979513934517709478252552309280270916202653365726591219198063597536812483568301622917160509027075508471349507817295226801011
e = 65537
ck = 8371316287078036479056771367631991220353236851470185127168826270131149168993253524332451231708758763231051593801540258044681874144589595532078353953294719353350061853623495168005196486200144643168051115479293775329183635187974365652867387949378467702492757863040766745765841802577850659614528558282832995416523310220159445712674390202765601817050315773584214422244200409445854102170875265289152628311393710624256106528871400593480435083264403949059237446948467480548680533474642869718029551240453665446328781616706968352290100705279838871524562305806920722372815812982124238074246044446213460443693473663239594932076
KEY = 0
e_inv = inverse(e, n)

start_time = time.time()
dict_temp = {}
for m1 in range(262144):
    dict_temp[pow(m1, e, n)] = m1
t1 = time.time() - start_time
print(f"Time taken to create dictionary: {t1} seconds")

start_time = time.time()
for m2 in range(262144, 68719476736):
    try:
        temp = (ck * pow(m2, -e, n)) % n
        if temp in dict_temp:
            KEY = m2 * dict_temp[temp]
            print(f"Found key: {KEY}")
            break
    except:
        continue
t2 = time.time() - start_time
print(f"Time taken to brute force: {t2} seconds")

# KEY = 62495925932
assert ck == pow(KEY, e, n)
flag = b"NSSCTF{" + md5(str(KEY).encode()).hexdigest().encode() + b"}"
print(flag)
# b'NSSCTF{14369380f677abec84ed8b6d0e3a0ba9}'

这是我跑的时间：

# Time taken to create dictionary: 17.384088039398193 seconds
# Found key: 62495925932
# Time taken to brute force: 57.97086429595947 seconds
# b'NSSCTF{14369380f677abec84ed8b6d0e3a0ba9}'

交换一下m₁ m₂的位置，用时差不多。

$m_2^e \equiv ck\cdot m_1^{-e} \mod n$

Time taken to create dictionary: 38.08794832229614 seconds
Found key: 62495925932
Time taken to brute force: 34.84964156150818 seconds
b'NSSCTF{14369380f677abec84ed8b6d0e3a0ba9}'

Sin

先在高精度下求m的一个解mf，根据公式 $m=mf+2k\pi$​ 构造格：

受限于计算过程中的精度损失，这里的0不是真正的0，而是在相对于K2的数量级下的一个较小的数。

from Crypto.Util.number import *

R = RealField(1024)
r = R(0.002127416739298073705574696200593072466561264659902471755875472082922378713642526659977748539883974700909790177123989603377522367935117269828845667662846262538383970611125421928502514023071134249606638896732927126986577684281168953404180429353050907281796771238578083386883803332963268109308622153680934466412)

mf = arcsin((r / 4) ** (1 / 3))
p = mf.precision()
K1 = 2**400
K2 = 2**p
M = matrix(QQ, [[1, 0, K2 * 1], [0, K1, K2 * mf], [0, 0, K2 * 2 * pi.n(p)]])

for line in M.LLL():
    if abs(line[1]) == K1:
        print(float(line[2]))
        m = abs(int(line[0]))
        print(long_to_bytes(m))
# b'NSSCTF{just_make_a_latter_and_LLL_is_OK_padpad}'

EZ_Fermat_bag_PRO

和之前的差不多，不妨先设 $C=f(x,y)$ ，则 $f(p,q)-f(x,y)= \sum a_n(p^mq^n-x^my^n)$，首先得想办法把这个q提出去，y必须是q的倍数，我们能选用的就只有N了，$p^mq^n-x^mN^n=(p^m-x^mp^n)q^n$，显然只要令 $x=1$，问题就解决了，所以$C=f(1, n)$​。

算出p、q还没完，根据题目，c只是模p得到的，而flag确定共88位，全是数字，整理一下：$m=kp+C=m_{min}+\sum256^{i} \cdot x_i$

m_min表示全取零的m，x_i 是每位数字，根据这个等式 $\sum256^{i} \cdot x_i + (m_{min}-C)- kp=0$ 构造格：

 

按照预期，格基规约后会得到一串前80位小于10，后两位依次取1和0的最短向量。

from Crypto.Util.number import *

e = 65537
n = ...
w = ...
c = ...

P. = ZZ[]
f = ...

C = f(1, n)

p = int(gcd(pow(2,int(C),n)-w, n))
q = n // int(p)
print(p, q, int(p*q))
assert p*q==n

flag_min = b"NSSCTF{" + b"0" * 80 + b"}"
m_min = bytes_to_long(flag_min)

# print(m_min , c)
M = matrix.identity(82)
for i in range(80):
    M[i, -1] = int(256**(80-i))
M[-1, -1] = p
M[-2, -1] = m_min - c
# print(M)
for line in M.LLL():
    if abs(line[-1])==0 and abs(line[-2])==1:
        flag = "NSSCTF{"
        for i in range(80):
            flag += str(line[-2]*line[i])
        flag += "}"
        if len(flag) == 88:
            print(flag)
# NSSCTF{38886172735077060750460332815973614272222523052135584902884007925985948919714862}

river

本来是想利用算法的性质，直接推出一些位置的，发现这个方法好笨。看了一眼官方WP，学了一个叫剪枝的玩意。前几位是否符合要求是可以判断出来的。满足条件的有9000多，填满64位后，逆推一下seed，看看解出来的是不是符合要求。

from Crypto.Cipher import AES
from hashlib import md5

Init_pattern = "011______1______1_11_1__1__1_1_1__1________11___1_1_______1___11"
Result = "1011111110000000110110001110011000111111111011110011111111000010"
enc = b"\x03\xd1#\xb9\xaa5\xff3y\xba\xcb\x91`\x9d4p~9r\xf6i\r\xca\x03dW\xdb\x9a\xd2\xa6\xc6\x85\xfa\x19=b\xb2)5>]\x05,\xeb\xa0\x12\xa9\x1e"

mask = 9494051593829874780
output = 13799267741689921474
mask = [int(i) for i in bin(mask)[2:]]
current = []
Count = 0


def reState(current: list[64]):
    l = current[-1]
    for i in range(63):
        l ^= mask[i + 1] & current[i]
    current = [l] + current[:-1]
    return current


def cut(s: list):
    s_out = []
    p = -1
    for i in range(len(s)):
        if i == 0:
            s_out = [1]
        else:
            if s[i] == 1:
                p += 1
                s_out.append(s[p])
            elif s[i] == 0:
                s_out.append(s[p])
    s_out = "".join(str(i) for i in s_out)
    if s_out == Result[0 : len(s)]:
        return True
    else:
        return False


def check(current: list[64]):
    global Count
    Count += 1
    seed = current.copy()
    for _ in range(64):
        seed = reState(seed)
    seed = int("".join(str(i) for i in seed), 2)

    m = AES.new(key=md5(str(seed).encode()).digest(), mode=AES.MODE_ECB).decrypt(enc)
    if m.isascii():
        print(m)
        exit()


def dfs(position):
    if position == 64:
        if cut(current):
            check(current)
        return

    current.append(0)
    if cut(current):
        dfs(position + 1)
    current.pop()

    current.append(1)
    if cut(current):
        dfs(position + 1)
    current.pop()


current = []
dfs(len(current))
# b'flag{5b322a2b-8d15-43b3-88f0-ee1586f1cf4f}\x06\x06\x06\x06\x06\x06'