Howdy! How can we help you?
(反対派を防衛する)Part1:暗号技術の紹介
暗号化とは何か？
学ぶべきこと
1. 暗号化の基本要素：平文、暗号文、暗号（または暗号化プロトコル）、暗号鍵
2. 古典的な暗号化手法の仕組み
3. 暗号化が破られる可能性のある方法
4. 破られない暗号
ここでは、「紙とペンを使った暗号」という基本的なものから始めて、コンピュータを使ったより複雑な暗号化方法に進んでいきます。
暗号化とは、メッセージにスクランブルをかけて、意図した相手だけが解読（読み取り）できるようにするプロセスです。元のメッセージ（平文）をスクランブルする方法は、暗号または暗号化プロトコルと呼ばれます。ほとんどの場合、暗号は秘密にすることを意図していません。スクランブルされた読めない暗号化されたメッセージは暗号文と呼ばれ、安全に共有することができます。ほとんどの暗号は、メッセージの暗号化と復号化（スクランブルとアンスクランブル）のために、暗号鍵と呼ばれる追加の情報を必要とします。
シンプルな暗号。シーザー暗号
まず，最も単純な暗号として，シーザー暗号を考えてみましょう。この暗号では，メッセージの各文字を，申し合わせておいた数だけアルファベットをシフトさせます。例えば，次のような平文を暗号化したいとします。
IF VOTING CHANGED ANYTHING IT WOULD BE ILLEGAL
という平文を暗号化しようとした場合、メッセージの各文字をアルファベットの3つ分後にずらし、AをD、BをE、そしてZをアルファベットの最初に折り返してCにします。この平文を暗号化すると、次のような暗号文になります。
li yrwlqj fkdqjhg dqbwklqj lw zrxog eh loohjdo
このメッセージを復号するには、受信者が逆の操作をします。メッセージの各文字をアルファベットの3つ前に戻して、ZをWに、Aをアルファベットの最後からさかのぼってXにします。シーザー暗号では、各文字をアルファベットの何番目に移動させるかを表しており、この例では「3」となっている。シーザー暗号の鍵は、Aからの変換結果に対応するアルファベットで表すこともできる。例えば、3のシフトはDの鍵、23のシフトはZの鍵、そしてゼロのシフト（同一性のシフト）はAの鍵となるでしょう。
用語のおさらいをしておきましょう。この例では、暗号（または暗号化プロトコル）を適用するには、次の指示に従うだけでよい。”暗号化するには、平文メッセージの各文字をアルファベットの後方にn文字ずつシフトシフトする。復号化するには，メッセージである暗号文の各文字を，アルファベットの前方にn文字ずつシフトする」．鍵となるのはシフト量のnです。
もちろん，シーザー暗号は強力な暗号ではありませんし，自分の計画を秘密にしておくためにシーザー暗号を信頼すべきではありません。敵対者があなたの秘密のコード（暗号文）を解読するために必要なことは、アルファベットを後方にシフトする可能性をすべて試すことです。鍵Aは暗号文と平文を等しくするものなので、25個の鍵しかありません。このような攻撃はブルートフォース攻撃と呼ばれ、可能な鍵をすべて試して暗号化されたメッセージを解読しようとする攻撃です。シーザー暗号の場合，可能な鍵が非常に少ないため，この攻撃が可能です。
少しだけ複雑な暗号。ヴィジュネル暗号
ヴィジュネル暗号は，複数のシーザー暗号を組み合わせたもので，それぞれに鍵があります．通常、鍵は単語として与えられ、その単語のアルファベットの位置によって、シーザー暗号のようにAの文字をどのようにずらすかが決まります。これは、例を挙げて説明するのが一番わかりやすい。例えば、次の平文を暗号化したいとします。
RESPECT EXISTENCE OR EXPECT RESISTANCE
(存在を尊重せよ、さもなくば抵抗に遭う)
をACTという鍵で暗号化したいとします。
このばあい
・平文の1文字目から始めて2つおきに現れる文字(R, P, T …)は、ACT鍵の1文字目がAなのでAを鍵とするシーザー暗号で暗号化します。このシーザー暗号はAをAに、RをRに、PをPに変換します。この鍵は0とも表されます。
・平文の2文字目から始めて2つおきに現れる文字(E, E, E …)は、ACT鍵の2文字目がCなのでCを鍵とするシーザー暗号で暗号化します。このシーザー暗号はAをCに、EをGに変換します。この鍵は2とも表されます。
・平文の3文字目から始めて2つおきに現れる文字(S, C, X …)は、ACT鍵の3文字目がTなのでTを鍵とするシーザー暗号で暗号化します。このシーザー暗号はAをTに、SをLに変換します。この鍵は19とも表されます。
この3つのシーザー暗号を適用すると、暗号文ができあがります。
rglpgvt gqiumepve qk ezieem rgliumapve
この暗号を破るには、敵が鍵の長さを知っているとします。敵は、その長さの3文字の単語（一般的には3文字の文字列）をすべて使って暗号文を復号しようとします。この例では、最大で25 × 26 × 26 = 16,900回の試行が必要になります。これは、人の手では簡単にできない量ですが、コンピュータでは容易にできます。もし敵があなたの鍵の長さを知らなければ、ブルートフォース法で暗号を解読するためには、さらに多くの可能な鍵（25 + 25 × 26 + 25 × 26 × 26 + …）を試さなければなりません。鍵が長ければ長いほど、ブルートフォース法は難しくなり、敵対者は暗号を破るために苦労しなければならないことに注意してください。
コンテクスト：破れないワンタイムパッド
ヴィジュネル暗号は、ランダムに選択された文字列を鍵とし、平文メッセージと同じか、より長い鍵を使うことで、ワンタイムパッドonetime padと呼ばれる暗号に発展できます。歴史的には、鍵自体を紙に書いて通信相手に配布していました。暗号化にはヴィジュネル暗号を適用するのですが、暗号鍵としてワンタイムパッドから拾う文字はどれも一度だけ使い、平文の次の文字に対してはワンタイムパッドから次の文字を鍵として使います。復号化には、このワンタイム・パッドと鍵の開始位置が必要となります。鍵がなければ、この暗号を破ることはできません。つまり、時間と資源が無限にあっても、鍵を推測して暗号文を解読することができないのです。これは、ある長さの暗号文が同じ長さの任意の平文に対応しうるためです。例えば、ランダムキーを知らない場合、ワンタイムパッドで暗号化された暗号文SOU DUCYFUK RXL HQKPJは、ALL ANIMALS ARE EQUALという平文にも、FEW ANIMALS ARE HAPPYという平文にも、同じ確率で対応しうるのです。鍵がなければ、意図した（平文の）メッセージを知る手立てがまるでないのです。単語間のスペースを省略したり、単語間のスペースを暗号化したりすれば（27文字のアルファベットABCDEFGHIJKLMNOPQRSTUVWXYZ_（_はスペース）を使用）、単語の文字数のパターンにあてはまる平文をいくつも推測することさえはるかに困難になります。
もちろん、ワンタイムパッドには、鍵（onetime pad自体）をどのように通信相手と交換するかという実用上の問題があります。その鍵は、メッセージの長さと同じか、将来起こりうるすべてのメッセージの合計の長さと同じです。それにもかかわらず、歴史的には、グループでワンタイムパッドを直接共有して、安全でないチャンネルでメッセージを送信するという方法が使われてきました。1980年代後半、南アフリカでアパルトヘイトと闘っていたアフリカ民族会議（ANC）は、海外の支持者と国内の工作員との間のメッセージを暗号化するためにワンタイムパッドを使用していました。ワンタイムパッド（鍵）は、アムステルダムからヨハネスブルグまでの路線を担当していた信頼できる航空スチュワードが物理的に輸送していました。ちなみに、ANCでは暗号化と復号化をコンピュータ化しており、暗号化されたメッセージを電話回線で送信し、留守番電話に録音したり、留守番電話から受信したりすることで、”非同期通信(訳註)”を可能にしていました。
訳註：通信を行う機器間でデータや信号の送信と受信のタイミングを合わせる動作や仕組みを用いずに通信することを非同期通信という。(https://e-words.jp/w/%E9%9D%9E%E5%90%8C%E6%9C%9F.html)
次に学ぶべきこと
現代の暗号技術
外部リソース
Jenkin, Tim “Talking with Vula: The Story of the Secret Underground Communications Network of Operation Vula.” (英語) Mayibuye: Journal of the African National Congress, October 1995.
現代の暗号技術
この章を読む前に、「暗号化とは」の章を読んでおくことをお勧めします。
この章で学ぶこと
1. 安全性と鍵の長さの関係
2. オープンソースソフトウェアとは何か、なぜそれがセキュリティにとって重要なのか
現代の暗号技術は、人の手で行うものではありません。コンピュータが代わりにやってくれるのですが、そのアルゴリズムの詳細については本書では触れません。しかし、現代のデジタル・セキュリティ・ツールをよりよく理解し、評価するのに役立つ一定の原則があります。
ブルートフォース・アタックを必要とするセキュリティ
現代の暗号プロトコルは、（暗号鍵を持たない）敵に、暗号を解読するために可能な限りの鍵を試すのと同じだけの時間を（ほぼ）費やさせるように設計されています。可能な限りの鍵を試すことはブルートフォース攻撃として知られていることを思い出してください。暗号プロトコルのパラメータは、ブルートフォース攻撃が実用にならないほどその計算に長時間を要するように設定されています。通常、最も重要なパラメータは、鍵の長さです。古典的なヴィジュネル暗号と同様に、鍵が長いということは、正しい鍵を推測するために、より多くの可能性のある鍵を探さなければならないということです。時代が進み、コンピュータの処理が高速化・高性能化すると、ブルートフォース攻撃が不可能であることを保証するために、より長い鍵が必要になることがあります。そのため、多くの暗号プロトコルでは、鍵のサイズを「鍵を表現するのに必要なビット数」で表している。
コンピュータは、暗号鍵を含む情報を、0と1の2値で表現します。0から9までの数字が10進数の桁を表すように、0と1は2進数のビットを表します。3桁の10進数は何個あるでしょうか？10×10×10＝103＝1000、つまり0～999の数字です。同じように、4ビットの2進数は、2×2×2×2＝24＝16個あります。
例として、AES暗号プロトコルを128ビット、256ビットの暗号鍵で使用する場合、AES-128、AES-256と呼ぶことがある。AES-128では、2128＝340282366920938463463374607431768211456個の鍵が考えられる。AES-256では、2256 = 115792089237316195423570985008687907853269984665640564039457584007913129639936個の鍵が考えられる。AES-256のすべての可能な鍵、あるいは可能な鍵のごく一部でも試してみることは、米国のような国民国家の計算能力をもってしても、計算上不可能である。
隠匿では安全性を確保できない
19世紀初頭から、数学者は「暗号方式は、その方式が秘密でなくても安全でなければならない」という基準を持っていた。これは、「安全性を確保するために方式を秘密にしなければならないのであれば、これまでにその方式で暗号化された、あるいはこれから暗号化されるすべてのメッセージは、その方式が明らかになってしまう危険性がある」という原理に基づくものです。一方、鍵を秘密にしておくことだけが必要な方法であれば、その鍵が漏洩した場合に、その鍵で暗号化されたメッセージが明らかになってしまうリスクがあるだけです。
透明性がもたらすセキュリティ
実際、暗号化方式の透明性が高ければ高いほど、その暗号化方式の安全性を信頼することができます。このことを理解するために、暗号化プログラム（あるいは他のコンピュータプログラム）がどのように作られるかを考えてみましょう。まず、暗号化を実行するためのアルゴリズムが作成されます。プログラマーは、このアルゴリズムをコンピュータのソースコードにします。コンピュータは、このソースコードをコンパイルして、あなたのコンピュータや携帯電話で動作するプログラムやアプリを作ります。
アルゴリズムからソースコード、コンパイルされたソースコードへ
優秀なプログラマーは、アルゴリズム（1）からソースコード（2）に変換し、さらに元に戻すことができるはずです。セキュリティの専門家であれば、アルゴリズムに基づいて暗号プロトコルの安全性を評価することができますが、同時にソースコードを評価して、その実装が忠実に行われているかどうか（意図的かどうかにかかわらず、間違いやバグがないかどうか）を確認する必要があります。しかし、ユーザーとしては、コンパイルされたプログラムにしかアクセスできません(3)。残念ながら、コンパイルされたコードしかない場合、誰もがソースコードを再現することはできません。そのため、ソースコードが入手できない限り、アプリのセキュリティに関する主張が正しいかどうかは誰にもわかりません。一方で、ハッカーがアプリのセキュリティを破ろうとするには、コンパイルされたプログラムだけあれば十分です。このようなソフトウェアはオープンソース・ソフトウェアと呼ばれ、Signal、Firefox、Linuxなど、セキュリティを含む多くの有名なプロジェクトが含まれています。もう一方はクローズドソースソフトウェアであり、Safari、Internet Explorer、Windows、Mac OSなど、プロプライエタリなソフトウェアの販売を通じて製品を収益化することを目的としたプロジェクトで採用されています。クローズド・ソース・ソフトウェアのセキュリティを評価することは可能ですが（例えば、社内や依託での監査など）、それを継続的に維持することははるかに困難です。オープンソース・プロジェクトは、誰でも自由に調査することができるため、セキュリティ上の（あるいはその他の）問題を発見する機会があるのです。
暗号化キーの保護によるセキュリティの確保
最近の暗号プロトコルでは、暗号化方式が一般的に公開されているため、セキュリティを確保するには、暗号化キーを保護する必要があります。これが実際にどのようなものかは、暗号鍵がどこにあるかによって異なります。安全なインスタントメッセージングアプリであるSignalの場合、暗号化キーは携帯電話内のファイルに記録され、携帯電話の通信を保護しています。あなたのパスワードをクラウドと同期できるようなパスワード・マネージャーの場合、あなたのパスワードを全部保存しているファイルは、パスワード・マネージャーにログインするときのパスワードから導出する鍵で暗号化されるか、そのログイン・パスワード自体で保護されています。
インフラへの不信感がセキュリティにつながる
エンド・ツー・エンドの暗号化とは、メッセージをスクランブルすることで、会話のエンドポイントでしか読めないようにすることです。しかし、ここで混乱が生じています。エンドポイントとは何でしょうか？エンドポイントとは、あなたとあなたの友人だけでしょうか？それとも、サーバーもエンドポイントなのでしょうか？それは、アプリケーションによって異なります。例えば、https（あなたがアクセスしたウェブページをホストするサーバーとあなたとの間の通信を保護する）は、あなたとサーバーだけがウェブページの内容を解読できるように暗号化されています。Signalはメッセージを暗号化して、あなたとあなたがメッセージを送っている友人だけが読めるようにします。どちらの場合も、情報を知る必要のある人や団体だけが情報を復号化することができます。これがエンド・ツー・エンド暗号化の本質です。
ここでは、プライベートメッセージングにおいてエンド・ツー・エンドの暗号化が重要な理由を説明します。これについては、”The Man in the Middle “の章で詳しく説明しています。次の図では、アサタ（左）がインターネットを介してボビー（右）にメッセージ（アーシュラ・K・ル・グインの『The Dispossessed』）を届けようとしています。
ボビーにメッセージを送ろうとするアサタ
しかし、インフラにはJ.エドガー・フーバーの亡霊がつきまとっている。この中間者(MITM)は、二人の友人の間で送られる保護されていないメッセージを傍受し、読み、変更することができるのだ。こんな感じです。
間にいる者がメッセージを傍受して変更する(エドガーは、メッセージをそのまま読んで送ることもできる)
さらに悪いことに、アプリが「暗号化」を使用しているといっても（誰が鍵を持っているかを明確にせずに）、メッセージのプライバシーが守られ本物であることは保証されません。例えば、2人の同志の間にあるサーバーが暗号化キーを管理している場合、そのサーバーにアクセスできる人は、2人の間のすべてのメッセージを読み、変更することができます。しかし、アサタとボビーがメッセージを（下図の青い鍵で）暗号化している場合、エドガーはメッセージを読むことができず、青い鍵で復号できるメッセージに置き換えることもできないでしょう。
暗号化によって、間にいる者によるメッセージの変更をできなくする
アプリケーションがエンド・ツー・エンドの暗号化を使用しているかどうかは、どうすれば分かるのでしょうか？暗号化キーを確認する方法があるということが最も良い方法といえます。Signalでは安全番号safety numbersを使ってこれを簡単に行うことができます。これについては、”暗号署名による認証 “の章で詳しく説明します。
悪意ある第三者の影響を受けにくくするもう一つの方法は、ピア・ツー・ピアのメッセージングで、メッセージや連絡先の管理の間に「サーバーが存在しない」ことだと言われています。あなたとあなたの友人の間には、膨大な量のインターネットインフラが存在していますが、ほとんどのユーザーやアプリケーションからは見えません。上述したように、このインフラこそが、国家が、検知されず疑われることなく大量監視を行うために利用するものなのです。
イン・コンテクスト：エニグマ・マシン
最初の近代的な暗号化技術は、おそらく第二次世界大戦中に使用されたものです。現代のコンピュータに先駆けて、そのプロトコルは洗練された機械装置によって支えられていました。その中でも最も有名なのが、ナチスドイツが使用したエニグマ・マシンです。エニグマは電気機械式の装置で、特定の鍵を設定して平文を入力すると、暗号文が出力される仕組みになっていました。同じ鍵で、暗号文を入力すると、元の平文が出力される。
エニグマ・マシン（写真提供：Greg Goebel
ここでの鍵とは、ローターの順番と初期位置（上の写真）のことです。標準的な操作では、毎日新しい鍵を使わなければなりませんでした。エニグマ・マシンのオペレーターに配布されたハンドブックには、日々の鍵が記載されており、これは実質的にワンタイムパッドです。ちなみに、この手帳は水溶性のインクで印刷されているので、敵の手に渡る恐れがあるときはすぐに破棄することができました。
エニグマで暗号化されたメッセージを解読するには、多くの努力が必要でした。第二次世界大戦中にいくつかの機械が接収されましたが、機械を手に入れてもメッセージを解読することはほとんど不可能でした（方法が公開されている現代の暗号と同様です）。コンピュータ科学の創始者の一人であるアラン・チューリングは、第二次世界大戦中、英国の暗号解読者の中心地であるブレッチリー・パークで働いていました。チューリングが設計したボンベbombeは、エニグマのメッセージを解読するために特別に設計されたコンピュータの一種です。しかし、ボンベだけでは不十分でした。実際、鍵なしでエニグマのメッセージを解読することは、現代の計算能力をもってしても非常に困難であり、戦時中に傍受されたエニグマ暗号でまだ解読されていない有名なメッセージが少なくとも1件はあります。）。しかし、ボンベと、早朝のメッセージのほとんどが天気予報や「Keine besonderen Ereignisse」（「何も報告することはない」）というフレーズを含んでいたという事実とが相まって、連合国側はエニグマの暗号化されたメッセージを定期的に解読することができました。
戦時中のチューリングの功績は、戦争を2年以上も短縮したと言われています。しかし、ブレッチリー・パークでの仕事は機密扱いだったため、彼の仕事は生涯知られることはなく、実際、彼は戦争に貢献していないと批判されていました。さらに悲劇的なことに、同性愛者である彼は、政府から迫害され、1952年には同性愛の罪に問われました。有罪となった彼は、化学的な去勢手術か投獄かの選択を迫られました。懲役刑を選択した彼は、あと2年しか生きられず、青酸カリの毒で自らの命を絶ったと言われています。
次に学ぶこと
暗号化のための鍵の交換
外部リソース
Caraco, Jean-Claude, Rémi Géraud-Stewart, and David Naccache. “Kerckhoffs’ Legacy.” 2020.
メディア掲載情報
source-code © OSU OERU is licensed under a CC BY-NC (Attribution NonCommercial) license
mitm-basic-1 © OSU OERU is licensed under a CC BY-NC (Attribution NonCommercial) license
mitm-basic-2 © OSU OERU is licensed under a CC BY-NC (Attribution NonCommercial) license
mitm-basic-3 © OSU OERU is licensed under a CC BY-NC (Attribution NonCommercial) license
Four-rotor-enigma © Greg Goebel is licensed under a Public Domain license
暗号化のための鍵の交換
本章を読む前に、「現代の暗号」の章を読むことをお勧めします。
学ぶこと
1. 暗号化キーを事前に共有せずにメッセージを暗号化する方法
2. 現在オンラインで行われている主な鍵の交換方法
インターネットを介した通信の盗聴は、直接接続しているWi-Fiホットスポット、インターネットサービスプロバイダー、閲覧したWebページをホストしているサーバー、各国のゲートウェイ、そしてその間にある膨大な数のルーターやスイッチなど、多くのポイントで行われています。
暗号化されていなければ、これらの通信はすべて、ストーカーやハッカー、政府機関などの盗聴者に読まれてしまいます。しかし、通信を暗号化するためには、通信相手との間で鍵を取り交わす必要があります。Webサイトを閲覧する場合、そのWebサイトを運営するサーバーと安全に鍵を交換するにはどうすればよいのでしょうか。インターネットのような安全ではない経路でしか通信できない2つの当事者（2人、1人と1台、2台のサーバーなど）が、会うことなく効率的に鍵の合意をする方法が必要です。
物理的な例。鍵を交換せずにメッセージを交換する場合
まず、物理的な例を以下に示します。アサタがボビーに荷物を送りたいとします。彼女はその荷物を、複数のロックをかけた大きな留め具のついた丈夫な箱に入れます(1)。彼女は箱にロックをかけましたが、ボビーはこれを開ける鍵を持っていません。アサタはボビーに箱を郵送しますが、ボビーは箱を開けることができません（箱が輸送されている間は誰も開けられません）。ボビーは箱を自分でロックします(2)が、これを開ける鍵をアサタは持っていません。箱を受け取ったアサタは、自分の鍵を外してボビーに箱を送り返します(3)。これでボビーは箱を開けることができるようになります。箱を開けようとする他の者は、アサタの鍵、ボビーの鍵、またはその両方を破らなければなりません。
このように、鍵を交換しなくても、何かを安全に送信することは可能です。しかし、暗号化キーを交換するために、物理的にロックされた箱を郵送するわけにはいきません。そこで必要になるのが、デジタル通信に使える数学的なバージョンです。
数学的な例。鍵を交換せずにメッセージを交換する方法
では、物理的な箱や鍵を使わずに、どのようにして暗号化を行うかを考えてみましょう。例えば、(いつものように)任意のテキストを暗号化することができ、(ここでもいつものように)複数の暗号化レイヤーを適用することができ、レイヤーの暗号化と復号化をどのような順序で行っても同じ結果が得られるような暗号化プロトコルがあるとします。この最後の性質を満たす数学的操作は、「可換commutative」と呼ばれます。暗号化とは何か」の章で説明した暗号化プロトコルはすべて可換です）。それでは、ヴィジュネル暗号を例にして説明します。
Assataは次のようなメッセージを暗号化します。
AT ONE TIME IN THE WORLD THERE WERE WOODS THAT NO ONE OWNED
(世界のある時代には、誰も所有していない森があった。)
というメッセージを、ヴィジュネル暗号と鍵ALDOで暗号化し、暗号文を得ます。
ae rbe elae tq hhp zcrwg hhpus wpus wzrrs ekot yr cnp rknpg
と入力し、その結果をBobbyに送ります。Bobbyは鍵を持っていません! しかし、Bobby はこの暗号文を Vigenère 暗号と LEOPOLD の鍵で暗号化し、二重に暗号化されたテキスト
li fqs poli hf vss kgflu skayg ldfv hdfgg pnzx mg qys cobeu
を得ます。
その結果を Assata に送り返します。AssataはBobbyからのメッセージを自分の鍵（ALDO）で “復号 “し、（暗号化されたままのメッセージ）
lx ccs elxi wc hsh hsfar ekpvs lsch hscsg eklx bd cyh zabtr
を取得し、その結果をBobbyに送ります。
最後に、Bobbyは自分の鍵（LEOPOLD）でこれを解読し、Assataが最初にBobbyに送りたかったメッセージを得ます。
AT ONE TIME IN THE WORLD THERE WERE WOODS THAT NO ONE OWNED
(世界のある時代には、誰も所有していない森があった。)
この例では、アサタは自分の鍵（ALDO）を誰とも共有しておらず、ボビーも自分の鍵（LEOPOLD）を誰とも共有していないことに注意してください。ヴィジュネル暗号は可換であるため、メッセージがアサタの鍵で暗号化され、次にボビーの鍵で暗号化され、次にアサタの鍵で復号化され、最後にボビーの鍵で復号化されても問題はありません。重要なのは、メッセージがそれぞれの鍵で一度ずつ暗号化され、復号されたということです。盗聴者は、3つある中間暗号文のいくつかを見ることしかできません。
物理的な例。安全でないチャンネルでの秘密の合意
現代の暗号システムでは、このようにメッセージ全体を何重かに暗号化してやり取りするのではなく、上記の例のように最初のやり取りを行い、目的の通信に使用する鍵を決定します。アサタは、「AT ONE TIME IN THE WORLD…」というメッセージを送信するのではなく、より長い通信に使用するための暗号化キーを送ったと考えてください。これからDiffie-Hellman鍵交換と呼ばれる、現代のほとんどすべての通信で使われている鍵交換の数学的基礎を説明します。
まず、数学の代わりに絵を使って、どのように行われるかを見てみましょう（下図）。ここでは、2色の絵の具を混合し、この二つの絵の具の混合を解除する[もとの二つの色に戻す]ことはできないと仮定します。具体的には、2色のうちの1色が何であるかを知っていても、それに何の色を混ぜて、結果的に混ざった色になったのかを知ることはできないと仮定します。
アサタとボビーは、まず絵の具の色（この例では黄色）と量（例えば10mL）に合意します（1）。これは安全ではない通信経路で行うことができ、盗聴者には色と量もわかってしまうことを想定します。次に、アサタは色(ここでは錆びたオレンジ)を選び、それを秘密にします(2)。彼女は黄色10mLと錆びたオレンジ10mLを混ぜて、珊瑚色のような色にします(3)。彼女はこれを、盗聴者に見られてしまうことを承知の上で、安全ではないチャンネルを使ってBobbyに送信します。Bobbyも同じように、自分の秘密の色を使います(4)。
次に、Bobbyから受け取った絵の具のサンプルを見てみましょう(5)。アサタは自分の秘密の色(6)を10mL混ぜて、濃い紫(7)にします。ボビーも同じことをします。黄色、彼女の秘密の色、そしてBobbyの秘密の色をそれぞれ10mLずつ混ぜると、Assataの不快な茶色っぽい暗い紫色が得られます。ボビーの絵の具の混合物は、黄色と彼の秘密の色とアサタの秘密の色を10mLずつ混ぜ合わせて得られます。つまり、Bobbyも同じように不快な茶色っぽい暗い紫(8)になってしまうのです! 盗聴者はこの暗い紫色を作ることができるのでしょうか？盗聴者は、黄色(1)、黄色とアサタの秘密の色の組み合わせ(3)、黄色とボビーの秘密の色の組み合わせ(5)を盗み見しています。しかし、不快な茶色を作るためには、盗聴者はアサタかボビーの秘密の色を得るために混合を解除する必要がありますが、それはできません。
ディフィー・ヘルマン鍵交換(Diffie-Hellman Key Exchange)
このプロセスを数学的に再検討してみましょう。ここでは、元に戻すことは不可能か困難で、しかも可換式の数学的操作を用います。逆転が困難な数学的演算や関数は一方向性関数と呼ばれます。この数学的操作を記号☆で表してみましょう。つまり、ある数a、b、cに対して、a ☆ b = cとなるとします。「可換」とは、a ☆ b = b ☆ aということです。実際には、ブルートフォースbrute-force攻撃（またはブルートフォースに近い攻撃）によってのみ、aに対してあらゆる可能性を試すことで、aが何であるかを知ることができるはずです。☆は乗算記号のようなものと考えてもよいでしょう。(なお普通の乗算は可換ですが一方通行ではありません。数学に興味のある方へ： 実際のDiffie-Hellmanでは、☆をべき剰余で実装できます。)
下の図は、アサタとボビーがある数字pに合意し、それを公開(1)します。アサタは秘密の数aを選び(2)、p ☆ aを計算し(3)、その結果をボビーに送ります。ボビーは秘密の数字bを選び(4)、p ☆ bを計算して、その結果をアサタに送ります(5)。アサタはボビーからのメッセージ(5)と自分の秘密番号(6)を使って、(p ☆ b) ☆ a (7)を計算します。ボビーは，アサタからのメッセージ(3)と自分の秘密の番号(4)を使って，(p ☆ a) ☆ b (8)を計算します．☆は可換なので、(p ☆ b) ☆ a = (p ☆ a) ☆ b となり、アサタとボビーがそれぞれ計算しても、同じ結果になるのです。盗聴者は p ☆ a, p ☆ b, それに p しか知らず、☆は一方通行なので、盗聴者はアサタとボビーの共有共通番号を計算する効率的な手段を持っていません。それはアサタとボビーの秘密です。アサタとボビーは、この共有する数を暗号鍵として使用することができます。
秘密鍵の合意
ディフィー・ヘルマン鍵交換の利用
ディフィー・ヘルマン鍵交換は、暗号鍵を合意するための手段としてあちこちで使用されています。この鍵交換は、皆さんが遭遇するほとんどの暗号化通信の基礎として使用されています。特に、httpsでWebサイトに接続する際の鍵交換の基本となっています。あなたがウェブサイトにアクセスするとき、URLは http:// または https:// で始まります。前者の場合、ウェブサイトのサーバーとの通信は一切暗号化されません。後者の場合、通信は暗号化され、その通信を暗号化するための鍵はDiffie-Hellman鍵交換で生成されます。
コンテクスト： 良いことが悪いことに
アサタとボビーが最初に行うことは、鍵交換の基礎となる数字pに合意することです。この数字は公開されていますが、私たちは数学の演算☆が一方通行であることを前提にしていたので、pが公開されていても問題ありませんでした。しかし、多くの計算資源を持っている人（裕福な国民国家など）は、2つの段階を経て（現実世界で☆に使われているべき剰余などの関数の）演算☆を反転させることができます。第1段階は、非常に長い時間をかけて、特定のpの値に対して行わなければなりません。第2段階は、第1段階が完了していると仮定して、同じpの値に対して非常に早く（リアルタイムで）行うことができます。つまり、同じ値pを使用するのではなく、異なる値pを使用し、頻繁に変更するべきなのです。
しかし、2015年に研究者が示したところによると、上位100万のhttpsドメインのうち18％が同じ値pを使用しているとのことです。ディフィー・ヘルマン鍵交換に依存している通信プロトコルには、他にもSSH（secure shell）とVPN（virtual private network）があります。同じ研究者は、SSHサーバーの26％とVPNサーバーの66％がディフィー・ヘルマン鍵交換に同じ値のpを使用していることを示しました。これは、強力な敵が暗号を解読するのにほとんど苦労しないことを意味します。
ディフィー・ヘルマンプロトコルは強力で信頼性の高いものですが、プロトコルを実装する側は、実際に安全であることを確認するために慎重に行う必要があることが浮き彫りになりました。
次に学ぶべきこと
中間者
公開鍵暗号方式
外部リソース
Adrian, David, Karthikeyan Bhargavan, Zakir Durumeric, Pierrick Gaudry, Matthew Green, J. Alex Halderman, Nadia Heninger, et al. “Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice.” In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, 5-17. デンバー。ACM, 2015.
メディアへの帰属
lockbox © OSU OERU is licensed under a CC BY-NC (Attribution NonCommercial) license
diffie-hellman-concept © Lorddota adapted by OSU OERU is licensed under a CC BY-SA (Attribution ShareAlike) license
diffie-hellman © Lorddota adapted by OSU OERU is licensed under a CC BY-SA (Attribution ShareAlike) license
暗号化ハッシュ
(訳注：前項で「次に学ぶべきこと」として記載されている「中間者」はこの次に説明されています)
本章を読む前に、「現代の暗号」の章を読むことをお勧めします。
この章で学ぶこと
1. ハッシュ関数とは何か
2. 暗号ハッシュ関数とは何か、通常のハッシュ関数との違いは何か
3. 暗号化ハッシュ関数の使用例
ハッシュ関数とは、任意の大きさのデータ（名前、文書、コンピュータプログラムなど）を、固定の大きさのデータ（3桁の数字、16ビットの数字など）に変換する（コンピュータの）関数のことです。ハッシュ関数の出力は、（入力メッセージの）ダイジェスト、フィンガープリント、ハッシュ値、またはハッシュと呼ばれます。
暗号化ハッシュ関数は、以下のような特性を持ち、暗号化アプリケーションにとって有用なものです。
1. 同じメッセージは常に同じ出力ハッシュになる。
2. 入力メッセージから出力ハッシュ値を生成することは、総当り（可能な入力メッセージをすべて試す）以外では不可能である。
3. 同じ出力ハッシュ値になる2つの異なる入力メッセージを見つけることは不可能である。
4. 入力メッセージへの小さな変更は、新しいハッシュ値が元のハッシュ値と無相関に見えるほど、出力ハッシュ値が大きく変化する。
これらの特性のうち、最初の2つはほとんどの暗号化プロトコルと同じ性質のものです。同じメッセージを2回別々に暗号化した場合、同じ暗号鍵を使用していると仮定すれば、同じ結果が得られるはずです。暗号文だけしかなければ、（復号鍵なしで）平文を生成することは不可能なはずです。しかし、暗号化は、復号鍵を使って、暗号文から平文へと遡ることができます。ハッシュ関数は本質的に一方通行であり、逆のことができるための鍵はありません。暗号ハッシュ関数の出力は、（暗号文のように）入力メッセージのすべての情報を暗号化しているわけではありませんが、入力を識別するのに十分な情報を暗号化しており（性質1と3に依存）、これを偽造することは極めて困難です（性質2）。
暗号ハッシュ関数の応用例は、「中間者」「パスワード」「公開鍵暗号」の章で紹介しますが、ここでは簡単な使い方として、コミットメント・スキームcommitment schemeを見てみましょう。
自分の頭の良さを証明する暗号化ハッシュ関数の使い方
アサタとボビーの二人が難しい数学の問題を解こうとしています。アサタは先に答え(S)を手に入れ、、ボビーに答えを漏らさずに、ボビーが解く前に自分が答えを持っていることを証明したいと考えています。そこで、アサタは解答Sの暗号化されたハッシュをhash(S)とし、ボビーにhash(S)を渡します。ハッシュは暗号化されているので、ボビーはhash(S)からSを知ることはできません（性質2）。ボビーが最終的に問題を解き、自分でSを見つけたとき、彼はhash(S)を計算し、その結果がアサタが彼に与えたものと同じであることを確認することができます。特性1と3により、ボビーはアサタのハッシュ関数への入力と自分のハッシュ関数への入力が同じに違いないことがわかり、アサタが先に問題を解決したことが証明されます。(特性4はここでは使われていませんが、この特性がないと、アサタが正解に近いが正解ではない解を得た場合、2つの出力は非常に似ていて、ざっと比較しただけでは違うことがわからない可能性があります)
ハッシュ関数はどのようなものか？
現在、様々な暗号化ハッシュ関数が使われていますが、それらを詳細に説明することは、本書の範囲を超えています。しかし、どのようなものかを知るために、暗号ハッシュ関数が持つ特性のすべてではないですが、いくつかの特性を満たす例を挙げてみよう。
ここでの例のハッシュ関数は、chunked XORと呼ばれるものです。排他的あるいはXORとは、一対の入力が与えられたときに、入力が異なる場合は真（または1）を出力し、そうでない場合は偽を出力する関数です。つまり、例えば、リンゴXORバナナ＝1、リンゴXORリンゴ＝0、0 XOR 1＝1、1 XOR 1＝0となります。2進数（0と1）のXORの連鎖を取ると、意味のある答えが得られる。すなわち、1 xor 1 xor 0 = 0, 1 xor 1 xor 0 xor 1 = 1です。2進数の列に対して、XORは、連鎖の中に奇数個の1があれば1を、そうでなければ0を返します。
chunked XORは、2進数の入力で動作します。(入力が2進数でない場合は、コンピュータと同じように、まず2進数で表現します)。入力をハッシュ関数の出力サイズと同じ大きさのチャンク（例えば8ビットのグループ）にグループ分けします。その塊を縦に並べて、各列の内容をXORすると、下図のようになります。
これは、入力の長さに関係なく、出力が常に同じ長さ（この例では8）になるという点で、ハッシュ関数です。chunked XORは、暗号ハッシュ関数の最初の特性を満たしていることがお分かりいただけると思います。しかし、残りの特性についてはうまくいっていません。例えば、入力メッセージ(必ずしもあなたの望むような入力メッセージだとは限りませんが)を所与の出力ハッシュで生成することは簡単です。例えばハッシュの結果に 11111111 11111111 を連結すると、そのハッシュとなる入力メッセージが作れるのです。
同じ理由から、同じ出力ハッシュとなるメッセージをいくつでも作ることができます。最後に、入力メッセージの1ビットだけ変更してみると、出力ハッシュは1ビットしか変化しません。
コンテクスト： 暗号化ハッシュは憲法修正第4条の権利を侵害する
2008年、米国の地方判事は、米国政府が個人のデータを暗号ハッシュ化したい場合は、まず令状が必要であるという判決を下しました。この事件では、ペンシルバニア州司法長官(the Pennsylvania Office of the Attorney General)事務所の特別捜査官が、容疑者のコンピュータのハードドライブをコピーしました。特別捜査官は、コピーの暗号ハッシュを計算しました（特性1と3を利用して、改ざんしていないことを証明するために、後からオリジナルと比較できるようにしたのです）。次に、フォレンジックツールを使って、コピーしたハードディスク上の個々のファイル（削除されたがまだ上書きされていないファイルを含む）の暗号ハッシュを計算し、これらのハッシュを、禁制品ファイルのデータベースにあるファイルのハッシュと比較しました。捜査官は、ハードドライブ上のファイルのハッシュと禁制品ファイルのハッシュの間に3つのマッチを発見しました。プロパティ1と3により、ハードドライブには少なくとも3つの違法ファイルが含まれていることになります。この事件を担当した裁判官は、この行為（ファイルをハッシュ化して既知のハッシュと比較すること）がハードドライブの捜索にあたると判断し、違法な捜索や押収からの保護に関する被告人の憲法修正第4条の権利を侵害したとしました。その結果、この証拠は裁判で使用することができませんでした。
私たちは、児童ポルノの所持に関わるこの事件の詳細を開示すべきだと考えています。私たちは、児童ポルノの所持（または作成や配布）の権利を擁護することはありませんが、権力（この場合は、コンピュータ上の特定のファイルの存在を決定する権力）が、例えば、友人があなたと共有していた音楽、原油流出の画像、#blacklivesmatterデモの画像、Earth First! ジャーナル記事とか、利用されたくないやり方でで利用する場合のことを想定することは重要です。
次に学ぶべきこと
パスワードについて
中間者
暗号化された署名による真正性
外部リソース
アメリカ合衆国 v. ロバート・エルズワース・クリスト（III）、被告。刑事訴訟番号1:07-cr-211。627 F.Supp.2d 575 (2008).
中間者
本章をお読みになる前に、「暗号化のための鍵の交換」および「暗号化ハッシュ」の章をお読みになることをお勧めします。
学ぶべきこと
