힐 암호(Hill Cipher)는 선형대수학(linear algebra)에 기반한 다중 문자 치환 암호(polygraphic substitution cipher)입니다. 1929년 Lester S. Hill이 고안한 이 암호는 평문과 키를 행렬 형태로 변환한 뒤 행렬 곱셈과 모듈러 연산을 통해 암호화·복호화를 수행하는 것이 특징입니다.
힐 암호의 동작 원리
암호화(Encryption)
키 문자열과 메시지 문자열을 각각 행렬 형태로 변환합니다. 두 행렬을 곱한 결과에 모듈로 26(알파벳 개수)을 적용하면 암호문이 생성됩니다. 이때 복호화를 위해 반드시 키 행렬이 역행렬(inverse matrix)을 가져야 합니다.
복호화(Decryption)
암호화에 사용된 키 행렬의 역행렬을 구한 뒤, 암호문 행렬과 곱하고 모듈로 26을 적용하면 원래의 평문을 얻을 수 있습니다.
예제로 살펴보기
키 행렬
1 0 1 2 4 0 3 5 6
메시지 문자열 'ABC'를 행렬 형태(A=0, B=1, C=2)로 나타내면 다음과 같습니다.
0 1 2
암호화 과정
위 두 행렬을 곱하면 다음과 같은 결과가 나옵니다.
2 4 17
각 값을 알파벳으로 변환하면 암호문은 'CER'이 됩니다.
복호화 과정
키 행렬의 역행렬은 다음과 같습니다.
1.09091 0.227273 -0.181818 -0.545455 0.136364 0.0909091 -0.0909091 -0.227273 0.181818
역행렬과 암호문 행렬을 곱하면,
0 1 2
다시 원래의 메시지 문자열 'ABC'가 복원됩니다.
C++ 구현 알고리즘
Begin
Function getKeyMatrix()
For i = 0 to 2
For j = 0 to 2
행렬 a[i][j]의 요소를 입력받는다.
m[i][j] = a[i][j]
done
done
메시지 문자열을 사용자로부터 입력받는다.
For i = 0 to 2
msg[i][0] = mes[i] - 65
done
End
Begin
Function encrypt()
For i = 0 to 2
For j = 0 to 0
For k = 0 to 2
en[i][j] = en[i][j] + a[i][k] * msg[k][j]
곱셈 결과 행렬의 각 요소에 모듈로 26을 적용하여 암호문을 출력한다.
End
Begin
Function decrypt()
inversematrix() 함수를 호출한다.
For i = 0 to 2
For j = 0 to 0
For k = 0 to 2
de[i][j] = de[i][j] + b[i][k] * en[k][j]
곱셈 결과에 모듈로 26을 적용하여 원래 메시지를 얻는다.C++ 전체 소스 코드
#include<iostream>
#include<math.h>
using namespace std;
float en[3][1], de[3][1], a[3][3], b[3][3], msg[3][1], m[3][3];
void getKeyMatrix() { //키와 메시지를 사용자로부터 입력받음
int i, j;
char mes[3];
cout<<"Enter 3x3 matrix for key (should have inverse):\n";
for(i = 0; i < 3; i++)
for(j = 0; j < 3; j++) {
cin>>a[i][j];
m[i][j] = a[i][j];
}
cout<<"\nEnter a string of 3 letter(use A through Z): ";
cin>>mes;
for(i = 0; i < 3; i++)
msg[i][0] = mes[i] - 65;
}
void encrypt() { //메시지를 암호화
int i, j, k;
for(i = 0; i < 3; i++)
for(j = 0; j < 1; j++)
for(k = 0; k < 3; k++)
en[i][j] = en[i][j] + a[i][k] * msg[k][j];
cout<<"\nEncrypted string is: ";
for(i = 0; i < 3; i++)
cout<<(char)(fmod(en[i][0], 26) + 65); //곱셈 결과 행렬의 각 요소에 모듈로 26 적용
}
void inversematrix() { //키 행렬의 역행렬 계산
int i, j, k;
float p, q;
for(i = 0; i < 3; i++)
for(j = 0; j < 3; j++) {
if(i == j)
b[i][j]=1;
else
b[i][j]=0;
}
for(k = 0; k < 3; k++) {
for(i = 0; i < 3; i++) {
p = m[i][k];
q = m[k][k];
for(j = 0; j < 3; j++) {
if(i != k) {
m[i][j] = m[i][j]*q - p*m[k][j];
b[i][j] = b[i][j]*q - p*b[k][j];
}
}
}
}
for(i = 0; i < 3; i++)
for(j = 0; j < 3; j++)
b[i][j] = b[i][j] / m[i][i];
cout<<"\n\nInverse Matrix is:\n";
for(i = 0; i < 3; i++) {
for(j = 0; j < 3; j++)
cout<<b[i][j]<<" ";
cout<<"\n";
}
}
void decrypt() { //메시지를 복호화
int i, j, k;
inversematrix();
for(i = 0; i < 3; i++)
for(j = 0; j < 1; j++)
for(k = 0; k < 3; k++)
de[i][j] = de[i][j] + b[i][k] * en[k][j];
cout<<"\nDecrypted string is: ";
for(i = 0; i < 3; i++)
cout<<(char)(fmod(de[i][0], 26) + 65); //모듈로 26을 적용해 원래 메시지 복원
cout<<"\n";
}
int main() {
getKeyMatrix();
encrypt();
decrypt();
}실행 결과
Enter 3x3 matrix for key (should have inverse): 1 0 1 2 4 0 3 5 6 Enter a string of 3 letter(use A through Z): ABC Encrypted string is: CER Inverse Matrix is: 1.09091 0.227273 -0.181818 -0.545455 0.136364 0.0909091 -0.0909091 -0.227273 0.181818 Decrypted string is: ABC
마무리
이 프로그램은 3×3 키 행렬과 3글자 메시지를 입력받아 힐 암호의 암호화와 복호화 과정 전체를 보여줍니다. 힐 암호는 단일 문자 치환 암호와 달리 여러 문자를 한 번에 처리하기 때문에 빈도 분석 공격에 상대적으로 강하지만, 알려진 평문 공격에는 취약하다는 점을 참고하면 좋습니다. 실습을 통해 행렬 연산이 암호학에서 어떻게 활용되는지 직접 확인해 보세요.