RSA 알고리즘 학습 정리

공개키 암호화 시스템 핵심 개념 노트

---

1. RSA란?

RSA는 1977년 Rivest, Shamir, Adleman 세 사람이 만든 공개키 암호화 알고리즘입니다.
HTTPS, 디지털 서명, SSH 등 인터넷 보안의 근간이 되는 기술입니다.

핵심 아이디어

• 두 개의 키 사용: 누구나 아는 공개키(Public Key) + 나만 아는 개인키(Private Key)
• 비대칭 암호화: 암호화와 복호화에 서로 다른 키를 사용
• 수학적 근거: 큰 수의 소인수분해는 현실적으로 불가능

---

2. 수학적 원리

키 생성 과정

1. 두 소수 p, q를 선택 → 예: p=13, q=7
2. n = p × q 계산 → 예: n = 91
3. φ(n) = (p−1)(q−1) 계산 → 예: φ(91) = 72
4. gcd(e, φ(n)) = 1 인 e 선택 → 공개키 지수
5. e × d ≡ 1 (mod φ(n)) 를 만족하는 d 계산 → 개인키 지수

암호화 / 복호화 공식

구분	공식	사용 키
암호화	C = Mᵉ mod n	공개키 (n, e)
복호화	M = Cᵈ mod n	개인키 (n, d)

보안 근거

n은 공개되지만, n에서 p와 q를 역으로 구하는 소인수분해는 현재 컴퓨터로 불가능합니다.
2048비트 RSA 키 기준, 인수분해에 우주 나이보다 긴 시간이 소요됩니다.

---

3. 키의 실제 형태

수학적 본질은 숫자

• 공개키: 숫자 쌍 (n, e)
• 개인키: 숫자 쌍 (n, d)
• 모든 암복호화 연산은 결국 정수 연산(mod)

파일로 저장 시

실제 키 파일을 열면 Base64로 인코딩된 문자열로 보입니다:

-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8A...
-----END PUBLIC KEY-----

이 문자열을 디코딩하면 결국 수천 자리의 정수 (n, e)가 나옵니다.
PEM, DER 등 표준 포맷으로 감싸는 이유는 다루기 편하고 명확한 경계를 표시하기 위해서입니다.

---

4. 암호화 vs 디지털 서명

RSA는 두 가지 방향으로 사용할 수 있습니다. 목적이 다르면 키 사용 방향도 반대입니다.

구분	목적	사용 키	예시
암호화	받는 사람만 읽게	받는 사람의 공개키로 잠금 → 개인키로 열기	철수→영희: 영희 공개키로 암호화
디지털 서명	내가 보냈음을 증명	보내는 사람 개인키로 서명 → 공개키로 검증	철수→영희: 철수 개인키로 서명

헷갈리지 않는 법

• 암호화: "영희만 열 수 있게" → 영희의 공개키로 잠근다
• 서명: "나만 만들 수 있음을 증명" → 나의 개인키로 서명한다
• 핵심: 암호화는 받는 사람 공개키 / 서명은 보내는 사람 개인키

---

5. 실제 활용

HTTPS (TLS 핸드셰이크)

RSA는 느리기 때문에 모든 데이터를 직접 암호화하지 않습니다.

• RSA로 AES 대칭키를 안전하게 교환
• 본 통신은 빠른 AES로 암호화
• 이를 하이브리드 암호화 방식이라 합니다

SSH

• 서버에 공개키를 등록해두고, 개인키로 인증
• 비밀번호 없이 안전하게 서버에 접속 가능

이메일 서명 (PGP/GPG)

• 개인키로 이메일에 서명 → 수신자가 공개키로 검증
• 메일이 위조되지 않았음을 보장

---

6. RSA의 한계와 미래

현재 한계

• 속도: AES 등 대칭키 대비 수백 배 느림 → 직접 암호화에 비효율적
• 키 크기: 보안을 위해 2048비트 이상 필요 → 저장/전송 용량 부담

양자컴퓨터 위협

양자컴퓨터의 Shor 알고리즘은 소인수분해를 빠르게 풀 수 있어 RSA를 이론적으로 깰 수 있습니다.
현재 NIST를 중심으로 양자내성 암호(Post-Quantum Cryptography) 표준화가 진행 중입니다.

---

7. 핵심 요약 한눈에 보기

개념	핵심 한 줄 요약
RSA란	큰 수 소인수분해의 어려움을 이용한 공개키 암호화
공개키 (n, e)	누구나 알 수 있는 키 — 암호화·서명 검증에 사용
개인키 (n, d)	절대 공개하면 안 되는 키 — 복호화·서명 생성에 사용
암호화 방향	받는 사람 공개키 → 받는 사람 개인키
서명 방향	보내는 사람 개인키 → 보내는 사람 공개키
실제 사용	HTTPS에서 AES 키 교환, SSH 인증, 이메일 서명
보안 크기	현재 최소 2048비트, 권장 4096비트