どうやらビットコインでは署名に楕円曲線暗号が使われているらしいです。
楕円曲線暗号というのはRSA暗号と同じ非対称型の暗号で秘密鍵と公開鍵のペアからなります。
秘密鍵は自分だけが知っている状態にし、公開鍵は他人に公開します。
ビットコインとは何か? 第3回:ビットコインの仕組み(アドレスの作成から送金まで) - ビットコインの解説 | Bitcoin日本語情報サイト
使われている楕円曲線暗号の形式はsecp256k1で、
曲線はだそうです。
法とする素数は
ベースポイント、ベースポイントの位数Lも定義されています。
cofactorは1ですね。
その他のコインはどうなっているのか調べてみると、
イーサリウムはビットコインと同じ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年の記事
署名のアルゴリズムとして、secp256k1 を選んだのは Satoshi Nakamoto のようです。
secp256k1 のkは有名な楕円曲線論研究者のKobliz先生の頭文字から来ています。
似た楕円曲線としてsecp256r1があります。
secp256k1ではxの係数が0で定数項が7ですが、secp256r1はxの係数も定数項も巨大な数です。
この数はNISTが定めたもののようですが、NSAによるバックドアが仕掛けられているかも知れないので、
Bitcoinでは採用されなかったのではないかと推測されているようです。
一般に知られている安全な楕円曲線の選び方としては、
こちらの本に記載されているように、
知られている攻撃法を回避するようにします。
1) は大きな素数Lと小さな正整数hでとなること。
2) L と p は互いに素であること。
3) の位数がLの元をGとするとき、 の双線型写像によるへの埋め込み次数kに対して以下のいずれかを満たす。
(a) の整数kに対し、 である。
(b) となるkがである。
supersingular曲線ではないことの確認
ですが、
A=0なのでこの曲線がsupersingularでないことを確かめます。
であることがpythonで簡単に確かめられます。
ではないのでsupersingularではありません。