TeXで暗号化(3) バーナム暗号

前回からかなり間が空いてしまいましたが，シリーズ「TeX で暗号化」の第3回です．

前回までの記事（第1回と第2回）では，それぞれシーザー暗号とアフィン暗号を扱い，いずれも暗号化・復号化方法を示した後にそれらが比較的簡単に「解読」できることを TeX のコードを記しながら述べてきたわけですが，今回は絶対に「解読」できない最強の暗号・バーナム暗号を扱いたいと思います．

突然の告知

本題に入る前に，いきなりですが1つ告知をさせてください．昨日，前回・前々回の記事で扱った命令および今回の記事で扱う命令の改良版をまとめたパッケージを公開しました．

ClassicalCipher - GitHub

是非，本シリーズで紹介した命令をテストしてみるときにはこのパッケージをご活用ください *1 ．v0.1ということもあり，まだまだ機能的に不十分な部分もありますが，記事中で紹介した~~手抜きの~~命令よりは格段に使い勝手がよくなっていると思います．もちろん，なんらかの実用的な用途で利用して頂いても構いません（~~実用的な使い道があるとはとても思えませんが~~）．

なお，classicalcipher.sty 中で記述している命令の定義は諸々の事由により些か煩雑なものとなっているので，本稿では簡略化した命令の定義を掲載しており，仕様も一部一致していないので注意してください．

バーナム暗号

バーナム暗号のアルゴリズムは極めて単純です．

まず， $\{0,1\}$ の並びからなる平文 $P$ と鍵 $S$ を用意します（ただし $S$ は $|P| = |S|$ を満たすランダムな文字列）．そして， $P$ と $S$ を用いて以下のような単純な演算を行い暗号文 $C$ を生成して終了です．

$\displaystyle\quad C = P \oplus S$

ここで， $\oplus$ は排他的論理和（XOR演算）を表します．排他的論理和などと言うと難解な専門用語のように聞こえますが，大したことはありません．次の表（真偽表）のような挙動を示す演算のことです．

入力1	入力2	出力
1	1	0
1	0	1
0	1	1
0	0	0

要するに「2つの入力が一致していると 0（偽），異なっていると 1（真）」を返します．

ところで，上記の真偽表の列を次のように入れ替えてみます．

入力2	出力	入力1
1	0	1
0	1	1
1	1	0
0	0	0

すると，入力1は入力2と出力の排他的論理和になっていることがわかります．ここで，入力1が平文，入力2が鍵，出力が暗号文であったと考えれば，鍵を暗号文で「暗号化」することによって平文を得ることができる（すなわち復号化することが可能）であることが直感的に理解できるかと思います．

このことを敢えて式で示すと次のようになります．

$\displaystyle\quad C \oplus S = (P \oplus S) \oplus S = P \oplus (S \oplus S) = P \oplus \{0\}^* = P$

最後の $P \oplus \{0\}^* = P$ （ $\{0\}^*$ は 0 の並びを表す）という変形は，最初の真偽表を「入力1から出力への変換」と考えて見返すと「入力2が 1 のとき真偽反転，0 のときはそのまま」となっていることから理解していただけるでしょう．

以上のことから，バーナム暗号は暗号文と鍵があれば暗号化とまったく同じ手順で復号化も行うことができるということがわかります．

バーナム暗号の TeX 実装

平文を指定した鍵でアフィン暗号化するマクロ \Vernam を作ります．

\Vernam{〈鍵〉}{〈平文〉}

なお，〈鍵〉と〈平文〉は ASCII コード表に載っている文字（以下，本稿では「ASCII 文字」と表記します）であれば基本的に何でも使用できます *2 ．ただし，鍵は平文と同じ長さである必要があります（平文より長い分には問題ありませんが，無視されるので意味もありません）．

さて，さきほど紹介したようにバーナム暗号による暗号化を行うためには，まず平文・鍵を $\{0,1\}$ の並びに変換する必要があります．これは単純に各文字の ASCII コードを2進数で表現してやればいいでしょう．そのための命令 \char@to@bin の定義を，その逆をする命令 \@bin@to@char の定義とともに載せておきます *3 ．

\makeatletter

\newcount\@result

\def\char@to@bin#1{%
  \bgroup
  \@tempcnta=`#1\relax
  \def\temp@bin{}%
  \def\add@temp@bin##1{\edef\temp@bin{##1\temp@bin}}%
  \@whilenum\@tempcnta>\z@\do{%
    \@tempcntb=\@tempcnta
    \divide\@tempcntb\tw@
    \multiply\@tempcntb\tw@
    \advance\@tempcntb-\@tempcnta
    \multiply\@tempcntb\m@ne
    \add@temp@bin{\the\@tempcntb}%
    \divide\@tempcnta\tw@
  }%
  \@tempcntb=\z@
  \expandafter\@tfor\expandafter\@member\expandafter:\expandafter=\temp@bin\do{%
    \advance\@tempcntb\@ne
  }%
  \xdef\@bin{%
    \ifcase\@tempcntb\relax0000000\or000000\or00000\or0000\or000\or00\or0\fi
    \temp@bin
  }%
  \egroup
}

\def\@bin@to@char#1{%
  \bgroup
  \@tempcnta=#1\relax
  \@tempcntb=\@ne
  \global\@result=\z@
  \expandafter\@tfor\expandafter\member\expandafter:\expandafter=\the\@tempcnta\do{%
    \multiply\@tempcntb\tw@
  }%
  \divide\@tempcntb\tw@
  \expandafter\@tfor\expandafter\member\expandafter:\expandafter=\the\@tempcnta\do{%
    \@tempcnta=\member\relax
    \ifnum\@tempcnta=\@ne
      \advance\@result\@tempcntb
    \fi
    \divide\@tempcntb\tw@
  }%
  \char\@result
  \egroup
}

\makeatother

いずれも，動作原理は非常に単純です．

\char@to@bin ではまず，受け取った文字の ASCII コード（10進数）を取り出し，これを商が1になるまで2で割り，それぞれの演算の余りを並べることで2進数化します（因みに，\def の定義中に登場する ## は # 1個に変換して解釈されます．ここでの ##1 は \add@temp@bin の第一引数を意味するわけですが，これを #1 と書くと，\char@to@bin の第一引数と解釈されてエラーになってしまいます）．ただし，結果が7桁にならなかった場合には頭に必要な数だけ0を補います．

その逆の \@bin@to@char は，受け取った2進数を10進数に変換し，\char コマンドでそのコードが表す文字を出力します．ただし，TeX で数値を後ろから読むのは（不可能ではありませんが）少々厄介なので，先に桁数を数えて上位の桁から足し算する方式を採っています．

これで，文字と ASCII コード（2進数）の相互変換ができるようになったので，あとは XOR 演算を行う部分を実装すれば \Vernam 命令が完成します．

\makeatletter

\def\Vernam#1#2{%
  \bgroup
  \def\temp@bin@key{}%
  \def\add@temp@bin@key##1{\edef\temp@bin@key{\temp@bin@key##1}}%
  \@tfor\member:=#1\do{%
    \expandafter\char@to@bin\member
    \add@temp@bin@key\@bin
  }%
  \@tempcnta=\z@
  \def\add@temp@bin@str##1{\edef\temp@bin@str{\temp@bin@str##1}}%
  \@tfor\member:=#2\do{%
    \def\temp@bin@str{}%
    \expandafter\char@to@bin\member
    \expandafter\@tfor\expandafter\@member\expandafter:\expandafter=\@bin\do{%
      \advance\@tempcnta\@ne
      \get@bin@key\temp@bin@key\@tempcnta
      \ifnum\@result=\@member
        \@tempcntb=\z@
      \else
        \@tempcntb=\@ne
      \fi
      \expandafter\add@temp@bin@str\the\@tempcntb
    }%
    \@bin@to@char\temp@bin@str
  }%
  \egroup
}

\makeatother

冒頭（\bgroup 以降 \@tempcnta=\z@ まで）部分では〈鍵〉を先ほどの \char@to@bin で1文字ずつ2進数に変換し，\temp@bin@key にすべて連結させて格納しています．

次に「現在（2進数 ASCII コード化した平文の）何文字目を処理しているか」を保持するためのカウンタレジスタ \@tempcnta を初期化し，「平文を1文字ずつ ASCII コード（2進数）化」するループとさらにその中の「ASCII コード（2進数）を1文字ずつ処理」するループで2進数 ASCII コード化した平文を1文字ずつ処理できるようにしています（内側のループが1度回る度に \@tempcnta が +1 されます）．

その内側のループでは「（\@tempcnta が保持する値）番目」の鍵（0または1）を \temp@bin@key から取り出し，読んだ平文（0または1）と一致するかどうかを \ifnum で判定して，一致すれば0，一致しなければ1を \temp@bin@str の末尾に追加していきます．

なお，「（\@tempcnta が保持する値）番目」の鍵（0または1）を \temp@bin@key から取り出す処理には，以下の \get@bin@key 命令が用いられています．

\makeatletter

\def\get@bin@key#1#2{%
  \bgroup
  \@tempcnta=#2\relax
  \@tempcntb=\z@
  \@result=\m@ne
  \expandafter\@tfor\expandafter\member\expandafter:\expandafter=#1\do{%
    \advance\@tempcntb\@ne
    \ifnum\@tempcnta=\@tempcntb
      \global\@result=\member\relax
    \fi
  }%
  \egroup
}

\makeatother

これで，ASCII コード（2進数）からなる暗号文が \temp@bin@str 内に格納されたので，最初に用意した \@bin@to@char で「文字」として出力させて終了です．

なお，バーナム暗号の暗号化と復号化の手順はまったく同一なので，

\Vernam{〈鍵〉}{〈暗号文〉}

とすれば \Vernam を復号化に使用することもできます．

バーナム暗号は解読できない

A君が \Vernam コマンドを使って次のような暗号文を作り，友人に送付したとします．

1fem87a=6w(

A君から暗号文を受け取ったB君は \Vernam コマンドを使って解読を試み，鍵が xF+(}sAus;x のときに意味の通る文になることに気が付きました．

【入力】

\Vernam{xF+(\}sAus;x}{1fem87a=6w(}

【出力】

I␣NEED␣HELP

また，同じくA君から暗号文を受け取り解読を試みたC君は，鍵が v/3(UR,rx2q のときに意味のわかる文字列になることを発見しました．

【入力】

\Vernam{v/3(UR,rx2q}{1fem87a=6w(}

【出力】

GIVEmeMONEY

これは困りました．解読（？）の結果がB君とC君で異なっています．

さらに，送信主のA君に聞くと 1fem87a=6w( という暗号文は次のように生成されたといいます．

\Vernam{p*)NqdAjs;d}{ALL\ IS\ WELL}

すなわち，A君は「ALL IS WELL（万事快調）」ということを伝えたかったわけですが，B君はこれを「I NEED HELP（助けが必要だ）」，C君は「GIVE ME MONEY（金をよこせ）」と，まったく見当違いの “解読” をしてしまったことになります．

実は，バーナム暗号のアルゴリズムでは，原理上長さが等しい限り任意の文字列を任意の文字列に変換できてしまいます *4 ．そのため，暗号化に用いた鍵を知らない人物が解読を試みたところで，意味の通る文を発見することはできても，どれが「真の平文」であるのかを判定することは不可能です．そのため，バーナム暗号は「解読不能」であると言うことができます．

なお，以上は直感的な説明でしたが，バーナム暗号の解読不能性は数学的にも証明されています．その証明に興味のある読者は下記資料の p.6-7 などを参照するといいかもしれません．

One Time Pad Encryption - The unbreakable encryption method (mils)

バーナム暗号は実用に向かない

これまでの説明では，バーナム暗号は「アルゴリズムが単純」かつ「解読不能」と非の打ち所のない暗号のようなのですが，実際にはほとんど実用されていません．

それはなぜか．

本稿では，冒頭の方で「鍵は暗号文と同じ長さをもつランダムな文字列である」ということをさらっと記述しました．しかし実は，これが大問題です．鍵がなければ正しく復号化することは不可能であることは既に示した通りなので，誰かに情報を伝えるには暗号文とは別に，鍵も『安全な方法』で伝える必要があるわけですが，その鍵が「暗号文と同じ長さをもつ」のです *5 ．当然「そんな方法があるなら最初から平文を『安全な方法』で送ればいいじゃないか」という話になります．

結局，バーナム暗号は『安全な方法』で伝えるべきものを平文から鍵に移し替えているだけで，通信の安全性を確保するという意味ではほぼ意味をなしていないと言うことができます．

\Vernam 命令の問題点

上述したバーナム暗号全般の問題とは別に，\Vernam 命令が抱える別の問題があります．それは，暗号化後の文字列が必ずしも TeX ソースに記述しやすいものとならない（もしくは印字不能文字に変換されて必要な情報が欠落してしまう）可能性があるという問題です．

この問題を解決するため，本稿の最初に告知させていただいた ClassicalCipher パッケージでは，暗号化後の出力を文字に変換する前の ASCII コード（2進数）のまま出力する命令 \BinVernam を用意してあります．また，この命令で出力される ASCII コード（2進数）を平文に復号化するための \DecodeBinVernam も用意されているので，これで \Vernam 命令特有の問題点を解消することができます．

告知ふたたび

ClassicalCipher パッケージでは本シリーズで紹介してきた種々の命令を強化してより便利になった命令を収録しています．是非，このパッケージを活用して「安全な」文書作成を実践してみてください *6 ．

Happy Secure LaTeXing!!

*1:詳しい使い方等はパッケージ付属の README.md を参照してください．

*2:ただし，今回の実装では TeX で特殊な働きをする文字（% や & など）はエスケープする（\% や \& とする）必要あります．

*3:\char@to@bin と \@bin@to@char は「対称的」な名前がつけられていますが，挙動は必ずしも対称でない点に注意してください．\char@to@bin は ASCII 文字を引数として受け取り，結果（ $\{0,1\}$ の文字トークン列）を \@bin に格納して返すのに対し，\@bin@to@char は $\{0,1\}$ の文字トークン列（またはカウンタ）を引数として受け取り，結果（ASCII文字）をそのまま「出力」します．

*4:今回の実装では，実際には印字可能文字のコードに変換されるとは限らないので「任意の」は言い過ぎになります．

*5:反復を入れるなど鍵を短くする方策を取ると解読不可能性が崩れ，そもそも「バーナム暗号」とは呼べなくなります．

*6:ただし，筆者は当該パッケージを利用することによって起こったあらゆる事象に対しても一切の責任を負わないので，ご利用は自己責任でお願いします．