Overview
An Elliptic Curve Cryptography challenge where we are given the curve parameters, a base generator G, a public key Q, and an XOR encrypted flag.
Reconnaissance
The curve parameters are:
p = 233970423115425145524320034830162017933
a = -95051
b = 11279326This curve is a weak curve whose twist group order is smooth (divisible by small prime factors), rendering it vulnerable to invalid-curve/twist attacks.
Exploitation Strategy
We solve the Elliptic Curve Discrete Logarithm Problem (ECDLP) to find k such that Q = k * G.
Since the twist order is smooth:
n_twist = 4 * 11 * 107 * 197 * 1621 * 105143 * 405373 * 2323367 * 1571528514013We apply the Pohlig-Hellman algorithm to calculate the secret key modulo each small factor, then combine the values using the Chinese Remainder Theorem (CRT) to determine k.
Finally, we hash k with SHA256 and decrypt the ciphertext to extract the flag.
Solution Code
# SageMath implementation of twist group Pohlig-Hellman:
# ...
# k = CRT(moduli_results)
# key_hash = hashlib.sha256(str(k).encode()).digest()
# Decrypted Flag: CrackOn{th3_kn0t_1s_unbr0k3n_wh4t_w4s_w1ll_4lw4ys_b3}Flag
CrackOn{th3_kn0t_1s_unbr0k3n_wh4t_w4s_w1ll_4lw4ys_b3}