ADFGVX와 분할화

1918년이 되자 독일군은 심각한 문제에 직면했습니다. 연합국의 암호 분석가들이 독일군의 야전 암호를 새 암호로 교체하는 속도보다 더 빠르게 해독하고 있었습니다. 1918년 춘계 공세를 위해서는 더 새롭고 강력한 암호가 긴급히 필요했습니다.

프리츠 네벨 대령은 군사 암호학에서 이전에는 시도된 적이 없는 방식으로 두 가지 고전적 기법을 결합한 ADFGVX 암호를 개발했습니다.

이 암호의 이름은 암호문에 사용되는 여섯 문자 A, D, F, G, V, X에서 유래했습니다. 이 문자들은 모스 부호 표현이 서로 매우 다르기 때문에 의도적으로 선택되었습니다.

덕분에 야전 무선 통신에서 전송 오류를 최소화할 수 있었습니다. 한 문자를 다른 문자로 잘못 알아보면 전체 메시지가 손상될 수 있었으므로, 설계자들은 모스 부호 패턴이 최대한 구별되는 문자들을 선택했습니다.

첫 단계는 6x6 폴리비오스 정사각형을 사용한 치환입니다. 36개의 칸에는 알파벳 26자와 숫자 0-9가 키로 정한 순서에 따라 배치됩니다. 행과 열의 머리글은 여섯 문자 A, D, F, G, V, X입니다.

각 평문 문자는 해당 칸의 행 머리글과 열 머리글이라는 두 문자로 바뀝니다. 예를 들어 H가 A행 F열에 있다면 "AF"가 됩니다.

치환한 뒤에는 두 문자로 늘어난 암호문을 키 길이와 같은 수의 열을 가진 격자에 씁니다. 두 번째 키워드가 열의 순서를 결정합니다.

열은 키 문자를 알파벳순으로 정렬한 순서대로 읽습니다. 이렇게 하면 치환된 문자 쌍의 순서가 바뀌어 남아 있는 패턴이 깨지고, 빈도 분석과 패턴 일치에 모두 강한 암호가 만들어집니다.

분할은 전치하기 전에 각 평문 문자를 여러 암호문 기호로 나누는 기법입니다. ADFGVX에서는 각 문자가 두 기호(행과 열)가 되며, 이 기호들을 서로 독립적으로 섞습니다.

따라서 하나의 평문 문자를 이루는 두 "절반"이 최종 암호문에서 서로 다른 위치에 놓이므로, 치환과 전치를 분리하여 분석하는 것이 불가능해집니다.

순수 치환 암호(플레이페어 등)는 빈도 분석에 취약합니다. 순수 전치 암호(레일 펜스 등)는 문자 재배열에 취약합니다. 두 기법을 결합하면 양쪽의 약점을 모두 보완할 수 있습니다.

ADFGVX는 치환된 기호를 분할하고 전치하여 빈도 분석을 더 어렵게 만듭니다. 전치를 해독하려면 치환 키를 알아야 하고, 그 반대도 마찬가지입니다.

프랑스의 암호 분석가 조르주 팽뱅은 1918년 6월, ADFGVX가 보호하던 독일의 공세가 시작되기 불과 며칠 전에 이 암호를 해독했습니다. 이는 WWI에서 가장 뛰어난 암호 해독 성과 중 하나로 평가되었습니다.

팽뱅은 같은 날 같은 키로 전송된 메시지의 패턴을 이용했습니다. 길이가 비슷한 암호문들을 비교하여 열의 경계를 식별하고 전치 과정을 거꾸로 따라갈 수 있었습니다.

팽뱅의 획기적인 성과는 연합국에 독일의 춘계 공세의 기세를 꺾는 데 도움이 되는 정보를 제공했습니다. ADFGVX를 해독하여 얻은 정보 우위가 공세 실패의 한 원인이었습니다.

이 사건은 작전 보안이 취약하면 아무리 영리하게 설계된 암호라도 해독될 수 있음을 보여 주었습니다. 독일군은 키를 재사용했고 짧은 시간에 너무 많은 메시지를 전송했기 때문에 팽뱅이 필요로 하던 자료를 제공하고 말았습니다.

열 단위 전치에서는 키워드 아래에 평문을 행별로 쓴 다음, 키워드 문자를 알파벳순으로 정렬한 순서대로 열을 읽습니다. 키워드 "KEY"를 사용하면 열 순서는 2-1-3이 됩니다(E가 K보다 앞서고 K가 Y보다 앞서기 때문입니다).

출력된 열은 원래 텍스트를 서로 교차시키는 방식으로 섞어 국소적인 패턴을 없앱니다. 복호화하려면 같은 순서로 암호문을 열에 다시 쓴 다음 행별로 읽어야 합니다.

고전 암호의 각 층은 서로 다른 약점을 해결합니다. 치환은 문자의 정체를 감추고, 전치는 문자의 위치를 감춥니다. 두 기법을 함께 사용하면 두 층을 동시에 공격해야 하는 암호가 만들어집니다.

혼돈(치환)과 확산(전치)을 결합하는 이 원리는 훗날 클로드 섀넌에 의해 정식화되었으며, AES와 같은 현대 블록 암호의 이론적 토대가 되었습니다.

ADFGVX 이전에 독일군은 더 단순한 5글자 변형인 ADFGX를 사용했습니다. ADFGX의 폴리비우스 정사각형에는 숫자가 포함되지 않았지만, ADFGVX에서는 정사각형을 6x6으로 확장하여 숫자 10개를 모두 포함할 수 있었고, 그 결과 숫자 데이터도 암호화할 수 있었습니다.

ADFGX에서 ADFGVX로 확장한 것은 연합군이 ADFGX를 부분적으로 해독하는 데 성공한 데 대한 대응이었습니다. 숫자를 추가하면 키 공간이 넓어지고 패턴이 더 많은 기호 쌍에 분산되므로 이중 문자 빈도 분석이 더 어려워졌습니다.

ADFGVX에서 분할이 어떻게 사용되는지 이해했는지 확인해 보세요.

ADFGVX는 폴리비우스 정사각형 치환과 열 전치를 결합하고, 분할을 사용하여 두 기법을 서로 교차 배치했습니다. 6글자 알파벳은 모스 부호 전송 오류를 최소화하도록 선택되었습니다.

정교한 암호였지만, 팽뱅은 키 재사용을 악용하여 이를 해독했습니다. 이 암호는 고전적 기법을 결합하는 것의 강력함과 운용 보안의 결정적 중요성을 모두 보여 주었습니다.