目的
Rで「ヴィジュネル暗号」を解きながら次のようなことを学びます。
– χ二乗検定を用いて既知の頻度分布と、手元のデータの分布が一致するか調べることができる。
– Rの（癖のある）文字列操作をちょっとできるようになる。
スポンサーリンク
今回解読する暗号文
sqxoipqubqafvblrpbbqeuddebwucqgjhoiotrrwuvilhgjrkjukvzeavlkuavdkujpdqybpfldpglsuqkqiyoguqonpgauqkfxjrfwljugsoecqvfjvqqqxnvdibzgqxhreubqgggbghcokejyhxhrgqdqtggfdniubqgelsyyydojruwfdtykbjuguqxnvqxjvqqlhnpbkqgkrkiberksrkybtnpgpeqggfsnvhasnpoldtgqakegzbqegpbjbpddhrcwyqgvobvvgoaesvkxjjcutuucybsbohqeqggfsnvhxfbtwfeaqiqxnvifuyfdpqskqxbegvqyaisiqpgilhgjrpujjreuegjxlrvkbyenlsufvkxjgjhkqgkrkcvikqbvxhfjvudijbihqxrtifjgkqdqafsoecguqxnvzbiuqxitqqweyfdxqyacoxhtgupuauhtupcqkegfhaypcwbmredkdbvfldfgfoqggzbsnpqljucoiejvkfittrrdqvkbrecybcrpoflvpjxdqfhxtjjrpjewjdbrfkbhrjdsupqqpuptdquqkwcqecellrqxofbqumejguqenfglhqgwoqpvweujquitjkoibvvwiuaqwbdbtoldtthjuzdhomucwtufcbeuegerjvvfxdagybhsqudugykxjgjhvtvfkbhrkwfisqurigjhiyikqdhnvkbhgqebtrflzqgggeuegwljugxkvvplpxrfzlhxykfsuvkbojjrcehikqxrtheqigwekfhdoibpryblcgsqaehaygkvoqgjhovbtxpjbdheueggbtvedquqvrqxriubqgvdpaegpxyakqdrrhrouhuweqghulcgjhpuuqqlhrfgbqqyhqqxglksegdpuqfhsegkrkjbvkxjpcxpusqutxvekqxrajxlrvkbbnuwckynpbqfwubesfhsegkrkjucwtuugubxvikioegvlbigweqgvkbirfhxtfjdibaqweqiggfuqkqsqvpweqgvkfiacwfeawqaueiraiucoixnxhxdryefhgjrcveghaezcqajucwdeigukcrpwlvgjhmubrobrlvkbfrqsiusquqxrrhlfygveqynqljcgufiuhulcgjhbqevkce
なお平文に関して以下は既知とします。
- アルファベット小文字（26文字）のみ
- ヴィジュネル暗号を使っていることは既知
暗号解読の方針
ヴィジュネル暗号は次の解き方がよく知られています。
- 鍵の長さを推定する
- 鍵の長さに従って文字列を分割し、頻度解析を行う
今回は鍵の長さを推定するところをRをうまく使ってみたいと思います。
解読作業
暗号文をRに読み込ませる
#暗号文を変数にいれる crypt = "sqxoipqubqafvblrpbbqeuddebwucqgjhoiotrrwuvilhgjrkjukvzeavlkuavdkujpdqybpfldpglsuqkqiyoguqonpgauqkfxjrfwljugsoecqvfjvqqqxnvdibzgqxhreubqgggbghcokejyhxhrgqdqtggfdniubqgelsyyydojruwfdtykbjuguqxnvqxjvqqlhnpbkqgkrkiberksrkybtnpgpeqggfsnvhasnpoldtgqakegzbqegpbjbpddhrcwyqgvobvvgoaesvkxjjcutuucybsbohqeqggfsnvhxfbtwfeaqiqxnvifuyfdpqskqxbegvqyaisiqpgilhgjrpujjreuegjxlrvkbyenlsufvkxjgjhkqgkrkcvikqbvxhfjvudijbihqxrtifjgkqdqafsoecguqxnvzbiuqxitqqweyfdxqyacoxhtgupuauhtupcqkegfhaypcwbmredkdbvfldfgfoqggzbsnpqljucoiejvkfittrrdqvkbrecybcrpoflvpjxdqfhxtjjrpjewjdbrfkbhrjdsupqqpuptdquqkwcqecellrqxofbqumejguqenfglhqgwoqpvweujquitjkoibvvwiuaqwbdbtoldtthjuzdhomucwtufcbeuegerjvvfxdagybhsqudugykxjgjhvtvfkbhrkwfisqurigjhiyikqdhnvkbhgqebtrflzqgggeuegwljugxkvvplpxrfzlhxykfsuvkbojjrcehikqxrtheqigwekfhdoibpryblcgsqaehaygkvoqgjhovbtxpjbdheueggbtvedquqvrqxriubqgvdpaegpxyakqdrrhrouhuweqghulcgjhpuuqqlhrfgbqqyhqqxglksegdpuqfhsegkrkjbvkxjpcxpusqutxvekqxrajxlrvkbbnuwckynpbqfwubesfhsegkrkjucwtuugubxvikioegvlbigweqgvkbirfhxtfjdibaqweqiggfuqkqsqvpweqgvkfiacwfeawqaueiraiucoixnxhxdryefhgjrcveghaezcqajucwdeigukcrpwlvgjhmubrobrlvkbfrqsiusquqxrrhlfygveqynqljcgufiuhulcgjhbqevkce" #1文字ずつ分解する strsplitはListを返す。配列化のためunlistする crypt.split = unlist(strsplit(crypt,""))
暗号文を1文字ずつ分割します。
1文字ずつ分割するにはstrsplitを使います。
strsplitはListを返すため unlistを使い配列化します。
アルファベットの頻度分布表を準備
#アルファベットの頻度分布表のデータを用意する
table_freq = c(0.0817,0.0149,0.0278,0.0425,0.1268,0.0223,0.0202,0.0609,0.0697,0.0015,0.0077,0.0403,0.0241,0.0675,0.0751,0.0193,0.001,0.0599,0.0633,0.0906,0.0276,0.0098,0.0236,0.0015,0.0197,0.0007)
#後ほど使いやすいようにソートする
table_freq.sort = sort(table_freq)
#factorは後ほど使います
table_freq.factor = c("a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z")
アルファベットの頻度分布表は以下から拝借しました。（合計が1となるよう少し数字を変えています）
Weblio 辞書 文字の出現頻度
鍵長を探す
鍵の長さをnと仮定し、暗号文からn文字ごとに文字を拾ってきて、アルファベットの頻度分布と比べます。
例えば暗号文が次のようになっているとして、n=3の場合を考えます。
| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 暗号文 | a | b | c | d | a | b | c | d | a | b | c | d | a | b | c |
この場合、3つの文字の集合に分割できます。
- index1から始まって3文字ごとに拾った文字集合1：「adcba」
- index2から始まって3文字ごとに拾った文字集合2：「badcb」
- index3から始まって3文字ごとに拾った文字集合3：「cbadc」
それぞれ集合の文字の度数分布表を作成し、アルファベットの頻度分布表に従っているかを見ていくことで、鍵長を推測します。
nが鍵長であれば、すべての集合がアルファベットの頻度表とよく一致するはずです。
n=1
n=1の場合は、ヴィジュネル暗号ではなくシーザー暗号というのですが、気にせず計算してみます。
n = 1 # n行のマトリックス＝n文字ごとに文字を拾う c.split = matrix(crypt.split,n) #1行目を抜き出して度数分布を作る。 #1度も利用されていないアルファベット文字も度数分布表に出てくるよう、factorを用いる。 #度数順にソートする X.1 = sort(table(factor(c.split[1,],levels=table_freq.factor))) #χ二乗検定でX.1と頻度分布表を比べる chisq.test(x=X.1,p = table_freq.sort)
X-squared = 759.61, df = 25, p-value < 2.2e-16
χ二乗検定の結果は上記のようになりました。
見るべき値は有意水準（p-value）です。
伝統的に有意水準を1%,5%,10%など決めて、その範囲を逸脱したら棄却するという風に検定を行います。今回は短い文なので10%ぐらいに設定したいと思います（つまり、p-valueが0.9以上で採択する）。
改めて出力されたp-valueを見ると、とても小さい値なので棄却です。
n=2
続けてn=2を見ていきましょう。
ここからは複数の文字集合が出てくるのですが1つずつ見てみます。
もし、1つ目で希望が持てなければ次のnを試します。
n = 2 # n行のマトリックス＝n文字ごとに文字を拾う c.split = matrix(crypt.split,n) # 1行目を抜き出して度数分布を作る。 #1度も利用されていないアルファベット文字も度数分布表に出てくるよう、factorを用いる。 X.1 = sort(table(factor(c.split[1,],levels=table_freq.factor))) #χ二乗検定でX.1と頻度分布表を比べる chisq.test(x=X.1,p = table_freq.sort)
X-squared = 279.19, df = 25, p-value < 2.2e-16
n=2の時も一致していないといえます。
n=5
いきなり飛んで申し訳ないですが、n=3,n=4も同様にみて、ダメだったとします。
n=5の場合はどうでしょうか。
n = 5 # n行のマトリックス＝n文字ごとに文字を拾う c.split = matrix(crypt.split,n) # 1行目を抜き出して度数分布を作る。 #1度も利用されていないアルファベット文字も度数分布表に出てくるよう、factorを用いる。 X.1 = sort(table(factor(c.split[1,],levels=table_freq.factor))) #χ二乗検定でX.1と頻度分布表を比べる chisq.test(x=X.1,p = table_freq.sort)
X-squared = 6.5934, df = 25, p-value = 0.9999
有意水準が0.9999とかなり高い値が出ました。
希望が持てます。
念のため、2～5行目も試してみます。
#2～5行目もやってみます。 X.2 = sort(table(factor(c.split[2,],levels=table_freq.factor))) X.3 = sort(table(factor(c.split[3,],levels=table_freq.factor))) X.4 = sort(table(factor(c.split[4,],levels=table_freq.factor))) X.5 = sort(table(factor(c.split[5,],levels=table_freq.factor))) chisq.test(x=X.2,p = table_freq.sort) #p-value = 0.6647 chisq.test(x=X.3,p = table_freq.sort) #p-value = 0.9963 chisq.test(x=X.4,p = table_freq.sort) #p-value = 0.9598 chisq.test(x=X.5,p = table_freq.sort) #p-value = 0.9256
いずれもとてもよく一致しているといえるので鍵長は5と推定できました。
復号化
鍵長がわかったので復号化をします。
鍵を求める
5つの文字セットそれぞれの鍵を突き止める必要があります。
暗号文字の出現回数から平文字を推測します。
まずは、暗号文字の出現回数を眺めてみます。
X.1
d k m w l o x c h z i y t f s p j q a b v n u e r g
0 0 0 0 2 2 2 3 3 3 5 5 6 7 8 9 10 13 15 15 15 16 16 18 28 29
gやrの出現回数が他の文字に比べて多いですね。
ここで、通常のアルファベットの頻度分布表を出現率の昇順に並べてみます。
Z Q J X K V B P Y G F W M U C L D R H S N I O A T E
出現率はE：12.7% , T：9.06%となっており圧倒的にEが多く出現することがわかります。そのため、鍵探しはEが何に対応するかを考えながら行います。
X.1の度数表ではg,rの出現率が高くなっていました。このいずれかがEであると考えてみます。
- gをEになるように置換する(鍵”25″に相当)
- 通常のアルファベットで頻度分布の上位に来る 「E,T,A,O,I」に対応するものは「G,V,C,Q,K」となります。これはX.1の度数分布で上位を占めているとはいいがたいですね。
- rをEになるように置換する(鍵”14″に相当)
- 同様に考えると、「E,T,A,O,I」に対応するものは「R,G,N.B,V」となります。これはX.1の度数分布の上位を占めているので鍵の1文字目は”14″と考えられます。
同様にX.2～X.5から鍵の2～5文字目を探します。
結果だけ書くと、鍵は 14,3,4,24,17となりました。
復号化する
いよいよ復号化です。
#鍵1～26に対応した変換表
key_list = c(
"a-z", # 鍵"1"に対応
"za-y",# 鍵"2"に対応(以下同様)
"y-za-x", "x-za-w", "w-za-v", "v-za-u", "u-za-t", "t-za-s", "s-za-r", "r-za-q", "q-za-p", "p-za-o",
"o-za-n", "n-za-m", "m-za-l", "l-za-k", "k-za-j", "j-za-i", "i-za-h", "h-za-g", "g-za-f", "f-za-e",
"e-za-d", "d-za-c", "c-za-b", "b-za"
)
#鍵を順番通りに配列にセットする
key = c(key_list[14],key_list[3],key_list[4],key_list[24],key_list[17])
#各成分に鍵を適用する
p.l1 = chartr("a-z",key[1],c.split[1,])
p.l2 = chartr("a-z",key[2],c.split[2,])
p.l3 = chartr("a-z",key[3],c.split[3,])
p.l4 = chartr("a-z",key[4],c.split[4,])
p.l5 = chartr("a-z",key[5],c.split[5,])
#１つの文字列に連結する
decrypt.matrix = rbind(p.l1,p.l2,p.l3,p.l4,p.l5)
decrypt.split = paste(decrypt.matrix[,])
decrypt = paste(decrypt.split,collapse="")
#平文
decrypt
fourscoreandsevenyearsagoourfathersbroughtforthonthiscontinentanewnationconceivedinlibertyanddedicatedtothepropositionthatallmenarecreatedequalnowweareengagedinagreatcivilwartestingwhetherthatnationoranynationsoconceivedandsodedicatedcanlongendurewearemetonagreatbattlefieldofthatwarwehavecometodedicateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthenationmightliveitisaltogetherfittingandproperthatweshoulddothisbutinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundthebravemenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorpowertoaddordetracttheworldwilllittlenotenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereitisforusthelivingrathertobededicatedheretotheunfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvanceditisratherforustobeherededicatedtothegreattaskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationundergodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearthfo
スペースやハイフン、カンマがなくて読みづらいですが、リンカーンの「ゲティスバーグ演説」でした。
参考