엘가말 암호

엘가말 암호(ElGamal encryption)는 타헤르 엘가말이 1985년에 고안한, 디피-헬먼 키 교환을 바탕으로 한 공개 키 암호 방식이다.

절차

아래는 엘가말 암호 알고리즘을 이용하여 송신인 앨리스가 수신인 밥에게 메시지를 전달하는 절차를 설명한 것이다.

준비

• 차수가 소수 $p$인 순환군 $G$와 이의 한 생성원 $\alpha$를 정한다.
• 밥은 정수 $y$를 선택한다. ($0\leq y\leq p-1$)
• $\beta :=\alpha ^{y}$을 계산한다.
• $(p,\alpha ,\beta )$가 공개 키가 된다.

암호화

• 앨리스는 밥의 공개 키를 전달받는다.
• 앨리스는 밥에게 전달할 메시지 $m\in G$을 선택한다.
• 앨리스는 무작위로 정수 $k$를 선택한다. ($0\leq k\leq p-1$)
• $c_{1}:=\alpha ^{k}$과 $c_{2}:=\beta ^{k}m$을 계산한다.
• 앨리스가 밥에게 암호문 $(c_{1},c_{2})$를 전달한다.

복호화

• 밥은 $s:=c_{1}^{y}$을 계산한다. (이는 $\beta ^{k}$와 그 값이 동일하다.)
• 밥이 $c_{2}s^{-1}$을 계산하면 앨리스가 전달하고자 했던 메시지 $m$이 나온다.

안전성

위 절차에서 제3자가 공개 키 $(p,\alpha ,\beta )$와 암호문 $(c_{1},c_{2})$를 모두 안다 하더라도 여기에서 $m$을 찾으려면 밥만이 아는 정보인 $y$를 (또는 앨리스가 일회용으로 정한 수인 $k$를) 알아야 하는데, 이는 이산 로그 방정식 $\beta =\alpha ^{x}$의 해 $x$를 구하는 것과 동일하며, $p$가 크면 클수록 해를 구하기 어려워진다.

참고 문헌

• Taher ElGamal (1985). “A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms” (PDF). 《IEEE Transactions on Information Theory》 31 (4): 469–472. doi:10.1109/TIT.1985.1057074. 
• Trappe, Wade; Washington, Lawrence C. 《Introduction to Cryptography with Coding Theory (Second Edition)》. Prentice Hall. 212-214쪽. ISBN 9788945001795.