暗号解読の手段：頻度分析

2022年9月12日 18:03

用語について

平文（クリアテキスト、cleartext）とは意味が理解できる、または直接利用できるデータである。
プレーンテキスト（plaintext）とは暗号化処理に入力され変換されるデータ、もしくは復号処理後の出力データである。
両者は区別されるべきである。暗号化処理に入力されるデータ（プレーンテキスト）自体が、別の暗号によって変換された（したがって平文ではない）ものである場合があるからである。
初版では筆者もこの二つを混同していたので、訂正を行った。

頻度分析とは

我々が日常的に使っている言語、つまり自然言語で書かれた文章には「特徴」がある。そして古典暗号（大雑把に言えば系統立った暗号理論が登場する以前の暗号）で暗号化された暗号文には、少なからず「特徴」が残る。ここではその一つである、文字の出現頻度分布を分析することについて述べたいと思う。

自然言語には、文字ごとにその出現頻度に偏りがある。つまり、たくさん出てくる文字とほとんど出てこない文字がある。頻度分析とは、簡単に言えばどの文字がどれだけ出てくるかを調べることである。

以下の記事やサイトも参照のこと。

ウィキペディア記事「頻度分析 (暗号)」
基本的なことは大体書かれている。

暗号解析サイトdcode.fr内の頻度分析ツール
アプリのダウンロード等不要で解析ツールを使える便利なWebページ。

通常の英文の場合

実際に適当な英文を用意して、その特徴を観察してみよう。

When, in the course of human events, it becomes necessary for one people to dissolve the political bands which have connected them with another, and to assume, among the powers of the earth, the separate and equal station to which the laws of nature and of nature's God entitle them, a decent respect to the opinions of mankind requires that they should declare the causes which impel them to the separation.

アメリカ独立宣言の一節

この英文は330文字（スペース、カンマ、ピリオドなどを除く）からなり、Eが50回出現する。その全体に占める割合は15.15%である。続いてTが37回(11.21%)、Hが27回(8.18%)、Oが27回(8.18%)、Aが26回(7.88%)、以下N, S, I, R, C, D, ....と続く。そしてB, G, Q, Yが2回、Kが1回出現し、JとXとZは出現しない。グラフにすると次のようになる（図1）。

今は文字1つごとに特徴を調べたが、2文字、3文字のかたまりについて調べてみてもやはり特徴がある。2文字の場合、THが17回、HEが15回出現し、以下AN(7回), AT, EC, ON, RE(以上6回), ...と続く。また、Qの次にはほぼ必ずUが続く、といった連接特徴も注目すべきである。
3文字の場合はTHEが14回も出現し、ANDが4回、ENTやHEMなどが3回出現している。特に英文において最頻出の語である「THE」は、さまざまな暗号の解読において強力な手がかりとなる（それを見越して敢えて「THE」を使わないなど、ある程度の人為的操作は出来るので過信は禁物）。

この特徴が暗号解読にどのように役立つかを考える。

単一換字式暗号の場合

単一換字式暗号とは、プレーンテキストの文字が、必ず同じ暗号文の文字（あるいは記号）に変換される暗号である。例を示す。

VTIFOFQTISJRMPIJNTREWFIUIFQPOQAISJEIPFISIPPWMYNJMJFIKIJKDIQJHOPPJDUIQTIKJDOQOSWDAWFHPVTOSTTWUISJFFISQIHQTIEVOQTWFJQTIMWFHQJWPPREIWEJFGQTIKJVIMPJNQTIIWMQTQTIPIKWMWQIWFHILRWDPQWQOJFQJVTOSTQTIDWVPJNFWQRMIWFHJNFWQRMIPGJHIFQOQDIQTIEWHISIFQMIPKISQQJQTIJKOFOJFPJNEWFCOFHMILROMIPQTWQQTIYPTJRDHHISDWMIQTISWRPIPVTOSTOEKIDQTIEQJQTIPIKWMWQOJF

これは上述のアメリカ独立宣言の一節を、単一換字式暗号で暗号化したものである。どのプレーンテキスト文字をどの暗号文字に対応させるかの方法は、ラテンアルファベット26文字の場合、$${26! \fallingdotseq4.03 \times 10^{26}}$$通り存在する。1つ1つ確かめていくことは事実上不可能である。また困ったことに、この暗号文はスペースやアポストロフィなどを取り去ってしまったため、単語の切れ目が分からない。したがって、1文字の単語を見つけてこの文字がaもしくはiであろう、と推測する手は使えない。
そこで威力を発揮するのが頻度分析である。単一換字式暗号では、あるプレーンテキスト文字は必ず同じ暗号文字に変換されるために、プレーンテキストの特徴が文字以外そっくりそのまま暗号文に残る。グラフにすると次のようになる（図2）。

最も頻出しているIがプレーンテキストのeに当たるであろうことは容易に推測できる。次に多いQはtだろうか。暗号文をよく見ると、「QTI」という3文字組がたくさん現れているが、これは「the」ではなかろうか。……と、このようにして解読を進めていく。このように、単一換字式暗号を解く場合、頻度分析はとても強力な道具となる。

ちなみに暗号化の規則は次の通り（図3）。

図3. プレーンテキスト文字と暗号文字の対応表

プレーンテキスト文字と暗号文字対応表を作成には、キーワード「WASHINGTON」（アメリカ合衆国初代大統領ジョージ・ワシントンに因む）を用いて行った。重複する文字を省いた「WASHINGTO」を書き入れ、続いて残るアルファベットを順に書き入れた。

転置式暗号の場合

転置式暗号とは、一定のアルゴリズムに従ってプレーンテキストの文字を並べ替える暗号である。例を示す。

WEITEOREFUAEETIBCMSEESRFRNPOLTDSOVTEOIIABNSHCHVCNETDHMIHNTEADOSUEMNTEOESFHERHHSPRTADQASAINOHCTEASFAUENONTRSOETTEHMDCNRSETOHOIINOMNIDEURSHTHYHUDELRTEASSHCIPLHMOHSPRTOHNNHCUSOHMNVNSTEOENCSAYOOEEPEOISLEHPLTCLADWIHAEONCETEWTAOHRNTASMAOGHPWROTEATTEEAAENEULTTOTWIHHLWONTRADFAUEGDNILTEAEETEPCTTEPNOSFAKNRQIETATESOLDCAEHCUEWIHMETETTEEAAIN

これは上述のアメリカ独立宣言の一節を、2段のレールフェンス暗号で暗号化したものである。頻度分布のグラフはプレーンテキストと同一である（図4）。

文字を並べ替えているだけだから、1文字に対して注目した時の頻度分布は変わらない（2文字、3文字の組に対する頻度分布は変わる）。もし、文字の頻度分布が通常の文章と同様の暗号文があれば、その暗号文は転置式暗号と推測することができる。なお、いったいどのような転置が施されているかまでは頻度分析からは分からない。

ヴィジュネル暗号の場合

ヴィジュネル暗号は、多表式の換字式暗号である。すなわち、プレーンテキストの文字が、必ずしも同じ暗号文字に変換されるとは限らない。例を示す。

WKEZANWHQUOXREWOIHGEAQEHWNWSULBHCAEEVNQUEVSMJYIODGNHPQGPOEFGDLSEGLYEFZESOXATLCMDBDNPKWKIOZHDVQUOQNQUTHDFZEPWULHDNALHHRMFDWOMKSXMQSMRNSLHHPAOEUSAXTKEQSRWHFZEVEBSRDTQSNGECMAOSFSTLOZLOZHUUHWHQDAZSAXNDTGJEDNPGFQAFMRHSSGDHNFATOEFZEPAPWCHNFJEVPQUTWOFZERPUFIRNEGFPAZCIQDDWQXIDWSWHMLTKEKKHRUXVDHCXSRHTTWCDUEWSZHUUHLMBWLWHQETRTTWSHPMJAWIAF

これは上述のアメリカ独立宣言の一節を、ヴィジュネル暗号で暗号化したものである。鍵は「ADAMS」（アメリカ合衆国第2代大統領ジョン・アダムズに因む）である。頻度分布のグラフは次のようになる（図5）。

これ自体は直接解読の役には立たないが、「ヴィジュネル暗号の頻度分布ってだいたいこんな感じなんだな」と思っていただければよい。暗号化方式の分からない暗号文があった場合、頻度分布はその方式を推測する貴重な情報となるかもしれない。
ではどうやって解読すればいいのかというと、ヴィジュネル暗号の弱点は周期性である。鍵の長さ（上の例「ADAMS」では5）ごとに、同じ暗号アルファベットを使って暗号化が行われているからである。その鍵の長さを推測するのが解読の第一歩であり、それには「カシスキー・テスト」といった手法が使われる。これについてはいずれ述べる。

プレイフェア暗号の場合

プレイフェア暗号は、1文字ごとにではなく2文字組ごとに暗号化を施すタイプの暗号である。その具体例を示す。

VA DC LA QC ME FZ ST FC KO TP NC KY DC UT MR DF OH TM XD ME DT RN TW PF UA CD MF FU MD UC BL XN UN GX MY CK UF ML RM ON ID NC LX VA MA NV AN YK OH DN CD EY FE QC MT AR QC NC CU CK WB DL UC NR TQ TM CI HC MQ CK UF YB ST FP QC DY BC SU CQ CK TD IO WB YM NC EF RQ NI TU CR PA CS AZ AG OA QC DM BA UN DO CR QS BC DL FP CN UQ TB QL NF DC RM SM MY CK IC EF EM CS TB UL ME SY UC QC FC GL AL HC UN EP NC BG DL TB RQ RW DT QC CR QC MC QN FZ SL EF NM BW MY CK ON QT DT VA MA AG PG DM QC MT UC QC DT FM BW CR PA DN

これは上述のアメリカ独立宣言の一節をキーワード「HANCOCK」（アメリカ独立宣言に最初に署名したジョン・ハンコックに因む）を用いて、プレイフェア暗号で暗号化したものである。頻度分析を試みる（図6）。

これ自体は直接解読の役には立たないが、「プレイフェア暗号の頻度分布ってだいたいこんな感じなんだな」と思っていただければよい。
ちなみに2文字の組ごとに出現頻度を分析してみる。QCが最も多く10回出現するが、これはプレーンテキストのthに当たる。次いで多いのはCK(プレーンテキストのhe)の6回、NC(an)の5回、DT(es)、CR(at)、UC(to)の以上4回である。このような特徴だけからプレイフェア暗号の解読をするのは実際やや困難であるが、手掛かりにはなる。

エニグマの場合

エニグマは周期のローター式暗号機、およびその暗号機により作成される暗号文の呼称である。その具体例を示す。

BPTPSPCWGVDCHZCLXXMZTDXMTQBFQLGBSEILRJDLBBTKSUZTEKFXYRJEOWJWJVTATKWFMOCVMSXECSZYICWAPPUKNWFYLRMKSDDDSFEXBNTIMQGEPWXDJBGZRHJBHQKYLZPMVRJZFUGFUNOZUBSTILNEEJPVLCCFLBQJDTYFMLPCFXOBLTQKJTKJSZRXNYMDVTUQKXFKAWJILUDSJKOSVYNFFQLEXCOOSTITITBNHALCQYVVNEIEXFSITBBCWVVJZWGRPWSBNANLWHDXCKQPAJBQOYHFPCJPIZBJBAMMJVCPYMNGZWUIHVIJBZERSHBYOMKJEGMEQT

これは上述のアメリカ独立宣言の一節をエニグマで暗号化したものである（詳しい条件は略）。頻度分析を試みる（図7）。

これ自体は直接解読の役には立たないが、「エニグマの頻度分布ってだいたいこんな感じなんだな」と思っていただければよい。頻度分布はまったく均等というわけではないが、通常の英文に比べると大分出現の偏りがなくなっていることが見て取れる。

頻度分析の歴史

9世紀のアラブの哲学者アル＝キンディーによる記述が、頻度分析による暗号解読法について言及した最古のものである。15世紀ルネサンス期のヨーロッパでも同様の暗号解読法が生まれた（ヨーロッパで独自に発見されたか、アラビアから持ち込まれたか、いずれの可能性もある）。これにより、カエサルの時代から千年以上にわたって用いられてきた単一換字式暗号は、もはや安全ではなくなった。暗号作成者たちの手により暗号は改良され、暗号解読者たちもまた分析法を洗練させていった。
この頃近代文学の世界では、エドガー・アラン・ポーの『黄金虫』やコナン・ドイルの『踊る人形』にて、頻度分析が言及されている。
20世紀初頭、機械式暗号が誕生すると、単純な頻度分析はもはや困難となった。しかし暗号文から一切の特徴が消え去ったわけではない。暗号解読者はその統計的性質を分析し、解読に成功した。
現代暗号は自然言語の持つ特徴を手がかりにできないように制作され、頻度分析を克服している。

まとめ

・頻度分析は暗号解読の強力な道具である
・暗号解読の直接の手掛かりにはならなくても、どのような暗号かを推測する手がかりになる

「○○暗号の頻度分布ってだいたいこんな感じなんだな」の「だいたいこんな感じ」を、もっと具体的に、数値で表すことはできないだろうか。その手法の一つが、次で紹介する"index of coincidence (IC)"である。

参考文献

『暗号解読』　サイモン・シン著、青木薫訳
ウィキペディア「頻度分析 (暗号)」

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