Schoofのアルゴリズムで楕円曲線の位数を求める - yoshicamp参加記(1)

前回のyoshicamp!
2日目朝
Schoofのアルゴリズムを用いた楕円曲線の位数計算
昼
次回予告

前回のyoshicamp!

./VespiaryからXornetさんとﾈｺﾁｬﾝを招き、例年以上の盛り上がりを見せるyoshicamp。芦ノ湖を見下ろしながら始まったキャンプだったが、久々ということで気合が入っていたのか、私の同種写像暗号の講義もptr-yudaiの量子の講義も時間内には終わらなかった！　コンビニのおかずと冷凍餃子を食べてボードゲームを遊び1日目を終えて、2日目朝〜の講義はmitsuくんによる「ネコちゃん式-～安全な楕円曲線の生成～」です。

他の人のyoshicampレポートは https://yoshicamp.zer0pts.com/ をご覧ください

2日目朝

前日結構ハードに体力を使った割にはそこそこ早起きできた。ptr-yudaiは先に起きていたっぽい。朝ゴハンのパンをかじりながら外を眺めていたら、芦ノ湖の向こう側に富士山が見えることに気がついた。雲のない開放的な空に堂々とそびえていてかっこよかった。白状するとこのタイミングまで富士山があることに気がついてなかったです。

それはそれとして8:30 頃にはmitsuくんがやってきて、9時か9時半ごろには講義がぬるりと始まった。

Schoofのアルゴリズムを用いた楕円曲線の位数計算

overview

暗号で楕円曲線を用いるにあたって楕円曲線の位数というのは重要な指標で、適当に楕円曲線を生成してしまうと性質の悪い（例えばECDLPが簡単に解ける）位数を持ってしまうことがある。そうならないように、暗号プロトコルで楕円曲線を利用するときはその曲線の位数を確かめておこう。ところで楕円曲線の位数をどうやって求めるかというと……というのが前説。

まずはSchoofのアルゴリズムを用いて位数を計算する方法が紹介された。Schoofのアルゴリズム自体は位数ではなくFrobenius写像のトレース $t$ を計算するアルゴリズムだが、標数 $p$ の楕円曲線 $E(\mathbb{F_p})$ の位数とFrobenius写像のトレース $t$ の間には次のような関係が成り立つことが知られている。

$p + 1 - \#E(\mathbb{F_p}) = t$

すなわち、 $t$ がわかれば $t, p$ から楕円曲線の位数が計算可能である。

tを求めるための立式

Frobenius写像 $\phi: E \to E$ は $\phi( (x, y) ) = (x^p, y^p)$ と定義される自己準同型写像で、なんか口頭で補足されていた感じだと行列表示みたいなのと対応付けられるらしく、特性多項式やトレースが定義できるということだった。その特性多項式とは $\lambda(X) = X^2 - tX + p$ であり、ここにトレース $t$ が登場する。ケイリー・ハミルトンの定理より $\lambda(\phi) = \phi^2 - t\phi + p = 0$ なので、具体的な点 $P = (x, y) \in E$ を代入して移項して $(x^{p^2}, y^{p^2})+ p(x, y) = t(x^p, y^p)$ を解けば良いということだったが、ここでケイリー・ハミルトンの定理が出てきた理由はちゃんとはわかっていない。

とにかく、

$(x^{p^2}, y^{p^2})+ p(x, y) = t(x^p, y^p) \cdots ( \triangle )$

を満たすような $t$ こそが今求めたい $t$ である。そしてこれを効率的に求める方法の一つがSchoofのアルゴリズムである。

Schoofのアルゴリズム(l-torsion pointについて考えることで次数と探索範囲を減らしてあとでCRTする）

Schoofのアルゴリズムでは小さい素数 $l_i$ を用いて $l_i$ -torsion pointを考えるということにして、 $t$ の代わりに $(x^{p^2}, y^{p^2})+ p(x, y) = t_i(x^p, y^p)$ を満たす $t_i \equiv t \mod l_i$ を全探索したあとで中国剰余定理を用いて $t$ を復元するという方法を取る*1。

$l$ -torsion point *2を考えているということは $x$ は必ず $l$ -division polynomial $f_l$ について $f_l(x) = 0$ を満たすから、 $(\triangle )$ は $f_l$ が生成するイデアルによる剰余類環 $\mathbb{F_p}\lbrack x, y \rbrack / (f_l)$ 上の式と思って良い。これによって、実装中に登場する、 $x^{p^2}$ のような指数が大きくなりうる項の次数を $\deg f_l$ 以下に抑えることができる。さらに $F = x^3 + ax + b$ と置けば、 $y^p = (y^2)^\frac{p - 1}{2}y = (F^\frac{p - 1}{2} \mod f_l )y$ と $F$ に置き換えることで $y$ の項についても次数を抑えることができる。

実装

ここまでを整理すると、Schoofのアルゴリズムでは次の手順で楕円曲線 $E(\mathbb{F_p})$ におけるFrobenius trace $t$ が計算でき、 $t$ を用いて位数を計算できる。

小さい素数 $l_i$ について、 $(x^{p^2} \mod f_l, (F^\frac{p^2 - 1}{2} \mod f_l)y)+ p(x, y) = t_i( (x^p \mod f_l, (F^\frac{p - 1}{2} \mod f_l)y) )$ を満たす $t_i$ を探索する
$\prod l_i \ge 4 \sqrt{p}$ を満たすにたるの $(t_i, l_i)$ の組*3が得られたら、中国剰余定理によって $t$ を復元する
$\#E(\mathbb{F_p}) = p + 1 - t$ と計算して位数を求める

以上をSageで実装したものがこちら。

gist.github.com

y座標については常に $(Fに関する式)y$ なので常に暗黙の $y$ がかかっているということにして実装に明に $y$ を登場させていないのが工夫ポイント。そのほか、説明に登場したとおりに剰余環 $\mathbb{F_p}\lbrack x \rbrack / (f_l)$ を定義してその上で演算を行っていたり、剰余環上の（symbolicな＝xをxのまま扱う）楕円曲線演算を実装していたり、 $f_l$ 上に逆元が存在しない要素を引いたときはその $l_i$ をスキップする処理を実装したりしている。また、講義では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アルゴリズムについてはまだ補講が終わっていないのでその後になります

*1:なんで特定のねじれ群についてだけ考えるでよいのかは理解できてない

*2:面倒なので添字のiを外しているけど、それぞれのiについて考えています

*3:Hasseの定理より $|t| \le 2\sqrt{p}$ なので正負の幅を考えて $4\sqrt{p}$ 以上としている

*4:実は私はほとんど実装できていたが、位数を計算するタイミングで $t$ の符号を間違えていたのに気がつけず大デバッグまつりをしていた

ふるつき

v('=')v かに