TeXで暗号化(2) アフィン暗号

今回はシリーズ「TeXで暗号化」の第二弾です．初回記事で扱ったシーザー暗号は極めて単純な暗号だったので，今回はそれよりも少しだけ複雑な暗号に挑戦してみます．また，この少し複雑になった暗号に対して，ブルートフォースアタックよりもほんの少しだけ高度な方法で解読を行うことを考えてみようと思います．

アフィン暗号

シーザー暗号は $C \equiv P + n \pmod{26}$ という一般式で書き表せました．しかし，鍵として自由に動かせる部分が $n$ しかないため，非常に弱い暗号でした．そこで，この式を次のように拡張してみます．

$\displaystyle\quad C \equiv aP + b \pmod{26}$

これで，鍵の数を1つから2つに増やすことができました．ただし，modの性質上，復号化可能であるためには $a$ は26と互いに素である必要があります．そこで，本記事では $a$ に対して次のような制約を設けることにします．

$\displaystyle\quad 0 \leq a \leq 25,\;\gcd(a,26)=1$

この条件に当てはまる $a$ をすべて書き出すと，

$\displaystyle\quad a=1,3,5,7,9,11,15,17,19,21,23,25$

の12通りの値をとり得ることがわかります． $b$ は26通りなので，アフィン暗号の鍵の種類は全部で312通りとなります．

なお，定義から明らかなように，シーザー暗号は $a=1$ のアフィン暗号です．

\Affine命令の実装と使い方

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

\Affine{〈鍵A〉}{〈鍵B〉}{〈平文〉}

〈鍵A〉と〈鍵B〉というのは，それぞれ先ほどの定義式の $a,b$ にあたる整数です．

それでは，早速実装してみましょう

\makeatletter

\newcount\@result
\newcount\@character
\newcount\key@a
\newcount\key@b

\def\calc@mod#1#2{%
  \bgroup
  \@tempcnta=#1\relax
  \@tempcntb=#2\relax
  \@whilenum\@tempcntb>\@tempcnta
    \do{\advance\@tempcntb-\@tempcnta}%
  \ifnum\@tempcntb=\@tempcnta
    \@tempcntb=0
  \fi
  \global\@result=\@tempcntb
  \egroup
}

\def\Affine#1#2#3{%
  \bgroup
    % 鍵の処理
    \key@a=#1\relax
    \key@b=#2\relax
    \ifnum\key@b<0
      \multiply\key@b\m@ne
      \calc@mod{26}{\key@b}%
      \key@b=\@result
      \multiply\key@b\m@ne
      \advance\key@b26
    \else
      \calc@mod{26}{\key@b}%
      \key@b=\@result
    \fi
    % 暗号化処理
    \@tfor\member:=#3\do{%
      \@character=\expandafter`\member\relax
      \ifnum\@character>`Z
        % 小文字
        \ifnum\@character<`a
          \member
        \else
          \ifnum\@character>`z
            \member
          \else
            \advance\@character-`a
            \multiply\@character\key@a
            \advance\@character\key@b
            \calc@mod{26}{\@character}%
            \@character=\@result
            \advance\@character`a
            \char\@character
          \fi
        \fi
      \else
        % 大文字
        \ifnum\@character<`A
          \member
        \else
          \ifnum\@character>`Z
            \member
          \else
            \advance\@character-`A
            \multiply\@character\key@a
            \advance\@character\key@b
            \calc@mod{26}{\@character}%
            \@character=\@result
            \advance\@character`A
            \char\@character
          \fi
        \fi
      \fi
    }%
  \egroup
}

\makeatother

\calc@modの定義は前回と同じですが，再掲しておきました．それ以外の部分も\Caesarの定義とかなり似通っています．

アフィン暗号は鍵が2つであるため\@tempcntaと\@tempcntbの2つのカウンターレジスタだけでは数が足りません．また，カウンターの使い回しを下手に行うと思わぬバグの原因になりかねないので，思い切っていくつかの専門用途カウンターレジスタを新設することにしました．今どきのTeXエンジンにはレジスタがたくさんあるので，このぐらいは消費しても問題ないでしょう．

実質的に\Caesarの定義と大きく異なっているのは「暗号化処理」の内部だけです．大文字・小文字の文字コードを単純な引き算によって0〜25までの値に収めた後，先の定義式通りの計算を"粛々と"実行していきます．

さて，では完成した\Affine命令を実際に使ってみましょう．

【入力】

\Affine{17}{7}{government\ of\ the\ people,\ by\ the\ people,\ for\ the\ people}

【出力】

flaxkudxus lo swx cxlcmx, yz swx cxlcmx, olk swx cxlcmx

ああ，崇高な民主主義の理念が，意味不明な文字列に変換されてしまいました……

アフィン暗号の復号化

シーザー暗号と異なり，アフィン暗号による暗号文を復号化するには，暗号化とは少し違った処理を行う必要があります．

まず， $aa^{-1}\equiv1\pmod{26}$ なる $a^{-1}$ を求める必要があります． $0 \leq a \leq 25,\;\gcd(1,26)=1$ を満たす $a$ について，その逆数を求めると下表のようになります．

$a$	1	3	5	7	9	11	15	17	19	21	23	25
$a^{-1}$	1	9	21	15	3	19	7	23	11	5	17	25

この $a^{-1}$ を用いて

$\displaystyle\quad P \equiv a^{-1}(C-b) \pmod{26}$

を計算してやれば，アフィン暗号を復号化することができます．

これを実行するためのマクロ\DecodeAffineも作ってみました．

\makeatletter

\def\DecodeAffine#1#2#3{%
  \bgroup
    % 鍵の処理
    \key@a=#1\relax
    \key@b=#2\relax
    \ifnum\key@b<0
      \multiply\key@b\m@ne
      \calc@mod{26}{\key@b}%
      \key@b=\@result
      \multiply\key@b\m@ne
      \advance\key@b26
    \else
      \calc@mod{26}{\key@b}%
      \key@b=\@result
    \fi
    % 復号化処理
    \@tfor\member:=#3\do{%
      \@character=\expandafter`\member\relax
      \ifnum\@character>`Z
        % 小文字
        \ifnum\@character<`a
          \member
        \else
          \ifnum\@character>`z
            \member
          \else
            \advance\@character-`a
            \advance\@character\key@b
            \multiply\@character\key@a
            \calc@mod{26}{\@character}%
            \@character=\@result
            \advance\@character`a
            \char\@character
          \fi
        \fi
      \else
        % 大文字
        \ifnum\@character<`A
          \member
        \else
          \ifnum\@character>`Z
            \member
          \else
            \advance\@character-`A
            \advance\@character\key@b
            \multiply\@character\key@a
            \calc@mod{26}{\@character}%
            \@character=\@result
            \advance\@character`A
            \char\@character
          \fi
        \fi
      \fi
    }%
  \egroup
}

\makeatother

\Affineとほとんど同じです．違いは\advance\@character\key@bと\multiply\@character\key@aの順番が逆になっただけです *1 ．

使い方も\Affineとほぼ同様です．

\DecodeAffine{〈復号鍵A〉}{〈復号鍵B〉}{〈暗号文〉}

〈復号鍵A〉と〈復号鍵B〉は，暗号化の際に用いた $a,b$ に対する $a^{-1},-b$ の数値に対応します．

実際に，先ほど暗号化した例文を復号化してみましょう． $a=17,b=7$ を指定していたので，復号鍵は $a^{-1}=23,b=-7$ です．

【入力】

\DecodeAffine{23}{-7}{flaxkudxus\ lo\ swx\ cxlcmx,\ yz\ swx\ cxlcmx,\ olk\ swx\ cxlcmx}

【出力】

government of the people, by the people, for the people

見事，民主主義が復活しました．めでたしめでたし．

アフィン暗号への攻撃

アフィン暗号はシーザー暗号の12倍鍵の種類があるので，ブルートフォースアタックをするのも少し大変になりました *2 ．そこで，もう少し効率よく攻撃を行うことを考えます．

単一換字式の暗号に対して有効な暗号解読の手法に，頻度分析というものがあります．これは，暗号文に登場する文字の相対頻度から，平文の対応する文字を推測するという手法です．

ここでは，実際に下記のアフィン暗号文（平文が英語であることは既知とする）を頻度分析により解読することを試みます．

VR CRWIO YRN LYQ XWJLIJ FLPIJWKHJXJP RC IOJ KBEMHPOHYV LWI!

まず，暗号文に登場するアルファベットの頻度を分析します．普通に数えてもいいのですが，面倒なのでTeXにやってもらいましょう．そのためのマクロ\FrequencyAnalysisを作成してあります．

\makeatletter

\def\FrequencyAnalysis#1{%
  \bgroup
  % 小文字
  \@tempcntb=\z@
  \@whilenum\@tempcntb<26\do{%
    \@tempcnta=`a
    \@result=\z@
    \advance\@tempcnta\@tempcntb
    \@tfor\member:=#1\do{%
      \ifnum\expandafter`\member=\@tempcnta
        \advance\@result\@ne
      \fi
    }%
    \ifnum\@result>0
      \char\@tempcnta:\the\@result\space
    \fi
    \advance\@tempcntb\@ne
  }%
  % 大文字
  \@tempcntb=\z@
  \@whilenum\@tempcntb<26\do{%
    \@tempcnta=`A
    \@result=\z@
    \advance\@tempcnta\@tempcntb
    \@tfor\member:=#1\do{%
      \ifnum\expandafter`\member=\@tempcnta
        \advance\@result\@ne
      \fi
    }%
    \ifnum\@result>0
      \char\@tempcnta:\the\@result\space
    \fi
    \advance\@tempcntb\@ne
  }%
  \egroup
}

\makeatother

使い方は簡単です．頻度分析したいアルファベット列を引数として与えてやれば，それぞれの文字数を数えて結果を出力してくれます（ただし，1度も登場しなかった文字は表示されません）．

【入力】

\FrequencyAnalysis{LaTeX is a word processor and document markup language.}

【出力】

a:6 c:2 d:3 e:4 g:2 i:1 k:1 l:1 m:2 n:3 o:4 p:2 r:4 s:3 t:1 u:3 w:1 L:1 T:1 X:1

ということで，例の暗号文についても頻度分析してみましょう．

【入力】

\FrequencyAnalysis{VR CRWIO YRN LYQ XWJLIJ FLPIJWKHJXJP RC IOJ KBEMHPOHYV LWI!}

【出力】

B:1 C:2 E:1 F:1 H:3 I:5 J:6 K:2 L:4 M:1 N:1 O:3 P:3 Q:1 R:4 V:2 W:4 X:2 Y:3

さて，一般的な英語のテキストには，各アルファベットは下図に示す頻度で登場します．

英文字の出現頻度（出典：Wikipedia）

すると，Eの出現頻度が最も高く，ついでTの出現頻度が高いことがわかります．さきほどの暗号文の頻度分析では，Jが6回登場で最も多く，Iの5回登場がこれについで2番目に多いという結果になっていました．そこでE→J，T→Iと対応していると仮定することにします．

すると，暗号化の式から次の連立方程式を立てることができます．

$\displaystyle\quad \begin{array}{l} 9\equiv4a+b\pmod{26} \\ 8\equiv19a+b\pmod{26} \end{array}$

最初の式を2番目の式から引くと $15a\equiv-1\equiv25\pmod{26}$ が得られるので，26を法とする15の逆数7を両辺に掛けることによって， $a\equiv19\pmod{26}$ がわかります．これを，最初の式に代入すると $b\equiv11\pmod{26}$ が求まります．

すなわち，例の暗号文は $a=19,b=11$ として暗号化されたものと考えられます．では，この仮定のもとで実際に復号化してみましょう．復号鍵は $a^{-1}=11,-b=-11$ です．

【入力】

\DecodeAffine{11}{-11}{VR\ CRWIO\ YRN\ LYQ\ XWJLIJ\ FLPIJWKHJXJP\ RC\ IOJ\ KBEMHPOHYV\ LWI!}

【出力】

GO FORTH NOW AND CREATE MASTERPIECES OF THE PUBLISHING ART!

めでたく，The TeXbook の「最後のアドバイス」が復元されました．

元の暗号文がこれだけ短くても復号化に成功できたことからも，頻度分析が非常に強力な暗号解読法であることが伺えます *3 ．この頻度分析（の改良手法）を利用することにより，ほとんどすべての単一換字式暗号を解読することができます．

結論

任意の単一換字式暗号よりTeX言語の方が解読困難．

2015/5/17 更新

コードの行末処理に問題があったので修正しました．ご指摘いただいた方々ありがとうございます．他にも一部数式の誤りと合理的でないコードがあったので修正しました．ZRさん本当にありがとうございます．

また，違法性のあるコンテンツへのリンクが貼られていたことが発覚したので削除しました．ご迷惑をおかけして申し訳ありません．

*1:「なら，もっとDRYに書けよ」という話なのですが，コピペした方が手間が省けるのでこうなりました．

*2:とはいえ，その気になれば数秒で解読できます．参考：独立行政法人情報処理推進機構

*3:今回は"たまたま"一発の推測で鍵を当てることができてしまいましたが，もう少し試行錯誤を必要とする場合もあるかと思います．

0番染色体

科学は全世界を照らす光である

TeXで暗号化(2) アフィン暗号

アフィン暗号

\Affine命令の実装と使い方

アフィン暗号の復号化

アフィン暗号への攻撃

結論

2015/5/17 更新