d.yoshimitsu

Posted on Mar 26, 2020

Elm(とHaskell)でシーザー暗号

#haskell #elm

なぜシーザー暗号

プログラミングHaskell 第2版を読んでたらシーザー暗号が出てきて、
昔々某社の中途採用試験のオンラインテストで全然できなかったのが思い出されたのでそのリベンジです。

シーザー暗号とは

Wikipedia読んでください。

シーザー暗号は単一換字式暗号の一種で、平文の各文字を、辞書順に3文字分シフトして暗号文を作る暗号である[4]。古代ローマの軍事的指導者ガイウス・ユリウス・カエサル(英語読みでシーザー)が使用したことから、この名称がついた[3]。文字のシフト数は固定であるが、3に限る必要はない。例えば左に3文字分シフトさせる場合、「D」は「A」に置き換わり、同様に「E」は「B」に置換される。

Haskellで書いてみる

Haskellの実装はプログラミングHaskell 第2版を引用させていただきました。 🙇

暗号化と復号

小文字を 0 から 25 の整数に変換する関数 let2int と、その逆関数 int2let を定義します。

let2int :: Char -> Int
let2int c = ord c - ord 'a'
int2let :: Int -> Char
int2let n = chr (ord 'a' + n)

この二つの関数を使うと、小文字をシフト数だけずらす関数 shift が定義できます。

shift :: Int -> Char -> Char
shift n c | isLower c = int2let ((let2int c + n) `mod` 26)
          | otherwise = c

関数 shift を使えば、与えられたシフト数で文字列を暗号化する関数が定義できます。

encode :: Int -> String -> String
encode n xs = [shift n x | x <- xs]

encode 3 "haskell is fun"
"kdvnhoo lv ixq"
encode (-3) "kdvnhoo lv ixq"
"haskell is fun"

文字の出現頻度表

26 文字の出現頻度表を定義します。

table :: [Float]
table = [8.1, 1.5, 2.8, 4.2, 12.7, 2.2, 2.0, 6.1, 7.0, 0.2, 0.8, 4.0, 2.4, 6.7, 7.5, 1.9, 0.1, 6.0, 6.3, 9.0, 2.8, 1.0, 2.4, 0.2, 2.0, 0.1]

百分率を計算して浮動小数点数として返す関数を定義します。

percent :: Int -> Int -> Float
percent n m = (fromIntegral n / fromIntegral m) * 100

lowers および関数 count は、それぞれ小文字あるいは指定した文字の個数を数える関数です。

lowers :: String -> Int
lowers xs = length [x | x <- xs, x >= 'a' && x <= 'z']

count :: Char -> String -> Int
count x xs = length [x' | x' <- xs, x == x']

任意の文字列に対して文字の出現頻度表を返す関数が定義できます。

freqs :: String -> [Float]
freqs xs = [percent (count x xs) n | x <- ['a'..'z']]
  where n = lowers xs

freqs "abbcccddddeeeee"
[6.666667, 13.333334, 20.0, 26.666668, ..., 0.0]

暗号解読

カイ二乗検定を使う。「計算された値が小さければ小さいほど二つのリストはよく似ている」ということらしい。

chisqr :: [Float] -> [Float] -> Float
chisqr os es = sum [((o-e)^2)/e | (o,e) <- zip os es]

リストの要素を n だけ左に回転させる関数を定義します。

rotate :: Int -> [a] -> [a]
rotate n xs = drop n xs ++ take n xs

目的とする値がリストのどの位置にあるかを調べて、その位置すべてをリストとして返す関数を定義します。

positions :: Eq a => a -> [a] -> [Int]
positions x xs = [i | (x',i) <- zip xs [0..], x == x']

暗号文に対する文字の出現頻度表を作り、その表を左に回転させながら、期待される文字の出現頻度表に対するカイ二乗検定の値を計算します。そして、算出されたカイ二乗検定の値のリストの中で最小の値の位置をシフト数とします。

crack :: String -> String
crack xs = encode (-factor) xs
  where
    factor = head (positions (minimum chitab) chitab)
    chitab = [chisqr (rotate n table') table | n <- [0..25]]
    table' = freqs xs

crack "kdvnhoo lv ixq"
"haskell is fun"
crack "vscd mywzboroxcsyxc kbo ecopev"
"list comprehensions are useful""

Elmで書いてみる

let2int : Char -> Int
let2int c =
    Char.toCode c - Char.toCode 'a'

ほぼHaskellですね。

int2let : Int -> Char
int2let n =
    Char.fromCode <| Char.toCode 'a' + n

Elmにはパイプライン演算子 ( <| ) があります。() のネストが深くならないので便利ですね。

shift : Int -> Char -> Char
shift n c =
    if Char.isLower c then
        int2let <| modBy 26 <| let2int c + n

    else
        c

Haskellは `` で関数を中置演算子にできるので便利ですね。Elmは愚直に書きましょう。これがElmの良さ。
これを書いてるときに気づいたんですが、パイプって難しいですね。右にも左にも流せるので、どういう時にどっち向きに書くのかルールを決めておかないと大変なことになりそうです。（このパイプの向き問題だけで、もうひとつアドベントカレンダーが書けそうな気がするので気力があれば...）
modByの引数を勘違いしてハマりました。n % 2 は modBy 2 n です、感覚的にはmodBy n 2なのに何でだよ！とSlackに書いたら、カリー化できるからと教えてもらいました。膝を打ちすぎて膝が壊れるかと思いました。
Haskellのガード式は雰囲気的にパターンマッチかなと思いパターンマッチで書いたら、同僚にBooleanを返すんだからifで書けと言われました。（if(true == true) true みたいで面白かったのに...）

encode : Int -> String -> String
encode n xs =
    String.fromList <| List.map (shift n) <| String.toList xs

ElmのStringはCharの配列ではないので変換しましょう。
Haskellは[]でmapが書けるので便利ですね。Elmは愚直に書きましょう。これがElmの良さ。

table : List Float
table =
    [ 8.1, 1.5, 2.8, 4.2, 12.7, 2.2, 2.0, 6.1, 7.0, 0.2, 0.8, 4.0, 2.4, 6.7, 7.5, 1.9, 0.1, 6.0, 6.3, 9.0, 2.8, 1.0, 2.4, 0.2, 2.0, 0.1 ]

ほぼHaskell(ry

percent : Int -> Int -> Float
percent n m =
    toFloat n / toFloat m * 100

ほぼ(ry

lowers : String -> Int
lowers xs =
    List.length <| List.filter (\n -> n >= 'a' && n <= 'z') <| String.toList xs

Haskellは[]でfilterMapと同じことができるので便利ですね。Elmは愚直に書きましょう。これがElmの良さ。（Haskellのほうが書いてて気持ちよかったのは内緒）

count : Char -> String -> Int
count c xs =
    String.length <| String.filter ((==) c) xs

ElmはStringにfilterがあって便利ですね。

lowerAlphabets : List Char
lowerAlphabets =
    List.map (\n -> Char.fromCode n) <| List.range (Char.toCode 'a') (Char.toCode 'z')


freqs : String -> List Float
freqs xs =
    let
        n =
            lowers xs
    in
    List.map (\x -> percent (count x xs) n) lowerAlphabets

List.range は、Intしか取らないので Char.toCode するか、 "abcdefghijklmnopqrstuvwxyz" を定義しましょう。

chisqr : List Float -> List Float -> Float
chisqr os es =
    List.sum <| List.map2 (\o e -> ((o - e) ^ 2) / e) os es

Elmにはzipが無いので、２つの配列をタプルにしたければ List.map2 Tuple.pair os es とします。ただし、今回の場合はタプルを作る必要はありません。

rotate : Int -> List a -> List a
rotate n xs =
    List.drop n xs ++ List.take n xs

positions : a -> List a -> List Int
positions y xs =
    List.filterMap
        (\( i, x ) ->
            if y == x then
                Just i

            else
                Nothing
        )
    <|
        List.indexedMap Tuple.pair xs

Elmは全ての型が比較可能なので、 Eq は不要です。
Elmの indexedMap 便利ですね。
Elmに無限配列はないらしい。
filterMap は、Maybeを受け取りNothingを除外します。

crack : String -> String
crack xs =
    let
        factor =
            List.head <| positions (Maybe.withDefault 0.0 <| List.minimum chitab) chitab

        chitab =
            List.map (\n -> chisqr (rotate n table2) table) <| List.range 0 25

        table2 =
            freqs xs
    in
    encode -(Maybe.withDefault 0 factor) xs

List.minimum と List.head はListが空だった場合、Nothingを返すため戻り値の型はMaybeです。 Haskellは例外が起きます。Elmのこういうところとても良いですね。

感想

新しい言語を学ぶというのはいいですね。
Elmは言語仕様がシンプルなので、公式ドキュメントを読めばなんとなくどうやれば実現できるのかわかるのが非常に良いですね。
普段はScalaを書いてるので、HaskellとElmは難しいなと思いました。関数を書く時って、関数の名前と、引数と戻り値の型を決めてから実装を書き始めると思うんですが（私はそう）、そうすると、ちょっと難しいことをやろうとするとコンパイルが通らない時間が長くてちょっと疲れちゃいます。 Scalaなら???でいいし、何なら手続きしまくって取り敢えず動かすができちゃうので楽（？逃げ？）ができて好きです。
- 同僚に Debug.todo があると教えてくれた。Elmがまた好きになりました。