暗号解読の手段：index of coincidence (IC)
前の記事
頻度分析について述べた前の記事はこちら。
用語について
暗号理論にはindex of coincidence (IC)という概念がある。直訳すると「一致指数」であり、これを用いているサイトも存在するが、別の分野で既に用いられている単語であるため、ここでは用いない。「一致反復率」という言葉も見かけるが、用例が少ないので使用を保留する。ここでは英語そのままindex of coincidence (IC)で通してしまうことにする。
ICとは
暗号解読において、ICは文章における文字の分布を評価する指標として使われる。大雑把に言えば、文中に出現する文字の出現頻度に偏りがある（たくさん出てくる文字がある）ほど大きく、偏りがない（ランダムである）ほど小さい値である。
以下の記事やサイトも参照のこと。
ウィキペディア（英語版記事）「Index of coincidence」
基本的なことはこちらに書いてある。
暗号解析サイトdcode.fr内のIC計算ツール
アプリのダウンロード等不要で解析ツールを使える便利な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.
ICの求め方は以下の通り。
$${\mathrm{IC} =\dfrac{\sum_{i} n_i(n_i-1)}{N(N-1)}}$$
i:A~Zのアルファベット $${n_i}$$:アルファベットiの出現回数 N:文章の文字数
数式の意味はだいたいこんな感じである。
1、AからZすべての文字について、それぞれの出現回数nを数える。A: 26, B: 2, C: 13, ...である。
2、すべての文字について、n×(n-1)を計算する。A: 650、B: 2、C: 156, ...である。
3、すべての文字についてn×(n-1)を足し合わせる。今回、その値は7962である。
4、文章の文字数Nを数える。この文章は330文字からなる。
5、N×(N-1)を計算する。今回、その値は108570である。
6、[3で求めた値]÷[5で求めた値]を計算する。これがICである。今回は0.07333...を得る。
やり方によっては、さらにアルファベットの数26をかけたものをICの値とする場合もある（英語版ウィキペディア「Index of coincidence」はこちらを採用している）。しかしここではこのような補正は行わず、上記の求め方で得た値そのままをICとして採用する。
また、文字数が十分多くない場合、ICが極端に大きい値もしくは小さい値を取る場合があるので注意が必要である。
一般的なの英語の文章におけるICはおよそ0.0667である。上述のアメリカ独立宣言の一節は、平均的英文よりも文字の出現頻度の偏りが大きいようだ。
他に極端な例を挙げると、全て同じ文字からなる文章であればIC=1であり、すべての文字が1回ずつしか出ない文章であればIC=0である。また、AからZのアルファベット26文字が偏りなくランダムに出現する文章であれば、文字数が十分多い場合、IC=1/26=0.03846…に収束する。
ICは、暗号文がどのような方法で暗号化されているかを推測する助けとなる。大体の目安を示す。
・ICが0.07程度の値を取る場合：これは通常の英文のICに近い。この場合、元の文章の文字の出現頻度分布が、文字を変えて、あるいは文字の位置を変えながら、そっくりそのまま残っているかもしれない。転置式暗号か、単一換字式暗号の可能性が考えられる。
・ICが0.045±0.005程度の場合：これは通常の英文のICよりやや低い。この場合、元の文章の特徴が若干残っているのかもしれない。これは鍵長さ4から8のヴィジュネル暗号の可能性がある。
・ICが0.0385に近い値を取る場合：これはランダムなテキストのICに近い。エニグマなど、長周期の多表式換字暗号の可能性がある。
あくまでこれは一例であり、多様な暗号の性質に対して大小さまざまな値を取る。
実際の例を示す。前の記事で例示した暗号文について、ICを計算すると次のようになる。
暗号化前の文章: IC=0.07333…
単一換字式暗号: IC=0.07333...
転置式暗号: IC=0.07333...
ヴィジュネル暗号（鍵長さ5）: IC=0.04478...
プレイフェア暗号: IC=0.05808...
エニグマ: IC=0.03835…
大体上で述べた目安に合っていることが分かる。暗号文がどの方法で暗号化されているかが未知である場合、ICはその推測の手がかりの一つとなる。無論、ICのみに頼り切りになるのではなく、暗号文の持つ他の特徴も観察すべきである。例えば「暗号文の文字数が偶数」「Jが1回も現れない」「2文字ごとに区切っても、同じ文字からなる2文字組が現れない」といった特徴があればプレイフェア暗号の可能性がある。
応用
暗号文全てではなく、「1文字目から5文字ごとの文字」「2文字目から5文字ごとの文字」……「5文字目から5文字ごとの文字」というように、一定周期ごとにICを求め、それらの平均を求める、といったこともできる。
これはヴィジュネル暗号のような、周期性を持つ暗号に対して威力を発揮する。ヴィジュネル暗号においては、一定周期ごとに同じ暗号アルファベットを用いて暗号化されているため、その頻度分布は単一換字式暗号と同様になるためである。
WKEZANWHQUOXREWOIHGEAQEHWNWSULBHCAEEVNQUEVSMJYIODGNHPQGPOEFGDLSEGLYEFZESOXATLCMDBDNPKWKIOZHDVQUOQNQUTHDFZEPWULHDNALHHRMFDWOMKSXMQSMRNSLHHPAOEUSAXTKEQSRWHFZEVEBSRDTQSNGECMAOSFSTLOZLOZHUUHWHQDAZSAXNDTGJEDNPGFQAFMRHSSGDHNFATOEFZEPAPWCHNFJEVPQUTWOFZERPUFIRNEGFPAZCIQDDWQXIDWSWHMLTKEKKHRUXVDHCXSRHTTWCDUEWSZHUUHLMBWLWHQETRTTWSHPMJAWIAF
これは前の記事にも登場したヴィジュネル暗号文である。鍵は「ADAMS」であり、その長さは5である。
実際に計算を行ってみる。5文字ごとにICを求めるとIC ≈ 0.07133 ± 0.004という高い値を得ることが出来る。4文字ごとの場合ではIC ≈ 0.04329 ± 0.032、6文字ごとの場合ではIC ≈ 0.04545 ± 0.03という低い値がでるのと対照的である。これを利用して、周期性のある暗号の周期を推測することが出来る。
dcode.frではこのような計算もやってくれるので便利。
まとめ
・暗号解読においてICとは文章の文字の出現分布を評価する指標である。たくさん出てくる文字があると大きく、ランダムだと小さい。
・ICはその暗号文がどの方法で暗号化されているかを推測する手がかりになる。
・一定周期ごとにICを求めることで、暗号文の持つ周期的特徴を明らかにすることが出来る場合がある。
参考文献
ウィキペディア（英語版）「Index of coincidence」
次の記事
この記事が気に入ったらサポートをしてみませんか？