./VespiaryからXornetさんとネコチャンを招き、例年以上の盛り上がりを見せるyoshicamp。芦ノ湖を見下ろしながら始まったキャンプだったが、久々ということで気合が入っていたのか、私の同種写像暗号の講義もptr-yudaiの量子の講義も時間内には終わらなかった! コンビニのおかずと冷凍餃子を食べてボードゲームを遊び1日目を終えて、2日目朝〜の講義はmitsuくんによる「ネコちゃん式-~安全な楕円曲線の生成~」です。
他の人のyoshicampレポートは https://yoshicamp.zer0pts.com/ をご覧ください
前日結構ハードに体力を使った割にはそこそこ早起きできた。ptr-yudaiは先に起きていたっぽい。朝ゴハンのパンをかじりながら外を眺めていたら、芦ノ湖の向こう側に富士山が見えることに気がついた。雲のない開放的な空に堂々とそびえていてかっこよかった。白状するとこのタイミングまで富士山があることに気がついてなかったです。
それはそれとして8:30 頃にはmitsuくんがやってきて、9時か9時半ごろには講義がぬるりと始まった。
暗号で楕円曲線を用いるにあたって楕円曲線の位数というのは重要な指標で、適当に楕円曲線を生成してしまうと性質の悪い(例えばECDLPが簡単に解ける)位数を持ってしまうことがある。そうならないように、暗号プロトコルで楕円曲線を利用するときはその曲線の位数を確かめておこう。ところで楕円曲線の位数をどうやって求めるかというと……というのが前説。
まずはSchoofのアルゴリズムを用いて位数を計算する方法が紹介された。Schoofのアルゴリズム自体は位数ではなくFrobenius写像のトレースを計算するアルゴリズムだが、標数の楕円曲線の位数とFrobenius写像のトレースの間には次のような関係が成り立つことが知られている。
すなわち、がわかればから楕円曲線の位数が計算可能である。
Frobenius写像はと定義される自己準同型写像で、なんか口頭で補足されていた感じだと行列表示みたいなのと対応付けられるらしく、特性多項式やトレースが定義できるということだった。その特性多項式とは であり、ここにトレースが登場する。ケイリー・ハミルトンの定理よりなので、具体的な点を代入して移項してを解けば良いということだったが、ここでケイリー・ハミルトンの定理が出てきた理由はちゃんとはわかっていない。
とにかく、
を満たすようなこそが今求めたいである。そしてこれを効率的に求める方法の一つがSchoofのアルゴリズムである。
Schoofのアルゴリズムでは小さい素数を用いて-torsion pointを考えるということにして、の代わりにを満たすを全探索したあとで中国剰余定理を用いてを復元するという方法を取る*1。
-torsion point *2を考えているということはは必ず-division polynomial についてを満たすから、はが生成するイデアルによる剰余類環上の式と思って良い。これによって、実装中に登場する、 のような指数が大きくなりうる項の次数を以下に抑えることができる。さらにと置けば、とに置き換えることでの項についても次数を抑えることができる。
ここまでを整理すると、Schoofのアルゴリズムでは次の手順で楕円曲線におけるFrobenius trace が計算でき、を用いて位数を計算できる。
以上をSageで実装したものがこちら。
y座標については常になので常に暗黙のがかかっているということにして実装に明にを登場させていないのが工夫ポイント。そのほか、説明に登場したとおりに剰余環を定義してその上で演算を行っていたり、剰余環上の(symbolicな=xをxのまま扱う)楕円曲線演算を実装していたり、上に逆元が存在しない要素を引いたときはそのをスキップする処理を実装したりしている。また、講義ではdivision polynomialを求める部分についても扱ったので自前実装している(Sageにも実装されているのでそちらを使うこともできる)
……というのを実装しようとしていたが13時を回ってしまいタイムオーバー*4。山を降りて芦ノ湖周辺のご飯屋さんへ。観光地だけあってこの時間は賑わっていた。適当な街の食堂? みたいな店に入ってご飯を食べたが、注文したカツカレーの量が多くて大変だった。重たいお腹を抱えて山を登り午後の講義に入る。これについてはまた後日、理解したら記事にします。
ところで今回作成したプログラムを何度か動かしてみる
order: 1781159094, time 0.4503579999999999 --- order: 1781159094, time 0.0009480000000001709
order: 957415846710361938, time 5.00586 --- order: 957415846710361938, time 0.04174399999999956
order: 5016171135827473028, time 2.770121 --- order: 5016171135827473028, time 0.03976999999999986
上が自前実装、下がSageによる実装で求めた位数。ランダムな32bitまたは64bitの標数の楕円曲線については、位数を正しく求められていそうなことがわかる。ただし、Sageの実装に比べて100〜500倍遅い。流石にこんなに遅いというのは何かある。
というわけで次回、Schoofのアルゴリズムより高速なSEAアルゴリズムについて扱います。SEAアルゴリズムについてはまだ補講が終わっていないのでその後になります