Misay's blog

imaginaryCTF-Ⅰ

发表于 更新于 分类于
本文字数： 33k
imaginaryCTF 2026 Jan.

冲浪发现的比赛 比赛地址 https://imaginaryctf.org/

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

pwq

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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相关 给出 已知 可以直接解出 又已知 可以分别解出 与 此时可做

未知量 构造

打二元Copper即可

exp.sage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
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

1
2
3
4
5
6
7
8
9
10
11
12
13
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模数,我们可以自己构造2026bits公钥指数 得到密文

本题关键切入有两个

flag 只有160bits

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

考虑取比较多组数据 得到 对于一系列较小的 我们提前假设好素数 当取足够多时 能够得到 这个概率大约是 如果我们传入的对应可逆 我们就可以解出 积累足够多数据 做CRT即可恢复

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

data-collect.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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曲线 编码一个曲线 曲线不奇异 看似很正常 阶数和比较接近 但是不能本质上简化DLP的求解

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

生成128bits的 215bits的随机数

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

靶机先给你 state 可以被如下操作修改

输入 计算

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

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

再 我们可以无限次添加调节state 但是只有一次获取hint机会 也就是 其中 注意到我们有3个未知量 但是只有两条方程

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

先考虑如何把异或变成线性式子 因为 这里测试出一个比较关键的性质 也就是说 如果我们构造 那么

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

注意到我们的目标向量可以看成上一组列向量

我们考虑采集组数据 拼接得到矩阵 问题此时描述为寻找选中向量 使得 我们可以不断增加 重新取样 让这个系统满秩 来解出

因为我们参与掩码的实际上也是完全唯一的 我们如果随机控制的低4位 比如说全取 此时的 offset是0~15之间随机取值 也就是说我们平均链接16次靶机 就会出现一次

此时 直接 exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
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曲线 可以自己给靶机发送”曲线的阶” 与生成元 靶机定义了一系列检测 尝试让用户发送的曲线素数不具备奇异性等常见漏洞 随后构造

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

所以目标是构造通过测试的伪素数 对应生成曲线 解ECDLP

检测方式

isPrime函数

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

对特定的几个witness中的数 进行Euler素性判断等式 梳理服务端的检测主要如下

校验 含义
isPrime(p) p 需通过伪素数测试
下界约 1.39×10⁴²
isPrime(E) E 需通过伪素数测试
阶的下界
防 anomalous 攻击
² Hasse 界
防 MOV 攻击
验证阶正确

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

绕过构造

核心问题还是解ECDLP 构造素数通过isPrime只是第一步 需要让构造的曲线的阶数易于做DLP 故而思路链条大概为 构造对应构造出素数构造复乘曲线满足恰为曲线的阶做

伪素数构造

要通过这里16组witness的检测 同时还要便于做DLP 考虑类似 其中 均为素数

此时有对每个素因子 ，有

所以对任意

落到靶机的检测 需要满足 推导一下也就是 对所有个 搜索方式是令 从开始搜索 自增12 并且对齐 每轮做一些检验

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

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

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

曲线/模数构造

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

交互/解ECDLP

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

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

solve.sage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
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}