CTFのCryptoにおける楕円曲線まとめ [EC, isogeny]

CTFにおけるCrypto入門とまとめの1つです。

体系的に理解できておらず、殴り書きです。何も分からん。

楕円曲線

• 楕円曲線: 体Kに対して y²+a_1xy+a_3y = x³ + a_2x²+a_4x + a_6 を満たす解の集合を楕円曲線と呼ぶ
  • 数学的には、楕円曲線とは種数1の非特異代数曲線のことを指す。その中でもワイエルシュトラスの標準形が一般的な表現形式の1つ
    • 点の計算方法は楕円曲線（weierstress, edwards, mongomery,...）によって違うが、代数的構造は同じになる
      • 離散対数問題の困難性は同等で、同じレベルのセキュリティを担保できる
      • 実用上用いる楕円曲線によって計算効率が異なったり、mongomery形式はサイドチャネル攻撃に脆弱と言った実装上の差もある
    • 「種数1の非特異代数曲線」とは
      • 代数曲線 -> 多項式方程式 f(x,y) = 0 で定義される曲線
      • 非特異（smooth） -> 特異点がない。つまり、曲線上で偏微分が同時に0になる点（∂f/∂x = 0 かつ ∂f/∂y = 0）がない。尖ってるとダメ。だからsmooth
        • 楕円曲線の計算に接線を用いるものがあるが、その際に接線が一意に定まらない
        • また、「特異楕円曲線では離散対数問題が多項式時間で解ける」
          • Smart攻撃: 特定の特異曲線で効率的に離散対数を計算
          • 以上楕円曲線攻撃: 特異点を利用した鍵回復
      • 種数(genus) -> 種数1：トーラス（ドーナツ型、穴が1個）- 楕円曲線
        • 種数1の曲線のみが自然な群構造を持つ
  • Weierstrass 方程式: y²+a_1xy+a_3y = x³ + a_2x²+a_4x + a_6
  • ワイエルシュトラスの標準形 y^2 = x^3 + ax + b
    • a,bは有限体、x,yはa,bの「代数的閉包」
    • 4 a^3 + 27 b^2 != 0を満たす必要がある
      • これは特異点が存在しないための条件
    • 体Kの標数が2,3でないとき、x,yの線形変換によって2次項を消すことができ、a,b ∈ Kを用いてワイエルシュトラスの標準形に変換可能
    • mod pで素数pは5以上である必要がある
  • 表現方法: アフィン座標(x,y) -> 投影座標[X:Y:Z]
    • 投影座標：楕円曲線上の点を[x:y:1]で、無限遠点Oは[0:1:0]と表現する
      • sagemathもこの形式
      • この形式で計算することで加算公式が無限遠点があっても統一的に書けるし、計算も早いらしい
    • 他にもJacobian座標やProjective座標が使われ、こっちは除算が避けられ、計算効率が良いらしい
    • 多分座標の取り方は単純に実装上の問題だけであり、数学的なアレコレの問題ではない
• 体Kいろいろ
  • 体の標数 ch(K): 1を何回足したら0になるのかという数。どんな数も標数倍すると必ず0になる
    • 素体Fp: ch(Fp)=p
    • 有理数体Q, 実数体R: ch(Q)=ch(R)=0
    • 代数閉包 K‾: K係数多項式の解を取り込むことをできるだけ繰り返した代数構造
      • 実数体Rの代数閉包は複素数体C
  • 体Fとその演算+と演算*について
    1. 演算+に関してFは群であり、かつ任意の要素a,bに関してa+b=b+a（可換群）
    2. 演算*に関してFは+の単位元0を除くと可換群であり、0には逆元が無い
    3. *と+に対して分配法則が成り立つ。つまり、(a+b)*c=a*c+b*cでありc*(a+b)=c*a+c*b
  • 有限体 GF(q): mod qの整数のみで構成した体
    • 素体 Fp: 素数mod
      • 剰余環の表記を使ってZ/Zpみたいに書いたりする？
      • mod 素数はガロア体になる？
      • 確かに自然に受け入れていたが、素数modの有限体であれば、楕円曲線の加法の性質が全て保存される https://leonahioki.medium.com/%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9A%E3%81%AE%E5%A4%A2%E3%81%AE%E5%9B%BD%E3%81%AB%E4%BD%8F%E3%82%82%E3%81%86-12dcc675995a
        • これは有限体であれば全てそうなんだろうか。それとも、有限体の中でも条件がある？体であればいい？
    • 拡大体 Fpⁿ
      • GF(q^2, 'i', modulus=x^2+1)のように素体の多項式Fp[x]をn次方程式f(x)で割ったもの
      • Weilの定理 Fp乗で定義された楕円曲線E, t=p+1-#E(Fp)とすると
        • 1-tT+pT^2=(1-αT)(1-βT)を満たすαβで、#E(Fp^k) = p^k+1-α^k-β^k
        • #E(Fp^2) = p^2+1-(t^2-2p)
        • #E(Fp^3) = p^3+1-(t^3-3pt)
      • 拡大体の楕円曲線の位数は、
        • Fp³上の位数はFpの位数と関連する因数を持つことがある
        • p自身が拡大体の楕円曲線の位数の因数になることがある
    • フロベニウス写像：有限体に存在する重要な準同型写像 F(r) = r^p
      • F(rs)=F(r)F(s)であり、また、mod q上にあるので、F(r+s)=F(r)+F(s)でもある
      • よって、これは環準同型である
    • Fp上の種数1の非特異射影代数曲線である楕円曲線Eは Y^2 = X^3 + aX + b (a,b ∈ Fp, 4a^3+27b^2 != 0) と書けて、
      • 集合 E(Fp) = {∞} ∪ {Fp上の楕円曲線上の解}
      • E(Fp)はアーベル群となる（楕円曲線群と呼んだりするらしい）
      • a,bによって楕円曲線が異なるが、どれも位数は以下を満たす p+1-2 sqrt(p) ≦ #E(Fp) ≦ p+1+2 sqrt(q)
  • Zmod(p*q)とかでもいける。何でもいいの？ https://qiita.com/kusano_k/items/1e90d8a0840c7e23ef75#43-show-me-your-private-key-crypto-200-points
    • これは体ではないくない？
  • 有理数Q上の楕円曲線 https://chocorusk.hatenablog.com/entry/2023/04/23/183504#dice-vs-kymn-crypto
  • 実数R上の楕円曲線もある？
  • ちなみに、整数は乗法逆元が無いので体にならない（有理数は体）
• 楕円曲線E上の点に対して特殊な演算を定義して、無限遠点を足すと群になる
  • この楕円曲線上の二点A,Bに対してA+Bの足し算を定義する（無限遠点を0として定義すると、交換法則・結合法則が成り立つ。可換群）
  • A(x,y)に対する逆数は-A(x,-y)とx座標で反転させた点になる
  • A(x1,y1) + B(x2,y2) = C(x3,y3)
    • x3 = φ² - x1 - x2
    • y3 = -φ x3 - ψ
      • φ = (y2 - y1) / (x2 - x1)
      • ψ = (y1 x2 - y2 x1) / (x2 - x1)
  • 可換群であるため、掛け算が定義可能になる
    • 3R = R + R + R
  • 同様の定義で楕円曲線の有理点のなす群と考えたものをMordell-Weil群という（？）
    • 楕円曲面の Mordell-Weil 群には格子の構造が入るらしい（？？？）
• スカラー倍について
  • 楕円曲線上の点に定数xの逆数x^−1をかけるときは楕円曲線の位数の逆数をとる。つまり、位数が分かっていればスカラー倍で割れる
• 楕円曲線の位数 #E(Fp): mod p上の楕円曲線上にある点の総数のこと
  • この、楕円曲線上の全ての点は特殊な加法を導入することで群を成す
    • 群：①a・b∈G ②a・e = e・a=aとなる単位元eがある ③ a・a' = a'・a = eとなる逆元a'がある
    • ちなみに楕円曲線上の単位元はO（無限遠点）
      • sagemathだと(0 : 1 : 0)が無限遠点
  • Schoof法：楕円曲線E/Fqの位数#E(Fq)をO(log^8q)で求めるアルゴリズム
    • https://furutsuki.hatenablog.com/entry/2023/01/02/233804
    • https://zenn.dev/anko/articles/ctf-crypto-ellipticcurve#%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9A%E3%81%AE%E4%BD%8D%E6%95%B0
  • sagemathだとEC.order()で計算可能
    • EllipticCurve(GF(p^3, 'x'), [a,b]).order()のように'x'と明記すると計算が早くなるらしい https://github.com/hackthebox/cyber-apocalypse-2025/tree/main/crypto/Kewiri
  • なお、楕円曲線の一般的な位数計算は未解決問題
• 楕円曲線上の「点Pの位数」とは，rP=Oとなる最小の正整数rである．位数は常に存在し，楕円曲線の位数 #E(Fq)を割り切る
  • 位数は「巡回群の位数」から来ており、gⁿ=e(単位元)となるnのことを巡回群の位数と呼ぶ
  • n-等分点: 楕円曲線Eの点Pについてn倍したら単位元OとなるPの呼び方
  • ねじれ群:
    • n-等分点の集合をn-ねじれ群E[n]という E[n] = {P ∈ E | nP=O}
      • 1等分点は無限遠点のみ
      • 2等分点は楕円曲線とx軸の交点
    • 等分多項式: 楕円曲線の加法公式から計算できるn-ねじれ点のx座標を根に持つ多項式
      • https://en.wikipedia.org/wiki/Division_polynomials
      • sagemathだとn-等分多項式はE.division_polynomial(n)で計算可能
      • Ricerca CTF 2023 dice-vs-kymn
        • https://ricercasecurity.blogspot.com/2023/06/ricerca-ctf-2023-writeup-crypto.html
        • 等分多項式はdivision_polynomial(a, b, x, n)のような入力から計算するので、x,nが既知のとき、それを使ってa,bを計算することができる。
        • n=6固定でxは与えられる状態からa,bを特定したいので、a,b,xを変数として多項式を作って、xを入力して根となるa,bを求めたいので、出てきた多項式を因数分解して、xの解がn=6以上のものを採用して、そこから無茶苦茶頑張ってa,bをxで表現する（分からん）
        • a,bは整数Zのものだが、気にせず計算していいっぽい
    • sagemath https://doc.sagemath.org/html/en/reference/arithmetic_curves/sage/schemes/elliptic_curves/ell_torsion.html
      • torsion_subgroup()
      • torsion_orderみたいなやつもあったはず
  • 楕円曲線の位数を割り切るので、逆言うと特定の位数を持つ点を期待するのであれば、楕円曲線の位数はその数の倍数である必要がある（ラグランジュの定理）
    • 楕円曲線上には様々な位数を持つ点が存在する
  • 第一の生成元: 位数が最大の巡回部分群を生成する基準点の1つを返す
    • sagemathだとE.gens()で全ての生成元を取ってこれる。E.gen(0)と書くとそこから1つ取れる
  • 特定の位数oの点を得るには、ランダムに点を取り×(楕円曲線の位数/o)を計算して0でなければ、位数oの点が得られる
• Hasse の定理
  • 体の標数が2,3ではない有限体Fq上の楕円曲線E/Fqの位数#E(Fq)について、|#E(Fp) - (q+1)| ≦ 2 sqrt(q) が成り立つ
  • Hasse の定理 |E(Fq)|=q−t+1 の方が正しい？
    • tはフロベニウス写像Φのtraceであり、Φ²-tΦ+p=0を満たす数tである
• 群構造
  • 楕円曲線はアーベル群
  • 楕円曲線がなす群については、以下のいずれかになる EC.abelian_group()で確認可能
    • 1点集合の群（自明な群） Trivial group embedded in Abelian...
    • 巡回群。Eが全体で巡回群であることはまあまあ多い。実用されている暗号システムでは基本的に素数位数の巡回群になるようにパラメタが選ばれる
    • 巡回群2個の直和
      • BLS12-381の大元となる群は巡回群ではないが、その一部だけを使って巡回群になるようにしている
• 安全曲線 https://www.fujitsu.com/downloads/JP/archive/imgjp/jmag/vol50-4/paper06.pdf
  1. 曲線の位数が素数、またはほぼ素数であること
  2. 特殊な曲線にならない（特にtraceは0～2にならない）
• sagemathでx座標から点を求めるときは、 A = E.lift_x([x座標])とする
• SageMathが曲線を初期化できない -> 曲線が壊れている -> 楕円曲線に置いて壊れているというのは「特異である」ということ
  • https://writeups.thebusfactoris1.online/posts/2025-07-28-FaultyCurve-writeup
• 曲線によって、色々な性質が出てきたり、計算が高速化できたりする
  • 規格化されたものはここにまとまっている https://neuromancer.sk/std/nist/P-256
  • BLS12-381曲線 a=0,b=4、つまり、y² = x³ + 4
    • AlpacaHack Round 3: A Dance of Add and Mul
    • https://hackmd.io/@benjaminion/bls12-381#Motivation
  • secp256k1 a=0,b=7としてy²=x³+7
    • ビットコインやイーサリアムで使用
  • curve25519 EllipticCurve(GF(2^255-19),[0,486662,0,1,0])
    • montgomery形式だが楕円曲線
  • ed25519 ツイストエドワーズ曲線
    • 位数が2²⁵⁶程度の群。正確には楕円曲線ではないらしい
  • paring friendly curves
    • BN254 (also called alt_bn_128 or BN128)
    • BLS12-381
  • NIST P-256: ecdsa-sha2-nistp256で使われる。これも位数が2²⁵⁶程度の群
  • 楕円曲線DB https://www.lmfdb.org/EllipticCurve/Q/?jinv=-3375&surj_quantifier=include&count=100
• 色々な楕円曲線
  • ワイエルシュトラス y^2+a_1xy+a_3y = x^3 + a_2x^2+a_4x + a_6かy^2 = x^3 + ax + bで定義され座標は(x,y)
  • モンゴメリー曲線 Montgomery y^2=x^3+Ax^2+x
    • Aはモンゴメリ係数
      • wikipediaではBy^2=x^3+Ax^2+xとして、パラメタをA,B（B(A^2-4)≠0を満たす）だった
    • 単一座標系を持つ。つまり、座標はx座標のみで表現される。yは無視される（なぜ無視してよいのかはよく分かってない）
      • これにより効率的なスカラー倍演算が可能になる
    • sagemathだと EllipticCurve(F, [0, A, 0, 1, 0])
    • ワイエルシュトラスに変換可能
  • Edwards形式 x² + y² = 1 + dx^2y2
    • sageでやるとき。p,c²,d PR.<x, y> = PolynomialRing(GF(p)) f = y^2 - (x - c^4*d - 1) * (x^2 - 4*c^4*d) EC = EllipticCurve(f) P_EC = EC(Px, Py) S_EC = EC(Sx, Sy) s = P_EC.discrete_log(S_EC)
    • P,Q,sP,tQの点からEdwards curveのパラメタを頑張って求められる https://blog.y011d4.com/20210801-crypto-ctf-writeup#rohald
  • ツイストエドワーズ曲線
  • バイナリエドワーズ曲線
  • Hessian形式
    • ねじれたヘッセ曲線
  • ヤコビ四次関数
  • ハフ曲線
  • 他にも https://zenn.dev/anko/articles/ctf-crypto-ellipticcurve#%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9A%E6%9A%97%E5%8F%B7%E3%81%AE%E3%83%91%E3%83%A9%E3%83%A1%E3%83%BC%E3%82%BF にある
  • sagemathの楕円曲線の定義の仕方
    • EllipticCurve([a1,a2,a3,a4,a6]) Weierstrass標準形の係数から作成
    • EllipticCurve_from_j(j0) j-不変量の値から作成
    • EllipticCurve('label') Cremona databaseと呼ばれる楕円曲線のデータベース上に登録されたラベルから作成
      • https://www.lmfdb.org/EllipticCurve/Q/910c1/ なら"910c1"を入れる
    • EllipticCurve_from_cubic 3次曲線から構成
      • 戻り値はECではなく、双有理写像が与えられる
• 有限体上の楕円曲線は通常曲線と超特異曲線に分類できる
  • 標数p上の超特異曲線は…
    • 約p/12個存在する。つまり、ランダムに曲線を生成したとき超特異である確率はおおよそ1/p
    • 全てFp²上で定義される（これ大事では？）
      • j-不変量を鍵として共有するときサイズは2logpくらい
  • Tateの定理：超特異曲線と同種な曲線は超特異
  • 超特異曲線Eは位数で特徴づけられる
    • #E(Fp) = p+1
    • #E(Fp^2) = (p+1)^2 または (p-1)^2
• 判別式D、j-不変量が固定であれば、位数と素数の間に固定的な関係があるかも
  • ハッセの定理
  • フロベニウス跡、トレース t を使って、#E(Fp) = p+1-t
• 色んな情報から、もともとの楕円曲線を導く
  • 加法計算と倍数計算が分かっているとき -> idekctf 2025 - Sadness ECC Revenge https://giapppp.github.io/posts/idekctf-2025/
    • dy/dxを導く | dy/dx=2x/3(y-1337)²
    • 分数をなくす | 2xdx = 3(y-1337)^2dy
    • 積分 | ∫2xdx = ∫3(y-1337)^2dy
    • x² = (y-1337)³ + C
    • サンプルを使ってCを特定
  • 計算を書き下して連立方程式とかgcdとか方程式とか https://blog.y011d4.com/20210801-crypto-ctf-writeup#double-miff
• sagemathでP(x,y)から定数倍をしたときのQの多項式表現が得られる
  • E.multiplication_by_m(2)とすると((x^4 + 2*x^2 - 24*x + 1)/(4*x^3 - 4*x + 12),(8*x^6*y - 40*x^4*y + 480*x^3*y - 40*x^2*y + 96*x*y - 568*y)/(64*x^6 - 128*x^4 + 384*x^3 + 64*x^2 - 384*x + 576))が得られる。x座標はxの多項式になり、次数はk²になる
  • E.multiplication_by_m(2, x_only=True)とすればx座標のみ得られる
  • https://github.com/ImaginaryCTF/ImaginaryCTF-2025-Challenges/blob/main/Crypto/scalar-division/solve2.sage
    • poly = E.multiplication_by_m(k,1)でk倍した表現を得て、定数倍した後のx座標Qxが分かっているので、poly = poly.numerator()-Qx*poly.denominator()という多項式が得られて、R.<x> = PolynomialRing(GF(p))のように多項式環を作ってpoly = R(poly)と変換し、mod pなのでpoly2 = pow(x,p,poly)-xも同様に成り立ち、これでfinal = poly.gcd(poly2)のように多項式のGCDをして簡約してroots = final.roots()のように根を取れば元々のxが分かる
• j-不変量
  • F = GF(p)でE = EllipticCurve(F, [1, 2])のとき- F(1728) * F(4*1) ** 3 / F(E.discriminant())で計算
  • 楕円曲線の同型類を考えるためのもの
• 性質の良い楕円曲線を探す https://github.com/Sarkoxed/ctf-writeups/blob/master/trx-2025/magic_curves/solve.py
  • 以下の条件を満たす(p,a,b)を探す例
    • Fp上の2つの楕円曲線、y²=x³+ax+bとy²=x³+bx+aが同型である
    • 同型であるということは位数が等しいということだが、その位数がsmoothである
  • 写像x→λxを使って色々変形すると、b/λ²=aかつa/λ³=bを満たせばよく、これはλ⁵=1を満たすλを選べば、この条件が満たされる。λ⁵=1を満たすλを見つけるためにはFpの位数が5の倍数である必要があるため、p-1が5の倍数であるpを最初に選択している。それで1の5乗根を取ってλとして、Fp乗の適当な元をaとして、そこからλを使ってb=a/λ³で計算し、あとは生成した楕円曲線の位数がsmoothであることを確認する。

楕円曲線暗号: ECC: Elliptic Curve Cryptography と楕円曲線上の離散対数問題 ECDLP: Elliptic Curve Discrete Logarithm Problem

• ECC: Elliptic Curve Cryptography
  • 楕円曲線を使う暗号プリミティブを総称して楕円曲線暗号方式と呼ぶ
  • ECDLPを背景とした、元々の離散対数問題を背景とした方式を拡張したもの
    • DH鍵共有 -> ECDH鍵共有
      • Union CTF human server
        • 鍵交換に不要なnonceのxorを追加したせいで壊れた例
        • https://blog.y011d4.com/20210222-unionctf-writeup#human-server
        • https://words.filippo.io/telegram-ecdh/
    • ElGamal暗号 -> 楕円ElGamal暗号
    • DSA署名 -> ECDSA署名
  • 以下の楕円曲線と生成元を公開パラメタとして使う
    • #E(Fp) = rが巨大な素数である有限体Fp上の楕円曲線E
      • 具体的には r≈pを満たす曲線パラメータを利用するらしい
    • 位数rの巡回群E(Fp)の生成元S
• CurveBall CVE-2020-0601: Q=dPでQとPが固定のときdを解くのは難しいが、Qが与えられてdとPを自由に決められるなら、等式を満たすdとPをQから決めるのは簡単。d=2とかにしてP=Q/dすればいい。

ECDLP 楕円曲線における離散対数問題

• ECDLP: 楕円曲線上の点P,QについてQ=dPという関係があるとき、P,Qからdを求めることが難しい
  • ECDLPはmod P上でのDLPよりも困難であると強く信じられているらしい
  • dPの計算は繰り返し二乗法を使う方法や、それ以外にもモンゴメリの二分法がある
    • 特にモンゴメリの二分法は加算と乗算の回数がどんな同じビット数の値でも等しくなるので、タイミング攻撃に強い
• 以下、解き方
• 楕円曲線の位数が小さいのでsageのdiscrete_logで殴ると解けます sG=Qならばs = G.discrete_log(Q)
  • CSAW CTF Qualification Round 2019 Supercurve https://furutsuki.hatenablog.com/entry/2020/05/05/112207
  • log(A,G)でも殴れる。discrete_logとの違いは分からないが、logだとSSSA Attackを自動でやってくれるっぽい？
    • いや、discrete_logはdepricatedな書き方で中身は同じっぽい？
• BSGS: Baby-step-giant-step, 平方根法
  • 楕円曲線の位数が小さいときに使える。位数N=#Eであり、m=sqrt(N)とすると、d=am+bと書くことができ、
  • Q=(am+b)PでQ-bP=a(mP)と変形でき、左辺右辺を0≦a,b＜mの範囲で全探索して一致するものを探す
  • sagemathであればdiscrete_logを使えば自動でPohlig–Hellman法+BSGSしてくれる
    • が、進捗が見えないので、tqdmで進捗を可視化した例がこちら https://github.com/Sarkoxed/ctf-writeups/blob/master/trx-2025/magic_curves/solve.py
• Pollardのρ法、λ 法 (kangaroo-algorithm) ？
• PHS法: Pohling-Hellman-Silverman法
  • 曲線の位数が小さい素因数の積の形に分解できる、つまり、位数が Smooth numberであれば適用可能。楕円曲線暗号の楕円曲線の位数は細かく素因数分解できることが多いので RSA とかと違って実用的な手法らしい。
  • #E=p1^e1 p2^e2 ... pk^ekとなるとき、O(ei sqrt(pi))でECDLPが解ける
    • https://zenn.dev/anko/articles/ctf-crypto-ellipticcurve#pohlig-hellman が無茶苦茶分かりやすい
    • G=xPであり、#E=A*Bのとき
      • G'=B*GしてP'=B*Pして、G'.discrete_log(P')で離散対数して、k'を得る
      • 同様にk''を得る
      • CRT(k', k'', A, B)で答えを得る
  • https://chocorusk.hatenablog.com/entry/2024/09/16/001208#A-Dance-of-Add-and-Mul
    • factor(E.order())で楕円曲線の位数を素因数分解して3 * 11^2 * 10177^2 * 859267^2 * 52437899^2 * 52435875175126190479447740508185965837690552500527637822603658699938581184513となったのでやった。今回はmod 10177だけ分かれば十分らしい
  • picoCTF 2017 ECC2 https://furutsuki.hatenablog.com/entry/2020/05/05/112207
• Index Calculus Algorithm https://zenn.dev/anko/articles/ctf-crypto-ellipticcurve#index-calculus-algorithm
  • Index Calculus: 種数の大きい超楕円曲線上の DLP を Index Calculus Algorithm で解く
  • Weil descent: Fpⁿ上の楕円曲線のDLPをFp上の超楕円曲線のDLPに置き換えてIndex Calculusを用いる
    • Weil-Descent Attack (有限体の n 次拡大体の上の楕円曲線のECDLPをDLPへ帰着し, Index-calculus法を併用してECDLPを解く. )
  • Generalized Weil descent: Fpⁿ上の楕円曲線のDLPに直接Index Calculus Algorithmを適用する
  • Xedni-Calculus法 (特定条件下の楕円曲線におけるIndex-Calculusの効率化. XedniはIndexの逆)
• SSSA(:Semaev-Smart-Satoh-Araki) Attack: Fp上の楕円曲線Eについて#E=pである、つまり、Anomalous な曲線（アノマラス曲線）であれば適用可能で、Fp+上（有限体の加法群上）のDLPに帰着できる
  • SSSA Attack, Smart Attack
  • 攻撃手順 アノマラス曲線E(Fp)と、その上の点P,Q、また、Q=nPであるときのnを求めることを考える
    1. p進数への持ち上げ: Fp上の点PとQをp進数体Qp上の楕円曲線上E'の点P'とQ'に持ち上げる。（Hensel Lift, Henselの補題などを使って行う）
       • 持ち上げ後はp進数上の楕円曲線であり、これは拡大体とは異なり、p進体Qp（または、p進整数環Zp）上で定義された楕円曲線
         • 拡大体は a0 + a1 x みたいな式だったが、そうではなく普通に[0, p²)みたいに純粋に累乗modとして考えたもの（多分）
         • 拡大体はGF(pⁿ)で、p進数はZmod(pⁿ)
       • p進数はa= a0 + a1p + a2p² + ...という形の無限級数で表現されるもの。Smart AttackではFp上の曲線を同型のZp上の曲線に持ち上げる
       • 持ち上げるときの精度はp²の精度で十分。Smart Attackの目的は形式群を使って離散対数を計算することで、そのためにはmod p-2の情報があれば十分
       • 楕円曲線の点のHensel Lifting
         • つまりは、mod pをmod p²に変換する。Fp上の点P=(x0, y0)をZp上の（mod p²の）点P'=(X, Y)に持ち上げる。mod p²と2乗で止めているのは近似的であるらしいがmod pで計算する場合はこの精度で問題ないとのこと。
           1. mod p²で定義する。 X=x0+tp (mod p²), Y=y0+sp (mod p²)とする。これならmod pで元々の点Pと一致する
           2. 持ち上げられた点はY²=X³+AX+B (mod p²)を満たす必要があるので、代入して整理し、mod pに変換して計算していくと、sとtの関係式を作ることができ、片方を固定すれば片方が決まり、s,tを決定できる。具体的には s = (3x0²+A)t/(2y0) mod p
         • 別の方法 https://mslc.ctf.su/wp/polictf-2012-crypto-500/ （上の式間違ってない？）
           1. X=x0 mod p²のままにして、Y=y0 + tp mod p²としてtを計算する（上のやり方で片方を0にしているだけ）
           2. fr = y² - (x³ + Ax + B)としたとき t = -fr/(2yp) mod p
       • 2番目の写像Φが同型である持ち上げ写像を利用する必要があり、そのためにAnomalousな曲線である必要がある？ https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1814-10.pdf
         • 「楕円曲線 E が anomalous のとき（つまり，N = p のとき），持ち上げ写像 u により定まる写像 λ(u) は群の同型写像か零写像である」 https://www.cryptrec.go.jp/exreport/cryptrec-ex-3001-2020.pdf
       • ちゃんと持ち上げをしなくても適当に(x,y) → (x,py)と変換してしまって、それに合うようにA,Bを作り直すという方法もある https://mslc.ctf.su/wp/polictf-2012-crypto-500/
    2. 形式群への写像: p進楕円曲線から加法群への同型写像Φを構築する。Φ：E'(Qp) → p Zpという準同型写像を使う
       • 具体的には、点P(x,y)のとき、Φ(P)=-x/y mod p² とする。←なんか違う? Claudeが出してきたやつ
       • あんこさん https://zenn.dev/anko/articles/ctf-crypto-ellipticcurve#anomalous-%E3%81%AA%E6%9B%B2%E7%B7%9A%E3%82%92%E7%94%A8%E3%81%84%E3%81%A6%E3%81%AF%E3%81%84%E3%81%91%E3%81%AA%E3%81%84-(sssa-attack)
         • Φ(P) = (xp-1 - x1)/(p(yp-1 - y1)) mod p²
         • hellmanさんもいっしょ https://mslc.ctf.su/wp/polictf-2012-crypto-500/
       • Kobaさん https://github.com/koba-e964/code-reading/tree/master/algorithm/smart-attack
         • Φ(P) = pPを計算したときのx座標？なんも分からん
           • https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecc/smart_attack.py と一緒で Φ(P)はpPとしてx/y？
       • これが以下を満たす。この写像がミソなんだと思うが、どういう難しさをクリアしているのかすらわからん
         • 準同型性: Φ(P+Q) = Φ(P) + Φ(Q)
         • 出力は常にpの倍数: Φ(P) ∈ p Zp
         • pねじれ点との交わりは無限遠のみ kerΦ ∩ E[p] = {0}
       • p進数体Qp上の楕円曲線E'に付随した形式群の対数関数を用いて、Z/pZへの同型写像λEを構成している。ということらしい
    3. 離散対数の計算: Φ(P')=a, Φ(Q')=bとすると、Φ(Q')=nΦ(P') mod p²が成立する。つまり、b=na mod p²であり、逆数を取ればn=b/a mod p²でnが求まる
    4. https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecc/smart_attack.py の実装を見ると上をやってる
  • SSSA Attackの説明で 0 → ker π → E(Qp) -π→ E(Fp) → 0というのがある
    • πは還元写像
    • 0 → ker π → E(Qp) πを使って元々は0となる数をp進数体Qpに持ち上げることで点に変換する。これは元々はmod pでは0だったが、mod p²にすることによって、0+tpになったものを指している
      • kerはkernelのことで、写像によって無限遠になる集合を指す
      • よって、ker πはpの倍数であると言える。それを表現しているのがp Zp。つまり、pの倍数。このとき、(x,y) ↦ x/yの群の同型写像が存在する
    • E(Qp) -π→ E(Fp) → 0 よくわからん
  • shihoさんの説明「 pべきでmodを取っていることからp進数体に持ち上げる攻撃が最も高速です. すなわち, Nを mod p上での 楕円曲線 y²=x³+ax+bの位数とするとき, N倍写像の像はその楕円曲線の形式群に含まれますから, 形式対数を取って割ればECDLPは解けます」https://gmo-cybersecurity.com/blog/ierae-ctf-2024-writeup-crypto/
    • SSSA AttackではAnomalousな曲線を使っているのでN=pであり、p倍写像をしていることになる
      • だが、そのままやると位数がpなので、任意の点をp倍すると0（無限遠点）となってしまう。なので、p進数体Qpに持ち上げることで、0ではなく、形式群に含まれる点になる
      • この場合、pPは完全な0（無限遠点）にはならず、わずかな「残り」が出る（つまり、この辺が無限遠点の近傍ということになるのだろう）
    • 形式群 formal group: 無限遠点の近くでの楕円曲線の振る舞いを記述する代数的構造。具体的には、無限遠点の近傍での加法群を形式的べき級数で表現したもの
      • 代数的構造ってなんだっけ
      • 無限遠点の近傍での加法群を形式的べき級数???
      • とりあえず、楕円曲線上の点のうち、無限遠点に十分近い点だけを考えた集合であり、これらの点は簡単な式で近似できる（これはべき級数であり、多項式近似と似たように近似できると考えれば良い）
    • 形式対数 formal logarithm: 楕円曲線の形式群から加法群への同型写像
      • 形式対数log_fを使うことで、log_f(pP)=p log_f(P)、log_f(pQ)=log_f(kpP)=kp log_f(P)となり、k=log_f(pQ)/log_f(pP)で計算可能になる
  • あまりよく分かっていないが p進数体 とは？
    • p進数体は、通常の10進数や2進数のような数の表し方ですが、基数がpで、特に「pで割り切れる回数」に注目します。
    • 距離の概念が少し違うらしい
  • 攻撃実装例
    • やるだけならライブラリでシュッとできる https://hackmd.io/@FurgjSzLSjeQo0q8zgTaqQ/HJT3Raboyx#Customizable-EC
  • O((logp)³)で解ける
  • https://zenn.dev/anko/articles/ctf-crypto-ellipticcurve#anomalous-%E3%81%AA%E6%9B%B2%E7%B7%9A%E3%82%92%E7%94%A8%E3%81%84%E3%81%A6%E3%81%AF%E3%81%84%E3%81%91%E3%81%AA%E3%81%84-(sssa-attack)
  • 多分理論を最も分かりやすく書いているであろう日本語の論文 https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/61761/1/1026-15.pdf
    • https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1814-10.pdf
    • https://dspace.jaist.ac.jp/dspace/bitstream/10119/4422/1/C-456.pdf
      • https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/61761/1/1026-15.pdf
      • https://www.cst.nihon-u.ac.jp/research/gakujutu/63/pdf/P-3.pdf
  • Easy? ECDLP -> modpで見ると楕円曲線の位数がちょうどpになっているので、SSSA attackでsecret modpが求まる。あとはzer0pts ctf 2021 pure divisionと同様にmodp⁴にliftできる https://hackmd.io/@mitsu/ByhK-tZX_
  • ecpyにソルバーがある https://furutsuki.hatenablog.com/entry/2020/05/05/112207#ptr-yudai%E3%81%AE%E7%99%BA%E8%A1%A8:~:text=print(m)-,TJCTF%202016%20Curvature2,-Anomalous%E3%81%AA%E6%9B%B2%E7%B7%9A https://github.com/elliptic-shiho/ecpy/tree/master
  • TJCTF 2016 Curvature2 https://furutsuki.hatenablog.com/entry/2020/05/05/112207
    • https://gist.github.com/elliptic-shiho/40d42dbab87065e06d6c473ef93e244e
  • 実装例 https://gist.github.com/saitenntaisei/d6c05c10276aaf3865fefd18fb331ccd
  • ガチすぎる。助けて https://github.com/koba-e964/code-reading/tree/master/algorithm/smart-attack
  • https://blog.y011d4.com/20221207-crypto-highlight#hitcon-ctf-2022-chimera
  • zer0pts pure division
    • https://mitsu1119.github.io/blog/p/zer0pts-ctf-2021-writeup-%E6%97%A5%E6%9C%AC%E8%AA%9E/
    • https://hackmd.io/@mitsu/ByhK-tZX_
    • https://rkm0959.tistory.com/213
      • https://arxiv.org/pdf/2010.15543
  • https://www.nayuki.io/page/elliptic-curve-point-addition-in-projective-coordinates
  • https://www.cryptrec.go.jp/exreport/cryptrec-ex-3001-2020.pdf
  • Anomalous curveの生成 https://github.com/koba-e964/code-reading/tree/master/algorithm/gen-anomalous
  • [類題] 似たような話として、楕円曲線E(Z/p^2Z)やE(Z/q^2Z)上では、解がp,q以下の場合、簡単に離散対数問題が解けるということがある。zer0pts 2021 - pure division
    • 作問者writeup https://mitsu1119.github.io/blog/p/zer0pts-ctf-2021-writeup-%E6%97%A5%E6%9C%AC%E8%AA%9E/
      • Z/p^3Z上での楕円曲線でECDLPする問題
      • Z/p^nZは精度n桁のQpを見ることができる。この問題はSSSA Attackの持ち上げ後からスタートと考えればいい？違いそう。
      • これはSSSA Attackと似たような整理なのでなんとなく分かる：還元写像πをP²(Qp)→P²(Fp)、εをEの形式群、Φ: ker π ∋ (x,y) ↦ -x/y ∈ P²(Q)とすれば、ker π -Φ→ ε(pZp) -logε→ pZpという同型写像が構成可能
      • 分からん: P ∈ E(Qp)に対して N=#Ef(Fp)とすれば、NP ∈ kerπなので、E(Qp) → ker π → pZp
      • 分からん: pZp ≃ Fp+なので、同型写像で変換していくことでFp上の問題に帰着でき、後は割り算でECDLPが解ける。
    • hellman https://affine.group/writeup/2021-01-Zer0pts#pure-division
      • Fp = Zmod(p**3)のようにZ/p^3Zが定義されていて、E = EllipticCurve(Fp, [a1, a2])のようにECを作っている
      • ordp = E.change_ring(GF(p)).order()のようにGF(p)に変換して位数を計算する。（が、これはブログを見ると分かるが#E(Fp) != pである
      • ここで、普通のSSSA Attackのように、つまり、Z/p^3Z上での楕円曲線を持ち上げ後の楕円曲線として考えて、ordp*Sをしてみると、エラーになる（pで割り切れるらしい）
      • なので、Z/p^3Zではなく、Qpにringを変換してやって、同様のことをする。
      • EQp = E.change_ring(Qp(p))として、pS = EQp(S)*ordpとpT = EQp(T)*ordpのようにしてやる。これならうまくいく
        • これは、SSSA Attackの時にもあった、持ち上げ後に零写像になってしまうことがあり、その場合は持ち上げのやり方を変えてやれば成功する的な話だろうか
      • あとは、同様に形式対数を取って、Fp上に同型写像して、割ればいいので、sol = ZZ((pT[0] / pT[1]) / (pS[0] / pS[1]))で解ける
        • このパートが一番良く分からんくて、anomalousな曲線ではないと思うのだが、これがうまくいく理由が分からない
        • sagemathだとBin(sol).bytesとすればint2bytesできるらしい。知らんかった
    • https://rkm0959.tistory.com/213
  • [類題] IERAE CTF 2024 - Heady Heights
    • https://gmo-cybersecurity.com/blog/ierae-ctf-2024-writeup-crypto/
  • [類題] TSGCTF2024 - Easy? ECDLP
    • Zp⁴でのECDLPを解く問題。#E(Fp)=pであり、SSSA Attackが使える
    • https://hackmd.io/@yu1hpa/Hk_1GznV1l#Easy-ECDLP
      • SSSA Attackを使う。Zp⁴をQp⁴に変換し、ヘンゼルリフトでQp⁵に変換し、Fpでの解を得る。
      • そこから、Fpでは情報量が足りないのか、p⁴に戻している。なぜできるのかはよく分かってないが、https://mitsu1119.github.io/blog/p/zer0pts-ctf-2021-writeup-%E6%97%A5%E6%9C%AC%E8%AA%9E/ を見ると、p進展開を利用しているように見える
      • https://x.com/nuo_chocorusk/status/1868193798322639193 も同様
    • https://www.youtube.com/watch?v=G0bHFyFWhL0
      • Zp⁴をQp⁸にヘンゼルリフトで変換して、SSSA Attackして、同様に諸々計算した結果がZp⁴でいる（#E(Zp⁴)=p⁴ということだろうか）kurenaifさんはライブラリ化していた。
    • [類題] TSGCTF2024 - Easy?? ECDL
      • https://x.com/JP3BGY/status/1868200686883856434
        • Silverman Chapter VII
        • 精度がほぼ常に8になることから剰余体上の楕円曲線の部分群をつぶしてQp上のDLPを解くだけで解けたみたい
      • https://x.com/nuo_chocorusk/status/1868193798322639193
        • 楕円曲線の方程式とP,Qの座標がちょうどZ_pの元になるように(x',y')=(p^2x,p^3y)の変換をすると、modpで見たときに楕円曲線がsingularになる。cuspの場合は簡単、nodeの場合は位数がp²-1の約数になるので、p-1とp+1の素因数がどちらも小さくなるようにpを決めれば、secret modpが求まる。これはSSSA Attackではなく、別のやつっぽい
      • https://d-xuan.github.io/wednesday/ctf/TSGCTF2024/
      • https://hackmd.io/@yu1hpa/Hk_1GznV1l#Easy-ECDLP24
    • スピードが求められる Smart Attackで使ったライブラリ
  • 解説シリーズ
    • Part1 https://solvable.group/posts/anomalous-curves-1/
    • Part2 https://solvable.group/posts/anomalous-curves-2/
    • Part3 https://solvable.group/posts/anomalous-curves-3/

MOV / FR Reduction

• MOV / FR Reduction: Fp上の楕円曲線Eについて#E=p±1である、つまり、Supersingular な曲線であれば適用可能で、埋め込み次数kを用いてFp^k+上の DLP に帰着できる。ECDLPをFFDLPに変換可能
  • 唯一日本語で細かく解説されている https://zenn.dev/anko/articles/ctf-crypto-ellipticcurve
  • https://risencrypto.github.io/WeilMOV/
    • MOV Attackができると、E(GF(p))をGF(p^k)×に、もっと言うとGF(p)×上での離散対数問題に帰着させることができる
    • この時、112ビットセキュリティを担保するには、RSA,DHだと2048bitsの鍵長が必要になるが、ECDHであれば224bitsの鍵長で済む
      • よって、同じGF(p)上での離散対数問題であってもECDHをDHに変換できるだけで、必要な計算量を各段に減らすことができている
    • 線形写像 linear map「f:V→W」において、「f(v1+v2)=f(v1)+f(v2)」かつ、「f(av)=af(v)」である
    • 双線形写像 Bilinear map「f:U×V→W」において、「f(u1+u2,v)=f(u1,v)+f(u2,v)」かつ「f(u,v1+v2)=f(u,v1)+f(u,v2)」かつ「f(au,v)=af(u,v)=f(u,av)」である
    • Fpの元は全部p-1乗すると1になる。その拡大体のFp^tでは全部p^t-1乗すると1になる（最小ではなくp^t-1を割り切るらしいが、今後の理論には関係しなさそう）
      • この式が埋め込み次数kと関係する
    • 埋め込み次数k: 素体Fq上の楕円曲線Eについて、Pを位数mの点、mが素数でありqと互いに素である場合に、q^k=1 mod mが成り立つ最小のkを埋め込み次数と呼ぶ
    • 位数mの点、つまりmP=Oを満たすPをm-ねじれ点といい、全てのm-ねじれ点の集合（m-ねじれ群）の部分集合をm-ねじれ部分集合という
      • m-ねじれ部分集合（m-ねじれ集合？） E(Fq)[m] = {P∈E: mP=O}
    • ここで、埋め込み次数kを使った、素体Fqの拡大体Fq^kを考える
      • 拡大体Fq^kはベースの体Fqよりも大きいため、m-ねじれ群もまた大きくなる
      • よって、この拡大体では、より多くのmねじれ点を追加しないFq^kよりもより大きい拡大体になる（？）
      • よって、E(Fq^k)[m]はfull m-ねじれ群と呼ばれる
    • Full Torsion Group、全ねじれ群は複数の部分群をもち、そのうちの2つをWeil Pairingでは使う
      • G1: E(Fq)上にある点の部分集合
      • G2: E(Fq)上にはないがE(Fq^k)にはある点の部分集合。複数考えられるが、どれを選んでも問題ない
    • Weil Pairing
      • 埋め込み次数の定義からq^k-1=0 mod mということはq^k-1=mxということになる
      • また、Fq^k上での乗法群を考えると0以外の全ての要素はq^k-1乗すると1になる。1つ上の定義からq^k-1はmで割り切れるため、巡回群の基本的な定理より、位数がmである一意の部分群GTが存在することになる
      • m∤(q−1)、つまり、mが(q-1)を割り切らないとき、G1×G2→GTとなるWeil pairingを構築可能（なぜ？）
        • em: G1×G2 → GT
      • このWeil Paringでは、EC側（左辺）は加算群であるが、GT側は乗法群となる。この写像は以下のような性質を持つ
        • 双線形写像
          • em(A1+A2,B)=em(A1,B)*em(A2,B)
          • em(A,B1+B2)=em(A,B1)*em(A,B2)
          • em(aG1,bG2)=em(bG1,aG2)=em(abG1,G2)=em(G1,abG2)=em(G1,aG2)^b=em(G1,G2)^ab
        • Identity: em(A,A)=1 for all A ∈ E[m]
        • Alternation: em(A,B)=em(B,A)^-1
        • 非退化 Non-Degeneracy: em(A,O)=1 for all A∈E[m] であり、逆にem(A,B)=1でB∈E[m]であればA=O
    • MOV Attack:
      • Fq上の楕円曲線Eで、素数位数mを持つ2点P,Qがあり、Q=rPという関係にあるとする。P,Q∈G1である
      • n = #E(Fq^k)を計算する。m|nになるはず
      • E(Fq^k)上にある位数がmの点Sを取得する
        • ランダムにT∈E(Fq^k)を取る。T∉E(Fq)である必要がある
        • S=(n/m)Tを計算する。S=OならTを取り直す。こうするとmS=nTになる
        • Tの位数をtとすると、ラグランジュの定理より、tは#E(Fq^k)を割り切る。つまり、t|n。よってdをつかってn=dtと書ける。こうすると、mS=dtTとなる
        • tはTの位数なのでdtT=dO=Oとなる。つまり、mS=Oとなり、Sの位数はmになる
        • https://furutsuki.hatenablog.com/entry/2022/12/13/131802 にあるテク
      • これでP,rP∈G1, S∈G2が手に入ったのでWeil Pairingをする
        • u=em(P,S)
        • v=em(rP,S)=em(P,S)^r
        • u,v∈Fq^k、かつ、v=u^rを満たすu,vが手に入り、これでECDLPからDLPへの変換が成功した
      • q^kが大きすぎなければ、u=v^rはIndex Calculusで解け、rが求まる。このrはECDLP上でのrの値と一致している
    • kは20以下でないことを確認するように推奨している。CTFでは2か、大きくても6くらい？
• 勉強してみたお気持ち: そのままWeil PairingをQ=rPに使おうとすると線形性があるのでem(P,rP)=em(P,P)^r=1となってしまって進まないので拡大体に一回映してねじれ群を増やして線形独立な点を探してきて使うことでem(P,B)!=1にしてうまくWeil Pairingによって乗法巡回群に落とし込んでいる？
  • https://blog.tanglee.top/2024/08/24/Intro-to-Bilinear-Map.html
• 実用的には...
  1. 埋め込み次数kの計算 p^k-1 = 0 mod #E(Fp)を満たす最小のkを計算
  2. k≦6ならMOV攻撃可能！
  3. https://zenn.dev/hk_ilohas/articles/3c7ff88cb319fc からmov_attackを借りて使う 他実装 https://www.hackthebox.com/blog/movs-like-jagger-ca-ctf-2022-crypto-writeup
• 埋め込み次数 k
  • k=1のとき、つまり、位数がp+1のとき、楕円曲線はSupersingularであると言う
    • E.is_supersingular()でsupersingularか判定できる
• MOV attack 有限体の上の離散対数問題になる -> Weil-paringを使う
  • E(GF(p)) ≅ E(GF(p**k)) ≅ GF(p**k)×
• Frey-Rück Reduction (同上, Tate-pairingを用いる)
  • https://gist.github.com/mcieno/f0c6334af28f60d244fa054f5a1c22d2
  • MOV Attackと比較して単純にペアリングパートでTate-pairingを使っただけ
  • https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecc/frey_ruck_attack.py
• https://zenn.dev/anko/articles/ctf-crypto-ellipticcurve#supersingular-%E3%81%AA%E6%9B%B2%E7%B7%9A%E3%82%92%E7%94%A8%E3%81%84%E3%81%A6%E3%81%AF%E3%81%AA%E3%82%89%E3%81%AA%E3%81%84-(mov-%2F-fr-reduction)
• 楕円曲線上のペアリングを利用して、楕円曲線のDLPを有限体の乗法群上のDLPへ帰着。特にEが超特異曲線のときに有効

Singular Curve Point Decompression Attack

• E = EllipticCurve(GF(p), [a,b])をしたときにSingularな曲線ならエラーになる
  • 4a^3+27b^2=0 mod pであれば特異点を持つSingular曲線
    • 楕円曲線の判別式 Δ=4a^3+27b^2
    • 特異な曲線であることから、この判別式を使ってaからbを求める問題 https://writeups.thebusfactoris1.online/posts/2025-07-28-FaultyCurve-writeup
  • sageでf = x^3 + a*x + bとしてf.factor()すればcuspかnodeか分かる
• Singularな曲線、特異点を持つ曲線、特異曲線の性質を利用するもの
  • 特異点 -> ある関数f(x,y)=0の特異点とは、∂f/∂x=0となるx座標、∂f/∂y=0となるy座標を持つ点のこと
    • 微分値が不定となる点、グラフ上では関数の曲線が交差している点
  • 楕円曲線の曲線は高々 1 回交わるので、Singularな曲線は、カスプ型とノード型の2タイプに分かれる
  • Singularな曲線は通常の楕円曲線と比べて、「つぶれた」単純な構造になっていて、群構造が単純になっている
    • それにより、より扱いやすい群への同型写像が定義できるようになる
• cusp カスプ型 -> y²=(x-a)³の形で表現できる
  • 尖っている楕円曲線　https://en.wikipedia.org/wiki/Cusp_%28singularity%29
  • どんなカスプ型楕円曲線も平行移動や線形変換でy²=x³の形になる
    • non-singular点が丁度p個存在し、Fpの加算群への効果的な写像がある
  • f: E/Fp → Fp+ という同型写像が常に存在。群同型になっている。尖端曲線上において、非特異点群は加法群と同型。
    • y²=x³のとき、f(x,y)=x/y, f(無限遠)=0という写像によってE/FpをFp+に（Fp上での加法群、Zmod(n)+と書いているものもある）変換できる
    • これにより、DLPが除算に変換可能
  • 手順
    1. Q=kGを解きたい
    2. q=ψ(Q), g=ψ(G)と写像変換する。これでFp+上に同型写像完了
    3. k=q/gするとkが求まる
  • idekctf 2025 - Sadness ECC Revenge https://giapppp.github.io/posts/idekctf-2025/
    • (y-1337)²=x³という楕円曲線が登場。この場合は並行移動しているため、f(x,y)=(y-1337)/3と同型写像する
      • なんで逆数になっているのかは不明。座標が反転しているためらしいが...不明
    • A, B, Cが曲線において一直線上に並ぶことに起因する関係式 A + B + C = 0 を方程式に変換するときに、そのままやると大変なのでSingularであることを生かして、それぞれZmod(n)+にA,B,Cをa,b,cに変換して a+b+c=0 として簡潔に方程式を作った
• node ノード型 -> y^2=(x-α)^2(x-β)と表現できる
  • 平行移動や線形変換でy²=x²(x-1)に変換する
    • p+1個かp-1個の点があるため、Fp²上での乗法群への効果的な写像がある
      • Fp²だと位数はp²-1でp²-1=(p+1)(p-1)で約数に持つため
    • 「節曲線上で、非特異点群は乗法群(GF(p), )と同型である」という説明も見た。GF(p)*って何だろう。*は×、乗法を指していそうだが... https://writeups.thebusfactoris1.online/posts/2025-07-28-FaultyCurve-writeup
      • この写像は、特異点における2本の接線の傾きを伴う。同型性は であるψ(P) = (y - m(x-x₀)) / (y + m(x-x₀))。
      • 手順
        1. 特異点見つける(x₀,y)
        2. mを解いて特異点における接線の傾きを求めますm² = 3x₀
        3. 新しい変換を適用すると、Q = flag * Gになりますψ(Q) = ψ(G)^flag。
        4. これで普通の離散対数問題に落ちたので、Sageの組み込み関数GF(p)をでflag = log(ψ(Q), ψ(G))とすれば解ける
  • E(Fp)上のECDLPをFp×のFFDLPに変換して解く
    1. αを計算する f = x^3 + a*x + bとしてf.factor()すると分かる
    2. (x,y)↦(x-α,y)と変換する
    3. するとy^2=x^2(x-s)となるsが得られる s=f_.factor()[0][0]-x
    4. この状態で同型写像が定義できる。f:E(Fp)→Fp×でf:(x,y)↦(y+x sqrt(s))/(y-x sqrt(s))
    5. 後はDLPする v.log(u)
    6. 上は何かうまく動かないので注意。なぜ...
  • GF(p)上でやるとp-1でPohlig-Hellmanだと思うが、p+1でPohlig-Hellmanもできるみたい
    • https://chocorusk.hatenablog.com/entry/2023/11/11/035738#crypto-Delta-Force だとp+1でPohlig-Hellmanしてる
  • https://blog.y011d4.com/20210801-crypto-ctf-writeup
    • y2=x^3^3x^2=(x+1)^2(x-2)のとき、ψ:(x,y)→{y+α(x+1)}/{y-α(x+1)}（ただし、α²=a）の写像によって、体Fp上の乗法群に移すことができる
    • 楕円曲線の位数ではなく、Fpのp-1を位数として計算が可能で、それをうまく使っている
• singular curve: 楕円曲線の判別式 Δを計算すると0の曲線
  • singularな楕円曲線には、nodeとcuspの2種類がある
  • Singular Curve Point Decompression Attack
  • https://chocorusk.hatenablog.com/entry/2023/11/11/035738
  • https://blog.y011d4.com/20210801-crypto-ctf-writeup#tiny-ecc
• Singular な曲線 Δ(E/Fp)=0 のとき、Fp+やFp×,Fp2×F上の DLP に帰着できる
• Singularな楕円曲線は準同型なほかの構造にうつして解ける
• 特異点を持つ楕円曲線は写像を通して FFDLP に落ちます。
• https://zenn.dev/anko/articles/ctf-crypto-ellipticcurve#%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9A%E4%B8%8A%E3%81%AB%E5%AD%98%E5%9C%A8%E3%81%97%E3%81%AA%E3%81%84%E7%82%B9%E3%82%84%E4%BD%8D%E6%95%B0%E3%81%AE%E5%B0%91%E3%81%AA%E3%81%84%E7%82%B9%E3%82%92%E6%8C%87%E5%AE%9A%E3%81%A7%E3%81%8D%E3%81%A6%E3%81%AF%E3%81%84%E3%81%91%E3%81%AA%E3%81%84-(invalid-curve-attack-%2F-small-subgroup-attack)
• Easy?? ECDLP
  • chocoruskさん: 楕円曲線の方程式とP,Qの座標がちょうどZ_pの元になるように(x',y')=(p^2x,p^3y)の変換をすると、modpで見たときに楕円曲線がsingularになる。cuspの場合は簡単、nodeの場合は位数がp²-1の約数になるので、p-1とp+1の素因数がどちらも小さくなるようにpを決めれば、secret modpが求まる。(SECCON 2023 Finals DLP4.0と同様)https://github.com/y011d4/my-ctf-challenges/tree/main/2023-SECCONCTF-Final/crypto/dlp-4.0/solution あとは同様にliftする。singularな楕円曲線の問題、楕円曲線が独自実装されてたりして丸わかりなことが多いけど、これはパッと見わからなくて面白かった
• nullcon HackIM 2019 Singular https://furutsuki.hatenablog.com/entry/2020/05/05/112207

Invalid Curve Attack / Small-Subgroup Attack

• 楕円曲線上であることを確認しないまま計算が行われると、別の楕円曲線上で計算されていることになり、想定よりも位数の少ない点を使ってしまうことがある
  • CodeGATE 2024 Baby Login
    • secp256r1: y²=x³-3x+0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b という楕円曲線上で計算しているつもりが、楕円曲線上にあることを確認しないまま計算することで、座標の計算にはy²=x³+ax+bの楕円曲線のaしか使われないため、別のbの楕円曲線上で計算が進んでしまうことになる
    • つまり、y²=x³-3x+b（bは[0,p)の任意の数）上で計算が進んでしまう
      • 任意の点を選ぶとbが決まるかというと、多分（というか大体？）Yesで、aが同じでbが異なる楕円曲線というのは上下の平行移動になるため、平行移動してその点に重なるbって2通りしかなさそう？（上側と下側）
    • よって、天下り的にbをランダムに選んで計算が移った先の楕円曲線を作って、そこからランダムな点を選び、更にtmp_E.gens()[0] * (tmp_n // tmp_p)みたいに「生成元×楕円曲線の位数÷求めたい素数位数」とやって点を求めることで、求めたい素数位数の点を見つけてくることができる
    • こうやって見つかった座標はaは共通しているがbは違うので元々の楕円曲線上には無く、また、Invalid Curve Attackで計算されたときに位数が小さくて便利という感じである
• https://github.com/ashutosh1206/Crypton/blob/master/Diffie-Hellman-Key-Exchange/Attack-Invalid-Curve-Point/README.md
• https://zenn.dev/kurenaif/articles/9cf509d9a15815
• 楕円曲線上に存在しない点や位数の少ない点を指定できるとき、さまざまな少ない位数の点を収集して中国剰余定理できる https://zenn.dev/anko/articles/ctf-crypto-ellipticcurve#%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9A%E4%B8%8A%E3%81%AB%E5%AD%98%E5%9C%A8%E3%81%97%E3%81%AA%E3%81%84%E7%82%B9%E3%82%84%E4%BD%8D%E6%95%B0%E3%81%AE%E5%B0%91%E3%81%AA%E3%81%84%E7%82%B9%E3%82%92%E6%8C%87%E5%AE%9A%E3%81%A7%E3%81%8D%E3%81%A6%E3%81%AF%E3%81%84%E3%81%91%E3%81%AA%E3%81%84-(invalid-curve-attack-%2F-small-subgroup-attack)
• tiramisu (Google CTF)
• Montgomery-Ladder Fault (Montgomery-Ladder法を用いて乗算処理を行う際, Invalid-curve Attackを用いて存在しない点に対して処理を行わせるとある別の楕円曲線での計算結果に帰着できる. もし, この曲線でPohlig-Hellman Attackのような別の攻撃を用いれる場合, ECDLPは間接的に解けてしまう. )
  • https://safecurves.cr.yp.to/twist.html の Invalid-curve attacks against ladders？
  • モンゴメリ曲線上にない入力xは、必ずねじれた曲線にあることが保証される
  • 別の楕円曲線はどうなんだろう
  • ねじれ曲線は E.quadratic_twist(d) で得られる
    • dの指定を省略するとランダムなねじれ曲線が得られる
    • dは非平方剰余な数で dy^2=x^3+Ax^2+x mod p が構築される
  • claudeによると...
    • 不正なxは全て単一のTwist曲線上に乗る
  • 別のねじれ曲線を用意するのではなく元の体を拡大することで解が存在する楕円曲線に移すことで解けたりする
    • GF(p)上で解が無いが、GF(p**2)上なら解が作れる
    • つまり、もともと E1 = EllipticCurve(GF(p), [a, b])であれば、 E2 = EllipticCurve(GF(p**2), [a, b])を楕円曲線として使うことで異なる位数上で同一の計算が行える
• TJCTF 2015 Curvature https://furutsuki.hatenablog.com/entry/2020/05/05/112207
• x座標だけを受け取って検証をしない場合は、x³+ax+bが平方剰余であればyが存在するので有効な点であり、非平方剰余であれば有効でない点になる
  • この有効でない点は、quadratic twist（2次ねじれ）の曲線E'上の点として振る舞い、#E(Fp)+#E'(Fp)=2p+2が成り立つ
    • quadratic twistはE.quadratic_twist()で得られる
  • https://cryptopals.com/sets/8/challenges/60.txt
• P256, P244
  • CodeGATE 2024 Baby Login https://blog.y011d4.com/20240602-codegate-writeup
    • golang 1.19未満ではelliptic.P256().ScalarMultが与えられた座標がP256の上にあるか検証してない
  • Google CTF 2021 TIRAMISU https://blog.y011d4.com/20210719-google-ctf-writeup#tiramisu

他、資料

• Weil-Descent Attack (有限体の n次拡大体の上の楕円曲線のECDLPをDLPへ帰着し, Index-calculus法を併用してECDLPを解く. )
• Xedni-Calculus法 (特定条件下の楕円曲線におけるIndex-Calculusの効率化. XedniはIndexの逆.)
• Yasuda-Attack (p進展開を利用したp進数体・有理数体におけるECDLP解法, 名前は特に付けられていないようなので発案者の安田氏の名前とした)
• Small-Subgroup Attack (位数の少ない点を指定し, それぞれについて何度も小さなECDLPを解き, 中国人剰余定理を用いてECDLPを解く. )
• https://elliptic-shiho.hatenablog.com/entry/2016/12/02/051931
• https://elliptic-shiho.hatenablog.com/entry/2016/07/20/084509
• https://tex2e.github.io/blog/crypto/DLP
• https://zenn.dev/anko/articles/ctf-crypto-ellipticcurve#pohlig-hellman
• https://github.com/elikaski/ECC_Attacks?tab=readme-ov-file#The-curve-is-supersingular

ECDH鍵共有: ECDH, 楕円ElGamal暗号

• ECDH鍵共有: ECDH
  1. 最初に、楕円曲線E/FpとベースポイントP ∈ E/Fpを作成し、共有する
  2. [Alice] 乱数aを用意して、aGを計算して、送る
  3. [Bob] 乱数bを用意して、bGを計算して、送る
  4. [Alice] 貰ったbGから、abGを計算する
  5. [Bob] 貰ったaGから、abGを計算する
  6. S=abGという共通鍵が生成できた
     • Sのx座標をハッシュ化して共通鍵とすることもある？
• 楕円ElGamal暗号
  1. [両者] ECDH鍵共有で共通鍵 abGを生成する
  2. [Alice] 送りたいメッセージ M を用意して、M+abGを計算して送る
  3. [Bob] 貰ったM+abGから-abGをしてMを復元する
  4. 楕円曲線のFp 有理点E(Fp)は巡回群 or 二つの巡回群の直積らしい https://mitsu1119.github.io/blog/p/%E7%BE%A4%E3%81%A7%E7%90%86%E8%A7%A3%E3%81%99%E3%82%8B-elgamal/

ECDSA署名

• 署名作成手順
  1. 楕円曲線のパラメタa,bを求める
     • 計算するときに使うmod pのpはもう決まった値があるっぽい
     • a,bはベストプラクティスがあるっぽい
     • ベースとなる座標Gを決める
       • 圧縮方式ではx座標しか書かれていないし、非圧縮方式ではy座標も書いてある
       • 確かにx座標があればy座標は2択まで絞れるな
     • ベースポイントの位数nを求める
       • 0 = nGとなるn
  2. 秘密鍵d（整数）をランダムに決める
     • 乱数でn以下の数字で決める
  3. Q = dGを求める
     • 繰り返し二乗法が使える
  4. nonceのkをランダムに決める（秘密鍵dは共通だが、kは毎回作り直す？）
  5. r := kGのx座標を求める (mod n?)
  6. s := (h(m) + rd) / k mod nを求める
  7. (r,s)が署名値で(G,Q)が公開鍵
     • このとき、1≦r,s＜nになっているはずなので、署名値はこれを満たしているか検証する必要がある
       • 検証しなかった脆弱性が CVE-2022-21449 https://blog.y011d4.com/20221011-cyber-security-rumble-writeup
• 検証手順
  • (h(m)/s)G + (r/s)Qのx座標はrかどうかを判定する(mod n?)
• Polynonce: An ECDSA Attack and Polynomial Dance
  • https://media.defcon.org/DEF%20CON%2031/DEF%20CON%2031%20presentations/Nils%20Amiet%20Marco%20Macchetti%20-%20Polynonce%20An%20ECDSA%20Attack%20and%20Polynomial%20Dance.pdf
  • https://eprint.iacr.org/2023/305.pdf
  • nonceがLCGのような単純なものが使われているとき、また、N個の署名を集め、N個のnonceが最大N-3次帰納関係に従っている場合はECDSAに対してキー回復攻撃が実行可能であるらしい https://research.kudelskisecurity.com/2023/03/06/polynonce-a-tale-of-a-novel-ecdsa-attack-and-bitcoin-tears/

攻撃手法

https://furutsuki.hatenablog.com/entry/2020/05/05/112207 https://eprint.iacr.org/2023/305.pdf

• dが漏洩すれば、どんな平文でも署名を偽造可能
• kが分かるとdが計算可能 d = (sk - h)/r mod n
  • 署名の手順6がs = (h(m) + rd) / k mod nで、未知数がdのみになり、dを計算可能になる
• kが使いまわされていると復元可能 / nonce再利用攻撃
  • kが共通な2つの署名付きメッセージが手に入るとkが得られるk = (h1 - h2)/(s1 - s2) mod n
  • Crypto failures in the wild
• 位数n
• invalid curve attack
  • Maple CTF 2022 Writeup - Satoooonの物置
• 楕円曲線の位数が素因数分解できる場合に、Pohlig-Hellman attackができるよ、という問題です。この問題も楕円曲線のパラメータbを求めるステップがあり、PolynomialRingのrootsで殴ります
• Biased Nonce Sense Lattice Attack https://www.youtube.com/watch?v=6ssTlSSIJQE
  • 生成されるkが小さい場合に複数の署名を収集することでdをLLLで計算できるかも
    • h1/s1 = - r1/s1 * d + k1 mod nであり既知部分をA1,B1として整理するとA1 = B1 * d + k1 mod nとなる
    • これを複数個用意して、LLLを使ってApproximate-GCD問題を解くことでdが求まる？
      • 資料のYoutubeではCVPに帰着させて解いていた
  • kの大きさと必要サンプル
    • (#samples,log|k|) = (2,128), (3,170), (4,190), (20,242), (40,248)
  • Nonceがbiasedであればkの不明箇所のサイズを下げることができ、LLLで解けるようになる
    • Shared unknown prefixes：k1-k2を計算することで共通しているprefixが消えてサイズが小さくなる
    • Shared unknown suffixes: 上とほぼ同様であり(k1-k2)/2^-tを計算する
  • k,dが小さいとHidden Number Problemに帰着させ、LLLで解ける
    • https://blog.y011d4.com/20210321-line-ctf-writeup
    • https://furutsuki.hatenablog.com/entry/2021/03/21/101039
  • kの一部が分かっているとHNPに帰着できる
    • https://eprint.iacr.org/2019/023.pdf
    • SECCON CTF - Sign Wars
      • https://project-euphoria.dev/blog/29-seccon-2021/#sign-wars
      • https://blog.y011d4.com/20211212-seccon-writeup#sign-wars
• CVE-2020-0601 Qが未検証だったた生じた脆弱性で自由に動かすことができ、Q=Gにすることができた
  • https://qiita.com/melonattacker/items/5451d967ae02a1d66f53#crypto-origin
• CVE-2024-31497
  • PuTTYにおいてP-521のECDSA鍵を使っていると乱数の偏りが原因で、署名を60個程度集めれば秘密鍵が復元できてしまう
  • P-521は名前の通り法に521ビットの素数を使うわけですが、当時のPuTTYはkの生成にSHA512を使っていて、つまり、521ビットに対して512ビットのkを使っていて差分の9ビットは常に0になる
  • PoC https://github.com/HugoBond/CVE-2024-31497-POC
• PREDICTING THE ELLIPTIC CURVE CONGRUENTIAL GENERATOR https://arxiv.org/pdf/1609.03305
  • https://connor-mccartney.github.io/cryptography/ecc/PrivateCurve-0xl4ughCTF2024
  • P=G*flagで、P, P+G, P+2G, ..., P+6Gのx座標が与えられたときにflagが復元できる

他メモ

• RSA+ECC https://ce-automne.github.io/2019/12/22/Watevr-CTF-2019-Crypto-WriteUp/
• よくわからん多次元の何かが実はECで、色々やると解けるみたいな問題 https://hxp.io/blog/110/hxp-38C3-CTF-alcoholic_variety-writeup/
  • https://affine.group/writeup/2024-12-hxp-AlcoholicVariety
• Dual EC DRBG: 楕円曲線暗号を用いて実装されたCSPRNG
  • 2006にNISTの標準規格として採用されたが、2014年には削除されている。バックドアがあったため
  • UTCTF 2021 Sleeves https://ctftime.org/writeup/26410
• 楕円曲線LCG: 安全でないので使ってはいけない
  • RCTF 2022 - IS_THIS_LCG? https://ctftime.org/writeup/36034

楕円ペアリング

• ペアリング：楕円曲線上で定義される関数であり，楕円曲線上の 2点を入力とし，ある有限体の元を出力とする双線形関数 https://sehermitage.web.fc2.com/cmath/pairing_1.html
  • 抽象的には e:G1×G1 → Gr の写像のうち 双線型性 と 非退化性 の両方を満たす写像をペアリングという
    • G1: Zp上の楕円曲線 E:y²=x³+ax+b 上の有理点の集合は群となりGとしたとき、その部分群で位数が素数qとなるもの
    • Gr: GP(p^k)の位数が素数qの部分群。kはq|(p^i-1)となる最小の正整数
    • 双線型性 e(aP,bQ)=e(P,Q)^(ab)を満たす
      • https://people.csail.mit.edu/alinush/6.857-spring-2015/papers/bilinear-maps.pdf
      • https://blog.tanglee.top/2024/08/24/Intro-to-Bilinear-Map.html
    • 非退化性 e(P,P)!=1となるPが存在する
  • Weilペアリング em(P,Q) ペアリング暗号において最初に用いられたペアリングの1つで計算量が非常に大きい
    • e: E[m]×E[m]→μm: m-ねじれ群のとある点同士を入れるとmの乗法巡回群が得られる
    • とある点P, Qがあり、P=kQであることを確かめたいときに、em(P,Q)=1であることを判定するというやり方がある https://furutsuki.hatenablog.com/entry/2024/09/15/201136#A-Dance-of-Add-and-Mul
      • これは、em(P,P)=1, ∀P∈E[m]と、em(kP,Q)=em(P,kQ)=em(P,Q)^kから言える
    • sagemathで計算するときは G1.weil_pairing(R, o1) のようにする
      • o1はG1の位数であるが、https://yu212.hatenablog.com/entry/2024/09/15/180420 だと、r = 0x5f19672fdf76ce50d28e776116d47d5841f8c5f1fba8d33881bfa40089fc5bffd1ffffff00010001と定数を使っていた。何なのかよく分からない
  • Tateペアリング: Weilペアリングよりも計算効率の高い双線形写像
  • Ateペアリング: Tateペアリングを改良し、計算効率がよりよい
  • BN(:Barreto-Naehrig)ペアリング: Barreto-Naehrig 曲線と呼ばれる特定の種類の楕円曲線上で定義される特別な種類のペアリング
  • ペアリング全体で満たす性質
    • e(P,aQ+bQ)=e(P,aQ)e(P,bQ)
    • e(aP+bP,Q)=e(aP,Q)e(bP,Q)
    • e(P,Q+R)=e(P,Q)e(P,R)
    • e(P+Q,R)=e(P,R)e(Q,R)
• ペアリングはそもそもPairing Friendly Curveでしか使えない
  • Pairing Friendly Curve: 埋め込み次数が小さい（6以下？）。逆に埋め込み次数が小さいと必ずペアリングが定義できる？
• BN254: Barreto-Naehrig曲線の一種で、ペアリングベース暗号に特化した楕円曲線
  • y²=x³+3（有限体Fp上）
    • 素数p = 36u⁴ + 36u³ + 24u² + 6u + 1 ここで u = 4965661367192848881
  • ペアリング構造 e: G1×G2 -> GT
    • G1: y²=x³+3（有限体Fp上）上の点の部分群
      • 大きな素数rを位数に持つ巡回群を使う。そのための生成元Gは標準的に選ばれたものがある
    • G2: ツイスト曲線上の点（FQ2拡張体）
      • Fp²上の楕円曲線のツイスト曲線上の点
        • G1を拡張体Fp²に持ち上げると、点の数が足りない問題が起きる。そこで使うのがツイスト曲線。y² = x³ + 3/ξ （Fp²上）
        • ξ（クサイ）は拡張体Fp²の特別な元
      • G1と同じ位数rを持ち、標準的な生成元がある
      • G2として使われるのはツイスト曲線上の部分群になる
        • よって、部分群として適したものを使わないとペアリングの性質が破れる
        • Alpacahack Round 13 - Jerr0-day https://soon.haari.me/alpacahack-round-13/
          • 公式解説では適さない点を探すのに曲線上のランダムな点を取得してペアリングが成立するかを角印することでガチャっている
    • GT: FQ12拡張体（ペアリング結果）
  • 性質
    • 双線形性
      • e(aP, bQ)=e(P,Q)^ab
      • e(P1+P2,Q)=e(P1,Q)×e(P2,Q)
      • e(P,Q1+Q2)=e(P,Q1)×e(P,Q2)
    • 非縮退性
      • G1,G2の生成元P,Qに対してe(P,Q)≠1
• ペアリングを理解するには因子 divisor という概念を理解する必要があるらしい https://zenn.dev/anko/articles/ctf-crypto-ellipticcurve#supersingular-%E3%81%AA%E6%9B%B2%E7%B7%9A%E3%82%92%E7%94%A8%E3%81%84%E3%81%A6%E3%81%AF%E3%81%AA%E3%82%89%E3%81%AA%E3%81%84-(mov-%2F-fr-reduction)
• ペアリングがどう使えるか？
  • 楕円曲線上の離散対数問題 Q=aPについて、ペアリングを計算したとき、e(P,Q)=e(P,aP)=e(P,P)^aとなり、普通の離散対数問題に帰着させられる
• 楕円曲線を使った鍵共有方式 https://crypto-writeup-public.hatenablog.com/entry/%25E3%2583%259A%25E3%2582%25A2%25E3%2583%25AA%25E3%2583%25B3%25E3%2582%25B0
• https://project-euphoria.dev/blog/36-pairing/
• https://zenn.dev/anko/articles/ctf-crypto-ellipticcurve
• https://zenn.dev/anko/articles/ctf-crypto-ellipticcurve
• 転用
  • 鍵共有 ID-NIKS
  • 公開鍵暗号 BF方式、SK方式
  • 署名 短い署名、グループ署名
  • ECDDHP: 楕円曲線上の楕円曲線決定Diffie-Hellman問題、安全じゃないっぽい？
• 資料 https://static1.squarespace.com/static/5fdbb09f31d71c1227082339/t/5ff394720493bd28278889c6/1609798774687/PairingsForBeginners.pdf
• https://ptr-yudai.hatenablog.com/entry/2023/03/11/233340#mitsu-%E3%83%8D%E3%82%B3%E3%81%A1%E3%82%83%E3%82%93%E5%BC%8F%E5%AE%89%E5%85%A8%E3%81%AA%E6%9B%B2%E7%B7%9A%E3%81%AE%E7%94%9F%E6%88%90

モンゴメリー曲線 Montgomery

• y^2=x^3+Ax^2+x
  • Aはモンゴメリ係数
  • sagemathだと EllipticCurve(F, [0, A, 0, 1, 0])
• wikipediaではBy^2=x^3+Ax^2+xとして、パラメタをA,B（B(A^2-4)≠0を満たす）だった
• 単一座標系を持つ。つまり、座標はx座標のみで表現される。yは無視される
  • これにより効率的なスカラー倍演算が可能になる
• モンゴメリー座標 P = (X:Z)
  • アフィン空間での座標(x,y)に対してx=X/ZとなるようにX,Zを取り、モンゴメリー座標 P=(X:Z) で表すことができる
    • 変換方法は色々ありそうだが、P(x,y) → P(x:1)
  • モンゴメリー座標に変換して計算することでy座標が無くても高速に計算が可能になる
• モンゴメリ曲線とツイステッドエドワーズ曲線とは双有理同値

超楕円曲線暗号

• 超楕円曲線 hyperelliptic curve とは y²=f(x) の代数曲線のこと
• 曲線の種数 g
  • f(x)の次数からを求めることができる。具体的には 次数 2g+1と2g+2の多項式で定義される超楕円曲線は種数g
  • つまり3次,4次ならg=1で種別1の楕円曲線（正確には特別な一点を付加する）。つまり、1＜gなら超楕円曲線
  • 次数が 2g + 1 のとき、虚超楕円曲線 imaginary hyperelliptic curve
  • 次数が 2g + 2 のとき、実超楕円曲線 real hyperelliptic curve
  • genus = floor((f.degree()-1) / 2)こんな感じに計算してたら種数を計算している
  • gは穴の数を表す位相的不変量。曲線のリーマン面における「穴」の数（楕円曲線はトーラスなのでg=1なのか）
• Mumford表現: 超楕円曲線での点の表現。多項式のペア (U,V)
  • U: 次数≦gのモニックな多項式
  • V: Uを法とした剰余
  • https://mitsu1119.github.io/blog/p/%E8%B6%85%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9A%E6%9A%97%E5%8F%B7%E3%82%92%E7%90%86%E8%A7%A3%E3%81%99%E3%82%8B%E3%81%9E/#mumford-%E8%A1%A8%E7%8F%BE
    • 楕円曲線では点で群を成せたが、超楕円曲線では点のタプル的なものを使うが、それを多項式で表現したもの
    • Harley加算などの高速な加算アルゴリズムも見つかり、計算機的にも嬉しい
    • 直線は曲線と5点で交わるため、楕円曲線に通常適用する通常の方法は使えません。なぜなら、選択できる点が多数あるからです。これを克服するために、単一の点ではなく、因子と呼ばれる小さな点のペアを用います。これらのペアは、曲線のヤコビアンとして知られる整然としたアーベル群を形成します。大まかに言えば、2つの点が直線を決定し、その直線を曲線に代入すると、もう一つの交点を与え、それを折り返して次数を小さく保つ。これはカントールのアルゴリズムと呼ばれる https://people.cs.nycu.edu.tw/~rjchen/ECC2012S/Elliptic%20Curves%20Number%20Theory%20And%20Cryptography%202n.pdf の13.3章
  • これを使うと、f(x) = v(x)² mod u(x) が成立するらしい
    • idekCTF 2025 - Happy ECC Revenge https://giapppp.github.io/posts/idekctf-2025/
      • 点をいくつか入手してf(x) = v(x)^2 mod u(x)を複数手に入れて、CRTするとf(x)が復元できる
      • CRTは多項式環でも使える
        • ラグランジュ補間でも行ける？（わからん）
• 曲線の位数は約 p^g (pは体の大きさ)
• 種数2の超楕円曲線の位数計算の方法 -> https://giapppp.github.io/posts/idekctf-2025/
• mitsuさんのどでか資料 https://mitsu1119.github.io/blog/p/%E8%B6%85%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9A%E6%9A%97%E5%8F%B7%E3%82%92%E7%90%86%E8%A7%A3%E3%81%99%E3%82%8B%E3%81%9E/
• https://www.iisec.ac.jp/proc/vol0002/iisec_proc_002_p043.pdf

同種写像 isogeny

https://mitsu1119.github.io/blog/p/%E3%82%BB%E3%82%AD%E3%83%A5%E3%83%AA%E3%83%86%E3%82%A3%E3%82%AD%E3%83%A3%E3%83%B3%E3%83%97%E5%BF%9C%E5%8B%9F%E8%AA%B2%E9%A1%8C%E6%99%92%E3%81%97-2023-l1-%E6%9A%97%E5%8F%B7%E5%8C%96%E9%80%9A%E4%BF%A1%E3%82%BC%E3%83%9F/ https://project-euphoria.dev/blog/35-yoshicamp-2022-winter-sidh/ https://giapppp.notion.site/Isogeny-based-cryptography-aec3e90af4d14ca1a3db8be7ffd0794a

• 同種写像 isogeny
  • 楕円曲線の写像Φ:E→E'において、以下を満たすものを同種写像という。以下を満たせば準同型写像らしい
    • 有理関数で表すことができる
    • 全射
    • Φ(OE)=OE'
  • E1, E2を楕円曲線とする。有理多項式で表せる群準同型写像f:E1→E2を同種写像と呼ぶ。また、このとき、E1とE2は同種であるという
    • 同種写像には次数が定義され、n次の同種写像のことをn-同種写像という（しばしば、素数n次の同種写像を考える）
  • n-同種写像f:E1→E2があるとき、f':E2→E1であって、f'○f=[n]なるものが唯一存在し、これをfの双対同種写像という
  • 楕円曲線E1とE2がFq上同種であること ⇔ #E1(Fq) = #E2(Fq)
  • 同種写像の例
    • 楕円曲線E上のスカラー倍 [n]:E→E;P↦nP n²-同種写像
  • Kernel 核 ker(Φ)
    • ker(Φ) = {P∈E|Φ(P)=0} 同種写像Φ:E→E'を考えるとき、Φによって無限遠点（単位元）に写る点の集合
    • ちなみに、kernelは群などに適用されるもの -> cry-math-.md
• 同種写像暗号 / Isogeny型の暗号 https://joint.imi.kyushu-u.ac.jp/wp-content/uploads/2022/08/220802_03aikawa.pdf
  • Alice (E,Φ) を定義
    • Eは楕円曲線で、公開情報
    • Φは同種写像で、秘密情報
  • Bob (E,Φ(E)) を定義
    • Φ(E)は同種写像の像となる曲線で、公開情報
  • （一般）超特異同種写像問題: 同種な超特異楕円曲線 E1 と E2 が与えられたとき、同種写像 f:E1 → E2 を求めよ
    • この問題の困難性を背景とした暗号
  • 超特異同種写像グラフを利用する
    • CGL-ハッシュ関数
    • SIDH鍵共有
    • SQISign署名 https://joint.imi.kyushu-u.ac.jp/wp-content/uploads/2022/08/220802_05onuki.pdf
  • アーベル多様体の同種写像グラフ
    • CGL-ハッシュの類似
    • グラフの局所的な記述や拡張性の研究 などなど
  • イデアル類群の群作用を利用する
    • CRS鍵共有: 通常曲線を利用し、実装性を伴わない
    • CSIDH鍵共有: 超特異曲線を利用し、効率的な方式
      • CSI-FiSh: CSIDHベースのデジタル署名
      • SiGamal, SimS: CSIDHベースの暗号化
  • 楕円曲線とその同種写像を用いた方式
  • 2022年7月にCastryckとDecruにより、同種写像暗号の1つであるSIKEに対する攻撃が示された
  • 同種写像計算問題の困難性を利用

• 資料

  • https://joint.imi.kyushu-u.ac.jp/wp-content/uploads/2022/08/220802_03aikawa.pdf
  • https://lazzzaro.github.io/2022/12/16/crypto-%E5%90%8E%E9%87%8F%E5%AD%90%E5%AF%86%E7%A0%81/

• 同型 isomorphic

  • ある体K上の2つの楕円曲線が本質的に同じ構造を持つ、正確にはある体K上の2つの楕円曲線E1, E2にK上の以下の条件を満たす準同型写像 Φ:E1→E2が存在するとき、E1とE2は同型であると言う
    1. 可逆である：Φに対する、双対の写像が存在する
    2. 群構造の保存：Φは加法群構造を保つ、つまり、楕円曲線上の点の加法を保つ
    3. 代数的な性質の保持：Φは有理関数（座標が有理数で表される）であり、その逆写像も有理関数
  • Weierstrass標準形ではΦ:(x,y)→(u^2x+r,u^3y+s)とすると同型に変換可能
    • Φ:x→λxも同型になる？書き方が分からんがΦ:(x,y)→(λ^2x,λ^3y)と同じな気がする https://github.com/Sarkoxed/ctf-writeups/blob/master/trx-2025/magic_curves/solve.py
  • 同型に関する性質
    • Eのj-不変量jE = 1728 * 4a^3 / (4a^3 + 27b^2)とすると、E1とE2が同型であることと、jE1=jE2は同値
    • 同型な楕円曲線は基本的な性質が同じのため、暗号観点ではセキュリティ強度が同じと考えられる。つまり、とある楕円曲線をより簡潔な同型の楕円曲線に変換することで、強度を保ちつつ計算を簡略化可能
      • 群構造: 楕円曲線上の点の加法が同じ形で保たれる
      • 位数や位数分布: 有限体上の点の個数（#E(Fp)など）が一致する
      • トーション部分群: ねじれ部分群（有限位数の点の集合）が一致する
      • ランク（有理点の自由部分の次元）: 有理点のランクも不変
    • ある曲線と同型なMontgomery曲線やEdwards曲線に変換することもできるっぽい
• 同種写像暗号の歴史 https://csidh.isogeny.org/index.html
  • Couveignes-Rostovtsev-Stolbunov方式: 1997年 Couveignesが提案した素体Fq上での通常の楕円曲線上で、同型写像をしてDHするもの
    • 2004年にRostovtsevとStolbunovにより独立に再発見された
    • これは2010年に、アーベル隠れシフト問題の例を解くことに相当するため、時間計算量がLqの量子アルゴリズムが存在することが示された https://arxiv.org/abs/1012.4019
  • SIDH: Supersingular Isogeny Diffie–Hellman
    • 2011年に自己準同型性の完全な環が四元数代数の順序である超特異楕円曲線を仕様した同方式のDHを提唱（と書いたが、ただ単に置き換えただけのものではないらしい）
      • SIDHをカプセル化（つまりは基盤とした）したSIKEというのもある
    • 2022年7月 深刻な鍵復元攻撃が提唱された https://k-nomoto1728.github.io/homepage/pdf/research/CSS2022.pdf
      • https://joint.imi.kyushu-u.ac.jp/wp-content/uploads/2022/08/220804_03onuki-.pdf
  • CSIDH
  • SQISign

SIDH

• SIDH
  • 耐量子性が期待されていた、鍵交換プロトコル
  • supersinglarな楕円曲線間の同種写像によって構成
    • 多分間違っているが概念的理解 → 楕円曲線EをAliceが持っている同種写像φAとBobが持っている同種写像φBがあって、j-不変量がφA〇φB(E)とφB〇φA(E)で一致するので、これを共通鍵にするDHで鍵交換
  • 多分ここが最も詳しい https://project-euphoria.dev/blog/35-yoshicamp-2022-winter-sidh/
  • GPST Attack
• https://triodelzx.github.io/2025/02/26/%E5%90%8C%E6%BA%90%EF%BC%881%EF%BC%89%E2%80%94%E2%80%94SIDH/
• https://triodelzx.github.io/2025/03/03/%E5%90%8C%E6%BA%90%EF%BC%882%EF%BC%89%E2%80%94%E2%80%94SIDH%E9%80%9A%E8%A7%A3/
• https://ptr-yudai.hatenablog.com/entry/2022/12/13/235034#theoremoon-%E7%8C%AB%E3%81%A8%E5%AD%A6%E3%81%B6%E5%90%8C%E7%A8%AE%E5%86%99%E5%83%8F%E6%9A%97%E5%8F%B7
• 2022年に完全に破られたらしい https://triodelzx.github.io/2025/02/26/%E5%90%8C%E6%BA%90%EF%BC%881%EF%BC%89%E2%80%94%E2%80%94SIDH/

CSIDH

• CSIDH: 虚⼆次体のorder Oに付随するイデアル類群の, ある超特異楕円曲線のFp-同型類の集合ℰℓℓp(O)への作⽤に基づく鍵共有⽅式
  • 有限可換群の超特異楕円曲線の同型類の集合への作用 [15] に基づいた同種写像暗号の鍵共有方式
    • 問題の困難性は、同型性発見問題に依存する
  • 超特異楕円曲線
    • Montgomery曲線っぽい？わからん
    • Edwards曲線を利用したCSIDH https://www.i.u-tokyo.ac.jp/edu/course/mi/master/2019/a/moriya.pdf
    • Hesse曲線を利用したCSIDH https://k-nomoto1728.github.io/homepage/pdf/research/CSS2022.pdf
    • 超特異楕円曲線
      • 超特異楕円曲線は楕円曲線全体と比較すると，指数関数的に数が少なく，ランダムな楕円曲線は現実的なスケールでは超特異楕円曲線にはなり得ない．既に超特異楕円曲線だと知られている特殊な楕円曲線も存在しているが，これらの特殊な楕円曲線を使ったプロトコルは脆弱性があることがわかっている．したがって，脆弱性のないような超特異楕円曲線を生成する手法が求められている
      • 作成手法
        • CGLハッシュ関数を用いてランダムな超特異楕円曲線を生成する
        • G-SIDH: グループ鍵共有方式であり、複数人の共有鍵を組み合わせることで超特異楕円曲線が生成できる
  • 資料
    • https://joint.imi.kyushu-u.ac.jp/wp-content/uploads/2022/08/220802_04moriya.pdf
• SIKE: SIDHのKey Encapsulation　https://speakerdeck.com/mitsu1119/castryck-decru-attack-nitiyotutohong-retemiru
  • 使う曲線は固定
    • NIST Round1: y² = x³+x
    • NIST Round 2..: y² = x³ + 6x² + x
• 実装
  • y011d4さん https://gist.github.com/y011d4/7b93a01f37c66aee2c27fd732126958a

CTF

• N1CTF - Seashells
  • https://github.com/hash-hash/My-CTF-Challenges/tree/main/n1ctf%202024/Seashells
  • https://magicfrank00.github.io/writeups/writeups/n1ctf2024/seashells/
• TRX2025 - Lepton2
  • https://github.com/Sarkoxed/ctf-writeups/tree/master/trx-2025/lepton2
  • Kernelを使った問題で良い感じにisogenyで変換すると、条件によって入力を単位元になったり、ならなかったりして、単位元になるときは.xy()を呼ぶと例外が発生するのでそれをオラクルとして良い感じに復元する
  • https://magicfrank00.github.io/writeups/writeups/trxctf/trxctf-crypto/#lepton2---writeup
• 0CTF 2024 - ZKPQC1
  • ker_phi.codomain()とEAのj-invariantが一致するようなkernelで、weil pairingが互いに1でない（1次独立な）ものを3つ見つけるところが問題
  • 2-isogenyでy²=x³-xに移して(x,y)->(-x,iy)することで、y²=x³+6x²+x上で2i倍写像が作れる（これ https://eprint.iacr.org/2020/439 の4.1）
  • E0->EAのkernelをKとしたとき、[i]Kと[1+i]Kをkernelとするisogenyも高確率でcodomainが同じj-invariantになった（謎）
• TSG Live CTF 14
  • https://github.com/tsg-ut/tsg-live-ctf-14/tree/main/crypto/saiku
  • https://github.com/tsg-ut/tsg-live-ctf-14/tree/main/crypto/gikou

巻末資料

• 読んだ入門資料
  • オススメ
    • ankoさんまとめ https://zenn.dev/anko/articles/ctf-crypto-ellipticcurve
    • furutsukiさんまとめ https://furutsuki.hatenablog.com/entry/2021/03/16/095021#%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9A%E6%9A%97%E5%8F%B7
• https://note.com/kokeshim0chi
• https://leonahioki.medium.com/%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9A%E3%81%AE%E5%A4%A2%E3%81%AE%E5%9B%BD%E3%81%AB%E4%BD%8F%E3%82%82%E3%81%86-12dcc675995a
• https://qiita.com/kobae964/items/e3927b57f1bf91f4caf6?utm_campaign=post_article&utm_medium=twitter&utm_source=twitter_share
• https://www.youtube.com/watch?v=jxmN8LqyTR4
• https://furutsuki.hatenablog.com/entry/2021/03/16/095021#%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9A%E6%9A%97%E5%8F%B7
• https://furutsuki.hatenablog.com/entry/2020/05/05/112207#ptr-yudai%E3%81%AE%E7%99%BA%E8%A1%A8
• https://zenn.dev/anko/articles/ctf-crypto-ellipticcurve
• https://qiita.com/rinr0q/items/c1180bf2bc8ab9c7e62e
• https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1814-10.pdf
• kurenaifさんオススメ本 https://www.amazon.co.jp/dp/462106343X/ref=cm_sw_r_tw_dp_CSSMANPTYEESMYPKW6TG
• kurenaifさんオススメ本 https://www.amazon.co.jp/dp/4621064533/ref=cm_sw_r_tw_dp_M9RBNDZYSFAMRXXK95BW
• http://www4.math.sci.osaka-u.ac.jp/~ogawa/documents/papers/1997SummerSchool/ellcur.pdf
• http://mathweb.sc.niigata-u.ac.jp/~hoshi/WatanabeNiigataMasterThesisSlide2024.pdf
• https://github.com/jvdsn/crypto-attacks/tree/master/attacks/ecc
• https://www.cryptrec.go.jp/exreport/cryptrec-ex-3001-2020.pdf
• https://safecurves.cr.yp.to/equation.html
• yoshi-campの同種写像暗号回 https://ptr-yudai.hatenablog.com/entry/2022/12/13/235034#theoremoon-%E7%8C%AB%E3%81%A8%E5%AD%A6%E3%81%B6%E5%90%8C%E7%A8%AE%E5%86%99%E5%83%8F%E6%9A%97%E5%8F%B7