Cryptography
Hard
250 points
Circle
Recuite 2025 - HCMUS
6 tháng 10, 2025
Elliptic Curve
Discrete Log
Pohlig-Hellman
Cryptography
Circle - Write-up
Overview
The challenge simulates elliptic-curve operations but actually performs operations on the unit circle in F_p.
Key Observations
Custom "point addition" is actually complex multiplication:
- Map point (x, y) → z = y + x·i (mod p) with i² ≡ -1 (mod p)
- Generator G and public point P both have norm 1: x² + y² ≡ 1
- Forms a multiplicative subgroup of F_p* with order dividing p-1
- Recovery becomes standard DLP in F_p!*
Exploitation Strategy
1. Convert Points to Complex Numbers
i = sqrt(-1) mod p # Tonelli-Shanks
g = Gy + Gx·i (mod p)
h = Py + Px·i (mod p)
2. Factorize p-1 (Smooth!)
p - 1 = 2² × 3715183 × 3759101 × 17817311 × 651593951 × 557030717
× 188500020953 × 100307721973 × 51289524067 × 876618444731
3. Run Pohlig-Hellman
- For each prime factor q: solve reduced DLP with BSGS
- Combine results via CRT to recover secret s
4. Derive AES Key & Decrypt
k = SHA256(s)[:16]
flag = AES-CBC-decrypt(ct, k, iv)
Recovery Script to solve flag
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}
Key Takeaways
- Custom crypto implementation can hide standard problems
- Group isomorphism reduces "new" problem to known problem
- Smooth order allows Pohlig-Hellman attack
- Always analyze underlying mathematical structure
250
Points
Hard
Difficulty
Cryptography
Category