ワンタイムパッド

ワンタイムパッド (one time pad, OTP) とは、乱数列を高々1回だけ使う暗号の運用法である。1回限り暗号、めくり暗号などとも呼ばれる。発案は戦前であるが、戦後、クロード・シャノンにより情報理論的安全性としてその強度の概念が確立された^[1]。

概要

通信量と同じ長さの乱数列を使用し、日めくりのように1回使った乱数表は捨てる。例えば1から26の範囲をとる乱数の場合、1つの乱数でアルファベット(A-Z)の1文字を暗号化できる。乱数の秘匿だけで暗号強度を保てるので暗号化/復号がシンプルで、手作業でも処理できる。換字表やコードブックは公知のものでもよいという利点がある。

理論的には、正しく運用された場合に解読不可能となる。たとえ総当たりで解読しようとしても、総当たりで生成される多数の文章(文字列)の中には、送信者が暗号化した文章以外にも、人間が意味を読み取れる文章（文字列）が生成されてしまう。従って、解読者には、送信者自身の文章とそれ以外の人間が意味が読み取れる文章を区別することができず、解読不可能となる。C. E. Shannon による解読不能の証明では、平文を $X$ 、暗号文を $C$ として例えば次のように記述され、いずれも暗号文を入手することで平文を特定することのアドバンテージを得られないことを意味する。

条件付き情報量表現: $H(X|C)=H(X)$

条件付き確率表現: $Pr(X|C)=Pr(X)$

ただし、 $X$ と $C$ は互いに独立になる必要があり、そのためには鍵となる乱数列 $K$ が独立同分布(IID)となる必要がある。例えば運用方法の誤りで解読可能となる場合がある。乱数表の流出はもちろんだが、乱数の使いまわしも暗号強度の低下を招くので注意が必要である。たとえば、OTP乱数表の使い回しを元にして解読したのが、ベノナプロジェクトである。戦場で回収された暗号表がアメリカ国家安全保障局に回され、OTP乱数表を前線と米国駐在情報官の両方で使った事に気がついた。OTP乱数表といえども2度使えば解読が出来た。その結果ローゼンバーグ夫妻たちのスパイ網が摘発された^[要出典]。冷戦中であり暗号解読の事実をソ連に認知される事を回避するため、暗号解読のことは裁判では全く公開されなかった。冤罪疑惑が残るまま夫妻は死刑になったが、近年、ソ連のスパイである事が確認されるも、夫人は冤罪疑惑が残る。

乱数の作成は想像よりも困難である。数式を使って規則的に作ると、乱数列から元の式が再現される可能性がある。人が無作為に選択してもその癖が出る。通信量と同じ長さの乱数を作成、配布するのは労力が掛かるので、それに見合う重要通信に用いるのが望ましい。例えば米ソ・ホットラインやスパイ通信である。

乱数の配布・保管にも注意が必要である。配布、保存時に裏切り、窃盗、盗写が出来る。また、廃棄後のゴミから復元・再生される事がある。

なお、バーナム暗号と混同される事があるが、ワンタイムパッドを利用しないバーナム暗号もある。

作成配布方法

OTPの作成配布は主に4パターンに分類される。

単線型：一対一で一方的な指令・報告形式であり同じOTPを1冊ずつ配布する。最もシンプルな形式でもある。
複線型：一対ーで相互に着発信する形式であり異なるOTPを2冊ずつ配布する、もしくは1冊を配布して乱数が重複しないよう開始位置を分かち合う。
放線型：放送形式であり、放送者と各受信者に同じOTPを1冊ずつ配布する。
星型：複数が相互に着発信する形式であり同じOTPを各1冊ずつ配布し開始位置を分かち合う。各個の受発信量に見合う開始位置規制が必要である。

例

いま、アリスがボブに "HELLO" というメッセージを送りたいとする。ランダムなアルファベット列が書かれた紙からなる完全に同一の2つの帳(pad)が事前に何らかの手段で用意されており、安全な方法で2人に渡されていると仮定する。アリスは、適切な方法で帳から未使用のページを選ぶ。この方法は事前に決めておく。例えば、「勤労感謝の日には12枚目を使う」とか、「次のメッセージには次のページを使う」などである。選んだページに書かれたアルファベット列が、暗号化の鍵となる。帳とメッセージの各文字を、事前に決めておいた方法で組み合わせていく。このとき、"A"は0、"B"は1、……"Z"は25のように、各文字に数値を割り当てるのが普通である（必ずしもこの方法である必要はない）。この例では、剰余演算を使用して鍵とメッセージを組み合わせる。対応する鍵とメッセージの数値を足し合わせ、法を26とする剰余をとる。もし鍵が

X M C K L

で始まっていて、メッセージが "HELLO" だとすると、計算は次のようになる。

  23 (X)  12 (M)   2 (C)  10 (K)  11 (L) 鍵
+  7 (H)   4 (E)  11 (L)  11 (L)  14 (O) メッセージ
= 30      16      13      21      25     鍵 + メッセージ
≡ 4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) 鍵 + メッセージ (mod 26)

数値が25を超えた場合は、剰余演算によって、その数字を26で割った余り (mod 26) を使う点に注意。これは、簡単に言えば、計算結果がZを超えたら再びAから数え始めるということである。

これによって、ボブに送る暗号文は "EQNVZ" となる。ボブは帳から対応するページを選び、同じ手順を逆に実行して平文を得る。今度は鍵の数値を暗号文から“引く”点が暗号化時と異なるが、剰余演算を使うのは同じである。

    4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) 暗号文
-  23 (X)  12 (M)   2 (C)  10 (K)  11 (L) 鍵
= -19       4      11      11      14     暗号文 - 鍵
≡  7 (H)   4 (E)  11 (L)  11 (L)  14 (O) 暗号文 - 鍵 (mod 26)

暗号化のときとは逆に、もし数値が負になれば、26を加算して正の数にする。（実際に人間が行うと、引けないときには26を加算してから引くかもしれない。）

これでボブは "HELLO" というアリスのメッセージを復元できる。アリスとボブは、2人とも使い終わった暗号鍵の紙をすぐに破棄し、再使用したり暗号解読に使われたりするのを防ぐ。KGBは、エージェントに渡すワンタイムパッドに、よくフラッシュペーパーでできた小さな紙を使った。フラッシュペーパーは、化学合成されたニトロセルロースでできており、火をつけると一瞬で燃え上がり灰を残さない。

スパイ活動で使う古典的なワンタイムパッド（隠しやすくした小さな帳と尖った鉛筆、それに暗算を必要とする）は、ソフトウエアとして実装することも可能で、データファイル（平文）と暗号鍵（ランダムな数列）を入力とし、暗号化されたデータファイルを出力する。この場合、平文と鍵を組み合わせるのには排他的論理和（XOR）がよく使われる。XORはマシンに特化した機械命令で実行され、通常は非常に高速なためである。しかしながら、暗号鍵が真にランダムで、一度だけ使用され、決して敵に知られず、また使用後に確実に破棄されることなどを確実にするのは難しい。特にソフトウエアでは、平文の安全な処理や伝送、真にランダムな鍵、その鍵の一度だけの使用といった、ワンタイムパッド実装の補助的な部分に多くの困難を伴う。

日本陸軍のワンタイムパッド

太平洋戦争中に陸軍は、ワンタイムパッドを無限式乱数（または特乱）と称して採用した。開発と採用に、釜賀一夫が貢献している。第一線部隊で全面採用された結果、「第一線部隊の暗号は弱い」との常識を覆した。戦後、GHQ尋問官は、この暗号を理論解読することができなかったことを彼に示唆した。

乱数は前線の暗号兵が袋に入れた乱数カードを引き出すハイハット方式で逐次作成するのを原則としたが、実際には暗号兵が思いついた数字を書き出していく「フリーハンド」方式も併用された。

暗号兵が乱数を作成し、カーボン複写紙で2部作成した。盗写対策として、各ページを黒紙と綴じ糸でマスクした。使用済みのワンタイムパッド（ページ）は、焼却処分した。未使用部分は、敵に捕獲されても問題なしとされ、玉砕時にも処分されなかった。陸軍の通信体系では通信相手が限定されているので、ワンタイムパッドの印刷・配布も実現できた。

ワンタイムパッドを捕獲した米兵からは、俗に「トイレットペーパー」と呼ばれた（価値がなく、一度使用したら捨てることから）。

参考文献

「座談会日本陸軍暗号はなぜ破られなかったか」、『歴史と人物』-太平洋戦争シリーズ：日本陸軍かく戦えり、1985年12月
「私も或る日、赤紙一枚で　－ある応召暗号兵の記録－」、太田俊夫、光人社

量子暗号との関係

ワンタイムパッドの最大の難点であり弱点は、事前に十分な量の秘密情報を共有しなければならない点である。ここで、なぜ「事前に」でなければならないか、ということを考えると、本文の通信時に、同時に同じだけの情報量の鍵を送っても安全なような秘匿性の高い回線があるのならば、そちらで本文ごと送ってしまえば良いからである。

そのため、ワンタイムパッドの最も多い利用法は、暗号の本文ではなく、鍵配送問題の解決である。一般に鍵配送問題の解決は困難だが、一般の暗号では鍵は本文に比べごく小さいのであるから、その鍵だけを確実に安全に送受信するためにワンタイムパッドを使用する。この場合、量は多くないものの、秘密情報の事前の共有は必要である。

量子暗号と総称される分野の研究の目的はさまざまであるが、実現が目指されていることのひとつに、事前の手続きに依らない情報の共有がある。それを利用することにより、前述した、ワンタイムパッドを利用した鍵の通信と同等のことが、事前の秘密情報の共有を必要とせず実現できる。量子の性質を利用した暗号プロトコルが量子暗号プロトコルであるが、その一つであるBB84などは、そのような事前の共有なしの情報共有を利用したプロトコルである。（It is usually explained as a method of securely communicating a private key from one party to another for use in one-time pad encryption. （英語版WikipediaのBB84の記事より））

脚注

^ Shannon, Claude. "Communication Theory of Secrecy Systems", Bell System Technical Journal, vol. 28(4), pp. 656–715, 1949.

外部リンク

Collections in Cryptology - One Time Tape Devices

[1] Shannon, Claude. "Communication Theory of Secrecy Systems", Bell System Technical Journal, vol. 28(4), pp. 656–715, 1949.

[1]