[정보보안] 비대칭키 암호 - RSA

1. RSA 알고리즘

RSA는 1977년 MIT의 Rivest, Shamir, Adleman에 의해 제안된 비대칭키 암호 체계이다. RSA는 소수(Prime)를 Modulo 하는 유한체(Galois Field) 상의 지수 연산을 기반으로 설계되었다.

• 연산 효율성: 암호화와 복호화에 사용되는 지수 연산은 $O((\log n)^3)$의 다항 시간 복잡도를 가져 매우 효율적인 구조다.
• 보안성: RSA의 안전성은 거대 정수의 소인수분해가 계산적으로 매우 어렵다는 점($O(e^{\log n \log \log n})$)에 근거한다. 일반적으로 1024비트 이상의 큰 정수를 사용하여 보안을 강화한다.

[RSA 구조]

RSA는 두가지 대수적 구조를 병행해서 사용한다. e는 공개키이고, d는 개인키이다.

• 암호화/복호화 링(Ring): $R = <Z_n, +, \times>$ 구조에서 실제 연산이 이루어진다.
• 키 생성 그룹(Group): $G = <Z_{\phi(n)}^*, \times>$ 구조에서 키 계산이 수행된다.

[Ring과 Group, $\phi(n)$ ]

• Ring, $R = <Z_n, +, \times>$: 정수 집합 $Z_n = \{0, 1, 2, \dots, n-1\}$ 위에서 덧셈($+$)과 곱셈($\times$)이라는 두 가지 이항 연산이 정의된 구조, 암호화($C = M^e \pmod n$)와 복호화($M = C^d \pmod n$) 과정의 모든 산술 연산은 이 Ring 안에서 수행된다.
• Group, $Z_{\phi(n)}^*$: $1$부터 $\phi(n)-1$ 사이의 정수 중 $\phi(n)$과 서로소인 원소들의 집합이며, 곱셈 연산에 대해 닫혀 있다. Group의 정의에 따라, 모든 원소는 반드시 곱셈에 대한 역원을 가진다. 이는 RSA에서 공개 지수 $e$로부터 개인 지수 $d$를 계산할 수 있는 수학적 토대가 된다. 공개키 $e$와 개인키 $d$ 사이의 관계인 $ed \equiv 1 \pmod{\phi(n)}$ 연산이 바로 이 군 안에서 정의된다.
• 오일러 파이 함수, $\phi(n)$: $1$부터 $n$까지의 자연수 중 $n$과 서로소인 수의 개수를 의미한다. $n = p \times q$ (단, $p, q$는 소수)일 때, $\phi(n) = (p-1)(q-1)$로 매우 쉽게 계산된다.

공격자(Eve)가 암호문 $C$로부터 평문 $M$을 얻으려면 $\sqrt[e]{C} \pmod n$을 계산해야 하는데, 이는 지수 시간 복잡도를 갖는 매우 어려운 문제이다. RSA는 이 보안성 큰 수 $n$을 두 소수 $p, q$로 분해하는 소인수분해 문제의 어려움을 이용하는 것이다..

---

2. RSA 키 생성

RSA에 필요한 키는 N, e, d이다. 암호화 키는 <N, e>로 공개하고, 복호화키 <N, d>는 개인이 가지고 있는다.

 

예를 들어보자. n=33, e=3, d=7일 때 예제이다.

[암호화]

n = 33, e=3일 때 평문 9를 암호화하려고한다면 $9^{3} % 33 = 3$이 되어서 3이 암호문이 된다.

 

[복호화]

n=33, d=7이고 암호문 3이 전달 되었을 때 $3^7 % 33=9$여서 9를 복호화할 수 있다.

 

그럼 이 $N, e, d$는 어떻게 생성해야할까?

과정	예시
1. 두 개의 소수 p, q를 정한다. 2. 두 소수의 곱을 $N$으로 한다. (N = pq) 3. N의 오일러 파이 함수값($\phi(N)$)을 계산한다. 4. 다음을 만족하는 수를 $e$로 한다.      $\phi(N)$보다 작고, $\phi(N)$과 서로소인 자연수 5. 다음을 만족하는 수를 $d$로 한다.      $ed$를 $\phi(N)$으로 나눴을 때, 나머지가 $1$이 된다.      즉, $e \cdot d \equiv 1 \pmod{\phi(n)}$이 되어야한다.       $e \cdot d = k \cdot \phi(n) + 1$ (단, $k$는 정수)이다.	1. p=3, q=11 2. $N=33$, (N=pq) 3. $\phi(33)=(3-1)*(11-1)=2*10=20$ 4. e = 20보다 작고, 20과 서로소인 자연수, 임의로 $e=3$ 선택 5. $3d \div 20$의 나머지가 1이 되는 $d$     $3d = 20k + 1$를 만족하는 $d$는 k=1일 때 $d=7$이 된다. 따라서 공개키와 비밀키는 아래와 같이 된다. 공개키 PU = <N, e> = <33, 3> 개인키 PR = <N, d> = <33, 7>            PR = <d, p, q> = <7, 3, 11> 이렇게 공개하기도 한다.

이렇게 공개키와 개인키를 만든 후에는 보안을 위해서 p, q는 폐기한다. 공개키와 개인키만 가지고 있으면 된다.

 

---

3. RSA 암호화 복호화

공개키로 PU = <n, e>, 개인키로 PR = <n, d>가 왔을 때 각각의 암호화, 복호화는 아래와 같이 계산한다. 

 

 

암호화 (Sender): 송신자는 평문 $M$을 수신자의 공개키 $e$만큼 거듭제곱한 후 $n$으로 나눈 나머지(모듈로 연산)를 한다.

$$C = M^e \pmod n$$

 

복호화 (Receiver): 수신자는 암호문 $C$를 자신의 개인키 $d$만큼 거듭제곱한 후 $n$으로 나눈 나머지를 구하여 원래의 평문 $M$을 복원한다.

$$M = C^d \pmod n$$

 

복호화 식이 이렇게 되는 이유가 바로 오일러 정리 때문이다. 복호화 과정인 $C^d \pmod n$을 전개하면 다음과 같다.

$$C^d \equiv (M^e)^d \equiv M^{ed} \equiv M^{k \cdot \phi(n) + 1} \equiv (M^{\phi(n)})^k \cdot M^1 \pmod n$$

오일러 정리에 의해 $M^{\phi(n)} \equiv 1$이므로, 결과적으로 $1^k \cdot M \equiv M$이 되어 원래의 메시지 $M$이 복원되는 것이다.

 

 

예시를 들어보자. 공개키, PU = <n, e> = <187, 7>이고, 개인키 PR = <d, p, q> = <23, 17, 11> 일 때 아래와 같이 암복호화된다.