RSA란?
글을 쓰는 이 시점에서 가장 알려져있고 널리 쓰이는 공개키 알고리즘이다.
이는 어려운 수학적 문제(큰 수의 소인수 분해)에 기반하여 만들어진 알고리즘으로 만약 이 문제가 나중에 쉽게 풀리게 된다면 대체될 수 있다.
원리
먼저 원리를 알기 전에, 오일러 정리를 알아야 한다.
오일러 정리
증명에 대한 부분은 생략하고 단순히 정리의 내용만 다루자면 아래와 같다.
\(a\) 와 \(n\) 이 서로 소인 양의 정수일 때, \(a^{\phi(n)} \equiv 1 (mod n)\)를 만족한다.
여기서 나오는 \(\phi(n)\) 은 1부터 n까지의 정수 중 n과 서로소인 정수의 개수를 뜻하는 오일러 파이 함수이다.
공개키, 비밀키 생성
먼저 아주 큰 소수 \(p\) 와 \(q\) 를 생성한다.
이후 \(n = p \times q\) 라고 하자.
이때, \(\phi(n) = (p-1) \times (q-1)\) 이 된다.
이 이유를 간단히 설명하자면,
\[\{\text{x는 2부터 p * q 까지의 수}\} - \{\text{p * q와 서로 소가 아닌 수}\} = \] \[ \{\text{x는 2부터 p * q 까지의 수}\} - \{\text{p * (1에서 q-1까지)}\} - \{\text{q * (1에서 p-1까지)}\} \] \[ (p \times q - 1) - (p-1) - (q-1) = (p-1) \times (q-1)\]이때, \(1 < e < \phi(n),\ gcd(e, \phi(n)) = 1\) 을 만족하는 e를 구한다.
그리고 \(e \times d \equiv 1 \pmod{\phi(n)}\) 인 d를 구한다.
이때, 공개키는 \(\{e, n\}\) 비밀키는 \(\{d, n\}\) 이 된다.
공개키로 암호화, 비밀키로 복호화
이제 메세지 M 을 암호화 한다고 해보자. 일반적으론 대칭키를 세션키로 사용해 암호화하는 것이 성능에 좋지만 일단 메세지를 직접 암호화하는 과정을 보자.
공개키는 \(K^+\), 비밀키는 \(K^-\) 라고 하겠다.
M을 byte sequence로 보면, 하나의 긴 숫자로 변한다.
이 값을 공개키로 암호화했다고 했을때, \(K^+(M) = M^e \bmod n\) 이 된다.
이제 \(K^-(K^+(M))\) 이 왜 \(M\) 이 되는지 보면 된다.
\[K^-(K^+(M)) = \] \[ (M^e \bmod n)^d \bmod n = \] \[ M^{e\times d} \bmod n\]이때 \(e\times d \equiv 1 \pmod{\phi(n)}\) 이므로 \(e\times d = k \times \phi(n) + 1\) 이 된다. 따라서
\[M^{k\times \phi(n) + 1} \bmod n = \] \[ (M \bmod n) \times (M^{k \times \phi(n)} \bmod n) \bmod n = \] \[ (M \bmod n) \times (M^{\phi(n)} \bmod n)^k \bmod n\]근데 여기서 오일러 정리가 마법같이 적용되서 \(M^{\phi(n)} \bmod n\) 가 \(1\)이 되버린다.
따라서 우린 \(M \bmod n\) 을 구했다!
여기서 알 수 있듯 \(M\) 은 \(n\) 보다 작아야 한다. Modulo 연산에서 빠져 나와야 하기 때문이다. 따라서 M이 너무 크다면 block 단위로 잘라서 암호화를 해야 한다.
추가적으로 서명 과정인 비밀키로 암호화, 공개키로 복호화를 진행해도 같은 방식으로 \(M\) 이 튀어 나온다.
상당히 비싼 작업
위에서 봤겠지만 \(M\) 이 긴 영상과 같은 큰 데이터라면 많은 block에 대해 지수연산을 해야 하기 때문에 상당히 오래 걸린다.
따라서 대칭키를 생성하여 상대방의 공개키로 암호화하여 보낸 뒤, 해당 대칭키로 M을 암호화하여 보내는 것이 효율적이다.
또 서명에 대해서도 \(M\) 을 해쉬 함수에 넣어 일정 길이로 압축 시킨 뒤에 비밀키로 암호화 하는 것이 성능과 용량을 둘 다 잡을 수 있는 방법이다.
\[\]