暗号化と復号化の手順のことを暗号アルゴリズムという、暗号アルゴリズムには鍵が必要
暗号アルゴリズムの変更可能な部分が鍵に相当する
シーザー暗号
暗号アルゴリズム：平文の各文字を「指定した文字数」ずらす
鍵：ずらす文字数
単一換字暗号
暗号アルゴリズム：「換字表」に従って、アルファベットを変換する
鍵：換字表
#暗号学者の道具箱
#1 対象暗号
暗号は、鍵の使い方によって対象暗号と公開鍵暗号の2種類に分類
対象暗号は、暗号化と復号化で同じ鍵を使う方式
対象暗号の代表例として、DESとAESがある
DES（対象暗号アルゴリズム）
DESの基本構造はファイステルネットワークと呼ばれる
ファイステルネットワークでは、ラウンドと呼ばれる暗号化の1ステップを何度も繰り返す
１）ラウンドへの入力を右と左に分ける
２）右を、そのまま右へ送る
３）右を、ラウンド関数fへも送る
４）ラウンド関数fは、右とサブ鍵を使って、ランダムに見えるビット列を計算する
５）得られたビット列と、左とのXORを計算した結果を暗号化された左とする
次のラウンドでは左と右を入れ替えて、同じことをする
復号化では、逆の順序で同じことをする
AES
DESと同じく、複数のラウンドからなる
1ラウンドは、SubBites,ShiftRows,MixColumns,AddRoundKeyという処理を続けて行う
SubBitesとは、1バイトの値（１〜２５５のいずれかの値）を1〜２５６のいずれかの数に入れ替える処理
単一換字暗号の２５６字版
イメージは
123 ----------543
456 ----------619
789 ----------872
4という値を6という値に変更
ShiftRowsとは、4バイト単位にまとまった行を左に規則的にシフトして混ぜこぜにする処理
イメージとしては1-2-3-4 を 4-1-2-3に
MixColumnsとは4バイトの値を行列計算して、別の４バイトの値に変換する処理
AddRoundKeyとはMixColumnsの出力とラウンド鍵(DESでいうサブ鍵?)とのXORをとる処理
対象暗号では、暗号化の鍵と復号化の鍵が等しいため、受信者に鍵を配送する必要がある
復号化の鍵を受信者に送信しなければならない、というこの問題を鍵配送問題と呼ぶ
AからBへメールで平文を暗号化して送りたい時、鍵を送らなければBは復号化できないが、メールで鍵を送る過程で盗聴者がいれば盗聴者にも復号化されてしまう
AとBのように少数であれば直接渡すといった解決策もあるが、数百人規模で暗号化と復号化を行う場合、コストが高い
現在、鍵を送る合理的な方法がない ->公開鍵暗号による解決
#2 公開鍵暗号
公開鍵暗号は暗号化と復号化で異なる鍵を使う方式
公開鍵を使った通信の流れを、アリスが送信者、ボブが受信者、イブが盗聴者として説明
１）ボブは、公開鍵・秘密鍵の鍵ペアを作る
秘密鍵は大切にしまっておく
２）ボブは、自分の公開鍵をアリスに送る
ボブの公開鍵は、イブに見られても構わない
３）アリスは、ボブの公開鍵をつかってメッセージを暗号化
暗号化したメッセージは、ボブの秘密鍵だけでしか復号化できない
４）アリスは暗号文をボブに送る
この暗号文はイブに見られても構わない
５）ボブは自分の秘密鍵を使って、暗号文を復号化
RSA（公開鍵暗号アルゴリズム）
暗号化の手順は
平文を表す数をE乗してmod N（Nで割った余り）をとったものを使って暗号文を作る
公開鍵は(E,N)
復号化では
暗号文をD乗してmod Nをとったものを使って平文に戻す
秘密鍵は(D,N)
公開鍵暗号は処理が遅いというデメリットがある
-> そこで、対象暗号と公開鍵暗号を組み合わせた暗号方式がハイブリッド暗号システムが使われる
対象暗号でメッセージを暗号化し、その時にだけ使うセッション鍵（DESの時はサブ鍵、AESの時はラウンド鍵）には公開鍵暗号を使い、暗号化する
セッション鍵に対してなら処理速度の遅さが問題にはならないし、セッション鍵を暗号化する時には受信者の公開鍵を使い、復号化する時には秘密鍵を使うことで鍵配送問題もクリアできる
#3 一方向ハッシュ関数
書き換えが行われていないことを確かめる「正真性」のためにハッシュ関数が有効
一方向ハッシュ関数は入力と出力があり、入力はメッセージと呼ばれ、出力はハッシュ値と呼ばれる
一方向ハッシュ関数は、メッセージを元にしてハッシュ値を計算する
あるファイルのハッシュ値をとっておき、別の日にそのファイルの正真性を確かめたいなら、ハッシュ関数にかけてハッシュ値をとり、ハッシュ値同士を比較すれば良い、ファイルの内容を隅から隅まで等しいかどうか確かめる必要はない
#4 メッセージ認証コード
確かに本人であることを確かめる「認証」
「メッセージが正しい送信者からの物である」という性質
メッセージ認証コードの利用手順
１）送信者アリスと受信者ボブは前もって鍵を共有しておく
２）送信者アリスは、送金依頼のメッセージを元にしてMAC値を計算する（共有鍵を使用）
３）送信者アリスは、受信者ボブに対して送金依頼のメッセージとMAC値の両方を送信
４）ボブは、受信した送金依頼のメッセージを元にして、MAC値を計算（共有鍵を使用）
５）ボブは、アリスから受信したMAC値と計算したMAC値を比較
６）正しければ認証成功
#5 デジタル署名
正真性を確かめ、認証と否認防止を行う暗号技術
印鑑の捺印やサインに相当する機能をコンピュータの世界で実現する
デジタル署名にはメッセージの署名を作成するという行為とメッセージの署名を検証するという行為がある
送信者は「署名用の鍵」を使って、メッセージの署名を作成
受信者や検証者は「検証用の鍵」を使って、メッセージの署名を検証
検証用の鍵で署名を作成することはできない
署名用の鍵は署名をする人だけがもっており、検証用の鍵は署名を検証する人なら誰でも持つことができる
公開鍵暗号と似ているが、公開鍵暗号では受信者が秘密鍵をもっていたのに対し、今回は送信者が秘密鍵に相当する署名用の鍵をもつ点で異なる
メッセージのハッシュ値に署名する方法
０）アリスは、秘密鍵と公開鍵を作り、ボブに公開鍵を送る
１）アリスは、一方向ハッシュ関数でメッセージのハッシュ値を計算
２）アリスは、自分の秘密鍵でハッシュ値を暗号化
暗号化した暗号文が署名となる
３）アリスは、メッセージと署名をボブに送信
４）ボブは、受信した署名をアリスの公開鍵で復号化
５）ボブは、受信した署名から得られたハッシュ値と、直接受信したメッセージのハッシュ値を比較
デジタル署名は「秘密鍵を使って作られた暗号文は、秘密鍵を知らない人には事実上作ることはできない」ということを利用して実現されている。ここで作った暗号文は、機密性を守るものとして使われているのではなく、「鍵をもっている人にしか作り出せない情報」として用いられている
デジタル署名は重要な認証の技術だが、署名の検証には送信者の公開鍵が本物であることが前提になる
公開鍵が正しいものかどうか証明するものが、「証明書」
認定局トレントを利用して、アリスがボブへ暗号文を送る例
１）ボブが鍵ペアを作成
２）ボブは、認定局トレントに自分の公開鍵を登録
３）認定局トレントは、ボブの公開鍵に自局の秘密鍵でデジタル署名をして証明書を作成
恐らく上のデジタル署名の例で言えば、メッセージがボブの公開鍵になると思う
４）アリスは証明書を入手
５）アリスは、トレントの公開鍵を使ってデジタル署名を検証し、証明書に書いてある公開鍵がボブの公開鍵であることを確認
６）アリスは、ボブの公開鍵でメッセージあるいは鍵を暗号化し、ボブへ送信
７）ボブは、暗号文を自分の秘密鍵で復号化、メッセージを読む
擬似乱数生成器は乱数列を擬似的に生成するアルゴリズムであり、乱数は鍵の生成に重要な役割