France Cybersecurity Challenge 2025
Problèmeuh
import sys
from hashlib import sha256
sys.set_int_max_str_digits(31337)
try:
a, b, c, x, y = [ int(input(f"{x} = ")) for x in "abcxy" ]
assert a > 0
assert a == 487 * c
assert 159 * a == 485 * b
assert x ** 2 == a + b
assert y * (3 * y - 1) == 2 * b
h = sha256(str(a).encode()).hexdigest()
print("FCSC{" + h + "}")
except:
print("Nope!")
Generic pell solver:
n = 313
K.<sqrtn> = QuadraticField(n)
G = K.unit_group()
u0, u1 = G.gens()
u = K(u1)
i = 0
while True:
x, y = list(u**i)
if x**2 - n*y**2 == 1 and x.is_integer() and y.is_integer():
print(x, y)
i += 1
1
Rearrange 159 * a == 485 * b for b
2
sub b into x ** 2 == a + b
3
sub a == 487 * c
4
Deduce for integer solution, c must be a multiple of 485, so sub in c = 485*k
\[x^2 = \frac{644 \cdot 487 \cdot 485 \cdot k}{485} = 644 \cdot 487 \cdot k\]5
factor:
\[x^2 = 2^2 \cdot 7 \cdot 23 \cdot 487 \cdot k\]6
For x^2 to be square, all factors must have even exponents.
So deduce k = 7 * 23 * 487 * m^2 for some m
7
sub everything into b
\[b = \frac{159 \cdot a}{485} = \frac{159 \cdot 487 \cdot c}{485} = \frac{159 \cdot 487 \cdot 485 \cdot k}{485} = \frac{159 \cdot 487 \cdot 485 \cdot 7 \cdot 23 \cdot 487 \cdot m^2}{485}\]8
sub b into y * (3 * y - 1) == 2 * b
9
Multiply everything by 12 and it becomes a nice pell equation
\[(6 \cdot y - 1)^2 - 145710941544 \cdot m^2 = 1\]10
Solve the pell equation t^2 - 145710941544 * m^2 = 1
to obtain m and t = 6*y-1
11
Solve the rest
y = (t+1)/6
b = y*(3*y-1)/2
a = (485 * b)/159
implementation
def pell(n):
K.<sqrtn> = QuadraticField(n)
G = K.unit_group()
u0, u1 = G.gens()
u = K(u1)
i = 1
while True:
x, y = list(u**i)
if x**2 - n*y**2 == 1 and x.is_integer() and y.is_integer():
return x, y
i += 1
t, _ = pell(145710941544)
assert t < 10**31337
y = (t+1)/6
b = y*(3*y-1)/2
a = (485*b)/159
from hashlib import sha256
h = sha256(str(a).encode()).hexdigest()
print("FCSC{" + h + "}")
# FCSC{b313c611e23a09e5479b10793705fb40a7a32dbcbd8c4bc2b1a33e42c4579cae}
Kzber
import os
import json
import zlib
import base64
import pickle
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from sage.all import *
class Kzber:
def __init__(self, q = 3329, d = 256, k = 2, B = 2):
self.q = q
self.d = d
self.k = k
self.B = B
Zq, Y = PolynomialRing(GF(q), 'Y').objgen()
R, X = Zq.quotient_ring(Y**d - 1, 'X').objgen()
self.R = R
self.X = X
self._keygen()
def _sample_short_poly(self):
coeffs = [randint(-self.B, self.B) for i in range(self.d)]
return self.R(coeffs)
def _sample_short_vector(self):
return vector(self.R, [self._sample_short_poly(), self._sample_short_poly()]).column()
def _keygen(self):
A = random_matrix(self.R, 2, 2)
s = self._sample_short_vector()
e1 = self._sample_short_vector()
t = A * s + e1
self.sk = s
self.pk = (A, t)
def encrypt(self, m):
A, t = self.pk
r = self._sample_short_vector()
e2 = self._sample_short_vector()
e3 = self._sample_short_poly()
u = r.transpose() * A + e2.transpose()
v = r.transpose() * t + e3 + (int(round(self.q/2)) * self.R(m))
return u, v
def decrypt(self, c):
u, v = c
w = (v - u * self.sk)[0, 0]
coeffs = list(w)
coeffs = [int(wi) if int(wi) < self.q//2 else int(wi) - self.q for wi in coeffs]
return [0 if abs(wi) <= self.q//4 else 1 for wi in coeffs]
PKE = Kzber()
A, t = PKE.pk
sk = randint(0, 2 ** 128)
C = [ PKE.encrypt(int(m)) for m in f"{sk:0128b}" ]
flag = open("flag.txt", "rb").read()
iv = os.urandom(16)
E = AES.new(int.to_bytes(sk, 16), AES.MODE_CBC, iv = iv)
enc = E.encrypt(pad(flag, 16))
print(base64.b64encode(zlib.compress(pickle.dumps({
"A": A,
"t": t,
"C": C,
"flag" : {
"iv": iv,
"enc": enc,
}
}))).decode())
Solve:
The typo is in the quotient ring. Y**d - 1 should be Y**d + 1
https://eprint.iacr.org/2024/1287.pdf (section 4.5)
https://crypto.stackexchange.com/questions/103373/choice-of-polynomial-quotient-ring
First a look at an example of multiplying 2 polynomials in a ring.
sage: q = 3329
....: d = 3
....: Zq.<Y> = PolynomialRing(GF(q))
....: R.<X> = Zq.quotient_ring(Y**d + 1)
....:
....:
....: f = 7*X^2 + 3*X + 4
....: g = 9*X^2 + 8*X + 6
....: print(f*g)
....:
102*X^2 + 3316*X + 3270
How can we get that manually?
First multiply normally (ZZ):
sage: var('X')
X
sage: f = 7*X^2 + 3*X + 4
sage: g = 9*X^2 + 8*X + 6
sage: (f*g).expand()
63*X^4 + 83*X^3 + 102*X^2 + 50*X + 24
Now how do you do a polynomial modulo another polynomial? You can divide with polynomial long division, then take the remainder.
(63*X^4 + 83*X^3 + 102*X^2 + 50*X + 24)/(X^3 + 1) = quotient + remainder/(X^3 + 1)
We get remainder 102*X^2 - 13*X - 59
The final step is to just take all the coefficients mod q.
sage: q = 3329
sage: -13 % q
3316
sage: -59 % q
3270
And now we’ve reached the same correct answer, 102*X^2 + 3316*X + 3270
Depending on your quotient ring, there are nicer formulas.
I implemented this one https://crypto.stackexchange.com/questions/99866/modular-reduction-in-the-ring-mathbbz-qx-xn-1 for X^d + 1
q = 3329
#d = 128
d = 3
Zq.<Y> = PolynomialRing(GF(q))
R.<X> = Zq.quotient_ring(Y**d + 1)
f = R.random_element()
g = R.random_element()
print(f*g)
def poly_mul_quotient_ring(f, g, d, q):
# polynomial multiplication in the quotient ring X^d + 1 mod q
Rq.<z> = PolynomialRing(GF(q))
f = Rq(f.list())
g = Rq(g.list())
ff = f.list()
gg = g.list()
ff += [0] * (d - len(ff))
gg += [0] * (d - len(gg))
s1 = 0
for i in range(d):
for j in range(d-i):
s1 += ff[i] * gg[j] * z**(i+j)
s2 = 0
for i in range(1, d):
for j in range(d-i, d):
s2 += ff[i] * gg[j] * z**(i+j-d)
return s1 - s2
print(poly_mul_quotient_ring(f, g, d, q))
We ultimately want to break the LWE thing in the keygen with LLL
def _keygen(self):
A = random_matrix(self.R, 2, 2)
s = self._sample_short_vector()
e1 = self._sample_short_vector()
t = A * s + e1
Let’s visualise this:
class Kzber:
#def __init__(self, q = 3329, d = 256, k = 2, B = 2):
def __init__(self, q = 3329, d = 3, k = 2, B = 2):
self.q = q
self.d = d
self.k = k
self.B = B
Zq, Y = PolynomialRing(GF(q), 'Y').objgen()
R, X = Zq.quotient_ring(Y**d + 1, 'X').objgen()
self.R = R
self.X = X
self._keygen()
def _sample_short_poly(self):
coeffs = [randint(-self.B, self.B) for i in range(self.d)]
return self.R(coeffs)
def _sample_short_vector(self):
return vector(self.R, [self._sample_short_poly(), self._sample_short_poly()]).column()
def _keygen(self):
A = random_matrix(self.R, 2, 2)
s = self._sample_short_vector()
e = self._sample_short_vector()
t = A * s + e
self.sk = s
self.pk = (A, t)
self.e = e
PKE = Kzber()
q = PKE.q
d = PKE.d
A, t = PKE.pk
s = PKE.sk
e = PKE.e
assert t - A*s == e
Zq.<Y> = PolynomialRing(GF(q))
R.<X> = Zq.quotient_ring(Y**d + 1)
A00 = R(list(A[0][0]))
A01 = R(list(A[0][1]))
A10 = R(list(A[1][0]))
A11 = R(list(A[1][1]))
s0 = R(list(s[0][0]))
s1 = R(list(s[1][0]))
t0 = R(list(t[0][0]))
t1 = R(list(t[1][0]))
assert t0 - s0*A00 - s1*A01 == e[0][0]
assert t1 - s0*A10 - s1*A11 == e[1][0]
Now let’s use my own poly_mul_quotient_ring function I wrote:
def m(f, g):
ff = f.list()
gg = g.list()
ff += [0] * (d - len(ff))
gg += [0] * (d - len(gg))
s1 = 0
for i in range(d):
for j in range(d-i):
s1 += ff[i] * gg[j] * Y**(i+j)
s2 = 0
for i in range(1, d):
for j in range(d-i, d):
s2 += ff[i] * gg[j] * Y**(i+j-d)
return s1 - s2
PKE = Kzber()
q = PKE.q
d = PKE.d
A, t = PKE.pk
s = PKE.sk
e = PKE.e
assert t - A*s == e
Zq.<Y> = PolynomialRing(GF(q))
A00 = Zq(list(A[0][0]))
A01 = Zq(list(A[0][1]))
A10 = Zq(list(A[1][0]))
A11 = Zq(list(A[1][1]))
s0 = Zq(list(s[0][0]))
s1 = Zq(list(s[1][0]))
t0 = Zq(list(t[0][0]))
t1 = Zq(list(t[1][0]))
assert t0 - m(s0, A00) - m(s1, A01) == e[0][0]
assert t1 - m(s0, A10) - m(s1, A11) == e[1][0]
Rewrite again to just deal with only vectors instead of sage polynomials:
def m(ff, gg):
ret = [0]*d
for i in range(d):
for j in range(d-i):
ret[i+j] += ff[i] * gg[j]
for i in range(1, d):
for j in range(d-i, d):
ret[i+j-d] -= ff[i] * gg[j]
return vector(ZZ, ret)
PKE = Kzber()
q = PKE.q
d = PKE.d
A, t = PKE.pk
s = PKE.sk
e = PKE.e
assert t - A*s == e
A00 = vector([ZZ(i) for i in list(A[0][0])])
A01 = vector([ZZ(i) for i in list(A[0][1])])
A10 = vector([ZZ(i) for i in list(A[1][0])])
A11 = vector([ZZ(i) for i in list(A[1][1])])
s0 = vector([ZZ(i) for i in list(s[0][0])])
s1 = vector([ZZ(i) for i in list(s[1][0])])
t0 = vector([ZZ(i) for i in list(t[0][0])])
t1 = vector([ZZ(i) for i in list(t[1][0])])
assert [i%q for i in t0 - m(s0, A00) - m(s1, A01)] == list(e[0][0])
assert [i%q for i in t1 - m(s0, A10) - m(s1, A11)] == list(e[1][0])
Finally, with symbolic vars (I’ve reduced the degree and I’ll ignore t):
class Kzber:
#def __init__(self, q = 3329, d = 256, k = 2, B = 2):
def __init__(self, q = 3329, d = 5, k = 2, B = 2):
self.q = q
self.d = d
self.k = k
self.B = B
Zq, Y = PolynomialRing(GF(q), 'Y').objgen()
R, X = Zq.quotient_ring(Y**d + 1, 'X').objgen()
self.R = R
self.X = X
self._keygen()
def _sample_short_poly(self):
coeffs = [randint(-self.B, self.B) for i in range(self.d)]
return self.R(coeffs)
def _sample_short_vector(self):
return vector(self.R, [self._sample_short_poly(), self._sample_short_poly()]).column()
def _keygen(self):
A = random_matrix(self.R, 2, 2)
s = self._sample_short_vector()
e = self._sample_short_vector()
t = A * s + e
self.sk = s
self.pk = (A, t)
self.e = e
def m(ff, gg):
ret = [0]*d
for i in range(d):
for j in range(d-i):
ret[i+j] += ff[i] * gg[j]
for i in range(1, d):
for j in range(d-i, d):
ret[i+j-d] -= ff[i] * gg[j]
return vector(ret)
for d in range(3, 6):
PKE = Kzber(d=d)
q = PKE.q
d = PKE.d
A, t = PKE.pk
s = PKE.sk
e = PKE.e
assert t - A*s == e
A00 = [var(f'A00{i}') for i in range(d)]
A01 = [var(f'A01{i}') for i in range(d)]
A10 = [var(f'A10{i}') for i in range(d)]
A11 = [var(f'A11{i}') for i in range(d)]
s0 = [var(f's0{i}') for i in range(d)]
s1 = [var(f's1{i}') for i in range(d)]
print(f'{d = }')
for row in (-m(s0, A00) - m(s1, A01)):
print(row)
print()
You can observe this diagonal pattern:
d = 3
-A000*s00 + A002*s01 + A001*s02 - A010*s10 + A012*s11 + A011*s12
-A001*s00 - A000*s01 + A002*s02 - A011*s10 - A010*s11 + A012*s12
-A002*s00 - A001*s01 - A000*s02 - A012*s10 - A011*s11 - A010*s12
d = 4
-A000*s00 + A003*s01 + A002*s02 + A001*s03 - A010*s10 + A013*s11 + A012*s12 + A011*s13
-A001*s00 - A000*s01 + A003*s02 + A002*s03 - A011*s10 - A010*s11 + A013*s12 + A012*s13
-A002*s00 - A001*s01 - A000*s02 + A003*s03 - A012*s10 - A011*s11 - A010*s12 + A013*s13
-A003*s00 - A002*s01 - A001*s02 - A000*s03 - A013*s10 - A012*s11 - A011*s12 - A010*s13
d = 5
-A000*s00 + A004*s01 + A003*s02 + A002*s03 + A001*s04 - A010*s10 + A014*s11 + A013*s12 + A012*s13 + A011*s14
-A001*s00 - A000*s01 + A004*s02 + A003*s03 + A002*s04 - A011*s10 - A010*s11 + A014*s12 + A013*s13 + A012*s14
-A002*s00 - A001*s01 - A000*s02 + A004*s03 + A003*s04 - A012*s10 - A011*s11 - A010*s12 + A014*s13 + A013*s14
-A003*s00 - A002*s01 - A001*s02 - A000*s03 + A004*s04 - A013*s10 - A012*s11 - A011*s12 - A010*s13 + A014*s14
-A004*s00 - A003*s01 - A002*s02 - A001*s03 - A000*s04 - A014*s10 - A013*s11 - A012*s12 - A011*s13 - A010*s14
And can build them like this
def rotate_vec(v):
v = [v[-1]] + v[:-1]
return v
def build_submatrix(Ai):
M = []
for _ in range(d):
M.append(vector(Ai))
Ai = rotate_vec(Ai)
return Matrix([[-M[i][j] if i<=j else M[i][j] for i in range(d)] for j in range(d)])
POC smaller degree:
class Kzber:
#def __init__(self, q = 3329, d = 256, k = 2, B = 2):
def __init__(self, q = 3329, d = 20, k = 2, B = 2):
self.q = q
self.d = d
self.k = k
self.B = B
Zq, Y = PolynomialRing(GF(q), 'Y').objgen()
R, X = Zq.quotient_ring(Y**d + 1, 'X').objgen()
self.R = R
self.X = X
self._keygen()
def _sample_short_poly(self):
coeffs = [randint(-self.B, self.B) for i in range(self.d)]
return self.R(coeffs)
def _sample_short_vector(self):
return vector(self.R, [self._sample_short_poly(), self._sample_short_poly()]).column()
def _keygen(self):
A = random_matrix(self.R, 2, 2)
s = self._sample_short_vector()
e = self._sample_short_vector()
t = A * s + e
self.sk = s
self.pk = (A, t)
self.e = e
while True:
PKE = Kzber()
q = PKE.q
d = PKE.d
A, t = PKE.pk
s = PKE.sk
e = PKE.e
assert t - A*s == e
print([i if 0<=i<3 else int(i)-q for i in list(e[0][0])]) # e0
print('---')
A00 = [ZZ(i) for i in list(A[0][0])]
A01 = [ZZ(i) for i in list(A[0][1])]
A10 = [ZZ(i) for i in list(A[1][0])]
A11 = [ZZ(i) for i in list(A[1][1])]
t0 = [ZZ(i) for i in list(t[0][0])]
t1 = [ZZ(i) for i in list(t[1][0])]
def rotate_vec(v):
v = [v[-1]] + v[:-1]
return v
def build_submatrix(Ai):
M = []
for _ in range(d):
M.append(vector(Ai))
Ai = rotate_vec(Ai)
return Matrix([[-M[i][j] if i<=j else M[i][j] for i in range(d)] for j in range(d)])
MA = block_matrix([
[build_submatrix(A00), build_submatrix(A01)],
[identity_matrix(d), 0],
[0, identity_matrix(d)],
])
M = Matrix(t0 + [0]*d*2).T.augment(MA).augment((diagonal_matrix(d*[q]).stack(zero_matrix(d)).stack(zero_matrix(d)))).T.LLL()
print(M.dimensions())
for row in M:
if row == 0:
continue
for row in [row, -row]:
row = list(row)
if row[:d] == [i if 0<=i<3 else int(i)-q for i in list(e[0][0])]:
print('success')
exit()
Ok at this point I realised all my previous work was kinda dumb, I should’ve read the link I gave fully.
Let’s start again lol
Basically just work mod q and evaluate at 1, ignoring the ring.
PKE = Kzber()
q = PKE.q
d = PKE.d
A, t = PKE.pk
s = PKE.sk
e = PKE.e
assert t - A*s == e
Zq.<Y> = PolynomialRing(GF(q))
A00 = Zq(list(A[0][0]))(1)
A01 = Zq(list(A[0][1]))(1)
A10 = Zq(list(A[1][0]))(1)
A11 = Zq(list(A[1][1]))(1)
s0 = Zq(list(s[0][0]))(1)
s1 = Zq(list(s[1][0]))(1)
t0 = Zq(list(t[0][0]))(1)
t1 = Zq(list(t[1][0]))(1)
e0 = Zq(list(e[0][0]))(1)
e1 = Zq(list(e[1][0]))(1)
assert t0 - s0*A00 - s1*A01 == e0
assert t1 - s0*A10 - s1*A11 == e1
Solve s with LLL:
class Kzber:
def __init__(self, q = 3329, d = 256, k = 2, B = 2):
self.q = q
self.d = d
self.k = k
self.B = B
Zq, Y = PolynomialRing(GF(q), 'Y').objgen()
R, X = Zq.quotient_ring(Y**d - 1, 'X').objgen()
self.R = R
self.X = X
self._keygen()
def _sample_short_poly(self):
coeffs = [randint(-self.B, self.B) for i in range(self.d)]
return self.R(coeffs)
def _sample_short_vector(self):
return vector(self.R, [self._sample_short_poly(), self._sample_short_poly()]).column()
def _keygen(self):
A = random_matrix(self.R, 2, 2)
s = self._sample_short_vector()
e = self._sample_short_vector()
t = A * s + e
self.sk = s
self.e = e
self.pk = (A, t)
PKE = Kzber()
q = PKE.q
d = PKE.d
A, t = PKE.pk
s = PKE.sk
e = PKE.e
assert t - A*s == e
Zq.<Y> = PolynomialRing(GF(q))
A00 = Zq(list(A[0][0]))(1)
A01 = Zq(list(A[0][1]))(1)
A10 = Zq(list(A[1][0]))(1)
A11 = Zq(list(A[1][1]))(1)
s0 = Zq(list(s[0][0]))(1)
s1 = Zq(list(s[1][0]))(1)
t0 = Zq(list(t[0][0]))(1)
t1 = Zq(list(t[1][0]))(1)
e0 = Zq(list(e[0][0]))(1)
e1 = Zq(list(e[1][0]))(1)
assert t0 - s0*A00 - s1*A01 == e0
assert t1 - s0*A10 - s1*A11 == e1
target = [int(i.lift_centered()) for i in [e0, e1, s0, s1]]
print(target)
print('...')
M = Matrix(ZZ, [
[t0, A00, A01, q, 0],
[t1, A10, A11, 0, q],
[ 0, 1, 0, 0, 0],
[ 0, 0, 1, 0, 0],
[ 1, 0, 0, 0, 0],
]).T
for w1 in range(1, 40, 5):
for w2 in range(1, 40, 5):
W = diagonal_matrix([w1, w1, w2, w2, 1])
L = (M/W).dense_matrix().LLL()*W
for row in L:
for row in [row, -row]:
if row[-1] != 1:
continue
for b1 in [1, -1]:
for b2 in [1, -1]:
if [int(b1*row[0]), int(b1*row[1]), int(b2*row[2]), int(b2*row[3])] == target:
print('success')
Decryption (not perfect):
class Kzber:
def __init__(self, q = 3329, d = 256, k = 2, B = 2):
self.q = q
self.d = d
self.k = k
self.B = B
Zq, Y = PolynomialRing(GF(q), 'Y').objgen()
R, X = Zq.quotient_ring(Y**d - 1, 'X').objgen()
self.R = R
self.X = X
self._keygen()
def _sample_short_poly(self):
coeffs = [randint(-self.B, self.B) for i in range(self.d)]
return self.R(coeffs)
def _sample_short_vector(self):
return vector(self.R, [self._sample_short_poly(), self._sample_short_poly()]).column()
def _keygen(self):
A = random_matrix(self.R, 2, 2)
s = self._sample_short_vector()
e1 = self._sample_short_vector()
t = A * s + e1
self.sk = s
self.pk = (A, t)
def encrypt(self, m):
A, t = self.pk
r = self._sample_short_vector()
e2 = self._sample_short_vector()
e3 = self._sample_short_poly()
u = r.transpose() * A + e2.transpose()
v = r.transpose() * t + e3 + (int(round(self.q/2)) * self.R(m))
return u, v
def decrypt(self, c):
u, v = c
w = (v - u * self.sk)[0, 0]
coeffs = list(w)
coeffs = [int(wi) if int(wi) < self.q//2 else int(wi) - self.q for wi in coeffs]
if 1 in [0 if abs(wi) <= self.q//4 else 1 for wi in coeffs]:
return '1'
else:
return '0'
while True:
PKE = Kzber()
A, t = PKE.pk
q = PKE.q
s = PKE.sk
sk = randint(0, 2 ** 128)
print(sk)
C = [ PKE.encrypt(int(m)) for m in f"{sk:0128b}" ]
print( int(''.join([PKE.decrypt(i) for i in C]), 2) )
Zq.<Y> = PolynomialRing(GF(q))
s0 = Zq(list(s[0][0]))(1)
s1 = Zq(list(s[1][0]))(1)
def decrypt_injected(c, sk):
u, v = c
w = (v - u * sk)
return '0' if abs(w.lift_centered()) <= q//4 else '1'
C_injected = [[vector([u[0][0].lift()(1), u[0][1].lift()(1)]), v[0][0].lift()(1)] for u, v in C]
dec = int(''.join([decrypt_injected(i, vector([s0, s1])) for i in C_injected]), 2)
print(dec)
if dec == sk:
exit()
print()
Putting it all together:
from os import environ
environ['TERM'] = 'xterm'
from pwn import remote
import base64
from base64 import b64decode
from zlib import decompress
from Crypto.Cipher import AES
def flag_it(C, s, iv, enc):
q = 3329
def decrypt_injected(c, sk):
u, v = c
w = (v - u * sk)
return '0' if abs(w.lift_centered()) <= q//4 else '1'
C_injected = [[vector([u[0][0].lift()(1), u[0][1].lift()(1)]), v[0][0].lift()(1)] for u, v in C]
sk = int(''.join([decrypt_injected(i, s) for i in C_injected]), 2)
cipher = AES.new(int.to_bytes(sk, 16), AES.MODE_CBC, iv)
flag = cipher.decrypt(enc)
if b"FCSC" in flag:
print(flag)
assert False
def main():
io = remote('chall.fcsc.fr', 2155)
recv = io.recvall(timeout=60).decode().strip()
recv = loads(decompress(b64decode(recv)))
A = recv["A"]
t = recv["t"]
C = recv["C"]
iv = recv["flag"]["iv"]
enc = recv["flag"]["enc"]
A00 = A[0][0].lift()(1)
A01 = A[0][1].lift()(1)
A10 = A[1][0].lift()(1)
A11 = A[1][1].lift()(1)
t0 = t[0][0].lift()(1)
t1 = t[1][0].lift()(1)
q = 3329
M = Matrix(ZZ, [
[t0, A00, A01, q, 0],
[t1, A10, A11, 0, q],
[ 0, 1, 0, 0, 0],
[ 0, 0, 1, 0, 0],
[ 1, 0, 0, 0, 0],
]).T
possible_s = []
for w1 in range(1, 40, 5):
for w2 in range(1, 40, 5):
W = diagonal_matrix([w1, w1, w2, w2, 1])
L = (M/W).dense_matrix().LLL()*W
for row in L:
if abs(row[-1]) != 1:
continue
s = vector(GF(q), [row[2], row[3]])
for s in [s, -s]:
if s not in possible_s:
possible_s.append(s)
for s in possible_s:
flag_it(C, s, iv, enc)
while True:
main()
FCSC{9fa12c00603e0399fb84939704f7eea5626c715318578b5793b5da240b151984}