見出し画像

暗号紹介:Four-square暗号(2) 解読実例

表記・用語について

プレーンテキスト(暗号化前のメッセージ)の文字は小文字で、暗号文の文字は大文字で表すことにする。

Four-square暗号とは

前回を参照。

プレーンテキストを推測する

ここでは、暗号文が与えられた状態で、プレーンテキストを推測しながら暗号表を構築し解読する方法を示す。
アメリカ陸軍作成のマニュアルに掲載されている例題を用いて、その解読作業を追っていく。マニュアルの7-0ページから7-11ページまでがFour-square暗号の分析を扱っている。

Four-square暗号に限らず、2文字ごとに暗号化を施す方式の暗号の解読は、いかに正しくプレーンテキストを推定できるかにかかっている。定型に沿った文章は、その定型を見出すことで解読しやすくなる。何らかのパターンがある文字列を見出すことも、解読の助けとなる。そのような特徴的パターンのある文字列の例を示す。

de co deAB -- AB
po
st po ne→AB -- AB --
ma in ta in in g-→-- AB -- AB AB --
-m ai nt ai n-→-- AB -- AB --

このようなプレーンテキストと暗号文の組み合わせはあらかじめリストアップしておくと便利である(参考とする文献にも付録としてそのリストがついている)。

解読実例・通常版

まずは通常のFour-square暗号を扱う。「通常の」というのは、プレーンテキストの格子がアルファベット順にAからZまで並んでいるということである。通常版はミックス版(プレーンテキストの格子も並べ替えられているバージョン)よりも若干解読が簡単である。

a. この場合、プレーンテキストの文字の位置は既に決まっている。したがってある種の単語を暗号化すると、特定の文字が繰り返し出現する場合がある。たとえばmi li ta ryという単語を暗号化する。表は図1に示したものを用いる。

図1. Four-square暗号表

得られる暗号文はKL KO NS SWである。1つ目の2文字組KLの始めの文字も、2つ目の2文字組KOの始めの文字も同じKである。これは、プレーンテキストのmiとliの始めの文字mとlが、左上の格子の同じ行にあること、およびそれれぞれの終わりの文字がいずれもiであることによる。

re qu es te d-→UR UM AU UT --は「A- A- -- A-」型の配置パターンを持つ。
el em en ts→PK LK AK RQは「-B -B -B」型の配置パターンを持つ。
qu ar te rm as te r-→UM LM US QF AM USは「AB -B AD -- -B AD」の配置パターンを持つ。

そのようなプレーンテキストと暗号文の組み合わせもあらかじめリストアップしておくと便利である。

b. Four-square暗号を他の2文字組を暗号化する方式の暗号(プレイフェア暗号やTwo-square暗号)と区別する方法はだいたいは消去法である。
Four-square暗号の暗号表が通常版かミックス版かを判別する明確な根拠はないが、まずは通常版と仮定したうえで解読を試みるのが分かりやすい。難しい方を仮定して取り組むのは、簡単な仮定がうまくいかなかった後でもよい。

c. 暗号解読を実践してみる。今、次の暗号文が得られたとする。

TA TO UT OD HI DM FI PK RO FM HR VH BM AH NH KM UN AN ZM RO SK HH RQ  BX FS YF KQ NS QF AT KQ UY SM QP SM NT MY RO RY DM FI PK RO FM IQ LT TY SQ RY RV FE DC AT GR TH TO AO TD QP

d. 暗号文中にDM FI PK RO FMの繰り返しが現れている。これは「-B A- -- -- AB」型のパターンを持つ。リストから当てはまるものを探してみると、in fo rm at io n-が当てはまりそうである。以上よりin=DM, fo=FI, rm=PK, at=RO, io=FMとついでにn-=HR, n-=IQが得られる。 これを暗号表に書き入れると図2のようになる。

図2. 暗号表(パラグラフd時点)

e. 暗号表外に書き込まれているHとIは、それらが左上の格子のnと同じ行のどこかにあることを示し、同じくRとQは、それらが左上の格子のnと同じ列のどこかにあることを表している。
アルファベット順を考慮すれば、さらに文字を描き加えることもできる。左下の格子を見てみると、I, K, ?, M, ?, Oという文字の並びが見て取れる。暗号文字の格子がなんらかのキーワードにより作られているとしたら(したがってキーワード部分以降はおおむねアルファベット順になっているものだとしたら)、この空いた場所にはLとNが入るのではないか、と推測するのも悪くないだろう。
右上の格子を見てみると、2行目にD, F, ?という並びが出来ており、また3行目にHとIが入ることが分かっている。もしかしたら、D, F, G, H, Iという並びができるかもしれない。
このように、明らかになった文字を用いて暗号文を部分的に解読してみる。暗号表を図3に、一部解読した暗号文を図4に示す。

図3. 暗号表(パラグラフe時点)
右上の格子にHとIを、左下の格子にLとNを追加
図4. 図3の暗号表を用いて解読を進めた暗号文

f. 次に、右上の格子のPの位置に注目する。Pの後には8つの文字が入る。一方、アルファベット順でPの後に存在するのはQ, R, S, T, U, V, W, X, Y, Zの10文字である。既にRがキーワードに用いられているから、Rを除く残る9文字のうち、1文字がキーワードに含まれていることになる。
仮にQがキーワードに含まれるとすると、必然的にUもその次に続くことになる。するとPの後に続くアルファベットは7文字となり、8つのスペースを埋めることはできなくなってしまう。このことから、Qはキーワードに含まれず、Pの次の位置に入ると考えてよいだろう。

g. ここまでの推定に不都合は生じていないので、自信を持っていいだろう。無論、そうではない可能性も膨大な数存在するが、それがあくまで可能性に過ぎないのならば、まずは紙と鉛筆があればできる範囲で取り組むべきである。
左下の暗号格子を見てみよう。今はRとQが暗号格子の外で浮いているが、O, P, Q, …の文字列の並びを仮定すればQは4行目に入るだろう。一方Rはキーワードに含まれると思われるから、1行目に入るだろう。
また、暗号文を見てみると?? ll=OD HIとなっている部分があるが、これはallの一部であろうと思われる。したがって?a=ODと推定できる。
現時点での暗号表と暗号解読の進展をそれぞれ図5、図6に示す。

図5. 暗号表(パラグラフg時点)
図6. 図5の暗号表を用いて解読を進めた暗号文

h. プレーンテキストのrs(2つあるうちの1つ目)について考える。rsの直前には母音が来るはずである。したがって暗号文字のSMは、終わりの文字が母音になるはずである。左下の格子にMが既に入っていることから、その母音というのはoであると分かる。したがってSは右上の格子の4列目に入るはずである。相応しい場所は、4列目のQの右しかない。そうすればP,Q,(キーワードのRを飛ばして)Sという並びができる。
現時点での暗号表と暗号解読の進展をそれぞれ図7、図8に示す。

図7. 暗号表(パラグラフh時点)
図8. 図7の暗号表を用いて解読を進めた暗号文

i. ここで、いくつかの可能性が浮かび上がってきた。rs to ??はstopを表しているのではないか。ならばp?=NTだろう。2つ目のinformationのあとのr????stとはrequestを表しているのではないか。ならばeq=LT、es=TYだろう。
これらの文字を、格子にうまくアルファベット順になるように書き入れると図9に示す暗号表を得られ、これを用いて解読すると図10のようになる。

図9. 暗号表(パラグラフi時点)
図10. 図9の暗号表を用いて解読を進めた暗号文

j. 最初の単語はrequestであり、最後の単語はheadquatersだろう。これらを書き入れれば、キーワードも判別し、完全な暗号表とプレーンテキストが得られる。これを暗号表を図11に示す。

図11. 完成した暗号表

整形し、元のメッセージを得ると次のようになる。
Request all information available on enemy patrol activity in southern sector. Updated information requested by higher headquarters.」(南セクターにおける敵の哨戒活動について、出来る限りの情報を求む。上位司令部より更新された情報を要求されている。)

解読実例・ミックス版

プレーンテキストの格子もミックスされ、AからZのアルファベット順に並んでいない場合。通常版のパラグラフaで言及した方法は使えない。

ここで解読する暗号文を示す。次のことが分かっている。
・Four-square暗号文である。
・同じ司令部の以前のメッセージはADAMSもしくはMILLERの署名が入っていた。
・この宛名からのメッセージには番号が振られており、最近のメッセージは4500番台半ばあたりである。

FM FE FM PX ZP YX IY YP GG ME TX GS YG GB YL FI HA GB YL MK MR GH YR FM BY YP MM BQ YM HD MH LN MN OS  YP VI DM XH RP GL MN SO QL MP GB YL VG QI QL YX KT ZG HE EM GB KM FL YK PH MA SR EE GD MK DE BG TT EB IX CN VI NI SO SC HH IG TH HM OQ PO TG KI VG QI PM XR CP GH YR SE PL MN LN MN AC VC OC OO KP WC PK IP PC SU GH YR FK SC YG XX

a. 暗号文中に見える繰り返しの特徴を観察する。
(1) 最初からFM FE FMには「AB -- AB」型のパターンが見える。これは一般的な定型文refferenceの一部であろう。
(2) GB YLが繰り返し現れているが、これは数字だろう。そして、FM FE FM … YL FI HA(最初からはじめのGB YLの直前まで)の文字数は、ちょうど定型文「refference your message number」に一致する。ここで、最近のメッセージの番号が4500番台半ばあたりであるということを思い出すと、続きの文章は数字の羅列からはじまり、おそらくその最初の3つは「four five four」ではないか、と推測できる。
(3) GH YRはそこそこの間をおいて現れている。おそらく一文の区切りを表すstopだろう。
(4) これらの可能性を暗号表に書き入れてみる。
この時点での暗号解読の進展を図12に示す。

図12. パラグラフa時点の暗号解読の進展

b. もし暗号表のプレーンテキストの格子が通常通りAからZのアルファベット順であるとすると、矛盾が生じる。最初の2組の2文字組re=FM、fe=FEを書き入れてみると、右上の格子の異なる2ヶ所にFの文字が入ってしまう。これを図13に示す。

図13. 通常版のFour-square暗号と仮定した場合の暗号表
re=FM、fe=FEを書き込んだところ、右上の格子の異なる2ヶ所にFが書き込まれるという矛盾が生じている。

したがってこれはミックス版のFour-square暗号である。そこで、紙に縦横の線を引き、4つの領域に分ける。それぞれの領域は暗号表のそれぞれの格子を表現している。それぞれの領域は、はじめは5×5マスに限定されない。最終的に5×5に収まるようにするのである。
プレーンテキストと暗号文の2文字組のペアを1つずつ暗号表に書き入れていく。そのとき、長方形の関係が保たれるように注意する。もし今から書き入れようとしているペアに含まれる文字が先に書き入れた文字の中にない場合は、新たに行もしくは列を作ってそこに書き入れる。その過程を図14に示す。

図14. 暗号表の構築過程(6番目のペアou=YXまで)
太字はそのステップで新たに追加された文字

7番目のペアrm=IYまで書き入れた暗号表を図15に示す。

図15. 暗号表(パラグラフb時点)

c. こうして文字を書き入れていき、8番目のペアes=YPを加えようとしたときに新しい状況が生じる。現在、左上の格子のeと右上の格子のYが異なる行にあるが、新しいペアを加えるにはこれらの行を統合しなければならない。この過程を図16に示す。

図16. 暗号表の構築過程
8番目のペアes=YPを加え、2つの行を統合してYを重ねる

d. 既知のプレーンテキスト・暗号文ペアを全て書き入れた暗号表は図17のようになる。

図17. パラグラフd時点の暗号表
(参考文書ではve=HAを含んでいないが、誤りか)

この時点での暗号解読の進展を図18に示す。

図18. パラグラフd時点での暗号解読の進展

e. 図18を見ていると、four five four ???? stopという部分がある。空いている部分(暗号文はMK MR)に入るのは数字であろう。ここに入り得る4文字の数字はzeroとnineである。しかしzeroではありえない。図17の暗号表を見ると、ro=G-であり、MRとはどうしても一致しないからである。したがってni ne=MK MRであろう。
2文目の始まり(1つ目のstopの直後)のre ?? es -eはおそらくrequestだろう。したがってqu=BY、te=MMを得られる。
また、最後のstop後から始まる?? ?? erだが、以前のメッセージの送信者の署名はADAMSかMILLERであったことを思い出せば、おそらくmillerであり、したがってmi ll er = FK SC YGであろう。

新たに得られたペアを暗号表に書き入れると図19のようになる。

図19. パラグラフe時点の暗号表

f. それぞれの領域に、アルファベット順の並びの痕跡がうっすらと見える。右上の領域にはFGI, MPT, YZの横並び。左下の領域にはIK, XYの横並び。左上の領域にはmno, qrtの縦並び。右下の領域にはprsuの縦並びが見える。このことから、左上と右下のプレーンテキストの格子はアルファベットが縦並びに、右上と左下の暗号文の格子はアルファベットが横並びになっていると推定できる。
これを念頭に置いて行や列を入れ替えてみよう。右上の領域のFGI, MPT, XZはそれぞれ最後から3番目、2番目、1番目の行に入ると考えられる。入れ替えを行った暗号表を図20に示す。

図20. パラグラフf時点での暗号表
色付き部分は入れ替えを行った行

g. そろそろ、広く散らばった文字たちを5×5の格子に押し込んでやることを視野に入れながら暗号表を整理しよう。
図20のように入れ替えを行った結果、左上の領域に注目するとmnoとfgがアルファベット順に並んでいる。この入れ替えは妥当なものとみてよいだろう。
列の入れ替えも行ってみる。右上の領域のYとZはそれぞれ最後から2番目、1番目の列に入ると思われる。TがYの直上に存在することから、TとY,Zの間にU, V, W, Xが入る。したがってTの右にUが入り、最後の行にはV, W, X, Y, Zが入るだろう。
Uがキーワードに入っていないことから、Qも同じくキーワードに含まれない。今4行目に入っている文字はM, P, T, Uであり、1つ空きがある。そこにQが入る。
左上の領域を見ると、fg, mno, qrtはそれぞれ2列目、3列目、4列目に入るだろう。これらの列を入れ替え、qとrが離れているので行の入れ替えもついでに行う。
また、左上と右上の領域に5×5の格子を作った。
その結果を図21に示す。

図21. パラグラフb時点での暗号表
太字は新たに追加した文字

h. 並べ替えれた格子を観察してみよう。左上の領域をみると、第4列目の一番下のマスと第5列目の5つのマスの合わせて6つのマスが空いているが、そこにu, v, w, x, y, zがぴったり当てはまる。このとき、5×5の格子外で浮いているuを含む列をqrtの列(第4列)に統合でき、また同じく浮いているvも同様に移動できる。
右上の領域を見ると、Gを含む列はFの右隣りの列に統合できそうである。
右下の領域を見ると、4列目にpusrの並びがあるが、qを補いつつ並び変えるとpqrsuというように、別のところにあるtを飛ばしつつもアルファベット順の並びができる。
これを図22に示す。

図22. パラグラフh時点の暗号表
太字は新たに追加した文字

i. 5×5の格子からはみ出している文字を、格子の中に詰め込んでいく作業を行う。たとえば左上の領域のsを含む列は、第1列目と統合できる。また、アルファベット順を考慮して文字を詰め込める場所があれば詰め込む。こうしてできた暗号表が図23になる。

図23. パラグラフi時点の暗号表
太字は新たに追加した文字

j. あらかた暗号表を埋めたので、暗号文の解読にも重点を置きつつ暗号表の完成と解読の完了を目指すと、図24に示す暗号表ができる。

図24. 完成した暗号表

プレーンテキストは次のようになる。
「referenceyourmessagenumberfourfivefourninestoprequestedsupplieswillbeshippedbyrailwithinfoureighthoursexceptforpriorityelectronicpartscommawhichwillbeshippedbyairfreighttodaystopdetailswillfollowassoonasknownstopmillerom」
整形すると次の文章を得るようになる。最後のom=XXは単語ではなく、通信終了を意味する符号だろうか。
Reference your message number four five four nine.  Requested supplies will be shipped by rail within four eight hours except for priority electronic parts, which will be shipped by air freight today. Details will follow as soon as known. Miller」(メッセージ番号4549を参照せよ。要求された物資は最重要の電子部品以外は鉄道にて48時間以内に輸送され、電子部品は航空により本日輸送される。詳細は分かり次第追って伝える。ミラー)

暗号表のキーワードは左上がBASIE、右上がHENDERSON、左下がHERMAN、右下がELLINGTONと思われる。これらはいずれもアメリカの高名なジャズミュージシャンの名前である(カウント・ベイシー、フレッチャー・ヘンダーソン、ウディ・ハーマン、デューク・エリントン)。またADAMSとMILLERもアメリカのジャズミュージシャンにちなむと思われる(ジョージ・アダムズ、グレン・ミラー)。

まとめ

・Four-square暗号の解読は、いかにプレーンテキストを正しく推測できるかにかかっている。定型文や繰り返し現れる文字列を利用するとよい。
・アルファベット順になりそうな並びを見つけたら、積極的に利用するとよい。そうではない可能性も膨大な数あるが、簡単な仮定で済むならばそれに越したことはない。

参考文献

ウィキペディア(英語版)「Four-square cipher」
"U.S. Army FM-34-40-2, Basic Crypt-analysis", by Headquarters Department of The Army, Washington D.C.


この記事が気に入ったらサポートをしてみませんか?