# Crew CTF 2025

## Misc - Bytecode Bonanza - Basics
> Python bytecode has many different opcodes, but how many opcodes do you really need? This challenge will teach you some of the concepts you need to tackle the RSA challenge.
> Author: Aali

Source chall:

import sys
import signal

assert((sys.version_info.major, sys.version_info.minor) == (3, 9))

signal.alarm(30)

FLAG = "crew{test flag please ignore}"

def dummy1(a):
  pass
def dummy2(a, b):
  pass
def dummy3(a, b, c):
  pass

dummies = [None, dummy1, dummy2, dummy3]

def create_function(parameters, prompt):
  bytecode = bytes.fromhex(input(prompt))
  
  if len(bytecode) > 512:
    print("Too long")
    exit()
  
  opcodes = [bytecode[i*2] + bytecode[i*2+1]*256 for i in range((len(bytecode)+1) // 2)]
  
  allowlist = [ 0x0001, 0x0004, 0x0006, 0x000f, 0x0017, 0x0190 ] + [0x0073 + i * 512 for i in range(128)]
  
  if any([op not in allowlist for op in opcodes]):
    print("Illegal opcode")
    exit()
  
  preamble = b"".join([bytes([0x7c, i]) for i in range(parameters)])
  
  code = preamble + bytecode + bytes([0x53, 0])
  
  dummy = dummies[parameters]
  
  dummy.__code__ = dummy.__code__.replace(co_code=code,co_stacksize=1000000000)
  
  return dummy

import secrets

subtract = create_function(2, "Enter a function which subtracts two numbers: ")

for i in range(10000):
  a = secrets.randbelow(2**32)
  b = secrets.randbelow(2**32)
  
  if subtract(a, b) != a - b:
    print("Nope")
    exit()

constant1337 = create_function(1, "Enter a function which always returns 1337: ")

for i in range(10000):
  if constant1337(secrets.randbelow(2**32)) != 1337:
    print("Nope")
    exit()

multiply = create_function(2, "Enter a function which multiplies two positive integers: ")

for i in range(10000):
  a = secrets.randbelow(255) + 1
  b = secrets.randbelow(255) + 1
  
  if multiply(a, b) != a * b:
    print("Nope")
    exit()

print(FLAG)

Ở bài này yêu cầu ta nhập vào chuỗi hex chính là dạng bytecode của python nhưng chỉ được dùng các lệnh đơn giản `POP_TOP, DUP_TOP, ROT_FOUR, UNARY_INVERT, BINARY_ADD, EXTENDED_ARG, POP_JUMP_FORWARD_IF_TRUE` để vượt qua 3 phần của challenge.

https://unpyc.sourceforge.net/Opcodes.html
Link trên là chi tiết các lệnh bytecode của python 3.9

Đầu tiên là bytecode hàm trừ nhận vào 2 tham số a, b trả về a - b:

Ta có: a - b = ~( ~(a) + b)
Vì ~( ~(a) + b) = ~(-1 - a + b) = ~(-1 - (a - b)) = -1 - (-1 - (a - b)) = -1 + 1 + (a - b) = a - b

Sau đó ta chuyển ~( ~(a) + b) sang dạng bytecode của python rồi là pass được part 1.

0f00  UNARY_INVERT     # [a, ~b]
1700  BINARY_ADD       # [a + ~b]
0400  DUP_TOP          # [res, res]
0400  DUP_TOP          # [res, res, res]
0f00  UNARY_INVERT     # [res, res, ~res]
1700  BINARY_ADD       # [res, -1]
0400  DUP_TOP          # [res, -1, -1]
1700  BINARY_ADD       # [res, -2]
0f00  UNARY_INVERT     # [res, 1]
1700  BINARY_ADD       # [res + 1]

Tiếp theo part2 là nhận vào 1 tham số a và luôn trả về 1337

Tạo 0 từ a: a ^ a == 0
z = a ^ a
Tạo 1 từ 0: ~0 == -1, -(-1) == 1
one = -~z

Bây giờ build 1337 bằng cách nhân 2 và cộng 1
bits của 1337 (từ MSB xuống LSB) = `1 0 1 0 0 1 1 1 0 0 1`
Ta "unroll" các bước: cho mỗi bit: result = result*2; nếu bit==1: result += one

result = 0
# bit10
result = result + result
result = result + one
# bit9
result = result + result
# bit8
result = result + result
result = result + one
# bit7
result = result + result
# bit6
result = result + result
# bit5
result = result + result
result = result + one
# bit4
result = result + result
result = result + one
# bit3
result = result + result
result = result + one
# bit2
result = result + result
# bit1
result = result + result
# bit0
result = result + result
result = result + one

Chuyển đoạn trên sang bytecode và pass part2.

Với part3 nhận 2 tham số a,b trả về a * b

result = 0
while b > 0:
    result += a
    b -= 1

Ta chuyển đoạn code đơn giản trên qua bytecode là xong.

00: DUP_TOP
01: DUP_TOP
02: UNARY_INVERT
03: BINARY_ADD
04: UNARY_INVERT
05: DUP_TOP
06: ROT_FOUR
07: POP_TOP
08: DUP_TOP
09: POP_JUMP_IF_TRUE 26      ; nếu b != 0 → vào thân (offset 26 = 0x1a)
10: POP_TOP                   ; (không dùng vì b≥1 theo đề)
11: DUP_TOP                   ; ---- thân: result += a ----
12: ROT_FOUR
13: POP_TOP
14: DUP_TOP
15: ROT_FOUR
16: BINARY_ADD
17: DUP_TOP
18: ROT_FOUR
19: POP_TOP
20: DUP_TOP                   ; ---- b = b - 1 ----
21: DUP_TOP
22: UNARY_INVERT
23: BINARY_ADD
24: BINARY_ADD                ; TOS = b-1
25: DUP_TOP                   ; copy để test
26: POP_JUMP_IF_TRUE 20       ; *** sửa: quay lại điểm kiểm tra (offset 20 = 0x14)
27: POP_TOP                   ; rơi ra khi b==0 → bỏ b
28: POP_TOP                   ; bỏ a, còn lại result ở TOS → RETURN_VALUE (tự chèn)

## Hardware
### Gas Gas Gas
![image](https://hackmd.io/_uploads/rJtIONlnel.png)
Trong tệp zip, ta có 1 folder `dist` chưa 1 tệp `gas.csv`
Tệp csv này có 5001 dòng và những dòng đầu của tệp này là:

#,Time(ms),CH1(mV),CH2(mV)
0,1.6800000,3360.00,3360.00
1,1.6760000,3320.00,3360.00
2,1.6720000,3360.00,3320.00
3,1.6680000,3360.00,3360.00
4,1.6640000,3320.00,3360.00
5,1.6600000,3320.00,3360.00
6,1.6560000,3360.00,3400.00
7,1.6520000,3400.00,3400.00
8,1.6480000,3360.00,3400.00
9,1.6440000,3400.00,3400.00
10,1.6400000,3360.00,3400.00
11,1.6360000,3400.00,3400.00
12,1.6320000,3400.00,3400.00
13,1.6280000,3400.00,3440.00
...

Đầu tiên, mình dùng AI để hỏi thêm về thông tin của đoạn này: [LINK](https://chatgpt.com/share/68dddd48-ee20-8006-b9d9-a66f2e604d83)
Từ đó mình thấy rằng trên mẫu này, màn hình hiển thị thông tin người lái sử dụng 2 ID CAN mở rộng trên bus tốc độ thấp nên sau đó mình tìm thông tin về Volvo 2 CAN và mình tìm thấy được link github này: https://github.com/martonn98/VolvoP2_CAN


1. Giải mã tệp csv như CAN tốc độ thấp (125kbps), loại bỏ bit, sau đó phân tích các frame mở rộng và bạn sẽ nhận được các frame 0x02A0240E ("activate") theo sau là một loạt các 0x01800008 frame.
2. Mỗi 0x01800008 frame bắt đầu bằng một byte điều khiển/vị trí nhỏ và phần còn lại là các ký tự cho LCD. Nhóm các frames thành hai dòng (2×16 của DIM).

Việc ghép lại các ký tự chính xác như DIM sẽ hiển thị sẽ cho kết quả:
Dòng 1: Decode Y3Jld3tzdDNwXzBO
Dòng 2: Base64 X3RIZV9nNHMhfQ==

    Flag: crew{st3p_0N_tHe_g4s!}
    
## PPC
### IOIOIOI
![image](https://hackmd.io/_uploads/r1kkdeb2xg.png)
:::spoiler `chall.py`

from solver import Solve
import signal
import secrets

def TLE(signum, frame):
print("Time Limit Exceeded. Try again...")
exit(0)

signal.signal(signal.SIGALRM, TLE)
signal.alarm(300)

params = [ # (N_min, N_max, K_min, K_max)
(1, 15, 0, 15), # Test 1
(1, 1000, 0, 1000), # Test 2
(5 * 10**8, 10**9, 0, 1000), # Test 3
(5 * 10**17, 10**18, 900, 1000), # Test 4
]

T = 300

for i in range(T):
test_id = i // 75
N_min, N_max, K_min, K_max = params[test_id]
N = N_min + secrets.randbelow(N_max - N_min + 1)
K = K_min + secrets.randbelow(K_max - K_min + 1)

ans = Solve(N, K)
assert 0 <= ans < 998244353

print("Test", i + 1)
print(f"{N = }")
print(f"{K = }")
print("Your answer: ", end="")
player_ans = int(input())

if ans == player_ans:
print("Accepted!")
else:
print("Wrong Answer. Try again...")
exit(0)

print("Congratulations! Here is your flag:")
print(open("flag.txt", "r").read())

:::
::: spoiler `README.md`
# IOIOIOI
## Statement
Let's think about length N binary string consisting only of the characters I and O.

The score of a string is defined as the sum of:
    - the number of contiguous substrings equal to "IOI"
    - the number of contiguous substrings equal to "IOIOI"
    - the number of contiguous substrings equal to "IOIOIOI"
and so on.

ex. score("IOIOIO") = 2 ("IOI") + 1 ("IOIOI") = 3

Find the number, modulo 998244353, of such strings have a score exactly equal to K.

## Constraints
- 1 ≦ N ≦ 10^18
- 0 ≦ K ≦ 1000

## Samples
### sample 1
#### input

N = 6
K = 3

#### output

4

#### explanation
There are 4 binary strings with length 6 have a score of 3: `IIOIOI`, `IOIOII`, `IOIOIO`, `OIOIOI`.

### sample 2
#### input

N = 9
K = 10

#### output

1

#### explanation
There is only 1 binary string with length 9 have a score of 10: `IOIOIOIOI`.

### sample 3
#### input

N = 40
K = 4

#### output

167288093

#### explanation
There are 144912719278 binary strings with length 40 have a score of 4, so the answer is 144912719278 mod 998244353 = 167288093.
:::

Thông qua đọc file `README.md` thì ta biết được yêu cầu của bài toán là đếm số chuỗi N có điểm đúng bằng K rồi mod 998244353, với K được tính là số đoạn con "IOI", "IOIOI", "IOIOIOI",... trong mẫu N.
Các mẫu "IOI", "IOIOI", … chính là những đoạn con có dạng lặp lại "IO" nhiều lần rồi kết thúc bằng "I". Vì vậy, mỗi khối luân phiên tối đa có `m` ký tự `I` sẽ góp $\binom{m}{2}$ vào số điểm.
$$
score = \displaystyle \sum_{blocks}\binom{m}{2}
$$

Ta mã hóa tất cả các xâu bằng hàm sinh hai biến A(x, y)
$$
A(x,y) = \displaystyle \sum_{m\ge 1} x^{2m-1}y^{\binom{m}{2}}
$$

và đa thức:
$$
F(x,y)=\dfrac{x+(1+x^2)A(x,y)}{1-x-(1-x+x^2)A(x,y)}
$$

, nên đáp số cần tìm là hệ số:
$$
[x^Ny^K]F(x,y)
$$

Thay vì viết toàn bộ $F(x,y)$, ta xây dựng một hệ đệ quy trạng thái dựa trên chuỗi Markov (ma trận chuyển tiếp). Từ đó biến nó thành:
$$
F(x,y)=\dfrac{P(x,y)}{Q(x,y)}
$$

Ở đây vì N rất lớn nên ta sẽ dùng thuật toán **Bostan-Mori** để lấy hệ số $x^N$ trong phân thức P/Q chỉ với $O(\log N)$ bước nhân đa thức.

Sau đó, rút gọn x = 0, ta còn 1 biểu thức chỉ phụ thuộc vào y và có thể lấy hệ số $y^K$ cuối cùng.
:::spoiler `sol.cpp`

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
const int MOD = 998244353;

inline int addmod(int a, int b){ a += b; if(a >= MOD) a -= MOD; return a; }
inline int submod(int a, int b){ a -= b; if(a < 0) a += MOD; return a; }
inline int mulmod(int a, int b){ return (int)((int64)a * b % MOD); }
inline int powmod(int a, long long e){ int r = 1; while(e){ if(e&1) r = mulmod(r,a); a = mulmod(a,a); e >>= 1; } return r; }
inline int invmod(int a){ return powmod(a, MOD-2); }

using ypoly = vector<int>; // coefficients in y, length K+1 (truncated)
using xpoly = vector<ypoly>; // coefficients in x, each coeff is a ypoly

// ---------- utilities for y-polynomials (dense) ----------
ypoly y_zero(int K){
return ypoly(K+1, 0);
}
ypoly y_monomial(int deg, int K){
ypoly r(K+1, 0);
if(deg <= K) r[deg] = 1;
return r;
}
ypoly y_add(const ypoly &A, const ypoly &B, int K){
ypoly C(K+1);
for(int i=0;i<=K;i++){
int v = A[i] + B[i];
if(v >= MOD) v -= MOD;
C[i] = v;
}
return C;
}
ypoly y_sub(const ypoly &A, const ypoly &B, int K){
ypoly C(K+1);
for(int i=0;i<=K;i++){
int v = A[i] - B[i];
if(v < 0) v += MOD;
C[i] = v;
}
return C;
}
ypoly y_scalar_mul(const ypoly &A, int s, int K){
if(s % MOD == 0) return y_zero(K);
ypoly R(K+1);
int ss = s % MOD;
for(int i=0;i<=K;i++){
if(A[i]) R[i] = mulmod(A[i], ss);
}
return R;
}
ypoly y_mul(const ypoly &A, const ypoly &B, int K){
// naive convolution truncated at degree K
ypoly C(K+1);
// pick smaller outer
if(&A == &B){
// square optimization? we skip to keep code simple
}
for(int i=0;i<=K;i++){
if(A[i]==0) continue;
int ai = A[i];
int lim = K - i;
for(int j=0;j<=lim;j++){
if(B[j]==0) continue;
C[i+j] = (C[i+j] + (int64)ai * B[j]) % MOD;
}
}
return C;
}

// ---------- utilities for x-polynomials ----------
void x_trim(xpoly &P){
while(!P.empty()){
// check if last ypoly is all zeros
ypoly &last = P.back();
bool allzero = true;
for(int v: last){ if(v) { allzero = false; break; } }
if(allzero) P.pop_back(); else break;
}
}
xpoly x_zero(int deg = 0, int K=0){
xpoly P(deg+1, y_zero(K));
return P;
}
xpoly x_add(const xpoly &A, const xpoly &B, int K){
int n = max((int)A.size(), (int)B.size());
xpoly C(n, y_zero(K));
for(int i=0;i<n;i++){
const ypoly &ai = (i < (int)A.size() ? A[i] : y_zero(K));
const ypoly &bi = (i < (int)B.size() ? B[i] : y_zero(K));
for(int d=0; d<=K; d++){
int v = ai[d] + bi[d];
if(v >= MOD) v -= MOD;
C[i][d] = v;
}
}
x_trim(C);
return C;
}
xpoly x_sub(const xpoly &A, const xpoly &B, int K){
int n = max((int)A.size(), (int)B.size());
xpoly C(n, y_zero(K));
for(int i=0;i<n;i++){
const ypoly &ai = (i < (int)A.size() ? A[i] : y_zero(K));
const ypoly &bi = (i < (int)B.size() ? B[i] : y_zero(K));
for(int d=0; d<=K; d++){
int v = ai[d] - bi[d];
if(v < 0) v += MOD;
C[i][d] = v;
}
}
x_trim(C);
return C;
}
xpoly x_scalar_mul(const xpoly &A, int s, int K){
if(s % MOD == 0) return xpoly();
int ss = s % MOD;
xpoly R = A;
for(auto &yp : R){
for(int i=0;i<=K;i++){
if(yp[i]) yp[i] = mulmod(yp[i], ss);
}
}
x_trim(R);
return R;
}
xpoly x_mul(const xpoly &A, const xpoly &B, int deg_limit, int K){
if(A.empty() || B.empty()) return xpoly();
int la = A.size(), lb = B.size();
int lim = min(deg_limit, la + lb - 2);
xpoly C(lim + 1, y_zero(K));
for(int i=0;i<la;i++){
if(i > lim) break;
const ypoly &ai = A[i];
bool ai_non = false;
for(int t=0;t<=K;t++){ if(ai[t]) { ai_non=true; break; } }
if(!ai_non) continue;
int maxj = min(lb - 1, lim - i);
for(int j=0;j<=maxj;j++){
const ypoly &bj = B[j];
bool bj_non = false;
for(int t=0;t<=K;t++){ if(bj[t]) { bj_non=true; break; } }
if(!bj_non) continue;
ypoly prod = y_mul(ai, bj, K);
if(prod.empty()) continue;
ypoly &cij = C[i+j];
for(int d=0; d<=K; d++){
if(prod[d]==0) continue;
cij[d] = (cij[d] + prod[d]) % MOD;
}
}
}
x_trim(C);
return C;
}
xpoly x_neg_x_substitute(const xpoly &Q, int K){
xpoly R(Q.size(), y_zero(K));
for(size_t i=0;i<Q.size();i++){
if(((int)i)&1){
// negate
for(int d=0; d<=K; d++){
if(Q[i][d]) R[i][d] = (MOD - Q[i][d]) % MOD;
}
}else{
for(int d=0; d<=K; d++) R[i][d] = Q[i][d];
}
}
x_trim(R);
return R;
}
xpoly x_even_coeffs(const xpoly &P, int K){
int n = P.size();
xpoly R((n+1)/2, y_zero(K));
for(size_t k=0; 2*k < P.size(); ++k){
R[k] = P[2*k];
}
x_trim(R);
return R;
}
xpoly x_odd_coeffs(const xpoly &P, int K){
int n = P.size();
if(n <= 1) return xpoly();
xpoly R(n/2, y_zero(K));
for(size_t k=0; 2*k+1 < P.size(); ++k){
R[k] = P[2*k+1];
}
x_trim(R);
return R;
}

// ---------- Build T matrix and P/Q ----------
struct PQpair { xpoly P, Q; };

static unordered_map<int, PQpair> PQ_cache;

PQpair build_PQ(int K){
auto it = PQ_cache.find(K);
if(it != PQ_cache.end()) return it->second;

int m_max;
if(K > 0){
long long disc = 1 + 8LL*K;
long long s = (long long) sqrt((double)disc);
while(s*s < disc) ++s;
while(s*s > disc) --s;
m_max = (int)((1 + s) / 2);
while(m_max*(m_max-1)/2 > K) --m_max;
} else m_max = 1;

int degT = 2*m_max + 1;
// create T entries: T00, T01, T10, T11 each xpoly with deg <= degT
xpoly T00(degT+1, y_zero(K)), T01(degT+1, y_zero(K)), T10(degT+1, y_zero(K)), T11(degT+1, y_zero(K));
// fill from earlier corrected logic
for(int m=1;m<=m_max;m++){
int e = m*(m-1)/2;
if(e > K) break;
int idx_odd = 2*m - 1;
int idx_even = 2*m;
// I->I via odd 2m-1 with weight y^{e}
if(idx_odd <= degT){
ypoly mono = y_monomial(e, K);
for(int d=0; d<=K; d++) if(mono[d]) T00[idx_odd][d] = addmod(T00[idx_odd][d], mono[d]);
}
// I->O via even 2m
if(idx_even <= degT){
ypoly mono = y_monomial(e, K);
for(int d=0; d<=K; d++) if(mono[d]) T01[idx_even][d] = addmod(T01[idx_even][d], mono[d]);
}
}
for(int m=0;m<=m_max;m++){
int e = m*(m-1)/2;
if(e > K) break;
int idx_odd = 2*m + 1;
int idx_even = 2*m;
if(idx_odd <= degT){
ypoly mono = y_monomial(e, K);
for(int d=0; d<=K; d++) if(mono[d]) T11[idx_odd][d] = addmod(T11[idx_odd][d], mono[d]);
}
if(m>=1 && idx_even <= degT){
ypoly mono = y_monomial(e, K);
for(int d=0; d<=K; d++) if(mono[d]) T10[idx_even][d] = addmod(T10[idx_even][d], mono[d]);
}
}
x_trim(T00); x_trim(T01); x_trim(T10); x_trim(T11);

// A = I - T, where I = 1 at degree 0 y^0
xpoly ident(1, y_zero(K)); ident[0][0] = 1;
// a11 = I - T00
xpoly a11 = x_sub(ident, T00, K);
xpoly a12 = x_scalar_mul(T01, MOD-1, K); // -T01
xpoly a21 = x_scalar_mul(T10, MOD-1, K); // -T10
xpoly a22 = x_sub(ident, T11, K);

// det Q = a11*a22 - a12*a21
int deg1 = (int)((a11.size()? a11.size()-1:0) + (a22.size()? a22.size()-1:0));
int deg2 = (int)((a12.size()? a12.size()-1:0) + (a21.size()? a21.size()-1:0));
int deg_limit = max(deg1, deg2);
xpoly term1 = x_mul(a11, a22, deg_limit, K);
xpoly term2 = x_mul(a12, a21, deg_limit, K);
xpoly Q = x_sub(term1, term2, K);

// adj(A) = [a22, -a12; -a21, a11]
xpoly adj11 = a22;
xpoly adj12 = x_scalar_mul(a12, MOD-1, K);
xpoly adj21 = x_scalar_mul(a21, MOD-1, K);
xpoly adj22 = a11;

// S = T * adj(A)
// Compute S00 = T00*adj11 + T01*adj21
xpoly S00 = x_add(x_mul(T00, adj11, (int)max((int)T00.size()-1,(int)adj11.size()-1) + (int)max((int)T00.size()-1,(int)adj11.size()-1), K),
x_mul(T01, adj21, (int)max((int)T01.size()-1,(int)adj21.size()-1) + (int)max((int)T01.size()-1,(int)adj21.size()-1), K), K);
xpoly S01 = x_add(x_mul(T00, adj12, (int)max((int)T00.size()-1,(int)adj12.size()-1) + (int)max((int)T00.size()-1,(int)adj12.size()-1), K),
x_mul(T01, adj22, (int)max((int)T01.size()-1,(int)adj22.size()-1) + (int)max((int)T01.size()-1,(int)adj22.size()-1), K), K);
xpoly S10 = x_add(x_mul(T10, adj11, (int)max((int)T10.size()-1,(int)adj11.size()-1) + (int)max((int)T10.size()-1,(int)adj11.size()-1), K),
x_mul(T11, adj21, (int)max((int)T11.size()-1,(int)adj21.size()-1) + (int)max((int)T11.size()-1,(int)adj21.size()-1), K), K);
xpoly S11 = x_add(x_mul(T10, adj12, (int)max((int)T10.size()-1,(int)adj12.size()-1) + (int)max((int)T10.size()-1,(int)adj12.size()-1), K),
x_mul(T11, adj22, (int)max((int)T11.size()-1,(int)adj22.size()-1) + (int)max((int)T11.size()-1,(int)adj22.size()-1), K), K);

xpoly P = x_add(x_add(S00, S01, K), x_add(S10, S11, K), K);

PQpair pq; pq.P = P; pq.Q = Q;
PQ_cache[K] = pq;
return pq;
}

// ---------- Bostan-Mori for P/Q where coefficients are y-polynomials ----------
xpoly x_trim_copy(xpoly P){
x_trim(P); return P;
}
xpoly x_even_coeffs_copy(const xpoly &P, int K){ return x_even_coeffs(P, K); }
xpoly x_odd_coeffs_copy(const xpoly &P, int K){ return x_odd_coeffs(P, K); }

int get_coefficient_bostan(const xpoly &P_in, const xpoly &Q_in, long long N, int K){
xpoly P = P_in;
xpoly Q = Q_in;
x_trim(P); x_trim(Q);
if(N < 0) return 0;
while(N){
xpoly Qminus = x_neg_x_substitute(Q, K);
xpoly U = x_mul(P, Qminus, (int)max(0, (int)P.size()-1 + (int)Qminus.size()-1), K);
xpoly V = x_mul(Q, Qminus, (int)max(0, (int)Q.size()-1 + (int)Qminus.size()-1), K);
if(N & 1){
P = x_odd_coeffs(U, K);
}else{
P = x_even_coeffs(U, K);
}
Q = x_even_coeffs(V, K);
N >>= 1;
x_trim(P); x_trim(Q);
if(Q.empty()){
return 0;
}
}
// Now result is P(0)/Q(0) as power series in y; compute coefficient y^K
ypoly P0 = (P.size()? P[0] : y_zero(K));
ypoly Q0 = (Q.size()? Q[0] : y_zero(K));
vector<int> Parr(K+1,0), Qarr(K+1,0);
for(int d=0; d<=K; d++){ Parr[d] = P0[d] % MOD; Qarr[d] = Q0[d] % MOD; }
if(Qarr[0] == 0) return 0;
int invq0 = invmod(Qarr[0]);
vector<int> R(K+1, 0);
for(int n=0; n<=K; ++n){
long long s = Parr[n];
if(n){
long long acc = 0;
for(int i=1;i<=n;i++){
if(Qarr[i]) acc = (acc + (long long)R[n-i] * Qarr[i]) % MOD;
}
s = (s - acc) % MOD;
if(s < 0) s += MOD;
}
R[n] = mulmod((int)s, invq0);
}
return R[K];
}

// ---------- top-level solve ----------
int solve_NK(long long N, int K){
if(N == 0) return (K == 0 ? 1 : 0);
PQpair pq = build_PQ(K);
int ans = get_coefficient_bostan(pq.P, pq.Q, N, K);
return ans;
}

// ---------- main: sample tests and optional stdin reading ----------
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);

for(int i=0;i<300;i++){
long long N; int K;
if(!(cin >> N >> K)) break;
int ans = solve_NK(N,K);
cout << ans << '\n';
cout.flush();
}

return 0;
}

:::
Sau đó, ta dùng: `g++ -O3 -march=native -std=c++17 -pipe -s sol.cpp -o sol`
:::spoiler `sol.py`

from pwn import *
context.log_level = "error"

solver = process(["/home/r1muru/workspace/CrewCTF2025/PPC/IOIOIOI/sol2"])

# Connect to remote
io = remote("ioioioi.chal.crewc.tf", 1337, ssl=True)

def take_data():
io.recvuntil(b"N = ")
N = int(io.recvline().decode().strip())
io.recvuntil(b"K = ")
K = int(io.recvline().decode().strip())
return N, K

for _ in range(300):
N, K = take_data()
# Feed query into C++ solver
solver.sendline(f"{N} {K}".encode())
ans = solver.readline().decode().strip()

# Send answer back to server
io.send(ans.encode()+b"\n")
# print(_ + 1)
print(io.recvall())

:::
    Flag: crew{Th1s_ch4llenge_i5_0ut_of_I0I_sylla6us_th0ugh_8eaf3fed84a94f3c62bc37553b14e270}
    
## Crypto
### GFLCG
![image](https://hackmd.io/_uploads/SJ3H9QM3xg.png)
::: spoiler `chall.sage`

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

class LCG:
def __init__(self, nbits):
self.nbits = nbits
R = GF(2)['x']
mod = 0
while True:
mod = R.random_element(degree=nbits)
if mod.is_irreducible():
break
assert mod.degree() == nbits
self.F = GF(2 ** nbits, 'x', modulus=mod)
self.a = self.F.random_element()
self.b = self.F.random_element()
self.m = mod
self.state = self.F.random_element()

def __next__(self):
self.state *= self.a
self.state += self.b
return self.state.to_integer() >> ((self.nbits * 2) // 3)

L = LCG(64 * 3)

values = [next(L) for _ in range(200)]
print(f'{values = }')

v1 = next(L)
v2 = next(L)
key = v1 + v2 * pow(2, 64)
key = int.to_bytes(int(key), 16)

flag = 'crew{*** REDACTED ***}'
cipher = AES.new(key, AES.MODE_ECB)

msg = cipher.encrypt(pad(flag.encode(), 16))
print(f'{msg = }')

:::
:::spoiler `out.txt`

values = [14841917648858837769, 9575471537143015742, 15844238770919434615, 5212260032608174747, 9233247444323572291, 10459091850700078324, 6348171461039085016, 11275083358377081726, 15851907641654315174, 5642462723638664555, 12166934227670445515, 16652002833255337213, 1100331227495018541, 17310052757528676070, 10647848709476991180, 7381860977210638817, 14749898712454789023, 9867793747622460486, 1616048454543341186, 8104578690941366513, 4083347094007115737, 11760837183986471162, 16862797396993697119, 1174637638031988756, 1804745826465075031, 16276632568687926630, 5043494920323747028, 11409272895120917919, 16265611200345769799, 14970614558261079002, 2250516726687967919, 1197248850350389243, 14603131310865530726, 16548361948476584779, 13353652992939482174, 13336486704510937571, 10441893770111811970, 4107764688249514273, 11772797255441774916, 12518165417933617541, 7010550077174075010, 14001355721098446832, 437777177382829002, 1722164767628433760, 6559647342847449596, 7938756427230732045, 13281366260429048930, 13092183655381323106, 11806529132310996843, 13947964017447178113, 4621312151518731422, 12501874612357040563, 10826458102042992364, 2159902472703790642, 13882393964322032422, 6529148921315953891, 10134887505878190392, 10419951393751420634, 10135848342454860542, 14313363158598253532, 8934368669847669830, 5124101360181491049, 14913219354552074425, 10908282099950928722, 4253964689299281724, 7407726974875151040, 14219905121435863470, 4181337490774743589, 4184184504223738823, 16936150976212002434, 14433936574129760038, 15520881989251542597, 11194070033146759221, 18174433602168311426, 13020442067015339358, 4382990166888652495, 10254297534043164279, 3817100944212579597, 5331877218604250458, 7185825545642354761, 338711531771068892, 10250264203376128253, 7359215208260510617, 14277514750873457414, 3460304295915392143, 3818816217224032441, 4483483566282319717, 2866544513807354462, 12135646457812113066, 8778669990047144231, 12989768322575258896, 8988116933722638298, 15692389573895602242, 4456647617936315332, 6039845569195475247, 14311304340715617600, 17295981409675358596, 11427453308135142971, 9052862849088317754, 6137397312278782739, 9544766266324391091, 16447228426027058890, 13803636818363488657, 16670480602864962535, 3351397243085772246, 5665702184993835815, 16424003006508152011, 13976194469704404585, 401185194999070420, 5699512823604259627, 17357160984615588720, 3670786096561696620, 4323747368693388297, 10876978042181159325, 7883125366518538304, 2344284687610109741, 12391759147373797536, 12590053927293200960, 8879156692797105548, 8461065756503570819, 17573320578141302871, 15642604376730203427, 12749133263385207476, 4133105186664632492, 18028280465459656846, 3067339009189147778, 15204862189705497345, 18132974384436241649, 8091492506662448517, 18147014166549437993, 5201643316892664569, 3104017212583314140, 3368545846626480386, 14752755621090773653, 9816609813405607817, 10989512726787524104, 17941375633925480992, 5969536734982737360, 3324460409144811670, 14364167734200742327, 10841885411537515505, 12033027733536926218, 13019115357341976440, 13723571084095846113, 14963449044276506843, 9241404467774916626, 1173475476199930336, 10007814422905689012, 880823326108631285, 2864914879726840475, 12348071585001057949, 6441302746542868688, 4806991077471213319, 8933141648678945175, 11649694907667295433, 8708277013041751508, 11719418456350910218, 16635157254108725579, 2134377351096125475, 10289961173017455600, 7055962786096505116, 21728601024181168, 16456998880597164728, 17216116874066795215, 3380132322173996284, 13114502767808007100, 4207348709474901930, 12916699834279235125, 15877440687400786825, 4585779573201771030, 3370966433634988692, 6413163656213101252, 8735986678159831147, 14813660282203931848, 4336269858741206951, 7680697319476289935, 3057350045239125021, 437484923622226917, 12182392489340614340, 7344380605957273905, 1047582581395548343, 9669150555048976950, 3445073427932842783, 5988003049280873305, 9984210927208328016, 8558400548885959238, 14932071850589169092, 10998241484982990572, 4061032217328993314, 16299495071317926943, 14159713152585339233, 7943955737745599039, 2708719529779063308, 5915795415723872866, 15610632814203455383, 9659638034966636775, 10804220067446596648, 3339259544022408735, 16353934319513835005, 7564345426168321381]
msg = b'\xf9\xb9p\xf1\xa0\xc2\x15-\xa1\x90b\x06\x85\x1e\xa9bH\x15\x02\xcc\xba\x97\xc9.\xd3\xc8#\x1af6N\x96x)\x89\xddrg\xa2\x8b\xdd\x0c\xc9peNzWU\xfc9fJ1\xef\xdd\n\x9c\xa2\tW\x97F\x9a'

:::
#### Phân tích
Đây không phải là 1 bài LCG thường mà là biến thể LCG trên trường hữu hạn $\mathbb{G}\mathbb{F}(2^{192})$. Ở hàm sinh số, trạng thái cuối bị cắt bớt (2/3)*nbits và chỉ giữ lại 1/3 số bit cao nhất (ở bài này là 64). 

def __next__(self):
self.state *= self.a
self.state += self.b
return self.state.to_integer() >> ((self.nbits * 2) // 3)

Nói cách khác, giả sử $s_t$ là dãy sinh ra từ LCG thì $y_t = P.s_t$, với $P$ là phép chiếu tuyến tính chọn 64 bit cao $\Rightarrow$ Chuỗi đầu ra là ảnh của 1 hệ tuyến tính hữu hạn chiều, tức là dãy $y_t$ sẽ thỏa 1 quan hệ truy hồi tuyến tính với bậc hữu hạn ($O(n)\le192+1$).

#### Ý tưởng
Vì hệ này tuyến tính trên $\mathbb{F}_2$, nên bất kỳ phép chiếu tuyến tính không tầm thường (ví dụ 64 bit cao) của trạng thái cũng sinh ra một dãy có độ phức tạp tuyến tính hữu hạn. Thu đủ nhiều mẫu là ta thừa sức khôi phục được quan hệ truy hồi.

**Note:** Khi đầu ra là tổ hợp tuyến tính của trạng thái tuân theo một số biến đổi cố định, tồn tại một đa thức triệt tiêu trên dãy $y_t$: $\displaystyle \sum_{i=0}^Lc_iy_{t+i}=0, c_i\in\mathbb{F}_2, \forall t$
$\rightarrow$ Tìm được bộ $c_i$, ta sẽ tính được các $y_t$ tiếp theo từ các giá trị cho trước.

Từ đó, ý tưởng của tôi là dựng 1 ma trận `m` có số hàng lớn hơn bậc hữu hạn $O(n)$, số cột là 1 hằng số $k$ sao cho $k\times64 > O(n)+1=194$ là số lượng các đầu ra liên tiếp để sử dụng ràng buộc tuyến tính giống hệt về cấu trúc giữa chúng.

k = 4
c = 64 * 3 + 2
m = []

for i in range(c):
row = []
for j in range(k):
U = values[i + j]
for l in range(64):
row.append(U & 1)
U >>= 1
m.append(row)

Sau đó, ta tìm ma trận cột `p` độ dài $k\times64$ sao cho $p\times m = 0$
Ở đây `p` mô tả một quan hệ tuyến tính bất biến theo t giữa k output liên tiếp (từng bit xét độc lập) và nó chính là “đa thức triệt tiêu” trên dãy, áp dụng đồng thời cho 64 bit.

p = m.left_kernel().basis()[0]

Sau khi có được `p`, ta áp cùng 1 tổ hợp tuyến tính trên $\mathbb{F}_2$ để sinh ra các đầu ra mới và sử dụng chúng để tạo key là có thể giải mã được `msg` của đề bài.

# sol.py
from sage.all import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

values = [14841917648858837769, 9575471537143015742, 15844238770919434615, 5212260032608174747, 9233247444323572291, 10459091850700078324, 6348171461039085016, 11275083358377081726, 15851907641654315174, 5642462723638664555, 12166934227670445515, 16652002833255337213, 1100331227495018541, 17310052757528676070, 10647848709476991180, 7381860977210638817, 14749898712454789023, 9867793747622460486, 1616048454543341186, 8104578690941366513, 4083347094007115737, 11760837183986471162, 16862797396993697119, 1174637638031988756, 1804745826465075031, 16276632568687926630, 5043494920323747028, 11409272895120917919, 16265611200345769799, 14970614558261079002, 2250516726687967919, 1197248850350389243, 14603131310865530726, 16548361948476584779, 13353652992939482174, 13336486704510937571, 10441893770111811970, 4107764688249514273, 11772797255441774916, 12518165417933617541, 7010550077174075010, 14001355721098446832, 437777177382829002, 1722164767628433760, 6559647342847449596, 7938756427230732045, 13281366260429048930, 13092183655381323106, 11806529132310996843, 13947964017447178113, 4621312151518731422, 12501874612357040563, 10826458102042992364, 2159902472703790642, 13882393964322032422, 6529148921315953891, 10134887505878190392, 10419951393751420634, 10135848342454860542, 14313363158598253532, 8934368669847669830, 5124101360181491049, 14913219354552074425, 10908282099950928722, 4253964689299281724, 7407726974875151040, 14219905121435863470, 4181337490774743589, 4184184504223738823, 16936150976212002434, 14433936574129760038, 15520881989251542597, 11194070033146759221, 18174433602168311426, 13020442067015339358, 4382990166888652495, 10254297534043164279, 3817100944212579597, 5331877218604250458, 7185825545642354761, 338711531771068892, 10250264203376128253, 7359215208260510617, 14277514750873457414, 3460304295915392143, 3818816217224032441, 4483483566282319717, 2866544513807354462, 12135646457812113066, 8778669990047144231, 12989768322575258896, 8988116933722638298, 15692389573895602242, 4456647617936315332, 6039845569195475247, 14311304340715617600, 17295981409675358596, 11427453308135142971, 9052862849088317754, 6137397312278782739, 9544766266324391091, 16447228426027058890, 13803636818363488657, 16670480602864962535, 3351397243085772246, 5665702184993835815, 16424003006508152011, 13976194469704404585, 401185194999070420, 5699512823604259627, 17357160984615588720, 3670786096561696620, 4323747368693388297, 10876978042181159325, 7883125366518538304, 2344284687610109741, 12391759147373797536, 12590053927293200960, 8879156692797105548, 8461065756503570819, 17573320578141302871, 15642604376730203427, 12749133263385207476, 4133105186664632492, 18028280465459656846, 3067339009189147778, 15204862189705497345, 18132974384436241649, 8091492506662448517, 18147014166549437993, 5201643316892664569, 3104017212583314140, 3368545846626480386, 14752755621090773653, 9816609813405607817, 10989512726787524104, 17941375633925480992, 5969536734982737360, 3324460409144811670, 14364167734200742327, 10841885411537515505, 12033027733536926218, 13019115357341976440, 13723571084095846113, 14963449044276506843, 9241404467774916626, 1173475476199930336, 10007814422905689012, 880823326108631285, 2864914879726840475, 12348071585001057949, 6441302746542868688, 4806991077471213319, 8933141648678945175, 11649694907667295433, 8708277013041751508, 11719418456350910218, 16635157254108725579, 2134377351096125475, 10289961173017455600, 7055962786096505116, 21728601024181168, 16456998880597164728, 17216116874066795215, 3380132322173996284, 13114502767808007100, 4207348709474901930, 12916699834279235125, 15877440687400786825, 4585779573201771030, 3370966433634988692, 6413163656213101252, 8735986678159831147, 14813660282203931848, 4336269858741206951, 7680697319476289935, 3057350045239125021, 437484923622226917, 12182392489340614340, 7344380605957273905, 1047582581395548343, 9669150555048976950, 3445073427932842783, 5988003049280873305, 9984210927208328016, 8558400548885959238, 14932071850589169092, 10998241484982990572, 4061032217328993314, 16299495071317926943, 14159713152585339233, 7943955737745599039, 2708719529779063308, 5915795415723872866, 15610632814203455383, 9659638034966636775, 10804220067446596648, 3339259544022408735, 16353934319513835005, 7564345426168321381]
msg = b'\xf9\xb9p\xf1\xa0\xc2\x15-\xa1\x90b\x06\x85\x1e\xa9bH\x15\x02\xcc\xba\x97\xc9.\xd3\xc8#\x1af6N\x96x)\x89\xddrg\xa2\x8b\xdd\x0c\xc9peNzWU\xfc9fJ1\xef\xdd\n\x9c\xa2\tW\x97F\x9a'

k = 4
c = 64 * 3 + 2

m = []

for i in range(c):
row = []
for j in range(k):
U = values[i + j]
for l in range(64):
row.append(U & 1)
U >>= 1
m.append(row)

m = matrix(GF(2), m)

p = m.left_kernel().basis()[0]

for idx in range(len(values), len(values) + 2):
ans = 0
for i in range(len(p) - 1):
if p[i] == 1:
ans ^= values[idx + i - len(p) + 1]
values.append(ans)

key = values[-2] + values[-1] * pow(2, 64)
key = int.to_bytes(int(key), 16)
cipher = AES.new(key,AES.MODE_ECB)
print(unpad(cipher.decrypt(msg), 16).decode())

    Flag: crew{Its_34513r_1n_GF2_d1a83b1addeb0ed863b46a85aef9a293}

### Inverse with errors only
![image](https://hackmd.io/_uploads/ryqySXhnge.png)
:::spoiler `chall.py`

import hashlib
import secrets

from Crypto.Cipher import AES
from Crypto.Util.number import getPrime as get_prime
from Crypto.Util.Padding import pad

flag = b"crew{*** REDACTED ***}"

bits = 1024
d = get_prime(bits)
values = []

for _ in range(30000):
n = secrets.randbits(1024) | (1 << 1024)
values.append(pow(d, -1, n))

key = hashlib.sha256(str(d).encode()).digest()
flag = pad(flag, 16)

cipher = AES.new(key, AES.MODE_CBC)
iv = cipher.iv.hex()
enc = cipher.encrypt(flag).hex()

print(f"{values = }")
print(f"{iv = }")
print(f"{enc = }")

:::
Mỗi `value` in ra là $v_i\equiv d^{-1}$ mod một số ngẫu nhiên $n_i$. Với một số nguyên tố $p$ nhỏ, khoảng $\dfrac{1}{p}$ của những giá trị $n_i$ này sẽ chia hết cho $p$.

Vì vậy, với những chỉ số này ta cũng sẽ có: $dv_i\equiv 1\mod p\Rightarrow d\equiv (v_i)^{-1}\mod p$.

Nếu ta phân tích tần suất $\forall i$, giá trị $d\equiv v^{-1}\mod p$ sẽ xuất hiện lặp lại nhiều lần với p. Khi đó, ta sẽ lọc các ứng viên $d$ có tần suất cao nhất với mỗi modulo $p$.

# Quét primes nhỏ lấy ứng viên
CAND = []
for p in prime_range(3, 1000):
counts = Counter(v % p for v in values).most_common(1)
r1 = counts[0][0]
a_p = pow(r1, -1, p)
CAND.append((p, a_p))

Thu được nhiều $d$ theo các modulo nguyên tố khác nhau, thì ta sử dụng định lý thặng dư trung hoa (CRT) cho các $d$ này với modulo tăng lên với $P=\displaystyle\prod p_i$ cho đến khi nó đạt được 1024 bit thì ta sẽ thử chúng làm key đến khi nhận được flag đúng.

# CRT từng ứng viên để lấy d
a_mod, mod = 0, 1
for p, a_p in CAND:
a_mod, mod = crt([a_mod, a_p], [mod, p]), mod * p
if iv_hex and enc_hex and mod.bit_length() >= 1024:
try:
pt = decrypt_flag(a_mod, iv_hex, enc_hex)
if pt.startswith(b"crew{"):
print(unpad(pt, 16).decode())
break
except Exception:
pass

Script:

import ast
import hashlib
from Crypto.Cipher import AES
from collections import Counter
from Crypto.Util.Padding import unpad
from sage.all import crt, prime_range

def decrypt_flag(d, iv_hex, enc_hex):
key = hashlib.sha256(str(d).encode()).digest()
iv = bytes.fromhex(iv_hex)
enc = bytes.fromhex(enc_hex)
cipher = AES.new(key, AES.MODE_CBC, iv=iv)
pt = cipher.decrypt(enc)
return pt

def get_flag(values, iv_hex, enc_hex):
# Quét primes nhỏ lấy ứng viên
CAND = []
for p in prime_range(3, 1000):
counts = Counter(v % p for v in values).most_common(1)
r1 = counts[0][0]
a_p = pow(r1, -1, p)
CAND.append((p, a_p))

# CRT từng ứng viên để lấy d
a_mod, mod = 0, 1
for p, a_p in CAND:
a_mod, mod = crt([a_mod, a_p], [mod, p]), mod * p
if iv_hex and enc_hex and mod.bit_length() >= 1024:
try:
pt = decrypt_flag(a_mod, iv_hex, enc_hex)
if pt.startswith(b"crew{"):
print(unpad(pt, 16).decode())
break
except Exception:
pass

if __name__ == "__main__":
with open("out.txt", "r") as f:
data = {}
for line in f:
key, rhs = line.strip().split(" = ", 1)
key = key.strip()
rhs = rhs.strip()
data[key] = ast.literal_eval(rhs)

values, iv_hex, enc_hex = data["values"], data["iv"], data["enc"]
get_flag(values, iv_hex, enc_hex)

    Flag: crew{1nvertin9_w17h_3rr0rs_4065fad3e73c13b3f467cfc7887ff960}