엘가말 편집하기

[[파일:엘가말.PNG|썸네일|600픽셀|'''엘가말'''(El Gamal)]]
''' 엘가말'''<!--엘 가말, 엘가멜, 엘 가멜-->(El Gamal)<!--El Gamal-->은 1984년 미국[[스탠퍼드 대학교]]의 [[타헤르 엘가말]](Taher ElGamal)이 제안한 [[암호 알고리즘]]으로, [[이산대수]] 문제의 어려움에 기반한 최초의 [[공개키]] 암호이다. 엘가말은 [[디피-헬만]] 키 교환 알고리즘을 참고하여 만들었다.

== 개요 ==
엘가말은 1984년에 미국 [[스탠퍼드 대학교]]의 [[타헤르 엘가말]](Taher ElGamal)이 제안한 공용 키 암호 방식의 하나이다.<ref>아랑이의 IT 탐험기, 〈[https://arang99.tistory.com/6 공개키 암호화]〉,《개인 블로그》, 2016-08-17</ref> 소수 p와 원시근 g를 공통의 공용키로 한다. 이용자는 자신의 비밀키 X를 정하고 g를 X 승해서 p로 나눈 나머지 Y(Y=gX mod p)를 자신의 공용키로 한다. 평문과 난수의 공용 키로부터 암호문을 생성, 비밀키로 [[복호화]](decoding)한다. 암호문의 길이가 평문 길이의 2배로 되는 결점이 있으나 이산대수 문제의 어려움에 안전성의 근거를 두고 있다. 엘가말은 공용 키 암호 방식의 하나로 [[이산대수]](離散對數) 문제에 대한 최초의 공용 키 암호이며 DH 공용 키 분배법의 확장형이고, 소수(素數) p와 원시근(原始根) g를 공통의 공용키로 한다.<ref>한국정보통신기술협회 공식 홈페이지 - 〈http://a.to/198yOi1〉</ref>

엘가말 암호는 이산대수(離散對數) 문제에 대한 최초의 공용 키 암호이며 DH 공용 키 분배법의 확정형이다. 이산대수 문제의 어려움이란, 주어진 g, x, p를 이용하여 y = g^x mod p를 구하긴 쉽지만, g, y, p 값을 이용하여 원래의 x는 찾기 어렵다는 것이다. 엘가말 암호의 장점은 난수 k를 이용하기 때문에, 매 암호화 시 다른 암호문을 얻어 [[RSA]]에 비해 더 안전하다. 그 이유는 RSA는 같은 메시지, 같은 킷값을 이용할 경우 그 암호문이 항상 일정한 데 반해, 엘가말 암호는 같은 메시지, 같은 킷값을 사용해도 암호화를 할 때마다 그 암호문의 값이 변하기 때문이다. 다만 메시지 M을 암호화하면 그 길이가 두 배가 되며 속도가 느리다는 단점이 있다.

== 특징 ==
* 엘가말 암호 알고리즘은 메시지의 길이가 두 배로 늘어나는 특징이 있다.
* 같은 평문이라도 암호화가 이루어질 때마다 암호문이 달라진다.
* [[RSA]] 암호보다 안전하지만, 속도가 느리다.
* [[이산대수]] 문제를 기반으로 하였다.
* 난수 K를 이용하므로 매 암호화 시 다른 암호문을 얻어 RSA에 비해 안전하다.
* 암호문의 길이가 평문 길이의 2배가 되는 단점이 있다.

* '''엘가말 암호의 취약점'''
# 작은 [[모듈러스]] 공격(Low-Modulus Attack) : p의 값이 충분히 크지 않을 경우 전수 조사나 이산대수의 성질을 이용한 효율적인 알고리즘을 통하여 개인 키 d나 임의의 값 r을 찾아낼 수 있다. p는 적어도 2048비트
# 알려진 평문 공격(Known-Plain text Attack) : 평문 m에 대응하는 암호문

* '''엘가말 암호의 안정성'''
: 컴퓨터 디피-헬만(The Computational Diffie-Hellman; CDH) 문제 : 계산 문제
: 순환군 : G of order q, 생성원 g∈G에 대하여,  a,b∈{0,1,...q - 1}, (<math>g,g^{a},g^{b},q</math>), 가 주어졌을때, <math>g^{ab}</math> mod q ≡?
: The Decisional Diffie-Hellman(DDH) 문제 : 결정 문제 (Yes or No)
: 순환군 : G of order q, 생성원 g∈G에 대하여,  a,b,c∈{0,1,...q - 1}, (<math>g,g^{a},g^{b},g^{c},q</math>), 가 주어졌을때, ab ≡?c(mod q)

===엘가말을 사용한 암호 설명===
[[파일:엘가.PNG|썸네일|600픽셀]]
: 대칭 키를 사용하지 않고도 EC Elgamal 방식으로 암복호화를 할 수 있다.
* Plain Text는 35이다. 밑은 5, 모듈로는 89이다.
* 앨리스의 개인 키는 13이다.
* 밥의 개인 키는 8이다.
* <math>X^{a,b}</math> 의 89 모듈로는 다음과 같다. 밑에 계산된 두 숫자 40과 4를 교환한다. 이때 공격자 Eve는 40 혹은 4로부터 개인 키 13 혹은 8을 추출할 수 없다.
 <math>Alice : 5^{13} mod 89 => 40</math>
 <math>Bob :  5^8 mod 89 => 4</math>
* 앨리스와 밥은 상대편의 지수 부분(비밀키)을 몰라도 전송된 각각의 40, 4를 가지고 암호 키를 계산할 수 있다. 즉 암호 키값은 16이다.
 <math>Alice : 4^{13} mod 89 = 16</math>
 <math>Bob  : 40^{8} mod 89 = 16</math>
* 평문(Plain Text) 35를 암호화 해서 보내고자 한다.
 <math>CT ( Cipher Text ) :  </math>
 <math>CT <= 16*35 mod 89 => 26 : X^{ab} * P mod N</math>
 <math>35*16 mod 89 => 26</math>
* 형성된 암호 키값 16의 모듈로 역수는 39이다. [G,C,~]=gcd(16,89); % C => 39 matlab 에서 위 함수를 사용하면 모듈로 인버스를 구할 수 있다. 모듈로의 역수를 구하는 방법은 0부터 계속 한 개씩 증가시켜서 모듈로 결과가 1이 나올 때 증가시켜서 대입한 그 값이 역수이다. 여기서는 대입해본 결과 39를 얻었다. 39번의 모듈로 계산했다는 이야기다.

* 복호(암호의 반대)를 하려면 암호된 값 26에 16의 모듈로 역수 39를 곱하면 나온다. 
 <math>CT = X^{ab} * P mod N   => 26</math>
 <math>PT = CT * X^{ab}-1 mod N</math>
 <math>26*39 mod 89 = 35 </math>
: 복호된 값이 암호된 값 35 와 동일하다.
'''matlab 확인 결과''' 
 <math>mod(5^{13},89) % ans = 40, Prv K : 13 N = 89 </math>
 <math>mod(5^{8},89) % ans = 4, Prv K : 8  </math>
: 
 <math>mod(4^{13},89) % ans = 16 Encryptin Key</math> 
 <math>mod(40^{8},89) % ans = 16 Encryptin Key</math> 
:   
 <math>mod(16*35,89) % ans = 26 CT : Cipher Text </math>
 <math>[G,C,~]=gcd(16,89); % C => 39</math>
:   
 <math>mod(16*39,89) % ans = 1 Inverse 16  </math>
 <math>mod(26*39,89) % ans = 35 : Decrypted V = Plain Text</math>

* '''엘가말 공개키 암호 시스템'''
: 일반 공개키 암호화의 안전성은 소인수 분해가 이루어져야 한다. 그 외의 다른 이산 로그는 문제를 공개키로 잡을 수 없고, 엘가 말은 공개 키핑이 대표적인 방법이다. 밥은 Prime Number p를 선택하고 Primitive Root을 선택한다. 여기서, m은 0 ≤ m <p 인 정수이다. 문제가되는 것은 밥은 비밀 키를 선택하고 β ≡ α ^ a (mod p)를 계산 한다. 여기서 (p, α, β)를 공개하고, 밥의 공개 키. 앨리스는 다음 과정을 거친 것이다. 
# 밥에게 메시지를 보내고, 밥의 공개 키 (p, α, β)를 가져 온다. 
# 임의의, 공시적 으로 선택을하고, r ≡ <math>a^{k}</math> (mod p)를 계산 한다.
# t ≡ <math>b ^{k}</math> * m (mod p)를 계산한다. 
# 앨리스는 밥에게 (r, t)를 보낸다. 
: 밥은 해독 할 수 있다. 
: <math>TR^{-a}</math> ≡ m (MOD P) 
: ∵ <math>TR^{-a}</math> ≡ <math>b^{k}</math>개의 * m 개의 * <math>(a^{K})^{-a}</math> ≡ <math>(a^{a})^{k}</math> 개의 * m의 *의 <math>a^{ak}</math> ≡ m (mod p)
: 여기서, k는 임의의 선택 정수이고, β k (mod p)는 임의의 정수이다. 즉, <math>t = b^{k} * m (mod p)</math>는 무작위 적이다. 결국, Eve는 대구 정보에 대해서도 마찬가지 이다. 이브는 추가 정보를 요구한다. 이브는 다음과 같이 나타낼 수있고, (- k)를 알아낼 수있다. 또한, 아무것도하지 않을 수도 있다. (r, t1)은 다른 사람들에게 (r, t2)가 거스름돈을 전달한다. 이브는 t1과 t2를 ≡ t2 / m1 / t1 (mod p)로 설정한다.

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

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

'''복호화'''
* 수신자는 자신의 비밀키 x를 이용하여 복호화한다.
* <math>m = (\frac{s}{r})^{x} mod p</math> 계산한다.<ref>〈[https://reinliebe.tistory.com/26 암호학 - Public Key Cipher :: ElGamal]〉, 《개인 블로그》, 2010-05-21 </ref>

== 예시 ==
* '''엘가말 서명'''
: ElGamal Encryption 또한 디지털 서명 할 수 있는데, 예를 들어, 앨리스는 서명한다고 하면 앨리스는 큰 소수 p와 원시적인 루트를 선택한다. 1 ≤ a ≤ p - 2 인 선택을하고 β ≡ <math>a^{a} (mod p)</math>를 계산한다. a 비밀 유지가되어야한다. 공개 키는 (p, α, β)가 있으면 앨리스는 이렇게 하면 된다.
 공개되지 않은 임의의, gcd (k, p - 1) = 1을 만족하는 것을 선택 한다. 
 r ≡ <math>a^{k}</math> (mod p) (0 <r <p)를 계산한다.
 s ≡ <math>k^{-1}</math> * (m - ar) (mod p - 1)을 계산한다.
: 서명을 확인하십시오. Bob은 다음 과정을 진행한다. 이때 서명된 의사는 (m, r, s)가 된다.
 앨리스의 공개키 (p, α, β)를 가져온다.
 v1 ≡ <math>b^{r} * r^{s}</math> (mod p)와 v2 ≡ <math>a^{m}</math> (mod p)를 계산한다.
 v1 ≡ v2라면,이 서명은 비싸지 않다.
: (m - ar) (mod p - 1)는 sk ≡ (m - ar) (mod p - 1)이고, (sk + ar) ≡ <math>(a^{a})^{r} * (a^{k})^{s}</math> ≡ <math>b^{r} * r^{s}</math> ≡ v1 (mod p)이다. 이브는 알지도 못하는 기사를 남겨두고, 비밀을 유지하라. 즉, 결과적으로 다음과 같은 문제가 되는데, 다시 정리해 보면 <math>(R^{S}</math> ≡ <math>b^{-R}) * a^{m} MOD (P)</math>, 즉 이산 대수 (discrete logarithm) 이다.<ref> Celdee, 〈[https://celdee.tistory.com/229 엘가말 서명]〉,《티스토리》, 2008-12-09</ref>

{{각주}}

== 참고자료 ==
* 한국전국통신기술협회 공식 홈페이지 - 〈http://a.to/198yOi1〉
* 〈[http://a.to/19aYP0n 암호 쉽게 이해하기]〉
* 〈[https://reinliebe.tistory.com/26 암호학 - Public Key Cipher :: ElGamal]〉, 《개인 블로그》, 2010-05-21
* Celdee, 〈[https://celdee.tistory.com/229 엘가말 서명]〉,《티스토리》, 2008-12-09
* 아랑이의 IT 탐험기, 〈[https://arang99.tistory.com/6 공개키 암호화]〉,《개인 블로그》, 2016-08-17
* 사랑과 생각, 〈[http://a.to/19dKxq7 EC Elgamal Encryption 설명]〉,《네이버》, 2018-11-26
* JayTech, 〈[https://pjh3749.tistory.com/221 EI Gamal(엘가말)과 Diffle-Hellman(디피헬만)프로토콜]〉,《티스토리》, 2018-12-08

== 같이 보기 ==
* [[암호 알고리즘]]
* [[공개키]]
* [[타헤르 엘가말]]
* [[디피-헬만]]
* [[RSA]]

{{암호 알고리즘|토막글}}