SECCON Beginners 2025 - Elliptic4b
secp256k1 の楕円曲線上で、与えられた y に対して x と a を求める。
sagemathのnth_root()で立方根を求めることができる。GF(p)を使ってpの有限体上で計算する。
楕円曲線上で x 軸対象の点は a = -1 だが、a > 0 に限定されている。mod n (位数) なので -1 ≡ n - 1 (mod n) である。fastecdsa.curve の secp256k1 では secp256k1.q が位数である。
code:python
from fastecdsa.curve import secp256k1
from sage.all import GF
p = secp256k1.p
Fp = GF(p)
y = 80535934131918414950009148618477744002878940735835809739032784996619249484510
# Solve x: x^3 = y^2 - 7
rhs = Fp(y)**2 - 7
x_cands = rhs.nth_root(3, all=True)
if not x_cands:
raise Exception("NG")
else:
print("x candidates:", cand_x)
for x in cand_x:
if secp256k1.is_point_on_curve((x, y)):
print(f"x = {x}")
print(f"a = {secp256k1.q - 1}") # n (order) - 1
exit()