For a better world

디피헬만 키 교환 프로토콜의 경우 간단한 형태이다. 예시를 들자면 A, B가 있을 때 A는 B에게 3을 보내고 B는 6에게 보냈다고 할 경우 서로 3과 6을 곱한 값인 18을 세션키로 사용하는 것과 같다.

세션키를 만들기 위해 각자의 개인키를 g의 승수로 취해 모듈러 연산을 한 다음 보낸다. Bob는 세션키를 생성하기 위해 Alice로부터 받은 $R_1$에 자신의 개인키인 $y$를 곱해주고,  Alice는 세션키를 생성하기 위해 해 Bob으로부터 받은 $R_2$에 자신의 개인키인 $x$를 곱하여 같은 세션키를 사용한다.

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에 대응하는 역원
을 곱하면 됨.

현대암호학에서 사용되는 블록 암호 운용 방식은 크게 5가지가 존재한다.

5가지를 확인하기 이전 핵심에 대한 이해를 위한 키워드는 다음과 같다.

Keyword: 개념, 암호화, 복호화, 장단점, 블록재사용, 병렬처리, 에러전파

1. ECB(Electronic Code Book)

ECB는 운용모드중 가장 간단한 형태로 암호화와 복호화가 독립적으로 이루어진다. 때문에 병렬처리가 가능하다는 장점이 있다. 반면 블록의 암호화와 복호화에 사용하는 키가 같기 때문에 같은 평문에 대해 같은 암호문이 나온다는 단점이 있다. 때문에 블록재사용과 같은 취약점이 발생할 수 있다. 암호문 생성 또는 전송 중에 에러가 발생할 수 있다. 이러한 에러에 있어서 ECB는 독립적으로 암복호화되기 때문에 다른 블록으로 에러가 전파되지 않고 에러가 발생한 블록만 영향을 받는다.

2. CBC (Cipher Block Chaining)

CBC 운용모드는 ECB 운용모드의 취약점을 극복하기 위해 나온 것이다. 한 블록의 평문을 암호화하기 이전에, 이전의 평문이 암호화된 암호문과 XOR 연산을 하는 것이 특징이다. 맨 앞의 블록의 경우 이전의 암호문이 없기 때문에 IV (Initial Vector)를 사용하여 랜덤 초기화를 하는 것이 특징이다. CBC의 경우 암호화때는 병렬처리가 불가능하지만 복호화시에는 병렬처리가 가능하다. 에러전파의 경우 복호화시 암호문 $C_1$에 에러가 발생하면 $P_1$, $P_{i+1}$블록에 영향을 미치고 $P_{i+2}$블록 부터는 자기 복구(self recovering)을 통해 올바르게 동작한다.

3. CFB (Cipher FeedBack)

CFB 운용모드는 블록암호를 스트림암호로 변환한다. 평문과 이전 암호문이 암호화된 값과 XOR 연산을 통해 암호문이 생성된다. 초기에는 IV 값을 암호화하고 평문과 xor하여 암호문을 생성하는 것이 특징이다. CFB 운용모드는 평문과 암호문의 길이가 같아 별도의 정수배를 맞추는 패딩이 필요하지 않다. 복호화시에는 암호문을 알고있다는 가정하에 병렬처리가 가능하다. 에러전파는 CBC와 마찬가지로 암호문에 에러가 발생하면 해당 암호문에 해당하는 평문과 다음 평문에 영향을 미치게 되는 것이 특징이다.

4. OFB (Output FeedBack)

OFB 운용모드는 블록암호를 스트림암호로 변환한다. 평문과 암호문의 길이가 같아 패딩이 필요하지 않다. 동작 방식은 이전의 암호화된 값이 다시 암호화되어 평문과 XOR하여 암호문을 만들어낸다. 초기에는 IV 값을 암호화하여 평문과 다시 XOR한 뒤 암호문을 생성한다. 암호화와 복호화 과정이 동일하다는 특징을 가진다. OFB 모드에서는 평문과 관계없이 암호 알고리즘을 미리 돌려 XOR하기 위한 키스트림을 준비할 수 있는 것이 특징이다. 암호문에 1비트의 문제가 발생하면 대응되는 평문에 1비트의 에러가 발생한다.

5. CTR (CounTeR)

CTR 운용모드는 평문과 암호문의 길이가 같아 패딩이 필요하지 않다. 암호화와 복호화과정이 동일하다. 임의로 순서로 암호화와 복호화가 가능하다. Nonce와 Counter를 암호화하고 평문과 XOR하여 암호문을 만드는 것이 특징이다. 동일한 비밀키와 IV를 반복하여 사용할 경우 안전성에 문제가 생길 수 있다. 이러한 과정은 독립적으로 진행되어 병렬처리가 가능하다는 것이 특징이다. 암호문에 1비트의 문제가 발생하면 대응되는 평문에 1비트의 에러가 발생한다. EBC 모드 처럼 한 블록에서 생긴 에러가 다음 블록으로 전파 되지 않는다.