你是Lilac成员吗？
我觉得我是。
This time, I was invited as an author to contribute three Crypto challenges—myRSA, myBlock, and nestDLP—to LilacCTF 2026.
Unfortunately, there were both unintended solutions and cases of AI brute-forcing everything, but overall the solving situation still looks reasonably good 🤨?
Judging from the situation on 闲鱼,
myRSAvery likely involved cheating. However, due to the limitations of the CTF platform, we were unfortunately unable to track down the seller…
Noisy Forest#
import random
import hashlib
from secret import input_str
TOTAL_BITS = 50000
huge_int = random.getrandbits(TOTAL_BITS)
def is_chinese(char):
return '\u4e00' <= char <= '\u9fa5'
def add_unicode_noise(text, step=100, noise_bits=2):
noisy_text = ""
bit_stream_segments = []
temp_val = huge_int
num_chunks = (TOTAL_BITS + 31) // 32
for _ in range(num_chunks):
chunk_val = temp_val & 0xFFFFFFFF
bit_stream_segments.append(format(chunk_val, '032b'))
temp_val >>= 32
full_bit_stream = "".join(bit_stream_segments)
stream_ptr = 0
for char in text:
if is_chinese(char):
if stream_ptr + noise_bits > len(full_bit_stream):
noisy_text += char
continue
chunk = full_bit_stream[stream_ptr : stream_ptr + noise_bits]
noise_val = int(chunk, 2)
stream_ptr += noise_bits
original_code = ord(char)
noisy_text += chr(original_code + (noise_val * step))
else:
noisy_text += char
return noisy_text
step_val = 9997
NOISE_BITS = 1
output_str = add_unicode_noise(input_str, step=step_val, noise_bits=NOISE_BITS)
with open("ciphertext.txt", "w", encoding="utf-8") as f:
f.write(output_str)
flag_hash = hashlib.sha256(input_str.encode('utf-8')).hexdigest()
print(f"LilacCTF{{{flag_hash}}}")
#
# LilacCTF{df0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}An interesting classical cipher. The challenge reads a segment of Chinese plaintext, generates a 50000-bit random number, and then makes a bit-by-bit decision: if the current bit is 0, the plaintext character is left unchanged; if it is 1, the character’s Unicode code point is increased by 9997 (only Chinese characters are processed).
Obviously, once you manage to recover part of the plaintext, you can attack MT19937 to predict the random number (in theory, you could even treat this entirely as a classical cipher).
- The most straightforward observation is that if a Chinese character in the ciphertext, after subtracting 9997, is no longer a Chinese character, then the corresponding random bit must be 0.
- Going further, if a ciphertext character is a rare character, while subtracting 9997 yields a common character, then you can almost certainly conclude that the corresponding random bit is 1.
The remaining case is when both the ciphertext character and the character obtained by subtracting 9997 are common characters.
In this situation, you cannot directly determine the corresponding random bit, but there is still a way to handle it:
feed the two candidate sentences (corresponding to the two character choices) to an LLM and let it judge which sentence is more fluent, thereby inferring the corresponding random bit.
In practice, the number of such uncertain bits appearing in a sentence is not large, so the number of sentence variants that need to be fed to the LLM for each clause is also limited.
You can just pick a relatively small model, such as Qwen 2.5-0.5B, and compute the loss locally; the computational requirements are not very high.
After recovering enough random bits, you can attack MT and thus predict the random number to recover the full plaintext.
myRSA#
import gmpy2
from Crypto.Util.number import isPrime, bytes_to_long
from sympy.ntheory import sqrt_mod
from sympy.ntheory.modular import crt
from secret import p, q, r, pp
import os
def oracle(x):
root_p = sqrt_mod(x, p)
root_q = sqrt_mod(x, q)
root_r = sqrt_mod(x, r)
if root_p is None or root_q is None or root_r is None:
return "🤐"
ans, _ = crt([p, q, r], [root_p, root_q, root_r])
return int(ans)
assert p == pp**2 + 3 * pp + 3 and q == pp**2 + 5 * pp + 7
assert isPrime(p) and isPrime(q) and isPrime(r)
m = bytes_to_long(os.getenv("FLAG", "LilacCTF{fake_flag}").encode().strip())
n = p * q * r
e = 65537
c = pow(m, e, n)
print(f"{n = }")
print(f"{c = }")
while True:
x = int(input("🧭 > "))
_, is_psq = gmpy2.iroot(x, 2)
assert not is_psq, "👿"
assert 80 < x < 100
print(oracle(x))The challenge generates primes with a specific structure and then applies RSA. You are also given an oracle that allows you to query square roots of certain values modulo n. The core idea is actually very simple—it is essentially a special case of ECM. However, before talking about ECM, let’s first review what factorization algorithms such as Pollard p-1, Williams p+1, Bach–Shallit, and so on are fundamentally doing.
Abstractly and somewhat informally, all of these algorithms exploit certain special structures of primes to construct a group. Then, starting from a known element in the group, we perform operations on it to obtain a controllable result. Using this result, we can often construct a value that shares a non-trivial common factor with n, thereby factoring n.
For example, Pollard p-1 constructs the multiplicative group modulo p and then computes .
Back to this challenge. If you try it out first, you will find that the oracle only returns a value when the input is 96. Without exploiting the structure of the primes, an oracle with only a single valid output is almost useless.
However, if you are sensitive to algebraic number theory (or if you are clever enough to know how to prompt an LLM), you will notice that:
Primes of this form allow us to construct elliptic curves with complex multiplication (Complex Multiplication, CM). We know that for an elliptic curve with CM, its order satisfies , where is the Frobenius trace.
Here we have successfully obtained a group with a known order. From the discussion above, you should be able to feel that “obtaining a group with known structure” is crucial for the subsequent factorization. So our current goal is to first find this curve.
Moreover, for a CM elliptic curve , its Frobenius trace satisfies . In this challenge, this corresponds to .
By consulting references (or asking an AI), we can learn that CM with corresponds to curves of the form , which have sextic twists.
Since in this challenge , the sextic twists correspond to six curves, i.e., six different values of b. In theory, we need to know a primitive root g modulo p, and then take
to obtain these six curves and then find the one with the desired order.
However, for this challenge, you can infer from the fact that “only oracle(96) returns a value” that the smallest primitive root modulo p is not large, and thus enumerate all possible b. On the other hand, you can also directly construct , and then brute-force the x-coordinates to try to obtain the corresponding curve and point.
In summary, the curve required for this challenge is , and the point returned by oracle(96) is (4, …), which we denote as .
Placing E modulo p, we have . Thus, over , we have .
Furthermore, with high probability holds, so in Zmod we also have . At this point, we can simply compute to recover p.
This technique is also known as Lenstra elliptic-curve factorization.
from sage.all import *
from Crypto.Util.number import long_to_bytes, inverse
# fmt: off
n = 320463398964822335046388577512598439169912412662663009494347432623554394203670803089065987779128504277420596228400774827331351610218400792101575854579340551173392220602541203502751384517150046009415263351743602382113258267162420601780488075168957353780597674878144369327869964465070900596283281886408183175554478081038993938477659926361457163384937565266894839330377063520304463379213493662243218514993889537829099698656597997161855278297938355255410088350528543369288722795261835727770017939399082258134647208444374973242138569356754462210049877096486232693547694891534331539434254781094641373606991238019101335437
c = 80140760654462267017719473677495407945806989083076205994692983838456863987736401342704400427420046369099889997909749061368480651101102957366243793278412775082041015336890704820532767466703387606369163429880159007880606865852075573350086563934479736264492605192640115037085361523151744341819385022516548746015224651520456608321954049996777342018093920514055242719341522462068436565236490888149658105227332969276825894486219704822623333003530407496629970767624179771340249861283624439879882322915841180645525481839850978628245753026288794265196088121281665948230166544293876326256961232824906231788653397049122767633
# fmt: on
# for g in sieve_base:
# for i in range(6):
# E = EllipticCurve(Zmod(n), [0, g**i])
E = EllipticCurve(Zmod(n), [0, 32])
# input 96 and get G.y
G = E(4, 34484956620179866074070847926139804359063142072294116788718557980902699327115656987124274229028140189100320603969008330866286764246306228523522742687628880235600852992498136916120692433600681811756379032521946702982740835213837602607673998432757011503342362501420917079002053526006602493983327263888542981905944223306284758287900181549380023600320809126518577943982963226746085664799480543700126384554756984361274849594593385089122492057335848048936127343198814676002820177792439241938851191156589839212021554296197426022622140915752674220260151964958964867477793087927995204920387657229909976501960074230485827919)
p = int(gcd((n*G)[0], n))
pp = var('pp')
p_eq = pp**2 + 3 * pp + 3 - p
print(solve(p_eq, pp))
"""[
pp == 42372609047860809496808615943578116396728576268208028714215582866043762198485,
pp == -42372609047860809496808615943578116396728576268208028714215582866043762198488
]
"""
pp = 42372609047860809496808615943578116396728576268208028714215582866043762198485
q = pp**2 + 5 * pp + 7
r = n // (p * q)
m = pow(c, inverse(65537, (p - 1) * (q - 1) * (r - 1)), n)
print(long_to_bytes(m))myBlock#
from secrets import randbits
from cipher import myFeistel, ROUNDS
from hashlib import sha3_256
import signal
import os
def handler(_signum, _frame):
raise TimeoutError("⏰")
def oracle(nums, subkeys):
cipher = myFeistel(subkeys)
pts = [(randbits(16), randbits(16)) for _ in range(nums)]
cts = cipher.enc(pts)
print(pts)
print(cts)
if __name__ == "__main__":
signal.signal(signal.SIGALRM, handler)
signal.alarm(512)
flag = os.getenv("FLAG", "LilacCTF{fake_flag}")
subkeys = [randbits(16) for _ in range(ROUNDS)]
nums = int(input("🎫 > "))
assert nums < 675
oracle(nums, subkeys)
key = b"".join(subkeys[i].to_bytes(2, "big") for i in range(ROUNDS))
print(sha3_256(key).digest().hex())
guess = bytes.fromhex(input("🔑 > ").strip())
assert guess == key, "💥"
print(flag)POLY = 0x1002D
ROUNDS = 8
class myFeistel:
def __init__(self, subkeys):
assert len(subkeys) == ROUNDS
self.subkeys = subkeys
@staticmethod
def add(a, b):
return a ^ b
@staticmethod
def mul(a, b):
res = 0
for i in range(16):
if (b >> i) & 1:
res ^= a
high_bit = (a >> 15) & 1
a = (a << 1) & 0xFFFF
if high_bit:
a ^= POLY & 0xFFFF
return res
@staticmethod
def cube(a):
sq = myFeistel.mul(a, a)
return myFeistel.mul(sq, a)
def enc_block(self, L, R):
for k in self.subkeys:
T = self.cube(L ^ k)
new_R = R ^ T
new_L = L
L, R = new_R, new_L
return L, R
def enc(self, data):
return [self.enc_block(l, r) for l, r in data] # noqa: E741It only retains the Interpolation Attack part of the original challenge, and slightly increases both the exponentiation degree in the F function and the number of Feistel rounds, thereby blocking solutions based on naive Gröbner Basis methods.
The challenge workflow itself is not complicated: you are given an oracle that allows you to encrypt arbitrary plaintexts and returns the corresponding ciphertexts, and you are required to recover the subkey within 512 seconds.
I will not go into details about the Interpolation Attack here; interested readers can refer to RBTree’s blog ↗. In short, since the F function in this challenge can be represented as a polynomial and we know plaintext–ciphertext pairs, we can obtain a system of multivariate polynomial equations in terms of the subkey. What remains is simply to solve this system.
There are not many algorithms for solving multivariate polynomial systems: essentially the Gröbner Basis family (GB, F4, F5) and the XL family (linearization), possibly plus the Crossbred algorithm and a Polynomial Method that mostly exists only in papers. The intended solution for this challenge is to use the XL algorithm, with the Gaussian elimination step accelerated by a GPU.
The core idea of the XL algorithm is to multiply the original multivariate polynomial system by suitable monomials, then treat the resulting new monomials as variables, in order to obtain a linear system that can be solved via Gaussian elimination.
——However, during the competition it was discovered that the F function in this challenge is too simple, which causes the resulting equation system to have a highly symmetric structure. As a result, running XL or Gröbner Basis solvers purely on the CPU also becomes feasible.
nestDLP#
from sage.all import PolynomialRing, Zmod
from Crypto.Util.number import getPrime
from random import SystemRandom
random = SystemRandom()
def otp(bitlen: int) -> int:
half_len = bitlen // 2
left = ["0"] * (half_len - 1)
right = ["1"] * (half_len + 1)
bits = left + right
random.shuffle(bits)
return int("".join(bits), 2)
def get_exps(msg: bytes, nums: int) -> list[int]:
exps = []
blen = len(msg) * 8
m = int.from_bytes(msg, "big")
for _ in range(nums):
padding = otp(blen)
exps.append(m ^ padding)
return exps
if __name__ == "__main__":
flag = open("flag.txt", "rb").read().strip()
assert flag.startswith(b"LilacCTF{") and flag.endswith(b"}")
flag = flag[9:-1]
exps = get_exps(flag, 384)
p = getPrime(384)
R = PolynomialRing(Zmod(p**3), names="x,y")
x, y = R.gens()
I = R.ideal([x**3 + y**5 + 13 * x * y - 37, y**3 + x**5 + 37 * x - 13]) # noqa: E741
S = R.quotient(I, names=("x,y"))
g = S(x**2 + y**2 + 13 * x + 37 * y + 1337)
print(p)
for e in exps:
print(g**e)In the first part, the p-adic DLP over a multivariate polynomial quotient ring can be handled via multivariate Hensel lifting to reduce it to a DLP over . Alternatively, following the intended solution, one can use Gröbner Basis techniques to obtain a matrix representation and then transform the problem by taking the determinant. The second part is intended to be solved using ortools, but during the competition it was discovered that it can actually be solved entirely with lattices.
If we look at the scale of the original simOTP challenge, using @糖醋小鸡块’s lattice approach for Neutrality would require BLASter acceleration to solve it. This challenge is slightly larger than simOTP so I didn’t thoroughly sanity-check the parameters, and I didn’t expect it to be completely steamrolled by AI-generated lattices in one shot 😓from sage.all import prod, matrix, PolynomialRing, GF, Zmod
from tqdm import tqdm
from ortools.sat.python import cp_model
def projected_basis(I, p): # noqa: E741
R = I.ring()
names = R.variable_names()
Rfp = PolynomialRing(GF(p), names=names)
Ifp = Rfp.ideal([Rfp(f) for f in I.gens()])
basis_fp = Ifp.normal_basis()
xs = R.gens()
basis = []
for m in basis_fp:
exps = m.exponents()[0]
mon = prod(x**e for x, e in zip(xs, exps))
basis.append(mon)
return basis
def padic_dlp(g: int, y: int, p: int, s: int):
def theta(k, p, s):
return (pow(k, (p - 1) * p ** (s - 1), p ** (2 * s - 1)) - 1) // (p**s)
g, y, p, s = int(g), int(y), int(p), int(s)
return pow(theta(g, p, s), -1, p ** (s - 1)) * theta(y, p, s) % (p ** (s - 1))
def get_matrix(element, quotient_ring, p):
I = quotient_ring.defining_ideal() # noqa: E741
base_ring = quotient_ring.base_ring()
basis = projected_basis(I, p)
g_poly = element.lift()
matrix_cols = []
for b in basis:
prod_poly = g_poly * b
reduced_poly = quotient_ring(prod_poly).lift()
coeffs = [reduced_poly.monomial_coefficient(mon) for mon in basis]
matrix_cols.append(coeffs)
M = matrix(base_ring, matrix_cols).transpose()
return M
def solve(nums):
max_bits = max(n.bit_length() for n in nums)
bitlen = (max_bits + 7) // 8 * 8
byte_len = bitlen // 8
C_bits = []
for c in nums:
bits = f"{c:0{bitlen}b}"
C_bits.append([int(b) for b in bits])
model = cp_model.CpModel()
m = [model.NewBoolVar(f"m_{j}") for j in range(bitlen)]
B = [model.NewIntVar(0, 255, f"B_{i}") for i in range(byte_len)]
for i in range(byte_len):
model.Add(sum(((1 << (7 - k)) * m[i * 8 + k]) for k in range(8)) == B[i])
for i in range(byte_len):
model.Add(B[i] >= 32)
model.Add(B[i] <= 126)
W = (bitlen // 2) + 1
for c_bits in C_bits:
coeffs = []
for j in range(bitlen):
c = c_bits[j]
a = 1 - 2 * c # c=0 -> 1; c=1 -> -1
coeffs.append(a)
rhs = W - sum(c_bits)
model.Add(sum(coeffs[j] * m[j] for j in range(bitlen)) == rhs)
solver = cp_model.CpSolver()
solver.parameters.num_search_workers = 8
status = solver.Solve(model)
if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
print("No solution found.")
return
bs = [solver.Value(bv) for bv in B]
inner = bytes(bs).decode("ascii")
flag = f"LilacCTF{{{inner}}}"
print("FLAG:", flag)
if __name__ == "__main__":
with open("output.txt") as f:
p = int(f.readline().strip())
datas = f.readlines()
R = PolynomialRing(Zmod(p**3), names="x,y")
x, y = R.gens()
I = R.ideal([x**3 + y**5 + 13 * x * y - 37, y**3 + x**5 + 37 * x - 13]) # noqa: E741
S = R.quotient(I, names=("x", "y"))
g = S(x**2 + y**2 + 13 * x + 37 * y + 1337)
exps = []
for data in tqdm(datas, total=len(datas)):
h = S(eval(data))
det_g = get_matrix(g, S, p).det()
det_h = get_matrix(h, S, p).det()
log_det = padic_dlp(det_g, det_h, p, 3)
exps.append(log_det)
solve(exps)BootsTrapping#
#include "seal/seal.h"
#include "seal/util/ntt.h"
#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>
#include <cassert>
using namespace std;
using namespace seal;
using namespace seal::util;
uint64_t inverse(uint64_t a, uint64_t m) {
int64_t t = 0, newt = 1;
int64_t r = m, newr = a;
while (newr != 0) {
int64_t quotient = r / newr;
t = t - quotient * newt; swap(t, newt);
r = r - quotient * newr; swap(r, newr);
}
if (t < 0) t += m;
return (uint64_t)t;
}
string flag = "LilacCTF{XXXXXXXXXXXXXXX}";
int main() {
EncryptionParameters parms(scheme_type::ckks);
size_t n = 4096;
parms.set_poly_modulus_degree(n);
auto coeff_modulus = CoeffModulus::Create(n, { 30, 30, 30 });
parms.set_coeff_modulus(coeff_modulus);
SEALContext context(parms);
KeyGenerator keygen(context);
SecretKey secret_key = keygen.secret_key();
PublicKey public_key;
keygen.create_public_key(public_key);
Encryptor encryptor(context, public_key);
Decryptor decryptor(context, secret_key);
CKKSEncoder encoder(context);
Evaluator evaluator(context);
vector<double> input;
for(int i = 0; i < flag.size(); i++){
input.push_back(1.0*flag.at(i)/256);
}
for(int i = flag.size(); i < 50; i++){
input.push_back(0.5);
}
double scale = pow(2.0, 20);
Plaintext pt_init, pt_mask;
encoder.encode(input, scale, pt_init);
encoder.encode(0, scale, pt_mask);
Ciphertext ct, ct_mask;
encryptor.encrypt(pt_init, ct);
encryptor.encrypt(pt_mask, ct_mask);
evaluator.add_inplace(ct,ct_mask);
ofstream fs_ct("ciphertext.dat", ios::binary);
ct.save(fs_ct);
fs_ct.close();
ofstream fs_ct_mask("ciphertext_mask.dat", ios::binary);
ct_mask.save(fs_ct_mask);
fs_ct_mask.close();
while (context.get_context_data(ct.parms_id())->next_context_data()) {
evaluator.mod_switch_to_next_inplace(ct);
}
auto context_low = context.get_context_data(ct.parms_id());
auto context_high = context.get_context_data(context.first_parms_id());
auto &mod_high = context_high->parms().coeff_modulus();
int q_low = context_low->parms().coeff_modulus().back().value();
Ciphertext ct_high;
ct_high.resize(context, context.first_parms_id(), ct.size());
evaluator.transform_from_ntt_inplace(ct);
for (size_t poly_idx = 0; poly_idx < ct.size(); poly_idx++) {
for (size_t i = 0; i < n; i++) {
uint64_t raw_val = *(ct.data(poly_idx) + i);
for (size_t rns_idx = 0; rns_idx < mod_high.size(); rns_idx++) {
uint64_t qi = mod_high[rns_idx].value();
*(ct_high.data(poly_idx) + (rns_idx * n) + i) = raw_val % qi;
}
}
}
ct_high.is_ntt_form() = false;
ct_high.scale() = ct.scale();
evaluator.transform_to_ntt_inplace(ct_high);
Plaintext pt_kq;
decryptor.decrypt(ct_high, pt_kq);
for (size_t rns_idx = 0; rns_idx < mod_high.size(); rns_idx++) {
inverse_ntt_negacyclic_harvey(pt_kq.data() + (rns_idx * n), context_high->small_ntt_tables()[rns_idx]);
}
uint64_t Q = 1;
for(auto &m : mod_high) Q *= m.value();
for (size_t i = 0; i < n; i++) {
uint64_t X = 0;
for (size_t j = 0; j < mod_high.size(); j++) {
int qj = mod_high[j].value();
int vj = pt_kq.data()[j * n + i];
int Mj = Q / qj;
int invMj = inverse((Mj % qj), qj);
X = (X + (unsigned __int128)vj * Mj * invMj) % Q;
}
int signed_X = (X > Q / 2) ? (int)X - Q : X;
int clean_m = (signed_X % q_low);
if (clean_m > q_low / 2) clean_m -= q_low;
if (clean_m < -q_low / 2) clean_m += q_low;
for (size_t j = 0; j < mod_high.size(); j++) {
int qj = mod_high[j].value();
int limb = clean_m % qj;
if (limb < 0) limb += qj;
pt_kq.data()[j * n + i] = limb;
}
}
for (size_t rns_idx = 0; rns_idx < mod_high.size(); rns_idx++) {
ntt_negacyclic_harvey(pt_kq.data() + (rns_idx * n), context_high->small_ntt_tables()[rns_idx]);
}
pt_kq.parms_id() = context_high->parms_id();
vector<double> result;
encoder.decode(pt_kq, result);
for(int i = flag.size(); i < 50; i++){
cout << result[i] - input[i] << endl;
}
return 0;
}
/*
-1.63573e-05
-6.73093e-07
-2.00591e-06
-2.59483e-05
-1.44904e-05
-3.5275e-05
-2.47104e-05
*/This challenge examines the bootstrapping process of CKKS, where there is an integer overflow issue. The key to solving it lies in understanding that the keys used during bootstrapping are sparse, or in observing that the keys must be sparse in order to avoid triggering the overflow.