ElGamal 란? 엘가말 암호란?

 

ElGamal 란? (엘가말 암호란?)

ElGamal 암호는 이산대수 문제의 어려움에 기반을 둔 최초의 공개키 암호 알고리즘입니다.

ElGamal은 1984년 스탠퍼드 대학의 암호 학자 T. ElGamal에 의해 제안되었습니다. ElGamal으로 암호화하면 메시지의 길이가 두 배로 늘어나는 특징이 있습니다. 하지만 암호화할 때 난수를 이용하므로 같은 메시지에 대해 암호화하여도 암호화할 때마다 서로 다른 암호문을 얻게 되는데, 이것은 정보보호 측면에서 큰 장점이 됩니다. 

 

개요

- ElGamal 암호는 이산대수 문제의 어려움에 근거하여 만든 체계입니다.

- 이산대수 문제의 어려움이란, p가 소수이고 g가 원시원소일 때, g, x, p를 이용하여 y=g^x mod p를 구하기 쉽지만 g, y, p 값을 이용하영 지수승의 x를 구하기는 어렵다는 의미입니다. 이와 같은 어려움을 이용하여 x는 개인키 , y는 공개키로 사용이 됩니다.

- ElGamal 암호는 디지털 서명, 암호화, 키 교환에 사용될 수 있는 공개키 알고리즘 입니다.

- ElGamal 암호의 단점은 다른 알고리즘과 비교했을때 가장 느리다는 단점이 있습니다.

 

쉽게 이해하실 수 있도록 예를 보여드리겠습니다.

 

이산대수의 문제 예입니다.

위 그림을 통해서 13은 5의 14제곰이라는 것을 알 수 있습니다. 하지만 위표가 없으면 알아내는데는 어려움이 있을 것입니다. 이런 어려움을 통한 암호가 ElGamal 암호 입니다.

 

그러면 이제 ElGamal 암호호와 복호화에 대해 설명 해드리겠습니다.

1. BOB이 개인키와 공개키를 생성합니다.

* 2와 p-2 사이에서 정수를 고르는 이유

- 개인키가 1일 경우 : 공개키가 원시원소(공개가 됨)가 되고 이를 통해 개인키를 유추할 수 있기때문에 안전성에 문제가 있습니다.

- 개인키가 p-1 일 경우 : p-1을 제곱할 경우 나머지가 1이 되기 때문입니다. 즉 공개키가 1이 되고 위와 마찬가지로 안전성에 위험이 있기 때문에 개인키를 유추할 수 있습니다.

 

2. ALICE가 BOB 에게 받은 공개키로 K를 만듭니다.

- r은 0~ p-1  사이의 수입니다.

- r 이 랜덤 수이기 때문에 암호화를 할때 마다 다른 K 값이 나와 같은 평문이라도 다른 암호문이 나오게 됩니다.

 

3. ALICE는 최종 암호문인 C를 생성합니다.

- C1: BOB이 K값을 BOB의 개인키로 알 수 있게 하는 암호문이며 r을 공개할 수 없기 때문에 암호문으로 보냅니다.

- C2: 실질적인 암호문입니다. 평문과 K를 곱해 p로 나눈 나머지 입니다.

 

4. BOB이 자신의 개인키로  K를 얻고 암호문을 복호화 합니다.

- 자신의 개인키(Xb)로 C1을 복호화 하여 K를 얻습니다.

- K로 C1을 나눠 p로 나눈 나머지 값을 구하여 암호문으로부터 평문을 얻습니다.

- K값을 얻을수 있는 이유는

ALICE가 생성한 K값 : K=(Yb)r mod p = (aXb)r mod p

BOB이 획득한 K값 : K = (C1)XB mod p = (ar)XB mod p 

이기 때문입니다.

설명이 어렵다 보니 예시로 암호화 및 복호화 하는것을 보여드리겠습니다.

 

ElGamal 암호의 특징은 다음과 같습니다.

- 같은 평문이라도 암호화가 이루어질 때마다 암호문이 달라집니다.

- ElGamal 암호계에서는 암호문 전달 과정에서 알 수 있듯이 평문이 암호문으로 될때 순서쌍으로 표현되므로 이 암호계에서 암호문의 길이는 평문의 약 2배가 된다.

- RSA암호화 비교하여 그만큼 많은 메모리 공간이 필요하며 전송 속도 또한 지체되는 단접을 가지고 있습니다.

 

ElGamal 의 응용

- ELGamal 은 RSA를 활용할 수 있는 곳 어디에서나 사용가능합니다. 키교환, 인증, 짧은 메세지의 암호화와 복호화에 사용할 수 있습니다.