RSA 암호

1. 개요#

RSA 암호(RSA cryptosystem)는 1977년 론 라이베스트(Ron Rivest), 아디 샤미르(Adi Shamir), 레너드 애들먼(Leonard Adleman) 세 사람이 개발한 공개키 암호 시스템이다.

현대 인터넷 보안의 근간을 이루는 암호화 기술로, HTTPS, SSL/TLS, 전자서명, VPN 등 우리가 매일 사용하는 수많은 보안 시스템에서 활용되고 있다.

RSA의 가장 큰 특징은 암호화 키와 복호화 키가 서로 다르다는 것이다. 기존의 대칭키 암호와 달리, 공개키로 암호화한 데이터는 오직 대응하는 개인키로만 복호화할 수 있다. 이 혁신적인 아이디어 덕분에 사전에 비밀 키를 교환할 필요 없이 안전하게 통신할 수 있게 되었다.

2. 역사#

2.1 탄생 배경#

1976년, 위트필드 디피(Whitfield Diffie)와 마틴 헬먼(Martin Hellman)이 혁명적인 논문 "New Directions in Cryptography"를 발표하면서 공개키 암호라는 개념을 처음 제시했다. 그러나 이들은 구체적인 구현 방법은 제시하지 못했다.

2.2 RSA의 탄생#

1977년, MIT의 세 교수가 이 문제를 해결했다. 론 라이베스트가 알고리즘을 고안했고, 아디 샤미르가 수학적 증명을 담당했으며, 레너드 애들먼은 보안성을 분석했다.

재미있는 일화가 있다. 라이베스트는 1977년 유월절 전날 밤, 친구들과 와인을 마신 후 집에 돌아와 소파에 누워 있다가 갑자기 RSA 알고리즘을 떠올렸다고 한다. 그는 새벽까지 논문을 완성했고, 이것이 암호학 역사상 가장 중요한 논문 중 하나가 되었다.

2.3 특허와 공개#

RSA 알고리즘은 1983년 미국에서 특허를 받았고(US 4,405,829), 2000년 9월 특허가 만료되었다. 특허 기간 동안 RSA Security라는 회사가 라이선스를 관리했으며, 상당한 수익을 올렸다.

한편 영국의 GCHQ(정보통신본부)에서는 RSA보다 4년 먼저 같은 원리의 암호를 개발했다는 사실이 1997년에 공개되었다. 제임스 엘리스, 클리퍼드 콕스, 말콤 윌리엄슨이 1973년에 이미 공개키 암호를 개발했지만, 군사 기밀로 분류되어 공개되지 못했다.

3. 작동 원리#

RSA는 큰 소수의 곱셈은 쉽지만, 그 결과를 다시 소인수분해하는 것은 매우 어렵다는 수학적 난제를 기반으로 한다.

3.1 기본 개념#

RSA는 다음과 같은 특징을 가진다:

• 공개키(Public Key): 누구에게나 공개되며, 데이터를 암호화하는 데 사용
• 개인키(Private Key): 자신만 가지고 있으며, 데이터를 복호화하는 데 사용
• 공개키로 암호화한 것은 대응하는 개인키로만 복호화 가능
• 개인키로 서명한 것은 대응하는 공개키로만 검증 가능

3.2 키 생성 과정#

RSA 키를 생성하는 과정은 다음과 같다:

1단계: 두 개의 큰 소수 선택

• 서로 다른 두 개의 큰 소수 p와 q를 무작위로 선택한다.
• 예시: p = 61, q = 53

2단계: n 계산

• n = p × q를 계산한다.
• 예시: n = 61 × 53 = 3233
• 이 n이 RSA 모듈러스(RSA modulus)라고 불리며, 공개키와 개인키 모두에 포함된다.

3단계: 오일러 함수 φ(n) 계산

• φ(n) = (p-1) × (q-1)을 계산한다.
• 예시: φ(3233) = 60 × 52 = 3120
• φ(n)은 n보다 작으면서 n과 서로소인 양의 정수의 개수를 의미한다.

4단계: 공개 지수 e 선택

• 1 < e < φ(n)이면서 φ(n)과 서로소인 정수 e를 선택한다.
• 보통 e = 65537 (= 2^16 + 1)을 많이 사용한다.
• 예시: e = 17

5단계: 개인 지수 d 계산

• d × e ≡ 1 (mod φ(n))을 만족하는 d를 구한다.
• 즉, d는 e의 모듈러 역원이다.
• 확장 유클리드 호제법을 사용하여 계산한다.
• 예시: d = 2753

6단계: 키 생성 완료

• 공개키: (n, e) = (3233, 17)
• 개인키: (n, d) = (3233, 2753)
• p, q, φ(n)은 반드시 폐기해야 한다!

3.3 암호화 과정#

평문 메시지 M을 암호화하여 암호문 C를 만드는 과정:

수식: C ≡ M^e (mod n)

예시:

• 평문: M = 123
• 공개키: (n=3233, e=17)
• 암호화: C = 123^17 mod 3233 = 855

이제 누구든 공개키 (3233, 17)을 알면 메시지를 암호화할 수 있지만, 개인키 없이는 복호화할 수 없다!

실제 계산 과정: 123^17 mod 3233을 직접 계산하는 것은 비효율적이다. 대신 제곱-곱셈 알고리즘(Square-and-Multiply)을 사용한다:

• 17 = 2^4 + 2^0 = 16 + 1
• 123^17 = 123^16 × 123^1
• 123^2 mod 3233 = 15129 mod 3233 = 1926
• 123^4 mod 3233 = 1926^2 mod 3233 = 2830
• 123^8 mod 3233 = 2830^2 mod 3233 = 2746
• 123^16 mod 3233 = 2746^2 mod 3233 = 2728
• 123^17 mod 3233 = 2728 × 123 mod 3233 = 855

3.4 복호화 과정#

암호문 C를 복호화하여 평문 M을 복원하는 과정:

수식: M ≡ C^d (mod n)

예시:

• 암호문: C = 855
• 개인키: (n=3233, d=2753)
• 복호화: M = 855^2753 mod 3233 = 123

원래 평문 123이 복원되었다!

3.5 왜 작동하는가?#

RSA가 작동하는 이유는 페르마의 소정리와 오일러 정리에 기반한다.

수학적 증명:

• M^(ed) ≡ M (mod n)임을 증명해야 한다.
• d × e ≡ 1 (mod φ(n))이므로, d × e = 1 + k × φ(n) (k는 정수)
• 따라서 M^(ed) = M^(1 + k×φ(n)) = M × (M^φ(n))^k
• 오일러 정리에 의해 M^φ(n) ≡ 1 (mod n) (M과 n이 서로소일 때)
• 따라서 M^(ed) ≡ M × 1^k ≡ M (mod n)

이 증명은 M과 n이 서로소일 때 성립한다. 만약 M이 p나 q의 배수라면? 그래도 중국인의 나머지 정리를 사용하면 증명할 수 있다.

4. 구체적인 예제#

4.1 작은 숫자로 이해하기#

실제 상황에서는 수백 자리 숫자를 사용하지만, 원리를 이해하기 위해 작은 숫자로 예를 들어보자.

앨리스와 밥의 통신:

1. 밥의 키 생성

• 밥이 두 소수 선택: p = 3, q = 11
• n = 3 × 11 = 33
• φ(n) = 2 × 10 = 20
• 공개 지수 선택: e = 3 (20과 서로소)
• 개인 지수 계산: d = 7 (3 × 7 = 21 = 1 + 1×20)
• 밥의 공개키: (33, 3)
• 밥의 개인키: (33, 7)

2. 앨리스의 암호화

• 앨리스가 보낼 메시지: M = 4
• 밥의 공개키 (33, 3)으로 암호화
• C = 4^3 mod 33 = 64 mod 33 = 31

3. 밥의 복호화

• 받은 암호문: C = 31
• 밥의 개인키 (33, 7)로 복호화
• M = 31^7 mod 33 = ?

31^7을 계산해보자:

• 31^2 = 961 mod 33 = 4
• 31^4 = 4^2 = 16 mod 33 = 16
• 31^7 = 31^4 × 31^2 × 31 = 16 × 4 × 31 mod 33 = 1984 mod 33 = 4

원래 메시지 4가 복원되었다!

4.2 텍스트 암호화하기#

실제로 문자를 암호화하려면 어떻게 할까?

방법:

• 각 문자를 숫자로 변환 (예: A=01, B=02, ..., Z=26)
• 메시지 "HI"를 암호화한다면:
  • H = 08, I = 09 → 메시지 = 0809 또는 따로따로 암호화

예시 (키: n=3233, e=17, d=2753):

• 평문: "HI" = 08, 09
• 암호화:
  • 08^17 mod 3233 = 2082
  • 09^17 mod 3233 = 2489
• 암호문: [2082, 2489]
• 복호화:
  • 2082^2753 mod 3233 = 08
  • 2489^2753 mod 3233 = 09
• 평문: "HI" 복원!

실제 시스템에서는 텍스트를 바이너리로 변환하고, 패딩을 추가하며, 여러 블록으로 나누어 암호화한다.

5. 수학적 배경#

5.1 소인수분해의 어려움#

RSA의 보안성은 큰 수의 소인수분해가 어렵다는 데 기반한다.

예를 들어:

• 61 × 53 = 3233은 계산하기 쉽다. (1초도 안 걸림)
• 하지만 3233 = ? × ?를 알아내는 것은 상대적으로 어렵다.

만약 n이 수백 자리의 수라면?

• 곱셈: 매우 빠름 (다항 시간)
• 소인수분해: 매우 느림 (지수 시간)

예시:

• RSA-2048 (617자리 수)를 소인수분해하려면 현대 슈퍼컴퓨터로도 수천 년이 걸린다고 추정된다.

5.2 모듈러 산술#

RSA는 모듈러 연산(modular arithmetic)에 크게 의존한다.

기본 개념:

• a ≡ b (mod n): a를 n으로 나눈 나머지가 b를 n으로 나눈 나머지와 같다
• 예: 17 ≡ 5 (mod 12) (시계 산술과 같다)

중요한 성질:

• (a + b) mod n = ((a mod n) + (b mod n)) mod n
• (a × b) mod n = ((a mod n) × (b mod n)) mod n
• (a^k) mod n을 효율적으로 계산할 수 있다

5.3 오일러 정리#

오일러 정리: a와 n이 서로소이면, a^φ(n) ≡ 1 (mod n)

이것이 RSA가 작동하는 핵심 이유다!

특별한 경우 - 페르마의 소정리:

• n이 소수 p일 때, φ(p) = p-1
• 따라서 a^(p-1) ≡ 1 (mod p)
• 페르마가 발견한 아름다운 정리다.

5.4 중국인의 나머지 정리#

RSA 복호화를 빠르게 하기 위해 중국인의 나머지 정리(Chinese Remainder Theorem, CRT)를 사용한다.

기본 아이디어:

• M^d mod n을 직접 계산하는 대신
• M^d mod p와 M^d mod q를 각각 계산하고
• 결과를 결합한다

이렇게 하면 4배 정도 빠르다!

6. 보안성#

6.1 안전한 키 길이#

RSA의 보안성은 키의 길이에 크게 의존한다.

키 길이	보안 수준	상태
512비트	매우 약함	1999년 RSA-155 (512비트) 인수분해됨
768비트	약함	2009년 RSA-768 인수분해됨
1024비트	위험	2030년까지 안전하지 않을 것으로 예상
2048비트	안전	현재 권장 최소 길이
3072비트	매우 안전	2030년 이후 권장
4096비트	극도로 안전	장기 보안이 필요한 경우

NIST 권장사항 (2024년 기준):

• 2048비트: 2030년까지 사용 가능
• 3072비트: 2030년 이후 권장
• 4096비트: 최상위 보안이 필요한 경우

6.2 알려진 공격 방법#

6.2.1 1. 작은 소수 공격#

p나 q가 너무 작으면 쉽게 소인수분해된다.

방어: p와 q는 충분히 큰 소수를 사용해야 한다. (최소 1024비트)

6.2.2 2. 공통 모듈러스 공격#

같은 n을 여러 사용자가 공유하면 위험하다.

공격 시나리오:

• 앨리스와 밥이 같은 n을 사용하지만 다른 e, d를 사용
• 공격자가 두 공개키를 알면 개인키를 계산할 수 있다!

방어: 각 사용자는 자신만의 n을 생성해야 한다.

6.2.3 3. 작은 지수 공격#

공개 지수 e가 너무 작고 평문이 작으면 취약하다.

예시:

• e = 3이고 M^3 < n이면
• C = M^3이 되고, 단순히 세제곱근을 구하면 M을 알 수 있다!

방어: 패딩 스킴(OAEP 등)을 사용해야 한다.

6.2.4 4. 타이밍 공격#

복호화 시간을 측정하여 개인키를 추정하는 공격.

원리:

• 개인키의 비트에 따라 연산 시간이 달라진다
• 여러 번 측정하면 패턴을 찾을 수 있다

방어:

• 블라인딩(Blinding) 기법 사용
• 상수 시간 알고리즘 구현

6.2.5 5. 부채널 공격#

전력 소비, 전자기파 방출 등을 분석하여 키를 추정.

방어: 하드웨어 수준의 보안 조치 필요.

6.2.6 6. 소인수분해 알고리즘의 발전#

현재까지 알려진 최선의 소인수분해 알고리즘:

• 일반 수체 체 알고리즘(General Number Field Sieve, GNFS)
• 타원 곡선 인수분해(Elliptic Curve Factorization)

기록:

• 2020년 2월: RSA-250 (829비트) 인수분해 성공

6.3 양자 컴퓨터의 위협#

쇼어 알고리즘(Shor's Algorithm)은 양자 컴퓨터로 소인수분해를 다항 시간에 해결할 수 있다는 것을 보였다.

현재 상황:

• 2019년: IBM이 53큐비트 양자 컴퓨터 개발
• 2023년: IBM이 1121큐비트 Condor 프로세서 발표
• RSA-2048을 깨려면 수천~수만 큐비트가 필요할 것으로 추정

대응:

• 양자내성암호(Post-Quantum Cryptography, PQC) 개발 중
• NIST가 표준화 진행 중
• RSA를 대체할 새로운 암호 시스템 준비 중

7. 장점과 단점#

7.1 장점#

• 키 배송 문제 해결: 사전에 비밀 키를 공유할 필요가 없다
• 전자서명 가능: 개인키로 서명하고 공개키로 검증
• 널리 사용됨: 표준화되어 있고 검증된 기술
• 수학적으로 증명됨: 안전성이 수학적으로 근거가 있다

7.2 단점#

• 느린 속도: 대칭키 암호(AES 등)보다 100~1000배 느리다
• 키 크기: 같은 보안 수준을 위해 대칭키보다 훨씬 긴 키 필요
  • AES-128 = RSA-3072 수준
• 양자 컴퓨터에 취약: 쇼어 알고리즘으로 깨질 수 있다
• 구현 복잡도: 올바르게 구현하기 어렵다

7.3 하이브리드 암호화#

RSA의 단점을 극복하기 위해 하이브리드 암호화를 사용한다.

방법:

1. 세션 키(대칭키)를 무작위로 생성
2. 세션 키로 데이터를 AES 등으로 암호화 (빠름!)
3. 세션 키를 RSA로 암호화 (작은 데이터만)
4. 암호화된 데이터와 암호화된 세션 키를 전송

이렇게 하면 RSA의 보안성 + 대칭키의 속도를 모두 얻을 수 있다!

8. 활용 사례#

8.1 HTTPS / SSL/TLS#

웹사이트에 접속할 때 주소창에 자물쇠 아이콘이 보이는가? 그것이 바로 RSA가 작동하는 증거다.

과정:

1. 브라우저가 서버의 공개키를 받는다 (인증서에 포함)
2. 브라우저가 세션 키를 생성
3. 세션 키를 서버의 공개키로 암호화하여 전송
4. 서버가 개인키로 세션 키를 복호화
5. 이후 세션 키로 대칭키 암호화 통신

8.2 전자서명#

RSA는 암호화뿐만 아니라 전자서명에도 사용된다.

원리:

• 암호화와 반대로, 개인키로 "암호화"하고 공개키로 "복호화"
• 개인키를 가진 사람만 서명할 수 있다
• 누구나 공개키로 서명을 검증할 수 있다

실제 과정:

1. 문서의 해시(예: SHA-256)를 계산
2. 해시를 개인키로 "암호화" (서명)
3. 문서와 서명을 함께 전송
4. 수신자가 서명을 공개키로 "복호화"
5. 문서의 해시를 계산하여 비교

용도:

• 소프트웨어 배포 (코드 서명)
• 이메일 서명 (PGP, S/MIME)
• 문서 인증
• 블록체인 (비트코인은 RSA 대신 ECDSA를 사용하지만)

8.3 SSH#

리눅스/Unix 서버에 원격 접속할 때 사용하는 SSH도 RSA를 사용한다.

과정:

1. 서버의 공개키를 클라이언트에 등록 (또는 반대로)
2. RSA를 사용하여 세션 키 교환
3. 이후 대칭키 암호화로 통신

8.4 VPN#

VPN 연결 시 RSA로 안전한 터널을 구축한다.

8.5 암호화폐#

일부 암호화폐는 RSA를 사용하지만, 대부분은 더 효율적인 타원곡선 암호(ECC)를 선호한다.

8.6 전자상거래#

신용카드 정보 전송, 전자결제 시스템에서 RSA가 사용된다.

9. 구현#

9.1 프로그래밍 언어별 구현#

Python:

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

# 키 생성
key = RSA.generate(2048)
public_key = key.publickey()

# 암호화
cipher = PKCS1_OAEP.new(public_key)
ciphertext = cipher.encrypt(b"Hello RSA!")

# 복호화
decipher = PKCS1_OAEP.new(key)
plaintext = decipher.decrypt(ciphertext)

Java:

import java.security.*;
import javax.crypto.Cipher;

KeyPairGenerator keyGen = KeyPairGenerator.getInstance("RSA");
keyGen.initialize(2048);
KeyPair pair = keyGen.generateKeyPair();

Cipher cipher = Cipher.getInstance("RSA");
cipher.init(Cipher.ENCRYPT_MODE, pair.getPublic());
byte[] encrypted = cipher.doFinal("Hello RSA!".getBytes());

cipher.init(Cipher.DECRYPT_MODE, pair.getPrivate());
byte[] decrypted = cipher.doFinal(encrypted);

JavaScript (Node.js):

const crypto = require('crypto');

// 키 생성
const { publicKey, privateKey } = crypto.generateKeyPairSync('rsa', {
  modulusLength: 2048,
});

// 암호화
const encrypted = crypto.publicEncrypt(
  publicKey,
  Buffer.from('Hello RSA!')
);

// 복호화
const decrypted = crypto.privateDecrypt(privateKey, encrypted);

9.2 주의사항#

절대 직접 구현하지 마라!

• 타이밍 공격, 부채널 공격 등 고려할 게 너무 많다
• 패딩, 난수 생성 등을 잘못하면 보안이 무너진다
• 검증된 라이브러리를 사용하라
  • OpenSSL
  • PyCryptodome
  • Bouncy Castle
  • libsodium

10. 변형과 개선#

10.1 RSA-OAEP#

OAEP(Optimal Asymmetric Encryption Padding)는 RSA의 보안성을 강화하는 패딩 방식이다.

특징:

• 작은 지수 공격 방어
• 결정론적 암호화 방지
• 무작위 오라클 모델에서 증명됨

표준: PKCS#1 v2.0 이상에서 권장

10.2 RSA-PSS#

PSS(Probabilistic Signature Scheme)는 RSA 서명을 위한 안전한 방식이다.

장점:

• 선택 메시지 공격에 안전
• 보안성 증명 가능

10.3 Multi-Prime RSA#

2개가 아닌 3개 이상의 소수를 사용하는 변형.

장점:

• CRT를 사용하면 더 빠른 복호화
• 같은 보안 수준에서 더 작은 개인키

단점:

• 보안성 분석이 덜 됨
• 표준화되지 않음

11. 관련 암호#

11.1 타원곡선 암호 (ECC)#

타원곡선 암호(Elliptic Curve Cryptography)는 RSA의 대안이다.

비교:

• 키 길이: ECC-256 ≈ RSA-3072
• 속도: ECC가 더 빠름
• 성숙도: RSA가 더 오래되고 검증됨
• 양자 컴퓨터: 둘 다 취약

11.2 ElGamal#

ElGamal 암호는 RSA와 비슷한 시기에 개발된 공개키 암호다.

차이점:

• 이산대수 문제에 기반 (소인수분해가 아님)
• 암호문 크기가 평문의 2배
• 특허 없음

11.3 Rabin 암호#

Rabin 암호는 RSA와 매우 유사하지만 e=2를 사용한다.

특징:

• 소인수분해와 직접 동치
• 복호화 시 4개의 평문 후보가 나옴
• 실용적이지 않아서 잘 안 쓰임

12. RSA 챌린지#

RSA Laboratories는 1991년부터 2007년까지 RSA Factoring Challenge를 운영했다.

목적:

• 소인수분해의 난이도 측정
• 암호학 연구 촉진
• 상금 제공

주요 결과:

번호	비트 수	인수분해 연도	상금
RSA-100	330	1991	없음
RSA-129	426	1994	$100
RSA-140	463	1999	$7,500
RSA-155	512	1999	$10,000
RSA-160	530	2003	없음
RSA-200	663	2005	없음
RSA-768	768	2009	챌린지 종료 후
RSA-250	829	2020	챌린지 종료 후

미해결 숫자들:

• RSA-617 (617비트)
• RSA-704 (704비트)
• RSA-896 (896비트)
• RSA-1024 (1024비트)
• RSA-1536 (1536비트)
• RSA-2048 (2048비트)

13. 흥미로운 사실#

• RSA-129는 원래 4천조 년이 걸릴 것으로 예상되었으나, 분산 컴퓨팅으로 8개월만에 깨졌다.

• RSA 알고리즘은 무기로 분류되어 미국 수출 규제 대상이었다. 1990년대까지 암호 기술을 인쇄된 책으로만 수출할 수 있었다.

• 2015년, 연구자들이 타이완의 국민신분증 카드에 사용된 RSA-1024 키를 생성할 때 약한 난수 생성기를 사용했다는 것을 발견했다. 이론상 모든 키를 깰 수 있었다!

• RSA의 세 발명자는 2002년 튜링상을 수상했다. 컴퓨터 과학계의 노벨상이라 불리는 상이다.

• 처음 RSA 논문이 제출되었을 때, 한 심사위원이 "이건 너무 간단해서 누군가 이미 발명했을 것"이라고 말했다고 한다.

• 일부 국가에서는 강력한 암호 사용을 불법으로 규정한다. 중국, 러시아 등에서는 정부가 복호화할 수 있는 암호만 허용한다.

• RSA-2048을 깼다고 주장하는 사람이 나왔다. 근데 p랑 q가 소수가 아니라 RSA가 아닌게 함정 당연히 거짓 논문이다. 자세한 내용은 Roughness of Area 엔진 문서를 참고하자.

14. 같이 보기#

• 공개키 암호
• 대칭키 암호
• AES
• 디피-헬먼 키 교환
• 타원곡선 암호
• 전자서명
• SSL/TLS
• 양자내성암호
• 소인수분해
• 오일러 정리
• 페르마의 소정리
• 중국인의 나머지 정리

15. 참고 문헌#

• R. L. Rivest, A. Shamir, and L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Communications of the ACM, vol. 21, no. 2, pp. 120–126, 1978.
• Dan Boneh, "Twenty Years of Attacks on the RSA Cryptosystem," Notices of the American Mathematical Society, vol. 46, no. 2, pp. 203–213, 1999.
• Victor Shoup, "OAEP Reconsidered," Journal of Cryptology, vol. 15, no. 4, pp. 223–249, 2002.

16. 외부 링크#

• RSA Security 공식 웹사이트
• OpenSSL 프로젝트
• NIST 양자내성암호 프로젝트