Pebble Coding

プログラマーの作業メモ

ビットコインでは楕円曲線暗号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年生レベルの数学の知識が必要になります。

楕円曲線暗号について詳しく知りたい方はこちらの記事もどうぞ。

pebble8888.hatenablog.com

OpenSSHにed25519が追加された経緯

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

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

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