概要

本

• ​暗号技術入門 | 結城 浩​

かかった時間

• 27.4 時間

感想

• とても読みやすい。数式ほぼ出てこない

• 暗号技術についてわかりやすく解説されている

• 次は実装したり、数学使ったりする本読みたい

  • あと暗号以外のセキュリティも学んでみたい

読書メモ

第 1 部: 暗号

1: 暗号の世界ひとめぐり

暗号

• 暗号は機密性を守る

  • 機密性: 決められた人だけが対象のデータにアクセスできるようにすること

対称暗号と公開鍵暗号

• 対称暗号(symmetric cryptography)と公開鍵暗号(public-key cryptography)

  • 「対称暗号」は暗号化と復号化で同じ鍵を使う方式

  • 「公開鍵暗号」は暗号化と復号化で異なる鍵を使う方式

    • このため公開鍵暗号は、「非対称暗号(asymmetric cryptography)」と呼ぶこともある

• ハイブリッド暗号システム(hybrid cryptography)

  • 対称暗号と公開鍵暗号を組み合わせた暗号方式が「ハイブリッド暗号システム」

その他の暗号技術

• 一方向ハッシュ関数(詳しくは 7 章)

  • 書き換えを防止するため、セキュリティを意識しているプログラムの提供者は、プログラムを広く公開すると共に、そのプログラムのハッシュ値というものも公開する場合がある

  • ハッシュ値とは「一方向ハッシュ関数」を使って計算した値

  • 一方向ハッシュ関数が提供しているものは、機密性ではなく「正真性(integrity)」。正真性は完全性とも呼ばれる

  • 一方向ハッシュ関数を使えば、データが改ざんされていないかどうかを調べられる

• メッセージ認証コード(message authentication code。詳しくは 8 章)

  • メッセージが期待した通信相手から来たものであることを確かめるために、「メッセージ認証コード」という技術が使われる

  • メッセージ認証コードを使うと、そのメッセージが改ざんされていないことと、期待した通信相手からのものであることを確かめられる

  • 正真性だけでなく、「認証(authentication)」も提供してくれる

• デジタル署名

  • 改ざん、否認という脅威を防ぐ技術が「デジタル署名」

    • 否認: 自分の主張をあとで翻すこと。メールを送ったのに、送ってないと主張するなど

  • メールの場合、送信者がデジタル署名を施してメールを送り、受信者はデジタル署名を検証する。これによって、正真性を確かめ、認証と否認防止を行う

• 疑似乱数生成器(pseudo random number generator: PRNG)

  • 「疑似乱数生成器」は、乱数列を擬似的に生成するアルゴリズム

暗号学者の道具箱

• 以下の 6 つの技術は特に重要な役割を果たす

  • 対称暗号

  • 公開鍵暗号

  • 一方向ハッシュ関数

  • メッセージ認証コード

  • デジタル署名

  • 疑似乱数生成器

ステガノグラフィ(steganography)と電子透かし

• メッセージの内容を読めないようにするのではなく、メッセージの存在そのものを隠してしまうのが「ステガノグラフィ」

  • しかし、いったんメッセージの埋め込み方法が解明されてしまうと、メッセージの内容はすぐにわかってしまう

  • なので、ステガノグラフィは暗号の代わりにはならない

• 最近では、「電子透かし」という技術にステガノグラフィが使われる

  • 電子透かしとは、ファイルの中に著作権者や購入者の情報を埋め込む技術

  • 電子透かし技術だけでは、情報を機密にしておくことはできないので、他の技術と組み合わせる必要がある

• 例えば暗号とステガノグラフィを組み合わせるのは、よく使われる

  • まず、埋め込みたい文章を暗号化して暗号文を作る

  • その上で、ステガノグラフィを使って暗号文を画像ファイルの中に隠す

  • このようにすれば、暗号文の存在に気づかれても、埋め込みたい文章の内容は読まれない

暗号とセキュリティの常識

• 以下は暗号を学び始めた人が最初にひっかかるポイント

• 秘密の暗号アルゴリズムは使うな

  • 秘密のアルゴリズムではなく、公開されていて強い暗号アルゴリズムを使うべき

  • 理由 1: 暗号アルゴリズムの秘密は必ず暴かれる

    • 歴史的に、暗号アルゴリズムの秘密が暴かれなかった例は 1 つもない

    • 暗号アルゴリズムそのものを秘密にして機密性を保とうとしている暗号システムは、暗号アルゴリズムの詳細が暴かれてしまったら終わり

  • 理由 2: 強い暗号アルゴリズムを生み出すことは非常に困難

    • 数学のように、暗号アルゴリズムの強さを証明することはできない。専門の暗号解読者たちが、その暗号アルゴリズムを解読しようと何年も試みて失敗した、という事実だけが暗号の強さを示す

• 弱い暗号は暗号化しないよりも危険である

  • ユーザーが「暗号」という言葉によって「誤った安心感」を抱きやすいため

• どんな暗号もいつかは解読される

  • どんな暗号アルゴリズムで作った暗号文でも、すべての鍵をしらみ潰しに試すことによって、いつかは必ず解読される

• 暗号はセキュリティのほんの一部である

  • 暗号アルゴリズムが破られなくても、メールの内容を知る方法は無数にある

  • 複雑なシステムは、たくさんのリンクが繋がった鎖のようなもの。システムの強さは、最も弱いリンクの強さにほかならない

  • そして、最も弱いリンクは暗号ではなく人間

2: 歴史上の暗号

シーザー暗号(Caesar cipher)

• 「シーザー暗号」は紀元前 100 年頃にローマで生まれ、活躍した武将シーザーが使っていたと言われる暗号

• シーザー暗号では、平文で使われているアルファベットを、一定の文字数だけずらすことによって暗号化を行う

• ブルートフォースアタック(brute-force attack)

  • すべての鍵の候補を試す暗号解読の方法

  • 全数探索(exhaustive search)、総当り法、しらみつぶし法などと呼ばれる

単一換字暗号(simple substitution cipher)

• 平文を構成するアルファベットを別のアルファベットへ変換する暗号のことを「単一換字暗号」と呼ぶ。シーザー暗号は単一換字暗号の 1 つ

• 単一換字暗号は、ブルートフォースアタックで解読することは困難

  • シーザー暗号に比べ、はるかに多くの鍵の候補を持つため

• ある暗号で使うことができる「すべての鍵の集合」のことを「鍵空間(keyspace)」といい、可能な鍵の総数のことを鍵空間の大きさという

• 頻度分析による解読

  • 暗号文に使われている文字の頻度を調べて解読する

エニグマ

• 「エニグマ(enigma)」はドイツのシェルビウスによって 20 世紀のはじめに発明された、暗号化・復号化を行う機械

• エニグマの構造(p35)

  • エニグマは打鍵ごとに 3 枚のローターが回転して回路が変化するあみだくじのようなもの

なぜ暗号アルゴリズムと鍵とを分けるのか

• 暗号アルゴリズムの中には「変更可能な部分」が必ず含まれる

  • この「変更可能な部分」が「鍵」に相当する

• もし、暗号化を行うたびに新しい暗号アルゴリズムを生み出さなければならないとしたら大変。私達は一度開発した暗号アルゴリズムを繰り返し使いたい

  • しかし、同じ暗号を繰り返し使っていると解読される可能性が高くなる

  • なので、暗号アルゴリズムに「変更可能な部分」を用意しておき、通信ごとにそれを変える。それが「鍵」

3: 対称暗号(共通鍵暗号)

文字の暗号からビット列の暗号へ

• 符号化(encoding)

  • 現実世界にあるものをビット列に対応付けることを「符号化」と呼ぶ

• XOR(exclusive or)

  • 排他的論理和

  • 0 XOR 0 = 0 / 0 XOR 1 = 1 / 1 XOR 0 = 1 / 1 XOR 1 = 0

  • 同じビット列を 2 回 XOR で重ねると、元に戻る。この性質は暗号化・復号化の手順によく似ている

使い捨てパッド - 絶対に解読できない暗号

• 使い捨てパッド(one-time pad)

  • 使い捨てパッドは、ブルートフォースアタックで鍵空間をすべて探索したとしても絶対に解読できない暗号

  • 使い捨てパッドは「平文と、ランダムなビット列との XOR をとる」というだけのシンプルな暗号

• 使い捨てパッドは解読できない

  • もし復号が行われたとしても、「それが正しい平文なのかどうか判定できない」というのが特徴

  • 解読不可能であることは 1949 年に数学的に証明され、使い捨てパッドは無条件に安全であり(unconditionally secure)、理論的に解読不可能(theoretically unbreakable)

• 使い捨てパッドはバーナム暗号(Vernam cipher)とも呼ばれる

• 使い捨てパッドはなぜ使われないのか

  • 使い捨てパッドは非常に使いにくい暗号のため、実際にはほとんど使われない

  • 問題点

    • 鍵の配送

    • 鍵の保存

    • 鍵の再利用ができない

    • 鍵の同期

    • 鍵の生成

  • 以上の理由から、使い捨てパッドが用いられるのは、鍵の生成と配送に莫大なお金と手間をかけることができ、機密性が最優先事項である場合のみ

  • このように、使い捨てパッドは実用的な暗号ではないが、このアイデアはストリーム暗号(stream cipher)に生かされている。ストリーム暗号について詳しくは 4 章で扱う

DES

• DES(Data Encryption Standard) とは

  • DES は 1977 年にアメリカの連邦情報処理標準規格に採用された対称暗号

  • コンピュータの進歩のため、現在はブルートフォースアタックで解読できるレベルまで落ちてしまった

• 暗号化・復号化

  • DES は 64 ビットの平文を 64 ビットの暗号文に暗号化する対称アルゴリズム。鍵のビット長は 56 ビット(鍵は 64 ビットだが、7 ビットおきにエラー検出のための情報が 1 ビット入るので実質的に 56 ビット)

  • DES では 64 ビットの平文をまとめて暗号化する。このまとまりを「ブロック」と呼ぶ

    • ブロック単位で処理を行う暗号アルゴリズムは「ブロック暗号(block cipher)」と呼ぶので、DES はブロック暗号の一種になる

• DES の構造(ファイステルネットワーク)

  • ファイステルネットワークでは、ラウンドと呼ばれる暗号化の 1 ステップを何度も繰り返す

  • DES は、ラウンドを 16 回繰り返すファイステルネットワーク

• 1 ラウンドは以下のように進む

  • ラウンドへの入力を、左と右とに分ける

  • 右をそのまま右に送る

  • 右をラウンド関数 f に送る

  • ラウンド関数 f は、右とサブ鍵を使って、ランダムに見えるビット列を計算する

  • 得られたビット列と、左との XOR を計算した結果を暗号化された左とする

• ファイステルネットワークの性質

  • 好きなだけラウンド数を増やせる

  • ラウンド関数 f にどんな関数を使っても、復号化が可能

    • つまりラウンド関数 f そのものは出力から入力が逆算できなくても良い

  • 暗号化と復号化が全く同じ構造で実現できる

• 差分解読法と線形解読法

  • ブロック暗号に対する暗号解読法の 1 つに「差分解読法」がある

    • これは「平文の一部を変更すると暗号文がどう変化するか」を調べる暗号解読法

    • 暗号文の変化の偏りを調べて、解読の手がかりを得る

  • 線形解読法

    • 「平文と暗号文のビットをいくつか XOR して 0 になる確率を調べる」という解読方法

    • 暗号文が十分にランダムになっているなら、平文と暗号文のビットをいくつか XOR した結果が 0 になる確率は 1/2 のはず。そこで 1/2 からのずれが大きいビットの箇所を調べて、鍵に関する情報を得ようというもの

  • 差分解読法や線形解読法では、暗号解読者が任意の平文を暗号化できるという仮定を置く。このことを「選択平文攻撃(Chosen Plaintext Attack: CPA)」という

トリプル DES

• トリプル DES(triple-DES)とは何か(p64)

  • DES よりも強力になるよう、DES を 3 段重ねにした暗号アルゴリズム

• トリプル DES の暗号化

  • 「暗号化 -> 暗号化 -> 暗号化」ではなく「暗号化 -> 復号化 -> 暗号化」と処理する

  • トリプル DES で 3 つの鍵をすべて等しくすると、トリプル DES はただの DES に等しくなる

• トリプル DES の復号化

  • 暗号化の逆の順で復号化できる

• トリプル DES の現状

  • 銀行などでまだ使われているが、処理スピードはあまり高くない

AES の選定プロセス

• AES とは何か

  • AES(Advanced Encryption Standard) はこれまで標準であった DES に代わって、新しい標準となる対称暗号アルゴリズム

  • 世界中の企業や学者から AES の候補としてアルゴリズムが提案され、その中から「Rijndael」という対称アルゴリズムが 2000 年に AES として選定された

Rijndael

• Rijndael とは何か

  • ベルギーの研究者が設計したブロック暗号アルゴリズムで、2000 年に次世代の標準アルゴリズム AES として選定された

  • AES は世界中で広く使われている対称暗号アルゴリズムであり、どんな暗号ソフトウェアも AES をサポートしているはず

• Rijndael の暗号化と復号化

  • Rijndael は DES と同じく、複数のラウンドから構成される

  • ファイステルネットワークではなく、「SPN 構造」という構造が使われている

  • 1 ラウンドは以下の 4 つの処理を行う

    • SubBytes(バイトごとの置換)

    • ShiftRows(行のシフト)

    • MixColumns(列の混合)

    • AddRoundKey(ラウンド鍵との XOR)

• どの対称暗号を使えばよいのか

  • DES は新しい用途には使うべきではない

  • トリプル DES も新しい用途に使うべきではない

  • 現在使うなら AES が良い

  • 一般に自作のアルゴリズムも使うべきではない

まとめ

• 大きな鍵空間を持ち、アルゴリズム上の弱点を持たない対称暗号を用いると、暗号文によって平文の機密性を守れる

• しかし、対称暗号を使って通信を行うためには、鍵を安全に受信者に送らなければならないという鍵配送問題が残る

  • この問題の解決のためには、公開鍵暗号の技術が必要になる

4: ブロック暗号のモード

ブロック暗号のモード

• 暗号アルゴリズムはブロック暗号とストリーム暗号の 2 つに分けられる

  • 「ブロック暗号(block cipher)」はある特定のビット数の「まとまり」を一度に処理する暗号アルゴリズムの総称

    • この「まとまり」のことを「ブロック」と呼ぶ

    • 例えば DES やトリプル DES のブロック長は 64 ビット、AES は 128 ビット

  • 「ストリーム暗号(stream cipher)」はデータの流れを順次処理していく暗号アルゴリズムの総称

    • ストリーム暗号では、1 ビット・8 ビット・32 ビットなどの単位で暗号化や復号化が行われる

  • ブロック暗号は、ブロック単位で処理が完了するので、どこまで暗号化が進んだかという内部状態を持つ必要はない

  • 一方、ストリーム暗号はデータの流れを順次処理していくので、内部状態を持つ

• モードとは何か

  • 長い平文を暗号化するためには、ブロック暗号アルゴリズムを繰り返し使って、長い平文全部を暗号化する必要がある

    • この繰り返しの方法のことを、ブロック暗号の「モード」と呼ぶ

  • ブロック暗号の主なモードは以下の 5 種類

    • ECB モード: Electronic CodeBook mode(電子符号表モード)

    • CBC モード: Cipher Block Chaining mode(暗号ブロック連鎖モード)

    • CFB モード: Cipher-FeedBack mode(暗号フィードバックモード)

    • OFB モード: Output-FeedBack mode(出力フィードバックモード)

    • CTR モード: CounTeR mode(カウンタモード)

• 平文ブロックと暗号文ブロック

  • 平文ブロック: ブロック暗号アルゴリズムで暗号化の対象となる平文のこと

  • 暗号文ブロック: ブロック暗号アルゴリズムを使って平文ブロックを暗号化した暗号文

ECB モード

• ECB モードとは何か(Electronic CodeBook mode、電子符号表モード)

  • ECB モードでは、平文ブロックを暗号化したものが、そのまま暗号文ブロックになる

  • 同じ平文ブロックは、同じ暗号文ブロックに変換される。つまり「平文ブロック→暗号文ブロック」という巨大な対応表を想定できる

  • ここから電子符号表モードという名前がついた

• ECB モードの特徴

  • たくさんあるモードの中でも最もシンプルで、最も機密性が低い

• ECB モードへの攻撃

  • 攻撃者マロリーは暗号を解読せずに平文を操作できる

  • 任意の暗号文ブロックを入れ替えると、対応する平文ブロックが入れ替わってしまう

CBC モード

• CBC モードとは何か(Cipher Block Chaining mode、暗号ブロック連鎖モード)

  • 暗号ブロックをチェーンのように連鎖させる

  • CBC モードでは 1 つ前の暗号文ブロックと平文ブロックの XOR をとってから暗号化を行う

• 初期化ベクトル

  • 最初の平文ブロックを暗号化するときには「1 つ前の暗号文ブロック」は存在しないので、代わりのビット列を 1 ブロック分用意する必要がある

  • このビット列のことを「初期化ベクトル(initialization vector)」または IV と呼ぶ

  • 初期化ベクトルには、暗号化のたびに異なるランダムなビット列を用いるのが普通

• CBC モードの特徴

  • 平文ブロック 1 と 2 の値が等しい場合でも、暗号文ブロック 1 と 2 の値が等しくなるとは限らない

    • ECB モードが持つ欠点は、CBC モードにはない

  • 復号化のときに、もし暗号文ブロックが 1 つ破損したとすると、平文ブロックに与える影響は 2 ブロック

  • もし暗号文ブロックでビットの欠落があったとすると、その暗号文ブロックの長さは変化してしまい、それ以降のブロックの区切りはずれてしまう。この場合、以降の暗号文ブロックはすべて復号化できなくなる

• CBC モードへの攻撃

  • もしマロリーが初期化ベクトルの任意のビットを反転できるなら、そのビットに対応する平文ブロックのビットを反転させられる

  • 初期化ベクトルに対してマロリーの攻撃は可能だが、暗号文ブロックに対する同様の攻撃は困難

• パディングオラクル攻撃

  • ブロック暗号では、平文の長さがブロックサイズの整数倍にならない時、最後のブロックにパディング(詰め物)というデータが必要になる場合がある

  • 攻撃者はパディング内容を少しずつ変化させて暗号文を何度も送信する

  • 受信者は正しく平文に復号化できなかった場合にエラーを返すので、それを使って平文の情報の一部を得ようとする

  • この攻撃は、CBC に限らず、パディングを行うモードすべてに使える

  • 実際に、この攻撃は 2014 年に大問題になった

  • 暗号文が平文を知っている相手によって正しく生成されたものであることを認証すれば、この攻撃を防げる

CFB モード

• CFB モードとは何か(Cipher-FeedBack mode、暗号フィードバックモード)

  • 1 つ前の暗号文ブロックを暗号アルゴリズムの入力に使う

  • 平文ブロックと暗号文ブロックの間にあるのは XOR だけ

• CFB モードとストリーム暗号

  • 使い捨てパッドに近い。使い捨てパッドの「ランダムなビット列」に相当するのが、CFB モードでは「暗号アルゴリズムの出力」

  • CFB モードで暗号アルゴリズムが生成するビット列のことを「鍵ストリーム(key stream)」と呼ぶ

  • CFB モードでは、平文のデータを 1 ビットずつ暗号化できる。CFB モードではブロック暗号を使ってストリーム暗号を作っているとみなすこともできる

• CFB モードの復号化

  • CFB モードで復号化を行う場合、ブロック暗号アルゴリズムそのものは暗号化を行う

• CFB モードへの攻撃

  • 「再生攻撃(replay attack)」が可能

  • 古い暗号文を保存しておいて、混ぜ込むことができる

OFB モード

• OFB モードとは何か(Output-FeedBack mode、出力フィードバックモード)

  • 暗号アルゴリズムの出力を暗号アルゴリズムの入力へフィードバックする

• CFB モードと OFB モードの比較

  • CFB モードと OFB モードでは、暗号アルゴリズムの入力だけが違う

  • CFB モードでは、暗号文ブロックをフィードバックするため、はじめの平文ブロックから順番に暗号化していく必要がある

  • OFB モードでは、平文ブロックとは無関係に暗号アルゴリズムを前もってぐるぐる回し、XOR するためのビット列を準備しておくことができる

    • なので準備しておけば、暗号化を高速に行える

CTR モード

• CTR モード(CounTeR mode、カウンタモード)

  • 1 ずつ増加していくカウンタを暗号化して、鍵ストリームを作り出すストリーム暗号

• OFB モードと CTR モードの比較

  • CTR モードは OFB モードと同じストリーム暗号の一種

  • OFB モードでは暗号化の出力を入力にフィードバックするが、CTR モードではカウンタの値が暗号化の入力になる

• CTR モードの特徴

  • CTR モードの暗号化と復号化はまったく同じ構造になる。これは OFB モードと同じストリーム暗号の特徴

  • CTR モードでは、ブロックを任意の順番で暗号化・復号化できる。「カウンタ」はノンスとブロック番号からすぐに求めることができるため

    • これは OFB モードにはなかった性質

• エラーと機密性

  • CTR モードでは、能動的攻撃者マロリーが暗号文ブロックのビットを反転させることで、復号化した時の平文ブロックのビットを反転できてしまう

    • OFB モードと同じ弱点

  • OFB モードでは、鍵ストリームの 1 ブロックを暗号化した結果が、暗号化前の結果とたまたま同じになってしまうと、それ以降、鍵ストリームはまったく同じ値の繰り返しになってしまう

    • CTR ではその心配はない

どのモードを使うべきか

• ECB は使うべきではない

• 比較表は p107 にあり

5: 公開鍵暗号

配送鍵問題とは(key distribution problem)

• 対称暗号では、鍵を送らなければ復号化できない

• しかし、鍵を送ったら、攻撃者にも復号化されてしまう

• これに対する解決方法

  • 鍵の事前共有による解決

  • 鍵配布センターによる解決

  • Diffie-Hellman 鍵交換

  • 公開鍵暗号による解決

• 鍵の事前共有による鍵配送問題の解決

  • 安全な方法で、鍵を前もって渡しておく

  • 隣の席の人と鍵を事前共有するのは簡単だが、メールや郵送で共有するのは安全ではない

  • また人数が多くなると、膨大な数になってしまう

• 鍵配布センター(key distribution center: KDC)による鍵配送問題の解決

  • 暗号通信が必要になるたびに、通信用の鍵を鍵配布センターに作ってもらい、各人は鍵配布センターとの間だけで鍵を事前共有する

  • この場合も、社員が多くなればなるほど、鍵配布センターの負荷が大きくなる

  • また鍵配布センターのコンピュータが故障すると、全社の暗号通信が麻痺する

  • また、攻撃者が鍵配布センターのコンピュータに侵入し、鍵のデータベースが盗まれてしまうリスクがある

• Diffie-Hellman 鍵交換による鍵配送問題の解決

  • 11 章で詳しく扱う

• 公開鍵暗号による鍵配送問題の解決

  • 公開鍵暗号では「暗号化の鍵」と「復号化の鍵」は別のもの

公開鍵暗号

• 公開鍵暗号(public-key cryptography)とは

  • 「公開鍵暗号」では「暗号化の鍵」と「復号化の鍵」をわける

  • ポイント

    • 送信者が必要なのは「暗号化の鍵」だけ

    • 受信者が必要なのは「復号化の鍵」だけ

    • 盗聴者に知られて困るのは「復号化の鍵」だけ

    • 「暗号化の鍵」は盗聴者に知られても構わない

• 公開鍵を使った暗号化の流れ(アリスが送信者、ボブが受信者)

  • 1: ボブは公開鍵・プライベート鍵(復号鍵)の鍵ペアを作る

  • 2: ボブは自分の公開鍵をアリスに送る

  • 3: アリスはボブの公開鍵を使って、メッセージを暗号化する

  • 4: アリスは暗号文をボブに送る

  • 5: ボブは自分のプライベート鍵を使って、暗号文を復号化する

• 様々な用語

  • 公開鍵暗号と同じ意味で「非対称暗号(asymmetric cryptography)」という用語が使われることもある

  • プライベート鍵と同じ意味で「個人鍵」「秘密鍵」「非公開鍵」なども使われる

• 公開鍵暗号でも解決できない問題

  • 鍵配送問題は解決した

  • しかし「公開鍵の認証」の問題がある

  • また、公開鍵暗号は対称鍵暗号と比べて、処理速度が何百倍も遅い

時計演算

• mod の計算。省略

RSA

• RSA とは何か

  • RSA は公開鍵暗号アルゴリズムの 1 つ

  • RSA という名前は、3 人の開発者の名前の頭文字をとって付けられた

  • RSA は公開鍵暗号とデジタル署名に使える。デジタル署名は 9 章で詳しく扱う

• RSA による暗号化

  • RSA の暗号化は 暗号文 = 平文^E mod N という式で表現できる

  • この E と N の組が公開鍵。E は Encryption、N は Number の頭文字

• RSA による復号化

  • 式で表現すると 平文 = 暗号文^D mod N

  • この D と N の組がプライベート鍵。D は Decryption の頭文字

• 鍵ペアを作る

  • 1: N を求める

    • 大きな素数 p と q を用意し、N = p・q とする

  • 2: L を求める

    • L は暗号化にも復号化にも関わらないが、鍵ペアを作る時にだけ使われる

    • L = lcm(p-1, q-1)。L は p-1 と q-1 の最小公倍数

  • 3: E を求める

    • 1 < E < L かつ gcd(E, L) = 1 となるように E を定める

  • 4: D を求める

    • 1 < D < L かつ E・D mod L = 1 となるように D を定める

RSA への攻撃

• ブルートフォースアタックで D を見つける

  • E や D は N と同程度の大きさにできるので、D をブルートフォースアタックで見つけるのは困難

• E と N から D を求める

  • 「素数 p と q を暗号解読者に知られてはいけない」というのがポイント

  • N を素因数分解する攻撃

    • これができたら、p と q が漏洩する

    • 大きな数の素因数分解を高速にできる方法が発見されたら、RSA は解読できる

  • p と q を推測する攻撃

    • p と q は疑似乱数生成器で生成されるので、疑似乱数生成器の品質が悪いと p と q が暗号解読者に推測される恐れがある

• man-in-the-middle 攻撃(p142)

  • RSA を解読するわけではないが、機密性に対する非常に有効な攻撃

  • man-in-the-middle 攻撃は、攻撃者マロリーが送信者と受信者の間に入り込み、送信者に対しては受信者のように、受信者に対しては送信者のようになりすます攻撃

  • この攻撃を防ぐためには認証が必要になる。詳しくは 10 章

• 選択暗号文攻撃

  • 暗号アルゴリズムの強さを研究するときには、攻撃者が様々な情報を知り得ることを仮定する

  • 「選択暗号文攻撃」というのは「任意のデータを送信すると、それを暗号文と見なして復号化し、返信してくれるサービス」を攻撃者が利用できることを仮定した攻撃

    • このサービスを「複合オラクル(Decryption Oracle)」という

• RSA を改良して、選択暗号文攻撃に対しても安全になる方法を考える

  • 復号化の際に「正しい平文を知っている人でなければ作れない暗号文である」ことが判定できればいい

  • 言い換えると、暗号文を「認証」すればよい

  • 「RSA-OAEP(Optimal Asymmetric Encryption Padding)」はこのような考え方で RSA を改良したもの

  • RSA-OAEP の暗号化では、平文のハッシュ値と決まった個数の 0 などから作った「認証の情報」を平文の前に追加し、その後に RSA で暗号化する

  • 復号化した時に、もし先頭に正しい認証の情報がなければ、「平文を知っている人が作った暗号文ではない」と判断し、一定のエラーメッセージを返す(どんなエラーであるか細かく知らせない)

他の公開鍵暗号

• ElGamal 方式

  • RSA は素因数分解が困難なことを利用していたが、ElGamal 方式は mod N で離散対数を求めるのが困難なことを利用している

• Rabin 方式

  • これは mod N で平方根を求めるのが困難なことを利用している

• 楕円曲線暗号

  • RSA に比べてビット数を少なくできるのが特徴

公開鍵暗号に関する Q&A

• 公開鍵暗号の鍵長と対称暗号の鍵長は直接比較できない

  • また異なる暗号アルゴリズムの強さを比較するのは単純な話ではない

6: ハイブリッド暗号システム

ハイブリッド暗号システム

• 対称暗号と公開鍵暗号

  • 公開鍵暗号は鍵配送問題は解決できるが、以下の 2 つの問題が残る

    • 1: 公開鍵暗号は、対称暗号に比べて処理速度がずっと遅い

    • 2: 公開鍵暗号は、man-in-the-middle 攻撃に弱い

  • ハイブリッド暗号システムは、上記の 1 の問題を解決する方法

• ハイブリッド暗号システム(hybrid cryptosystem)

  • 対称暗号と公開鍵暗号の長所を生かすように組み合わせた方法

  • 手順

    • 1: メッセージは対称暗号で暗号化する

      • あとは鍵の機密性を守れば良い

    • 2: 対称暗号の暗号化で使うセッション鍵は、疑似乱数生成器で生成する

    • 3: セッション鍵は、公開鍵暗号で暗号化する

      • 対称暗号の鍵は短いのが普通なので、公開鍵暗号のスピードの遅さは気にならない

    • 4: 公開鍵暗号の暗号化で使う鍵は、ハイブリッド暗号システムの外部から与える

• 暗号化

  • 上記の手順で暗号化し、「対称暗号で暗号化されたメッセージ」と「公開鍵暗号で暗号化されたセッション鍵」を最後に結合する

  • 結合したものが、ハイブリッド暗号システム全体にとっての「暗号文」となる

• 復号化

  • まずメッセージとセッション鍵を分割するところから始まる

強いハイブリッド暗号システムとは

• 疑似乱数生成器

  • ハイブリッド暗号システムでは、セッション鍵を作るために疑似乱数生成器を使う

  • この品質が悪いと、作り出されるセッション鍵を攻撃者に推測されてしまう危険がある

• 対称暗号

  • 強い対称暗号アルゴリズムを用い、鍵長も十分に長くする

  • また、適切なブロック暗号のモードを用いる必要がある

• 公開鍵暗号

  • 強い公開鍵暗号アルゴリズムを用い、鍵長も十分に長くする

• 鍵長のバランス

  • どちらかが極端に短いと、攻撃がそちらに集中する可能性があるので、対称暗号と公開鍵暗号の鍵長は、どちらも同程度の長さにすることが望ましい

  • ただし、長期間の運用を考慮するなら、対称暗号よりも公開鍵暗号のほうを強くすべき

    • 対称暗号のセッション鍵が破られたときに解読されるのは今回の通信文だけだが、公開鍵暗号が破られたときには、過去から未来に渡る暗号通信のすべてが解読されてしまうため

第 2 部: 認証

7: 一方向ハッシュ関数

一方向ハッシュ関数とは何か

• マロリーがファイルを書き換えていないかどうか調べたい

  • 1 ビットでも異なっていたり、増えていたり、減っていたりしたら、それは本物ではない

  • このような意味で「本物である」性質のことを「正真性(integrity)」または「完全性」と呼ぶ

• 一方向ハッシュ関数(one-way hash function)とは

  • 一方向ハッシュ関数には、入力と出力がそれぞれ 1 つずつある。入力はメッセージと呼ばれ、出力はハッシュ値(hash value)と呼ばれる

  • メッセージを元にしてハッシュ値を計算する

  • ハッシュ値は、メッセージの正真性のチェックに使える

  • ハッシュ値の長さはメッセージの長さとは無関係。メッセージが何ビットでも、固定サイズのハッシュ値を計算する

• 一方向ハッシュ関数の性質

  • 任意長のメッセージから固定長のハッシュ値を計算する

  • ハッシュ値を高速に計算できる

  • メッセージが異なればハッシュ値も異なる

    • 2 つの異なるメッセージが同じハッシュ値を持つことを「衝突(collision)」という

    • 衝突を見つけることが困難な性質を「衝突耐性(collision resistance)」と呼ぶ

    • 一方向ハッシュ関数は、衝突耐性を持つ必要がある

  • 一方向性(one-way)を持つ

    • ハッシュ値からメッセージを逆算できないという性質

  • 用語について

    • 一方向ハッシュ関数は「メッセージダイジェスト関数(message digest function)」、「メッセージ要約関数」、あるいは「暗号的ハッシュ関数」などと呼ばれる

    • 一方向ハッシュ関数の入力となるメッセージは「プレ・イメージ」と呼ばれることもある

    • 一方向ハッシュ関数の出力となるハッシュ値は「メッセージダイジェスト(message digest)」や「フィンガープリント(fingerprint)」と呼ばれることもある

    • 正真性は「完全性」や「保全性」と呼ばれることもある

一方向ハッシュ関数の応用例

• ソフトウェアの改ざん検出

• パスワードを元にした暗号化(password based encryption: PBE)

  • PBE では、パスワードとソルト(疑似乱数生成器で生成したランダムな値)を混ぜた結果のハッシュ値を求め、それを暗号化の鍵に使う

  • 詳しくは 11 章で扱う

• メッセージ認証コード

  • メッセージ認証コードとは「送信者と受信者だけが共有している鍵」と「メッセージ」を混ぜ合わせ、そのハッシュ値を計算した値

  • 通信中のエラーや改ざん、なりすましを検出できる

  • メッセージ認証コードは SSL/TLS でも用いられる

• デジタル署名

  • デジタル署名とは、現実社会の署名や押印に相当する行為をデジタルの世界に持ち込んだもの

  • デジタル署名の処理には時間がかかるので、メッセージ全体に施すのではなく、メッセージのハッシュ値に対してデジタル署名を施す

• 疑似乱数生成器

  • 一方向ハッシュ関数を使って、疑似乱数生成器を構成できる

• ワンタイムパスワード(one-time password)

  • ワンタイムパスワードは、正当なクライアントであるかどうかをサーバーが認証するときに使う

  • この方式では、一方向ハッシュ関数を使って通信経路上に流れるパスワードが 1 回限りになるように工夫される

一方向ハッシュ関数の具体例

• MD4, MD5

  • MD4 は Rivest が 1990 年に作った一方向ハッシュ関数で、128 ビットのハッシュ値を持つ

    • しかし Dobbertin によって MD4 の衝突を見つける方法が考案され、安全ではない

  • MD5 は Rivest が 1991 年に作った一方向ハッシュ関数で、128 ビットのハッシュ値を持つ

    • MD5 の強衝突耐性はすでに破られている。すなわち、同じハッシュ値を持つ 2 つのメッセージを作り出す攻撃が可能になっているので、安全ではない

• SHA-1, SHA-256, SHA-384, SHA-512

  • SHA-1

    • SHA-1 は 160 ビットのハッシュ値を持つ一方向ハッシュ関数

    • 1993 年にアメリカの連邦情報処理標準規格として発表されたものを SHA と呼び、1995 年に発表された改訂版を SHA-1 と呼ぶ

    • SHA-1 の強衝突耐性は 2005 年に破られた

    • SHA-1 は互換性維持以外の目的の利用では推奨できない

  • SHA-256, SHA-384, SHA-512

    • それぞれ 256 ビット、384 ビット、512 ビットのハッシュ値を持つ

    • これらの一方向ハッシュ関数をまとめて「SHA-2」と呼ぶ場合もある

    • メッセージの長さには上限がある

    • SHA-2 の強衝突耐性はまだ破られていない

• RIPEMD-160

  • RIPEMD-160 は 1996 年に作られた 160 ビットのハッシュ値を持つ一方向ハッシュ関数

  • RIPEMD-128, RIPEMD-256, RIPEMD-320 という別バージョンもある

  • RIPEMD-160 は互換性維持以外の目的の利用では推奨できない

  • RIPEMD の強衝突耐性は 2004 年に破られたが、RIPEMD-160 はまだ破られていない

  • RIPEMD-160 はビットコインで使われている

• SHA-3

  • 2005 年に SHA-1 の強衝突耐性が破られたのを受け、NIST は 2007 年に新しい一方向ハッシュ関数の選定を開始した

  • 2012 年に選定が終了し、SHA-3 となった

SHA-3 の選定プロセス

• SHA-3 とは何か

  • SHA-3(Secure Hash Algorithm-3) は SHA-1 に代わって、新しい標準となる一方向ハッシュ関数アルゴリズム

  • 世界中の企業や暗号学者が SHA-3 の候補となるアルゴリズムを多数提案し、5 年間にわたる選定作業のあと 2012 年に KECCAK というアルゴリズムが SHA-3 として選定された

  • SHA-3 が決まったからと言って、SHA-2 が安全でなくなったわけではない。両者は共存する形で使われていく

• KECCAK が SHA-3 として選定された理由は以下の通り

  • SHA-2 とまったく異なる構造をしていること

  • クリーンな構成で解析しやすいこと

  • 多様なデバイスで動き、組み込み用途にも良いこと

  • ハードウェア上の実装で高い性能を示したこと

  • 他のファイナリストに比べて高いセキュリティマージンがあること

KECCAK

• KECCAK とは何か

  • SHA-2 のビット長にあわせて、SHA3-224, SHA3-256, SHA3-384, SHA3-512 の 4 種類が SHA-3 として規定されている

  • SHA-1 には 2^64 - 1 の、SHA-2 には 2^128 - 1 の入力サイズ制限があるが、KECCAK に入力サイズの制限はない

• スポンジ構造

  • KECCAK では SHA-1 や SHA-2 とは全く異なるスポンジ構造が使われている(p187)

  • KECCAK のスポンジ構造では、入力となるメッセージにパディングをほどこした後、吸収フェーズと搾出フェーズという 2 つのフェーズを通って出力となるハッシュ値が生成される

  • 吸収フェーズは以下のように進む

    • パディングされた入力メッセージを、r ビットごとに入力ブロックに分割する

    • まず「内部状態の r ビット」と「入力ブロック 1」の XOR を求め、それを「関数 f への入力」とする

    • 次に「関数 f の出力 r ビット」と「入力ブロック 2」の XOR を求め、それを再度「関数 f への入力」とする

    • これを入力ブロックが尽きるまで繰り返す

    • 入力ブロックが尽きると、吸収フェーズを終えて搾出フェーズに進む

  • 関数 f は b = r + c ビットの内部状態を操作するように実装される

    • r を「ビットレート」、c を「キャパシティ」と呼ぶ

  • 搾出フェーズは以下のように進む

    • まず「関数 f の出力のうち r ビット」を「出力ブロック 1」として記録し、出力全体(r + c ビット)は、関数 f へ再度入力する

    • 次に「関数 f の出力のうち r ビット」を「出力ブロック 2」として記録し、出力全体(r + c ビット)は、関数 f へ再度入力する

    • これを、必要なビット数の出力が得られるまで繰り返す

  • 関数 f の処理そのものは、吸収フェーズと搾出フェーズでまったく同じであり、関数 f の処理を行うたびにスポンジ構造の内部状態がかき混ぜられることになる

• デュプレクス構造(p189)

  • KECCAK ではスポンジ構造の変形として、デュプレクス構造も提案している

  • スポンジ構造では、入力をすべて吸収し終えたあとで出力が始まった。しかし、デュプレクス構造では入力と出力が同じスピードで進む

  • デュプレクス構造を用いると、ハッシュ値を求めるという用途だけでなく、疑似乱数生成器、ストリーム暗号、認証付き暗号、メッセージ認証コードなど暗号学者の道具箱の多くをカバーする用途としても利用できる

• KECCAK の内部状態

  • KECCAK の内部状態は 3 次元のビット配列

  • 1 ビットを表す小さな立方体が、b 個すなわち「5 × 5 × z 方向の数」だけ集まって、大きな直方体を作る

  • x, y, z のすべての方向を考えた 3 次元の内部状態全体を「ステート」と呼ぶ

  • 内部状態のうち 2 次元だけに注目するときには xz 平面を「プレーン」、xy 平面を「スライス」、yz 平面を「シート」と呼ぶ

  • 1 次元だけに注目するときには x 方向を「row」、y 方向を「column」、z 方向を「レーン」と呼ぶ

• 関数 KECCAK-f[b]

  • KECCAK の関数 f は実際には KECCAK-f[b] と呼ばれている

    • パラメータ b は内部状態のビット長を表し、「幅」と呼ぶ

  • KECCAK の仕様では、幅 b に 25, 50, 100, 200, 400, 800, 1600 の 7 種類があるが、SHA-3 ではこの中で最大の幅 b = 1600 が使われる

  • KECCAK-f[b] では、以下で説明する θ, ρ, π, χ, ι という 5 個のステップを 1 ラウンドとして 12 + 2l ラウンドを繰り返す関数

    • SHA-3 で使われる KECCAK-f[1600] の場合、ラウンド数は 24 になる

  • θステップ(p193)

    • 位置をずらした 2 本の column の 5 ビットを XOR で足し合わせ、それを目的のビットにさらに XOR で足し込む

  • ρステップ(p193)

    • z 方向のビット移動を行う

  • πステップ(p194)

  • χステップ(p194)

  • ιステップ

    • ラウンド定数と呼ばれる定数とステート全体のビットとの XOR を取る処理

• KECCAK への攻撃

  • これまでの一方向ハッシュ関数は、圧縮関数を繰り返し用いる MD 変換と呼ばれる処理を使って、ハッシュ値を求めるものがほとんどだった

    • MD4, MD5, RIPEMD, RIPEMD-160, SHA-1, SHA-2 などで用いられている

  • SHA-1 の攻撃を回避するために SHA-2 が作られたが、同じ MD 構造であることに変わりないので、SHA-2 に対しても SHA-1 と同じような攻撃が見つかるのではないかと懸念されている

  • 実際に使われる KECCAK への脅威となる攻撃方法はまだ見つかっていない

• 弱い KECCAK への攻撃コンテスト

どの一方向ハッシュ関数を使えばよいのか

• MD5 は安全ではないので、使ってはいけない

• SHA-1 は過去に作られたハッシュ値の確認に使う以外、新しい用途に使うべきではない

• SHA-2 は安全。使っていて問題はない

• SHA-3 も安全。使っていて問題はない

• 自作のアルゴリズムは使うべきではない

一方向ハッシュ関数への攻撃

• ブルートフォースアタック

  • マロリーはアリスが作った「百万円契約書」と同じハッシュ値を生成する「一億円契約書」を探す

  • これは一方向ハッシュ関数の「弱衝突耐性」を破ろうとする攻撃

  • 弱衝突性

    • ​暗号学的ハッシュ関数 - Wikipedia​

  • 原像攻撃: 1 つのハッシュ値が与えられ、そのハッシュ値を持つメッセージをどんなものでもいいから見つける攻撃

  • 第二原像攻撃: あるメッセージ 1 が与えられ、そのメッセージ 1 のハッシュ値と同じハッシュ値を持つ、別のメッセージ 2 を見つける攻撃

• 誕生日攻撃

  • マロリーはハッシュ値の等しい「百万円契約書」と「一億円契約書」を用意しようとする

    • ハッシュ値は何でも良いから、同じハッシュ値を生成する 2 つのメッセージを求めれば良い

  • これは一方向ハッシュ関数の「強衝突耐性」を破ろうとする攻撃

  • アリスが使うハッシュ値が 512 ビットだとすると、ブルートフォースアタックの試行回数は 2^512 回。誕生日攻撃の試行回数は 2^256 回なので、ブルートフォースアタックに比べると、試行回数は非常に少なくなる

一方向ハッシュ関数で解決できない問題

• 一方向ハッシュ関数では「改ざん」を検出できるが「なりすまし」を検出できない

• そのファイルが本当にアリスのものか調べるためには、正真性だけでなく「認証」が必要になる

  • 認証を行うための技術が「メッセージ認証コード」と「デジタル署名」

8: メッセージ認証コード

メッセージ認証コード

• メッセージ認証コード(message authentication code)とは何か

  • メッセージ認証コードは正真性を確認し、メッセージの認証を行う技術。頭文字をとって「MAC」と呼ばれる

  • メッセージ認証コードは、任意長のメッセージと、送信者と受信者が共有する鍵という 2 つの入力を元にして、固定ビット長の出力を計算する関数

  • 任意長のメッセージから固定ビット長の出力を計算する、というのは一方向ハッシュ関数と似ている。ただし、一方向ハッシュ関数ではハッシュ値を計算する時には鍵を使わなかった。それに対してメッセージ認証コードでは、送信者と受信者で共有する鍵を使う

• メッセージ認証コードの利用手順

  • 1: 送信者アリスと受信者ボブは、前もって鍵を共有しておく

  • 2: 送信者アリスは、送金依頼のメッセージを元にして、MAC 値を計算する

  • 3: 送信者アリスは、受信者ボブに対して送金依頼のメッセージと MAC 値の両方を送る

  • 4: 受信者ボブは、受信した送金依頼のメッセージを元にして、MAC 値を計算する(共有鍵を使用)

  • 5: 受信者ボブは、アリスから受信した MAC 値と、計算で得られた MAC 値を比較する

  • 6: 受信者ボブは、2 つの MAC 値が等しかったら、送金依頼が間違いなくアリスから来たものだと判断する(認証成功)。等しくなかったら、アリスから来たものではないと判断する(認証失敗)

• メッセージ認証コードの鍵配送問題

  • 対称暗号のときの鍵配送問題と同じ問題がメッセージ認証コードにも起こる

  • 公開鍵暗号、Diffie-Hellman 鍵交換、鍵配布センター、あるいは鍵を安全な方法で別途届けるなど、目的に応じた方法で鍵を配送する必要がある

メッセージ認証コードの利用例

• SWIFT(Society for Worldwide Interbank Financial Telecommunication、国際銀行間通信協会)

  • 国際的な銀行間の送金を安全に行うために 1973 年に設立された団体

  • 銀行と銀行は SWIFT を通して取引のメッセージをやり取りする

  • SWIFT では正真性を確認し、メッセージの認証を行うために、メッセージ認証コードを使っている

  • 公開鍵暗号を使った鍵配送が使われるまでは、メッセージ認証コードで用いる共有鍵の配送は人間が行っていた

• IPsec

  • IPsec は、インターネットの根底をなす通信プロトコルの IP(Internet Protocol) にセキュリティの機能を加えたもの

  • IPsec では、通信内容の認証と正真性のチェックを行うために、メッセージ認証コードを用いている

• SSL/TLS

  • SSL/TLS は、私達が Web でオンラインショッピングを行うときなどに使用されている通信プロトコル

  • SSL/TLS でも、通信内容の認証と正真性のチェックを行うために、メッセージ認証コードを用いている

メッセージ認証コードの実現方法

• 一方向ハッシュ関数を使って実現

  • 方法の 1 つに HMAC があるが、具体的な手順は次節で扱う

• ブロック暗号を使って実現

  • ブロック暗号の鍵をメッセージ認証コードの共有鍵として使い、CBC モードを使ってメッセージ全部を暗号化する

  • 最終ブロック以外は廃棄し、最終ブロックを MAC 値として使う

  • CBC モードの最終ブロックは、メッセージ全文と鍵の影響を受けるので、メッセージ認証コードとして利用できる

• その他の方法で実現

  • ストリーム暗号や公開鍵暗号などを使って、メッセージ認証コードを実現できる

認証付き暗号

• 認証付き暗号は、対称暗号とメッセージ認証コードを組み合わせることで、機密性・正真性・認証を同時に満たそうとする仕組み

• 認証付き暗号の 1 つの方法である「Encrypt-then-MAC」では、平文を対称暗号で暗号化し、その後で暗号文の MAC 値を計算する

  • 他にも Encrypt-and-MAC(平文を対称暗号で暗号化し、それとは別に平文の MAC 値を得る方法)や、MAC-then-Encrypt(あらかじめ平文の MAC 値を得て、平文と MAC 値の両方をまとめて対称暗号で暗号化する方法)がある

• GCM と GMAC

  • GCM(Galois/Counter Mode) は、認証付き暗号の一種

  • GCM では、AES のような 128 ビットブロック暗号を CTR モードで用い、MAC 値を得るために加算と乗算を繰り返すハッシュ関数を用いる

  • GCM をメッセージ認証コード専用として用いたものを GMAC と呼ぶ

HMAC の詳細

• HMAC とは何か

  • HMAC の H は Hash を意味する

  • HMAC は一方向ハッシュ関数を用いて、メッセージ認証コードを構成する手法

  • HMAC では、使用する一方向ハッシュ関数をただ 1 種類に定めているわけではない。強い一方向ハッシュ関数なら何でも HMAC に用いることができる

  • SHA-256 を使う HMAC を HMAC-SHA-256、SHA-512 を使う HMAC を HMAC-SHA-512 などのように呼ぶ

• HMAC の手順(p212)

  • 1: 鍵へのパディング

  • 2: パディングした鍵と ipad の XOR

    • パディングした鍵と、ipad と呼ばれるビット列の XOR をとる(ipad の i は inner を表す)

  • 3: メッセージとの結合

  • 4: ハッシュ値の計算

  • 5: パディングした鍵と opad の XOR

    • パディングした鍵と、opad と呼ばれるビット列の XOR をとる(opad の o は outer を表す)

  • 6: ハッシュ値との結合

    • opadkey の後に 4 のハッシュ値を結合する

  • 7: 6 の結果を一方向ハッシュ関数に入力し、ハッシュ値を計算する

• HMAC は次の擬似コードで表現できる

  • hash(opadkey || hash(ipadkey || message))

メッセージ認証コードに対する攻撃

• 再生攻撃

  • マロリーは保存しておいた正しい MAC 値を繰り返し送信することで攻撃する

    • メッセージ認証コードを破っていなくても 100 万円をもとに 1 億円を騙し取れる

• 再生攻撃を防ぐ方法

  • シーケンス番号

    • 送信メッセージに毎回 1 ずつ増加する番号(シーケンス番号)を振る約束にし、MAC 値の計算ではシーケンス番号もメッセージに含める

    • こうしておけばマロリーはシーケンス番号を増やした時の MAC 値を計算できないので、再生攻撃を防げる

    • この方法は有効だが、通信相手ごとに最後のシーケンス番号を記録しておく必要が生じる

  • タイムスタンプ

    • 送信メッセージに現在時刻を埋め込む約束にしておき、古いメッセージが送られてきた場合には、MAC 値が正しくてもエラーだと判断する

    • この方法は有効だが、送信者と受信者の間で時計を一致させておかなければならない

    • また、通信時間のゆらぎを考慮して時間に余裕をもたせる必要があるので、どうしても再生攻撃の余地が残る

  • ノンス

    • 受信に先立って、受信者から送信者に対して使い捨てのランダムな値を渡す。この値のことを一般に「ノンス(nonce)」と呼ぶ

    • そして送信者は、メッセージの中にノンスを含めて MAC 値を計算する

    • ノンスの値は通信ごとに変わるので、再生攻撃はできない

    • この方法は有効だが、通信量が少し多くなる

• 鍵の推測による攻撃

  • 一方向ハッシュ関数の攻撃と同様に、メッセージ認証コードに対しても、ブルートフォースアタックや誕生日攻撃が可能

メッセージ認証コードで解決できない問題

• 「第三者に対する証明」と「否認防止」の 2 つを解決できない

• 第三者に対する証明

  • 第三者にヴィクターに証明したい場合、アリスとボブだけが知っているべき鍵をヴィクターにも教えなければならない

  • 仮に鍵をもらっても、ヴィクターはその鍵が正しいか判断できない

  • 9 章の「デジタル署名」を使えば、第三者に対する証明が可能になる

• 否認防止

  • 送信者アリスが「私はボブにそんなメッセージを送っていないわ」と検証者ヴィクターに主張すること

  • これも 9 章の「デジタル署名」を使えば、否認防止が可能になる

9: デジタル署名

デジタル署名

• メッセージ認証コードからデジタル署名へ

  • メッセージ認証コードの限界

    • メッセージ認証コードは否認防止には役立たない。それは送信者と受信者が鍵を共有する必要があったため

  • デジタル署名による解決

    • 送信者と受信者は別の鍵を使うことにする

• 署名の作成と署名の検証

  • デジタル署名という技術には、以下の 2 つの行為が登場する

    • メッセージの署名を作成するという行為

    • メッセージの署名を検証するという行為

  • デジタル署名では、「署名用の鍵」と「検証用の鍵」が分かれており、検証用の鍵で署名を作成することはできない

    • また、「署名用の鍵」は署名をする人だけが持っているが、「検証用の鍵」は署名を検証する人なら誰でも持てる

  • デジタル署名は公開鍵暗号を逆に使うことで実現できる

• 公開鍵暗号とデジタル署名

  • 公開鍵暗号では、公開鍵で暗号化して、プライベート鍵で復号化する

  • デジタル署名では、プライベート鍵で暗号化して、公開鍵で復号化する

デジタル署名の方法

• メッセージに直接署名する方法(p230)

  • 1: 送信者アリスは自分のプライベート鍵でメッセージを暗号化する

  • 2: アリスは、メッセージと署名を受信者ボブに送信する

  • 3: ボブは受信した署名をアリスの公開鍵で復号化する

  • 4: ボブはいま署名を復号化して得られたメッセージと、アリスから直接受信したメッセージとを比較する

• メッセージのハッシュ値に署名する方法

  • メッセージ全体を暗号化すると時間がかかってしまう。公開鍵暗号のアルゴリズムは非常に遅いため

    • 一方向ハッシュ関数を使ってメッセージのハッシュ値を求め、ハッシュ値を暗号化する

    • メッセージがいくら長くても、ハッシュ値は短いので、暗号化するのがずっと楽になる

  • 1: アリスは一方向ハッシュ関数でメッセージのハッシュ値を計算する

  • 2: アリスは自分のプライベート鍵でハッシュ値を暗号化する

  • 3: アリスはメッセージと署名をボブに送信する

  • 4: ボブは受信した署名をアリスの公開鍵で復号化する

  • 5: ボブは受信した署名から得られたハッシュ値と、アリスから直接受信したメッセージのハッシュ値とを比較する

デジタル署名に対する疑問

• 暗号文がなぜ署名として使えるのか

  • 暗号文は、機密性を守るものとして使われるのではなく、「鍵を持っている人にしか作り出せない情報」として用いられる

    • このような情報のことを一般に「認証子(authenticator)」と呼ぶ

• 機密性が保てないのではないか

  • デジタル署名は機密性を守るためのものではない

  • 暗号化と署名を組み合わせる方法については 13 章「PGP」で詳しく紹介する

• 書き換えができるのではないか

  • 事実上できない

  • メッセージを 1 ビットでも修正すると、プライベート鍵を知らない状態でハッシュ値を暗号化しなければならないが、それは事実上不可能

• 署名だけ再利用できてしまうのではないか

  • 他のメッセージに添付はできるが、署名の検証には失敗する

  • メッセージと署名との間に対応関係があるので、再利用はできない

デジタル署名の利用例

• セキュリティ情報のアナウンス

  • セキュリティ団体がアナウンスしていることを証明するために使われる

  • この場合、メッセージは暗号化されないが、デジタル署名だけ施される

  • メッセージが暗号化されない署名のことを、一般に「クリア署名(clearsign)」という

• ソフトウェアのダウンロード

  • ソフトウェアの作成者が、ソフトウェアにデジタル署名を作成し、ダウンロードした後に私達が署名を検証すれば、能動的攻撃者マロリーによる書き換えを検出できる

• 公開鍵の証明書

• SSL/TLS

  • SSL/TLS では、サーバが正しいものであることを認証するのに、サーバ証明書を用いる

  • サーバの公開鍵にデジタル署名が施されたもの

  • 逆に、サーバに対してクライアントを認証してもらうためにクライアント証明書を用いることもある

RSA によるデジタル署名

• RSA による署名の作成

  • RSA では署名対称となるメッセージも、鍵も、作成された署名も、すべて数として表現する

    • 文章に署名したい場合には、符号化を行って文章を数に変換しておかなければならない

  • RSA による署名の作成は次の式で表現できる

    • 署名 = メッセージ^D mod N

    • ここで使われる D と N は、署名者のプライベート鍵

• RSA による署名の検証

  • 次の式で表現できる

    • 署名から得られたメッセージ = 署名^E mod N

    • ここで使われる E と N は、署名者の公開鍵

他のデジタル署名

• ElGamal 方式

• DSA(Digital Signature Algorithm)

• ECDSA(Elliptic Curve Digital Signature Algorithm)

• Rabin 方式

デジタル署名に対する攻撃

• man-in-the-middle 攻撃

  • 公開鍵暗号に対する man-in-the-middle 攻撃は、デジタル署名にも脅威となる

  • man-in-the-middle 攻撃を防ぐには、入手した公開鍵が正しい相手のものかどうか正しいか確かめる必要がある

    • ボブはアリスに電話をかけて自分が持っている公開鍵が本物かどうか確かめる

    • 一方向ハッシュ関数を使って、ハッシュ値を確認すれば良い

    • このハッシュ値のことを「フィンガープリント」と呼ぶ

• 一方向ハッシュ関数に対する攻撃

  • デジタル署名で使う一方向ハッシュ関数は、衝突耐性を持たなければならない

• デジタル署名を使って公開鍵暗号を攻撃

  • 最も重要な対策は、意味がわからないメッセージには、絶対にデジタル署名をしないこと

• 潜在的偽造

  • 署名対象となるのが意味のないメッセージだとしても、正しいデジタル署名がもし作れてしまうなら、それはデジタル署名のアルゴリズムに対する脅威となる

    • これをデジタル署名の「潜在的偽造」という

  • メッセージを RSA で復号化するデジタル署名のアルゴリズムでは、潜在的偽造が可能になる

    • ランダムなビット列 S を RSA の公開鍵で暗号化したものを M とすると、S が M の正しいデジタル署名になってしまう

    • 公開鍵は攻撃者でも入手できるから、デジタル署名の潜在的偽造が可能

  • 潜在的偽造に対処するため、RSA を改良した RSA-PSS(Probabilistic Signature Scheme)という方法が開発されている

• その他の攻撃

  • 公開鍵暗号に対する攻撃の多くは、デジタル署名への攻撃としても使える

• 対称暗号の鍵は、機密性のエッセンスであり、一方向ハッシュ関数のハッシュ値は、正真性のエッセンスである

デジタル署名で解決できない問題

• デジタル署名が正しく用いられるためには、大きな前提条件がある

  • 署名の検証を行うときに用いる公開鍵が、本物の送信者の公開鍵であること

• 正しい公開鍵を入手するために考えられたのが「証明書」

  • 証明書とは、公開鍵をメッセージとみなし、信頼できる別の人にデジタル署名してもらった公開鍵のこと

  • しかし、そうするとこのデジタル署名を検証するためにまた別の公開鍵が必要になってしまう

• この信頼できるデジタル署名の連鎖を構築するには、公開鍵暗号およびデジタル署名の技術を社会的な基盤にしていく「公開鍵基盤(Public Key Infrastructure: PKI)」が必要

  • 10 章で詳しく扱う

10: 証明書

証明書

• 証明書とは何か

  • 公開鍵証明書(public-key certificate: PKC) には、名前や所属、メールアドレスなどの個人情報、その人の公開鍵が記載され、認証局(certification authority: CA) によるデジタル署名が行われている

  • 有名な認証局に「ベリサイン」がある

• 証明書を使うシナリオ

  • 暗号文を作成するときに用いたボブの公開鍵は認証局を利用して取得する

  • 1: ボブが鍵ペアを作成する

    • 鍵ペアを認証局に作ってもらう場合もある

  • 2: ボブは、認証局トレントに自分の公開鍵を登録する

  • 3: 認証局トレントは、ボブの公開鍵に自局のプライベート鍵でデジタル署名をして証明書を作成する

  • 4: アリスは、認証局トレントのデジタル署名がついたボブの公開鍵(証明書)を入手する

  • 5: アリスは、認証局トレントの公開鍵を使ってデジタル署名を検証し、ボブの公開鍵が正しいことを確認する

  • 6: アリスは、ボブの公開鍵でメッセージを暗号化し、ボブへ送信する

  • 7: ボブは、暗号文を自分のプライベート鍵で復号化し、アリスのメッセージを読む

• 証明書を作ってみよう

  • 証明書の標準規格

    • 最も広く使われているのは ITU(International Telecommunication Union) や ISO(International Organization for Standardization) で定めている X.509 という規格

公開鍵基盤(PKI)

• 公開鍵基盤(public-key infrastructure: PKI)とは何か

  • 公開鍵基盤は、公開鍵を効果的に運用するために定められた多くの規格や仕様の総称

  • PKI はあくまで総称であり、単独の規格や仕様を指すものではない

    • 例えば RSA が定めていた PKCS(Public-Key Cryptography Standards) という規格の集合も PKI の一種だし、インターネットの仕様を定めている RFC(Requests for Comments) の中にも、PKI に関連した文書がたくさんある

  • PKI の構成要素(p260)

    • PKI の構成要素は主に以下の 3 つ

      • 利用者: PKI を利用する人

      • 認証局: 証明書を発行する人

      • リポジトリ: 証明書を保管しているデータベース

  • 認証局の仕事

    • 証明書の破棄も行う

      • リポジトリから削除しても破棄したことにならない

      • 証明書を破棄する場合、認証局は「証明書破棄リスト(certificate revocation list: CRL)」を作成する

      • 公開鍵の利用者アリスは、認証局のデジタル署名が付けられて有効期限内であっても有効な証明書とは言えない。認証局の最新の CRL を調べて、その証明書が有効かどうかを確認する必要がある

  • 階層になった証明書

    • 認証局の公開鍵に対して、別の認証局がデジタル署名を施すことで、認証局の公開鍵を検証できる

    • 自分自身の公開鍵に対して行うデジタル署名のことを「セルフ署名」という

  • 様々な PKI

    • 誰でも認証局になれるし、世の中には無数の認証局がある

    • 日本が定めている PKI は、政府認証基盤(GPKI) と呼ばれる

証明書に対する攻撃

• 公開鍵の登録前を攻撃

  • デジタル署名される前の公開鍵を攻撃する

  • マロリーが公開鍵を自分のものにすりかえ、「ボブの情報」と「マロリーの公開鍵」の組み合わせに対して、デジタル署名してしまう

• 似た人間を登録する攻撃

  • コンピュータには区別されるけど、人間には誤認されるようなユーザー情報を使う

  • Bob と BOB など

• 認証局のプライベート鍵を盗み出す攻撃

  • 認証局のプライベート鍵が手に入れば、誰でもその認証局発行の証明書が作れる

  • 認証局のプライベート鍵を盗み出すには、認証局のコンピュータに忍び込んだり、認証局のプライベート鍵にアクセスできる人間を買収したりすることが必要

  • もしも認証局のプライベート鍵が漏洩したならば、認証局は自分の鍵が漏洩したことを CRL を使って利用者に通知する必要がある

• 攻撃者自身が認証局になる攻撃

  • 認証局を信頼できなければ、証明書がいくら正しくても、その公開鍵を使ってはならない

• CRL の隙を突く攻撃(1)

  • マロリーは CRL が届くまでの時間差を利用したスピーディーな攻撃を試みる

  • 対策

    • 公開鍵が無効になったら可能な限り早く認証局に伝える

    • CRL はすばやく発行する

    • CRL はきちんと更新する

    • 公開鍵を利用する前には、公開鍵が無効になっていないかを再確認する

• CRL の隙を突く攻撃(2)

  • CRL の隙を突くことによって、否認の可能性が出る

• Superfish

  • コンピュータにプリインストールされていた Superfish というアドウェアがセキュリティ上の問題を引き起こした事件

    • アドウェア: 無料で使える代わりに広告を表示するソフト

証明書に対する Q&A

• 証明書がなぜ必要なのか

  • 認証局から証明書を入手すると、man-in-the-middle 攻撃の可能性を減らせる

  • まとめ

    • 信頼できる公開鍵を入手できるなら、認証局は不要

    • 信頼できる認証局の公開鍵を持っていて、認証局の本人確認を信頼するなら、その認証局の発行した証明書によって入手した公開鍵は信用できる

第 3 部: 鍵・乱数・応用技術

11: 鍵

鍵とは何か

• 鍵はとても大きな数

  • 対称暗号、公開鍵暗号、メッセージ認証コード、デジタル署名などの暗号技術を使うには、必ず「鍵(key)」と呼ばれる大きな数が必要になる

  • 重要なのは数そのものの大きさというよりも鍵空間の大きさ、すなわち「可能な鍵の総数」

  • 鍵空間の大きさは、鍵のビット長で定まる

• 鍵は平文と同じ価値を持つ

• 暗号アルゴリズムと鍵

  • 情報の機密性は、暗号アルゴリズムそのものを秘密にするのではなく、鍵を秘密にすることで守る

様々な鍵

• 対称暗号の鍵と公開鍵暗号の鍵

  • 対称暗号では、暗号化と復号化で共通の鍵を使う

  • 公開鍵暗号では、暗号化と復号化で異なる鍵を使う

• メッセージ認証コードの鍵とデジタル署名の鍵

  • メッセージ認証コードでは、送信者と受信者が共通の鍵を使って認証を行う

  • デジタル署名では、署名の作成と検証とで異なる鍵を使う

• 機密性のための鍵と認証のための鍵

  • 対称暗号や公開鍵暗号で使われる鍵は、機密性を保つための鍵

  • メッセージ認証コードやデジタル署名で使われる鍵は、認証を行うための鍵

• セッション鍵とマスター鍵

  • 通信ごとに一度しか使われない鍵を「セッション鍵(session key)」と呼ぶ

    • https:// ではじまるページにアクセスするときの Web サーバとブラウザの間では SSL/TLS によって暗号化された通信が行われるが、このときに使われるのはセッション鍵

  • 鍵を 1 回しか使わないことのメリット

    • 万一、盗聴者にその回のセッション鍵が知られたとしても、解読されるのはその通信 1 回分だけ

    • 次回の通信では、また異なるセッション鍵が使われるため、他の通信の機密性は保たれる

    • ただし、セッション鍵を作るときに使用する疑似乱数生成器の品質がよくないと、次に生成されるセッション鍵を盗聴者に予測されてしまう危険がある

  • 通信ごとに新しく作られるセッション鍵に対して、繰り返し使われる鍵を「マスター鍵(master key)」と呼ぶことがある

• コンテンツを暗号化する鍵と、鍵を暗号化する鍵

  • 通常はユーザーが直接利用する情報が暗号化の対象になる

    • このときに使う鍵を「CEK(contents encrypting key)」と呼ぶ

  • 鍵を暗号化する鍵を「KEK(key encrypting key)」と呼ぶ

  • セッション鍵は CEK として使われ、マスター鍵は KEK として使われることが多い

鍵を管理する

• 鍵を作る

  • 乱数から鍵を作る

    • 鍵を作る最も良い方法は「乱数を使う」こと

    • なぜなら、鍵には「他の人に推測されにくい」という性質が必要であるため

    • 暗号用に用いる疑似乱数生成器は、暗号用として設計されているものを選ぶべき

      • なぜなら、暗号用として設計されていない疑似乱数生成器は「予測不可能性」という性質を持たないため

      • 詳しくは 12 章

  • パスワードから鍵を作る

    • 人間が記憶できるパスワードやパスフレーズから鍵を作る場合もある

    • 厳密にはパスワードを鍵として直接用いることはめったになく、パスワードを一方向ハッシュ関数に入力して、得られたハッシュ値を鍵として用いる

    • パスワードから鍵を作るときには、辞書攻撃という攻撃を防ぐため、パスワードにソルトと呼ばれる乱数を付加してから、一方向ハッシュ関数に入力する

      • この方法を PBE(password based encryption) と呼ぶ

• 鍵を配送する

  • 鍵配送問題を解決するには、鍵の事前共有を行う方法、鍵配布センターを使う方法、公開鍵暗号を使う方法などがある

  • もう 1 つの方法として Diffie-Hellman 鍵交換がある。これは後で紹介する

• 鍵を更新する

  • 通信の機密性を高めるテクニックの 1 つに「鍵更新(key updating)」と呼ばれるものがある

    • これは共通の鍵を使って通信を行っている最中に、定期的に鍵を変えていく方法

    • 現在の鍵のハッシュ値を次の鍵とする

  • 鍵更新を行うメリット

    • 鍵が盗聴者に知られてしまったとしても、鍵更新を行った時点よりも過去にさかのぼって通信を復号化することはできない

    • このように、過去にさかのぼった解読を防止することを「バックワードセキュリティ」という

• 鍵を保存する

  • 鍵を繰り返し使う場合には、鍵の保存を考えなければならない

  • 鍵は記憶できない

    • 人間は実用的なサイズの鍵を記憶しておくことはできない

  • 鍵を暗号化することの意味

    • 鍵を保存する 1 つの方法は、金庫などの安全な場所に保管しておくこと

    • 鍵を盗まれても、その鍵を攻撃者が使うことができるまでの時間をかせぐために、鍵を暗号化して保存するというテクニックが使われる

      • 鍵を暗号化するために別の鍵が必要になってしまうが、守るべき鍵の本数を少なくできる

• 鍵を捨てる

  • 鍵がコンピュータ上のファイルになっている場合、そのファイルを削除しただけでは鍵を削除したことにならない

  • ファイルの内容がコンピュータのメモリに残っている場合もあるので、その痕跡も削除する必要がある

  • きちんと鍵を削除するためには、暗号ソフトウェアだけでなく、コンピュータ全体がセキュリティを意識した設計にする必要がある

Diffie-Hellman 鍵交換

• Diffie-Hellman 鍵交換とは何か

  • 1976 年に発明されたアルゴリズム

  • このアルゴリズムは、他人に知られても構わない情報を 2 人が交換するだけで、共通の秘密の数を作り出すという方法

  • この秘密の数を対称暗号の鍵として使う

  • 鍵交換という名前がついているが、実際には鍵を交換しているわけではなく、共有する鍵を計算によって作り出している

• Diffie-Hellman 鍵交換の手順

  • 1: アリスはボブに対して 2 つの素数 P と G を送信する

  • 2: アリスは乱数 A を用意する

  • 3: ボブは乱数 B を用意する

  • 4: アリスはボブに対して、G^A mod P という数を送信する

  • 5: ボブはアリスに対して、G^B mod P という数を送信する

  • 6: アリスはボブから送られてきた数を A 乗して、mod P をとる

  • 7: 一方ボブはアリスから送られてきた数を B 乗して、mod P をとる

    • これでアリスとボブは等しい鍵を共有する

• イブは鍵を計算できないのか

  • G^A mod P から数 A を簡単に計算するアルゴリズムは、まだ発見されていない

  • これは有限体の上の離散対数問題と呼ばれている

• ただし、man-in-the-middle 攻撃は受ける可能性がある

• 楕円曲線 Diffie-Hellman 鍵交換

  • 「離散対数問題」を「楕円曲線上の離散対数問題」に置き換えた鍵交換アルゴリズムもある

  • これを「楕円曲線 Diffie-Hellman 鍵交換」と呼ぶ

パスワードを元にした暗号

• パスワードを元にした暗号(password based encryption: PBE)とは何か

  • パスワードを元にして作った鍵で暗号化を行う方法

  • 暗号化と復号化で同じパスワードが必要になる

• PBE の暗号化(p300)

  • 1: KEK の生成

    • まず疑似乱数生成器がソルトと呼ばれる乱数を生成する

    • ソルトとアリスが入力したパスワードを、順に一方向ハッシュ関数に入力する

    • 得られたハッシュ値が、鍵の暗号化のための鍵(KEK)になる

  • 2: セッション鍵の生成と暗号化

    • 次に疑似乱数生成器を使って、セッション鍵を生成する

    • セッション鍵はメッセージを暗号化するための鍵(CEK)になる

    • セッション鍵は、1 で作った KEK を使って暗号化し、ソルトと共に安全な場所に保存する

      • セッション鍵の暗号化がすんだら、KEK は捨ててしまう。保存しておく必要はない。ソルトとパスワードがあれば KEK は復元できる

  • 3: メッセージの暗号化

    • 最後に 2 のセッション鍵を使ってメッセージの暗号化を行う

    • PBE の暗号化でできるものは以下の 3 つ

      • ソルト

      • KEK で暗号化されたセッション鍵

      • セッション鍵で暗号化されたメッセージ

• PBE の復号化

  • 1: KEK の復元

    • 保存しておいたソルトと、アリスが入力したパスワードを一方向ハッシュ関数に入力する

    • これで KEK が得られる

  • 2: セッション鍵の復号

    • 保存しておいた「KEK で暗号化されたセッション鍵」を持ってきて、1 で復元させた KEK を使って復号化する

  • 3: メッセージの復号化

    • 最後に 2 で復号化したセッション鍵を使って、暗号化されたメッセージを復号化する

• ソルトの役割

  • ソルトは辞書攻撃を防ぐためにある

• ストレッチングによる PBE の改良

  • KEK を作る際に、一方向ハッシュ関数を何度も通すようにすれば安全性を高められる

  • ユーザーにとってはハッシュ値を 1000 回繰り返すことは大した負担にならない

    • ユーザーがパスワードを 1 回入力する時間に比べたら、ハッシュ関数を 1000 回繰り返す時間は無視できる時間であるため

  • このように一方向ハッシュ関数を何度も通す方法を「ストレッチング」と呼ぶ

安全なパスワードを作るには

• 安全なパスワードを作るヒント

  • 自分だけが知りうる情報を使うこと

    • 大事なものの名前を使ってはいけない

    • 自分に関する情報を使ってはいけない

    • 他人が目にする情報を使ってはいけない

  • 複数のパスワードをつかい分けること

  • メモを有効に使うこと

  • パスワードの限界を知ること

  • パスワード生成/管理ツールを使うこと

12: 乱数

乱数が使われる暗号技術

• 乱数は次のような場面に登場する

  • 鍵の生成

  • 鍵ペアの生成

  • 初期化ベクトルの生成

  • ノンスの生成

  • ソルトの生成

乱数の性質

• 乱数の性質を分類する

  • 無作為性

    • 統計的な偏りがなく、でたらめな数列になっているという性質

  • 予測不可能性

    • 過去の数列から次の数を予測できないという性質

  • 再現不可能性

    • 同じ数列を再現できないという性質

  • 上記 3 つの性質は、下に行くほど厳しいものになる

• 無作為性

  • 無作為性とは、簡単に言えば「でたらめ」に見える性質のこと

  • でたらめであっても、見破られる可能性はある

  • 本書では、無作為性だけ持つ疑似乱数を「弱い疑似乱数」と呼ぶ

• 予測不可能性

  • 予測不可能性とは、過去に出力した疑似乱数列を攻撃者に知られても、次に出力する疑似乱数を攻撃者は言い当てることはできない、という性質

  • 本書では、予測不可能性を持つ疑似乱数を「強い疑似乱数」と呼ぶ

• 再現不可能性

  • 再現不可能性とは、ある乱数列と同じ数列を再現することはできない、という性質

  • ソフトウェアが生成する数列はいつか繰り返しになる。繰り返しに陥るまでの数列の長さを「周期」という

  • 周期を持つ数列は、再現不可能性を持たない

  • 本書では、再現不可能性を持つ乱数を「真の乱数」と呼ぶ

疑似乱数生成器

• 乱数は、ハードウェアで生成する場合と、ソフトウェアで生成する場合がある

• ハードウェアで乱数を生成する場合、熱や音の変化などの、予測や再現が事実上不可能である自然現象をセンサーで検知し、その結果を元に乱数列を生成する

  • そのようなハードウェアを乱数生成器(random number generator: RNG)と呼ぶ

• 乱数を生成するソフトウェアを疑似乱数生成器(pseudo random number generator: PRNG)と呼ぶ

  • ソフトウェアだけでは真の乱数を生成できないので「疑似」乱数生成器と呼ぶ

• 疑似乱数生成器の構造

  • 疑似乱数生成器は「内部状態」を持ち、外部から与えられた「種」を元に疑似乱数列を生成する

    • 疑似乱数の「種」はランダムなビット列

具体的な疑似乱数生成器

• でたらめな方法

  • 単に複雑にしただけのアルゴリズムを暗号技術で使ってはいけない

  • 理由

    • 周期の短さ

    • プログラマが詳細を理解できないようなアルゴリズムでは、生成した乱数が予測不可能性を持つかどうかの評価ができない

• 線形合同法(linear congruential method)

  • 最初の疑似乱数 R0 = (A * 種 + C) mod M

  • ここで A, C, M は定数で、A と C は M よりも小さい数を選ぶ

  • R1 は R0 から同じ計算式を使って作る R1 = (A * R0 + C) mod M

  • 以下同様に繰り返し Rn+1 = (A * Rn + C) mod M

  • 線形合同法では、A, C, M を注意深く選択すれば、無作為性を持つ疑似乱数列を簡単に生成できる

  • しかし、線形合同法は「予測不可能性」は持たない。なので線形合同法を暗号技術に使ってはいけない

• 一方向ハッシュ関数を使う方法

  • 手順

    • 1: 疑似乱数の種を使って内部状態(カウンタ)を初期化する

    • 2: 一方向ハッシュ関数を使ってカウンタのハッシュ値を得る

    • 3: そのハッシュ値を疑似乱数として出力する

    • 4: カウンタを 1 増加する

    • 5: 必要なだけの疑似乱数が得られるまで 2 - 4 を繰り返す

  • この疑似乱数生成器では、一方向ハッシュ関数の一方向性が疑似乱数生成器の予測不可能性を支えている

• 暗号を使う方法(p325)

  • 暗号を使って「強い疑似乱数」を生成する疑似乱数生成器を作れる

  • AES のような対称暗号や RSA のような公開鍵暗号のどちらを使っても構わない

  • 手順

    • 1: 内部状態(カウンタ)を初期化する

    • 2: 鍵を使ってカウンタを暗号化する

    • 3: その暗号文を疑似乱数として出力する

    • 4: カウンタを 1 増加する

    • 5: 必要なだけの疑似乱数が得られるまで 2 - 4 を出力する

  • 暗号の機密性が疑似乱数生成器の予測不可能性を支える

• ANSI X9.17 の疑似乱数生成器(p326)

  • 手順

    • 1: 内部状態を初期化する

    • 2: 現在時刻を暗号化して「かき混ぜ役」を作る

    • 3: 内部状態とかき混ぜ役の XOR をとる

    • 4: 3 の結果を暗号化する

    • 5: 4 の結果を疑似乱数として出力する

    • 6: 4 の結果とかき混ぜ役の XOR をとる

    • 7: 6 の結果を暗号化する

    • 8: 7 の結果を新しい内部状態とする

    • 9: 2 - 8 を必要なだけの疑似乱数が得られるまで繰り返す

疑似乱数生成器に対する攻撃

• 種に対する攻撃

  • 擬似乱数の種は、暗号の鍵に匹敵する重要性を持つ

  • 種を攻撃者に知られないように、再現不可能性を持つ「真の乱数」を種にする

• ランダムプールに対する攻撃

  • 必要になったときにその場で真の乱数を作るのではなく「ランダムプール」と呼ばれるファイルにランダムなビット列を蓄えておく

  • 攻撃者には、ランダムプールの内容を知られてはいけない

13: PGP

PGP の概要

• PGP(Pretty Good Privacy) とは何か

  • PGP は 1990 年頃に作成され、現在も世界中で使われている暗号ソフトウェア

• OpenPGP について

  • OpenPGP とは、暗号文やデジタル署名の形式を定めた規格

• GNU Privacy Guard について

  • GNU Privacy Guard(GnuPG, GPG) は、OpenPGP の規格に従って作られた暗号化ソフトウェア

  • 暗号化、デジタル署名、鍵管理、S/MIME と ssh などをサポートしている

• PGP の機能

  • PGP は、現代の暗号ソフトウェアに必要な機能をほぼすべて備えている

  • 対称暗号

    • PGP は、対称暗号による暗号化と復号化をサポートしている

  • 公開鍵暗号

    • PGP は、公開鍵暗号の鍵ペア作成、公開鍵暗号による暗号化と復号化をサポートしている

    • 実際には、公開鍵暗号によって直接平文を暗号化するのではなく、ハイブリッド暗号システムを用いる

  • デジタル署名

    • PGP は、デジタル署名の作成と検証をサポートしている

  • 一方向ハッシュ関数

    • PGP は、一方向ハッシュ関数を用いてメッセージのハッシュ値を計算・表示できる

  • 証明書

    • PGP は、OpenPGP で定められた形式の証明書と、X.509 互換の証明書を作成できる

    • 公開鍵の無効証明書も発行できる

  • 圧縮

    • PGP は、データの圧縮と伸張を行える

  • テキストデータ

    • PGP は、バイナリデータとテキストデータの相互互換を行える

  • 大きなファイルの分割と結合

    • PGP は、大きすぎてメールで送れないようなファイルを送りたい場合に備えて、1 つのファイルを複数ファイルに分割する機能を持つ

    • 逆に複数ファイルを結合して、1 つのファイルにする機能も持つ

  • 鍵リングの管理

    • PGP は、生成した自分の鍵ペアや、入手した公開鍵を管理する機能を持つ

    • 鍵を管理しているファイルは、「鍵リング(key ring)」あるいは「鍵束」と呼ばれる

鍵ペアの作成

• PGP を使って暗号化やデジタル署名を行うには、まず自分の鍵ペアを作成する必要がある

暗号化と復号化

• 暗号化(p341)

  • セッション鍵の生成と暗号化

    • 1: 疑似乱数生成器を使って、セッション鍵を作成する

    • 2: セッション鍵を公開鍵暗号で暗号化する。使う鍵は受信者の公開鍵

  • メッセージの圧縮と暗号化

    • 3: メッセージを圧縮する

    • 4: 圧縮したメッセージを対称暗号で暗号化する。使う鍵は 1 のセッション鍵

    • 5: 暗号化したセッション鍵と、暗号化したメッセージを結合する

    • 6: 5 の結果をテキストデータに変換する。変換した結果が送信データになる

  • このようにメッセージは対称暗号で暗号化し、セッション鍵は公開鍵暗号で暗号化するのがハイブリッド暗号の特徴

• 復号化(p343)

  • プライベート鍵の復号化

    • 1: 受信者は、復号化のためのパスフレーズを入力する

    • 2: パスフレーズのハッシュ値をとり、プライベート鍵を復号化するための鍵を生成する

    • 3: 鍵リングの中にある、暗号化されているプライベート鍵を復号化する

  • セッション鍵の復号化

    • 4: 受信データ(テキストデータ)をバイナリデータに変換する

    • 5: バイナリデータを、暗号化されているセッション鍵と、圧縮 + 暗号化されているメッセージとに分解する

    • 6: 暗号化されているセッション鍵を、公開鍵暗号で復号化する。このとき手順 3 で生成した受信者のプライベート鍵を使う

  • メッセージの復号化と伸張

    • 7: 手順 5 で得た、圧縮 + 暗号化されているメッセージを対称暗号で復号化する。このとき手順 6 で生成したセッション鍵を使う

    • 8: 手順 7 で得た、圧縮されているメッセージを伸張する

    • 9: これでメッセージを得られる

デジタル署名の作成と検証

• デジタル署名の作成(p346)

  • プライベート鍵の復号化

    • 1: 送信者は、署名のためのパスフレーズを入力する

    • 2: パスフレーズのハッシュ値をとり、プライベート鍵を復号化するための鍵を生成する

    • 3: 鍵リングの中にある、暗号化されているプライベート鍵を復号化する

  • デジタル署名の作成

    • 4: 一方向ハッシュ関数を使って、メッセージのハッシュ値を計算する

    • 5: 手順 4 で得たハッシュ値に署名する。これは手順 3 で得たプライベート鍵を使って暗号化することに相当する

    • 6: 手順 5 で作成したデジタル署名とメッセージを結合する

    • 7: 手順 6 の結果を圧縮する

    • 8: 手順 7 の結果をテキストデータに変換する

    • 9: 手順 8 の結果が送信データになる

• デジタル署名の検証(p348)

  • 送られてきたハッシュ値の復元

    • 1: 受信データをバイナリデータに変換する

    • 2: 圧縮されているデータを伸張する

    • 3: 伸張したデータを、署名されているハッシュ値と、メッセージとに分解する

    • 4: 署名されているハッシュ値(暗号化されているハッシュ値)を、送信者の公開鍵を使って復号化し、送られてきたハッシュ値を復元する

  • ハッシュ値の比較

    • 5: 手順 3 で分解したメッセージを、一方向ハッシュ関数に与えてハッシュ値を計算する

    • 6: 手順 4 で得たハッシュ値と、手順 5 で得たハッシュ値を比較する

    • 7: 手順 6 の結果が等しければ、デジタル署名の検証に成功したことになり、等しくなければ検証に失敗したことになる。これがデジタル署名の検証結果

    • 8: 手順 3 で分解したメッセージが送信者のメッセージ