https://gitlab.com/n0tsobad/ctf-writeups/tree/master/2019-02-01-nullcon/Singular
https://grosquildu.github.io/writeups/2019/01/03/nullcon-singular/
https://crypto.stackexchange.com/questions/61302/how-to-solve-this-ecdlp
Alice and Bob calculated a shared key on the elliptic curve
y2 = x3 + 330762886318172394930696774593722907073441522749x2 + 6688528763308432271990130594743714957884433976x + 759214505060964991648440027744756938681220132782
p = 785482254973602570424508065997142892171538672071
G = (1, 68596750097555148647236998220450053605331891340)
(Alice's public key) P = d1 * G = (453762742842106273626661098428675073042272925939, 680431771406393872682158079307720147623468587944)
(Bob's poblic key) Q = d2 * G = (353016783569351064519522488538358652176885848450, 287096710721721383077746502546881354857243084036)
They have calculated K = d1 * d2 * G. They have taken K's x coordinate in decimal and took sha256 of it and used it for AES ECB to encrypt the flag.
Here is the encrypted flag: 480fd106c9a637d22fddd814965742236eb314c1b8fb68e70a7c7445ff04476082f8b9026c49d27110ba41b95e9f51dc
EllipticCurveの問題。もっと言うと楕円曲線ディフィー・ヘルマン鍵共有ECDHの問題っぽい
愚直にやるとPとQからそれぞれd1, d2を求めることができればKが求まるので暗号鍵も求められる。Gが生成する巡回群の位数が小さければ容易らしいので確かめてみる。
が、この時点で怒られた
from sage.all import * p = 785482254973602570424508065997142892171538672071 E = EllipticCurve(GF(p), [0, 330762886318172394930696774593722907073441522749, 0, 6688528763308432271990130594743714957884433976, 759214505060964991648440027744756938681220132782])
エラーによるとこの曲線は特異点(singular point)を持つらしい。つまりこういう曲線になってる。
こういう singular curve では離散対数は簡単に求められてしまう。singular elliptic curveにはnode型とcusp型の二種類があってそれぞれ対応する群が違うが、どちらの場合も曲線上の演算で構成した群が別の群と同型になってそちらでDLPが簡単に計算できるらしい。
曲線が本当に楕円曲線で無いのかを調べるために判別式Δを用いる。Δ=0なら特異点を持つので楕円曲線ではない。Δの求め方は次の通り
from sage.all import *
def discriminant(a1, a2, a3, a4, a6, p):
b2 = pow(a1,2) + 4*a2
b4 = 2*a4 + a1*a3
b6 = a3*a3 + 4 * a6
b8 = a1*a1*a6 + 4*a2*a6 - a1*a3*a4 + a2*pow(a3, 2) - pow(a4, 2)
return (-pow(b2, 2)*b8 - 8*pow(b4, 3) - 27*pow(b6, 2) + 9*b2*b4*b6) % p
p = 785482254973602570424508065997142892171538672071
a1 = 0
a2 = 330762886318172394930696774593722907073441522749
a3 = 0
a4 = 6688528763308432271990130594743714957884433976
a6 = 759214505060964991648440027744756938681220132782
print(discriminant(a1, a2, a3, a4, a6, p))
確かに0が出力された。続いて、node型かcusp型かを調べる。これにはc4という値を計算して、c4 = 0 ならcuspでc4 != 0ならnodeになる。
def c4(a1, a2, a3, a4, a6, p):
b2 = pow(a1,2) + 4*a2
b4 = 2*a4 + a1*a3
return (pow(b2, 2) - 24*b4) % p
これも0が出力されたのでcusp型ということになる。cusp型の場合は特異点を(0, 0)とするのがわかりやすいので、曲線を平行移動する。ここからはスクリプティングではうまく動かないので対話シェルを使う。
sage: P.<x,y> = GF(p)[] sage: f = x**3 + a2*x**2 + a4*x + a6 sage: C = Curve(f - y**2) sage: C.singular_points() [(413400541209677581972773119133520959089878607131, 0)]
このように出てきたのでfをx方向に +413400541209677581972773119133520959089878607131する。
f2 = f.subs(x = x+413400541209677581972773119133520959089878607131)
これの関数で描かれる曲線では特異点が(0, 0)になる。曲線を平行移動したので問題文に登場する値も平行移動させる。値の平行移動と式の平行移動は符号が逆なので注意
ssage: G = (GF(p)(1 - 413400541209677581972773119133520959089878607131), GF(p)(68596750097555148647236998220450053605331891340)) sage: P = (GF(p)(453762742842106273626661098428675073042272925939 - 413400541209677581972773119133520959089878607131), GF(p)(680431771406393872682158079307720147623468587944)) sage: Q = (GF(p)(353016783569351064519522488538358652176885848450 - 413400541209677581972773119133520959089878607131), GF(p)(287096710 721721383077746502546881354857243084036))
さて、この曲線上で構成される群と同型な群Fp+では 点(x, y) は x/y に相当し無限遠点は0になる。
sage: G_p = G[0] / G[1] sage: P_p = P[0] / P[1] sage: Q_p = Q[0] / Q[1]
この世界では除算が簡単なので例えば P = d1 * Gなるd1もすぐに見つかる
sage: P_p / G_p 733677047520440525642834723493438680490143125031 sage: Q_p / G_p 763634997366397729521910551455953865027020672657
さて、求めたいのは K = d1 * d2 * G の x 座標だったのでそれを求める。同型写像から戻ってくるには x = 1/(t2), y = 1/(t3)という変換になるらしい
G2 = (GF(p)(1 / (763634997366397729521910551455953865027020672657 * 733677047520440525642834723493438680490143125031 * G_p)^2), GF(p)(1 / (763634997366397729521910551455953865027020672657 * 733677047520440525642834723493438680490143125031 * G_p)^3))
これは平行移動した曲線上の点なのでもとに戻してやる
(GF(p)(G2[0] + 413400541209677581972773119133520959089878607131), GF(p)(G2[1])) (165140565353247266256196454126511228757085857653, 231669028154545692129434024805430410636820018050)
x 座標は 165140565353247266256196454126511228757085857653
from Crypto.Cipher import AES from hashlib import sha256 from binascii import unhexlify key = sha256(b'165140565353247266256196454126511228757085857653').digest() c = unhexlify("480fd106c9a637d22fddd814965742236eb314c1b8fb68e70a7c7445ff04476082f8b9026c49d27110ba41b95e9f51dc") print(AES.new(key, AES.MODE_ECB).decrypt(c))
hackim19{w0ah_math_i5_quite_fun_a57f8e21}
綺麗に書き直した
from sage.all import *
from Crypto.Cipher import AES
from hashlib import sha256
def c4(a1, a2, a3, a4, a6, p):
b2 = pow(a1,2) + 4*a2
b4 = 2*a4 + a1*a3
return (pow(b2, 2) - 24*b4) % p
PRIME = 785482254973602570424508065997142892171538672071
Field = GF(PRIME)
_, (x, y) = PolynomialRing(Field, 2, names=["x", "y"]).objgens()
A2 = 330762886318172394930696774593722907073441522749
A1 = 6688528763308432271990130594743714957884433976
A0 = 759214505060964991648440027744756938681220132782
f = x**3 + x**2 * A2 + x * A1 + A0 - y**2
C = Curve(f)
Dx, Dy = C.singular_points()[0]
print("[+] singular poinrt: ({}, {})".format(Dx, Dy))
if c4(0, A2, 0, A1, A0, PRIME) == 0:
print("[+] curve is cusp")
else:
print("[+] curve is node")
f2 = f.subs(x=x - Dx, y = y - Dx)
G = (1, 68596750097555148647236998220450053605331891340)
P = (453762742842106273626661098428675073042272925939, 680431771406393872682158079307720147623468587944)
Q = (353016783569351064519522488538358652176885848450, 287096710721721383077746502546881354857243084036)
# map from elliptic curve to finite field
Fg = Field(G[0] - Dx) / Field(G[1] - Dy)
Fp = Field(P[0] - Dx) / Field(P[1] - Dy)
Fq = Field(Q[0] - Dx) / Field(Q[1] - Dy)
# solve discrete log
d1 = Fp / Fg
d2 = Fq / Fg
print("d1: {}".format(d1))
print("d2: {}".format(d2))
# find K
Fk = d1 * d2 * Fg
# reverse map from finite field to elliptic curve
K = (Fk**(-2) + Dx, Fk**(-3) + Dy)
key = sha256(str(K[0]).encode()).digest()
c = bytes.fromhex('480fd106c9a637d22fddd814965742236eb314c1b8fb68e70a7c7445ff04476082f8b9026c49d27110ba41b95e9f51dc')
m = AES.new(key, AES.MODE_ECB).decrypt(c)
print(m)
