5장 5절 카이사르 암호

박준규·2023년 3월 3일

Programming in Haskell 의역

목록 보기

2/3

카이사르 암호는 알파벳 문자를 세 칸 뒤에 있는 문자로 바꾸는 방식이다. 예를 들어 알파벳 a를 d로 바꾸면 된다. z처럼 뒤에 더 글자가 없을 때는 다시 a로 돌아간다.

haskell is fun

위 문장을 카이사르 방식으로 암호화하면 아래 문장이 된다.

kdvnhoo lv ixq

꼭 세 칸일 필요는 없고 1과 25 사이의 정수이면 된다. 예를 들어 세 칸이 아니라 열 칸 뒤의 문자로 한다면 아래와 같은 문자열이 된다.

rkcuovv sc pex

하스켈로 카이사르 암호를 만드는 방법을 알아보자.

암호화와 복호화

여기서는 소문자만 바꾸고 대문자나 구두점 같은 글자는 바꾸지 않기로 한다. a부터 z까지에 해당하는 문자를 0부터 25 사이의 숫자로 바꾸는 함수 let2int와 그 반대로 바꾸는 함수 int2let을 아래와 같이 구현할 수 있다.

let2int :: Char -> Int
let2int c = ord c - ord 'a'

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

라이브러리 함수인 ord :: Char -> Int와 chr :: Int -> Char는 문자와 유니코드를 서로 바꿔준다.

ghci> let2int 'a'
0

ghci> int2let 0
'a'

위 두 함수를 이용해서 몇 칸을 옮길 건지 정할 숫자와 소문자를 인자로 받아서 그에 해당하는 카이사르 글자를 리턴하는 함수 shift를 아래와 같이 정의할 수 있다. int2let에 넣을 인자는 26으로 나눈 나머지로 해야 25보다 큰 수를 다룰 수 있다.

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

이 함수는 첫 번째 인자로 0보다 작은 수를 받을 수도 있고 두 번째 인자가 소문자일 때만 바뀐다.

ghci> shift 3 'a'
'd'

ghci> shift 3 'z'
'c'

ghci> shift (-3) 'c'
'z'

ghci> shift 3 ' '
' '

아래와 같이 리스트 컴프리헨션을 이용하면 문자열 전체를 쉽게 암호화할 수 있다.

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

함수 shift의 첫 번째 인자로 음수를 넣으면 따로 함수를 만들지 않아도 복호화를 할 수 있다.

ghci> encode 3 "haskell is fun"
"kdvnhoo lv ixq"

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

알파벳 빈도표

많은 영어 문장을 관찰하면 특정 문자가 다른 문자보다 더 자주 나오는데 이걸 이용하면 카이사르 암호를 깰 수 있다.

table :: [Float]
table = [ 8.2, 1.5, 2.8, 4.3, 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.1, 2.8, 1.0, 2.4, 0.2, 2.0, 0.1 ]

예를 들어 알파벳 e는 12.7%로 빈도수가 제일 높다. 반면에 q나 z는 0.1%로 빈도수가 낮다. 아래와 같이 함수 percent를 정의할 수 있다.

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

함수 percent와 앞 절에서 소개한 함수 lowers와 count를 이용하면 입력한 문자열의 알파벳 빈도수 테이블을 리턴하는 함수 freqs를 만들 수 있다.

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

ghci> freqs "abbcccddddeeeee"
[6.7,13.3,20.0,26.7,33.3,0.0,0.0,...,0.0]

여기서 알파벳 a의 빈도수는 6.7%이고 b는 13.3%인 식이다.

암호 깨기

두 빈도수 리스트를 비교하는 방법 중에 카이제곱(chi-square)이라는 것이 있다. 아래 식에서 $n$ 은 두 리스트의 길이를 나타내고 $xs_i$ 는 리스트 $xs$ 의 $i$ 번째 원소를 나타낸다.

$\sum\limits_{i=0}^{n-1} = \frac{(os_i-es_i)^2}{es_i}$

위 식의 결과가 작을 수록 두 빈도수 리스트가 일치할 확률이 높다고 해석할 수 있다. 함수 zip과 리스트 컴프리헨션을 이용하면 위 식을 아래처럼 구현할 수 있다.

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

문자열을 n만큼 왼쪽으로 미는 함수 rotate를 아래처럼 구현할 수 있다. 밀린 글자들은 오른쪽에 다시 붙인다. n에는 0과 문자열 길이 사이의 수만 입력된다고 가정한다.

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

ghci> rotate 3 [1,2,3,4,5]
[4,5,1,2,3]

카이사르 방식으로 암호화된 문자열은 있는데 몇 칸만큼 밀었는지 알 수는 없을 때 모든 경우의 수에 대해서 카이제곱한 결과 중 가장 작은 수를 고르면 암호를 깰 수 있다.

table' = freqs "kdvnhoo lv ixq"

ghci> [chisqr (rotate n table') table | n <- [0..25]]
[1408.8,640.3,612.4,202.6,1439.8,4247.2,651.3,...,626.7]

결과 중 가장 작은 값은 202.6이고 세 번째 값이므로 카이사르 암호화 할 때 세 칸 밀었음을 알 수 있다.

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

ghci> crack "kdvnhoo lv ixq"
"haskell is fun"

ghci> crack "vscd mywzboroxcsyxc kbo ecopev"
"list comprehensions are useful"

주어진 문자열이 너무 짧거나 빈도수가 일반적이지 않으면 이 방법으로 암호를 깰 수 없다.

ghci> crack (encode 3 "haskell")
"piasmtt"

ghci> crack (encode 3 "boxing wizards jump quickly")
"wjsdib rduvmyn ephk lpdxfgt"

참고

박준규

코딩하는 물총새

이전 포스트

5장 리스트 컴프리헨션

다음 포스트