위키원
엘가말
엘가말(ElGamal)은 1984년 미국 스탠퍼드 대학교의 타헤르 엘가말(Taher ElGamal)이 제안한 암호 알고리즘으로, 이산대수 문제의 어려움에 기반한 최초의 공개키 암호이다. 엘가말은 디피-헬만 키 교환 알고리즘을 참고하여 만들었다.
개요
엘가말은 1984년에 미국 스탠퍼드 대학교의 타헤르 엘가말(Taher ElGamal)이 제안한 공용 키 암호 방식의 하나다. 소수= p와 원시근= g를 공통의 공용 키로 한다. 이용자는 자신의 비밀 키 X를 정하고 g를 X승 해서 p로 나눈 나머지 Y(Y=gX mod p)를 자신의 공용 키로 한다. 평문과 난수의 공용 키로부터 암호문을 생성, 비밀 키로 복호화(decoding)한다. 암호문의 길이가 평문 길이의 2배로 되는 결점이 있으나 이산 대수 문제의 어려움에 안전성의 근거를 두고 있다. 엘가말은 공용 키 암호 방식의 하나로 이산 대수(離散對數) 문제에 대한 최초의 공용 키 암호이며 DH 공용 키 분배법의 확장형이고, 소수(素數) p와 원시근(原始根) g를 공통의 공용 키로 한다.[1]
엘가말 암호는 이산 대수(離散對數) 문제에 대한 최초의 공용 키 암호이며 DH 공횽 키 분배법의 확정형이다. 이산대수 문제의 어려움이란, 주어진 g, x, p를 이용하여 y = g^x mod p를 구하긴 쉽지만 g, y, p 값을 이용하여 원래의 x는 찾기 어렵다는 것이다. 엘가말 암호의 장점은 난수 k,를 이용하기 때문에, 매 암호화 시 다른 암호문을 얻어 RSA에 비해 더 안전하다. 그 이유는 RSA는 같은 메시지, 같은 키 값을 이용할 경우 그 암호문이 항상 일정한 데 반해 엘가말 암호는 같은 메시지, 같은 키 값을 사용해도 암호화를 할 때마다 그 암호문의 값이 변하기 때문이다. 다만 메시지 M을 암호화 하면 그 길이가 두 배가 되며 속도가 느리다는 단점이 있다.
특징
- 엘가말 암호 알고리즘은 메시지의 길이가 두 배로 늘어나는 특징이 있다.
- 같은 평문이라도 암호화가 이루어질 때마다 암호문이 달라진다.
- RSA 암호에 비해 안전하지만 속도가 느리다.
- 이산대수 문제를 기반으로 하였다.
- 난수 K를 이용 하므로 매 암호화시 다른 암호문을 얻어 RSA에 비해 안전하다.
- 암호문의 길이가 평문길이의 2배가 되는 단점이 있다.
- 엘가말 공개키 암호시스템
- 일반 공개 키 암호화의 안전성은 소인수 분해가 이루어져야 한다. 그 외의 다른 이산 로그는 문제를 공개 키로 잡을 수 없고, 엘가말은 공개 키핑이 대표적인 방법이다. 밥은 Prime Number p를 선택하고 Primitive Root를 선택한다. 여기서, m은 0 ≤ m <p 인 정수이다. 문제가되는 것은 밥은 비밀 키를 선택하고 β ≡ α ^ a (mod p)를 계산 한다. 여기서 (p, α, β)를 공개하고, 밥의 공개 키. 앨리스는 다음 과정을 거친 것이다.
- 밥에게 메시지를 보내고, 밥의 공개 키 (p, α, β)를 가져 온다.
- 임의의, 공시적 으로 선택을하고, r ≡ α ^ k (mod p)를 계산 한다.
- t ≡ β ^ k * m (mod p)를 계산한다.
- 앨리스는 밥에게 (r, t)를 보낸다.
밥은 해독 할 수 있다.
- TR ^ (- a) ≡ m (MOD P)
- ∵ TR ^ (- a) ≡ β ^ k 개의 * m 개의 * (α ^ (K)) ^ (- a) ≡ (α ^ a)는 ^ k 개의 * m의 *의 α (^ ak) ≡ m (mod p)
- 여기서, k는 임의의 선택 정수이고, β k (mod p)는 임의의 정수이다. 즉, t = β ^ k * m (mod p)는 무작위 적이다. 결국, 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를 선택한다.
- 암호문인 r = g^k mod p 와 s = my^k mod p를 계산한다.
- 암호문 (r, s)를 수신자에게 전송한다.
복호화
- 수신자는 자신의 비밀키 x를 이용하여 복호화한다.
- m = s/r^x mod p 계산한다.
예시
- 엘가말 서명
- ElGamal Encryption 또한 디지털 서명 할수 있는데, 예를 들어, 앨리스는 서명을 한다고 하면 앨리스는 큰 소수 p와 원시적 인 루트를 선택한다. 1 ≤ a ≤ p - 2 인 선택을하고 β ≡ α ^ a (mod p)를 계산한다. a 비밀 유지가되어야한다. 공개 키는 (p, α, β)가 있으면 앨리스는 이렇게 하면 된다.
공개되지 않은 임의의, gcd (k, p - 1) = 1을 만족하는 것을 선택 한다. r ≡ α ^ k (mod p) (0 <r <p)를 계산한다. s ≡ k ^ (- 1) * (m - ar) (mod p - 1)을 계산한다.
- 서명을 확인하십시오. Bob은 다음 과정을 진행 한다. 이때 서명 된 의사는 (m, r, s)가 된다.
앨리스의 공개 키 (p, α, β)를 가져온다. v1 ≡ β ^ r * r ^ s (mod p)와 v2 ≡ α ^ m (mod p)를 계산한다. v1 ≡ v2라면,이 서명은 비싸지 않다.
- (m - ar) (mod p - 1)는 sk ≡ (m - ar) (mod p - 1)이고, (sk + ar) ≡ (α ^ (a)) ^ r * (α ^ (k)) ^ s ≡ β ^ r * r ^ s ≡ v1 (mod p)이다. 이브는 알지도 못하는 기사를 남겨두고, 비밀을 유지하라. 즉, 결과적으로 다음과 같은 문제가되는데, β ^ r에 * 연구 ^ S ≡ α ^ m (MOD P) 이것을 다시 정리해 보면 R ^ S ≡ β ^ (- (R)) * α ^ m MOD (P), 즉 이산 대수 (discrete logarithm) 이다.
각주
- ↑ 한국정보통신기술협회 공식 홈페이지 - 〈http://a.to/198yOi1〉
참고자료
- 한국전국통신기술협회 공식 홈페이지 - 〈http://a.to/198yOi1〉
- 〈암호 쉽게 이해하기〉
- 〈암호학 - Public Key Cipher :: ElGamal〉, 《개인 블로그》, 2010-05-21
- Celdee, 〈엘가말 서명〉,《티스토리》, 2008-12-09
- 아랑이의 IT 탐험기, 〈공개키 암호화〉,《개인 블로그》, 2016-08-17
같이 보기
