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 공격에 안전하지 않다.

1. RSA 알고리즘 개요

공개키 암호에는 대표적으로 RSA 암호가 일반적으로 사용된다. 하지만 RSA 알고리즘의 경우 수학적으로 안정성이 검증되지 않았고, 취약점이 나올 경우 거기에 맞춰 알고리즘을 수정하는 방식을 사용한다고 한다. 기본적으로 RSA 알고리즘은 같은 메시지에 대해서 같은 암호문을 생성하는 결정적인 특징을 가진다. 이를 방지하고자 확률적인 특징을 가지도록 하기 위해 고정패딩과 랜덤패딩을 붙이는 RSA-OAEP 방식을 사용한다. RSA-OAEP는 RSA 알고리즘의 취약점 중 하나인 CCA(선택암호문공격)에 안전하다는 것이 특징이다. RSA 암호이외에도 레빈 암호 시스템이 있다. 이는 수학적으로 안정성이 검증되었고 RSA보다 뛰어난 것으로 판단되었지만 RSA 암호보다 유명세를 타지 못해 별로 사용되지 않는 것이라 한다.

2. RSA 알고리즘

절차

(1) 서로 다른 두 소수 $p, q$를 선택
(2) $p$와 $q$를 곱하여 $n=p*q$를 계산
(3) $\phi(n) = (p-1)(q-1)$을 계산
(4) $1<e<\phi(n)-1$의 범위에서 공개키 $e$를 선택
(5) $d=e^{-1}\ mod\ \phi(n)$을 통해 비밀키 $d$를 계산
——————————
public key = $(n, e)$
private key = $(d)$
검증키 = $(n,e)$
서명키 = $(d)$

암호화 (Encryption)

$C \equiv m^e\ mod\ n$

복호화 (Decryption)

$m \equiv C^d\ mod\ n$

서명 (Signing)

$S \equiv H(m)^d\ mod\ n$ // $H()$ is hash function

검증 (Verification)

check if $S^e \equiv H(m)\ mod\ n$

$S^e \equiv (H(m)^d)^e\equiv H(m)$

= $m$과 $s$가, 검증키 $(e,n)$을 이용하여 $s^e\ mod\ n = m$이 되는지 확인.

3. RSA 알고리즘에 대한 선택암호문공격

1. $c = m^e\ mod\ n$이 주어짐.

2. 공격자는 $gcd(r,n)=1$이면서 $r\in(0,n-1)$을 선택

3. 공격자는 공개키 r을 이용하여 암호화하여 $c^*\equiv\ r^ec\ mod\ n$을 생성

4. 복호화 오라클로 전송하여 $c^{*d}\equiv\ ({r^ec})^d\ mod\ n$을 받음

5. $c^{*d}\equiv\ rc^d\ mod\ n$

6. $c^{*d}\equiv r(m^c)^d\ mod\ n$

7. $c^{*d} \equiv\ rm\ mod\ n$

8. $c^{*d}r^{-1} \equiv m\ mod\ n$을 통해 m을 구할 수 있음. 공격자는 자신이 선택한 r에 대응하는 역원
을 곱하면 됨.