こんにちは。くろこんです。今回は「ビットコイン署名解読用イジングモデルの生成に成功した人」であれば知っているであろう、楕円曲線上の和の表し方についてです。
初めて完全な技術よりの内容となります。
楕円曲線上の点
楕円曲線とはビットコインの署名方式である secp256k1 などで用いられている曲線で
y^2 \equiv x^3 + 7 \pmod{p}
p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1
などのことです。secp256k1 では上記の方程式が用いられていて、公開鍵は例外なく上記の方程式を満たします。公開鍵はこの曲線上の点になっている、ということです。
ここで楕円曲線上の点に和を定めます。
(x1, y1)+(x2, y2) = (x3, y3)
\phi = \frac{y_2 - y_1}{x_2 - x_1}
\psi = \frac{y_1 x_2 - y_2 x_1}{x_2 - x_1}
x_3 = \phi^2 - x_1 - x_2
y_3 = -\phi x_3 - \psi
のように計算します。元の方程式に$\pmod{p}$がついているので、これらの計算すべてにも$\pmod{p}$が付きます。また、$(x1, y1)$ と $(x2, y2)$ は異なる点であるとします。同じ場合には分母が０になってしまうので、違う計算規則を適用します（調べればすぐわかるので、今回は割愛します）。
もう一つ、生成点Gという点を決めます。
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
急に１６進数です。ほとんどのサイトでは１６進数で表記されているので、今回もその流儀にならっています。同じ点の場合の計算規則で、$G + G = 2G$ を計算しておきます。
2Gx = 0xC6047F9441ED7D6D3045406E95C07CD85C778E4B8CEF3CA7ABAC09B95C709EE5
2Gy = 0x1AE168FEA63DC339A3C58419466CEAEEF7F632653266D0E1236431A950CFE52A
これで和を繰り返すことによって $dG$ を任意の整数 $d$ に対して計算できます。
この $d$ の値がビットコインでいう秘密鍵です。「$G$ を何回足したら公開鍵になるかの回数」が秘密鍵であってパスワードの役割を果たしています。公開鍵の座標がわかったら、そんな $d$ なんて計算できてしまうのでは？ と思ってしまいますが、相当難しく実際問題不可能とされています。
イジングモデルでの楕円曲線の和の表現
先ほどまでは楕円曲線の基本的な知識ですが、イジングモデル上でこの和を表すのはかなり難しいので、従来の文献を参考にします。
この文献では、イジングモデルで楕円曲線の方程式を表すために式変形を提案しています。文献中の式（１８）が、先ほどの点の和を表した式です。
x_3 = \frac{(y_2 - y_1)^2 - (x_1 + x_2)(x_2 - x_1)^2}{(x_2 - x_1)^2}
y_3 = \frac{(2 x_1 + x_2)(y_2 - y_1)(x_2 - x_1)^2 - (y_2 - y_1)^3 - y_1 (x_2 - x_1)^3}{(x_2 - x_1)^3}
先ほどの計算式とは異なり、$\phi$ と $\psi$ は代入して式から消去しています。文献では式（２０）のように分母を払って方程式を計算しても、制約としては等価であることを利用した式変形を提案しています。
(x_2 - x_1)^2 x_3 = (y_2 - y_1)^2 - (x_1 + x_2)(x_2 - x_1)^2
(x_2 - x_1)^3 y_3 = (2 x_1 + x_2)(y_2 - y_1)(x_2 - x_1)^2 - (y_2 - y_1)^3 - y_1 (x_2 - x_1)^3
こんな感じの方程式でイジングモデルを生成しても制約としては等価である、ということです。
何の説明もなく「分母を払う」と言っていますが、楕円曲線では$\pmod{p}$があるので割り算の扱いには注意が必要です。おおざっぱな説明ですが、「$\pmod{p}$において$a$で割る」というのは「$\pmod{p}$において$a^{p-2}$をかける」ことに相当します。実はとんでもなく面倒くさい計算です。
式（１８）はこの割り算のせいで、とんでもなく面倒くさい計算を表していますが、式（２０）では一転して４次式くらいになっています。すごく楽できるでしょう？ という文献です。ありがたく使わせてもらって secp256k1 の和を表したら、３００万変数より少し多いくらいで何とかなりました。
後は基底ベクトルを表すようなイメージで、
a_0 2^0 G + a_1 2^1 G + ...... + a_{255} 2^{255} G = P
という方程式を計算すればよいわけです。実際には和は２つの点にしか定義されていないので、for 文などで２５５回繰り返すことになります。３００万変数×２５５＝ ７億６５００万変数くらいで何とかなるはずです。
しかし、生成成功の記事には「８５００万変数で生成できたのは間違いない」とされています。この違いは何でしょうか？
イジングモデルでの楕円曲線の和の表現におけるコツ
ここで冷静に考えてみます。
a_0 2^0 G + a_1 2^1 G = P_1
を計算すると３００万変数かかります。しかし、これは大損です。
なぜなら、$P_1$ の値は $0G$ $1G$ $2G$ $3G$ の４通りしかないからです。あらかじめ４点を計算して、フラグを立てて管理したほうが圧倒的に軽い処理になります。
(1-a_0) (1-a_1) (0G)_x + a_0 (1-a_1) (1G)_x + (1-a_0) a_1 (2G)_x + a_0 a_1 (3G)_x = (P_1)_x
式が点$G$の和ではなく、$x$座標の計算になっているので、簡単な足し算になっています。いやいや、それなら２回や３回足すだけなのも馬鹿らしいです。３回なら、
\sum^{15}_{i=0} flag(i)\ (iG)_x = (P_3)_x
なので、$0G$ から $15G$ の１６通りにフラグを立てればOKです。
気づかれた方もいると思いますが、この〇〇通りというのは指数関数的に増えていきます。３００万変数という和の処理コストを考えて、良さそうなところまで和をサボります。今回は１１個のフラグをくっつけて、２３グループに分けています。
\sum^{2047}_{i=0} flag(i2^{11j})\ (i2^{11j} G)_x = (P_{11,j})_x
\sum^{22}_{j=0} P_{11,j} = P
としました。上の式は$x$座標の簡単な計算で同様に$y$座標も計算して、下の式は楕円曲線の点の和を計算しています。11 * 23 = 253 なので「３ビット推定をサボっている」ということです。追加で推定するのも難しくはないですが、バグが増えるとつらすぎるので初回はサボる仕様にして生成しました。
こうすると和が２２回で済んで、１１個のフラグをくっつけた処理も数千万変数で済むので、「８５００万変数で生成できたのは間違いない」ということになります。
記事作成者の本音
前の記事には「８０万変数でできたかもしれない」みたいな書き方をしてファイルもアップロードをしましたが、ちょっと怪しいと思っています。検算していたのですが、z3 と pysat で結果が違うという現象が発生。（それらを使った私のコードがおかしい可能性は十分にありますが……）
流石に最適化にミスがあるのでは、と弱気になっています。一方で「８５００万変数で生成できたのは間違いない」というのは、今回紹介させてもらった内容によるものでこちらは正解していそうです。
今回の記事は以上となります。お読みいただきありがとうございます。