周波数分析

暗号解読において、頻度分析（文字数えとも呼ばれる）は、暗号文内の文字または文字グループの頻度を研究するものである。この方法は、古典的な暗号を解読するための補助として使用される。

頻度分析は、ある特定の書き言葉において、特定の文字や文字の組み合わせがさまざまな頻度で出現するという事実に基づいています。さらに、その言語のほぼすべてのサンプルで、文字の特徴的な分布がほぼ同じです。たとえば、英語のセクションを考えると、え、T、あそしてお最も一般的ですが、ず、質問、バツそしてJ稀である。同様に、TH、緊急、の上、 そしてAN最も一般的な文字のペア（バイグラムまたはダイグラフと呼ばれる）であり、SS、EE、TT、 そしてFF最も一般的な繰り返しです。^[1]ナンセンスフレーズ「ETAOIN SHRDLU」は、典型的な英語のテキストで最も頻繁に使用される12文字を表しています。

一部の暗号では、自然言語の平文のこのような特性が暗号文に保存されており、これらのパターンは暗号文のみの攻撃で悪用される可能性があります。

単純な置換暗号では、平文の各文字が別の文字に置き換えられ、平文の特定の文字は常に暗号文で同じ文字に変換されます。たとえば、文字e手紙に変えるバツ、多数の文字を含む暗号文メッセージバツ暗号解読者に示唆するバツを表すe。

頻度分析の基本的な使用法は、まず暗号文の文字の頻度を数え、次に推測した平文の文字をそれらに関連付けることです。詳細バツ暗号文中のsは、他の何よりもバツ対応するe平文ではそうであるが、これは確実ではない。tそして1つの英語でも非常によく使われるのでバツどちらかである可能性があります。平文である可能性は低いですずまたはq、あまり一般的ではありません。したがって、暗号解読者は、暗号文と平文の文字間のマッピングの組み合わせをいくつか試す必要がある場合があります。

より複雑な統計の使用も考えられます。例えば、文字のペア（バイグラム）、トリプレット（トリグラム）などの数を考慮することです。これは、暗号解読者により多くの情報を提供するために行われます。たとえば、質問そしてあなた英語ではほとんどの場合、この順序で一緒に出現するが、質問それ自体は珍しいです。

イブが以下の暗号文を傍受し、それが単純な置換暗号を使用して暗号化されていることがわかっている とします。

LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM
WQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ 翻訳:
GSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXV
IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE
PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP
XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX

この例では、大文字は暗号文を表し、小文字は平文（またはそれに類する文）を表し、バツ〜t暗号文の文字を推測するために使用されるバツ平文の文字を表すt。

イブは頻度分析を使って、次のようなメッセージを解読することができた。暗号文の文字数を数えると、私最も一般的な一文字である^[2] XL最も一般的なバイグラム、そして41条最も一般的なトリグラムです。e英語で最も一般的な文字です。番目最も一般的なバイグラムであり、の最も一般的なトリグラムです。これは、バツ〜t、ら〜hそして 私〜e暗号文で2番目によく使われる文字はえ英語で最初に、そして2番目に頻繁に使われる文字なので、eそしてtが説明されているので、イブは推測するえ〜1つの、3番目によく使われる文字です。これらの仮定を暫定的に行うと、次の部分的な復号化されたメッセージが得られます。

ヘベTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReM
翻訳:
GSTVレアヤヴェアCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtV
えZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMtha
PPtheACCeaVawgeSJKTVWMRHehysphtheQeMYhtSJtheMWReGtQaROEVFVeZaVAakPeaWHtaAMWYaPP
thMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVeRCeGtMWYMt

これらの最初の推測を使用して、イブは自分の選択を裏付けるパターンを見つけることができます。たとえば、「それ「さらに、他のパターンはさらなる推測を示唆しています。」レート「かもしれない」州「つまりR〜s同様に「翻訳者「は次のように推測できます」その時"、降伏ま〜私そしてず〜メートル。 さらに、 "彼「かもしれない」ここ「、与える五〜rこれらの推測を​​入力すると、Eve は次のようになります。

ここTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGasei
WQhiGitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaあの時TWAWSQWtSWatTraPistsSJ
GSTrseayreatクリウエイワギウィティジGCsiwtsjoieqthereqeretQsrSTWHKPaGAsCStsWeeBtr
放出FSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQitha
PPtheACCearWgeSJKTRWishHysphtheQeihtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPP
thiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiSWresCeGtiWYit

これらの推測は、さらに他の推測を示唆します（たとえば、「再マー「かもしれない」述べる「」は、あ〜け) などがあり、残りの文字を推測するのは比較的簡単で、最終的に平文が得られます。

そこでレグランダは厳粛で荘厳な雰囲気を漂わせ、ガラスケースから甲虫を連れてきた。
それは閉ざされていた美しいスカラベで、当時は博物学者には知られていなかった
もちろん、科学的な観点から素晴らしい賞です。近くに丸い黒い点が 2 つありました。
背中から放射状に伸びた鱗は非常に硬く光沢があり、
磨かれた金の外観昆虫の重量は非常に顕著であり、すべてを取ります
考慮すべき事柄は、木星の意見を尊重することを責めることはできない

この時点で、Eve はスペースと句読点を挿入することをお勧めします。

そこでルグランは、厳粛で威厳のある態度で立ち上がり、私に甲虫を持って来た。
ガラスケースに入っていたそれは美しいスカラベで、
当時、博物学者には知られていなかったが、もちろん科学的な観点からは大きな賞賛に値する。
視界の端に丸い黒い斑点が2つあり、
長い鱗は、非常に硬く光沢があり、
光沢のある金色の外観。昆虫の重さは非常に顕著で、
あらゆることを考慮すると、私はジュピターの意見を責めることはほとんどできない
それを尊重する。

「 The Gold-Bug 」のこの例では、Eve の推測はすべて正しかった。ただし、常に正しいとは限りません。個々の平文の統計のばらつきは、最初の推測が間違っていることを意味する場合があります。間違った推測を遡ったり、上記の例で示したやや単純化した説明よりもさらに詳細に利用可能な統計を分析する必要があるかもしれません。

平文が期待される文字頻度分布を示さない可能性もある。短いメッセージはより多くのバリエーションを示す可能性が高い。人工的に歪んだテキストを作成することも可能である。例えば、文字を省略した小説が書かれている。e全体として、リポグラムとして知られる文学形式です。

頻度分析（実際はあらゆる種類の暗号解読）に関する最初の記録された説明は、9世紀にアラブの博学者アル・キンディーが『暗号解読に関する手稿』で行ったものである。^[3]コーランの詳細なテキスト研究によって、アラビア語には特徴的な文字頻度があることが初めて明らかになったとされている。 ^{[4]その使用は広まり、}ルネッサンスの頃までに同様のシステムがヨーロッパ諸国で広く使用されていた。1474年までに、チッコ・シモネッタはラテン語とイタリア語のテキストの暗号解読に関するマニュアルを執筆した。^[5]

単純な置換暗号化のこの弱点を克服するために、暗号学者によっていくつかの方式が考案されました。これには次のものが含まれます。

• 同音異義語の置換:同音異義語の使用。単一アルファベットの置換暗号で最も一般的な文字の複数の代替。たとえば、英語の場合、暗号文 X と Y はどちらも平文 E を意味する可能性があります。
• 多アルファベット置換、つまり、多かれ少なかれ巧妙な方法で選択された複数のアルファベットの使用（これを最初に提案したのはレオーネ・アルベルティのようだ）。
• ポリグラフィック置換、単一の文字ではなく、平文の文字のペアまたはトリプレットが置換の単位として扱われる方式。たとえば、19 世紀半ばにチャールズ ホイートストンが発明したプレイフェア暗号など。

周波数カウント攻撃を阻止しようとするこれらの試みの欠点は、暗号化と解読の両方が複雑になり、間違いにつながることです。有名な話ですが、英国の外務大臣は、ホイートストンとプレイフェアが示したように、たとえ学校の少年たちがうまく対処できたとしても、「わが国の外交官がそれを学ぶことは絶対にできない」という理由で、プレイフェア暗号を拒否したと言われています。

20世紀前半のローター式暗号機（例えばエニグマ暗号機）は、周波数解析だけでは本質的に解読できなかった。しかし、他の種類の解析（「攻撃」）によって、それらの暗号機の一部からのメッセージを解読することに成功した。^[6]

頻度分析には、平文言語の統計に関する基本的な理解と、ある程度の問題解決スキル、そして手作業で行う場合には、膨大な文字の記録に耐えられることだけが必要です。第二次世界大戦中、イギリスとアメリカの両国は、主要な新聞にクロスワードパズルを掲載し、誰が一番早く解けるかを競うコンテストを開催することで、暗号解読者を募集しました。枢軸国が使用した暗号のいくつかは、頻度分析を使用して解読可能でした。たとえば、日本が使用した領事暗号の一部です。文字のカウントと統計分析の機械的な方法 (通常はIBMカードタイプの機械) は、第二次世界大戦で初めて使用され、おそらく米軍のSISによって使用されました。今日、文字のカウントと分析の作業は、数秒でそのような分析を実行できるコンピューター ソフトウェアによって行われます。現代の計算能力では、古典的な暗号では機密データを実際に保護できない可能性があります。

頻度分析はフィクションでも説明されています。エドガー・アラン・ポーの「黄金虫」や、アーサー・コナン・ドイルの シャーロック・ホームズの物語「踊る男」は、頻度分析を使用して単純な置換暗号を攻撃する方法について説明した物語の例です。ポーの物語の暗号には、いくつかの欺瞞手段がちりばめられていますが、これは暗号学上重要なものではなく、文学的な仕掛けです。

• 偶然のインデックス
• 暗号に関するトピック
• ジップの法則
• ジョルジュ・ペレックの小説『虚空』 。フランス語の原文はeの文字なしで書かれており、英語訳も同様です。スペイン語版にはa が含まれていません。
• ガズビー (小説) 、アーネスト・ヴィンセント・ライトの小説。この小説はリポグラムとして書かれており、文字 E を含む単語は含まれていません。

• ヘレン・フーシェ・ゲインズ、「暗号解析」、1939年、ドーバー。ISBN  0-486-20097-3。
• アブラハム・シンコフ、「初等暗号解読：数学的アプローチ」、アメリカ数学協会、1966年。ISBN 0-88385-622-0。 

• オンライン周波数分析ツール
• 41 言語の文字と音節の頻度と、頻度と音節の分布を作成するためのポータブル ツール
• アラビア文字の頻度分析
• 英語テキスト内の文字の条件付き確率
• チェコ語の文字/バイグラム/トリグラムの頻度