[Cryptography 2.] ElGamal system

이번 포스트에서는 public key system들 중, ElGamal system에 대해 간략하게 소개하겠습니다.

ElGamal system이란 무엇인가

ElGamal system은 매우 큰 수에 대한 이산 로그(discrete logarithm)를 구하기 어렵다는 가정에서 출발합니다. 이산 로그 문제는 다음과 같이 정의할 수 있습니다.

• 소수 $p$, 그리고 $p$와 서로소인 수 $a$ 가 주어졌을 때,
• $a^{x} \equiv b \pmod {p}$를 만족하는 $x$ 를 구하는 것

현재까지 이산 로그 문제를 효율적으로 계산하는 알고리즘은 없다고 합니다. 그리고 $p$ 가 커질수록 이산 로그는 더 계산하기 어려워 집니다.

이를 기반으로, 다음과 같이 ElGamal system을 정의하겠습니다.

먼저, 매우 큰 소수 $p$ 와,$\mod {n}$ 에 대한 원시근 $g$를 준비합니다. 이 두 수는 공개되어 있습니다.

아래와 같이 public key와 private key를 정의합니다.

Private key는 $0 < a < p - 1$ 을 만족하는 $a$ 로 정의합니다. Public key는 $b \equiv g^{a} \pmod {p}$ 를 만족하는 $b$ 로 정의합니다.

암호화할 메시지 M 이 있다고 하고, 이를 암호화하기 전 특정 규칙에 따라 일련의 수로 변환했다고 가정하겠습니다. 암호화는 다음과 같은 과정으로 이루어집니다. 암호화는 메시지를 전달할 대상의 public key를 이용합니다.

$0 < k < p - 1$ 을 만족하는 random number $k$ 를 생성합니다. 암호화된 메시지는 $(g^{k} \pmod {n}, \;M* b^{k} \pmod {n})$로 정의합니다.

복호화는 메시지를 전달받은 쪽의 private key를 통해 이루어집니다.

복호화는 $M \equiv M * b^{k} * ((g^{k})^{a})^{-1}$ 을 통해 이루어집니다.

ElGamal system의 정당성

위에서 소개한 복호화 방법으로 어떻게 원문을 얻어낼 수 있는 걸까요? 간단한 수학적 증명으로 보일 수 있습니다.

암호화된 메시지가 다음과 같이 주어졌다고 가정하겠습니다.

random number $k$ 의 값을 공개하는 대신, $g^{k} \pmod {n}$ 값을 전달했습니다.

위 식의 우변에 $((g^{k})^{a})^{-1} \pmod {n}$ 을 곱함으로써 원문 M을 얻어낼 수 있습니다.

Private key $a$ 를 알고 있으면, 전달받은 $g^{k}$ 과 $a$ 를 통해 $(g^{k})^{a}$ 을 계산하고, 이의 $\mod {n}$ 에 대한 inverse를 계산함으로써 메시지를 복호화할 수 있습니다. 하지만 $a$ 를 모른다면 복호화는 (거의) 불가능합니다. 이는 이산 로그를 계산하기 어렵다는 가정이 뒷받침되기 때문입니다.

만약 이산 로그를 효율적으로 계산할 수 있다면 어떻게 될까요? Private key를 몰라도 ElGamal 암호는 풀리고 맙니다. $g^{k} \mod {n}$ 을 통해 이산 로그 $k$를 계산할 수 있고, 이를 통해 $(b^{k})^{-1} \mod {n}$ 을 계산할 수 있기 때문입니다.