[전공수업][정보보호] Discrete Logarithms

해당 내용은 20년 2학기 COSE354 "정보보호" 수업을 듣고 정리한 내용입니다.

---

Asymmetric Property

현대 암호 알고리즘은 수학에 기반한 Asymmetric Property를 활용해 암호화(encryption)는 쉽게, 복호화(decryption)는 어렵게 한다. 현대 공개키 암호는 한쪽 방향은 easy 하게, 반대쪽 방향은 hard 하게 하면서(oneway function), 더 나아가 key를 알면은 반대쪽 방향도 easy(trapdoor oneway function)하게 해결되도록 한다.

 

예를 들어, 대표적으로 Integer Factorization 문제가 있다. 큰 숫자를 소수의 곱으로 소인수분해 나타내는 것은 어렵지만, 소수를 곱해 큰 숫자를 계산하는건 비교적 쉽다. 소수를 곱해 큰 숫자를 만들어 쉽게 암호화 하고, 반대로 소수는 주어지지 않고 큰 숫자를 쪼개는 것의 어려움을 기반으로 해 복호화를 어렵게 한 암호가 RSA 암호다. 한편, RSA의 비밀키를 알면 복호화도 쉽다.

 

Integer Factorization과 함께 이러한 속성을 갖는 문제가 DLP다. Discrete Logarithm Problem이다. 이 수학적 개념을 활용해 공개키 교환 방식인 Diffie-Hellman key exchange 와 암호화 알고리즘인 Elgamal Encryption이 이루어진다. DLP가 무엇인지 알아보기 앞서, "원시근"에 대해 알아보자.

 

Primitive Roots

오일러 정리에 의해, a^Φ(n)mod n =1 이다.

a^m= 1 (mod n) 이고 gcd(a,n)=1 가 있다고 가정하자. Φ(n)보다 작은 m이 존재한다.

만약 가장 작은 m이 Φ(n)이면, a가 "primitive root"이다.

 

p가 소수라면, primitive root a의 제곱들이 mod p내의 숫자들(0~p-1)을 생성시킨다.

 

a가 2고 p가 19라 했을떄,

a¹mod n 과 a²mod n과..... a^p-1mod n까지를 계산해보면, 각각 2,4,8,16,13,7,14......의 결과가 나오고, 이는 모두 0부터 18까지의 숫자를 모두 포함한다. 

 

하지만 모든 숫자가 primitive root가 있는건 아니다. primitive root가 있는 수들의 형태는 2, 4, p^k , 2*p^k 이다. (이때, p는 홀수인 소수, k는 양의 정수).

 

primitive root는 매우 유용하지만 찾기 힘들다.

 

Discrete Logarithms

Exponentiation의 역은 계산하기 힘들다는 것에 착안하는 문제다. 

모듈러 p에 대해 discrete logarithm을 구하는 것은 다음과 같다.

 

b= aⁱ mod p

i= d*log_ab mod p

이때, i를 찾는게 discrete logarithm problem이다.

 

만약 a가 primitive root라면, 항상 i가 존재하지만, 만약 아니라면 i는 존재하지 않는 경우도 있다.

 

x= log₂9 mod 19 일땐, 2는 primitive root기에 x는 존재해야한다.

x= log₇9 mod 19 일땐, 7은 primitive root가 아니기에 답이 없다.

x= log₃4 mod 13 일때도 마찬가지로 답이 없고

x= log₂3 mod 13 일땐 답이 4다.

 

첫번째 x를 구하기 위해선, 2에 대해 모두 2의 제곱,3의 제곱...19-1의 제곱을 해보고 이에 대해 mod 19를 해봐야한다. 그랬을 때 나오는 값이 9이면 x를 구할 수 있다.

 

따라서 연속적으로 제곱 (successive power)을 모두 시도해봐야 DLP를 풀 수 있는데, 숫자가 매우 크면 computationally infeasible하다.

이러한 원리를 활용해 만들어진 공개키 교환 방식이 Diffie-Hellman 방식이고, Elgamal encryption도 이에 착안한 암호화 방식이다.