ブロックチェーン/レベル I · お金/1.2 サイファーパンクの道のり/レッスン 1
公開鍵暗号：ディフィー・ヘルマンとRSA
会わずに共有される秘密と、所有を証明する署名
用意するものモジュラー演算に対応した電卓やスプレッドシートディフィー・ヘルマンの論文（1976年）
問い
- 他の全員が聞いている中で、見知らぬ二人はどうやって秘密鍵について合意するのか？
- なぜ2つの大きな素数を掛け合わせるのは簡単なのに、その積から元の素数を見つけ出すのはほぼ不可能なのか？
- 署名できる能力によって所有が定義されるとしたら、何かを所有するとはどういう意味なのか？
探究
- 1976年以前は、安全な通信のためには信頼できるチャネルを通じて共有秘密を交換する必要があった。もし傍受者がその鍵を手に入れれば、その後のすべての通信が危険にさらされることになる。ホイットフィールド・ディフィーとマーティン・ヘルマンは『New Directions in Cryptography』（IEEE Transactions on Information Theory、1976年11月号）で解決策を提案した。2者はべき剰余演算（モジュラー指数演算）を用いて、公開されたチャネル上でも共有秘密を導き出すことができる。この数学は一方向性を持ち、順方向の計算は容易だが、秘密の入力値がなければ逆方向の計算は計算量的に不可能である。
- ラルフ・マークルは1974年から1975年にかけて同様のパズルを考案し、1978年に発表した。一方の当事者が多数の小さな暗号化されたパズルを公開し、もう一方の当事者はその中からランダムに1つを解いて、その内容を鍵として使用する。この方式の優位性は二乗の差にとどまった。n個のパズルがある場合、両当事者の作業量は約n単位であるのに対し、盗聴者の作業量は約n²単位である。ディフィー・ヘルマン方式ではこの差が鍵サイズとともに拡大し、さらにセッションごとに新しい鍵ペアを使用すれば、後に長期鍵が漏洩しても過去の通信内容は露見しない。
- 1977年、MITのロン・リベスト、アディ・シャミア、レオナルド・エーデルマンがRSAを開発した。正式な論文が『Communications of the ACM』（1978年2月）に掲載される前に、マーティン・ガードナーが『サイエンティフィック・アメリカン』1977年8月号のコラムでこの方式を紹介した。RSAは、2つの大きな素数の積を元の素数に分解することの難しさに基づいている。RSAによってデジタル署名が可能になった。秘密鍵でデータに署名し、対応する公開鍵で、署名者の秘密を明かすことなくその署名を検証できる。
- GCHQのジェームズ・エリスは1969年頃に「非秘密暗号」を考案し、1970年にそれを文書にまとめた。クリフォード・コックスは1973年にRSAに相当する方式を、マルコム・ウィリアムソンは1974年にディフィー・ヘルマン方式に相当する方式を導き出した。これらの発見は1997年まで機密扱いとされていた。この並行した発見は、1970年代初頭には数学的基盤がすでに成熟していたことを示しているが、実際の普及は学術研究者による公開後に初めて進んだ。秘密裏の研究では公共のインフラは築かれない。
- リベスト、シャミア、エーデルマンは2002年に、ディフィーとヘルマンは2015年にチューリング賞を受賞した。これはビットコインにとって重要な意味を持つ。所有権はもはや物理的な保管や銀行の記録に結びつくのではなく、秘密鍵で有効な署名を生成できる能力に結びつく。ビットコインはRSAではなくsecp256k1の楕円曲線暗号を使用しているが、根本的な構造は変わらない。ユーザーはトランザクションに署名することで資金の管理権を証明し、ネットワークは秘密鍵を一切見ることなく公開鍵によってそれを検証する。
- 小さな数を使ってディフィー・ヘルマン方式を計算してみよう。まず素数p = 23と底g = 5を公開で取り決める。アリスは秘密の値a = 6を選び、5^6 mod 23 = 8を送る。ボブはb = 15を選び、5^15 mod 23 = 19を送る。アリスは19^6 mod 23 = 2を、ボブは8^15 mod 23 = 2を計算する。公開チャネルを通ったのは23、5、8、19だけだが、両者とも秘密の値2を共有したことになる。実際のシステムでは数百桁の数が使われ、公開された値からaやbを復元することは計算量的に不可能である。
重要な事実
- ディフィーとヘルマンは1976年11月に彼らの鍵交換プロトコルを発表した。
- RSAは1977年にMITで開発され、1978年2月に『Communications of the ACM』に掲載された。
- GCHQでは、ジェームズ・エリス、クリフォード・コックス、マルコム・ウィリアムソンが1970年から1974年頃にかけて、後のアメリカの研究とは独立して公開鍵方式を開発した。
- GCHQによる公開鍵暗号の研究は、1997年に機密指定が解除された。
- RSAの安全性は、2つの大きな素数の積を素因数分解することの難しさに基づいている。
- ビットコインの所有権は、秘密鍵で署名できる能力によって定義される。
演習 九・六・三・一
9集める1970年から2008年にかけて開発された暗号学的プリミティブまたはプロトコルを9つ挙げてください。発明者、年、および中心的な数学的性質を記載してください。
6まとめる9つを、鍵交換、デジタル署名、ハッシュ、共通鍵暗号、認証、その他の6つのカテゴリーに分類してください。
3絞り込む6つのグループを、非対称暗号が分散型システムを可能にした3つの理由に絞り込んでください。
1結晶化する秘密鍵が何を証明するのか、そしてそれがなぜ所有のあり方を変えるのかを1文で書いてください。
事実確認
日付、数字、主張は、下記に記載された公表資料と照合して確認しました。
- W. Diffie & M. Hellman, 'New Directions in Cryptography', IEEE Transactions on Information Theory (Nov 1976)
- R. Rivest, A. Shamir & L. Adleman, 'A Method for Obtaining Digital Signatures and Public-Key Cryptosystems', Communications of the ACM (Feb 1978)
- S. Singh, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography (1999)
- S. Levy, Crypto: How the Code Rebels Beat the Government—Saving Privacy in the Digital Age (2001)