imaginaryCTF-Ⅰ • Misay's blog

赛题质量不错写一下blog来复盘

pwq#

task.py

from Crypto.Util.number import getPrime, bytes_to_long


m = b'ictf{REDACTED}'

p = getPrime(512)
q = getPrime(512)
w = getPrime(400)

N = p * q

ct = pow(bytes_to_long(m),0x10001,N)
hint = pow(p+q,0x10001,w)

print(f"ct = {ct}")
print(f"w = {w}")
print(f"N = {N}")
print(f"hint = {hint}")

RSA相关给出

h\equiv (p+q)^e \mod w

$w$ 已知可以直接解出

p+q\mod w

又已知 $n=pq$ 可以分别解出 $p_0\equiv p\mod w$ 与 $q_0\equiv q\mod w$ 此时可做

p=uw+p_0

q=vw+q_0

未知量 $u\;v\sim2^{112}$ 构造

(uw+p_0)(vw+q_0)\equiv 0\mod n

2^{112}\lt n^{\frac{1}{8}}

打二元Copper即可

exp.sage

from sage.all import *
from Crypto.Util.number import long_to_bytes
import itertools

ct = 33742801557737914301901758559773831721843597978574609375921011645265195943976625144590771297602879590127872129996873293713011525883543502714062823608171155290413260608149852074509908003146800678440445886970444074021592724652271171760839657854820704492173967811290731517610626718548890222659813688028758740276
w = 1333784115660651539426484312602224132943210956786085047526154379154338526734338314429353112586107913320509925611218257033
N = 112798766402177436729349365676331693992552968963886648322556025048578258372898748992930617929101204247707637182037063215803739825565173179631633516061095595677836327208144578596531454197942860179720300613793209449731317719547805213007449821013788848923929225904305654955777258574354919679160321088284094400591
hint = 630804891598507417470106737947995598552415288963827588976836412594062559962786200570507255312369893282748568763446527802
e = 0x10001

d_w = inverse_mod(e, w - 1)
S = power_mod(hint, d_w, w)
print('S:', S)

# p = s1 + u*w   q = s2 + v*w  s1 + s2 = s
# triple Coppersmith

def small_roots(f, bounds, m=5, d=None):
    if not d:
        d = f.degree()
 
    R = f.base_ring()
    N = R.cardinality()
 
    # f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
 
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
 
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
 
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
 
    B = B.dense_matrix().LLL()
 
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
 
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

P.<x> = PolynomialRing(Zmod(w))
# solve p mod w  q mod w
g = x^2 - S*x + N
roots = g.roots()
print('roots:', roots)
s1 = Integer(roots[0][0])
s2 = Integer(roots[1][0])
assert (s1 + s2) % w == S
print(f"p mod w: {s1}")
print(f"q mod w: {s2}")

R.<u,v> = PolynomialRing(Zmod(N))
f = (s1 + u*w) * (s2 + v*w)

roots = small_roots(f, (2^113, 2^113))
print(roots)
u = Integer(roots[0][0])
v = Integer(roots[0][1])
p = s1 + u*w
assert N % p == 0
q = s2 + v*w
assert N % q == 0

phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
m = long_to_bytes(pow(ct, d, N))
print(m)
# ictf{generic_monthly_coppersmith_challenge}

RSA2026#

server.py

from Crypto.Util.number import *
FLAG = b"ictf{REDACTED123456}"
assert len(FLAG) == 20

while True:
  print("Let's build an RSA-2026 public key together! I provide the exponent, you provide the modulu.")
  e = getRandomNBitInteger(2026)
  N = int(input("N = "))
  assert e.bit_length() == N.bit_length() == 2026, "We failed to collaborate on a RSA-2026 key :("
  
  m = bytes_to_long(FLAG)
  c = pow(m, N, e) # I might have mixed up the exponent and modulus. oh well
  print(f"{c = }")

修正一下参数顺序

靶机生成2026bits模数 $N$ ,我们可以自己构造2026bits公钥指数 $e$ 得到密文

本题关键切入有两个

flag 只有160bits

模数 $N$ 的生成调用的是getRandomNBitInteger 也就是说是有可能生成一个合数的

考虑取比较多组数据 $(e_i,N_i)$ 得到 $c_i$ 对于一系列较小的我们提前假设好素数 $a_i$ 当 $N_i$ 取足够多时能够得到 $a_i \;|\; N_i$ 这个概率大约是 $\frac{1}{a_i}$ 如果我们传入的 $e_i$ 对应 $\phi(a_i)=a_i-1$ 可逆我们就可以解出 $m_i\equiv m\mod a_i$ 积累足够多数据做CRT即可恢复 $m$

本题取了20000组数据构造一致的2026bits的大素数 $e_i$

data-collect.py

from concurrent.futures import ThreadPoolExecutor, as_completed
from threading import Lock

from pwn import remote
from Crypto.Util.number import getPrime
from tqdm import tqdm

HOST = "155.248.210.243"
PORT = 42126
TARGET = 20000
WORKERS = 24
OUT_FILE = "data.txt"


def connect():
    io = remote(HOST, PORT)
    io.recvuntil(b"N = ")
    return io


def collect_chunk(n_value: int, amount: int, progress, progress_lock: Lock):
    chunk = []
    io = connect()

    while len(chunk) < amount:
        try:
            io.sendline(str(n_value).encode())
            line = io.recvline(timeout=5)
            if not line:
                raise EOFError("empty response")
            if b"c = " not in line:
                raise ValueError(f"unexpected line: {line!r}")

            c_value = int(line.strip().split(b"=", 1)[1])
            chunk.append(c_value)
            io.recvuntil(b"N = ")

            with progress_lock:
                progress.update(1)
        except Exception:
            try:
                io.close()
            except Exception:
                pass
            io = connect()

    try:
        io.close()
    except Exception:
        pass

    return chunk


def main():
    n_value = getPrime(2026)
    worker_count = min(WORKERS, TARGET)
    print(f"[+] fixed N bit_length={n_value.bit_length()} workers={worker_count}")

    base = TARGET // worker_count
    remainder = TARGET % worker_count
    chunks = [base + (1 if i < remainder else 0) for i in range(worker_count)]

    progress_lock = Lock()
    all_samples = []

    with tqdm(total=TARGET, desc="collect") as progress:
        with ThreadPoolExecutor(max_workers=worker_count) as executor:
            futures = [
                executor.submit(collect_chunk, n_value, amount, progress, progress_lock)
                for amount in chunks
            ]
            for future in as_completed(futures):
                all_samples.extend(future.result())

    with open(OUT_FILE, "w", encoding="utf-8") as output:
        output.write(f"# N={n_value}\n")
        for c_value in all_samples:
            output.write(f"{c_value}\n")

    print(f"[+] saved {len(all_samples)} samples to {OUT_FILE}")


if __name__ == "__main__":
    main()

24线程大约跑15分钟

recover.py

from math import gcd

from Crypto.Util.number import inverse, long_to_bytes, isPrime


DATA_FILE = "data.txt"
MAX_P = 127
MIN_GAP = 40
FLAG_LEN = 20
PREFIX = b"ictf{"
SUFFIX = b"}"


def prime_list(limit: int):
    primes = []
    for value in range(3, limit + 1):
        if isPrime(value):
            primes.append(value)
    return primes


def parse_data(path: str):
    with open(path, "r", encoding="utf-8") as file:
        lines = [line.strip() for line in file if line.strip()]

    if not lines or not lines[0].startswith("# N="):
        raise ValueError("data file must start with '# N=<int>'")

    n_value = int(lines[0].split("=", 1)[1])
    samples = [int(line) for line in lines[1:]]
    return n_value, samples


def top_two_counts(samples, p: int):
    counts = [0] * p
    for c_value in samples:
        counts[c_value % p] += 1
    ranked = sorted(range(p), key=lambda residue: counts[residue], reverse=True)
    top1 = ranked[0]
    top2 = ranked[1]
    return top1, counts[top1], top2, counts[top2]


def crt_pair(a1: int, m1: int, a2: int, m2: int):
    inv = inverse(m1 % m2, m2)
    k = ((a2 - a1) % m2) * inv % m2
    merged = a1 + m1 * k
    modulus = m1 * m2
    return merged % modulus, modulus


def combine_crt(congruences):
    value, modulus = congruences[0]
    for next_value, next_modulus in congruences[1:]:
        value, modulus = crt_pair(value, modulus, next_value, next_modulus)
    return value, modulus


def is_printable_ascii(data: bytes):
    return all(32 <= byte <= 126 for byte in data)


def main():
    n_value, samples = parse_data(DATA_FILE)
    print(f"[+] loaded samples={len(samples)} N_bits={n_value.bit_length()}")

    congruences = []
    used_primes = []

    for p in prime_list(MAX_P):
        if gcd(n_value, p - 1) != 1:
            continue

        top_residue, top_count, second_residue, second_count = top_two_counts(samples, p)
        gap = top_count - second_count
        if gap < MIN_GAP:
            continue

        exp_inv = inverse(n_value % (p - 1), p - 1)
        m_mod_p = pow(top_residue, exp_inv, p)
        congruences.append((m_mod_p, p))
        used_primes.append((p, gap, top_residue, second_residue))

    if not congruences:
        raise RuntimeError("no valid congruences found; increase samples or lower MIN_GAP")

    m0, modulus = combine_crt(congruences)
    print(f"[+] used primes={len(congruences)} CRT_bits={modulus.bit_length()}")

    for p, gap, top_residue, second_residue in used_primes:
        print(f"    p={p:>3} gap={gap:>4} top={top_residue:>3} second={second_residue:>3}")

    if modulus.bit_length() >= FLAG_LEN * 8:
        candidate = long_to_bytes(m0, FLAG_LEN)
        print(f"[+] candidate={candidate}")
        if candidate.startswith(PREFIX) and candidate.endswith(SUFFIX):
            print(f"[+] FLAG likely: {candidate.decode(errors='ignore')}")
        elif is_printable_ascii(candidate):
            print("[?] candidate is printable ASCII but format mismatch")
    else:
        print("[!] CRT modulus too small for unique 20-byte recovery")
        print("[!] try larger MAX_P or collect more samples")


if __name__ == "__main__":
    main()


# ictf{sh0rt_fl4g_l0l}

Equinox#

ECC.py


class ECC:
    def __init__(self, a, b, p):
        self.a = a % p
        self.b = b % p
        self.p = p

    def inv(self, x):
        if x % self.p == 0:
            return None
        return pow(x, self.p - 2, self.p)

    def add(self, P, Q):
        if P is None: return Q
        if Q is None: return P

        x1, y1 = P
        x2, y2 = Q
        
        if x1 == x2 and (y1 + y2) % self.p == 0:
            return None

        if P == Q:
            num = (3 * x1 * x1 + self.a)
            den = (2 * y1)
        else:
            num = (y2 - y1)
            den = (x2 - x1)

        inv_den = self.inv(den)
        if inv_den is None:
            return None
            
        m = (num * inv_den) % self.p
        x3 = (m * m - x1 - x2) % self.p
        y3 = (m * (x1 - x3) - y1) % self.p
        return (x3, y3)

    def mul(self, k, P):
        R = None
        Q = P

        while k > 0:
            if k & 1:
                R = self.add(R, Q)
            Q = self.add(Q, Q)
            k >>= 1

        return R

Equinox.py

from ECC import ECC
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Random import random
from Crypto.Hash import SHA256
from Crypto.Cipher import AES



#cryptographically safe curve params
gens = [13188118025080711829022518351884446943050377821527037811365908495,23899821555513862312200164500716013270997305429524362731285660314 ]
a = 4865221480871918980735535897980865817234292524771826877403276978
b = 12424209829949936204181246920695524007984572978335931676282863845
p = 26328072917139296674479506920917642091979664886232678979756108269


curve = ECC(a,b,p)



key = random.getrandbits(128)


flag = b'ictf{11REDACTED}'

cipher = AES.new(long_to_bytes(key),AES.MODE_ECB)

print(f"flag = {bytes_to_long(cipher.encrypt(flag))}")


#very cute looking eclaire
class Equinox:
    def __init__(self):
        self.a = random.getrandbits(215)
        
    def scramble(self,seed):
        h = bytes_to_long(SHA256.new(seed).digest()) & ((1 << 215) - 1)       
        self.a = self.a ^ h

    def giveHint(self,P):
        Q = curve.mul(self.a,P)
        return (Q[1] + key) % p


G = curve.mul(random.getrandbits(215),gens)

horse = Equinox()

print(f"hint_1 = {horse.giveHint(G)}")


while(True):
    option = int(input("option: "))
    
    if option == 1:
        seed = input("msg? ").encode()
        horse.scramble(seed)
    elif option == 2:
        print(f"hint_2 = {horse.giveHint(G)}")
        break
    else:
        print("sorry I don't understand that")
        break

基于ECC的Oracle靶机

这里给出了一个标准的ECC的Wiersstrass曲线编码一个曲线

\mathbf{E}:y^2\equiv x^3+ax+b\mod p

曲线不奇异看似很正常阶数和 $p$ 比较接近但是不能本质上简化DLP的求解

随后定义基点 $G$ 也没什么特殊的

生成128bits的 $key$ 215bits的随机数 $r$

定义Equinox类其包含state变量 215bits的 $a$

靶机先给你

hint_1\equiv y(a\cdot r\cdot G)+key\mod p

state $a$ 可以被如下操作修改

输入 $msg$ 计算

mask = bytes_to_long(SHA256.new(msg).digest()) & ((1 << 215) - 1)

也就是 $msg$ 进行SHA256哈希后取低215位

再

a=a\oplus mask

我们可以无限次添加 $msg$ 调节state 但是只有一次获取hint机会也就是

hint_2\equiv y(a_1\cdot r\cdot G)+key\mod p

其中

a_1=a\oplus mask_1\oplus\cdots\oplus mask_i

注意到我们有3个未知量 $r\;a\;key$ 但是只有两条方程 $hint_1\;hint_2$

一开始考虑利用 $key$ 比较小找线性关系做格来规约但是在ECC中显然非线性还是强

先考虑如何把异或变成线性式子因为

a\oplus 11\cdots11=2^{215}-1-a

这里测试出一个比较关键的性质

2^{215}-1\equiv -15\mod \mathbf{\#E}

也就是说如果我们构造

mask_1\oplus\cdots\oplus mask_i=111\cdots111

那么

hint_2\equiv y(a_1\cdot r\cdot G)+key\equiv y((2^{215}-1-a)\cdot r\cdot G)+key\mod p

hint_2\equiv y((-15-a)\cdot r\cdot G)+key

那么如何构造我们预期的一系列 $mask$ 呢

注意到我们的目标向量 $m$ 可以看成 $\mathbf{GF(2)}$ 上一组列向量 $v_{215\times1}$

我们考虑采集 $i$ 组数据 $m_{215\times1}$ 拼接得到矩阵 $M_{215\times i}$ 问题此时描述为寻找选中向量 $c_{i\times1}$ 使得

M_{215\times i}\times c_{i\times1}=m_{215\times1}

我们可以不断增加 $i$ 重新取样让这个系统满秩来解出 $c_i$

因为我们参与掩码的 $a$ 实际上也是完全唯一的我们如果随机控制 $m$ 的低4位比如说全取 $0000$ 此时的

m\oplus a\equiv (2^{215}-1-a+\text{offset})\equiv(\text{offset}-15-a)\mod \mathbf{\#E}

offset是0~15之间随机取值也就是说我们平均链接16次靶机就会出现一次 $m\oplus a\equiv -a$

此时

hint_2\equiv y(-a\cdot r\cdot G)+key\equiv-y(a\cdot r\cdot G)+key\mod p

直接

key\equiv \frac{hint_1+hint_2}{2}\mod p

exp.py

from pwn import *
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Cipher import AES

p = 26328072917139296674479506920917642091979664886232678979756108269

SEEDS = ['2', '3', '7', '8', '16', '17', '19', '21', '22', '23', '24', '26', '27', '30', '32', '33', '36', '43', '44', '46', '47', '48', '49', '50', '51', '53', '54', '59', '61', '63', '67', '71', '72', '73', '74', '76', '77', '78', '79', '81', '84', '87', '91', '92', '93', '95', '96', '98', '99', '101', '103', '104', '105', '106', '107', '108', '109', '114', '115', '116', '119', '121', '124', '125', '126', '128', '129', '131', '134', '135', '136', '140', '142', '143', '148', '149', '152', '153', '154', '155', '157', '158', '161', '163', '165', '166', '167', '168', '169', '172', '173', '179', '180', '183', '184', '186', '187', '190', '191', '192', '193', '195', '197', '199', '205', '206', '207', '208', '211', '212', '213', '216']

HOST = "155.248.210.243"
PORT = 42125

def try_once():
    r = remote(HOST, PORT)

    r.recvuntil(b"flag = ")
    enc_flag = int(r.recvline().strip())
    r.recvuntil(b"hint_1 = ")
    hint_1 = int(r.recvline().strip())
    for s in SEEDS:
        r.sendlineafter(b"option: ", b"1")
        r.sendlineafter(b"msg? ", s.encode())
    r.sendlineafter(b"option: ", b"2")
    r.recvuntil(b"hint_2 = ")
    hint_2 = int(r.recvline().strip())
    r.close()
    s = (hint_1 + hint_2) % p
    if s % 2 != 0:
        s += p
    key = s // 2

    try:
        cipher = AES.new(long_to_bytes(key), AES.MODE_ECB)
        pt = cipher.decrypt(long_to_bytes(enc_flag))
        if b"ictf{" in pt or b"CTF{" in pt or b"flag{" in pt:
            return pt
    except:
        pass
    return None


for attempt in range(100):
    log.info(f"Attempt {attempt + 1}")
    result = try_once()
    if result:
        log.success(f"Flag: {result}")
        break
else:
    log.failure("Failed after 100 attempts")

# ictf{omg_xor_is_just_like_multiplication_chat}

Elegant

Illiterate#

chal.py

flag = b'ictf{REDACTED}'
def jacobiSymbol(a, n):
    a %= n
    result = 1
    while a != 0:
        while a % 2 == 0:
            a //= 2
            n_mod_8 = n % 8
            if n_mod_8 in (3, 5):
                result = -result
        a, n = n, a
        if a % 4 == 3 and n % 4 == 3:
            result = -result
        a %= n
    return result if n == 1 else 0


def isPrime(p):
    if p == 2:
        return True
    if p < 2:
        return False
    if p % 2 == 0:
        return False
    witnesses = [1273076718476451754317013814127123029, 845257091632129340504606410993318513, 986506745201158482766197094546488559, 707012940092118175868299125612312793, 1213424722665355883998859353747948559, 1096649821936509780592216743717621961, 1203575152124577162570333987040475647, 1034195762268271985553343293758258647, 941579813597084827990555116503495071, 1160627089774708491508668155051404403, 836824746890078856005143966739466953, 799204280537044489268386103838528451, 1172614136539511046357433964488059979, 1305442193052048480095062472502986473, 770725442321657635681777052007000523, 1235844317457938473442373336659073467]
    e = p // 2
    if all(pow(a,e,p) == (jacobiSymbol(a,p) % p) for a in witnesses):
        return True
    else:
        return False
    
    

class ECC:
    def __init__(self, a, b, p):
        self.a = a % p
        self.b = b % p
        self.p = p

    def inv(self, x):
        if x % self.p == 0:
            return None
        return pow(x, self.p - 2, self.p)

    def add(self, P, Q):
        if P is None: return Q
        if Q is None: return P

        x1, y1 = P
        x2, y2 = Q
        
        if x1 == x2 and (y1 + y2) % self.p == 0:
            return None

        if P == Q:
            num = (3 * x1 * x1 + self.a)
            den = (2 * y1)
        else:
            num = (y2 - y1)
            den = (x2 - x1)

        inv_den = self.inv(den)
        if inv_den is None:
            return None
            
        m = (num * inv_den) % self.p
        x3 = (m * m - x1 - x2) % self.p
        y3 = (m * (x1 - x3) - y1) % self.p
        return (x3, y3)

    def mul(self, k, P):
        R = None
        Q = P

        while k > 0:
            if k & 1:
                R = self.add(R, Q)
            Q = self.add(Q, Q)
            k >>= 1

        return R
    

def main():
    global flag  # Add this line to access global flag


    a = int(input('a:'))
    b = int(input('b:'))
    p = int(input('p:'))
    
    if not isPrime(p) or p < 1393796574908163946345982392040522594123776:
        print('invalid modulus')
        exit(1)
        
    if (4 * pow(a,3,p) + 27 * pow(b,2,p)) % p == 0:
        print("no singular curves plz >:(")
        exit(1)

    a = a % p
    b = b % p

    E = int(input('E'))

    if E < 1393796574908163946345982392040522594123776:
        print("order too small")
        exit(1)

    if E > (1<<1024) or p > (1<<1024):
        print("too hard pick smaller numbers")
        exit(1)
    
    if not isPrime(E):
        print("order is too smooth")
        exit(1)
    
    if abs(E - p) < 10:
        print("too anomalous")
        exit(1)
    
    if pow(E - p - 1,2) > (4 * p):
        print("I don't believe you")
        exit(1)

    for k in range(1,1000):
        if pow(p,k,E) == 1:
            print("hey no MOVing around")
            exit(1)
        
    g_x = int(input('g.x:')) % p
    g_y = int(input('g.y:')) % p

    if pow(g_y,2,p) != (pow(g_x,3,p) +  a * g_x + b) % p:
        print("invalid generator")
        exit(1)
        
    curve = ECC(a,b,p)
    generator = (g_x,g_y)

    if curve.mul(E,generator) != None:
        print("order is incorrect")
        exit(1)
    flag = flag[5:-1]
    f1 = int.from_bytes(flag[:18],'big')
    f2 = int.from_bytes(flag[18:],'big')
    P1 = curve.mul(f1,generator)
    P2 = curve.mul(f2,generator)
    print(P1)
    print(P2)
        
    
        
if __name__ == "__main__":
    main()

靶机允许构造一条标准Wiersstrass曲线

\mathbf{E}:y^2\equiv x^3+ax+b\mod p

可以自己给靶机发送”曲线的阶” $\mathbf{\#E}$ 与生成元 $G$ 靶机定义了一系列检测尝试让用户发送的曲线素数不具备奇异性等常见漏洞随后构造

f1 = int.from_bytes(flag[:18],'big')
f2 = int.from_bytes(flag[18:],'big')
P1 = curve.mul(f1,generator)
P2 = curve.mul(f2,generator)

所以目标是构造通过测试的伪素数 $p$ 对应生成曲线 $\mathbf{E}$ 解ECDLP

检测方式#

isPrime函数

def isPrime(p):
    e = p // 2
    if all(pow(a, e, p) == (jacobiSymbol(a, p) % p) for a in witnesses):
        return True

对特定的几个witness中的数 $a$ 进行Euler素性判断等式

a^{\frac{(p-1)}{2}} \equiv \left(\frac{a}{p}\right) \pmod{p}

梳理服务端的检测主要如下

校验	含义
`isPrime(p)`	p 需通过伪素数测试
$p ≥ 2^{140}$	下界约 1.39×10⁴²
`isPrime(E)`	E 需通过伪素数测试
$\#E ≥ 2^{140}$	阶的下界
$	#E - p
$(E-p-1)² ≤ 4p$	Hasse 界
$p^k ≢ 1 \mod E\;\;;\; k∈[1,999]$	防 MOV 攻击
$\mathbf{E}·\mathbf{G} = \mathbf{O}$	验证阶正确

这里主要的检测手法都是判断曲线的阶 $\mathbf{\#E}$ 不能被轻松的推到易于求解的DLP

绕过构造#

核心问题还是解ECDLP 构造素数 $p$ 通过isPrime只是第一步需要让构造的曲线 $E$ 的阶数易于做DLP 故而思路链条大概为

\text{构造}\#E=\prod q_i\rightarrow \text{对应构造出素数}p\rightarrow \text{构造复乘曲线满足}\#E\text{恰为曲线的阶}\rightarrow\text{做ECDLP}

伪素数构造#

要通过这里16组witness的检测同时还要便于做DLP 考虑类似

E = (6L+1)(12L+1)(18L+1), \quad L \equiv 0 \pmod{12}

其中 $p_1 = 6L+1,\ p_2 = 12L+1,\ p_3 = 18L+1$ 均为素数

此时有对每个素因子 $p_i$ ，有 $(p_i - 1) \mid (E - 1)$

所以对任意 $\gcd(a, E) = 1$ $a^{E-1} \equiv 1 \pmod{E}$

落到靶机的检测需要满足

a^{\frac{(E-1)}{2}} \equiv \left(\frac{a}{E}\right) \pmod{E}

推导一下也就是

\prod_{i=1}^{3} \left(\frac{a}{p_i}\right) = 1 \quad \text{对所有 16 个 witness } a

搜索方式是令

p_1=L+1,\quad p_2=2L+1,\quad p_3=3L+1,\quad E=p_1p_2p_3

从 $(\frac{2^{140}}{6})^{\frac{1}{3}}$ 开始搜索 $L$ 自增12 并且对齐每轮做一些检验

搜索约 272 秒后找到第 4 个候选：

E = 1393987673345391394931205800131659111954649 (141 bits)
p1 = 61475569549627,  p2 = 122951139099253,  p3 = 184426708648879

plaintext

三个因子均约 47 bits 141bits略小于18*8=144 爆破即可

曲线/模数构造#

还是利用老朋友复乘CM曲线阶的可计算性注意要让曲线的类数为1 这样曲线不变量是已知且确定的直接构造曲线就行了这里找到的曲线是

y^2\equiv x^3+3\mod p

交互/解ECDLP#

得到阶数模数的构造后可以直接发送过去得到两个点的值因为阶能拆成三个47bits的小因子可以在 $O(\sqrt{q})$ 的复杂度下做BSGS解DLP 实测大概14分钟能够跑完

后续求出来第一段的flag bit还不够稍微爆破一下即可

solve.sage

from sage.all import *
import sys, re, time
from pwn import *

def jacobiSymbol(a, n):
    a = int(a) % int(n); n = int(n); result = 1
    while a != 0:
        while a % 2 == 0:
            a //= 2
            if n % 8 in (3, 5): result = -result
        a, n = n, a
        if a % 4 == 3 and n % 4 == 3: result = -result
        a %= n
    return result if n == 1 else 0

WITNESSES = [
    1273076718476451754317013814127123029, 845257091632129340504606410993318513,
    986506745201158482766197094546488559, 707012940092118175868299125612312793,
    1213424722665355883998859353747948559, 1096649821936509780592216743717621961,
    1203575152124577162570333987040475647, 1034195762268271985553343293758258647,
    941579813597084827990555116503495071, 1160627089774708491508668155051404403,
    836824746890078856005143966739466953, 799204280537044489268386103838528451,
    1172614136539511046357433964488059979, 1305442193052048480095062472502986473,
    770725442321657635681777052007000523, 1235844317457938473442373336659073467
]

def check_isPrime(p):
    p = int(p)
    if p < 2 or p % 2 == 0: return False
    e = p // 2
    for a in WITNESSES:
        if pow(a, e, p) != (jacobiSymbol(a, p) % p): return False
    return True

MIN_BOUND = 1393796574908163946345982392040522594123776

# CM class number 1 discriminants and their j-invariants
CM_CLASS1 = {
    -3: 0, -4: 1728, -7: -3375, -8: 8000, -11: -32768,
    -19: -884736, -43: -884736000, -67: -147197952000,
    -163: -262537412640768000
}

def solve_norm_eq(D0_neg, primes_list):
    """Solve x^2 + |D0|*y^2 = 4*prod(primes) by solving per-prime
    and combining via Brahmagupta-Fibonacci identity.
    Returns list of (x, y) with x^2 + |D0|*y^2 = 4*N."""
    D = abs(D0_neg)
    Q = BinaryQF([1, 0, D])

    # Solve for each prime
    per_prime = []
    for p in primes_list:
        sol = Q.solve_integer(4 * int(p))
        if sol is None:
            return []
        per_prime.append((abs(int(sol[0])), abs(int(sol[1]))))

    # Combine: (a+b*sqrt(-D))*(c+d*sqrt(-D)) = (ac-D*bd) + (ad+bc)*sqrt(-D)
    # This gives (ac-Dbd)^2 + D*(ad+bc)^2 = (a^2+Db^2)*(c^2+Dd^2) = 16*p1*p2
    # We need to halve to get 4*p1*p2: need ac-Dbd and ad+bc both even.
    # Try all sign combos of b,d to find even results.

    def combine_two(s1, s2):
        a, b = s1
        c, d = s2
        results = set()
        for sb in [1, -1]:
            for sd in [1, -1]:
                x = a*c - D*(b*sb)*(d*sd)
                y = a*(d*sd) + c*(b*sb)
                if x % 2 == 0 and y % 2 == 0:
                    results.add((abs(x)//2, abs(y)//2))
        return list(results)

    combined = [per_prime[0]]
    for i in range(1, len(per_prime)):
        new_combined = []
        for s1 in combined:
            new_combined.extend(combine_two(s1, per_prime[i]))
        # Deduplicate
        combined = list(set(new_combined))

    # Verify and return
    N = 1
    for p in primes_list:
        N *= int(p)
    valid = []
    for x, y in combined:
        if x*x + D*y*y == 4*N:
            valid.append((x, y))
    return valid

# ============================================================
# Main search: iterate Chernick L values
# ============================================================
print("[*] Searching for E with small CM discriminant prime p...")
t0 = time.time()

L_start = int((MIN_BOUND // 6) ** (1/3)) + 1
L_start = L_start + (6 - L_start % 12) % 12

found = None
E_count = 0

for L in range(L_start, L_start + 50000000000, 12):
    p1 = L + 1
    p2 = 2*L + 1
    p3 = 3*L + 1

    if p1 % 3 == 0 or p2 % 3 == 0 or p3 % 3 == 0: continue
    if p1 % 5 == 0 or p2 % 5 == 0 or p3 % 5 == 0: continue
    if p1 % 7 == 0 or p2 % 7 == 0 or p3 % 7 == 0: continue
    if p1 % 11 == 0 or p2 % 11 == 0 or p3 % 11 == 0: continue
    if p1 % 13 == 0 or p2 % 13 == 0 or p3 % 13 == 0: continue

    if not is_pseudoprime(p1): continue
    if not is_pseudoprime(p2): continue
    if not is_pseudoprime(p3): continue

    n = p1 * p2 * p3
    if n < MIN_BOUND: continue

    ok = True
    for w in WITNESSES:
        if kronecker_symbol(w, p1) * kronecker_symbol(w, p2) * kronecker_symbol(w, p3) != 1:
            ok = False; break
    if not ok: continue

    if not check_isPrime(n): continue

    E_count += 1
    E_val = n
    E_factors = [p1, p2, p3]

    if E_count % 1 == 0:
        print(f"    E #{E_count}: L={L}, E={E_val} ({time.time()-t0:.1f}s)", flush=True)

    # Try each CM discriminant
    for D0, j_inv in CM_CLASS1.items():
        sols = solve_norm_eq(D0, E_factors)
        if not sols:
            continue
        for x, y in sols:
            for t_candidate in [x + 2, -x + 2]:
                cp = int(E_val) - 1 + t_candidate
                if cp < int(MIN_BOUND): continue
                if abs(int(E_val) - cp) < 10: continue
                if t_candidate * t_candidate > 4 * cp: continue
                if not is_prime(cp): continue
                # MOV check
                mov_ok = True
                for k in range(1, 1000):
                    if pow(int(cp), k, int(E_val)) == 1:
                        mov_ok = False; break
                if not mov_ok: continue
                found = {
                    'E': E_val, 'factors': E_factors, 'L': L,
                    'p': cp, 't': t_candidate, 'D0': D0, 'j': j_inv
                }
                break
            if found: break
        if found: break
    if found: break

if found is None:
    print("[-] Failed!"); sys.exit(1)

E = found['E']
E_prime_factors = found['factors']
p = found['p']
trace_val = found['t']
D0_used = found['D0']
j_used = found['j']

print(f"\n[+] SUCCESS after {E_count} E candidates ({time.time()-t0:.1f}s)")
print(f"    E = {E} ({Integer(E).nbits()} bits)")
print(f"    p1={E_prime_factors[0]}, p2={E_prime_factors[1]}, p3={E_prime_factors[2]}")
print(f"    p = {p}, trace = {trace_val}, D0 = {D0_used}, j = {j_used}")

all_small_factors = set()
for pp in E_prime_factors:
    for f, e in factor(pp - 1):
        all_small_factors.add((int(f), e))
print(f"    Max prime in p_i-1: {max(f for f,e in all_small_factors)}")

# ============================================================
# Construct curve via CM (instant for class number 1)
# ============================================================
print("\n[*] Constructing curve via CM")
t3 = time.time()

Fp = GF(p)
curve = None

j_fp = Fp(j_used)
if j_used == 0:
    # j=0: y^2=x^3+b, 6 twists parameterized by b in Fp*/(Fp*)^6
    g = Fp.multiplicative_generator()
    cands = [EllipticCurve(Fp, [0, g^i]) for i in range(6)]
elif j_used == 1728:
    # j=1728: y^2=x^3+ax, 4 twists parameterized by a in Fp*/(Fp*)^4
    g = Fp.multiplicative_generator()
    cands = [EllipticCurve(Fp, [g^i, 0]) for i in range(4)]
else:
    k = j_fp / (Fp(1728) - j_fp)
    a4, a6 = Fp(3)*k, Fp(2)*k
    C = EllipticCurve(Fp, [a4, a6])
    cands = [C, C.quadratic_twist()]

for C in cands:
    try:
        if C.order() == E:
            curve = C
            print(f"[+] CM succeeded! ({time.time()-t3:.1f}s)")
            break
    except:
        continue

if curve is None:
    print("[-] CM failed to produce correct order!"); sys.exit(1)

a_int = int(curve.a4())
b_int = int(curve.a6())
print(f"    a = {a_int}, b = {b_int}")

# ============================================================
# Generator
# ============================================================
print("\n[*] Finding generator")
G = None
for _ in range(500):
    P = curve.random_point()
    if P != curve(0) and int(E) * P == curve(0):
        G = P; break
if G is None:
    print("[-] No generator!"); sys.exit(1)

gx, gy = int(G[0]), int(G[1])
print(f"[+] G = ({gx}, {gy})")

# ============================================================
# Connect to remote
# ============================================================
print("\n[*] Connecting to remote...")
t5 = time.time()

HOST = "155.248.210.243"
PORT = 42123

io = remote(HOST, PORT)

io.sendlineafter(b'a:', str(a_int).encode())
io.sendlineafter(b'b:', str(b_int).encode())
io.sendlineafter(b'p:', str(int(p)).encode())
io.sendlineafter(b'E', str(int(E)).encode())
io.sendlineafter(b'g.x:', str(gx).encode())
io.sendlineafter(b'g.y:', str(gy).encode())

resp = io.recvall(timeout=60).decode().strip()
io.close()
print(f"    Response: {resp}")
print(f"    ({time.time()-t5:.1f}s)")

tuples = re.findall(r'\((\d+),\s*(\d+)\)', resp)
if len(tuples) >= 2:
    P1x, P1y = int(tuples[0][0]), int(tuples[0][1])
    P2x, P2y = int(tuples[1][0]), int(tuples[1][1])
else:
    print(f"[-] Failed to parse points! Response: {repr(resp)}")
    sys.exit(1)

print(f"[+] P1 = ({P1x}, {P1y})")
print(f"[+] P2 = ({P2x}, {P2y})")

# ============================================================
# Pohlig-Hellman ECDLP
# ============================================================
print("\n[*] Pohlig-Hellman ECDLP")
t6 = time.time()

P1 = curve(P1x, P1y)
P2 = curve(P2x, P2y)

def bsgs_ecdlp(target, gen, q, curve_zero):
    """Baby-step Giant-step for ECDLP in subgroup of order q.
    Stores (x,y) tuples as keys for exact matching."""
    q = int(q)
    m = int(q**0.5) + 1

    # Baby steps: build table {point_key: j} for j*gen, j in [0, m)
    print(f"        Baby steps (m={m})...", end="", flush=True)
    t_bs = time.time()
    baby = {}
    P = curve_zero
    for j in range(m):
        if P == curve_zero:
            baby['inf'] = j
        else:
            baby[(int(P[0]), int(P[1]))] = j
        P = P + gen
    print(f" done ({time.time()-t_bs:.1f}s)", flush=True)

    # Giant step: -m * gen
    print(f"        Giant steps...", end="", flush=True)
    t_gs = time.time()
    giant_step = Integer(-m) * gen

    P = target
    for i in range(m):
        if P == curve_zero:
            key = 'inf'
        else:
            key = (int(P[0]), int(P[1]))
        if key in baby:
            print(f" found at i={i} ({time.time()-t_gs:.1f}s)", flush=True)
            return (baby[key] + i * m) % q
        P = P + giant_step

    raise ValueError(f"BSGS failed for q={q}")

def pohlig_hellman(target, gen, order, factors):
    residues, moduli = [], []
    curve_zero = curve(0)
    for q in factors:
        cofactor = order // q
        G_sub = Integer(cofactor) * gen
        T_sub = Integer(cofactor) * target
        if G_sub == curve_zero:
            residues.append(Integer(0)); moduli.append(Integer(q)); continue
        if T_sub == curve_zero:
            residues.append(Integer(0)); moduli.append(Integer(q)); continue
        t_q = time.time()
        k_q = bsgs_ecdlp(T_sub, G_sub, q, curve_zero)
        print(f"      q={q}: k={k_q} ({time.time()-t_q:.1f}s)")
        residues.append(Integer(k_q)); moduli.append(Integer(q))
    return CRT_list(residues, moduli)

print("    Solving f1...")
f1 = pohlig_hellman(P1, G, Integer(E), [Integer(x) for x in E_prime_factors])
print(f"    f1 = {f1}")
print("    Solving f2...")
f2 = pohlig_hellman(P2, G, Integer(E), [Integer(x) for x in E_prime_factors])
print(f"    f2 = {f2}")

assert Integer(f1) * G == P1, "f1 check failed!"
assert Integer(f2) * G == P2, "f2 check failed!"
print(f"[+] Verified! ({time.time()-t6:.1f}s)")

# ============================================================
# Flag
# ============================================================
# Since E (~2^141) < 2^144 (18 bytes), the real flag values may be f + k*E
# for small k. Brute force k to find printable ASCII.
print("\n[*] Recovering flag (brute-forcing k offsets)...")
max_18 = (1 << 144) - 1
best_flag = None

for k1 in range(int(max_18 // int(E)) + 1):
    real_f1 = int(f1) + k1 * int(E)
    if real_f1 > max_18:
        break
    b1 = real_f1.to_bytes(18, 'big')
    if not all(32 <= c < 127 or c == 0 for c in b1):
        continue
    for k2 in range(int(max_18 // int(E)) + 1):
        real_f2 = int(f2) + k2 * int(E)
        if real_f2 > max_18:
            break
        b2 = real_f2.to_bytes(18, 'big')
        content = b1 + b2
        # Strip null bytes and check if printable ASCII
        text = content.replace(b'\x00', b'')
        if all(32 <= c < 127 for c in text) and len(text) >= 20:
            flag = b'ictf{' + text + b'}'
            print(f"    k1={k1}, k2={k2}: {flag.decode()}")
            if best_flag is None:
                best_flag = flag

if best_flag:
    print(f"\n{'='*70}")
    print(f"FLAG: {best_flag.decode()}")
    print(f"{'='*70}")
    with open('flag.txt', 'wb') as ff:
        ff.write(best_flag)
else:
    print("[-] Could not find printable flag!")
    # Fallback: dump hex
    flag_part1 = int(f1).to_bytes(18, 'big')
    flag_part2 = int(f2).to_bytes(18, 'big')
    flag = b'ictf{' + flag_part1 + flag_part2 + b'}'
    print(f"FLAG (hex): {flag.hex()}")
    with open('flag.txt', 'wb') as ff:
        ff.write(flag)

print(f"[+] Done! Total time: {time.time()-t0:.1f}s")

# ictf{ai_told_me_16_rounds_was_solid}