この記事は CTF Advent Calendar 2016 - Adventar の22日目の記事です. 21日目の記事は@nolzeさんの どのCTFに出たらいいか分からない人のためのCTF年表 (2016年版) - A602 です. 多表式暗号の解読ではカシスキー・テストを用いた解読法がよく知られているが…

Exhaustive Search法 いわゆる全探索法であり, 力任せな方法. 与えられる楕円曲線$E$とその上の点$P$, $Q$について$m = \#P$とする. この時, ECDLPの解$d$は$1 \leq d \leq m $の不等式を満たす. このため, この$d$の範囲を全て計算してみることでECDLPは解…

楕円曲線離散対数問題(Elliptic Curve Discrete Logarithm Problem, 以下ECDLP)が解けるか否か, という問題は暗号理論において楕円曲線が用いられる際の安全性基準として一般的である. 本記事から數回に分けてECDLPに対する攻撃手法についてまとめる. ECDLP…

Miller Algorithmの実装を高速化した際のメモ。 Miller Algorithmは基本紹介される際にはEuclid空間上の楕円曲線の点について紹介されるが、変数変換をしてやることで射影座標上のアルゴリズムとすることが出来る。(なお、Miller Algorithm自体は任意の種数…

$\def\O{\mathcal{O}}$ ここでは標数2, 3の体は考えないため, 全ての楕円曲線はWeierstrass標準形 $y ^ 2 = x ^ 3+ax+b$ で表せるとする. また, 楕円曲線上の点 $P$ の $x$ 座標を $x(P)$ , $y$ 座標を $y(P)$ と表す. 位数2の点 複素数体上の楕円曲線 $y ^ …

本記事では中国剰余定理(Chinese Reminder Theorem, CRT)1について解説する. 数学的な定義や意義について触れた後, 応用例としてRSA-CRT, Multi-Prime RSA, そしてPohlig-Hellman Attackについて述べる. 前提知識として, 簡単な初等整数論・群・環の言葉を知…