「バーナム暗号」・絶対に解読できない暗号

投稿日：2022/05/30 更新日:2024/04/18

排他的理論和（XOR）

前提知識としてXORの計算方法を知っておく必要があります。そんなに難しいものではありません。

1bitの $a, b$ があったとします。そして、XORを $a \oplus b$ とすると以下のように計算できます。

\begin{split} 0 \oplus 0 = 0\\ 0 \oplus 1 = 1\\ 1 \oplus 0 = 1\\ 1 \oplus 1 = 0\\ \end{split}

つまり、 $a$ と $b$ が同一の時に $0$ 、異なる時は $1$ となります。

$n$ bitの平文 $M$ があった時、ランダムに生成した $n$ bitの $key$ を用意します。そして、その2つのXORを取れば暗号文 $C$ の完成です。

C = M \oplus key

暗号化に用いた $key$ と暗号文 $C$ とのXORを取ります。そうすると、元の平文 $M$ が得られます。

M = C \oplus key

平文 $M$ を10bitの $0101101011$ とし、鍵を $1011010111$ とします。

これら2つのXORを取ると

\begin{array}{rr} &0101101011 &\text{平文}\\ \oplus &1011010111 &\text{鍵}\\ \hline &1110111100 &\text{暗号文} \end{array}

となり暗号文は $1110111100$ となります。

先ほどの暗号文 $1110111100$ と、鍵 $1011010111$ とのXORを取ります

\begin{array}{rr} &1110111100 &\text{暗号文}\\ \oplus &1011010111 &\text{鍵}\\ \hline &0101101011 &\text{平文} \end{array}

となり、正しく復号化できました！

「全通りの鍵を試せばいつか正しい平文が得られて解読できそうだ」と思うでしょう。

鍵を全通り試すと $2^n$ 通りあります。また、考えられる平文も $2^n$ 通りあります。したがって、鍵を全通り試すと、考えうる平文すべてが出てきます。全パターンの平文が出ると、どれが正しいのかを判定することができません。

つまり、解読不可というのは「正しい平文かどうかを判定できない」ということです。「現実的な時間で解読困難」というわけではないです。

バーナム暗号はほとんど使われていないのが現状です。

暗号化に使った鍵は安全に保存しておく必要があります。ここで、バーナム暗号の鍵の長さと平文の長さは同じです。もし、鍵を安全に保存できるのであればそこに平文を保存すればいいことになります。そうなれば暗号化は不要なことになります。

バーナム暗号は平文と同じサイズの鍵を使用します。その鍵を安全に配送できるならば、その経路を使って同じサイズの平文をそのまま送信すればよいのです。

事前に鍵を共有して、その後何回でも通信すれば良いと思うかもしれません。これは、やってはいけません。

もし、鍵が流出した際に、過去の通信すべてが解読されることになるからです。

よって、バーナム暗号では毎回の通信ごとに鍵を変えなければなりません。毎回変えるとなれば、鍵配送問題に直面します。

IPUSIRON　(2017)　暗号技術のすべて　翔永社