ElGamal 암호는 symmetric cryptography의 일종이다.

이산대수문제(DLP)에 기반한 암호이다.

ElGamal의 개요

키 생성

1. 큰 소수 $p$ 선택 (2048bit 이상의 크기)
2. $1 \leq d \leq p-2$ 범위의 임의의 d를 선택
3. $Z_n^*$ 에서 원시근 $e_1$을 선택
4. $e_2 \equiv e_1^d \pmod{p}$ 를 계산
5. 공개키는 $(e_1, e_2, p)$, 개인키는 $d$

암호화

1. 임의의 값 $r$ 선택
2. $c_1 \equiv e_1^r \pmod{p}$
3. $c_2 \equiv (m \times e_2^r) \pmod{p}$
4. 암호문 $(c_1, c_2)$

복호화

1. $c_2 \times (c_1^d)^{-1} \mod{p}$

   $c_2 \times (c_1^d)^{-1} \equiv (e_2^r \times m) \times (e_1^{rd})^{-1} \equiv (e_1^{rd} \times e_1^{rd})^{-1} \times m \equiv m \pmod{p}$

ElGamal의 취약점

Low-Modulus Attack

충분히 크지 않은 소수 $p$를 사용한다면 전수 조사나 이산대수의 성질로 인해 개인키 $d$나 임의의 값 $r$이 노출될 수 있다.
따라서 $p$는 적어도 2048bit 이상을 사용한다.

Known Plaintext Attack

$m$에 대한 $c_1, c_2$를 알고 있으며
같은 $r$을 사용한 $m^*$에 대한 암호문 $c_1^*, c_2^*$을 얻으면

1. $e_2^r \equiv c_2 \times m^{-1} \pmod{p}$
2. $c_2^* \times (e_2^r)^{-1} \mod{p} = m^*$