記事をランダムに表示するボタン作った

scrapboxのrandomボタンが好きなのではてなブログでも出したいと思って作った。うまくいっていれば→のサイドバーに出ています。

こういう感じのHTMLを書いて、HTMLモジュールってやつでおいている *1

<button onclick='javascript: fetch("/rss").then(r => r.text()).then(data => { const parser = new DOMParser(); return parser.parseFromString(data, "text/xml") }).then(dom => {const items = dom.querySelectorAll("channel>item"); const item = items[ Math.floor(Math.random() * items.length) ]; location.href = item.querySelector("link").innerHTML; })' style="font-size: 120%; border: none; background: none; cursor: pointer;">🔄</button>

後から考えると関連記事モジュールでも十分な気がする

*1:よくみると/rssの出力を雑にパースしているだけなので真に昔の記事は取れてない。うそランダムです

2023-01-18

楕円曲線上の複数の点からその曲線のパラメータを思考停止で求めるテク

最近このテクを使う問題をいくつか解いたのでメモ。楕円曲線 $E$ と $E$ 上のいくつかの点 $P, Q, R, S \in E$ みたいなのがあって、 $E$ は与えられておらず $P, Q, R, S$ の座標だけがある、みたいな状況。

（今回なら）4点の座標と、その座標が満たすべき制約（Weierstrass標準形なら $y^2 \equiv x^3 + ax + b \mod p$ ）から、 $E$ のパラメータ（ $a, b, p$ ）を求めたい。知っている限りだとASIS CTF 2019 QualsのHalloween Partyとか、UIUCTF 2020のnook cryptoが出題例。

scrapbox.io

上記writeupにもあるようにこれは愚直な式変形でできる。 $a$ や $b$ のような知らないパラメータがなくなるように式変形して、複数の式でGCDを取ると剰余の法 $p$ （か、その小さい倍数）が得られるので、あとは $a$ だけが不明とか $b$ だけが不明みたいな式を作って剰余方程式を解いていく、という方針。

そんなに難しいということはないんだが、式変形というのは結構大変なので自分でやらなくていいならやりたくない。幸い変数をどんどん消去するように式変形する、という処理は自動化できる。

どうやるかというと消去式（resultant）というやつを使う*1。細かい内部の挙動は置いておいて、これは2式と消したい変数を与えると、その消したい変数を消去した形の式を返すようなインタフェースを持つ関数だと思って良い。

$f_1 = y_1^2 - (x_1^3 + ax_1 + b)$

$f_2 = y_2^2 - (x_2^3 + ax_2 + b)$

みたいに2つ式を立てておいて、g = f1.resultant(f2, b)とすると $g = (y_1^2 - y_2^2) - (x_1^3 - x_2^3+ a(x_1 - x_2))$ みたいな式を返してくれる。このくらいなら人間がやってもわけないが、 $b$ でなく $a$ を消したいという場合にも勝手にやってくれるので便利。

ただしこの方法も万能ではないので、resultantが使えないような式と変数の組み合わせや、そもそもresultantを呼び出せないような環が存在する。それぞれ消したいと指定した変数が消えてない式が帰ってきたりする場合や、除算が定義されていない集合上の多項式を定義している場合。

ということで、最近ではとりあえずあらゆる値を変数にして $\mathbb{Q}$ 上の多変数多項式環 $\mathbb{Q}\lbrack x_1, x_2, \dots \rbrack$ 上で立式して、あらゆる式の組み合わせでとにかう消去式を試して変数を片っ端から消していきうまく消えているやつを使う、という方法をとっている。

例えば ASIS CTF Finals 2022で出題されたmonwardという問題や、idekCTF 2022で出題されたECRSAという問題でこのテクを使った。monwardはWeierstrass標準形ではなくてEdwards曲線でパラメータを求める問題だったが、同じテクが使えた。

scrapbox.io

（idekCTF 2022のwriteupはまだ書いてないので、書いたら載せます）

グレブナー基底で全てを一発でやるとか、そうでなくても処理を一般化＆関数化するとか、もうちょっと洗練されたやり方がありそうだが、今のところはこれで満足しているし他に良い方法も知らない。

何かのタイミングでこのテクがお役に立てば幸いです && もっと良いテクを知っていたら教えてください。

*1:Sagemathではresultantというそのままの名前のメソッドが存在するのでこれを使ったら良いが、巷のCTFプレイヤーのコードを読んでいるとSylvester行列を経由して変数を消去するコードもよく見かける。どういう違いがあるかはわかっていないので、知っている人がいたら教えてください。

2023-01-02

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 かに