RSA Cryptography - 보안 & 프라이버시 > 암호학 | AI Insight Note

RSA는 1977년 Ron Rivest, Adi Shamir, Leonard Adleman이 개발한 공개키 암호화 알고리즘이다. 거대한 정수의 소인수분해가 수학적으로 어렵다는 원리에 기반하며, 디지털 서명, SSL/TLS, 암호화폐 주소 생성 등 현대 보안의 기반이다.

핵심 원리

소인수분해의 비대칭성:
  3 × 7 = 21         → 곱하기: 매우 쉬움 (O(1))
  21 = ? × ?         → 분해: 작은 수는 쉽지만
  → 2048비트 수라면   → 분해: 현재 컴퓨터로 수천 년 필요

키 생성 과정

1. 큰 소수 p, q 선택 (각 1024비트 이상)
2. n = p × q  (모듈러스)
3. φ(n) = (p-1)(q-1) 계산
4. e 선택: 1 < e < φ(n), gcd(e, φ(n)) = 1  (공개 지수)
5. d = e⁻¹ mod φ(n) 계산  (개인 지수)

공개키: (n, e)  → 누구에게나 공개
개인키: (n, d)  → 비밀 보관

암호화 / 복호화

암호화: C = Mᵉ mod n   (공개키로 암호화)
복호화: M = Cᵈ mod n   (개인키로 복호화)

디지털 서명:
  서명: S = Mᵈ mod n   (개인키로 서명)
  검증: M = Sᵉ mod n   (공개키로 검증)

소규모 수치 예시

실제 RSA는 수백 자릿수 소수를 사용하지만, 원리 이해를 위한 작은 예시:

p = 3, q = 11
n = p × q = 33
φ(n) = (p-1)(q-1) = 2 × 10 = 20

e 선택: φ(n)=20과 서로소인 수 → e = 7
d 계산: ed ≡ 1 mod 20 → 7×3 = 21 ≡ 1 mod 20 → d = 3

공개키: (n=33, e=7)
개인키: (n=33, d=3)

평문 M = 4 암호화:
C = 4^7 mod 33 = 16384 mod 33 = 16

암호문 C = 16 복호화:
M = 16^3 mod 33 = 4096 mod 33 = 4  ✓

실제 RSA: 각 소수가 1024비트(약 309자리 숫자), n은 2048비트. e는 통상 65537 = 2^16 + 1 고정 사용 (이진수로 1 0000 0000 0000 0001 — 비트가 적어 고속 거듭제곱 가능).

패딩 (Padding)의 중요성

Raw RSA(패딩 없음)는 안전하지 않다. 같은 평문은 항상 같은 암호문이 되므로 패턴 분석에 취약하다.

패딩 방식	설명	현황
PKCS#1 v1.5	랜덤 바이트를 앞에 추가	취약점 발견, 사용 지양
OAEP (Optimal Asymmetric Encryption Padding)	해시+MGF로 안전성 강화	현재 권장 표준

# OAEP 패딩 예시 (Python)
ciphertext = public_key.encrypt(
    message,
    padding.OAEP(
        mgf=padding.MGF1(hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

코드 예시

python

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes

# 키 쌍 생성
private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key = private_key.public_key()

# 암호화 (공개키)
ciphertext = public_key.encrypt(
    b"Hello, RSA!",
    padding.OAEP(mgf=padding.MGF1(hashes.SHA256()), algorithm=hashes.SHA256(), label=None)
)

# 복호화 (개인키)
plaintext = private_key.decrypt(
    ciphertext,
    padding.OAEP(mgf=padding.MGF1(hashes.SHA256()), algorithm=hashes.SHA256(), label=None)
)
print(plaintext)  # b"Hello, RSA!"

RSA 키 크기와 보안 강도

키 크기	보안 강도	권장 여부
512비트	매우 취약	✗ 사용 금지
1024비트	취약	✗ 사용 금지
2048비트	112비트 보안	△ 최소 권장
4096비트	140비트 보안	✓ 권장

RSA vs 타원 곡선 암호 (ECC)

항목	RSA	ECC (ECDSA)
동일 보안 강도 키 크기	2048비트	256비트
연산 속도	느림	빠름
메모리 사용	많음	적음
블록체인	거의 미사용	Bitcoin, Ethereum (secp256k1)

블록체인에서의 활용

Bitcoin과 Ethereum은 RSA 대신 secp256k1 타원 곡선(ECDSA) 을 사용한다. RSA보다 키가 작고 빠르기 때문이다.

Bitcoin 주소 생성:
  개인키 (256비트 랜덤) → ECDSA 공개키 → SHA-256 → RIPEMD-160 → 주소

하이브리드 암호화 (Hybrid Encryption)

RSA는 느리므로 실제로 대용량 데이터를 직접 암호화하지 않는다. 대칭키(AES)와 결합한다.

1. 송신자가 임시 AES 세션키 생성
2. 세션키를 수신자의 RSA 공개키로 암호화
3. 실제 데이터는 빠른 AES로 암호화
4. 수신자가 RSA 개인키로 세션키 복호화 → AES로 데이터 복호화

장점: RSA의 키 배포 안전성 + AES의 속도
활용: TLS, PGP, SSH

TLS 핸드셰이크에서의 RSA 활용

Client                              Server
   │                                   │
   │── ClientHello (지원 알고리즘) ──>  │
   │<── ServerHello + 인증서(공개키) ── │
   │                                   │
   │  (인증서의 공개키로 pre-master 암호화)
   │── ClientKeyExchange ────────────> │
   │                                   │ (개인키로 복호화)
   │<──── Finished (세션키 공유 완료) ──│
   │                                   │
   │==== 이후 AES로 암호화된 통신 ====  │

TLS 1.3 변경사항: RSA 키 교환 제거, ECDHE만 사용 (완전 순방향 비밀성 보장)

RSA의 한계와 포스트 양자 암호화

양자 컴퓨터의 위협

1994년 피터 숄(Peter Shor)이 양자 컴퓨터로 RSA의 핵심인 인수분해를 다항 시간에 풀 수 있는 알고리즘(숄 알고리즘)을 발견했다.

•충분히 큰 양자 컴퓨터(수천 큐비트)가 등장하면 RSA 2048비트도 해독 가능
•NIST는 2024년 포스트 양자 암호화(PQC) 표준을 발표: ML-KEM, ML-DSA, SLH-DSA

현재 권고사항

상황	권고
단기 보안	RSA-2048 이상 유지
장기 기밀 데이터	하이브리드 암호화 (RSA + 격자 기반 PQC) 고려
TLS 1.3	ECDHE와 함께 사용 (완전 순방향 보안)

참고문헌

•Rivest, Shamir, Adleman (1978). A Method for Obtaining Digital Signatures and Public-Key Cryptosystems
•NIST SP 800-57 — Recommendation for Key Management

RSA CryptographyRSA 암호화