[암호학] RSA 알고리즘과 선택암호문공격(CCA)

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