暗号紹介:Bifid暗号 暗号の仕組みとその特徴
用語について
bifidとは「二つの部分に裂けた」「二分の」「二裂の」を意味する語。発音は「バイフィド」。強いて訳せば「二分暗号」「二裂暗号」となるだろうか。その用例はないので、ここでは原語のままで通す。
Bifid暗号とは
1901年頃、フランス人の暗号作成者Félix-Marie Delastelle(1840-1902)により発明された。DelastelleはTrifid暗号(Bifid暗号の発展形)やFour-square暗号も発明している。
Bifid暗号が政治・軍事・外交的に実用されたという記述は見かけない。しかし、それは暗号学者クロード・シャノンのいうところの攪乱と拡散(confusion and diffusion)、すなわち「暗号文と鍵の関係を複雑にすること」と「暗号文に平文の統計的特徴を反映させないこと」を実装した暗号としては早期のものであった(同様のことを行っているADFGVX暗号より早い)。これは暗号学上かなり重要な仕組みである。
Delastelle自身は軍人や外交官、学者と言ったプロフェッショナルではなく、アマチュアの暗号作成者で、本業は保税倉庫業者であった。
以下のサイトも参考のこと。
ウィキペディア記事(英語版)「Bifid cipher」
暗号解析サイトdcode.fr内のBifid暗号化・復号ツール
暗号化方式
「example message」をBifid暗号で暗号化する。用意するものはポリュビオスの暗号表と、周期である。今回は次の暗号表を使い、周期は5とする。
\ 1 2 3 4 5
1 D E L A S
2 T B C F G
3 H I K M N
4 O P Q R U
5 V W X Y Z
(キーワードはDelastelleである)
1、表を用いて、各文字を2桁の数字に変換する。e→12(eは1行2列目にあるので)、x→53、……、g→25、e→12という具合である。その2桁の数字を縦書きする。2行×(暗号の文字数)列の数字の行列ができる。
2、数字の行列を(周期の数)列ごとに区切る。今回の周期は5なので、行列は左から5列ずつ区切る。場合によっては周期の数に満たない列ができるが問題ない。これで、2×5=10文字からなるブロックがいくつかと、場合によっては文字数の少ないブロックができる。
3、1つ目のブロックに注目する。数字を横方向に読み取ると、1513423442となる。これを2つごとに区切り、表を用いて文字に変換する。15→S、13→L、……という具合である。これによりSLPMPの文字列を得る。
4、残るブロックにも同様の操作を施す。得られた文字列を連結させ、暗号文「SLPMPDH LFGDTYW」を得る。
以上の過程を図1に示す。
復号方法
鍵を知っている正当な受信者が、受け取った暗号文を復号する方法を述べる。
1、暗号文を周期ごとに区切る。
2、各ブロックの文字列を、暗号表を用いて数字の列に変換する。それを2分割して縦に並べる。2行×(周期の数)列の数字の行列ができる。
3、それぞれの列に含まれる2つの数字を、暗号表を用いて文字に変換する。
4、すべてのブロックに対して同じ操作を行い、得られた文字列を連結すると元のメッセージを得られる。
解読方法
Bifid暗号の性質
解読を行うにあたり、まずBifid暗号の性質を調べる。Bifid暗号は周期が奇数か偶数かによって少し異なる性質を持っている。
まず周期が偶数、例えば4の場合を考える。元のメッセージ「example message」の一部だけを取り出し、それがどのように変換されるかを観察する。なお、暗号表は図1と同じものを用いる。これを図2に示す。
exaの3文字組が2つ離れたSとCに、lemの3文字組が2つ離れたLとFに変換されている。この2つ離れた、というのがポイントである。周期が4の場合、元のメッセージの3文字組は、暗号文の2つ離れた2文字のペアに変換される。一般化すると、周期がp(偶数)の場合、元のメッセージの3文字組から、暗号文のp/2だけ離れた2文字のペアを得られる。
続いて周期が奇数、例えば5の場合を考える。「example message」の一部だけを取り出し、それがどのように変換されるかを観察する。なお、暗号表は図1と同じものを用いる。これを図3に示す。
exaの3文字組が3つ離れたSとMに、emeの3文字組が2つ離れたHとFに変換されている。周期が5の場合、元のメッセージの3文字組は、暗号文の2つもしくは3つ離れた2文字のペアに変換される。一般化すると、周期がp(奇数)の場合、元のメッセージの3文字組から、暗号文の「p/2の直前または直後の整数」だけ離れた2文字のペアを得られる。
以上のことから、元のメッセージの3文字組が、「一定数だけ離れた2文字のペア」に影響することが見て取れる。
つまり暗号解読に当たっては「一定数だけ離れた2文字のペア」の数を数え上げてみることが有効のようである。その「一定数」を1,2,3,…と変えて逐一2文字のペアを数え上げていくのは、人力ではかなり大変である。これはコンピューターを使う必要があるようだ。
周期特定の実践
ここで実践のために、長文の暗号文を用意する。
まず1だけ離れた2文字のペア(つまり隣り合う2文字組)を数え上げる。5回出現するペアが1種類、4回出現するペアが1種類、3回出現するペアが14種類、2回出現するペアが52種類、1回だけ出現するペアが174種類。これをどうすればいいかというと、一致するペアが多いほど大きい値を取るような指標を求める。ここでは分散を計算する。その値は0.4220…である。
ついで2だけ離れた2文字のペアについても数え上げ、分散を求めると0.6098…となる。3だけ離れた場合、4だけ離れた場合、……も同様に分散を求めると次の図4に示すような結果を得る。
5、6文字だけ離れたペアに関して分散の値が大きい、つまり一致するペアが多いということになる。したがって、周期は11であると推定できる。
暗号表の決定
暗号表の決定が一番難しいところである。方法は次の3通りが考えられる。
1、鍵となる単語・フレーズに心当たりがあれば、それをもとに暗号表を作ってみる。
2、プレーンテキストの一部を推測し、暗号表を復元する。
3、暗号文のみから、コンピューター任せの力業で解く。
ここでは2を少し詳しく見てみる。
暗号文の冒頭が「when in the course of human events」だということが分かったとする。
まず、Wが1行2列目、Hが3行4列目、Eが5行6列目……というように仮の行数・列数を当てはめていく。この仮に当てはめた数を用いて、暗号文の行数と列数を表す。これを図5に示す。
暗号文のEは5行13列目、4行6列目、そして行は不明ながら6列目に存在する。プレーンテキストのEは5行6列目に存在することから、4・5番目の行および列、6・13番目の行および列はそれぞれ一致する。これを4-5、6-13というように表記する。Wを見れば2-4であり、Hを見れば4-6であるから、これらをまとめて2-4-5-6-13が成り立つ。このように、一致する行・列をまとめていき、表にする。これを図6に示す。
暗号表は5×5なので、はみ出している文字を詰め込んでいく。8列目に着目すると、1行目に空きがあり、28行目にYがある。このことから1行目と28行目は一致する(1-28)。
続いて26列目に着目すると、1行目にX、7行目にMの2文字がある。暗号表の中を見ると、1行目と7行目がともに空いているのは7列目のみである。このことから7列目と26列目は一致する(7-26)。
Iに着目すると3行目と9行目が一致し、Gに着目すると3列目と27列目が一致する(3-9-27)。これにより27行目(=3行目)のAも暗号表内に入り、はみ出している文字はなくなった。
ここで、列を並べ替え、Q,R,S,T,Uがアルファベット順に並ぶようにしておく。この時同時に行も並べ替え、どちらも上・左から3,2,7,8,1の順番が保たれるようにする。
以上の過程を図7に示す。
残った文字はD,P,Zだが、これらは未解読の部分を解くか推測するかして埋めることが出来る。これらを埋めて、仮の番号を真の番号で書き換えて暗号表は完成する。
\ 1 2 3 4 5
1 P H I L A
2 D E B C F
3 G K M N O
4 Q R S T U
5 V W X Y Z
(キーワードはPhiladelphiaである)
元のメッセージは次のようになる。
Bifid暗号の特徴
・元のメッセージの3文字組は、「一定数離れた2文字のペア」に影響する。その「一定数」を求めるには、逐一数え上げてその特徴を見る方法がある。(他の方法を筆者は知らない)。
・index of coincidence(IC)は0.04から0.05程度の値を取る。上の例ではIC=0.04731である。
・暗号表の任意の2行もしくは2列を入れ替えると、暗号文の出力結果が変わってしまう。しかし2行と同時に対応する2列も入れ替えると、暗号文は変化しない。
まとめ
・Bifid暗号は、平文の文字を2つ以上の要素に分割したうえで転置を施し、個々の文字の構成要素が暗号文内で分離するようにしている。
・解読のために周期を特定する必要があるが、人力ではかなり大変である。プログラムを組むまではいかなくても、エクセルもしくはスプレッドシートをある程度扱えれば周期を求めることができる。
・周期を特定した後、人力で暗号表を求めるには鍵となる単語・フレーズを探すか、プレーンテキストの一部を推測する必要がある。暗号文のみから人力で表を求めるのは困難。
参考文献・資料
・Practical cryptography
Bifid暗号の周期特定について説明している。また、暗号表を焼きなまし法により求める、C言語のプログラムを載せているようだ(筆者はC言語環境を持っていないので確かめられず)。
この記事が気に入ったらサポートをしてみませんか?