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

【暗号の歴史】に関する話も長くなってしまいましたが、最後にもう一つ、計算量的安全性の計測についてお話しします。細かい理論まで話すととてつもなく長くなるので、超基本の理論だけ触れたいと思います。

何をもって安全と見なすか？

そもそも何をもって安全と見なすか、というのが議論の始まりです。

攻撃者が攻撃に成功してしまったら、もちろん安全とは言えませんが、そもそも攻撃者には、どのような資源が与えられているかなども考える必要があります。

一例をあげますと、以下のようになります。

たったこれだけを成し遂げるにも途方もない時間がかかりますが、これができたところでハッカーが自由に攻撃を行なって、あらゆる悪事を働ける状況にはほど遠いです。

よく揶揄されるのですが、暗号学者は堅牢で強固な家にあるお宝が、その家の屋根の瓦1枚にひびが入っただけで盗まれたと騒ぎます。

アルゴリズムの中身をよく研究して、同じ暗号文を生成を目論むのはとても難しいことなのです。

一方で、どのくらい時間がかかるかを予測するだけなら、広く知られた手法があります。一般に「バースデーアタック」と呼ばれ、wikipediaにもページがあります。

ある部屋にn人の人がいるとき、1ペアでも同じ誕生日の人がいる確率はどれくらいか。これがバースデーアタックの問題です。

2人なら1/365、1%以下ですね。3人なら1-(364*365)^3、これも1%以下です。ところがこの確率、たかだか23人で50%を超えます。50人いたらほぼ100%です。

うまい具合にショートカットして同じ値を生成する手段がない以上、1, 2, 3…と1から試していくしかありません。この攻撃方法を「ブルートフォースアタック」と言います。

128ビットなら2^128通りありますが、1, 2, 3…と試していっても意外と早く同じ値が衝突します。（意外と早いといっても相応の時間はかかりますが・・・）

「バースデーアタック」と「ブルートフォースアタック」を組み合わせた解読時間を計算し、その量を現実のマシンで解読していくには、どれくらい時間がかかるかを見積もるというのが一般的な計測方法になります。

最近、新しい標準暗号を決めるコンテストが開かれましたが、応募されたすべての暗号はこの計測法で安全性が計算されています。

それ以外にもハードウェア効率、サイドチャネル攻撃、暗号化の速さ、並列処理、アルゴリズムの単純さ、などなど、さまざまな評価項目が存在し、すべてを考えてアルゴリズムを作るには、少なくとも10年はかかるといわれています。果てしない世界ですね。