엘가말 편집하기

''' 엘가말'''<!--엘 가말, 엘가멜, 엘 가멜-->(ElGamal)<!--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-Plaintext 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]]

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