ElGamal — 이산 대수 기반 공개키 암호

RSA가 소인수분해의 어려움에 기반한다면, ElGamal은 이산 대수 문제(DLP)에 기반한다. 두 시스템은 서로 다른 수학적 어려움을 활용하는데, 결정적 차이가 하나 있다. ElGamal은 암호화할 때마다 다른 암호문을 생성한다. 이 점이 의미론적 안전성(IND-CPA)의 핵심이 된다.

RSA와의 차이: 왜 다른 어려움이 필요한가

RSA는 $n = pq$ 소인수분해의 어려움에 의존한다. 이 문제는 검증된 어려움이지만, 같은 평문을 항상 같은 암호문으로 변환한다는 결정론적(deterministic) 특성이 있다. 공격자가 후보 평문을 암호화해 비교하는 선택 평문 공격(CPA)에 취약하다.

ElGamal은 이산 대수 문제(Discrete Logarithm Problem, DLP) 라는 독립적인 어려움을 사용한다. 그리고 암호화 과정에 랜덤성을 도입해 동일한 평문도 매번 다른 암호문으로 변환된다.

이산 대수 문제 (DLP)

소수 $p$, 생성원(generator) $g \in \mathbb{Z}_p^*$, 그리고 $h = g^x \bmod p$가 주어졌을 때, $x$를 구하여라.

정방향 계산 $k \to g^k \bmod p$는 Square-and-Multiply로 $O(\log k)$에 가능하다. 반면 역방향 $g^k \bmod p \to k$를 구하는 알고리즘은 아직 다항식 시간으로 알려져 있지 않다. 가장 빠른 알고리즘(Number Field Sieve)조차 준지수 시간 $L[1/3]$이 필요하다.

생성원(Generator): 소수 $p$에 대해 $g \in \mathbb{Z}_p^*$가 생성원 이라는 것은 $g$의 거듭제곱이 $\mathbb{Z}_p^*$의 모든 원소를 순환한다는 의미다.

$$\{g^0, g^1, g^2, \ldots, g^{p-2}\} = \mathbb{Z}_p^* \quad (\bmod\ p)$$

$p = 11$, $g = 2$이면 $\{1, 2, 4, 8, 5, 10, 9, 7, 3, 6\} = \mathbb{Z}_{11}^*$으로 10개 원소 전부를 생성한다. 페르마의 소정리에 의해 $g^{p-1} \equiv 1 \pmod{p}$이므로, 지수는 주기 $p-1$로 순환한다.

ElGamal 설정

공개 파라미터: 큰 소수 $p$, $\mathbb{Z}_p^*$의 생성원 $g$

평문 공간: 메시지 $m$은 아무 정수가 아니라 연산하는 군의 원소여야 한다. $\mathbb{Z}_p^*$에서 쓴다면 $1 \le m \le p-1$이고, 특히 $m = 0$은 평문이 될 수 없다. $m = 0$이면 $B = 0 \cdot h^k = 0$이 되어 $k$와 무관하게 암호문이 늘 $0$이고, 그 순간 확률적 암호화도 IND-CPA도 무너진다.

임의의 바이트열을 보내려면 먼저 군의 원소로 옮기는 인코딩이 필요하다. 데이터를 $p$보다 작은 수로 자르고 $0$을 피하도록 옮기는 방식이 가장 단순하고, 뒤에서 볼 소수 위수 부분군에서 쓴다면 그 부분군 안으로 보내는 사상이 따로 필요하다. 인코딩은 복호 뒤 되돌릴 수 있어야 하므로 단사여야 한다.

키 생성 (수신자 Alice):

1. 비밀키 $x$를 $1 \leq x \leq p-2$ 범위에서 무작위 선택
2. $h = g^x \bmod p$ 계산
3. 공개키: $(p,\ g,\ h)$ · 개인키: $x$

암호화 (송신자 Bob):

1. 임시 비밀(ephemeral key) $k$를 $1 \leq k \leq p-2$ 범위에서 무작위 선택
2. $A = g^k \bmod p$
3. $B = m \cdot h^k \bmod p$
4. 암호문: $(A,\ B)$

복호화 (수신자 Alice):

1. 공유 비밀 $s = A^x \bmod p$ 계산
2. $s$의 모듈러 역원 $s^{-1} \bmod p$ 계산 (확장 유클리드 알고리즘)
3. 복원: $m = B \cdot s^{-1} \bmod p$

복호화 정확성 증명

왜 $B \cdot s^{-1}$이 $m$을 복원하는가.

$$s = A^x = (g^k)^x = g^{kx} \pmod{p}$$ $$h^k = (g^x)^k = g^{xk} \pmod{p}$$

따라서 $s = h^k$이다. $B$의 정의에 의해

$$B \cdot s^{-1} = m \cdot h^k \cdot (h^k)^{-1} = m \pmod{p} \quad \checkmark$$

핵심은 Alice와 Bob이 각자 독립적으로 동일한 공유 비밀 $g^{kx} \bmod p$를 계산한다는 것이다.

• Bob: $h^k = (g^x)^k$ (Alice의 공개키 $h$와 자신의 임시 키 $k$ 사용)
• Alice: $A^x = (g^k)^x$ (Bob이 보낸 $A$와 자신의 비밀키 $x$ 사용)

이는 Diffie-Hellman 키 교환의 직접적인 응용이다. ElGamal 암호화는 DH 키 교환에 메시지 마스킹($m \cdot h^k$)을 결합한 구조이다.

보안 근거: CDH 가정

ElGamal이 기대는 가정은 두 개이고 서로 다른 것을 보장한다.

메시지를 통째로 복원하지 못한다 — CDH

CDH. $g$, $g^x$, $g^k$ 가 주어졌을 때 $g^{xk}$를 계산하는 다항식 시간 알고리즘이 존재하지 않는다.

공격자가 암호문 $(A, B) = (g^k, m \cdot h^k)$을 가로채더라도 공유 비밀 $g^{xk}$를 계산하지 못하면 $m$을 복원할 수 없다. 이것이 단방향성(one-wayness) 이다.

DLP와의 관계는 한쪽 방향만 알려져 있다. DLP를 풀 수 있으면 $g^x$에서 $x$를 얻어 $(g^k)^x$를 계산할 수 있으므로 CDH도 풀린다. 여기서 나오는 결론은 CDH가 어려우면 DLP도 어렵다이다. 반대로 CDH를 푸는 능력에서 DLP 해법을 얻는 일반적인 방법은 알려져 있지 않다. 그러니 「DLP가 어려우니 CDH도 어렵다」고 말할 수는 없고, CDH는 DLP보다 강한 가정으로 따로 세워야 한다.

한 비트도 새지 않는다 — DDH

IND-CPA는 CDH만으로는 나오지 않는다. $g^{xk}$를 통째로 계산하지 못해도 그 일부 정보가 새면 두 후보 평문을 구별할 수 있기 때문이다. 그래서 필요한 것이 더 강한 가정이다.

DDH. $g$, $g^x$, $g^k$, $Z$ 가 주어졌을 때 $Z = g^{xk}$인지 $Z$가 무작위인지 구별하는 것이 어렵다.

DDH는 $\mathbb{Z}_p^*$ 전체에서는 성립하지 않는다. 르장드르 기호로 제곱잉여 여부를 다항식 시간에 판정할 수 있고, $g^{xk}$의 제곱잉여 여부가 $g^x$와 $g^k$의 그것으로 정해지기 때문이다. 그래서 IND-CPA를 말하려면 소수 위수 $q$인 부분군에서 연산해야 한다. $p = 2q+1$인 안전 소수의 제곱잉여 부분군이 그런 군이다. 자세한 이야기는 Diffie-Hellman 글에서 다룬다.

확률적 암호화와 IND-CPA 안전성

ElGamal의 핵심 이점은 확률적(randomized) 암호화다.

같은 평문 $m$도 임시 키 $k$가 달라지면 완전히 다른 암호문이 생성된다.

이 성질은 IND-CPA(선택 평문 공격 하 식별 불가능성) 안전성을 가능하게 한다.

• RSA(교과서적): $m \to C$가 결정론적. 공격자가 두 후보 $m_0, m_1$을 직접 암호화해 도전 암호문 $C^*$와 비교 가능.
• ElGamal: $m \to (A, B)$가 확률적. 공격자가 $m$을 암호화해도 $k$가 달라 $C^*$와 일치하지 않음.

단, 암호문이 두 개의 군 원소 $(A, B)$로 구성되므로 평문 대비 암호문 크기가 2배로 증가한다. RSA 대비 트레이드오프다.

올바른 파라미터 선택

소수 $p$ 크기: DLP의 어려움은 $p$의 크기에 비례한다. 현재 권장은 2048비트 이상. $p-1$이 큰 소인수를 포함해야 한다 (Pohlig-Hellman 공격 방지).

생성원 $g$ 선택: $g$가 $\mathbb{Z}_p^*$ 전체를 생성해야 한다. $p-1$의 소인수 $q$에 대해 $g^{(p-1)/q} \not\equiv 1 \pmod{p}$를 확인한다.

임시 키 $k$ 관리: $k$는 암호화마다 독립적으로 새로 선택해야 한다. 같은 $k$를 두 번 사용하면 두 암호문 $B_1 = m_1 \cdot h^k$, $B_2 = m_2 \cdot h^k$에서 $B_1 / B_2 = m_1 / m_2$가 노출된다.