Pebble Coding

ソフトウェアエンジニアによるIT技術、数学の備忘録

ビットコインでは楕円曲線暗号secp256k1が使われている

どうやらビットコインでは署名に楕円曲線暗号が使われているらしいです。
楕円曲線暗号というのはRSA暗号と同じ非対称型の暗号で秘密鍵と公開鍵のペアからなります。
秘密鍵は自分だけが知っている状態にし、公開鍵は他人に公開します。

ビットコインとは何か? 第3回:ビットコインの仕組み(アドレスの作成から送金まで) - ビットコインの解説 | Bitcoin日本語情報サイト

使われている楕円曲線暗号の形式はsecp256k1で、
曲線は {y}^{2} = {x}^{3} + 7だそうです。
法とする素数 {2}^{256} - {2}^{32} - {2}^{9} - {2}^{8} - {2}^{7} - {2}^{6} - {2}^{4} - 1 ( = {2}^{256} - {2}^{32} - 977 )
ベースポイント、ベースポイントの位数Lも定義されています。
cofactorは1ですね。

Secp256k1 - Bitcoin Wiki

その他のコインはどうなっているのか調べてみると、
イーサリウムはビットコインと同じsecp256k1のようです。
楕円曲線暗号に使う楕円曲線、法素数、ベースポイントは、暗号学者やNISTが安全だと認めたもののうちから使うのが普通です。
世の中に出回っている仮想通貨の多くはsecp256k1とed25519のどちらかを利用しているようです。

secp256k1の実装

bitcoinで使われているsecp256k1のソースはC言語で書かれていますが、
現在のメンテナーは、bitcoin core開発者の一人である Pieter Wuille 氏です。
C言語による実装ソースはこちら

GitHub - bitcoin-core/secp256k1: Optimized C library for EC operations on curve secp256k1

処理時間を気にしなければ、この暗号をpythonで実装することも容易で、数百行で実装出来てしまいます。
ただし、処理時間がめちゃくちゃかかり実用に耐えませんでので、実際は、
演算を高速に行うための様々なアルゴリズムを駆使した上、さらにアセンブリを使い、C言語で最も高速に動作するところまで、
ギリギリにチューニングしてあります。
暗号の演算を高速に行うためのアルゴリズムはそれだけで論文になるほどで、
大学4年生レベルの数学の知識が必要になります。

OpenSSHにed25519が追加された経緯

この調査の過程で、OpenSSHにed25519が追加された経緯を知りました。

leah blogs: The road to OpenSSH bliss: ED25519 and the IdentityPersist patch

NISTというアメリカの暗号学者が多数所属する国家機関であるNSA
(マットデイモン脚本、主演の映画 グッドウィルハンティングにも出てきましたね。)
に関連のある団体が決めた楕円曲線は何か重大なバックドアがあるかもしれない。
心配だからed25519も追加しようぜってことらしい。どんだけパラノイアなんだって話ですが。

この曲線を選んだのは Satoshi Nakamoto

こちらの記事や、
NSA Backdoors and Bitcoin | Escape Velocity

Vitalik Buterin による2013年の記事

Satoshi’s Genius: Unexpected Ways in which Bitcoin Dodged Some Cryptographic Bullets - Bitcoin Magazine - Bitcoin News, Articles and Expert Insights によると、

署名のアルゴリズムとして、secp256k1 を選んだのは Satoshi Nakamoto のようです。
secp256k1 のkは有名な楕円曲線論研究者のKobliz先生の頭文字から来ています。
似た楕円曲線としてsecp256r1があります。
secp256k1ではxの係数が0で定数項が7ですが、secp256r1はxの係数も定数項も巨大な数です。
この数はNISTが定めたもののようですが、NSAによるバックドアが仕掛けられているかも知れないので、
Bitcoinでは採用されなかったのではないかと推測されているようです。
一般に知られている安全な楕円曲線の選び方としては、
こちらの本に記載されているように、

知られている攻撃法を回避するようにします。
1)  \# E(F_q) は大きな素数Lと小さな正整数hで \# E(F_q)=L \cdot hとなること。
2) L と p は互いに素であること。
3)  E(F_q)の位数がLの元をGとするとき、 \langle G \rangle の双線型写像による {F_q}^{k}への埋め込み次数kに対して以下のいずれかを満たす。
(a)  1 \lt k \lt {(\log q)}^{2} の整数kに対し、 L \nmid ({q}^{k} - 1 ) である。
(b)  L \mid ( {q}^{k} - 1)となるkが 6 \leq k \lt 20である。

supersingular曲線ではないことの確認

 p = 2^{256} - 2^{32} - 977 ですが、
 y^{2} = x^{3} + Ax + B
A=0なのでこの曲線がsupersingularでないことを確かめます。
 p = 1 (mod 3)
であることがpythonで簡単に確かめられます。
 p = 2 (mod 3)ではないのでsupersingularではありません。