Brain072. 다중 치환 암호 (Poly-alphabetic Substitution)
⚠️ 이 문서는 "E는 무조건 Q로 바뀐다"는 단일 치환 암호의 맹점을 깨부수고, 똑같은 평문 글자라도 위치와 암호 키워드에 따라 매번 다르게 변환되도록 고안하여 빈도 분석법을 300년 동안 무력화시킨 천재적 발명, 비제네르(Vigenère) 암호를 다룹니다.
핵심 인사이트 (3줄 요약)
- 본질: 다중 치환 암호(Poly-alphabetic)는 26개의 서로 다른 카이사르 암호 원반(표)을 겹쳐놓고, 사용자가 지정한 '키워드(Keyword)'의 알파벳 순서에 따라 암호 표를 매 글자마다 번갈아 가며 사용하는 동적 치환 암호다.
- 가치: 평문의 'A'라는 똑같은 글자가 나와도, 첫 번째 'A'는 'K'로, 두 번째 'A'는 'Z'로 변환된다. 즉, 평문의 언어적 특성(알파벳 빈도수)이 암호문에 전혀 나타나지 않게 뭉개버려, 해커의 무기인 '빈도 분석법'을 완벽하게 파괴했다.
- 한계: 비제네르 암호는 16세기 발명 후 "절대 풀 수 없는 암호(Le Chiffre Indéchiffrable)"로 칭송받았으나, 19세기에 반복되는 키워드의 길이(주기)를 찾아내어 단일 치환 암호 여러 개로 쪼개버리는 찰스 배비지와 카시스키 테스트에 의해 결국 몰락했다.
Ⅰ. 개요 및 탄생 배경 (Context & Necessity)
카이사르 암호나 무작위 단일 치환 암호는 언어가 가진 태생적 습관(E가 제일 많이 나온다) 때문에 알킨디의 '빈도 분석법'에 의해 종이조각이 되었다.
16세기 프랑스의 외교관 **블레즈 드 비제네르(Blaise de Vigenère)**는 이 문제를 근본적으로 해결할 아이디어를 완성했다. "도둑이 빈도수를 세지 못하게, 같은 글자라도 그때그때 다른 가면을 씌우면 되지 않을까?" 그는 카이사르 암호의 밀어내기 규칙 26가지를 모두 합쳐 거대한 26x26 바둑판(비제네르 방진)을 만들었고, 수신자와 송신자가 나눠 가진 **비밀 단어(Keyword)**에 맞춰 가면을 계속 바꿔가며 암호화하는 방식을 고안했다.
📢 섹션 요약 비유: 단일 치환 암호가 1반 선생님 한 명이 반 학생 전원의 이름을 바꿔 부르는 것이라면, 다중 치환 암호는 26명의 선생님이 번갈아 가며 들어와서 학생 이름을 계속 다르게 부르는 것입니다. 도둑은 누가 누군지 패턴을 잡을 수가 없어 미쳐버립니다.
Ⅱ. 비제네르 암호의 동작 원리 (비제네르 방진)
비제네르 암호는 **평문(Plaintext)**과 반복되는 **키워드(Keyword)**를 교차시켜 암호문을 생성한다.
- 준비물: 비제네르 방진 (가로축은 평문, 세로축은 키워드 알파벳을 나타내는 26x26 알파벳 표)
- 예시 시나리오:
- 평문:
ATTACK(공격하라) - 키워드:
KEY - 암호화 준비: 키워드
KEY를 평문의 길이에 맞춰 반복해서 아래에 적는다.
- 평문:
┌─────────────────────────────────────────────────────────────────┐
│ 비제네르 암호(다중 치환)의 동적 맵핑 메커니즘 시각화 │
├─────────────────────────────────────────────────────────────────┤
│ │
│ [ 암호화 세팅 ] │
│ 평문 (Plain) : A T T A C K │
│ 키워드 (Key) : K E Y K E Y (반복) │
│ │
│ [ 비제네르 방진을 통한 1:1 교차 변환 ] │
│ 1번 글자: 평문 A 와 키워드 K 가 방진에서 만나는 곳 ─▶ K │
│ 2번 글자: 평문 T 와 키워드 E 가 방진에서 만나는 곳 ─▶ X │
│ 3번 글자: 평문 T 와 키워드 Y 가 방진에서 만나는 곳 ─▶ R │
│ │
│ ★ 주목! 똑같은 평문 'T' 지만: │
│ 두 번째 'T'는 'X'로 암호화되었고, │
│ 세 번째 'T'는 'R'로 다르게 암호화되었다! │
│ │
│ 암호문(Cipher): K X R K G I │
└─────────────────────────────────────────────────────────────────┘
[다이어그램 해설] 이 원리가 빈도 분석을 박살 낸 핵심이다. 암호문에 'K'가 두 번이나 나왔다고 해서 평문의 빈도가 높은 'E'라고 유추할 수 없다. 첫 번째 K는 평문 A에서 왔지만, 네 번째 K는 키워드 K의 영향을 받아 평문 A에서 온 것이기 때문이다(우연의 일치). 이처럼 '1글자 대 多문자' 치환이 이루어지면서 통계적 패턴은 완벽하게 평탄화된다.
- 📢 섹션 요약 비유: 페인트 붓(평문)을 도화지에 칠할 때, 단일 암호는 빨간색 필터(키) 1개만 써서 무조건 빨갛게 칠합니다. 하지만 다중 암호는 빨강, 파랑, 노랑 셀로판지(키워드 K, E, Y)를 1초마다 바꿔 끼며 색을 칠하기 때문에, 완성된 그림은 온통 섞인 색으로 도배되어 원래 무슨 색 붓이었는지 절대 알 수 없게 됩니다.
Ⅲ. 난공불락의 붕괴: 카시스키 검사 (Kasiski Examination)
비제네르 암호는 약 300년 동안 해독 불가 암호로 군림했으나, 1863년 프리드리히 카시스키(실제로는 찰스 배비지가 먼저 발견)에 의해 허무하게 뚫렸다.
그가 찾아낸 치명적인 약점은 바로 **"키워드(예: KEY)가 일정한 주기(3칸)로 계속 반복된다"**는 것이었다.
- 카시스키의 통찰:
- 암호문을 길게 뽑다 보면, 우연히 똑같은 글자 덩어리(예:
KXR)가 반복해서 나오는 패턴이 발견된다. - 이 덩어리들이 나타난 위치의 간격을 잰다 (예: 9칸 떨어져 있음).
- 9의 약수는 3이므로, 카시스키는 "아하! 이 암호의 키워드는 3글자짜리 단어(예: KEY, DOG 등)구나!"라고 주기를 알아챈다.
- 암호문을 길게 뽑다 보면, 우연히 똑같은 글자 덩어리(예:
- 다중 암호를 단일 암호로 쪼개기:
- 주기가 3임을 알았으니, 암호문의 1번째, 4번째, 7번째 글자들만 모아 뽑아낸다. 이 글자들은 모두 첫 번째 키워드 'K' 하나에 의해서만 암호화된 것이다.
- 즉, 이 글자들만 모아놓으면 동일한 규칙의 '단일 치환 암호'로 둔갑한다!
- 이제 해커는 뽑아낸 글자들에 과거의 구식 무기인 '빈도 분석법'을 써서 손쉽게 키를 해독해 버린다.
Ⅳ. 결론
"완벽을 깨뜨린 것은 암호의 규칙이 아니라, 인간이 만든 '주기성(반복)'이었다." 다중 치환 암호(비제네르 암호)는 단 하나의 치환표를 벗어나, 다수의 치환표를 동적으로 스와핑하는 시대를 열어 현대 암호(혼돈과 확산의 다중 라운드)의 철학적 기반을 닦았다. 비록 반복되는 키워드라는 멍청한 약점 때문에 깨졌지만, 이 약점을 없애기 위해 **"키워드를 평문만큼 무한히 길게 만들고 절대 반복하지 말자"**는 궁극의 아이디어인 **'일회용 패드(One-Time Pad)'**로 인류를 이끄는 징검다리 역할을 훌륭히 수행했다.
📌 관련 개념 맵
- 분류: 치환 암호 $\rightarrow$ 다중 치환 암호 (Poly-alphabetic Substitution)
- 대표 구현체: 비제네르 방진 (Vigenère Square)
- 파해법 (취약점): 카시스키 테스트 (주기 분석 후 빈도 분석 적용)
- 후속 진화: 일회용 패드 (One-Time Pad, 주기가 없는 무한 키)
👶 어린이를 위한 3줄 비유 설명
- 단일 암호는 내 얼굴에 '호랑이 가면' 딱 하나만 쓰고 돌아다니는 거라, 걸음걸이만 보면 누군지 다 들켰어요.
- 비제네르 암호는 1분마다 호랑이, 토끼, 독수리 가면을 번갈아 가며 계속 바꿔 쓰는 마법이에요! 경찰이 도저히 통계(버릇)를 잡을 수 없어 300년 동안 아무도 못 잡았죠.
- 하지만 아주 똑똑한 경찰이 "가면을 호-토-독, 호-토-독 순서로 3분에 한 번씩 똑같이 반복해서 쓰네?"라는 비밀(주기성)을 알아채고, 호랑이 가면 쓴 시간만 다 모아서 조사해 결국 정체를 밝혀냈답니다!