偶然のインデックス

暗号学において、同時発生数え上げ法は、2つのテキストを並べて、両方のテキストの同じ位置に同一の文字が出現する回数を数える手法です（ウィリアム・F・フリードマン^{[1]によって発明されました）。この数は、合計に対する比率として、またはランダムソースモデルの期待値で割って正規化されたもので、}一致指数、略してIC、IOC ^[2]、IoC ^[3]として知られています。

自然言語の文字は均等に分布していないため、そのようなテキストの IC は、一様にランダムなテキスト文字列の場合よりも高くなります。IC が特に便利なのは、両方のテキストが同じ単一アルファベット置換暗号で暗号化されてもその値が変わらないため、暗号解読者がその形式の暗号化をすぐに検出できる点です。

一致指数は、特定のテキストから 2 つの文字をランダムに選択して、一致する 2 つの文字が出現する可能性の尺度を提供します。テキスト内で特定の文字が出現する確率は、(その文字の出現回数 / テキストの長さ) です。同じ文字が再び出現する確率 (置き換えなし) は、(出現回数 - 1 / テキストの長さ - 1) です。これら 2 つの値の積は、その文字が 2 回続けて出現する確率を示します。テキスト内に表示される文字ごとにこの積を求め、これらの積を合計すると、同じ文字が 2 つ出現する確率が得られます。この確率は、英語では通常 26 などの係数を掛けて正規化できます。

${\displaystyle \mathbf {IC} =c\times \left({\left({{\frac {n_{\mathrm {a} }}{N}}\times {\frac {n_{\mathrm {a} }-1}{N-1}}}\right)+\left({{\frac {n_{\mathrm {b} }}{N}}\times {\frac {n_{\mathrm {b} }-1}{N-1}}}\right)+\cdots +\left({{\frac {n_{\mathrm {z} }}{N}}\times {\frac {n_{\mathrm {z} }-1}{N-1}}}\right)}\right)}$

ここで、cは正規化係数 (英語の場合は 26)、n _{a は}テキスト内で文字「a」が出現する回数、N はテキストの長さです。

与えられた文字頻度分布の 一致指数IC は、次のように合計として表すことができます。

${\displaystyle \mathbf {IC} ={\frac {\displaystyle \sum _{i=1}^{c}n_{i}(n_{i}-1)}{N(N-1)/c}}}$

ここで、Nはテキストの長さ、n ₁からn _{c は}アルファベットのc文字の頻度（整数）です（モノケース英語の場合はc = 26 ）。 n _iの合計は必ずN になります。

積n ( n − 1)は、 n個の要素を2 つずつ組み合わせた数です (実際には各ペアを 2 回カウントします。2 という余分な因数は、式の分子と分母の両方に出現するため、打ち消されます)。i 番目の文字の n i 回の出現は、同じ_文字の残りのn _i − 1 回の出現のそれぞれと一致します。テキスト全体では合計N ( N − 1)個の文字ペアがあり、1/ c は、文字が均一にランダムに分布していると仮定した場合の各ペアの一致の確率です(「ヌル モデル」、下記参照)。したがって、この式は、観測された一致の合計数と、ヌル モデルから予想される一致の合計数の比率を示します。^[4]

ICの予想平均値は、ソース言語の 相対的な文字頻度f _iから計算できます。

${\displaystyle \mathbf {IC} _{\mathrm {期待値} }={\frac {\displaystyle \sum _{i=1}^{c}{f_{i}}^{2}}{1/c}}.}$

アルファベットのすべてのc文字が等しく出現する確率である場合、期待される指数は 1.0 になります。実際の電信英語テキストのモノグラフィック IC は約 1.73 であり、自然言語の文字分布の不均一性を反映しています。

時には、正規化分母なしで値が報告されることもあります。たとえば、英語の場合、 0.067 = 1.73/26です。このような値はIC ではなくκ _p (「カッパ平文」)と呼ばれ、 κ _r (「カッパランダム」) は分母1/ c (同じアルファベットの一様分布の期待一致率、英語の場合0.0385=1/26 ) を表すために使用されます。英語の平文は通常、1.5 から 2.0 の範囲になります (正規化計算)。^[5]

一致度指数は、自然言語の 平文の解析と暗号文の解析（暗号解読）の両方で役立ちます。暗号文のみがテストに使用でき、平文の文字の同一性が偽装されている場合でも、暗号文の一致は、基礎となる平文の一致によって引き起こされる可能性があります。この手法は、たとえば、ヴィジュネル暗号の暗号解読に使用されます。マトリックスに配置された繰り返しキーの多アルファベット暗号の場合、各列内の一致率は通常、マトリックスの幅がキーの長さの倍数であるときに最も高くなります。この事実を使用して、システムを解読するための最初のステップであるキーの長さを判断できます。

偶然の一致を数えることは、2 つのテキストが同じ言語で同じアルファベットを使って書かれているかどうかを判断するのに役立ちます。(この手法は、聖書の暗号とされるものを調べるために使用されています。)このようなテキストの因果的偶然の一致数は、異なる言語のテキスト、異なるアルファベットを使ったテキスト、または意味不明なテキストの偶然の一致数よりも明らかに高くなります。^{[引用が必要]}

理由を理解するには、A と B の 2 つの文字だけからなる「アルファベット」を想像してください。私たちの「言語」では、文字 A が 75% 使用され、文字 B が 25% 使用されると仮定します。この言語の 2 つのテキストを並べると、次のペアが予想されます。

全体として、「偶然」の確率は 62.5% (AA の場合は 56.25%、BB の場合は 6.25%) です。

ここで、両方のメッセージが A を B に、またはその逆を置き換える 単純な単一アルファベット置換暗号を使用して暗号化されている場合を考えてみましょう。

この状況で一致する全体的な確率は 62.5% (AA の場合は 6.25%、BB の場合は 56.25%) で、暗号化されていない「プレーンテキスト」の場合とまったく同じです。実際には、置換によって生成された新しいアルファベットは、元の文字 ID の均一な名前変更にすぎず、一致するかどうかには影響しません。

ここで、 1 つのメッセージ (たとえば 2 番目のメッセージ)だけが同じ置換暗号 (A,B)→(B,A) を使用して暗号化されているとします。次のペアが予想されます。

これで、一致の確率はわずか 37.5% (AA で 18.75%、BB で 18.75%) になりました。これは、同じ言語、同じアルファベットのテキストが使用された場合の確率よりも著しく低いです。明らかに、各テキストで最も頻繁に使用される文字が同じ場合、一致の可能性が高くなります。

同じ原理は英語のような実際の言語にも当てはまります。なぜなら、E のような特定の文字は他の文字よりもはるかに頻繁に出現するからです。この事実は、換字式暗号の頻度分析で使用されます。たとえば、文字 E に関する一致は比較的起こりやすいものです。そのため、任意の 2 つの英語のテキストを比較すると、一致数は英語のテキストと外国語のテキストを比較した場合よりも多くなります。

この効果は微妙な場合があります。たとえば、類似した言語は、類似していない言語よりも一致数が高くなります。また、実際のテキストに似た頻度分布を持つランダム テキストを生成し、一致数を人工的に増やすことも難しくありません。それでも、この手法は、2 つのテキストに同じアルファベットを使用する同じ言語で意味のある情報が含まれている可能性が高い場合を特定したり、キーが繰り返される期間を発見したり、暗号文内または暗号文間で他の多くの種類のランダムでない現象を発見したりするために効果的に使用できます。

^{さまざまな言語[6]}の期待値は以下のとおりです。

上記の説明は、相関の一般的な概念に関連する一致指数の使用についての紹介に過ぎません。一致指数にはさまざまな形式が考案されています。「デルタ」IC（上記の式で与えられる）は、実質的に単一の分布の自己相関を測定しますが、「カッパ」ICは2つのテキスト文字列を一致させるときに使用されます。 ^[7]一部のアプリケーションでは、や などの定数は無視できますが、より一般的な状況では、各ICを帰無仮説（通常は一致なし、一様ランダムシンボル分布）に期待される値に対して実際にインデックス付けすることにかなりの価値があります。これにより、すべての状況で相関なしの期待値は1.0になります。したがって、特定のテスト設定を使用して、実際に観測された一致の数と（帰無モデルに従って）期待される一致の数の比として、どの形式のICも表すことができます。 ${\displaystyle c}$${\displaystyle N}$

以上のことから、κICの式は次のように表せることが分かる。

${\displaystyle \mathbf {IC} ={\frac {\displaystyle \sum _{j=1}^{N}[a_{j}=b_{j}]}{N/c}},}$

ここで、 は2 つのテキストAとBの共通の長さであり、括弧内の項は、テキストAの - 番目の文字がテキストBの - 番目の文字と一致する場合は 1 、それ以外の場合は 0 と定義されます。 ${\displaystyle N}$${\displaystyle j}$${\displaystyle j}$

関連する概念である分布の「膨らみ」は、観測された IC とヌル値 1.0 の間の差異を測定します。多アルファベット暗号で使用される暗号アルファベットの数は、単一のアルファベットのデルタ IC の予想される膨らみをメッセージの観測された膨らみで割ることで推定できますが、多くの場合 (繰り返しキーが使用される場合など)、より優れた手法が利用できます。

IC の使用の実際的な例として、次の暗号文メッセージを傍受したと仮定します。

私達はあなたのために働く
IZRVK CVKVL XNEIC FZPZC ZZHKM LVZVZ IZRRQ WDKEC HOSNY XXLSP
MYKVQ XJTDC IOMEE XDQVS RXLRL クゾフ

(5 文字にグループ化するのは単なる電信上の慣例であり、実際の単語の長さとは関係ありません。) これは、通常の A ～ Z の要素と短い繰り返しキーワードを含むVigenère 暗号を使用して暗号化された英語の平文であると推測され、暗号文がいくつかの列、たとえば 7 列に「積み重ねられた」ものと考えられます。

QPWKALV
RXCQZIK
GRPBFAE
オムフルール
翻訳
ジェビム
TRQWN…

キー サイズが想定された列数と同じだった場合、1 つの列内のすべての文字が同じキー文字を使用して暗号化されます。これは、ランダムに選択された英語のプレーンテキスト文字に適用される単純なシーザー暗号と実質的に同じです。対応する暗号文の文字セットは、文字 ID が入れ替わっている (キー文字に対応する一定量だけシフトしている) にもかかわらず、英語と同様の頻度分布の粗さを持つはずです。したがって、すべての列 (「デルタ バー」) の合計デルタ IC を計算すると、約 1.73 になります。一方、キー サイズ (列数) を誤って推測した場合、合計デルタ IC は約 1.00 になります。したがって、想定されるキー サイズが 1 から 10 の場合のデルタ IC を計算します。

キーのサイズはおそらく 5 であることがわかります。実際のサイズが 5 の場合、幅 10 でも高い IC が報告されると予想されます。これは、各列が単純なシーザー暗号にも対応しており、これが確認されたためです。したがって、暗号文を 5 つの列に積み重ねる必要があります。

クムル
LVRXC
クジク
RBPFA
EOMFL
ＪＭＳＤＺ
VDH…

それぞれの列について最も可能性の高いキー文字を決定しようと試みることができる。そのためには、列全体の試行シーザー復号をキー文字の26のA～Zのそれぞれについて実行し、復号された列の文字頻度と通常の英語テキストの相対的な文字頻度との間に最も高い相関関係を生み出すキー文字を選択する。この相関関係は正規化を気にする必要がなく、次のように簡単に計算できる。

${\displaystyle \mathbf {\chi } =\sum _{i=1}^{c}n_{i}f_{i}}$

ここで、 は観測された列の文字頻度であり、は英語の相対的な文字頻度です。これを試すと、最も適合するキー文字は「」であると報告され、これは実際の単語として認識され、それをヴィジュネル復号化に使用すると、次の平文が生成されます。 ${\displaystyle n_{i}}$${\displaystyle f_{i}}$EVERY

マスト・ハンゲがリッジ・トゥーン・エルパスからのグロックと会う
SSINC EENEM YAGEN TSARE BELIE VEDTO HAVEB EENAS SIGNE
DTOWA TCHBR IDGES TOPME ETING TIMEU NCHAN GEDXX

そこから次のものが得られます。

集合場所を橋から地下道へ変更する必要があります
敵のエージェントが派遣されていると考えられているため
ブリッジを見るには、会議時間を変更せずに停止しますXX

単語の区切りが明らかな位置で復元された後。「XX」は明らかに、送信のために最後のグループを埋めるために使用される「ヌル」文字です。

この手順全体を、このような暗号を解読するための自動化アルゴリズムに簡単にパッケージ化できます。通常の統計的変動により、このようなアルゴリズムは、特に短い暗号文メッセージを分析する場合に、誤った選択をすることがあります。

• カシスキ検査
• リバーバンク出版
• 暗号に関するトピック