共通鍵暗号と公開鍵暗号

1対1 の暗号化通信の仕組み（共通鍵暗号）

Alice と Bob が暗号化通信をする場合、共通の暗号化方式を事前に決めて、その方式で暗号化したデータを送り合えばいい。例えば、アルファベットを一文字後ろにずらす、という暗号化アルゴリズムを採用する場合は、暗号文の受け手は一文字前にずらせば複合化できる。

[Alice]         [Bob]
ABCDE           ABCDE
  |               ↑
  | 1文字ずらす     | 1文字もどす            
  ↓               |
BCDEF --------> BCDEF
        送信

1文字ではなく、13文字ずらす暗号を ROT13、別名シーザー暗号と呼ぶ。ローマ帝国のシーザーが使っていた暗号の一種であることによる。

# 暗号化
$ echo ABCDE | tr 'A-Za-z' 'N-ZA-Mn-za-m'
NOPQR
$ echo abcde | tr 'A-Za-z' 'N-ZA-Mn-za-m'
nopqr

# 複合化（アルファベットは26文字なので、13文字のシフトを 2回実施すると元に戻る）
$ echo NOPQR | tr 'A-Za-z' 'N-ZA-Mn-za-m'
ABCDE
$ echo nopqr | tr 'A-Za-z' 'N-ZA-Mn-za-m'
abcde

暗号化方式はアルゴリズムと鍵から構成されるという捉え方をすると、文字をアルファベット順にずらすというのがアルゴリズム、n文字ずらすというのがキーだといえる。この暗号化方式は、アルゴリズムとキーの双方を秘匿し、より推測されにくいものを利用することで安全性を保つ。これを共通鍵暗号という。

n人のグループでの暗号化通信（共通鍵暗号）

1対1でなく、複数人のグループで暗号化通信をしたい場合も、グループ内で共通鍵を共有すれば暗号化通信ができる。しかし、Alice、Bob、Carol の 3名がいて、Alice と Bob の通信を Carol には秘密にしたい場合がある。この場合は、共通鍵を 3つ作ればいい。

3人で共有する共通鍵            3人で共有しない共通鍵

   Alice                          Alice
     |                           /     \
     * 共通鍵              共通鍵 *       * 共通鍵
   /   \                       /         \
Bob     Carol                Bob ---*--- Carol
                                   共通鍵

3人の通信には 3つの共通鍵が、4人の通信には 6つの共通鍵が必要になる。一般には n人で n(n-1)/2 の共通鍵が必要になる。100人の通信では 4950個だ。

n人のグループでの暗号化通信（公開鍵暗号）

公開鍵暗号は1970年代に発明された。暗号は紀元前3000年頃のバビロニアの時代から使われていたと言われているが、公開鍵暗号が発明されるまでの5000年間、人類は共通鍵暗号をより安全にするための工夫を続けてきた。

共通鍵暗号（Public key cryptograpy）では通常はキーを一つのみ作って、情報の送り手と受け手とで共有する。公開鍵暗号では、送り手も受け手もそれぞれ独立して、公開鍵（public key）と秘密鍵（private key）という、対応した 2つのキーを作る。公開鍵で暗号化したデータは対応する秘密鍵で復号化できる。同様に秘密鍵で暗号化したデータは、対応した公開鍵で復号化できる。

この特殊な性質を利用して、Bob は自分の公開鍵を世間に公開してしまう。世の中の人誰でもが、Bob の公開鍵を使って自分で暗号化したデータを Bob に送ることができる。この暗号化データは、対応する秘密鍵を持つ Bob のみが復号化できる。

共通鍵暗号では、通信したいペア毎に網目のように共通鍵を生成してお互い共有しておく必要があったが、秘密鍵暗号では n人が暗号化通信するのに必要なキーの数は、n個だけになる。100人なら100個。

[Alice]                    [Bob]
MESSAGE                   MESSAGE
  ↓                          ↑
  ↓ Bobの公開鍵で暗号化         ↑ Bobの秘密鍵で復号化
  ↓                          ↑
??????? ----------------> ???????
              送信

公開鍵暗号による署名

公開鍵で暗号化したデータは対応する秘密鍵のみで復号化できる。これは、秘密鍵所有者のみが復号化できることを意味する。一方、秘密鍵で暗号化したデータは対応する公開鍵のみで復号化できる。これは、秘密鍵所有者のみが暗号化できることを意味する。

秘密鍵所有者のみが暗号化できて、対応する公開鍵を使うと全世界の人がだれでも復号化できる。これは、秘密鍵所有者のみが可能な署名と見なすことができる。

あるメッセージを Alice が、確かにこれは自分が書いたものだと署名したい場合、メッセージの平文とともに、秘密鍵で暗号化したメッセージを同梱する。受け手の Bob が Alice の公開鍵で復号化すると、同じ平文が得られる。暗号化（署名）は Alice の秘密鍵のみでできるから、このメッセージは確かに Alice が署名したものであることがわかる。

[Alice]                         [Bob]
メッセージ（平文）                メッセージ（平文）
   ↓                              ↑↓ この二つを照合して合致すれば署名の検証成功
   ↓ Aliceの秘密鍵で暗号化        メッセージ（平文）
   ↓                              ↑ Aliceの公開鍵で復号化
????????（署名） -------------> ????????（署名）
                     送信

実際には、メッセージそのものを暗号化するとメッセージのサイズが大きい場合に署名も大きくなるので、メッセージをハッシュ化して小さくしたものを秘密鍵で暗号化して署名を生成している。

[Alice]                         [Bob]
メッセージ（平文）                メッセージ（平文）
    ↓                             ↓ ハッシュ化
    ↓ ハッシュ化   　　          メッセージハッシュ
    ↓                             ↑↓ この二つを照合して合致すれば署名の検証成功
メッセージハッシュ                メッセージハッシュ
    ↓ Aliceの秘密鍵で暗号化          ↑ Aliceの公開鍵で復号化
????????（署名）  ------------> ????????（署名）
            　　　メッセージ（平文）
                    と署名を送信