엘가말 암호

ElGamal Encryption

• 확률적 암호화 방식
• 결정론적 디피-헬만 문제가 불가능할 경우 IND-CPA(INDistinguishability under Chosen-Plaintext Attack) 보안성을 제공

$g, g^a, g^b$와 $X$가 주어졌을 때 $X$가 $g^{ab}$인지 $g^c$인지 구분하는 문제(c는 무작위)

• $E_{K_{pub}}(M_1) \cdot E_{K_{pub}}(M_2) = E_{K_{pub}}(M_1 \cdot M_2)$
  일반적인 변환을 사용하면 IND-CCA2(INDistinguishability under Chosen-Ciphertext Attack) 보안성을 제공

• 키 생성
  1. 소수 $p$ 선택
  2. $\mathbb{Z}_p^*$의 부분군 $\mathbb{G}$에서 생성자 $g$ 선택
     • 이 부분군의 차수: $q$
  3. $\mathbb{Z}_q$에서 무작위 원소 $x$ 선택 후 $X = g^x \pmod{q}$ 계산
  4. 공개 키 $\text{pk} = (p, q, g, X)$, 비밀 키 $\text{sk} = x$ 출력
• 암호화
  1. $\mathbb{Z}_q$에서 무작위 원소 $r$ 선택
  2. $C_1 = g^r$과 $C_2 = M \cdot X^r$ 계산 후 암호문 $CT = (C_1, C_2)$ 출력
• 복호화
  1. 비밀 키 $\text{sk} = x$와 암호문 $CT = (C_1, C_2)$가 주어졌을 때
  2. $C_2 / (C_1)^x (= M \cdot X^r / (g^r)^x = M)$을 계산하여 평문 $M$ 출력

• 공개 키: $\text{pk} = (23, 11, 2, 8)$, 비밀 키: $\text{sk} = 6$
• 암호화
  • $r = 3$ 일 때,
  • $C_1 = 2^3 = 8$
  • $C_2 = 9 \cdot 8^3 = 9 \cdot 512 = 4608$
• 복호화
  • $M = 4608 / 8^6 = 9$