엘가말 암호

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

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

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

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

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

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