Circle - Write-up#

Tổng Quan#

Challenge mô phỏng các phép toán elliptic-curve nhưng thực tế thực hiện phép toán trên unit circle trong F_p.

Quan Sát Chính#

Custom "point addition" chính là phép nhân phức:

• Ánh xạ điểm (x, y) → z = y + x·i (mod p) với i² ≡ -1 (mod p)
• Generator G và public point P đều có norm 1: x² + y² ≡ 1
• Tạo thành multiplicative subgroup của F_p* với order chia hết p-1
• Khôi phục trở thành DLP chuẩn trong F_p!*

Chiến Lược Khai Thác#

1. Chuyển Đổi Points sang Số Phức#

pythonCopy
i = sqrt(-1) mod p  # Tonelli-Shanks
g = Gy + Gx·i (mod p)
h = Py + Px·i (mod p)

2. Phân Tích Thừa Số p-1 (Smooth!)#

p - 1 = 2² × 3715183 × 3759101 × 17817311 × 651593951 × 557030717 
        × 188500020953 × 100307721973 × 51289524067 × 876618444731

3. Chạy Pohlig-Hellman#

• Với mỗi thừa số nguyên tố q: giải DLP rút gọn với BSGS
• Kết hợp kết quả qua CRT để khôi phục secret s

4. Tạo AES Key & Giải Mã#

pythonCopy
k = SHA256(s)[:16]
flag = AES-CBC-decrypt(ct, k, iv)

Recovery Script để giải flag#

pythonCopy
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import hashlib

p = 307119639745751469235752346635781766287891925576026383455555022557456022240440834093
Gx = 269706932193805755534663280853021102698237187960981530911954571811593219484562877686
Gy = 64681749570942311062995683097786979736444359061659263379460834230175114182600310869
Px = 66458087392047205569134518238677614962987250315628901489579974197182257590937156372
Py = 60031618721128621274849877211225119325796011838618857532417555895902612101315597171
iv = bytes.fromhex('8447d89c8f2ddb200d0c3307c2dea7fa')
ct = bytes.fromhex('308a8c3e3c705e9d2ba5cb25c28c3738d3e177c8d1327e534ce11cad77dc9bd3feba a5b0341b12449f439bcdf3567c9b'.replace(' ', ''))

def tonelli_shanks(n, p):
    assert pow(n, (p - 1) // 2, p) == 1
    q, s = p - 1, 0
    while q % 2 == 0:
        q //= 2
        s += 1
    if s == 1:
        return pow(n, (p + 1) // 4, p)
    z = 2
    while pow(z, (p - 1) // 2, p) != p - 1:
        z += 1
    c = pow(z, q, p)
    r = pow(n, (q + 1) // 2, p)
    t = pow(n, q, p)
    m = s
    while t != 1:
        i = 1
        temp = pow(t, 2, p)
        while temp != 1:
            temp = pow(temp, 2, p)
            i += 1
        b = pow(c, 1 << (m - i - 1), p)
        r = (r * b) % p
        t = (t * b * b) % p
        c = (b * b) % p
        m = i
    return r

i = tonelli_shanks(p - 1, p)
g = (Gy + Gx * i) % p
h = (Py + Px * i) % p
factorization = {
    2: 2,
    3715183: 1,
    3759101: 1,
    17817311: 1,
    651593951: 1,
    557030717: 1,
    188500020953: 1,
    100307721973: 1,
    51289524067: 1,
    876618444731: 1,
}

def bsgs(g, h, p, order):
    m = int(order ** 0.5) + 1
    table, e = {}, 1
    for j in range(m):
        table.setdefault(e, j)
        e = (e * g) % p
    factor = pow(pow(g, p - 2, p), m, p)
    gamma = h
    for i in range(m + 1):
        if gamma in table:
            x = i * m + table[gamma]
            if x < order:
                return x
        gamma = (gamma * factor) % p
    raise ValueError('log not found')

def crt(congruences):
    x, M = 0, 1
    for _, mod in congruences:
        M *= mod
    for r, mod in congruences:
        m = M // mod
        inv = pow(m, -1, mod)
        x = (x + r * m * inv) % M
    return x

congruences = []
for prime, exp in factorization.items():
    mod = prime ** exp
    m = (p - 1) // mod
    g_i = pow(g, m, p)
    h_i = pow(h, m, p)
    if prime == 2 and exp > 1:
        cur, val = 1, None
        for k in range(mod):
            if cur == h_i:
                val = k
                break
            cur = (cur * g_i) % p
        congruences.append((val, mod))
    else:
        congruences.append((bsgs(g_i, h_i, p, mod), mod))

s = crt(congruences)
k = hashlib.sha256(long_to_bytes(s)).digest()[:16]
flag = unpad(AES.new(k, AES.MODE_CBC, iv).decrypt(ct), 16)
print(flag.decode())

Flag#

BPCTF{Group_isomorphism_and_smooth_order}

Bài Học Rút Ra#

• Triển khai crypto tùy chỉnh có thể ẩn các vấn đề chuẩn
• Group isomorphism giảm vấn đề "mới" về vấn đề đã biết
• Order smooth cho phép tấn công Pohlig-Hellman
• Luôn phân tích cấu trúc toán học cơ bản