[암호학] 카이사르 암호와 빈도 분석

암호는 생각보다 오래전부터 사용되어 왔습니다.
 
거의 모든 암호학 수업에서 반드시 언급하는 고대암호가 있습니다. 바로 카이사르 암호입니다.
 
카이사르 암호는 기원전 로마의 율리우스 카이사르라는 인물이 사용했던 암호입니다.
 
사실 카이사르 암호 자체가 그렇게 어려운 암호는 아닙니다.
 
오히려 너무 여러 군데서 잘 설명해 놔서 따로 설명하는 게 미안할 정도입니다. Wiki의 그림을 보시면 진짜 별거 아니라는 생각이 드실 겁니다.
 
위키를 보고 오셨다는 가정하에 간단하게 다시 설명하자면
카이사르 암호는 간단한 치환 암호로, 알파벳을 일정한 거리만큼 옮겨서 암호화합니다. 예를 들어, "A"를 1만큼 옮겨서 "B"로 바꾸는 식입니다.

카이사르 암호 - 위키백과, 우리 모두의 백과사전

카이사르는 암살당해 죽게 됩니다. 하지만 암살당하기 전에 가족들이 카이사르 암호를 이용하여 메시지를 하나 보냈었습니다. 바로 EH FDUHIXO IRU DVVDVVLQDWRU입니다.
 
이 암호문의 뜻은 BE CAREFUL FOR ASSASSINATOR(암살자를 조심하라)로 A는 D로, B는 E로 각각의 알파벳을 3개씩 밀려 쓴 것입니다.
 
만약 A가 D로 대응된다면 이렇게 암호화 표를 하나 만들 수 있습니다.
원래 알파벳:       ABCDEFGHIJKLMNOPQRSTUVWXYZ
암호화된 알파벳: DEFGHIJKLMNOPQRSTUVWXYZABC
 

---

용어 정리

평문(Plaintext): BE CAREFUL FOR ASSASSINATOR (암살자를 조심하라)
암호문(Ciphertext): EH FDUHIXO IRU DVVDVVLQDWRU
키(Key): 3
 
여기서 키(Key)라는 용어가 나왔습니다. 앞에서 뭐라고 설명했었죠? 금고의 키(열쇠) 같은 역할을 한다고 말했습니다. 금고를 열고 안의 내용물을 가져가기 위해 키(열쇠)가 필요한 것 처럼 평문을 암호문으로, 암호문을 평문으로 되돌리려면 꼭 필요한 값이 키(Key)입니다.
 
카이사르 암호에서 키(Key)가 3이라는 것은 예를 들어, 알파벳 "A"를 3만큼 미뤄 "D"에 대응시켰다는 의미입니다.
원래 알파벳:       ABCDEFGHIJKLMNOPQRSTUVWXYZ
암호화된 알파벳: DEFGHIJKLMNOPQRSTUVWXYZABC
 
A ~ Z까지 알파벳의 개수가 26개라서  카이사르 암호에서 키(Key) 값의 후보는 0 ~ 25로 26가지가 있습니다.   
예를 들어, A는 A ~ Z까지로 26가지 대응 방법이 존재합니다.
 
여기서 카이사르 암호의 키(Key) 공간의 크기를 26이라고도 합니다.
 
키 공간은 특정 암호에서 사용할 수 있는 모든 키 후보들의 집합을 의미하고, 전체 키 후보들의 개수를 키 공간의 크기라고 부릅니다.
 
이렇게 키 공간의 크기가 작은 암호는 무차별 대입공격(bruce force attack)으로 금방 풀 수 있습니다.

따라서 암호에서는 키 공간의 크기가 매우 매우 중요합니다.
 
아래는 Python 예제 코드입니다. 키 공간의 크기가 26이라 평문 복원하는데 1초도 안걸립니다.

def caesar_decrypt(ciphertext, key):
    plaintext = ""
    for char in ciphertext:
        if char.isalpha():
            ascii_offset = 65 if char.isupper() else 97
            decrypted_char = chr((ord(char) - ascii_offset - key) % 26 + ascii_offset)
            plaintext += decrypted_char
        else:
            plaintext += char
    return plaintext

def brute_force_caesar(ciphertext):
    for key in range(26):
        decrypted_text = caesar_decrypt(ciphertext, key)
        print(f"Key {key}: {decrypted_text}")

# 예시: 암호문을 모든 Key 값 후보에 따라 복호화
ciphertext = "RUSQHUVKBVEHQIIQIYDQJEH"
brute_force_caesar(ciphertext)

 
그런데 점점 현대로 오면 지금은 쓰이지 않아도 여러분의 머리로 풀기에 굉장히 머리 아픈 암호들도 많습니다.
Hill cipher만 해도 연필과 종이만 주고 무차별 대입공격(bruce force attack)으로 키(Key) 값(행렬)을 찾아보라고 하면 쉽게 찾을 수 있을 것 같지 않습니다. Hill cipher는 그냥 이런 암호도 있었구나 하고 넘어가시면 됩니다.

Hill cipher - Wikipedia

 
그렇다면 심지어 컴퓨터도 없던 옛날에는 어떻게 암호를 해독하기 위해 노력했을까요?
대표적으로 빈도분석이 있습니다.
영어의 일반적인 문장의 경우, 알파벳 수를 세어 픽토그램을 작성하면(표 참조), 대개 e, t, a, o, i, n, …, j, x, q, z의 순으로 출현하는 것을 알 수 있다. - Wiki
참고로 한글에서는 ㅇ, ㅣ이 약 10% 정도로 빈도가 높습니다.

알파벳 빈도 표

Reference

빈도분석 (암호) - 위키백과, 우리 모두의 백과사전

 
아까 여러분이 마스터하신 카이사르 암호를 예시로 보겠습니다.
암호문 EH FDUHIXO IRU DVVDVVLQDWRU가 평문으로 무슨 뜻이었는지 기억하시나요? 기억 못 하셔도 좋습니다.
 
우선 암호문에서 제일 많이 출연하는 알파벳이 무엇일까요? 바로 D와 V로 총 4번 나옵니다. 이제 알파벳 빈도 표를 보시죠!
 
솔직히 D, V가 어떤 알파벳에 대응될지 후보가 확 줄어드는 것이 느껴지시나요?? 정상적인 문장이라면 D, V가  X, Z, J 이렇게 3 개중 하나로 대응될 가능성은 매우 낮아 보입니다. 빈도표에 의하면 적어도 E, A, T 중에 하나는 매칭되는게 있다고 생각할 수 있습니다.
 
실제로 D는 평문에서 A를 대체하는 문자임을 알 수 있습니다. 
 
암호화된 알파벳: DEFGHIJKLMNOPQRSTUVWXYZABC
원래 알파벳:        ABCDEFGHIJKLMNOPQRSTUVWXYZ


이런 통계적인 분석법을 실제 암호 분석에서도 많이 사용됩니다.
 
현대 암호들은 빈도 분석으로 쉽게 해킹할 수없으니 안심하셔도 좋습니다.
하지만 사람도 그렇듯 모든 것이 완벽한 암호는 없다는 점을 기억해 주세요🍀
 
영화 이미테이션 게임의 타노스급 빌런 에니그마가 현대에는 사용되지 않는 것은 다 이유가 있습니다.