ワンタイムパッド

ワンタイムパッド (one time pad, OTP) とは、乱数列を高々1回だけ使う暗号の運用法である。1回限り暗号、めくり暗号などとも呼ばれる。発案は戦前であるが、戦後、クロード・シャノンにより情報理論的安全性としてその強度の概念が確立されたShannon, Claude. "Communication Theory of Secrecy Systems", Bell System Technical Journal, vol. 28(4), pp. 656–715, 1949.。

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

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

条件付き情報量表現: 

条件付き確率表現: 

ただし、とは互いに独立になる必要があり、そのためには鍵となる乱数列が独立同分布(IID)となる必要がある。

理論的には解読不能でも、運用方法を誤り解読が可能になる場合がある。乱数表の流出はもちろんだが、乱数の使いまわしも暗号強度の低下を招く。たとえば、ベノナ・プロジェクトでは使いまわされた乱数表をもとに解読作業が行われてた。戦場で回収された暗号表がアメリカ国家安全保障局に回されP乱数表が前線と米国駐在情報官の両方で使われた事が発覚したのである。ワンタイムパッドによる乱数表といえども2度使えば解読が出来た。その結果ローゼンバーグ夫妻たちのスパイ網が摘発された。冷戦中であり暗号解読の事実をソ連に認知される事を回避するため、暗号解読のことは裁判では全く公開されなかった。

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

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

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

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

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

量子暗号との関係
ワンタイムパッドの最大の難点は、事前に十分な量の秘密情報を共有しなければならない点である本文と同じ情報量の鍵を送っても安全な秘匿性の高い回線があるのならば、その回線で本文を送ってしまえばそもそも暗号化は不要である。そのため、ワンタイムパッドの最も多い利用法は、暗号の本文ではなく、鍵配送問題の解決である。一般に鍵配送問題の解決は困難だが、一般の暗号では鍵は本文に比べごく小さいのであるから、その鍵だけを確実に安全に送受信するためにワンタイムパッドを使用する。この場合、量は多くないものの、秘密情報の事前の共有は必要である。

量子暗号と総称される分野の研究の目的はさまざまであるが、実現が目指されていることのひとつに、事前の手続きに依らない情報の共有がある。それを利用することにより、前述した、ワンタイムパッドを利用した鍵の通信と同等のことが、事前の秘密情報の共有を必要とせず実現できる。量子の性質を利用した暗号プロトコルが量子暗号プロトコルであるが、その一つであるBB84などは、そのような事前の共有なしの情報共有を利用したプロトコルである。

脚注

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

関連項目
暗号理論
ベノナ（再利用されたワンタイムパッドを破った例）
ワンタイムパスワード

外部リンク
Collections in Cryptology - One Time Tape Devices

Category:暗号
Category:クロード・シャノン