엘가말 암호 문서 원본 보기

{{위키데이터 속성 추적}}
'''엘가말 암호'''({{lang|en|ElGamal encryption}})는 [[타헤르 엘가말]]이 1985년에 고안한, [[디피-헬먼 키 교환]]을 바탕으로 한 [[공개 키 암호 방식]]이다.

== 절차 ==
아래는 엘가말 암호 알고리즘을 이용하여 송신인 [[앨리스와 밥|앨리스]]가 수신인 밥에게 메시지를 전달하는 절차를 설명한 것이다.
=== 준비 ===
* 차수가 소수 <math>p</math>인 [[순환군]] <math>G</math>와 이의 한 생성원 <math>\alpha</math>를 정한다.
* 밥은 정수 <math>y</math>를 선택한다. (<math>0 \leq y \leq p-1</math>)
* <math>\beta := \alpha ^{y}</math>을 계산한다.
* <math>(p, \alpha, \beta)</math>가 [[공개 키]]가 된다.

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

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

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

== 같이 보기 ==
* [[동형암호]]
== 참고 문헌 ==
* {{저널 인용|author=Taher ElGamal |title=A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms |journal=IEEE Transactions on Information Theory |volume=31 |issue=4 |year=1985 |pages=469–472 |doi=10.1109/TIT.1985.1057074 |url=http://caislab.kaist.ac.kr/lecture/2010/spring/cs548/basic/B02.pdf}}
* {{서적 인용|성1=Trappe|이름1=Wade|성2=Washington|이름2=Lawrence C.|제목=Introduction to Cryptography with Coding Theory (Second Edition)|출판사=Prentice Hall|쪽=212-214|isbn=9788945001795}}


{{공개 키 암호 방식}}

[[분류:암호 알고리즘]]