TSJ CTF 2022 WriteUps

發表於
分類於 CTF

This time I created several challenges for TSJ CTF 2022, and I published my challenges and writeups in maple3142/My-CTF-Challenges. Due to GitHub’s poor support of mathjax rendering in markdown, I decided to create this one for readers of Crypto writeups.

For other categories, please read it here

Futago

  • Category: Crypto, CSC (Cursed Shaman Challenges, guessy challenges in TSJ CTF)
  • Score: 56/100 (CSC)
  • Solves: 14/428

Description

Who need source for RSA challenges?

Overview

See the README of this challenge.

Solution

Stage 1

Guess that two public keys shares a prime, so you can factor it with gcd.

Stage 2

Found out that n1=n2n_1=n_2, but e1e2e_1 \neq e_2. Using common modulus attack with found that gcd(e1,e2)=3\gcd(e_1,e_2)=3, so you need to take the cube root over integers to decrypt the message.

Stage 3

You got two seemingly normal 2048 bits RSA public key n1,n2n_1,n_2, but it is easy to see n1n2|n_1-n_2| is about 1024 bits only.

If you write them like this:

n1=pqn2=(p+a)(q+b)\begin{aligned} n_1 &= pq \\ n_2 &= (p+a)(q+b) \end{aligned}

Then substracting them:

n1n2=pb+qa+ab|n_1-n_2|=|pb+qa+ab|

Suppose p,qp,q are balanced, this means a,ba,b needs to be really small to keep n1n2|n_1-n_2| about 1024 bits only. So we have pp+ap \approx p+a and qq+bq \approx q+b.

Then you can multiply them together:

n1n2=pq(p+a)(q+b)n_1 n_2 = pq(p+a)(q+b)

It is easy to see pq(p+a)(q+b)pq \approx (p+a)(q+b) and p(q+b)q(p+a)p(q+b) \approx q(p+a) too. Running fermat factorization on n1n2n_1 n_2 will output these two pairs, and you can factor them with gcd.

from Crypto.PublicKey import RSA
from Crypto.Util.number import *


def read_stage(stage):
    with open(f"{stage}/key1.pub", "rb") as f:
        key1 = RSA.import_key(f.read())
    with open(f"{stage}/key2.pub", "rb") as f:
        key2 = RSA.import_key(f.read())
    with open(f"{stage}/flag.txt.key1.enc", "rb") as f:
        c1 = bytes_to_long(f.read())
    with open(f"{stage}/flag.txt.key2.enc", "rb") as f:
        c2 = bytes_to_long(f.read())
    ret = (key1.n, key1.e, c1, key2.n, key2.e, c2)
    return map(ZZ, ret)


def solve1():
    n1, e1, c1, n2, e2, c2 = read_stage("stage1")
    p = gcd(n1, n2)
    q = n1 // p
    d = inverse_mod(e1, (p - 1) * (q - 1))
    m = power_mod(c1, d, n1)
    return long_to_bytes(m)


def solve2():
    n1, e1, c1, n2, e2, c2 = read_stage("stage2")
    g, a, b = xgcd(e1, e2)
    mg = power_mod(c1, a, n1) * power_mod(c2, b, n1) % n1
    m = mg.nth_root(g)
    return long_to_bytes(m)


def solve3():
    n1, e1, c1, n2, e2, c2 = read_stage("stage3")

    def fermat(x, mx):
        a = floor(sqrt(x))
        b2 = a * a - x
        cnt = 0
        while True:
            if is_square(b2):
                b = floor(sqrt(b2))
                yield a + b, a - b
            a += 1
            cnt += 1
            if cnt == mx:
                return
            b2 = a * a - x

    ar = list(fermat(n1 * n2, 1000000))
    # print(ar)
    assert len(ar) == 2
    assert set(ar[1]) == set([n1, n2])
    p1 = gcd(ar[0][1], n1)
    # print(p1)
    p2 = gcd(ar[0][0], n2)
    # print(p2)

    q1 = n1 // p1
    d1 = inverse_mod(e1, (p1 - 1) * (q1 - 1))
    m = power_mod(c1, d1, n1)
    return long_to_bytes(m)


print(solve1() + solve2() + solve3())

RNG++

  • Category: Crypto
  • Score: 213/500
  • Solves: 21/428

This is actually a broken version of RNG+++.

Description

I encrypted the flag and messages by xoring them with a random number generator.

Overview

You got a simple LCG with si+1=Asi+C(modM)s_{i+1} = A s_i + C \pmod{M}, where A,CA,C are prime and MM is a power of 22. The flag are encrypted by xor it with initial state s0s_0. Some random messages are generated by randmsg are encrypted by the same way.

Solution

The first thing to notice is randmsg generated messages are all decimal digits, and they are 0x30 to 0x39 in ASCII. It is obvious that their binary representation are all 0011????, so we can get serveral non continuous bits of states sis_i.

The most simple unintended solution is to use z3. You just let the state be log2M\log_2{M} bits unsigned bitvector, and write LCG and specify the constraints, and it will magically found the state, so you can get the flag too.

Another more mathematical unintended solution by @Kuruwa: Since MM is a power of 22, reducing it to mod28i\bmod{2^{8i}} works too. And just do some bruteforce searching over the digits to see if it holds.

The intended solution will be in the writeup of RNG+++.

babyRSA

  • Category: Crypto
  • Score: 276/500
  • Solves: 13/428

Description

is this rsa?

Overview

We have n=pqn=pq, where pp is 1024 bit prime and qq is 512 bit prime. Define an elliptic curve E:y2=x3+px+qE: y^2=x^3+px+q over Zn\mathbb{Z}_n, flag (with some random padding) are encoded as x coordinate of a point PP on curve. The ciphertext is another point C=ePC=eP, where e=65537e=65537.

Solution

By substituting the coorinates of CC back to the original curve, we have ap+qr(modn)ap+q \equiv r \pmod{n}, where a,ra, r are known. If we change this equation to modp\bmod{p}, we get qr(modp)q \equiv r \pmod{p}.

Define another polynomial f(x)=rxf(x)=r-x, it is easy to see f(q)=0(modp)f(q)=0 \pmod{p}. Since qq is small compared to nn, we use Coppersmith’s method to solve for the root qq and factor nn.

For more details: Extensions of Coppersmith algorithm

Once you got p,qp,q, the remaining part should be easy. Change the curve to Fp\mathbb{F}_p and Fq\mathbb{F}_q and compute the order separately, and invert the scalar multiplication to get the flag.

from Crypto.Util.number import *

proof.arithmetic(False)

n = 1084688440161525456565761297723021343753253859795834242323030221791996428064155741632924019882056914573754134213933081812831553364457966850480783858044755351020146309359045120079375683828540222710035876926280456195986410270835982861232693029200103036191096111928833090012465092747472907628385292492824489792241681880212163064150211815610372913101079146216940331740232522884290993565482822803814551730856710106385508489039042473394392081462669609250933566332939789
xx, yy = (
    1079311510414830031139310538989364057627185699077021276018232243092942690870213059161389825534830969580365943449482350229248945906866520819967957236255440270989833744079711900768144840591483525815244585394421988274792758875782239418100536145352175259508289748680619234207733291893262219468921233103016818320457126934347062355978211746913204921678806713434052571635091703300179193823668800062505275903102987517403501907477305095029634601150501028521316347448735695,
    950119069222078086234887613499964523979451201727533569872219684563725731563439980545934017421736344519710579407356386725248959120187745206708940002584577645674737496282710258024067317510208074379116954056479277393224317887065763453906737739693144134777069382325155341867799398498938089764441925428778931400322389280512595265528512337796182736811112959040864126090875929813217718688941914085732678521954674134000433727451972397192521253852342394169735042490836886,
)

e = 65537

r = ZZ((yy ^ 2 - xx ^ 3) % n)
P = PolynomialRing(Zmod(n), "q")
q = P.gen()
f = r - q
q = ZZ(f.monic().small_roots(X=2 ^ 512, epsilon=0.8, beta=0.66)[0])
p = n // q
assert p * q == n

print((log(p) / log(n)).n())

E = EllipticCurve(Zmod(n), [p, q])

phi = E.change_ring(GF(p)).order() * E.change_ring(GF(q)).order()
d = inverse_mod(e, phi)
x, y = (d * E(xx, yy)).xy()
print(long_to_bytes(x))

Another way to factor it by @Kuruwa:

Since rq(modp)    r=q+xpr \equiv q \pmod{p} \implies r=q+xp, the vector v=(q2,2512q)v=(q^2,2^{512}q) will be in lattice spanned by the following basis BB.

B=[q+xp2512n0]B= \begin{bmatrix} q+xp & 2^{512} \\ n & 0 \end{bmatrix}

Since qq is just 512 bits, vv is probably a short vector in it. Run LLL or Lagrange-Gauss algorithm could produce the vector vv.

Top Secret

  • Category: Crypro
  • Score: 325/500
  • Solves: 9/428

Description

In year 2087, the TSJ corporation invented a new patented stream cipher to protect their communication. One day, another member stole an important file from the CEO’s computer, but it turns out to be encrypted. Fortunately, the script used to encrypt the file were stolen too. You, as a member of Nantou Resistance, accept the challenge to decrypt it.

Overview

This is a weird stream cipher that has an internal state s, and it will update its state using the forward/fast_forward function:

def forward(s: int, n: int, k: int) -> int:
    for _ in range(n):
        s = (s >> 1) ^ ((s & 1) * k)
    return s

The k is a known constant, and the n is the key of the cipher. The initialize state of the cipher is fixed too. The objective is to decrypt a PNG encrypted by it.

Solution

First, it is necessary to understand the meaning of s = (s >> 1) ^ ((s & 1) * k). If you ever tried to read the implementation of AES, you may find that it is pretty similar to the xtime operation. (An example in C)

xtime operation means multiplying an GF(28)GF(2^8) element by xx, and each element is represented by a polynomial of xx, modulo x8+x4+x3+x+1x^8+x^4+x^3+x+1. In AES, the lowest bit represents x0x^0, and the highest bit represents x7x^7.

In this challenge, the order of bits are swapped, so the bit shifting direction are different. And the constant k obvious represents a 128 degree polynomial…?

Actually, key = randbelow(2 ** 128) is meant to confuse people. If you try to construct the polynomial by f'{k:0128b}1' you will see it is not a prime polynomial, because its leftmost bit is 0. The correct degree is 127, so you can construct the field in Sage and implements fast_forward like this:

from sage.all import GF, var


def fast_forward(s, n, k):
    x = var("x")
    coefs = [int(x) for x in (f"{k:0127b}1")]
    poly = sum(c * x ** i for i, c in enumerate(coefs))
    F = GF(2 ** 127, "a", modulus=poly)
    a = F.gen()
    s_coefs = [int(x) for x in f"{s:0127b}"]
    ss = sum(c * a ** i for i, c in enumerate(s_coefs))
    sn = ss * a ** n
    return int("".join(map(str, sn.polynomial().list())).ljust(127, "0"), 2)

The next step is to observe that the first 16 bytes of PNG is known, not just 8 bytes, because of the IHDR chunk. Xor the first chunk of ciphertext and the first 16 bytes of PNG gives second state of the cipher. This can be written as:

s1=xkeys0    s1s01=xkeys_1 = x^{key} s_0 \implies s_1 s_0^{-1} = x^key

So this is a discrete log problem in GF(2127)GF(2^{127}). Unfortunately, 212712^{127}-1 is a mersenne prime, so you can’t use Pohlig–Hellman to compute keykey.

The intended way is to use Fast Evaluation of Logarithms in Fields of Characteristic Two , which can solve discrete log in this size easily, and it is implemented in pari too.

In Sage, you can just use pari.fflog(e, g) to find x such that g^x == e. In newer version of Sage (9.5 or above), e.log(g) works too.

from sage.all import var, GF, pari

s = 0x6BF1B9BAE2CA5BC9C7EF4BCD5AADBC47
k = 0x5C2B76970103D4EEFCD4A2C681CC400D

x = var("x")
coefs = [int(x) for x in (f"{k:0127b}1")]
poly = sum(c * x ** i for i, c in enumerate(coefs))
F = GF(2 ** 127, "a", modulus=poly)
alpha = F.gen()


def int2el(r):
    return sum(c * alpha ** i for i, c in enumerate(int(x) for x in f"{r:0127b}"))


with open("flag.png.enc", "rb") as f:
    data = f.read()

pngheader = bytes.fromhex("89504E470D0A1A0A0000000d49484452")

ks = bytes(x ^ y for x, y in zip(data, pngheader))
A = int2el(s)
B = int2el(int.from_bytes(ks, "big"))
key = int(pari.fflog(B / A, alpha))  # https://trac.sagemath.org/ticket/32842

from challenge import Cipher

with open("flag.png", "wb") as f:
    f.write(Cipher(key).decrypt(data))

By the way, @Utaha tells me that it is not necessary to compute the discrete log to solve this challenge. Because the key stream is just xkeys0,(xkey)2s0,(xkey)3s0x^{key}s_0, (x^{key})^2 s_0, (x^{key})^3 s_0 \cdots like a geometric progression. And xkeyx^{key} can be simply computed by s0s11s_0 s_1^{-1}, so it is enough to decrypt the flag actually.

Cipher Switching Service

  • Category: Crypto
  • Score: 416/500
  • Solves: 4/428

Description

You can freely swap the encrypted flag between two cryptosystem, but you still don’t know what is the flag.

Overview

The server prints one 1024 bits RSA public key and one 1024 bits ElGamal public key on connection, and gives an RSA encrypted randomly padded flag (padded length is 96 bytes). The length of the flag is 20.

Server supports two operations, allowing you to decrypt a RSA ciphertext and encrypt it using ElGamal, and vice versa.

Solution

Note: There is a much more simpler unintended solution idea from @Mystiz, scroll to the bottom to see

Using the homomorphic property of RSA, we can get any ciphertext of ammodnam \bmod{n}. ElGamal is encrypted as c1=gr,c2=yrmc_1=g^r, c_2=y^r m for some random number rr and public key y=gxy=g^x.

I use L(x,y)L(x,y) to denote Legendre Symbol here because it is hard to type in Latex. Obviously, L(c2,p)=L(yr,p)L(m,p)=L(g,p)rxL(m,p)L(c_2,p)=L(y^r,p) L(m,p)=L(g,p)^{rx} L(m,p). Also, by how gg is generated, it is easy to see L(g,p)=1L(g,p)=1, so we have L(m,p)=L(c2,p)L(m,p)=L(c_2,p).

When it decrypts aemea^e m^e with RSA private, it actually gives ammodnam \bmod{n}, so it is L(c2,p)=L(ammodn,p)L(c_2,p)=L(am \bmod{n},p) actually.

Suppose am<nam \lt n, ammodnam \bmod{n} is just amam, so L(c2,p)=L(a,p)L(m,p)L(c_2,p)=L(a,p) L(m,p) should hold. If amnam \ge n, L(c2,p)=L(a,p)L(m,p)L(c_2,p)=L(a,p) L(m,p) might not hold. From this, it is possible find aa such that amnam \approx n with binary search, so the flag mm is approximately na\lfloor\frac{n}{a}\rfloor.

Since the oracle is not really robust, might need to use some heuristic to make it more stable.

from pwn import *
import ast
from Crypto.Util.number import *
from gmpy2 import powmod as pow


def to_elgamal(c):
    io.sendlineafter(b"> ", b"1")
    io.sendlineafter(b"c = ", str(c).encode())
    return ast.literal_eval(io.recvlineS())


def to_rsa(c1, c2):
    io.sendlineafter(b"> ", b"2")
    io.sendlineafter(b"c1 = ", str(c1).encode())
    io.sendlineafter(b"c2 = ", str(c2).encode())
    return int(io.recvlineS())


def legendre(a, p):
    return pow(a, (p - 1) // 2, p)


io = remote("localhost", 8763)
io.recvuntil(b"RSA")
n, e = ast.literal_eval(io.recvlineS())
io.recvuntil(b"ElGamal")
p, g, y = ast.literal_eval(io.recvlineS())
io.recvuntil(b"len(flag) = ")
flagln = ast.literal_eval(io.recvlineS())
io.recvuntil(b"flagenc = ")
c = ast.literal_eval(io.recvlineS())
assert legendre(g, p) == 1


def legendre(a, p):
    r = pow(a, (p - 1) // 2, p)
    return r if r != p - 1 else -1


cnt = 0


def get_legendre(a):
    # get legendre((a * m) % n, p)
    global cnt
    cnt += 1
    ca = pow(a, e, n)
    cc = (ca * c) % n
    c1, c2 = to_elgamal(cc)
    lc2 = legendre(c2, p)
    return lc2


ln = 96
k_lb = int.from_bytes(b"TSJ{" + b"\x00" * (ln - 4), "big")
k_ub = int.from_bytes(b"TSJ{" + b"\xff" * (ln - 4), "big")
a_lb = n // k_ub
a_ub = n // k_lb

expected = get_legendre(1)


def oracle(a, b):
    # return True if a * k < n
    # no guarantee
    for i in range(a - b, a + b):
        if get_legendre(i) * legendre(i, p) != expected:
            return False
    return True


b = 3  # 3~4 is the best
t = 10
until = (a_ub - a_lb).bit_length() - (flagln - 4) * 8 - 5


def search(l, r, hist):
    # dfs with some pruning
    global b
    if (r - l).bit_length() < until:
        for aa in range(l, r):
            f = long_to_bytes(n // aa)
            if f.startswith(b"TSJ{"):
                print(f)
                break
        print(f"{cnt = }")
        exit()
    if sum(hist[-t:]) >= t or sum(hist[-t:]) <= -t:
        # because oracle may have false positive
        # discard current branch if it is search on a single direction
        print("bad", f"{t = }")
        b = min(b + 1, 10)  # increase bruteforcing window
        return t  # rewind t recursive call
    print((r - l).bit_length(), b)
    m = (r + l) // 2
    while True:
        if oracle(m, b):
            r = search(m, r, hist + [1])
            if r is not None and r > 0:
                return r - 1
        else:
            r = search(l, m, hist + [-1])
            if r is not None and r > 0:
                return r - 1
        if r != 0:
            break


search(a_lb, a_ub, [])

An unintended solution by @Mystiz is to find a kk such that kmkm is just slightly above pp, this means kmmodpkm \bmod{p} is kmpkm-p. By using homomorphic property of ElGamal you can get the RSA ciphertext of kmmodpkm \bmod{p}, which is just (kmp)e(km-p)^e. And you can just do gcd(mec,(kmp)ec)\gcd(m^e-c,(km-p)^e-c') to find the plaintext.

Signature

  • Category: Crypto
  • Score: 469/500
  • Solves: 2/428

Description

Another boring crypto challenge about signatures.

Overview

This challenge signs 6 signatures using ECDSA on Secp256k1. The nonce kk is generated by xoring hash zz and private key dd. The flag is encrypted with AES-CTR, key are derived from ECDSA private and IV are unknown.

Solution

This challenge is based on jonasnick/ecdsaPredictableNonce.

Need to use two basic facts:

  • ab=a+b2(ab)a \oplus b = a + b - 2 (a \land b)
  • For two n bits integer a,ba,b, ab=i=0n12iaibia \land b = \sum_{i=0}^{n-1} 2^i a_i b_i, where aia_i and bib_i is their n-th bit.

So ki=dzik_i=d \oplus z_i can be written as ki=d+z2j=0n1dizijk_i=d+z-2 \sum_{j=0}^{n-1} d_i z_{ij}. And it can be substituted back to skz+rd(modn)sk \equiv z+rd \pmod{n} to get a bunch of equations that have did_i as their roots.

In Secp256k1, dd is a 256 bit number. So in the jonasnick/ecdsaPredictableNonce, you can collect 256 signatures and solve did_i with linear algebra.

But it forgot an important fact: 0di10 \le d_i \le 1. This problem can be transform into finding a short vector in lattice, and use LLL to solve it.

Details are in the solution script

After recovering dd, we still need IV to decrypt the flag with AES-CTR. Notice there is a prefix Congrats! This is your flag: in the plaintext, we can take the first block and xor it with the first block of ciphertext, they decrypt it with the key. This is how AES-CTR works.

from fastecdsa.curve import secp256k1 as CURVE
from Crypto.Cipher import AES
from hashlib import sha256
from operator import xor
import ast

with open("output.txt") as f:
    sigs = []
    for _ in range(6):
        z, r, s = map(int, f.readline().strip().split())
        sigs.append((z, r, s))
    msgct = ast.literal_eval(f.readline())


def recover_d(sigs):
    P = PolynomialRing(Zmod(CURVE.q), "d", 256)
    ds = P.gens()
    dd = sum([2 ** i * di for i, di in enumerate(ds)])
    polys = []
    for z, r, s in sigs:
        d_and_z = sum([2 ** i * ((z & (1 << i)) >> i) * di for i, di in enumerate(ds)])
        # fact: (a xor b) = a + b - 2 * (a and b)
        k = dd + z - 2 * d_and_z
        polys.append((s * k) - (z + r * dd))
    M, v = Sequence(polys).coefficient_matrix()
    print(v.T)
    M = M.T.dense_matrix()
    a, b = M.dimensions()
    B = block_matrix(
        ZZ, [[matrix.identity(b) * CURVE.q, matrix.zero(b, a)], [M, matrix.identity(a)]]
    )
    B[:, :b] *= 2 ^ 64
    print("LLL", B.dimensions())
    for row in B.LLL():
        if row[:b] == 0 and row[-1] == 1 and all(0 <= x <= 1 for x in row[b:-1]):
            dbits = row[b:-1]
            d = int("".join(map(str, dbits[::-1])), 2)
            return d


d = recover_d(sigs)
print(f"{d = }")
key = sha256(str(d).encode()).digest()[:16]
nonce = AES.new(key, AES.MODE_ECB).decrypt(
    bytes(map(xor, b"Congrats! This is your flag: "[:16], msgct[:16]))
)[:8]
cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)
print(cipher.decrypt(msgct))

RNG+++

  • Category: Crypto
  • Score: 469/500
  • Solves: 2/428

This upgraded version of RNG++, so you might want to read it before reading this.

Description

I encrypted the flag and messages by xoring them with a random number generator again. But it should be harder to break this time.

Overview

Basically same as RNG++, but MM is a prime this time.

Solution

Since we only know some bits in each state sis_i, it can be written as:

si=Yi+j28uijs_i = Y_i + \sum_{j} 2^8 u_{ij}

YiY_i is a known part of each state and 0uij150 \leq u_{ij} \leq 15 are unknowns.This is equivalent to this binary representation:

0011????0011????0011????0011????0011????...

It is easy to see Asi+Csi+10(modM)A s_i + C - s_{i+1} \equiv 0 \pmod{M}, and trying to substitute sis_i with uiju_{ij} will find out that it is just some linear combination of uiju_{ij}. And the fact 0uij150 \leq u_{ij} \leq 15 tells us we need to find something small, so it isn’t too hard to think about lattice.

Using coefficient matrix of those polynomials (Asi+Csi+1A s_i + C - s_{i+1}), we can transform this problem into finding closest vector of a lattice. And using Babai Nearest Plane algorithm on a BKZ reduced basis (LLL reduced basis doesn’t work well here) allows you to find the correct uiju_{ij}.

from Crypto.Util.number import *
from operator import xor


with open("output.txt") as f:
    lines = f.readlines()
    M, A, C = [ZZ(x) for x in lines[0].strip().split()]
    sz = round(M.log(2))
    cts = [bytes_to_long(bytes.fromhex(line.strip())) for line in lines[1:]]

flagct = cts[0]
cts = cts[1:1+4]
n = len(cts)

mask1 = sum(
    [
        (1 << (7 + 8 * i))
        + (1 << (6 + 8 * i))
        + (1 << (5 + 8 * i))
        + (1 << (4 + 8 * i))
        for i in range(sz // 8)
    ]
)
mask2 = sum([+(1 << (5 + 8 * i)) + (1 << (4 + 8 * i)) for i in range(sz // 8)])
ys = [xor((mask1 & s), mask2) for s in cts]

F = Zmod(M)
# t = F(C / (1 - A))
unames = ",".join(sum([[f"u_{i}_{j}" for j in range(sz // 8)] for i in range(n)], []))
P = PolynomialRing(F, unames)
U = matrix(n, sz // 8, P.gens())
rs = [ys[i] + sum([2 ^ (8 * j) * U[i, j] for j in range(sz // 8)]) for i in range(n)]
fs = [A * r + C - rr for r, rr in zip(rs, rs[1:])]
# rs = [r - t for r in rs]  # substitution
# fs = [A ^ 1 * r - rr for r, rr in zip(rs, rs[1:])]

B, v = Sequence(fs).coefficient_matrix()
print(vector(v))
B = B.T.dense_matrix().change_ring(ZZ)
target = (-B[-1]).list()
B = B[:-1]
a, b = B.dimensions()
print(a, b)
I = matrix.identity(a)
B = block_matrix([[B, I], [M * matrix.identity(b), matrix.zero(b, a)]])
print(B.dimensions())


def Babai_CVP(mat, target):
    # M = mat.LLL()
    M = mat.BKZ(algorithm="NTL", prune=5)
    G = M.gram_schmidt()[0]
    diff = target
    for _ in range(1):
        for i in reversed(range(G.nrows())):
            diff -= M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff


cvp_target = vector(target + [8] * (n * sz // 8))
rr = Babai_CVP(B, cvp_target)
xx = B.solve_left(rr)
print("CVP")
print(rr)
print(xx)
print((rr - cvp_target).norm().n())
print()
found = xx[: n * (sz // 8)]
print(found)

if all(0 <= x < 16 for x in found):
    print("good")
    mat = matrix(n, sz // 8, found)
    ss = [
        ys[i] + sum([2 ^ (8 * j) * mat[i, j] for j in range(sz // 8)]) for i in range(n)
    ]
    print(ss)
    assert (A * ss[0] + C) % M == ss[1]
    flag = long_to_bytes(xor(ZZ(F(ss[0] - C) / A), flagct)).decode()
    print(f"TSJ{{{flag}}}")