# KMA CTF 2024
## EzRSA

**server.py**

import base64
import hashlib
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
import random

FLAG = "KMACTF{s0m3_r3ad4ble_5tr1ng_like_7his}"

def verifySignature(public_key, msg: bytes, sig_bytes: bytes, key_size: int, prefix: bytes, namePrefix):
    HASH_FUNC = {
        'MD5': hashlib.md5(msg).digest(),
        'SHA-1': hashlib.sha1(msg).digest(),
        'SHA-256': hashlib.sha256(msg).digest(),
        'SHA-384': hashlib.sha384(msg).digest(),
        'SHA-512': hashlib.sha512(msg).digest()
    }
    message_sum = HASH_FUNC[namePrefix]
    c = bytes_to_long(sig_bytes)
    m = long_to_bytes(pow(c, public_key.e, public_key.n))
    em = bytearray(key_size//8)
    em[key_size//8-len(m):] = m
    em = bytes(em)

    i = 0
    if em[i] != 0 or em[i+1] != 1:
        return 0

    i = i + 2
    while i < key_size//8 and em[i] == 0xff:
        i += 1

    if em[i] != 0:
        return 0
    i += 1

    if em[i:i+len(prefix)] != prefix:
        return 0

    i = i + len(prefix)
    if em[i:i+len(message_sum)] != message_sum:
        return 0
    
    return 1

def main():
    HASH_ASN1 = {
        'MD5': b'\x30\x20\x30\x0c\x06\x08\x2a\x86\x48\x86\xf7\x0d\x02\x05\x05\x00\x04\x10',
        'SHA-1': b'\x30\x21\x30\x09\x06\x05\x2b\x0e\x03\x02\x1a\x05\x00\x04\x14',
        'SHA-256': b'\x30\x31\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x01\x05\x00\x04\x20',
        'SHA-384': b'\x30\x41\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x02\x05\x00\x04\x30',
        'SHA-512': b'\x30\x51\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x03\x05\x00\x04\x40'
    }

    namePrefix = random.choice(list(HASH_ASN1.keys()))
    p, q = getPrime(1024), getPrime(1024)
    modulus = p*q
    key_size = modulus.bit_length()
    public_key = RSA.construct((modulus, 3))
    print("Hash:", namePrefix)
    print("Modulus =", modulus)

    try:
        message = input("Enter the message you want to verify: ")
        signature = base64.b64decode(input("Enter its base64 signature: "))
    except:
        print("Invalid input!")
        exit()

    err = verifySignature(public_key, message.encode(), signature, key_size, HASH_ASN1[namePrefix], namePrefix)

    if err:
        print("Well done! This is your flag:", FLAG)
        exit()
    else:
        print("Not good enough! Try harder! -.-")
        exit()

if __name__ == "__main__":
    main()

### Phân tích:
Để lấy được FLAG ta cần gửi đến server một message và signature của message đó.

Hàm `verifySignature`:

def verifySignature(public_key, msg: bytes, sig_bytes: bytes, key_size: int, prefix: bytes, namePrefix):
    HASH_FUNC = {
        'MD5': hashlib.md5(msg).digest(),
        'SHA-1': hashlib.sha1(msg).digest(),
        'SHA-256': hashlib.sha256(msg).digest(),
        'SHA-384': hashlib.sha384(msg).digest(),
        'SHA-512': hashlib.sha512(msg).digest()
    }
    message_sum = HASH_FUNC[namePrefix]
    c = bytes_to_long(sig_bytes)
    m = long_to_bytes(pow(c, public_key.e, public_key.n))
    em = bytearray(key_size//8)
    em[key_size//8-len(m):] = m
    em = bytes(em)

    i = 0
    if em[i] != 0 or em[i+1] != 1:
        return 0

    i = i + 2
    while i < key_size//8 and em[i] == 0xff:
        i += 1

    if em[i] != 0:
        return 0
    i += 1

    if em[i:i+len(prefix)] != prefix:
        return 0

    i = i + len(prefix)
    if em[i:i+len(message_sum)] != message_sum:
        return 0
    
    return 1

Đọc kỹ đoạn code thì mình nhận thấy m phải có dạng như sau:
`00 01 FF FF FF ... FF FF 00 ASN HASH`
Như vậy `m` cần theo format của ASN.1
Lại có: $m = c^3 \bmod n$
Vì vậy để có thể tạo ra một "fake" signature thì ta cần tìm được giá trị $c$ để lũy thừa của nó thảo mãn định dạng trên.

Mình đã rất mất thời gian để đi tìm được một con $c$ như vậy.
Sau một hồi lần mò thì mình tìm được link này: https://landonhemsley.com/bleichenbacher-06-rsa-signature-forgery-what-they-assume-you-know/

Và rồi mình nhận thấy:

if em[i:i+len(message_sum)] != message_sum:
        return 0

vì thế những gì sau `hash` không còn quan trọng nữa và ta có thể truyền vào một giá trị xấp xỉ khi đó:
`m = 00 01 FF FF FF ... FF FF 00 ASN HASH GARBAGE`

### Script

from pwn import *
import base64
import hashlib
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
from gmpy2 import iroot

io = remote("157.15.86.73", 2003)

msg = b"a"

HASH_FUNC = {
        'MD5': hashlib.md5(msg).digest(),
        'SHA-1': hashlib.sha1(msg).digest(),
        'SHA-256': hashlib.sha256(msg).digest(),
        'SHA-384': hashlib.sha384(msg).digest(),
        'SHA-512': hashlib.sha512(msg).digest()
    }


HASH_ASN1 = {
        'MD5': b'\x30\x20\x30\x0c\x06\x08\x2a\x86\x48\x86\xf7\x0d\x02\x05\x05\x00\x04\x10',
        'SHA-1': b'\x30\x21\x30\x09\x06\x05\x2b\x0e\x03\x02\x1a\x05\x00\x04\x14',
        'SHA-256': b'\x30\x31\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x01\x05\x00\x04\x20',
        'SHA-384': b'\x30\x41\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x02\x05\x00\x04\x30',
        'SHA-512': b'\x30\x51\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x03\x05\x00\x04\x40'
    }

io.recvuntil(b'Hash: ')
namePrefix = io.recvuntil(b'\n')[:-1].decode()
io.recvuntil(b'Modulus = ')
n = int(io.recvuntil(b'\n')[:-1].decode())


def forge_signature(message, n, e): 
   key_length = len(bin(n)) - 2
   block = b'\x00\x01\xff\x00' + HASH_ASN1[namePrefix] + HASH_FUNC[namePrefix]
   garbage = (((key_length + 7) // 8) - len(block)) * b'\xff'
   block += garbage

   pre_encryption = bytes_to_long(block)
   forged_sig = iroot(pre_encryption, e)[0]

   return long_to_bytes(forged_sig)

payload = base64.b64encode(forge_signature(msg, n, 3))

io.recvuntil(b'Enter the message you want to verify: ')
io.sendline(msg)
io.recvuntil(b'Enter its base64 signature: ')
io.sendline(payload)

io.interactive()


## Encrypt Message System
**server.py**

import secrets
import hashlib
from Crypto.Cipher import ChaCha20_Poly1305
from Crypto.Util.number import getPrime
import json

flag = b'KMACTF{******************************}'

l = 16
key = secrets.token_bytes(32)
def enc(cmt, nonce):
    nonce = hashlib.sha256(nonce).digest()[:12]
    cipher = ChaCha20_Poly1305.new(key=key, nonce=nonce)
    ct, tag = cipher.encrypt_and_digest(cmt)
    return nonce + ct + tag

def dec(cmt):
    nonce = cmt[:12]
    ct = cmt[12:-16]
    tag = cmt[-16:]
    cipher = ChaCha20_Poly1305.new(key=key, nonce=nonce)
    pt = cipher.decrypt_and_verify(ct, tag)
    return pt

def polynomial_evaluation(coefficients, x):
	at_x = 0
	for i in range(len(coefficients)):
		at_x += coefficients[i] * (x ** i)
		at_x = at_x % p
	return at_x

def verify(enc_message):
    message = dec(enc_message)
    print(message)
    if message == b'give me the flag':
        return True
    return False

print("Welcome to the encrypt message system\n")
print("1. Encrypt message")
print("2. Get flag")

p = getPrime(512)
print(f"p = {p}")

while True:
    try:
        option = input("Enter option: ")
        if option == "1":            
            coefficients = [secrets.randbelow(p) for _ in range(l)]
            print(f"coefficients = {coefficients}")
            message = input("Enter message: ")
            
            if message == "give me the flag":
                print("Invalid message")
                break
            
            x = int(input("Enter x: "))
            y = polynomial_evaluation(coefficients, x)
            encrypted = enc(message.encode(), str(y).encode())
            print(encrypted.hex())
        
        if option == "2":
            encrypted = bytes.fromhex(input("Enter encrypted message: "))
            try:
                if verify(encrypted):
                    print(flag)
            except:
                print("you failed")
                pass
    except: 
        print("Invalid input")
        break   

### Phân tích
Server có 2 chức năng chính như sau:
1. Encrypt message:
Nhận vào một message và giá trị $x$. Từ giá trị $x$ tạo `nonce` bằng các bỏ vào một đa thức với các hệ số cho trước. Sau đó `encrypt(message)` và in ra màn hình `nonce + ct + tag`.
2. Get flag:
Gửi đến các `nonce + ct + tag` của `encrypt('give me the flag')`. Server sẽ kiểm tra nếu đúng thì ta sẽ nhận được FLAG.

Khi đọc qua mình đã nghĩ đến việc sử dụng **Nonce reuse attack**.

### ChaCha20-Poly1305


Ciphertext được tạo ra từ **ChaCha20**.
Tag được tạo thành từ **Poly1305** và được định nghĩa như sau:

$tag = (((c_1 r^q + c_2 r^{ q−1} + \cdots + c_q r^1 ) \bmod 2^{130} - 5) + s) \bmod 2^{128}$

Trong đó $c_i$ là những encoded của $m$ và $(s,r)$ là one-time key được tạo ra từ hàm **Poly1305_Key_Gen**.

Với 2 tag được tạo thành từ một key và một nonce ta có:
$tag - tag' =((c_1 r^q + c_2 r^{ q−1} + \cdots + c_q r^1 ) \bmod 2^{130}-5) \bmod 2^{128}$ $- ((c'_1 r^q + c'_2 r^{ q−1} + \cdots + c'_q r^1 ) \bmod 2^{130}-5) \bmod 2^{128}$
suy ra:
$tag - tag' + 2^{128}k = (((c_1-c'_1) r^q + (c_2-c'_2) r^{ q−1} + \cdots + (c_q-c'_q) r^1 ) \bmod 2^{130}-5)$

, với $k \in \{-4,..., 4\}$

Ta có thể khôi phục lại $r$ và $s$ bằng việc giải pt ở trên. Brute $k$ để tìm được nghiệm đúng $r$. Sau đó tìm $s$. Và ta có `key = long_to_bytes(r) + long_to_bytes(s)`.

Mình sẽ dùng tool này để thực hiện attack:
- https://github.com/tl2cents/AEAD-Nonce-Reuse-Attacks?tab=readme-ov-file

### Script
Việc để nonce reuse khá dễ dàng ta chỉ cần chọn đại một giá trị $x$ và tìm được $y$. Với các lần encrypt sau ta chỉ cần dùng $y$ và coefficients để tìm $x$.
Scipt mình cứ viết từ từ rồi nghĩ tiếp nên nó khá dài 😅

from pwn import *
from sage.all import *
from chacha_poly1305_forgery import chachapoly1305_forgery_attack, chachapoly1305_forgery_attack_general
from chacha_poly1305_forgery import poly1305, sage_poly1305, recover_poly1305_key_from_nonce_reuse, chachapoly1305_nonce_reuse_attack, derive_poly1305_key


while 1:
    #io = process(['python3', 'server.py'])
    io = remote("157.15.86.73", 1305)
    io.recvuntil(b'p = ')
    p = int(io.recvuntil(b'\n')[:-1].decode())

    F = GF(p)

    def polynomial_evaluation(coefficients, x):
        at_x = 0
        for i in range(len(coefficients)):
            at_x += coefficients[i] * (x ** i)
        return at_x % p

    io.sendline(b'1')
    io.recvuntil(b'coefficients = ')
    message_1 = b'quandasssssssssssssssssss'
    io.sendline(message_1)
    coefficients = eval(io.recvuntil(b'\n')[:-1].decode())
    io.recvuntil(b'Enter x: ')
    x_1 = 1
    io.sendline(str(x_1).encode())
    enc1 = bytes.fromhex(io.recvline().decode())
    ct1 = enc1[12:-16]
    tag1 = enc1[-16:]

    y = polynomial_evaluation(coefficients, x_1)

    io.sendline(b'1')
    io.recvuntil(b'coefficients = ')
    message_2 = b'ziuanaaaaaaaaaaaaaaaaaaaaaaaaa'
    io.sendline(message_2)


    #R.<x> = PolynomialRing(F)
    R = PolynomialRing(F, names=('x',)); (x,) = R._first_ngens(1)
    coefficients = eval(io.recvuntil(b'\n')[:-1].decode())

    polynomial = sum(c * x**i for i, c in enumerate(coefficients))

    equation = polynomial - y
    roots = equation.roots()
    print(roots)
    if len(roots) == 0:
        continue
    x_2 = roots[0][0]
    io.recvuntil(b'Enter x: ')
    io.sendline(str(x_2).encode())
    assert y == polynomial_evaluation(coefficients, x_2)

    enc2 = bytes.fromhex(io.recvline().decode())
    ct2 = enc2[12:-16]
    tag2 = enc2[-16:]
   
    io.sendline(b'1')
    io.recvuntil(b'coefficients = ')
    message_3 = b'ziiiiiiiiiiiiiiiiiiiiiaaaaaaaaa'
    io.sendline(message_3)

    #R.<x> = PolynomialRing(F)
    R = PolynomialRing(F, names=('x',)); (x,) = R._first_ngens(1)
    coefficients = eval(io.recvuntil(b'\n')[:-1].decode())

    polynomial = sum(c * x**i for i, c in enumerate(coefficients))

    equation = polynomial - y
    roots = equation.roots()
    print(roots)
    if len(roots) == 0:
        continue
    x_3 = roots[0][0]
    io.recvuntil(b'Enter x: ')
    io.sendline(str(x_3).encode())
    assert y == polynomial_evaluation(coefficients, x_3)

    enc3 = bytes.fromhex(io.recvline().decode())
    ct3 = enc2[12:-16]
    tag3 = enc2[-16:]
    a1 = a2 =a3 = b""
    ct, tag = chachapoly1305_forgery_attack_general([a1, a2, a3], [ct1, ct2, ct3], [tag1, tag2, tag3], message_1, b'give me the flag', a1)
    
    nonce = enc2[:12]
    
    payload = nonce + ct + tag
    io.sendline(b'2')
    io.recvuntil(b'Enter encrypted message: ')
    io.sendline(payload.hex())
    res = io.recvline()
    if b'KMA' in res:
        io.interactive()
    io.sendline(b'asjhdjakhsdkahkd')

# io.interactive()


## pickleball

Thấy khá nhiều solve nên mình qua làm thử.
Bằng khả năng của trùm pico thì bài này khá đơn giản, FLAG được chia thành ba phần:

:::success
FLAG: KMACTF{p1Ckleb4ll_WitH-uU_piCklepal_5a6b89113abb}
:::

## zkp_of_qnr

Yeah và ta có một bài được viết bằng Rust.
**main.rs**

use num_bigint::BigUint;
use std::str::FromStr;
pub mod prover;
pub mod utils;
pub mod verifier;
use num_traits::cast::ToPrimitive;
use prover::*;
use std::fs::{self, File};
use std::io::{BufWriter, Write};
use utils::*;
use verifier::Verifier;

fn main() -> std::io::Result<()> {
    let flag = b"KMACTF{*******************************************}";
    let num_flag = bytes_to_biguint(flag);

    let num_rounds = num_flag.bits() as usize;

    // Define the folder name
    let folder_name = "Log";

    // Create the folder if it doesn't exist
    if fs::metadata(folder_name).is_err() {
        fs::create_dir(folder_name)?;
    }

    println!("Number of rounds: {}", num_rounds);

    let x = BigUint::from_str(
        "106276637345585586395178695555113419125706596151484787339368729136766801222943",
    )
    .unwrap();
    let y = BigUint::from_str(
        "67502870359608496464376733754660348616157530226832182619029429292243849029379",
    )
    .unwrap();

    let prover = Prover::new(x.clone(), y.clone(), num_rounds);
    let mut verifier = Verifier::new(x.clone(), y.clone(), num_rounds);

    for i in 0..num_rounds {
        let file_name = format!("{}/output_{}.txt", folder_name, i);
        let file = File::create(&file_name)?;

        let mut writer = BufWriter::new(file);

        writeln!(writer, "Round {}", i)?;

        let bit = ((&num_flag >> i) & BigUint::from(1_u32))
            .to_u32()
            .expect("Can not do this");

        let r = verifier.get_r();

        // give the prover the pair and r
        let w = verifier.gen_w(bit as i32, &r);
        let pair = verifier.gen_pairs();

        writeln!(writer, "w = {}", w)?;

        writeln!(writer, "Pair = ")?;
        for p in pair {
            writeln!(writer, "({}, {})", p.0, p.1)?;
        }

        let list_i = prover.gen_list_i();
        writeln!(writer, "list_i = {:?}", list_i)?;

        let v = verifier.respond(&bit, list_i, &r);

        let v = convert_rp_to_string(&v);

        writeln!(writer, "list_of_respond = ")?;
        for line in v {
            writeln!(writer, "{}", line)?;
        }

        writer.flush()?;
    }

    Ok(())
}

prover.rs

use num_bigint::BigUint;
use rand::Rng;

pub struct Prover {
    pub x: BigUint,
    pub y: BigUint,
    pub num_rounds: usize,
    pub list_i: Vec<Vec<u32>>,
}

impl Prover {
    pub fn new(x: BigUint, y: BigUint, n: usize) -> Self {
        Prover {
            x,
            y,
            num_rounds: n,
            list_i: Vec::new(),
        }
    }

    pub fn gen_list_i(&self) -> Vec<u32> {
        let mut rng = rand::thread_rng();
        let list_i: Vec<u32> = (0..self.num_rounds).map(|_| rng.gen_range(0..2)).collect();
        list_i
    }

    // I forgot to implement verify function
    // pub fn verify() -> {
    //
    // }
}

verifier.rs

use crate::utils::*;
use num_bigint::BigUint;
use serde_derive::Serialize;
pub struct Verifier {
    pub x: BigUint,
    pub y: BigUint,
    rs: Vec<Vec<(BigUint, BigUint)>>,
    pub pairs: Vec<Vec<(BigUint, BigUint)>>,
    pub num_rouns: usize,
}

#[derive(Serialize, Debug)]
pub enum Rp {
    Tuple(BigUint, BigUint),
    Number(BigUint),
}

impl Verifier {
    pub fn new(x: BigUint, y: BigUint, n: usize) -> Self {
        Verifier {
            x,
            y,
            rs: Vec::new(),
            pairs: Vec::new(),
            num_rouns: n,
        }
    }

    pub fn gen_w(&self, bit: i32, r: &BigUint) -> BigUint {
        if bit == 0 {
            r.modpow(&BigUint::from(2_u32), &self.x)
        } else {
            r.modpow(&BigUint::from(2_u32), &self.x) * &self.y % &self.x
        }
    }

    pub fn gen_pairs(&mut self) -> Vec<(BigUint, BigUint)> {
        let mut rr: Vec<(BigUint, BigUint)> = Vec::with_capacity(self.num_rouns);
        let mut pair: Vec<(BigUint, BigUint)> = Vec::with_capacity(self.num_rouns);
        for _ in 0..self.num_rouns {
            let r1 = rand_below(&self.x);
            let r2 = rand_below(&self.x);
            let a = r1.modpow(&BigUint::from(2_u32), &self.x);
            let b = r2.modpow(&BigUint::from(2_u32), &self.x) * &self.y % &self.x;

            pair.push((a, b));
            rr.push((r1, r2));
        }
        self.rs.push(rr.clone());
        self.pairs.push(pair.clone());
        pair
    }

    pub fn respond(&self, bit: &u32, list_i: Vec<u32>, r: &BigUint) -> Vec<Rp> {
        let mut v: Vec<Rp> = Vec::with_capacity(self.num_rouns);
        for (i, a) in list_i.iter().enumerate() {
            match (a, bit) {
                (&0, _) => {
                    let vj = &self.rs[self.rs.len() - 1][i];
                    v.push(Rp::Tuple(vj.0.clone(), vj.1.clone()));
                }
                (1, &0_u32) => {
                    let vj = r * &self.rs[self.rs.len() - 1][i].0 % &self.x;
                    v.push(Rp::Number(vj));
                }
                (1, &1_u32) => {
                    let vj = r * &self.rs[self.rs.len() - 1][i].1 * &self.y % &self.x;
                    v.push(Rp::Number(vj));
                }
                _ => panic!("Invalid input"),
            }
        }
        v
    }

    pub fn get_r(&self) -> BigUint {
        rand_below(&self.x)
    }
}

utils.rs

use crate::verifier::Rp;
use num_bigint::{BigUint, RandomBits};
use rand::Rng;

pub fn rand_below(n: &BigUint) -> BigUint {
    let mut rng = rand::thread_rng();
    let bit = n.bits();

    loop {
        let y: BigUint = rng.sample(RandomBits::new(bit));
        if y < *n {
            return y;
        }
    }
}

pub fn bytes_to_biguint(bytes: &[u8]) -> BigUint {
    BigUint::from_bytes_be(bytes)
}

pub fn convert_rp_to_string(v: &[Rp]) -> Vec<String> {
    let mut normal_numbers = vec![];
    for item in v {
        match item {
            Rp::Tuple(a, b) => {
                normal_numbers.push(format!("({}, {})", a, b));
            }
            Rp::Number(n) => {
                normal_numbers.push(format!("{}", n));
            }
        }
    }
    normal_numbers
}

Flag được mã hóa như sau:

    for i in 0..num_rounds {
        let file_name = format!("{}/output_{}.txt", folder_name, i);
        let file = File::create(&file_name)?;

        let mut writer = BufWriter::new(file);

        writeln!(writer, "Round {}", i)?;

        let bit = ((&num_flag >> i) & BigUint::from(1_u32))
            .to_u32()
            .expect("Can not do this");

        let r = verifier.get_r();

        // give the prover the pair and r
        let w = verifier.gen_w(bit as i32, &r);
        let pair = verifier.gen_pairs();

        writeln!(writer, "w = {}", w)?;

Nó sẽ lặp qua từng bit của Flag và tạo ra các giá trị như sau:

pub fn gen_w(&self, bit: i32, r: &BigUint) -> BigUint {
        if bit == 0 {
            r.modpow(&BigUint::from(2_u32), &self.x)
        } else {
            r.modpow(&BigUint::from(2_u32), &self.x) * &self.y % &self.x
        }
    }

với bit = 0: $w = r^2 \pmod x$
với bit = 1: $w = r^2*y \pmod x$

pub fn gen_pairs(&mut self) -> Vec<(BigUint, BigUint)> {
        let mut rr: Vec<(BigUint, BigUint)> = Vec::with_capacity(self.num_rouns);
        let mut pair: Vec<(BigUint, BigUint)> = Vec::with_capacity(self.num_rouns);
        for _ in 0..self.num_rouns {
            let r1 = rand_below(&self.x);
            let r2 = rand_below(&self.x);
            let a = r1.modpow(&BigUint::from(2_u32), &self.x);
            let b = r2.modpow(&BigUint::from(2_u32), &self.x) * &self.y % &self.x;

            pair.push((a, b));
            rr.push((r1, r2));
        }
        self.rs.push(rr.clone());
        self.pairs.push(pair.clone());
        pair
    }

hàm này sẽ trả về cho ta cặp giá trị.
$\begin{cases}a &=r_1^2 \pmod x \\ b &= r_2 ^2*y \pmod x \end{cases}$

    pub fn respond(&self, bit: &u32, list_i: Vec<u32>, r: &BigUint) -> Vec<Rp> {
        let mut v: Vec<Rp> = Vec::with_capacity(self.num_rouns);
        for (i, a) in list_i.iter().enumerate() {
            match (a, bit) {
                (&0, _) => {
                    let vj = &self.rs[self.rs.len() - 1][i];
                    v.push(Rp::Tuple(vj.0.clone(), vj.1.clone()));
                }
                (1, &0_u32) => {
                    let vj = r * &self.rs[self.rs.len() - 1][i].0 % &self.x;
                    v.push(Rp::Number(vj));
                }
                (1, &1_u32) => {
                    let vj = r * &self.rs[self.rs.len() - 1][i].1 * &self.y % &self.x;
                    v.push(Rp::Number(vj));
                }
                _ => panic!("Invalid input"),
            }
        }
        v
    }

Hàm này trả về các giá trị như sau:
- Nếu a = 0: Trả về $(r_1, r_2)$
- Nếu a = 1; bit = 0: trả về $vj = r*r_1 \pmod x$
- Nếu a = 1; bit = 1: trả về $vj = r*r_2*y \pmod x$

Như vậy ta có thể xác định bit của Flag bằng cách kiểm tra tại ví trí `a = 1`:
Nếu $vj^2 = a*w = r^2 * r_1^2 \pmod x$ thì tại đó `bit = 0`

File cho rất nhiều giá trị nhưng ta chỉ cần kiểm tra một ví trí có `a=1` là đủ.

num_rounds = 407 
folder_name = "Log"
flag = ''
x = 106276637345585586395178695555113419125706596151484787339368729136766801222943

from Crypto.Util.number import * 
from ast import literal_eval

for i in range(num_rounds):
    file_name = f"{folder_name}/output_{i}.txt"
    f = open(file_name, 'r')
    f.readline()
    w = int(f.readline().split('=')[1])
    
    f.readline()
    Pair = []
    for _ in range(407) : 
        Pair.append(literal_eval(f.readline()))
    
    
    list_i =  literal_eval(f.readline().split('=')[1])
    f.readline()
    list_of_respond = []
    for _ in range(10) : 
        list_of_respond.append(literal_eval(f.readline()))
    
    #dectect
    index = list_i.index(1)
    if(w * Pair[index][0] % x == pow(list_of_respond[index], 2, x)):
        flag += '0'
    else:
        flag+= '1'

print(long_to_bytes(int(flag[::-1],2)))

ở phần pair mình lấy hết để con trỏ nó chạy xuống dưới `list_of_respond`. Nếu không ta chỉ cần lấy tầm 10 giá trị là được rùi.

:::success
KMACTF{https://www.youtube.com/watch?v=fHCraDGaotM}
:::

## Let them share
server.py

import os 
import random
from Crypto.Util.number import bytes_to_long, getPrime

DEGREE = 10
BITSIZE = 64
FLAG = "KMACTF{s0m3_r3ad4ble_5tr1ng_like_7his}"

def get_coeff(p):
    # bigger coeff, safer sss :D
    while True:
        coeff = bytes_to_long(os.urandom(BITSIZE // 16).hex().upper().encode())
        if BITSIZE - 1 <= coeff.bit_length() and coeff < p:
            return coeff

def _eval_at(poly, x, prime):
    """Evaluates polynomial (coefficient tuple) at x, used to generate a
    shamir pool in make_random_shares below.
    """
    accum = 0
    for coeff in reversed(poly):
        accum *= x
        accum += coeff
        accum %= prime
    return x, accum

def make_random_shares(secret, modulus):
    coefficients = [secret] + [get_coeff(modulus) for _ in range(DEGREE)]
    return [_eval_at(coefficients, random.randint(0, modulus - 1), modulus) for _ in range(DEGREE)]

def main():
    p = getPrime(BITSIZE)
    SECRET = get_coeff(p)
    points = make_random_shares(SECRET, p)
    print("Wait, there's something wrong, is our secret lost ?")
    print("p =", p)
    print("points =", points)
    number = int(input("What's our secret ? "))
    if number == SECRET:
        print("Cool!! You can deal with hard challenge, get your treasure here:", FLAG)
        exit()
    else:
        print("We lost it! :((")
        exit()

if __name__ == "__main__":
    main()

việc của ta là tìm ra secret và gửi đến server để nhận flag.

def make_random_shares(secret, modulus):
    coefficients = [secret] + [get_coeff(modulus) for _ in range(DEGREE)]
    return [_eval_at(coefficients, random.randint(0, modulus - 1), modulus) for _ in range(DEGREE)]

Nhận thấy ta có 11 ẩn `coefficients` nhưng chỉ có 10 pt (DEGREE = 10).
Các pt có dạng: $y = coeff_{10}*x^{10} + coeff_9*x^9 + .. coeff_0$
Như vậy thì hệ pt này sẽ không giải được hoặc thiếu nghiệm.

Ta xem xét hàm `get_coeff()`

def get_coeff(p):
    # bigger coeff, safer sss :D
    while True:
        coeff = bytes_to_long(os.urandom(BITSIZE // 16).hex().upper().encode())
        if BITSIZE - 1 <= coeff.bit_length() and coeff < p:
            return coeff

Như vậy mỗi coeff được tạo ra bằng cách tạo ra 4 bytes ngẫu nhiên sau đó chuyển sang `HEX.upper().encode()`.
Với mỗi `coeff` ta có:
$coeff = a_1* 2^{56} + a_2 * 2^{48} + \cdots+ a_{8}*2^0$ với $a_i \in [48, 70]$ là các ký tự trong HEX.
Thế vào pt:
$y = (a_1*2^{56} + a_2*2^{48} + .. a_8*2^0)*x^{10} + (a_9*2^{56} + .. + a_{16}*2^0)*x^9 + ... + (a_{81}*2^{56} + a_{82}*2^{48} + .. + a_{88})$
Tương tự cho các `coeff` ta sẽ có tổng cộng là 88 ẩn. Với việc có được bounds của các ẩn này mình sẽ **solve linear** giải.

**script:** by anh Tuệ_AT19

from pwn import *
from json import * 
from ast import literal_eval
from Crypto.Util.number import *
io = remote('157.15.86.73', 2004)
io.recvuntil(b'p = ')

p = int(io.recvline()[:-1].decode()) 

io.recvuntil(b'points = ')
points = literal_eval(io.recvline()[:-1].decode())
scale = [2^i for i in range(56,-1,-8)]

x = []
b_values = []

for i in points :
    x.append(i[0])
    b_values.append(i[1])
    
DEGREE = 10
BITSIZE = 64
A_values = []
for i in x :
    multi_tmp = [(i^z)%p for z in range(10,-1,-1)]
    
    multi = []
    for o in multi_tmp :
        for f in scale :
            multi.append((o*f)%p)
    A_values.append(multi)

from sage.modules.free_module_integer import IntegerLattice
import numpy as np
from Crypto.Cipher import AES
from hashlib import sha256
from random import SystemRandom
import sys
from sage.all import GF, PolynomialRing, Zmod, matrix, QQ, ZZ, block_matrix, zero_matrix, vector
from copy import copy



"""
Solve a bounded system of modular linear equations.

(c) 2019-2022 Robert Xiao <[e-mail]>
https://robertxiao.ca

Originally developed in May 2019; updated July 2022

Please mention this software if it helps you solve a challenge!
"""

from collections.abc import Sequence
import math
import operator
from typing import List, Tuple
from sage.all import ZZ, gcd, matrix, prod, var


def _process_linear_equations(equations, vars, guesses) -> List[Tuple[List[int], int, int]]:
    result = []

    for rel, m in equations:
        op = rel.operator()
        if op is not operator.eq:
            raise TypeError(f"relation {rel}: not an equality relation")

        expr = (rel - rel.rhs()).lhs().expand()
        for var in expr.variables():
            if var not in vars:
                raise ValueError(f"relation {rel}: variable {var} is not bounded")

        # Fill in eqns block of B
        coeffs = []
        for var in vars:
            if expr.degree(var) >= 2:
                raise ValueError(f"relation {rel}: equation is not linear in {var}")
            coeff = expr.coefficient(var)
            if not coeff.is_constant():
                raise ValueError(f"relation {rel}: coefficient of {var} is not constant (equation is not linear)")
            if not coeff.is_integer():
                raise ValueError(f"relation {rel}: coefficient of {var} is not an integer")

            coeffs.append(int(coeff) % m)

        # Shift variables towards their guesses to reduce the (expected) length of the solution vector
        const = expr.subs({var: guesses[var] for var in vars})
        if not const.is_constant():
            raise ValueError(f"relation {rel}: failed to extract constant")
        if not const.is_integer():
            raise ValueError(f"relation {rel}: constant is not integer")

        const = int(const) % m

        result.append((coeffs, const, m))

    return result


def solve_linear_mod(equations, bounds, verbose=False, **lll_args):
    """Solve an arbitrary system of modular linear equations over different moduli.

    equations: A sequence of (lhs == rhs, M) pairs, where lhs and rhs are expressions and M is the modulus.
    bounds: A dictionary of {var: B} entries, where var is a variable and B is the bounds on that variable.
        Bounds may be specified in one of three ways:
        - A single integer X: Variable is assumed to be uniformly distributed in [0, X] with an expected value of X/2.
        - A tuple of integers (X, Y): Variable is assumed to be uniformly distributed in [X, Y] with an expected value of (X + Y)/2.
        - A tuple of integers (X, E, Y): Variable is assumed to be bounded within [X, Y] with an expected value of E.
        All variables used in the equations must be bounded.
    verbose: set to True to enable additional output
    lll_args: Additional arguments passed to LLL, for advanced usage.

    NOTE: Bounds are *soft*. This function may return solutions above the bounds. If this happens, and the result
    is incorrect, make some bounds tighter and try again.

    Tip: if you get an unwanted solution, try setting the expected values to that solution to force this function
    to produce a different solution.

    Tip: if your bounds are loose and you just want small solutions, set the expected values to zero for all
    loosely-bounded variables.

    >>> k = var('k')
    >>> # solve CRT
    >>> solve_linear_mod([(k == 2, 3), (k == 4, 5), (k == 3, 7)], {k: 3*5*7})
    {k: 59}

    >>> x,y = var('x,y')
    >>> solve_linear_mod([(2*x + 3*y == 7, 11), (3*x + 5*y == 3, 13), (2*x + 5*y == 6, 143)], {x: 143, y: 143})
    {x: 62, y: 5}

    >>> x,y = var('x,y')
    >>> # we can also solve homogenous equations, provided the guesses are zeroed
    >>> solve_linear_mod([(2*x + 5*y == 0, 1337)], {x: 5, y: 5}, guesses={x: 0, y: 0})
    {x: 5, y: -2}
    """

    # The general idea is to set up an integer matrix equation Ax=y by introducing extra variables for the quotients,
    # then use LLL to solve the equation. We introduce extra axes in the lattice to observe the actual solution x,
    # which works so long as the solutions are known to be bounded (which is of course the case for modular equations).
    # Scaling factors are configured to generally push the smallest vectors to have zeros for the relations, and to
    # scale disparate variables to approximately the same base.

    vars = list(bounds)
    guesses = {}
    var_scale = {}
    for var in vars:
        bound = bounds[var]
        if isinstance(bound, Sequence):
            if len(bound) == 2:
                xmin, xmax = map(int, bound)
                guess = (xmax - xmin) // 2 + xmin
            elif len(bound) == 3:
                xmin, guess, xmax = map(int, bound)
            else:
                raise TypeError("Bounds must be integers, 2-tuples or 3-tuples")
        else:
            xmin = 0
            xmax = int(bound)
            guess = xmax // 2
        if not xmin <= guess <= xmax:
            raise ValueError(f"Bound for variable {var} is invalid ({xmin=} {guess=} {xmax=})")
        var_scale[var] = max(xmax - guess, guess - xmin, 1)
        guesses[var] = guess

    var_bits = math.log2(int(prod(var_scale.values()))) + len(vars)
    mod_bits = math.log2(int(prod(m for rel, m in equations)))
    if verbose:
        print(f"verbose: variable entropy: {var_bits:.2f} bits")
        print(f"verbose: modulus entropy: {mod_bits:.2f} bits")

    # Extract coefficients from equations
    equation_coeffs = _process_linear_equations(equations, vars, guesses)

    is_inhom = any(const != 0 for coeffs, const, m in equation_coeffs)

    NR = len(equation_coeffs)
    NV = len(vars)
    if is_inhom:
        # Add one dummy variable for the constant term.
        NV += 1
    B = matrix(ZZ, NR + NV, NR + NV)

    # B format (rows are the basis for the lattice):
    # [ mods:NRxNR 0
    #   eqns:NVxNR vars:NVxNV ]
    # eqns correspond to equation axes, fi(...) = yi mod mi
    # vars correspond to variable axes, which effectively "observe" elements of the solution vector (x in Ax=y)
    # mods and vars are diagonal, so this matrix is lower triangular.

    # Compute maximum scale factor over all variables
    S = max(var_scale.values())

    # Compute equation scale such that the bounded solution vector (equation columns all zero)
    # will be shorter than any vector that has a nonzero equation column
    eqS = S << (NR + NV + 1)
    # If the equation is underconstrained, add additional scaling to find a solution anyway
    if var_bits > mod_bits:
        eqS <<= int((var_bits - mod_bits) / NR) + 1
    col_scales = []

    for ri, (coeffs, const, m) in enumerate(equation_coeffs):
        for vi, c in enumerate(coeffs):
            B[NR + vi, ri] = c
        if is_inhom:
            B[NR + NV - 1, ri] = const
        col_scales.append(eqS)
        B[ri, ri] = m

    # Compute per-variable scale such that the variable axes are scaled roughly equally
    for vi, var in enumerate(vars):
        col_scales.append(S // var_scale[var])
        # Fill in vars block of B
        B[NR + vi, NR + vi] = 1

    if is_inhom:
        # Const block: effectively, this is a bound of 1 on the constant term
        col_scales.append(S)
        B[NR + NV - 1, -1] = 1

    if verbose:
        print("verbose: scaling shifts:", [math.log2(int(s)) for s in col_scales])
        print("verbose: unscaled matrix before:")
        print(B.n())

    for i, s in enumerate(col_scales):
        B[:, i] *= s
    B = B.LLL(**lll_args)
    for i, s in enumerate(col_scales):
        B[:, i] /= s

    # Negate rows for more readable output
    for i in range(B.nrows()):
        if sum(x < 0 for x in B[i, :]) > sum(x > 0 for x in B[i, :]):
            B[i, :] *= -1
        if is_inhom and B[i, -1] < 0:
            B[i, :] *= -1

    if verbose:
        print("verbose: unscaled matrix after:")
        print(B.n())

    for row in B:
        if any(x != 0 for x in row[:NR]):
            # invalid solution: some relations are nonzero
            continue

        if is_inhom:
            # Each row is a potential solution, but some rows may not carry a constant.
            if row[-1] != 1:
                if verbose:
                    print(
                        "verbose: zero solution",
                        {var: row[NR + vi] for vi, var in enumerate(vars) if row[NR + vi] != 0},
                    )
                continue

        res = {}
        for vi, var in enumerate(vars):
            res[var] = row[NR + vi] + guesses[var]

        return res
a = [var(f"a_{i}") for i in range(len(A_values[0]))]

eqs = []
for x in range(len(A_values)) :
    eq = 0 
    assert len(A_values[x]) == len(a)
    for c,d in zip(A_values[x],a) :
        eq += c*d 
    
    eqs.append((b_values[x] == eq,p))
    
bounds = {x: (48,70) for x in a }
print(bounds)

sol = solve_linear_mod(eqs,bounds)

ks = list(sol.values())[-8:]
print(ks)
print(sol.values())
y = bytes(ks)
y = bytes_to_long(y)

io.sendline(str(y).encode())

io.interactive()

:::success
KMACTF{Us1nG_LLL_1s_4n_4rt_f0rm__:)))}
:::