RSA 암호화리즘

## 개요

RSA 공개키 암호화(Public-keyography)의 대표적인 알고리 중 하나로, 177년 로널드 리베스트(R Rivest), 아디 샤미르(Adi Shamir), 레오날드 애들먼(Leonard Adleman)이 제안하여 세 사람의 이름 첫 글자를 따서 명명된 알고리즘이다. RSA는 정보의 기밀성, 인증, 디지털 서명 등 다양한 보안 목적에 활용되며, 인터넷 통신, 전자상거래, SSL/TLS 프로토콜 등에서 널리 사용되고 있다.

RSA의 핵심 원리는 소인수분해의 어려움에 기반한다. 즉, 두 개의 큰 소수를 곱하는 것은 계산이 쉬우나, 그 곱으로부터 원래의 소수를 다시 찾아내는 것은 계산상 매우 어려운 문제라는 점을 이용한다. 이 수학적 특성 덕분에 RSA는 오랜 기간 동안 안전한 암호 체계로 인정받아 왔다.

---

## 원리와 작동 방식

### 1. 키 생성 (Key Generation)

RSA는 공개키(Public Key)와 개인키(Private Key)의 쌍을 사용한다. 키 생성 과정은 다음과 같다:

1. **두 개의 큰 소수 선택**: 서로 다른 두 소수 \( p \)와 \( q \)를 선택한다.
2. **모듈러스 \( n \) 계산**: \( n = p \times q \)를 계산한다. 이 \( n \)은 공개키와 개인키 모두에 사용된다.
3. **오일러 파이 함수 \( \phi(n) \) 계산**: \( \phi(n) = (p-1)(q-1) \)를 구한다.
4. **공개키 지수 \( e \) 선택**: \( 1 < e < \phi(n) \)이고, \( e \)와 \( \phi(n) \)이 서로소(coprime)인 정수를 선택한다. 일반적으로 \( e = 65537 \)이 자주 사용된다.
5. **개인키 지수 \( d \) 계산**: \( d \times e \equiv 1 \mod \phi(n) \)을 만족하는 \( d \)를 계산한다. 이는 확장 유클리드 알고리즘을 통해 구할 수 있다.

최종적으로:
- **공개키**: \( (e, n) \)
- **개인키**: \( (d, n) \)

### 2. 암호화 (Encryption)

메시지 \( m \)을 암호화할 때는 수신자의 공개키 \( (e, n) \)을 사용하여 다음과 같이 계산한다:

\[
c = m^e \mod n
\]

여기서 \( c \)는 암호문(Ciphertext)이다.

### 3. 복호화 (Decryption)

수신자는 자신의 개인키 \( (d, n) \)을 사용하여 암호문을 복호화한다:

\[
m = c^d \mod n
\]

이 과정을 통해 원래의 메시지 \( m \)이 복원된다.

---

## 수학적 기반

RSA의 보안성은 **소인수분해 문제**(Integer Factorization Problem)에 의존한다. 즉, 큰 수 \( n \)을 \( p \)와 \( q \)로 분해하는 것이 계산적으로 어렵기 때문에, 공격자가 공개키 \( (e, n) \)만으로는 개인키 \( d \)를 유추하기 어렵다.

또한 RSA는 **오일러의 정리**(Euler's Theorem)를 기반으로 한다. 오일러 정리에 따르면, \( a \)와 \( n \)이 서로소일 때 다음이 성립한다:

\[
a^{\phi(n)} \equiv 1 \mod n
\]

이 정리를 통해 \( m^{ed} \equiv m \mod n \)이 성립하게 되고, 복호화가 정확하게 이루어진다.

---

## 응용 분야

RSA는 다음과 같은 다양한 분야에서 사용된다:

- **SSL/TLS 프로토콜**: 웹 브라우저와 서버 간의 안전한 통신에서 인증 및 키 교환에 사용.
- **전자서명**: 문서나 메시지에 대한 진위 확인을 위해 개인키로 서명하고, 공개키로 검증.
- **이메일 암호화**: S/MIME, PGP 등에서 메시지의 기밀성 보장.
- **소프트웨어 인증**: 코드 서명을 통해 소프트웨어의 무결성과 출처 확인.

---

## 보안 고려사항

### 1. 키 길이

RSA의 보안성은 키 길이에 크게 영향을 받는다. 현재로서는 **2048비트 이상의 키**를 사용하는 것이 권장되며, 1024비트 키는 점차 취약해지고 있어 사용이 줄어들고 있다. 4096비트 키는 더 높은 보안을 제공하지만, 성능 저하가 발생할 수 있다.

### 2. 공격 방식

- **소인수분해 공격**: \( n \)을 분해하여 \( p \)와 \( q \)를 구하는 공격. 양자컴퓨팅 시대의 도래로 위협이 증가하고 있음.
- **타이밍 공격**(Timing Attack): 복호화 시간을 분석하여 키를 추정.
- **선택 암호문 공격**(Chosen Ciphertext Attack): 공격자가 암호문을 선택하여 복호화 결과를 관찰.

이러한 공격을 방지하기 위해 **OAEP**(Optimal Asymmetric Encryption Padding)와 같은 안전한 패딩 방식이 사용된다.

---

## 양자컴퓨팅 시대의 전망

쇼어 알고리즘(Shor's Algorithm)과 같은 양자 알고리즘은 소인수분해를 다항 시간 내에 해결할 수 있어, RSA의 기반이 되는 수학적 난제를 무력화시킬 가능성이 있다. 따라서 **양자내성 암호**(Post-Quantum Cryptography) 연구가 활발히 진행 중이며, 향후 RSA는 점차 다른 알고리즘으로 대체될 전망이다.

---

## 관련 표준 및 알고리즘

| 표준/알고리즘 | 설명 |
|---------------|------|
| PKCS #1       | RSA 암호화 및 전자서명을 위한 공식 표준 |
| FIPS 186-4    | 디지털 서명 표준(DSS)에서 RSA 사용 규정 |
| OAEP          | RSA 암호화 시 보안성을 높이기 위한 패딩 방식 |

---

## 참고 자료

- Rivest, R. L., Shamir, A., & Adleman, L. (1978). "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems". *Communications of the ACM*.
- NIST Special Publication 800-56B: Recommendation for Pair-Wise Key Establishment Schemes Using Integer Factorization Cryptography.
- RFC 8017: PKCS #1: RSA Cryptography Specifications Version 2.2.

RSA는 현대 암호학의 기초를 다진 중요한 알고리즘으로, 여전히 널리 사용되지만, 보 환경의 변화에 따라 새로운 기술로의 전환이 필요한 시점에 도달하고 있다.