シーザー暗号

date:2012/11/30

1. 概要

  1. 実際にモジュールを使ってみる
  2. シーザー暗号のエンコード用の関数を作る
  3. 解読を頻度分析でやってみる

2. シーザー暗号

シーザー暗号は、いわゆる単一換字式の暗号です。
つまり、元々の文で1文字だったものが、暗号化の後にも1文字になり、文字置き換えのルールは文脈に依りません。
(ある’a’が’e’に置き換えられているなら、文章中のどこにあっても、’a’は’e’に置き換えられているということ。特に隣の文字や、出現回数に依存しません。)

Note

このページでは、文字は小文字のアルファベットのみであるとして考えています。
また、a, b, c, ..., x, y, z の順に順序が入っていて、さらに z の次は再び a であることにします。
シーザー暗号の文字の置き換えのルールは、”何文字ずらすか” で決まります。
例えば、 2文字ずらすシーザー暗号を考えれば、 ‘a’->’c’, ‘b’->’d’, ‘c’->’e’, ..., ‘x’->’z’, ‘y’->’a’, ‘z’->’b’ というようになります。
シーザー暗号は非常に単純な暗号で、復号するのも、 ずらした分を逆側にずらせばよいです。先ほどの例なら、2文字戻せば復号できることになります。

3. 解読について

よく知られているように、暗号の解読の手法として”頻度分析”というものがあります。
統計的によく使う文字とあまり使わない文字があり、それをヒントに解読をするというものです。
英文の場合、e, t などは非常によく使われています。
例えば、暗号文に ‘g’ が多かったとすると、’e’ -> ‘g’ という置き換えの結果だと仮定して、2文字ずらすシーザー暗号で暗号化されたと仮定して、復号してみるのがよいでしょう。
これは、統計的な出現頻度のみを手がかりにしているので、あまりうまくいかないこともあるかもしれません。
特に短文ではうまくいかない場合が多いと思います。

4. まとめ

途中にコードを書くと長くなってしまうので、先にまとめをしておきます。
まず、シーザー暗号では、鍵長(何文字ずらすか)が非常に制限されており、文字集合とその順序を固定した場合、短文では総当たりが可能です。
そして、たとえ総当たりできないほどの長文になったとすると、今度は、先ほどのような頻度分析の結果から復号される危険性があります。
例えば、文章中の位置に依存した置き換えを行うなどすれば頻度分析も困難になると思います。
(もう少し現代的な暗号について知りたいところ...)

5. コード

以下、Haskell のコードを貼り付けています。
今回は、 Haskell でしか書いていません。
ここでは、スペースやコンマといった、小文字のアルファベット以外は無視しています。
import qualified Data.Char as Char

-- 小文字を小文字のまま文字をずらす
chr2int :: Char -> Int
chr2int c = Char.ord c - Char.ord 'a'
int2chr :: Int -> Char
int2chr n = Char.chr (Char.ord 'a' + n)
shift :: Int -> Char -> Char
shift n c
  | Char.isLower c = int2chr $ (chr2int (Char.toLower c) + n) `mod` 26
  | otherwise = c
-- 単語をずらす
wordShift :: Int -> String -> String
wordShift n str = map (shift n) str

--
-- Define : シーザー暗号
--
-- encode and decode
encode :: Int -> String -> String
encode n xs = unwords $ map (wordShift n) (words xs)
decode n xs = encode (negate n) xs

--
-- Cracking : 頻度分析
--
isKey :: (Eq a) => a -> [(a,b)] -> Bool
isKey x xs = any (\(k,v) -> (x==k)) xs
-- 各文字が使われている回数の調査
freq :: String -> [(Char,Int)]
freq xs = foldr groupTapple [] xs
          where groupTapple x ys = if isKey x ys then map (\(x,v) -> (x,v+1)) ys else (x,1):ys
-- 各文字が使われている頻度の調査
percent :: String -> [(Char,Float)]
percent xs = map (\(k,v) -> (k, 100 * fromIntegral(v) / fromIntegral(length(xs)) )) (freq xs)
-- 各文字が使われる頻度の統計
-- From : http://www.codeproject.com/Articles/10519/Crack-the-Modified-Caesar-Cipher-with-Relative-Fre
statPercent :: [(Char,Float)]
statPercent = [('a',6.63),('b',1.2),('c',2.27),('d',3.45),('e',10.3),('f',1.92),('g',1.44),('h',4.82),('i',5.79),('j', 0.067),('k',0.55),('l',3.24),('m',1.99),('n',5.75),('o',6.01),('p',1.54),('q',0.09),('r',4.57),('s',5.4),('t',7.84),('u',2.47),('v',0.75),('w',1.92),('x',0.15),('y',1.27),('z',0.056)]
-- 評価関数
evaluate :: [(Char,Float)] -> [(Char,Float)] -> Float
evaluate decrypt stat = sum [ ((c - s) ** 2.0) / s | (k,c) <- decrypt, (t,s) <- stat,k == t ]
-- Crack
decrypt :: String -> String
decrypt crypt = decode (shift) crypt
                where
                  shift = head $ minPosition rotationDecryptTest
                  rotationDecryptTest = [ evaluate (percent (decode n crypt)) statPercent | n <- [0..length(statPercent)] ]
                  minPosition xs = [ n | (n,x) <- zip [0..length(statPercent)] xs, x == minimum xs]

--
-- 実際に確認
--
-- London Bridge
string1 = map Char.toLower $ filter (`elem` (['a'..'z'] ++ ['A'..'Z'])) "London Bridge is broken down,\nBroken down, broken down.\nLondon Bridge is broken down,\nMy fair lady.\n\nBuild it up with wood and clay,\nWood and clay, wood and clay,\nBuild it up with wood and clay,\nMy fair lady.\n\nWood and clay will wash away,\nWash away, wash away,\nWood and clay will wash away,\nMy fair lady.\n\nBuild it up with bricks and mortar,\nBricks and mortar, bricks and mortar,\nBuild it up with bricks and mortar,\nMy fair lady.\n\nBricks and mortar will not stay,\nWill not stay, will not stay,\nBricks and mortar will not stay,\nMy fair lady.\n\nBuild it up with iron and steel,\nIron and steel, iron and steel,\nBuild it up with iron and steel,\nMy fair lady.\n\nIron and steel will bend and bow,\nBend and bow, bend and bow,\nIron and steel will bend and bow,\nMy fair lady.\n\nBuild it up with silver and gold,\nSilver and gold, silver and gold,\nBuild it up with silver and gold,\nMy fair lady.\n\nSilver and gold will be stolen away,\nStolen away, stolen away,\nSilver and gold will be stolen away,\nMy fair lady.\n\nSet a man to watch all night,\nWatch all night, watch all night,\nSet a man to watch all night,\nMy fair lady.\n\nSuppose the man should fall asleep,\nFall asleep, fall asleep,\nSuppose the man should fall asleep?\nMy fair lady.\n\nGive him a pipe to smoke all night,\nSmoke all night, smoke all night,\nGive him a pipe to smoke all night,\nMy fair lady"
-- From Gentoo Wiki(http://www.gentoo.org/proj/en/qa/pms.xml)
string2 = map Char.toLower $ filter (`elem` (['a'..'z'] ++ ['A'..'Z'])) "\n\nIn the past,the ebuild environment has been defined by what Portage has supported. With the advent of alternative package managers,such a moving standard is no longer sufficient. The Package Manager Specification (PMS) aims to solve this by defining,independent of any package manager,what is and is not allowed in the tree,and what ebuilds may assume about their environment.\n\nIt is also required to document what each value of the EAPI ebuild variable actually means. At present PMS aims to document all Council - approved EAPIs.\n\nA git repository with the document's sources can be found at http://git.overlays.gentoo.org/gitweb/?p = proj/pms.git;a = summary. A convenient way to be up to date with the current document is the live ebuild found in the Gentoo repository,called app - doc/pms (TeX Live needs to be installed). Additionally the approved versions are available as ebuilds of that package,too and will install a normal PDF file only. "
-- テスト : true が返れば正しくクラックできることがわかる
test :: String -> Bool
test str = str == (decrypt str)