[암호학] 3. 디피-헬만 알고리즘과 ElGamal

저번 글에서 DLP에 대해서 설명했습니다. 이번 글에서는 DLP를 이용한 암호 시스템인 ElGamal에 대해서 알아보겠습니다.
ElGamal은 디피-헬만 키 교환 알고리즘을 참고해서 만들어졌습니다. 먼저 디피-헬만 키 교환 알고리즘에 대해 설명하겠습니다.

Diffie-Hellman key exchange

디피-헬만 키 교환 혹은 키 합의 알고리즘은 가장 오래된 공개키 암호화 방식입니다. 암호학 #1에서 설명했던 RSA 암호 시스템도 디피-헬만 알고리즘에 영향을 받아 만들어졌습니다.
디피-헬만 알고리즘은 암호 송신자와 수신자가 각각 알고있는 정보를 이용해 복호화 함수 $d_K(c)$를 알고 있는 공격자가 평문을 알아낼 수 없게 하는 알고리즘입니다. 여기서 복호화 함수는 $K$ 값을 필요로 합니다.

소수 $p$가 있고 $\text{ord}_p(g)$가 큰 소수인 $g$가 있을 때, $\mathbb{F}_p^* = \mathbb{F}_{p} \setminus \left\{ 0 \right\} = \{ 1, g , g^2 , \cdots , g^{p-2} \}$는 원소의 개수가 $(p - 1)$ 개인 순환군입니다.

암호 송신자를 앨리스, 수신자를 밥, 공격자를 이브라고 하겠습니다.

Alice, Bob, Eve는 암호학에서 자주 쓰는 가상 이름입니다.
Alice는 A, Bob은 B에서 나온 이름이며 각각 통신 과정의 첫 번째, 두 번째 당사자를 의미합니다.
Eve는 '엿듣는 사람'이라는 뜻을 가진 'eavesdropper'에서 유래했으며 평문의 내용을 궁금해하지만 바꿔치기는 하지 않는 소극적 공격자를 의미합니다.

디피-헬만 키 합의 과정

알고리즘은 다음과 같은 과정으로 이루어져 있습니다.

첫 번째로 아주 큰 소수 $p$와 $\text{ord}_p(g)$가 큰 소수인 $g \in \mathbb{F}_p^*$ (되도록이면 원시근을 선택합니다)를 선택해서 공개합니다.
이 때 앨리스, 밥, 이브 모두 $p$, $g$를 알고 있습니다.

두 번째로 앨리스가 임의의 정수 $a$, 밥이 임의의 정수 $b$를 선택합니다.
앨리스가 알고 있는 정보는 $a$, $p$, $g$ 입니다.
밥이 알고 있는 정보는 $b$, $p$, $g$ 입니다.
이브가 알고 있는 정보는 $p$, $g$ 입니다.

각각 $A \equiv g^a \pmod p$, $B \equiv g^b \pmod p$ 를 계산 후 공개합니다.
앨리스가 알고 있는 정보는 $a$, $A$, $B$, $p$, $g$ 입니다.
밥이 알고 있는 정보는 $b$, $A$, $B$, $p$, $g$ 입니다.
이브가 알고 있는 정보는 $A$, $B$, $p$, $g$ 입니다.

평문 $m$을 $K \equiv B^a \equiv A^b \pmod p$로 암호화한 $c = e_K(m)$을 사용하면 이브는 복호화 함수 $d_K$를 알고 있더라도 $K$를 알 수 없어 $m$을 알 수 없습니다.

$\begin{aligned} K &\equiv A^b\\ &\equiv (g^a)^b\\ &\equiv (g^b)^a\\ &\equiv B^a \pmod p \end{aligned}$

여기서 중요한 점은 $a$와 $b$가 모두 임의의 정수라는 점입니다. 암호화 과정에서 매번 새롭게 임의의 정수를 선택한다면 평문이 같더라도 암호문이 달라지게 됩니다. 이 성질이 안전성을 높여주게 됩니다.
디피-헬만 알고리즘은 공개키 암호, 디지털 서명 등에 모두 쓰입니다.

ElGamal 암호

ElGamal 암호 시스템은 디피-헬만 키 합의와 동일하게 아주 큰 소수 $p$와 $\text{ord}_p(g)$가 큰 소수 $g \in \mathbb{F}_p^*$ (되도록이면 원시근)를 선택해 먼저 공개한 상황에서 시작합니다.

암호화 과정

암호를 보내는 사람을 앨리스, 받는 사람을 밥이라고 하겠습니다.

1. 밥은 먼저 $x \in [1, p - 1]$인 $x$를 고르고, $y = g^x\mod p$를 구하고 공개합니다.
2. 앨리스는 $k \in [1, p - 1]$인 $k$를 고르고,
   $C_1 = g^k \pmod p$
   $C_2 = m \cdot y^k \pmod p$
   두 값을 계산해 $(C_1, C_2)$를 밥에게 보냅니다.
3. 밥은 $x$를 알고 있으므로 $m$을 다음과 같은 식으로 구할 수 있습니다.
   $m = C_2 \cdot C_1^{-x}\pmod p$

위 3번의 계산 과정은 다음과 같습니다.

이브는 $C_1$과 $C_2$가 공개되어 있다고 해도 $x$와 $k$를 알 수 없으므로 $m$을 알아내는 것이 매우 어렵습니다.

앞서 설명했던 RSA 암호와 ElGamal 암호는 각각 IFP, DLP라는 문제의 어려움을 이용해 암호의 안전성을 확보합니다. 그러나 둘 다 준지수시간 알고리즘을 통해 해를 구할 수 있고, 키 길이가 길다는 단점이 존재합니다.
다음 글에서는 아직 적용 가능한 준지수시간 알고리즘이 존재하지 않는 타원곡선암호에 대해 알아보겠습니다.