やっほー! こんにちはー!
物理好きのオザキ(@sena0801masato)です。
今回は、現代暗号の1つであるストリーム暗号の基礎になっている、ワンタイムパッドについてお話しようと思います。
自分なりの考察をまとめたものですから、間違っている可能性もあります。
この記事の対象者
- 暗号の勉強を始めたばかり
- 暗号の難しい数式は見たくない!
- 絶対に安全な暗号ってなに?
暗号に関する用語の紹介
暗号を勉強するときによく出てくる単語です。
だいたい分かる人は本題まで飛んじゃいましょう。本題へ
- 平文：第三者に見られたくない元の文のこと。
- 暗号文：平文を第三者が見ても意味が分からないように細工した文のこと。
- 暗号化：平文を暗号文にすること。
- 復号：暗号文を平文にすること。
復号化と書かれることもあるが、正しくないです。
○○化と書きたいなら、暗号にするから暗号化、平文にするから平文化になります。
(でも平文化は一般的に使われていません)
「暗号化」の対語が「復号化」ではない理由の記事が参考になります。 - 鍵：暗号文にするときの細工(暗号化)で使うもの。
ワンタイムパッドとは
まずはワンタイムパッドとは何か、順番に確認していきます。
ワンタイムパッドとは
ストリーム暗号の基礎になった暗号です。
ストリーム暗号とは
共通鍵暗号の1つです。
bit、バイト、ワードごとに暗号化します。
共通鍵は擬似乱数によって平文より長いデータにして使われます。
共通鍵暗号とは
現代暗号のうち、暗号化に使う鍵と復号に使う鍵が同じものです。
例えると玄関の鍵みたいな感じです。
住んでる人全員が同じ鍵(共通鍵)を持っていれば家の中(平文)が見れます。
現代暗号とは
情報化社会で現在使われている暗号のことです。
暗号を歴史的に分類すると、古典暗号と現代暗号があります。
古典暗号を分類すると、換字式暗号と転字式暗号があります。
現代暗号を分類すると、共通鍵暗号と公開鍵暗号があります。
ワンタイムパッドの原理
ワンタイムパッドとは平文と共通鍵をbit(0と1の並び)で考えて、bitごとにXOR演算をします。
共通鍵に真の乱数を使うと、共通鍵の推測や平文を特定することがまったくできません。
ただし共通鍵のデータが平文より長くなってしまうため、利便性が悪く現在あまり使われていません。
ここで私は疑問を持ちました。
- なぜbitで考えるか?
- bitの並びにも偏りがあるでは?
- なぜXOR演算を使うのか?
- なぜ完全に安全なのか
これらを考えていきたいと思います。
ワンタイムパッドの安全性
なぜbitで考えるか?
結論：平文で使われている文字に偏りがあるから
文章を作っているのは人間であり、文章として成立するには一定のルールに従って書かなければなりません。
すると、よく使われる単語やよく使われる文字が出てきます。
これが平文で使われている文字の偏りです。(アルファベットだとe,t,aがよく使われ、z,qがあまり使われません)
この偏りは統計的に出てしまうため、避けようがありません。
この偏りを分かりにくくするために、bitで考えるのだと思います。
bitの並びにも偏りがあるでは?
結論：共通鍵が真の乱数のとき、偏りは生じない
さきほど、平文の文字に偏りはあると言いました。
その偏りのある平文に基づいてbitに変換しても、あるまとまりごとに同じ並びのbitが出てきたり、偏りがあるのではないかと思いました。
しかし、bitにすると、どこからどこまでを1つのまとまりとして見るか分かりにくくなる、共通鍵にも何かしらの偏りがないと同じ並びが出てこないことに気づきました。
よって共通鍵を作るときは、あるルール(擬似乱数など)によって作られるものではなく、完全な真の乱数を使う必要があると納得しました(笑)
なぜXOR演算を使うのか?
結論：便利かつ完全な安全性を持つから
XOR演算を使う利点は2つあります。
- 平文に鍵を2回演算させると平文に戻るから
(暗号として成り立つためには当たり前(笑)) - 暗号文の各bitで0と1になる確率が同じになるから
(XNOR演算でもいいが回路の作りやすさからXOR演算を使っていると思います。)
1つ目を説明していきます。(2つ目は次の節と関わりがあるので次の節で話します。)
暗号化と復号
XOR演算の確認
入力をa, b、出力をcとします。
| a | b | c |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
平文に鍵を2回演算させると平文に戻る
平文を01011、共通鍵を00101とします。
- 暗号化
平文に共通鍵を使ってXOR演算を1回します。
すると結果は01110に、これが暗号文となります。
| 0 | 1 | 0 | 1 | 1 | |
| + | 0 | 0 | 1 | 0 | 1 |
| = | 0 | 1 | 1 | 1 | 0 |
- 復号
暗号文に共通鍵を使ってXOR演算を1回します。
(つまり平文に共通鍵を使ってXOR演算を2回と同じ)
すると結果は01011になり、これは平文と一致します。
| 0 | 1 | 1 | 1 | 0 | |
| + | 0 | 0 | 1 | 0 | 1 |
| = | 0 | 1 | 0 | 1 | 1 |
- 試しに共通鍵同士をXOR演算してみる
すると00000となり、平文に戻る仕組みがより分かると思います。
| 0 | 0 | 1 | 0 | 1 | |
| + | 0 | 0 | 1 | 0 | 1 |
| = | 0 | 0 | 0 | 0 | 0 |
なぜ完全に安全なのか
結論：暗号文が分かっても分からなくても、平文の値の確率が同じだから
それぞれのbitに依存関係がないため、1つのbitに注目します。
1bitの平文をM、秘密鍵をK、暗号文をCとします。
$...$が起こる確率を$P_{(...)}$とします。
秘密鍵が真の乱数より
P_{(K=0)}=\frac{1}{2}\\
P_{(K=1)}=\frac{1}{2}
暗号文が0のとき$P_{(C=0)}$を考えます。
P_{(C=0)}=P_{(C=0かつM=0)}+P_{(C=0かつM=1)}
右辺の項を1つずつ見ていきます。
右辺の第1項は、XOR演算でM=0のとき、C=0となるのはK=0より
P_{(C=0かつM=0)}=P_{(K=0かつM=0)}
MとKのbitに依存関係がないから
P_{(K=0かつM=0)}=P_{(K=0)}P_{(M=0)}\\
=\frac{1}{2}P_{(M=0)}
つまり
P_{(C=0かつM=0)}=\frac{1}{2}P_{(M=0)}
右辺の第2項も同様に
P_{(C=0かつM=1)}=P_{(K=1かつM=1)}\\
=P_{(K=1)}P_{(M=1)}\\
=\frac{1}{2}P_{(M=1)}
まとめると
P_{(C=0)}=P_{(C=0かつM=0)}+P_{(C=0かつM=1)}\\
=\frac{1}{2}P_{(M=0)}+\frac{1}{2}P_{(M=1)}\\
=\frac{1}{2}(P_{(M=0)}+P_{(M=1)})
また、すべての起こり得る確率の和は1より
$P_{(M=0)}+P_{(M=1)}=1$を使って
P_{(C=0)}=\frac{1}{2}
同様に暗号文が1のとき$P_{(C=1)}=\frac{1}{2}$となります。
つまり秘密鍵が真の乱数のとき暗号文は0か1のランダムと分かります。
次に
C=0が分かっているときのM=0の確率(条件付き確率)を考えます。
C=0が分かっているときのM=0の確率を$P_{(C=0|M=0)}$とします。
条件付き確率の定義から
P_{(C=0|M=0)}=\frac{P_{(C=0かつM=0)}}{P_{(C=0)}}
右辺第1項で示した$P_{(C=0かつM=0)}=\frac{1}{2}P_{(M=0)}$と右辺の結果$P_{(C=0)}=\frac{1}{2}$より
P_{(C=0|M=0)}=\frac{\frac{1}{2}P_{(M=0)}}{\frac{1}{2}}\\
=P_{(M=0)}
つまり、C=0と分かった状態でのM=0の確率と、Cが何か分からない状態でのM=0の確率が同じとなりました。
同様に他のパターンでも同じことが言えます。
よってC(暗号文)からM(平文)はまったく推定できない、完全に安全な暗号ということが分かります。
まとめ
共通鍵が平文より長くないといけない点と、真の乱数をどうやって生成するかという点がありますが、
共通鍵に真の乱数を使う条件さえ満たせば、シンプルかつ完全に安全な暗号になるなぁと思いました。
ではでは!
参考文献
中西透『現代暗号のしくみ』 2017/01/10第1刷 共立出版