엘가말

엘가멜 (El Gamal)은 1984년 스탠퍼드 대학의 타헤르 엘가멜 (Taher ElGamal)이 제안한 알고리즘으로, 이산대수 문제의 어려움에 기반한 최초의 공개키 암호이다. 엘가멜은 디피-헬만 키 교환 알고리즘을 참고해 만들어졌다.

특징

• 엘가멜 암호 알고리즘은 메시지의 길이가 두 배로 늘어나는 특징이 있다.
• 같은 평문이라도 암호화가 이루어질 때마다 암호문이 달라진다.
• RSA 암호에 비해 안전하지만 속도가 느리다.

절차

키 생성

• 큰 소수 p를 선택하고 생성자 g를 선택한다.
• 비밀키인 x를 선택하고 공개키 y = g^e mod p 를 계산한다.
• (y, g, p)를 공개키로 공개하고 x는 비밀키로 안전하게 보관한다.

암호화

• 메시지 m을 암호화 하기 위해 난수 k를 선택한다.
• 암호문인 r = g^k mod p 와 s = my^k mod p를 계산한다.
• 암호문 (r, s)를 수신자에게 전송한다.

복호화

• 순시자는 자신의 비밀키 x를 이용하여 복호화 한다.
• m = s/r^x mod p 계산.

참고 자료

〈 암호 쉽게 이해하기 〉

〈 암호학 - Public Key Cipher :: ElGamal 〉《개인블로그》, 2010-05-21

같이 보기

• 디피-헬만
• RSA