힐 암호란 무엇인가?
힐 암호(Hill Cipher)는 1929년 레스터 S. 힐(Lester S. Hill)이 발명한 다중 문자 다중 알파벳(multiletter polyalphabetic) 암호입니다. 이 암호는 평문을 암호문으로 변환하고 암호문을 다시 평문으로 되돌리는 과정에서 행렬(matrix)의 개념과 선형 합동(linear congruence) 방식을 결합한 부호화 체계입니다.
힐 암호는 행렬 곱셈을 활용해 암호화와 복호화를 수행하기 때문에, 평문 속 동일한 문자가 항상 동일한 암호문 문자로 치환되지 않습니다. 또한 처리 대상 텍스트를 일정한 크기의 블록으로 나누어 다루기 때문에 다중 알파벳 암호인 동시에 블록 암호(block cipher)로 분류할 수 있습니다.
블록 안의 각 문자는 암호화·복호화 절차에서 블록 내 다른 문자들에게 영향을 주므로, 같은 문자가 반드시 같은 문자로 매핑되지 않는다는 점이 단일 치환 암호와의 큰 차이입니다.
힐 암호는 고전 암호학 알고리즘에 속하며, 암호문만 가지고 해독하려면 암호분석가 입장에서 매우 어려운 작업입니다. 하지만 암호문과 함께 평문의 일부까지 확보된다면 상대적으로 간단히 해독할 수 있습니다. 이러한 암호 분석 기법을 기지 평문 공격(known-plaintext attack)이라고 부르며, 공격자가 원하는 평문을 직접 암호기에 입력할 수 있는 선택 평문 공격(chosen-plaintext attack)에서는 더욱 쉽게 깨집니다.
힐 암호의 기본 원리
힐 암호는 행렬 곱셈 기법과 역행렬(inverse matrix) 계산에 기반을 두고 있습니다. 핵심은 n×n 행렬이며, 여기서 n은 블록 크기를 의미합니다.
키로 사용되는 K 행렬은 반드시 가역행렬(invertible matrix)이어야 합니다. 즉, 역행렬 K-1이 존재해야 하는데, 복호화에 사용되는 키가 바로 이 K-1 행렬이기 때문입니다.
힐 암호의 진행 단계
- 블록 분할: 평문을 동일한 크기의 블록으로 나눕니다.
- 순차 암호화: 블록을 한 번에 하나씩 암호화하며, 블록 내 각 문자가 같은 블록에 있는 다른 문자들의 암호화 결과에 기여합니다.
- 키 구조: 키는 m×m 크기의 정방행렬(square matrix)이며, m은 블록 크기를 결정합니다. 이 키 행렬을 K라고 합니다.
평문 블록에 m개의 문자 P1, P2, …, Pm이 있을 때, 암호문 블록의 대응 문자 C1, C2, …, Cm은 다음 연립 방정식으로 정의됩니다.
C1 = (P1K11 + P2K12 + P3K13) mod 26
C2 = (P1K21 + P2K22 + P3K23) mod 26
C3 = (P1K31 + P2K32 + P3K33) mod 26
이 식들은 열벡터(column matrix) 형태로 간결하게 표현할 수 있으며, 일반화하면 다음과 같습니다.
C = KP mod 26 (암호화)P = K-1C mod 26 (복호화)
기지 평문 공격과 선택 평문 공격에 대한 취약성
힐 암호는 기지 평문 공격에 의해 매우 쉽게 무너질 수 있습니다. 길이가 m인 평문-암호문 쌍을 m개 확보했다고 가정해 보겠습니다.
Ci = KPi (1 ≤ i ≤ m)
이때 미지의 키 행렬 K는 다음과 같이 계산할 수 있습니다.
K = Ci · Pi-1
역행렬이 존재하는 평문 행렬 Pi를 하나만 확보해도 키를 역산할 수 있으며, 키가 한 번 계산되는 순간 해당 암호체계는 손쉽게 깨집니다. 선택 평문 공격에서는 공격자가 임의의 평문을 암호기에 입력하고 그 결과를 관찰할 수 있으므로, 가역적인 평문 행렬을 의도적으로 구성해 키를 더욱 빠르고 확실하게 추출할 수 있습니다.
이처럼 힐 암호는 선형성(linearity)으로 인해 소량의 평문 정보만으로도 전체 키가 노출되는 구조적 취약점을 지니며, 현대의 실제 보안 목적으로 사용하기에는 부적합합니다. 다만 행렬과 선형대수를 암호학에 도입한 초기 사례 중 하나로서 학술적으로 중요한 의미를 가지는 암호입니다.