[암호학] Elgamal 암호 알고리즘과 취약점

1. Elgamal 암호 알고리즘 개요

Elgamal 암호는 공개키암호시스템으로서 디피헬만의 키교환과 같은 원리를 사용하는 것이 특징이다. Elgamal 암호는 이산대수 문제의 어려움에 기반하고 있다. 예를 들어 (x,g,p)가 주어졌을 때 y=g^x mod p는 계산하기 쉽지만, (y,g,p)가 주어졌을 때 x를 찾기 쉽지 않다는 것이다. Elgamal 암호는 Textbook-RSA보다 암호문의 길이가 2배나 길다. 하지만 동일한 평문에 대해 동일 암호문을 출력하는 Textbook-RSA와 달리 동일 평문에 대해 매번 다른 암호문을 출력하는 probabilistic한 성질을 가진다.

 

 

키생성

1. 큰 소수 $p$를 선택한다.

2. $1\le d\le p-2$의 범위에서 임의의 d를 선택한다.

3. $Z_p^{\ast }$에서 임의의 원시근 $e_1$을 선택한다.

4. $e_2=e_1^{d}modp$를 계산한다.

 

암호화

1. 메시지 $m$과 랜덤 $r$을 선택

2. $c_1=e_1^{r}modp$를 계산

3. $c_2=e_2^{r}mmodp$를 계산

4. $(c1,c2)$를 수신자에게 전송

 

복호화

개인키 d를 이용해 $c_2(c_1^d{)}^{-1}modp$를 계산 → M 도출 가능

$c_2(c_1^d{)}^{-1}modp$

= $c_2{e}_1^{-rd}modp$

= $e_2^{r}m\ast e_1^{-rd}modp$

= $e_1^{rd}m{e}_1^{-rd}modp$

= $mmodp$

 

 

2. Elgamal 암호 알고리즘과 KPA 공격

random number를 사용하지 않으면 Elgamal 암호는 KPA 공격에 취약하다. KPA 공격은 알려진평문공격으로 공격자가 평문에 대응하는 암호문 쌍 일부를 알고 있을 때다. 공격자는 이를 통해 새로운 평문에 대해 평문과 키를 알아내는 것을 목표로 한다.

 

방법 1

공격자는 자신이 알고 있는 평문 m과 $(c_1,c_2)$를 이용해 아래와 같이 계산가능하다.

$c_2=e_2^{r}mmodp$

$e_2^r=c_2{m}^{-1}modp$

이때 공격자는 자신이 원하는 $m^{\ast }$에 대해 아래와 같은 과정을 통해 알 수 있다.

$c_1^{\ast }=e_1^{r}modp$

$c_2^{\ast }=e_2^r{m}^{\ast }modp$

일 때 이미 계산해둔 정보를 통해 아래와 같이 계산하여 $m^{\ast }$를 얻을 수 있다.

$(e_2^r{)}^{-1}{c}_2^{=}{m}^{\ast }modp$

 

방법 2

$[m]$
1) $C_1=e_1^{r}modp$

2) $C_2=e_2^r\ast mmodp$

$[m^{\prime }]$
1) $C_1^{\prime }=e_1^{r}modp$

2) $C_2^{\prime }=e_2^r\ast m^{\prime }modp$

$\therefore \frac{C_2}{C_2‘}=\frac{e_2^{r}mmodp}{e_2^r{m}^{\prime }modp}$

attacker가 m를 알고 동일한 r값이 쓰였다면 m'을 알게 되는 것과 같아지기 때문에 Elgamal은 KPA 공격에 안전하지 않다.