엘가말 암호

틀:위키데이터 속성 추적 엘가말 암호(틀:Lang)는 타헤르 엘가말이 1985년에 고안한, 디피-헬먼 키 교환을 바탕으로 한 공개 키 암호 방식이다.

절차

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

준비

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

암호화

• 앨리스는 밥의 공개 키를 전달받는다.
• 앨리스는 밥에게 전달할 메시지 $m\in G$을 선택한다.
• 앨리스는 무작위로 정수 $k$를 선택한다. ($0\le k\le 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$가 크면 클수록 해를 구하기 어려워진다.

같이 보기

• 동형암호

참고 문헌

• 틀:저널 인용
• 틀:서적 인용

틀:공개 키 암호 방식