5 RSA
================
RSA 공개 키 암호 시스템 1 (RSA public-key cryptosystem)
이 알고리즘은 보안 기법중 하나로 가장 흔한 예시로서는 공인인증서가 있다.
\(A \longrightarrow B\) \(A\)가 \(B\)에게 숫자를 하나 보낸다고 생각 해보자.
\(A\)에게는 공개키가 필요하며 \(B\)에게는 개인키가 있어야한다. 공개키는 누가
가져도 상관없는 키이며 개인키는 절대로 노출되어서는 안되는 키이다.
\(A\)는 \(B\)에게 \(a\)를 보낼때 공개키를 이용하여 \(a\)를 \(c\)로 암호화 하여
보내며 \(B\)는 \(c\)를 공개키와 개인키를 이용하여 \(a\)로 복호화하여 읽는
방식이다.
공개키, 암호키 생성
두 개의 소수 \(p,q\)를 선택하여 \(n=pq\)를 계산한다. 2 그 후 \(\phi =(p-1)(q-1)\)을 계산하고 \(\gcd(n,\phi)=1\)인 정수 \(e\)을 선택한다. 그후 \(n\)과 \(e\)를 공개한다. \(ed\bmod \phi =1\)이고 \(0<d<\phi\)를 만족시키는 \(d\)를 생성하여 \(d\)를 개인키로 사용한다. 3\
단계
\(A\)가 \(B\)에게 정수 \(a(0\le a\le z-1)\)를 보내기 위해서 \(A\)는 \(c=a^e \bmod n\) 를 계산하여 \(c\)를 보낸다. 4 \(B\)는 \(c^d \bmod n\)를 계산하면 이 값이 \(a\)이다.\
복호화 과정
\[\phi(n) = \phi\]\(ed\bmod \phi =1 \Longleftrightarrow ed = b\phi(n)+1\)(\(b\)는 어떤 상수)
\[\begin{aligned} c^d \bmod n &=(a^e \bmod n)^d \bmod n \\ &=(a^e)^d \bmod n = a^{ed} \bmod n \\ &= a^{b\phi(n)+1}\bmod n \\ &= (a^{\phi(n)} \bmod n)^{b} a \bmod n =a \end{aligned}\]이게 과연 안전한가?
이를 구하기위한 해결방법은 결과적으로 소인수분해와 직결되는데 그냥 n을 p와 q로소인수 분해해버리면 끝난다. 그러나 소인수분해를 다항시간내에하는 알고리즘은 개발되지 않았다.
advanced RSA
오리지널은 위와 같지만 PKCS#1 (en) v2.0에 표준 RSA 알고리즘 방식이 바뀌었다. \(\phi\) 대신 \(\lambda\)를 사용하는 방법이다. \(\lambda\)를 사용했을때, \(\phi\)일때보다 개인키의 범위가 작아지기 때문에 큰값을 가지지 않아도 되기때문이다.