For a better world

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\leq d\leq p-2$의 범위에서 임의의 d를 선택한다.

3. $Z_p^*$에서 임의의 원시근 $e_1$을 선택한다.

4. $e_2=e_1^d\ mod\ p$를 계산한다.

암호화

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

2. $c_1=e_1^r\ mod\ p$를 계산

3. $c_2=e_2^rm\ mod\ p$를 계산

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

복호화

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

$c_2(c_1^d)^{-1}\ mod\ p$

= $c_2e_1^{-rd}\ mod\ p$

= $e_2^rm*e_1^{-rd}\ mod\ p$

= $e_1^{rd}me_1^{-rd}\ mod\ p$

= $m\ mod\ p$

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

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

방법 1

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

$c_2=e_2^rm\ mod\ p$

$e_2^r=c_2m^{-1}\ mod\ p$

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

$c_1^*= e_1^r\ mod\ p$

$c_2^*=e_2^rm^*\ mod\ p$

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

$(e_2^r)^{-1}c_2^ = m^*\ mod\ p$

방법 2

$[m]$
1) $C_1=e_1^r\ mod\ p$

2) $C_2 = e_2^r*m\ mod\ p$

$[m']$
1) $C_1'=e_1^r\ mod\ p$

2) $C_2'=e_2^r*m'\ mod\ p$

$\therefore {C_2\over C_2`}={{e_2^rm\ mod\ p}\over {e_2^rm'\ mod\ p}}$

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