📂整数論

暗号理論における暗号化と復号화

ビルドアップ

アリスがボブに伝えたいメッセージがあるとしよう。この世に二人しかいなければ、このメッセージは二人だけのもので、隠す必要はない。[ NOTE: 暗号理論では、アリスとボブはそれぞれ$A$と$B$を表す名前としてよく用いられる。] しかし、第三者のイヴがいるとしよう。イヴは特に悪意があるわけではないが、アリスがボブに伝えたいメッセージに興味がある。一方、アリスは自分が送るメッセージがボブだけに知られたいと願っている。[ NOTE: 暗号理論では、イヴは「盗聴者」を意味するEavesdropperの頭文字を取って$E$として表され、メッセージを盗み見するだけの受動的攻撃者の役割を持つ。] だから、アリスはイヴに知られないようにメッセージを送りたい。これは「暗号理論」のモチーフであり、誰もが共感できるものだ。

アリスがメッセージをボブだけが理解できるように変換することを暗号化とし、ボブが変形されたメッセージを元の形に戻せるようにすることを復号という。また、暗号化される前のメッセージを平文といい、その集合を$\mathcal{M}$、暗号化された後のメッセージを暗号文といい、その集合を$\mathcal{C}$と表す。暗号化と復号は何らかのルールに基づいて行われるが、第三者がこのルールを知っていても復号できないようにキーを共有する。このようなキーの集合を$\mathcal{K}$とするならば、暗号化と復号は以下のように数学的に表現できる。

定義 ¹

1. 関数$e : \mathcal{K} \times \mathcal{M} \to \mathcal{C}$を暗号化といい、簡単に$e_{k} : \mathcal{M} \to \mathcal{C}$とも表す。
2. 関数$d : \mathcal{K} \times \mathcal{C} \to \mathcal{M}$を復号といい、簡単に$d_{k} : \mathcal{C} \to \mathcal{M}$とも表す。

ただし、$e_{k}$と$d_{k}$は互いに逆関数でなければならない。つまり、全ての$m \in \mathcal{M}$に対して$d_{k} \left( e_{k} ( m ) \right) = m$である必要がある。

しかし、このような対応関係は非常に多く、その中で使い物になる暗号は次の条件を満たさなければならない。

暗号システム$( \mathcal{K} , \mathcal{M} , \mathcal{C} , e , d )$は次の性質を持つ時に有用である。

• (i): 全ての$k \in \mathcal{K}$と$m \in \mathcal{M}$に対して$e_{k} (m)$を計算するのが容易でなければならない。
• (ii): 全ての$k \in \mathcal{K}$と$c \in \mathcal{C}$に対して$d_{k} (c)$を計算するのが容易でなければならない。
• (iii): $k$を知らない場合、$c_{1} , \cdots , c_{n} \in \mathcal{C}$が与えられても$d_{k} ( c_{1} ) , \cdots , d_{k} ( c_{n} )$を計算するのが困難でなければならない。

説明

要約すると、資格のある人だけが簡単にメッセージを見られ、資格のない人は見られないような暗号システムが有用だ。メッセージを傍受する攻撃者がいなければ最も良いが、仮にいたとしても、その内容を漏らしてはならない。さらに、通信を行う当事者同士でも、暗号化と復号に時間がかかりすぎると、セキュリティが良くても通信の機能性を大きく損なってしまう。