暗号技術入門

概要

本

• 暗号技術入門 | 結城 浩

かかった時間

• 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 次元の内部状態全体を「ステート」と呼ぶ