엘가말 암호

3. 알고리즘

엘가말 암호 알고리즘은 디피-헬만 키 교환을 수행하여 공유 비밀 $s$를 설정하고, 이를 메시지 암호화를 위한 일회용 패드로 사용하는 방식이다. 엘가말 암호화는 키 생성, 암호화, 복호화의 세 단계로 수행된다.

• 키 생성: 앨리스는 순환군 $G$와 그 생성원 $g$, 그리고 무작위로 선택한 정수 $x$를 이용하여 공개 키 $(G,\; q,\; g,\; h)$를 생성하고, $x$를 비밀 키로 유지한다.
• 암호화: 밥은 앨리스의 공개 키를 사용하여 메시지 $M$을 암호화한다. 밥은 무작위로 선택한 정수 $y$와 공유 비밀 $s$를 계산하고, 이를 통해 암호문 $(c\_1,\; c\_2)$를 생성하여 앨리스에게 전송한다.
• 복호화: 앨리스는 자신의 비밀 키 $x$와 암호문 $(c\_1,\; c\_2)$를 이용하여 공유 비밀 $s$를 계산하고, $s$의 역원 $s^\{-1\}$을 구한다. 그 후, $m\; :=\; c\_2\; \backslash cdot\; s^\{-1\}$ 계산을 통해 원래 메시지 $m$을 복구하고, 이를 다시 평문 메시지 $M$으로 변환한다.

3. 1. 키 생성

• 순환군 $G\backslash ,$를 생성한다. $G\backslash ,$는 차수가 $q\backslash ,$이고, 생성원 $g$를 갖는다.
• $\backslash \{1,\; \backslash ldots,\; q-1\backslash \}$에서 정수 $x$를 무작위로 선택한다.
• $h\; :=\; g^x$를 계산한다.
• $(G,\; q,\; g,\; h)$를 공개 키로 하고, $x$를 비밀 키로 한다. 비밀키는 비밀로 유지해야 한다.

3. 2. 암호화

• 앨리스는 밥의 공개 키를 전달받는다.
• 앨리스는 밥에게 전달할 메시지 ''m''을 선택한다.
• 앨리스는 무작위로 정수 ''k''를 선택한다. (0 ≤ ''k'' ≤ ''p''-1)
• ''c''₁ := α^''k''과 ''c''₂ := β^''k''''m''을 계산한다.
• 앨리스가 밥에게 암호문(''c''₁, ''c''₂)를 전달한다.

• 메시지 ''M''을 가역 매핑 함수를 사용하여 ''G''의 요소 ''m''으로 매핑한다.
• {1, ..., ''q''-1}에서 정수 ''y''를 무작위로 선택한다.
• ''s'' := ''h''^''y''를 계산한다. 이것을 ''공유 비밀''이라고 한다.
• ''c''₁ := ''g''^''y''를 계산한다.
• ''c''₂ := ''m'' · ''s''를 계산한다.
• 밥은 암호문 (''c''₁,''c''₂)를 앨리스에게 보낸다.

• 평문으로 ''G''의 원소 ''m''을 받는다.
• ''r''을 {0,...,''q''-1}에서 무작위로 선택한다.
• ''c''₁ = ''g''^''r'', ''c''₂ = ''m'' · ''h''^''r''을 계산한다.
• (''c''₁, ''c''₂)를 암호문으로 한다.

3. 3. 복호화

• $s\; :=\; c\_1^x$를 계산한다. $c\_1\; =\; g^y$이므로, $c\_1^x\; =\; g^\{xy\}\; =\; h^y$이며, 이는 밥이 암호화에 사용한 값과 동일하다.
• $s$의 역원인 $s^\{-1\}$을 계산한다. 이는 여러 방법으로 계산할 수 있다.
• $G$가 소수 $n$을 법으로 하는 정수의 곱셈 그룹의 부분군인 경우, 확장 유클리드 알고리즘을 사용하여 모듈러 곱셈 역원을 계산할 수 있다.
• $s^\{-1\}$을 $c\_1^\{q-x\}$로 계산할 수 있다. 이는 라그랑주 정리에 의해 $s$의 역원인데, $s\; \backslash cdot\; c\_1^\{q-x\}\; =\; g^\{xy\}\; \backslash cdot\; g^\{(q-x)y\}\; =\; (g^\{q\})^y\; =\; e^y\; =\; e$이기 때문이다.
• $m\; :=\; c\_2\; \backslash cdot\; s^\{-1\}$를 계산한다. 이 계산은 원래 메시지 $m$을 생성하는데, $c\_2\; =\; m\; \backslash cdot\; s$이므로 $c\_2\; \backslash cdot\; s^\{-1\}\; =\; (m\; \backslash cdot\; s)\; \backslash cdot\; s^\{-1\}\; =\; m\; \backslash cdot\; e\; =\; m$이다.
• $m$을 평문 메시지 $M$으로 다시 변환한다.

4. 안전성

제3자가 공개 키 $(p,\; \backslash alpha,\; \backslash beta)$와 암호문 $(c\_\{1\},\; c\_\{2\})$를 모두 안다고 해도, 여기서 메시지 $m$을 찾으려면 밥만이 아는 비밀 정보인 $y$나 앨리스가 일회용으로 정한 수 $k$를 알아야 한다. 이는 이산 로그 방정식 $\backslash beta\; =\; \backslash alpha\; ^\{x\}$의 해 $x$를 구하는 것과 같으며, $p$가 클수록 해를 구하기 어렵다.

엘가말 암호의 안전성은 기저 그룹 $G$의 속성과 메시지에 사용된 패딩 방식에 따라 달라진다. 기저 순환 그룹 $G$에서 계산적 디피-헬만 가정(CDH)이 성립하면 암호화 함수는 일방향 함수가 된다.^[2]

만약 $G$에서 결정적 디피-헬만 가정(DDH)이 성립하면 엘가말 암호는 의미적 안전성을 달성한다.^[2][3] 의미적 안전성은 계산적 디피-헬만 가정만으로는 보장되지 않는다. 이 가정이 성립한다고 여겨지는 그룹은 결정적 디피-헬만 가정 문서를 참고할 수 있다.

엘가말 암호는 가소성 (암호학)을 가지므로 선택 암호문 공격에 안전하지 않다. 예를 들어 메시지 $m$의 암호문 $(c\_1,\; c\_2)$가 주어졌을 때, 메시지 $2m$의 유효한 암호문 $(c\_1,\; 2\; c\_2)$를 쉽게 구성할 수 있다.

선택 암호문 안전성을 달성하기 위해서는 추가적인 수정이나 적절한 패딩 방식이 사용되어야 한다. 수정 사항에 따라 DDH 가정이 필요할 수도 있고 그렇지 않을 수도 있다.

엘가말 암호와 관련된 다른 방식들도 제안되었다. 크래머-슈프 암호 시스템은 $G$에 대해 DDH가 성립한다고 가정하면 선택 암호문 공격에 안전하다. 이 증명은 랜덤 오라클 모델을 사용하지 않는다. 또 다른 제안된 방식은 통합 암호화 방식인 DHIES^[4]인데, 이 증명에는 DDH 가정보다 더 강력한 가정이 필요하다.

엘가말 암호는 선택 평문 공격에 대해 완전 해독할 수 없다는 것(OW-CPA)과 CDH 가정이 동치이다. 또한, 엘가말 암호가 선택 평문 공격 하에서 Indistinguishability를 갖는다는 것(IND-CPA)과 DDH 가정은 동치이다.

5. 효율성

엘가말 암호는 확률적 암호화 방식이다. 이는 하나의 평문을 여러 개의 가능한 암호문으로 암호화할 수 있음을 의미하며, 일반적으로 엘가말 암호화는 평문에서 암호문으로 크기가 1:2로 확장되는 결과를 낳는다.

엘가말 암호화는 두 번의 지수 연산을 필요로 한다. 그러나 이러한 지수 연산은 메시지와 독립적이므로, 필요하다면 미리 계산해 놓을 수 있다. 복호화는 한 번의 지수 연산과 한 번의 그룹 역원 계산을 필요로 하지만, 이를 한 번의 지수 연산으로 쉽게 결합할 수 있다.

6. 순환군 G의 선택

• 순환군 ''G''에서 위수가 소수인 ''q''를 선택하고, ''q''의 비트수는 ''k''로 한다.
• ''G''의 생성원 ''g''를 선택한다.
• ''x''를 {0,...,q-1}에서 무작위로 선택한다.
• $h\; =\; g^x$로 계산한다.
• $(G,\; q,\; g,\; h)$를 공개키로 하고, ''x''를 비밀키로 한다.

• 순환군 ''G''를 $\{\backslash mathbb\; Z\}\_p^\{*\}$의 부분군으로 한다.
• 순환군 ''G''를 타원 곡선 암호에서처럼 타원 곡선 위에서 정의한다.

• 작은 자연수 ''k''와 큰 소수 ''q''에 대해 ''p = kq+1''이 성립하는 소수 ''p''를 찾는다.
• 먼저 소수 ''q''를 선택한 후, ''p = kq + 1''이 소수인지 확인하는 방식으로 진행할 수 있다.
• $g\; \backslash in\; \{\backslash mathbb\; Z\}\_p^\{*\}$를 ''g''의 위수가 ''q''가 되도록 무작위로 선택한다.
• $G\; =$는 $\{\backslash mathbb\; Z\}\_p^\{*\}$의 부분군이 된다.

7. 응용

대부분의 공개 키 시스템과 마찬가지로, 엘가말 암호 시스템은 일반적으로 하이브리드 암호 시스템의 일부로 사용된다. 여기서 메시지 자체는 대칭 암호 시스템을 사용하여 암호화되고, 엘가말은 대칭 키만 암호화하는 데 사용된다. 이는 엘가말과 같은 비대칭 암호 시스템이 동일한 보안 수준에서 대칭 암호 시스템보다 일반적으로 느리기 때문이다. 따라서 임의로 큰 메시지를 대칭 암호로 암호화한 다음, 메시지 크기에 비해 일반적으로 매우 작은 대칭 키만 엘가말로 암호화하는 것이 더 빠르다.

디피-헬만 키 교환 방식을 암호 방식으로 활용할 수 있도록, Diffie-Hellman 키 공유 방식으로 공유된 난수를 사용하여 일회용 패드(OTP)를 수행하는 방식에서 변형되었다.

엘가말 암호는 암호 (cipher)이지만, 이와는 별도로 디지털 서명 (digital signature)에 응용할 수 있는 엘가말 서명도 발표되었다.

용어에 대해서는 암호 용어, 암호 이론 용어를 참조하라.

참조

_[1] 논문 A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms https://caislab.kais[...]
_[2] 웹사이트 Elgamal encryption scheme https://crypto.cs.ui[...] University of Illinois at Urbana-Champaign 2008-12-13
_[3] 서적 Public Key Cryptography 2006-05-24
_[4] 서적 Topics in Cryptology — CT-RSA 2001 2001-01-01