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

前回からの続きです。今回もガッツリ数学の話をしましょう。

世界標準の暗号アルゴリズム

計算量的安全性とは、現代最強クラスのマシンが力を合わせても、暗号を破るのに3億年くらいかかるから実質安全、という根拠に基づいています。

AESという暗号は皆さんご存じではないでしょうか。世界標準の暗号アルゴリズムです。

カギは128ビットの01の並びなので、カギとして取りうる値は「2の128乗」種類しかありません。(256版の方がメジャーですが、ここでは128で話を進めます)

アルゴリズムをブラックボックスなものとして捉えると、ただの2入力1出力関数と見なせます。

カギが固定だったなら、同じ平文からは必ず同じ暗号文が生成されます。

しかし、そもそも128ビット入出力の関数はどのくらいあるのでしょうか。小さい値で考えてみましょう。例えば2ビット入力1ビット出力の関数は全部で16種類あります。

ランダムな暗号化関数

3つほど例を挙げてみましょう。これらはすべて異なる関数です。

一般的にmビット入力nビット出力の関数は全部で、通りあります。

128ビット入出力なら、通り存在します。

この中からランダムに1つを選んで用いることが、真にランダムな関数と言えます。ですが、これらの中に暗号化関数として使えないものも含まれます。

要するに全単射でないために復号ができないものです。詳しい計算は省きますが、このうち全単射関数は、 通りです。

この中からランダムに1つを選ぶことこそが、今度こそ真にランダムな暗号化関数と言えます。

いまだに破られていないAESという暗号

しかし先ほども話した通り、実際にはカギが「2の128乗」種類しかないので、「2の128乗」種類しか関数を表せないのです。

これほど弱い条件下にも関わらず、今に至るまでまったく破られていません。実際にAESの中身はビットシフトや排他的論理和など、ノイマン型コンピュータが、高速に計算しやすい単純な演算の組み合わせでできています。それでもなお人類は破ることができていないのです。

なので、現代の暗号の関心はもっぱら破ることにあり、新しくいいアルゴリズムを考えたとしてもさほど評価はされないのです。

しかも、実際世の中で起こっているセキュリティ事件は、権限付与の設定ミス、重要書類の置き忘れ、ドアの施錠忘れ、SQLインジェクションなどなど、原因は多々あります。

しかし、ただの1件の例外もなく、暗号アルゴリズムの脆弱性によって引き起こされてはいません。攻撃者たちも七面倒な数学を学ぶより、ヒューマンエラーを狙うほうが早いからです。

少なくとも量子コンピュータが現実のものとなるまでは、暗号の世界に大きな動きはないでしょう。