[암호론]11. 폴리그-헬만 지수 암호(Pohlig-Hellman exponentiation cipher), 페르마의 작은정리(Fermat's little theorem), 오일러의 정리(Euler's theorem)

지금까지의 암호를 만들 때는 덧셈이나 곱셈을 사용했습니다.

암호에 사용할 수 있는 또 다른 수학적 연산에는 지수연산(exponentiation)이 있습니다.

평문 P를 모듈러 n에 대해서 e번 곱한 수를 암호문으로 나타내는 암호를 생각할 수 있습니다.

예를 들면 1615을 769번 곱한 후 모듈러2819 연산을 하면 1592라는 암호문이 만들어집니다.

이와 같은 암호를 폴리그-헬만 지수암호(Pohlig-Hellman exponentiation cipher)라고 합니다.

그렇다면 암호문 1592를 복호화하려면 어떻게 해야할까요? 

가장 먼저는 지수 연산의 역연산인 제곱근을 생각할 수 있을것입니다.

하지만 1592의 769제곱근은 약 1.0096 으로 복호화하는 것에 도움이되지 않습니다.

 

지수암호를 복호화하려면 먼저 페르마의 작은 정리(Fermat's little theorem)에 대해 살펴보아야 합니다.

p가 소수이고 a가 정수일 때, 페르마의 작은 정리에 따르면 모듈러 p에서 a의 p제곱과 a는 서로 합동입니다.

즉, 아래와 같은 합동식을 만족합니다.

Fermat's little theorem

이를 증명해봅시다.

우리는 앞에서 a x b ≡ 1 mod n에서 b 와 n의 최대공약수가 1일 때만 a에 대한 모듈러n에 대한 곱셈에 대한 역원이 있음을 알 수 있었습니다. 

따라서 a x c ≡ b x c mod n 일때 c 와 n의 최대공약수가 1일 때만 a ≡ b mod n인 것을 알 수 있습니다.

p를 소수라고 할 때 집합 A를 p로 나눈 나머지의 집합이라고 합시다.

A = {0,1,2,...,p-1} 이 됩니다.

B를 A중 역원이 있는 원소들의 집합, 즉 A의 원소와 최대공약수가 1인 원소들의 집합이라고 합시다.

B = {1,2,3,...,p-1} 이 됩니다.

B에서 임의의 원소 a를 뽑은 후 B에 곱해줍니다.

a x B = {a*1,a*2,a*3,...,a*(p-1)}

이때 a x B를 모듈러p연산을 한다면 집합 B와 집합의 원소와 원소의 갯수가 같아짐을 알 수 있습니다.

그렇다면 B의 모든 원소의 곱과 a x B의 모든 원소의 곱은 같을 것입니다.

즉, 1 x 2 x 3 x ... x (p-1) ≡ (a x 1) x (a x 2) x (a x 3) x ... x (a x (p-1)) ≡ a^(p-1) x (1 x 2 x 3 x ... x (p-1)) mod p 입니다.

따라서 양변을 (p-1)!으로 나누면 a^(p-1) ≡ 1 mod p , 즉 페르마의 작은 정리가 성립함을 알 수 있습니다.

 

우리는 이를 만족하는 d를 구하면 지수 암호를 복호화 할 수 있습니다.

페르마의 작은 정리에서 지수만 본다면 p-1은 0과 같으므로 일반적으로 모듈러 p에 대한 지수방정식을 다루고 있다면 지수에 대해서는 모듈러 p-1에 대한 연산을 한다고 할 수 있습니다. 

평문을 암호화 하는 지수를 e라고 할 때 e x d ≡ 1 mod p-1 인 d을 구함으로써 복호화를 할 수 있습니다.

이때 암호화를 하는 사람은 사전에 p-1과 최대공약수가 1인 e를 선택해야 합니다.

우리는 e x d ≡ 1 mod p-1 만족하는 d는 Euclid Algorithm으로 구할 수 있습니다.

 

p=13, e=5이고 암호문이 6일때의 예시를 살펴봅시다.

이 같은 과정을 통해 평문이 2였음을 알 수 있습니다.

 

페르마의 작은 정리에서는 소수 모듈러연산에 대해서만 합동식이 성립했습니다.

이를 합성수로 일반화한 공식이 오일러 공식(Euler's theorem)입니다. 

Euler's theorem

오일러 공식을 이해하기 위해서는 먼저 a의 지수승에 해당하는 오일러 파이 함수를 알아야합니다.

오일러 파이 함수는 이와같이 나타낼 수 있으며 n과 서로소인 a의 갯수를 나타내는 함수입니다.

또한 p,q가 소수일 때 이와같은 공식으로 나타낼 수 있습니다. 

즉 오일러 파이 함수에 들어갈 n이 합성수라면 소인수분해를 통해 소수의 곱으로 나타낸 후 오일러 파이 함수의 값을 구할 수 있습니다.

모듈러 연산을 할 n이 합성수 일경우 위와 같은 합동식을 이용해 d를 구한 후 오일러 정리를 이용해  폴리그-헬만 지수암호를 복호화 할 수 있습니다.

이와 같은 지수암호는 공개키 암호의 수학적 기반이 되었습니다.

 

오늘도 긴글 읽어 주셔서 감사합니다.

틀렸거나 부족한 부분은 알려주시면 감사하겠습니다.