【暗号の歴史】アラン・チューリングがイギリス紙幣になるそうです②

前回の続きから、もはやチューリング関係ないですが。

公開鍵暗号と共通鍵暗号

クリプトグラフィーは大別すると2種類ありまして、公開鍵暗号、共通鍵暗号と呼ばれます。私は共通鍵暗号をやっていました。

公開鍵暗号は南京錠のイメージです。閉めるときには、ただカチッと押し込むだけですが、開けるには鍵が必要になります。なので開け方と閉じ方が違い、必要な鍵も異なります。

太平洋戦争後に発明された公開鍵暗号によって、それまで最も苦労していた安全な鍵情報の受け渡し問題が解決されました。

数学的な説明は省きますが、通信をしたいお互いが、あらかじめ鍵を共有する必要がなくなったのです。

一方、シーザー暗号でいうところの「1文字ずつ」という情報は、あらかじめ通信をしたいお互いがわかっていなくてはなりません。

これを共通鍵暗号と言い、前回お話しした画家の話をはじめ、歴史上古くから使われてきたものです。

公開鍵暗号の欠点

だったら、公開鍵暗号だけ使えばいいじゃないかと思いますが、現代の暗号は基本的にコンピュータで生成、通信されますよね。

公開鍵暗号の暗号化計算は数学的に難しく、世にはびこるノイマン型のコンピュータには不向きなのです。

なのでとても暗号化の速度が遅いという欠点があります。「RSA」、「楕円曲線」など、さまざまな種類がありますがすべて該当します。

共通鍵暗号は、さらに2つに安全性根拠によって大別できます。理論的安全性と計算量的安全性です。

理論的安全性とは、どれほどのマシンがどれだけの時間をかけても、絶対に鍵を推定できないことを安全性の根拠にしています。いわば最強の暗号です。

バーナム暗号

例えばバーナム暗号という暗号があります。あらかじめお互いが無限に等しい長さの01で書かれた同じ紙をそれぞれ持っています。

Aさん　010100110011010110101010110101010101110101001…
Bさん　010100110011010110101010110101010101110101001…

別れたあと、AさんがBさんに通信をしたくなったとしましょう。その場合、先頭から必要な分だけ切り出します。

0101001100110101

これを暗号化したいメッセージ(平文〈plaintext〉)と排他的論理和をとります。例えば「あ」のJISコードは16進数で82A0、2進数に直すと0100001010110000です。

0100001010110000 XOR 0101001100110101 = 0001000110000101

これが暗号文になります。

受け取ったBさんは暗号文と同じ長さだけ紙を切り取り、排他的論理和をとると復号できます。

0001000110000101 XOR 0101001100110101 = 0100001010110000

これで「あ」という文字が見えるようになるわけです。

これ以降、また通信したくなったらちぎった紙の続きを使って同じ方法で通信を行います。この暗号は感覚的にもわかると思いますが、紙をもっていない人には、絶対に破ることができない暗号なのです。

次回は、計算量的安全性についてお話しします。