暗号紹介：プレイフェア暗号(2) 解読実例
表記・用語について
プレーンテキスト（暗号化前のメッセージ）の文字は小文字で、暗号文の文字は大文字で表すことにする。
プレイフェア暗号とは
前回の記事を参照。
解読実例
ここでは、暗号文が与えられた状態で、プレーンテキストを推測しながら暗号表を構築し解読する方法を示す。
アメリカ陸軍作成のマニュアルに掲載されている例題を用いて、その解読作業を追っていく。マニュアルの7-12ページから7-18ページまでがプレイフェア暗号の分析を扱っている。
この暗号文は、とある旅団(brigade)の司令部からその旗下の3つの大隊(battalion)に送られたメッセージである。
DT BV VF GO OG MV CQ IH NS MN VI FC IK FK NX KH UB GK AV LH CA CF WC YC IA VM PB CI FK CA GV UH NC BX OV LY NU CQ ED GO OG MV CQ VW OV UB QH CM CM QM UO BX OV YG DH HB KR CY OG MV CQ IH NS NS QR EX IU GO OG OE GO XK AV DT CB XK AV XK AV YV TQ RH OC NS NB GS LG FN RH GO CV MX VM SL FU CM GO XK AV KT GH KT GH DT CB YV TQ
まずは、繰り返し頻出する2文字の組や、反転関係にある2文字の組などに着目し、いくつかの解読の手がかりを得る。
(1) XK AV DT CB XK AV XK AVという形で、XK AVが繰り返し出現している。これは何らかの数字（特に時刻）を表しているのではないかと推測する。よって、XK AV=ze roと仮定する。
(2) 時刻の後や文末にはYV TQが現れる。これはおそらくstopを表しているだろう。よってYV TQ=st opと仮定する。
(3) 文最後のXK AV KT GH KT GH DT CB YV TQ=ze ro ?? ?? ?? ?? ?? st opは別の時刻を表しているだろうか。
(4) 暗号文中にはGO OG MV CQという文字列が2回繰り返し現れる。はじめの2組の2文字GOとOGは反転関係にある。この特徴的な暗号文が、どのような単語やフレーズに解読されうるかは、あらかじめリストアップされている。候補はたくさんあるが、これが大隊(battalion)に送られたという文脈から考えて-- GO OG MV CQ=-b at ta li onだろうか。
(5) もし(4)の仮定が正しければ、KY CR OG MV CQ=?? ?? ta li onである。これもまたbattalionを表しているのだろう。しかし、ba tt al io nという形で区切ろうとすると、同じ2文字の繰り返しttが生じてしまうので、無意味な文字（例えばx）を挿入したのだろう。したがってKY CR OG MV CQ=ba tx ta li onと考えられる。
(6) GO OG OE GOは、これまでの仮定からat ta ?? atと解読されることが分かった。おそらくこれはattack atであろう。したがってGO OG OE GO=at ta ck atであろう。
軍人ではない自分には「なんでそうなるの？」と言いたくなるような難しい分析だが、こうしていくつかの手がかりを得た。現在の暗号解読の進展を示す（図1）。
次は暗号表の復元を試みよう。最初にどの手がかりから復元を始めるかというのが重要なところである。不注意に手がかりを加えていけば、あり得る暗号表の可能性は際限なく膨らみ、非常に面倒な作業になる。そこで、はじめにどのようなプレーンテキストと暗号文のペアを選べばいいかを紹介する。
(1) 可能であれば、プレーンテキストと暗号文のペアのうち、同じアルファベットを共有しているものを最初に選ぶとよい。今回の問題には存在しないが、仮にab=BCのようなペアがあった場合、「A, B, Cが長方形をなす」パターンはあり得ないため、「上からA, B, Cの順に同じ列に並ぶ」か「左からA, B, Cの順に同じ行に並ぶ」の2通りだけに絞られるからである（図2）。
(2) 次によい選び方は、2つの文字が共通しているペア2組を探すことである。今回の問題では、ro=AVとat=GOの2組が当てはまる。2組にはAとOの2つが共通するからである。他の組み合わせを選んでもよい。
(3) ro=AVに対して、「R, O, A, Vが長方形をなす」「R, O, A, Vが同じ行にある」「R, O, A, Vが同じ列にある」の3通りが考えられる（図3）。
(4) 注意するべきことは、アルファベットの位置は仮に決めたものに過ぎないということである。「R, O, A, Vが長方形をなす」場合であったとしても、RとAのいずれが左にあるか、またRとVのいずれが上にあるかまでは分からない。同様に、「R, O, A, Vが同じ行にある」場合であったとしても、RAとOVのいずれが左にあるかは分からない。
(5) 次は、2つ目のペアを暗号表に加えることを考える。1つ目のペアについて、可能な配置は3パターンある。2つ目のペアについても、同様に3パターンの配置が考えられる。もし1つ目と2つ目のペアの間に共通する文字がない場合、出来上がる暗号表は3×3=9パターンの配置を考えなければならない。これは面倒くさいので、2つ目のペアは1つ目のペアと少なくとも1つの（できれば2つの）文字が共通するものを選ぶとよい。
(6) 2つ目のペアはat=GOである。「R, O, A, Vが長方形をなす」場合と「A, T, G, Oが長方形をなす」場合の組み合わせは次のようになる（図3）。
(7) 「R, O, A, Vが長方形をなす」場合、AとOが異なる行にあることが確定してしまっている。したがって「A, T, G, Oが同じ行にある」場合とは両立し得ない（図4）。このようにあり得ないパターンを排除していって、暗号表のパターン数を絞っていく。
(8) 「R, O, A, Vが長方形をなす」場合と「A, T, G, Oが同じ列にある」場合を両立させると、次のようになる（図5）。
(9) 次に「R, O, A, Vが同じ行にある」場合を考えるが、これとat=GOは両立しない。「A, T, G, Oが長方形をなす」場合と「A, T, G, Oが同じ列にある」、AとOが異なる行にあることになり、矛盾する。「A, T, G, Oが同じ行にある」場合、一つの行に異なる6つの文字が入ることになる（図6）。したがって、「R, O, A, Vが同じ行にある」場合を可能性から排除してもよい。
(10) 最後に「R, O, A, Vが同じ列にある」場合を考える。これとat=GOが両立するのは、「A, T, G, Oが長方形をなす」場合のみである。「A, T, G, Oが同じ行にある」場合は、矛盾する。「A, T, G, Oが同じ列にある」場合は、1つの列に異なる6つの文字が入ることになり、あり得ない。
以上より、ro=AVとat=GOを両立する暗号表のパターンは次の3つである（図7）。
(11) 次のペアを暗号表に加える。既に表にある文字と少なくとも2つ以上共通するペアを選ぶとよい。ここではba=KRを加えることにする。上と同様のアプローチにより、次の4つのパターンを得る（図8）。
(12) さらに、st=YVとop=TQを追加する（図9）。
(13) さらに暗号表に文字を付け加えていくのもいいが、ここで一端、今出来上がった暗号表からさらにプレーンテキストを復元することを考えてみよう。暗号文中にはKT GHが繰り返し現れる。これはおそらく数字を表している。今得られている暗号表からKTの解読を試みると、-O（図9の左上・右上・右下）もしくはG-（図9の左下）が得られる。1文字目がGから始まる数字はないので、これは排除してよい。2文字目がOになる数字は、fourのみが当てはまる。したがって、fo=KT, ur=GHを得る。さらにur=GHを加えると、また1つパターンが減って次の2パターンが残る（図10）。
(14) ところが、図10の右側のパターンはよく見ると不可能である。なぜなら、隣り合っているSYを入れる余地がどこにもないからである。これを排除し、とうとう暗号表は1パターンのみとなった。さらにon=CQ, tx=CY, ze=XKを追加する（図11）。
(15) X, Y ,Zが同じ行にある。これをアルファベット順に並べてみる（図15）。
(16) 暗号表を大分復元できたので、ここで解読を進めてみる（図13）。
(17) DT CB=?? veは明らかにfi veを表している。よってfi=DTを得る。また、RH OC NS NB GS=ar t- -x -e ryは、ar ti lx le ryすなわちartillery（砲兵）であろうから、ti=OC, lx=NS, le=NBを得る。数字を含んでいるPB CI FK CA GV UH NC BX=-f ?? ef ou rt hr ?? esは、-f iv ef ou rt hr ex esであろうから、iv=CI, ex=NCを得る。これらの情報を暗号表に加える。
(18) 残るMとWはアルファベット順を考慮して簡単に配置できる。さらに行を並べ替えて、キーワード以降がアルファベット順に並ぶようにする。キーワードはVICTOR HUGOである。完成した暗号表を示す（図15）。
プレーンテキストは「fi rs tb at ta li on wi lx lm ov et od ef en da re af ro mr ou te xi xt oh il lf iv ef ou rt hr ex es to ps ec on db at ta li on is to re ma in in pl ac es to pt hi rd ba tx ta li on wi lx lx la un ch at ta ck at ze ro fi ve ze ro ze ro st op ar ti lx le ry pr ep ar at io nw il lb eg in at ze ro fo ur fo ur fi ve st op」である。これを整形する。単語を適切に区切り、余分なxを省き、stopをピリオドとして処理するなどすると、次の文を得る。
「First battalion will move to defend area from route XIX to hill five four three. Second battalion is to remain in place. Third battalion will launch attack at zero five zero zero. Artillery preparation will begin at zero four four five.」
（第1大隊はルート19から丘543までの領域を防衛するために移動する。第2大隊はその場に留まること。第3大隊は05:00に攻撃を仕掛ける。砲兵隊の準備は04:45に始めること。）
(19) このようなプレイフェア暗号の解読においては、あらゆる可能性を検討することと、問題を可能な限りシンプルにすることが大切である。適切なペアを探すことで、暗号表のパターンが手に負えないくらい増える可能性は低くなるだろう。もしアルファベット順になりそうなところがあったら、それを利用してもよい。
まとめ
・パターン数を少なくするように、注意深くプレーンテキスト文字と暗号文字のペアを選びつつ暗号表を構築しよう。
・暗号表の構築とプレーンテキストの推測はプレイフェア暗号解読の両輪をなす。片方がある程度進展したら、もう片方に考えを切り替えてみよう。
・もし暗号表にアルファベット順になりそうなところがあったら、それを利用してもよい。
参考文献
ウィキペディア（英語版）「Playfair cipher」
"U.S. Army FM-34-40-2, Basic Crypt-analysis", by Headquarters Department of The Army, Washington D.C.