🤽‍♀️

ワンタイムパッドはなぜ安心安全なのか

2021/01/03に公開

Security

現代のインターネット通信において利用されるケースはほとんどありませんが、安全性に関してはほぼ完璧なランダム性を誇るワンタイムパッドについて少し紹介します。

ワンタイムパッドって何？

ワンタイムパッド（OTP）とは、秘密鍵の事前共有を前提とする共有鍵暗号方式の一つです。太平洋戦争では日本陸軍で利用された歴史があり、情報理論のパパ、クロード・シャノンによってその安全性が証明されています。

ワンタイムパッドの仕組み

ワンタイムパッドは排他的論理和（XOR）を利用して平文を暗号化します。排他的論理和についての詳細は他の説明記事をご覧ください。

暗号化

まず平文1ビットごとに秘密鍵との排他的論理和を演算し、暗号文を算出します。例えば平文が1101001、秘密鍵が1000100だった場合
$1\oplus1=0$ , $1\oplus0=1$ , $0\oplus0=0$ といった具合に平文の1ビット目と秘密鍵の1ビット目、平文の2ビット目と秘密鍵の2ビット目...で排他的論理和をとっていきます。ここでの秘密鍵のビット列は完全なランダム（真の乱数）である必要があります。この要領でビット列を全て暗号化すれば、ワンタイムパッドの暗号文の完成です。

復号

復号に関しても至ってシンプルです。排他的論理和は、演算に用いたどちらかの値は、他方の値と演算結果の値の排他的論理和であるという特徴があります。下に例を挙げます。

0 XOR 1 = 1 ⇨ 0(左項) = 1(右項) XOR 1(演算結果) 
1 XOR 1 = 0 ⇨ 1(左項) = 1(右項) XOR 0(演算結果)

ワンタイムパッドは共通鍵暗号なので、復号をするデータ受信者も秘密鍵を保持していることになります。なのでこの排他的論理和の性質を使って1ビットずつ復号を行うことができるのです。

ワンタイムパッドの安全性

以上がワンタイムパッドの仕組みになります。見ての通りすごく簡潔ですが、実はこの上ない情報理論的安全性、つまり当てずっぽと同じ確率でしか平文を割り出せないことが証明されています。

前提として、平文のビット列を $M$ 、秘密鍵のビット列を $K$ 、算出された暗号文を $C$ とします。

暗号文の発生確率を調べる

秘密鍵のビットの確率

1ビットずつ暗号化する過程を考えるとして、 $K$ のビットが0である確率と1である確率はどちらも1/2、式にすると $Pr(K=0)=Pr(K=1)=\frac{1}{2}$ となります。これは秘密鍵が真の乱数であるという前提に基づいています。

暗号文のビットの確率

次に $C$ のビットが0である確率を調べます。 $C$ と $M$ が決まれば $K$ の値も必然的に判明するので $M$ との関係のみを考えると、 $C=0$ かつ $M=1$ の場合と $C=0$ かつ $M=0$ の場合が存在します。これを式にすると
$Pr(C=0)=Pr(C=0\land M=0)+Pr(C=0\land M=1)$
となります（①）。同様に
$Pr(C=0\land M=0)=Pr(C=0\land K=0)$
も成り立つことがわかります(②)。
また先にも書いた通り、 $K$ は真の乱数であり、 $M$ との依存関係はないため、
$Pr(K=0\land M=0)=Pr(K=0)Pr(M=0)=\frac{1}{2}\cdot Pr(M=0)$
が成り立ちます。この式と②の式を組み合わせると、
$Pr(C=0\land M=0)=\frac{1}{2}\cdot Pr(M=0)$
が導き出されます(③)。同様の演算で
$Pr(C=0\land M=1)=\frac{1}{2}\cdot Pr(M=1)$
であることも分かります。ここで上の二つの式と①の式を組み合わせると、
$Pr(C=0)=\frac{1}{2}\cdot Pr(M=0)+\frac{1}{2}\cdot Pr(M=1)$
つまり
$Pr(C=0)=\frac{1}{2}\cdot {Pr(M=0)+Pr(M=1)}$
となります。M=0になる確率とM=1になる確率を足せば当然1になるので、
$Pr(C=0)=\frac{1}{2}$
であると分かります(④)。これはつまり暗号文の一つのビットが0になる確率が1/2、完全にランダムであることを示しています。

暗号文から平文を推測できる確率を調べる

条件付き確率を用いた演算

暗号文のある１ビット $C$ が0であるとわかっていた時、対応する平文の1ビット $M$ が0である確率を
$Pr(M=0|C=0)$
と表す。これを条件付き確率といいます。この式はつまり、 $C$ が0の確率を分母にとり、 $C=0\land M=0$ を分子にとった分数 $\frac{Pr(C=0\land M=0)}{Pr(C=0)}$ と同じです。前章④より $Pr(C=0)$ は $\frac{1}{2}$ 、③より $Pr(C=0\land M=0)$ は $\frac{1}{2}\cdot Pr(M=0)$ 、つまり上の条件付き確率の式は
$Pr(M=0|C=0)=\frac{Pr(C=0\land M=0)}{Pr(C=0)}=\frac{\frac{1}{2}\cdot Pr(M=0)}{\frac{1}{2}}=Pr(M=0)$
となります。これはつまり、Cが0であるとわかっている時のMが0になる確率と、Cが分からない状態でMが0になる確率が等しい、言い換えれば暗号文を知っても平文を知ることの役には立たないということなのです。これでワンタイムパッドの安全性を理解していただけたでしょうか。

なんで使われてないの？

これ以上ないほど安全性の高いのになぜ日常的に通信で使われていないのでしょうか。その最大の理由は秘密鍵が長すぎるということです。これまでの説明を読んできたあなたは、ワンタイムパッドにおいて秘密鍵の長さが平文の長さと同じ必要があるとわかっていただけたはず。１ビットずつ平文と真の乱数である秘密鍵を用いて暗号化するので、長さが違ってはランダム性に狂いが出てしまうのです。しかし、平文と秘密鍵の長さが同じということは通信するデータ量が元の2倍になるということです。短いチャットとかであれば耐えますがこれが4K動画等超重量級のデータになると話が違ってきます。いくら安全でも重すぎて届かないのでは意味がないのです。

おわりに

このような排他的論理和の特性を用いた暗号は、DESなどの暗号にも利用されています。暗号は調べれば調べるほど楽しいので大学でCSを学ぶのが楽しみで仕方ないですね。