読者です 読者をやめる 読者になる 読者になる

0x90

一回休み

SECCON 2016 ヴィジュネル暗号をHaskellで解いてみる

昨日のSECCONのヴィジュネル暗号、Haskellで書いてみようかとも思ったんだけど、どう考えてもPythonのほうが慣れているので本番ではPythonで書いてしまった。 でもやっぱせっかくなのでHaskellで書いてみました。下手の横好きレベルですけどやっぱHaskellは楽しいなあ

import Data.List
import Data.Digest.Pure.MD5
import Data.ByteString.Lazy.Char8 (pack)

toMD5String :: String -> String
toMD5String = show . md5 . pack

decode :: [Char] -> Char -> Char -> Char
decode keys k e = v
  where
    newkeys = (dropWhile (/= k) keys) ++ keys
    (_, v) = head $ dropWhile ((/= e) . fst) $ zip newkeys keys

check :: [Char] -> [Char] -> [[Char]] -> [Char] -> [Char] -> [Char]
check hash keys (restKey:restKeys) firstKey after
  | toMD5String decoded == hash = decoded
  | otherwise                   = check hash keys restKeys firstKey after
    where
      decoded = map (uncurry $ decode keys) $ zip (cycle key) after
      key = firstKey ++ restKey

main :: IO()
main = putStrLn $ check hashed keys possibleKeys firstKey after
  where
    keys = "ABCDEFGHIJKLMNOPQRSTUVWXYZ{}"
    after = "LMIG}RPEDOEEWKJIQIWKJWMNDTSR}TFVUFWYOCBAJBQ"
    hashed = "f528a6ab914c1ecf856a1d93103948fe"
    init = "SECCON{"
    len = length "????????????"
    firstKey = map (uncurry $ decode keys) $ zip init after
    restLen = len - length firstKey
    possibleKeys = sequence $ replicate reasLen keys

知らなかったところ

与えられたListの無限の繰り返しを返す関数([a] -> [a])

cycle :: [a] -> [a]

Listの積(それぞれのリストから任意の要素を取ってきたものの繰り返し)

itertools.productのequivalentが欲しかった。

これを理解するには、MonadとしてのListを理解する必要があるっぽいです。まずsequenceの定義は

sequence :: Monad m => [m a] -> m [a]

で、MonadのListを取ってそれぞれのMonadから「中身を取り出し(=bind)」てListを作り、そのMonadを返す関数です。(関係ないですが、haskellってこういう短い関数の場合定義を見ると内容が明らかなのがいいですよね。だからhoogleも型で検索できるんでしょう)

ここで、sequenceにList MonadのListを与えてみましょう。すると、返すのはList Monadの中身のListのList Monadです。では、List Monadの中身を取り出すという作業は何でしょうか?

a :: [(Int, Int)]
a = do
  i <- [1, 2, 3, 4]
  j <- [4, 5]
  return $ (i * 2, j)
Prelude> :l test.hs 
[1 of 1] Compiling Main             ( test.hs, interpreted )
Ok, modules loaded: Main.
*Main> a
[(2,4),(2,5),(4,4),(4,5),(6,4),(6,5),(8,4),(8,5)]

これを見ればわかるように、List Monadの中身を取り出すということは、Listの中身のそれぞれを取り出すということにほかなりません。したがって、ListのListにsequenceを作用させると、それぞれのListから1要素ずつ持ってきたもののListを返すことになります。