暗号技術入門

概要

本

かかった時間

• 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 つに「差分解読法」がある

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

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

  • 線形解読法