絶対に解読できない暗号

はじめに

ワンタイムパッドという暗号をご存じでしょうか？

シーザー暗号やRSA暗号は聞いたことがあるけれども、ワンタイムパッドは聞いたことがないという方が多いのではないかと思います。

ワンタイムパッドは

• 極限までシンプル
• 絶対に解読できない
• 非常に使いにくい

という面白い暗号です。

この記事は、ワンタイムパッドがなぜ解読できないのかをメモしたものです。

ワンタイムパッドとは

ワンタイムパッド (one-time pad) とは、「メッセージ(平文)と、同じビット長の鍵とのXORを取る」というシンプルな暗号です。
ただし、鍵はランダムなビット列であり、1回 (one-time) しか使ってはいけません。

メッセージを $m$ (message)、鍵を $k$ (key)、暗号文を $c$ (ciphertext) とします。
ワンタイムパッドにおける暗号化は

c = m \oplus k

で表されます。例えば $m = 01101101,, k = 11011001$ のとき $c$ は

    m = 01101101
(+) k = 11011001
----------------
    c = 10110100

となります。XORは2回行うと元に戻るため、復号化も

m = c \oplus k

のように、$k$ とのXORを取る形で表されます。先ほどの例では

    c = 10110100
(+) k = 11011001
----------------
    m = 01101101

となります。

ワンタイムパッドの特徴

ワンタイムパッドは解読できない

ワンタイムパッドは絶対に解読できません。
言い換えれば、ワンタイムパッドにおける暗号文は暗号解読の上で何の情報も提供しません。

確かに直観的には納得できる主張だと思います。
ランダムなビット列とのXORを取るとは、ビットをランダムに反転するということであり、暗号文それ自体も(他者から見た限りでは)ランダムなビット列であるからです。

ところで、実はワンタイムパッドが解読できないことは数学的に証明できます。
後で実際に証明します。

ワンタイムパッドは使いにくい

ワンタイムパッドはシンプルかつ解読不可能な暗号ですが、実際はほとんど使われていません。
その理由は、非常に使いにくいからです。

ワンタイムパッドでは、メッセージと同じ長さのランダムな鍵を相手に送る必要があります。
しかし、そもそもその鍵はどのように送ればいいのでしょうか？
メッセージと同じ長さの鍵を安全に送ることができるのであれば、そもそも安全にメッセージを送ることができるはずですよね。

他にも、鍵の保存、鍵の生成など、ワンタイムパッドには多くの問題があります。
ただし、大国同士のホットラインなど、機密性が最優先事項である場合は使われることもあるそうです。

ワンタイムパッドが解読できないことの証明

ワンタイムパッドが解読できないことを、数学的に証明します。
確率に関する基本的な知識を前提とします。

確率変数として、メッセージ $M$ (message), 鍵 $K$ (key), 暗号文 $C$ (ciphertext) を考えます。また各ビット長を $N$ とします。暗号化は

C = M \oplus K \tag{1}

で表されます。

ここで何点か確認しておきましょう。

• 鍵 $k$ に対し $K = k$ である確率は $P(K = k) = 2^{-N}$ です。
  これは $K$ が完全にランダムであることによります。

• メッセージ $m$ に対し $M = m$ である確率 $P(M = m)$ は $2^{-N}$ とは限りません。
  メッセージが完全にランダムであるとは限らないからです。

$m$ をメッセージ、$c$ を暗号文とします。目標は、以下の式を示すことです。

P(M = m | C = c) = P(M = m) \tag{2}

$P(M = m | C = c)$ は、$C = c$ という条件のもとで $M = m$ となる確率(条件付き確率)です。
$(2)$ は、$C = c$ という条件があってもなくても $M = m$ である確率は変わらない、つまり暗号文は暗号解読の上で何の情報も提供しないということを表しています。

まず条件付き確率の定義から

P(M = m|C = c) = \frac{P(M = m, C = c)}{P(C = c)} \tag{3}

です。分子と分母をそれぞれ計算しましょう。分子は

\begin{align}
& P(M = m, C = c) \\
= \quad & P(M = m, K = m \oplus c) \\
= \quad & P(M = m) P(K = m \oplus c) & (\because MとKは独立) \\
= \quad & 2^{-N} P(M = m)
\end{align}
\tag{4}

となり、分母は

\begin{align}
& P(C = c) \\
= \quad & \sum_m P(M = m, C = c) \\
= \quad & \sum_m 2^{-N} P(M = m) & (\because (4))\\
= \quad & 2^{-N} \sum_m P(M = m) \\
= \quad & 2^{-N} \\
\end{align}
\tag{5}

となります。したがって $(3), (4), (5)$ から

\begin{align}
& P(M = m|C = c) \\
= \quad & \frac{P(M = m, C = c)}{P(C = c)} \\
= \quad & \frac{2^{-N} P(M = m)}{2^{-N}} \\
= \quad & P(M = m)
\end{align}
\tag{6}

となり $(2)$ が示されました。

最後に

この記事では、ワンタイムパッドが解読できないこと、つまり暗号文が暗号解読の上で何の情報も提供しないということを証明しました。¹

これを機に、暗号に興味を持った方は暗号技術について調べてみてはいかがでしょうか。
また、情報と確率の関係に興味を持った方は情報理論について調べてみてはいかがでしょうか。

参考文献

• 暗号技術入門 第3版 秘密の国のアリス
• Proving the semantic security of the One Time pad

1. ただし、暗号文からメッセージのビット長を推定することはできます。 ↩