ビットコインでは楕円曲線暗号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が追加された経緯を知りました。

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 によると、

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

代数学から学ぶ暗号理論: 整数論の基礎から楕円曲線暗号の実装まで

作者: 宮地充子
出版社/メーカー: 日本評論社
発売日: 2012/03/09
メディア: 単行本（ソフトカバー）
この商品を含むブログを見る

知られている攻撃法を回避するようにします。
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$ である。

ビットコインとブロックチェーン:暗号通貨を支える技術

作者: アンドレアス・M・アントノプロス,今井崇也,鳩貝淳一郎
出版社/メーカー: NTT出版
発売日: 2016/07/14
メディア: 大型本
この商品を含むブログ (7件) を見る

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ではありません。