Step 228. RSA 완전 구현: 키 생성부터 암복호화까지 — 교과서를 내 손으로
Level 3 — CTF 실전과 공격 스킬 심화 | 난이도 ★★★★☆ | 예상 소요 시간 5시간
전제: Step 227(모듈러 연산, 유클리드 호제법, 오일러 정리) — 오늘의 모든 수학은 지난 챕터에서 만들었습니다.
⚠️ 이 챕터의 실습은 내 랩·합법 플랫폼 전용입니다. 허가 없는 시스템에 적용하면 범죄입니다.
- 준비물: 파이썬 3(실측: 3.12.14). 표준 라이브러리만 씁니다 — 설치 없음.
- 주의: 오늘의 규칙 하나 —
cryptography같은 실전 암호 라이브러리 사용 금지. 소수 생성부터 서명까지 전부 직접 구현하는 것이 이 챕터의 학습 목표입니다. 그리고 오늘 만드는 "교과서 RSA"는 패딩이 없어 실전에 쓰면 취약합니다 — 배우기 위한 구현입니다.
Step 227에서 부품(역원, 오일러 정리)을 만들었으니, 오늘은 조립입니다. RSA는 "큰 수의 소인수분해가 어렵다"는 사실 하나에 선 암호입니다 — 두 소수를 곱한 n은 공개해도, n을 다시 쪼개지 못하면 비밀키를 모릅니다. 오늘 512비트 소수를 직접 생성해 1024비트 키를 만들고, 한글 문장을 암호화·복호화하고, 서명과 변조 검출까지 전 과정을 실측합니다. 끝나면 RSA는 더 이상 "믿는" 암호가 아니라 "내가 만든" 암호입니다.
1. 학습 목표
이 챕터를 끝내면 다음을 할 수 있습니다:
- Miller-Rabin 소수 판별로 512비트 소수를 직접 생성한다
n, φ(n), e, d의 관계를 계산하고 각 변수의 역할을 설명한다- 메시지 ↔ 정수 변환(
int.from_bytes/to_bytes)을 올바르게 한다 pow(m, e, n)/pow(c, d, n)으로 암호화·복호화하고, 서명·검증에 같은 키를 반대로 적용한다- 패딩 없는 교과서 RSA의 한계(m < n 제한, 결정론적 암호화)를 설명한다
2. 배경 지식 — 오늘의 도구와 개념
오늘의 도구 한눈에 보기
| 구분 | 내용 |
|---|---|
| 언어·환경 | 파이썬 3 (실측: 3.12.14), secrets(난수), hashlib(서명용 해시) |
| 오늘의 명령어 | secrets.randbits(), pow(a, b, n), pow(e, -1, phi), int.from_bytes(), int.to_bytes() |
| 필요한 개념 | Step 227 전부 + Miller-Rabin 소수 판별, 공개키/개인키, 디지털 서명 |
| 오늘의 산출물 | rsa.py — 키 생성·암복호화·서명·검증이 되는 완성 구현 + 검증 실험 출력 |
2-1. RSA 키의 해부도
p, q : 직접 생성한 큰 소수 둘 — 비밀
n = p × q : 공개. "쪼개기 어려운 수"가 전부의 기초
φ(n) = (p-1)(q-1) : 비밀. p, q를 아는 사람만 계산 가능
e = 65537 : 공개 지수. φ(n)과 서로소인 소수로 고르는 것이 관행
d : 비밀 지수. e의 mod φ(n) 역원 — pow(e, -1, phi)
공개되는 것은 (n, e)뿐입니다. 공격자가 d를 얻으려면 φ(n)이 필요하고, φ(n)을 얻으려면 n을 p, q로 쪼개야 합니다 — 1024비트 이상에서는 사실상 불가능합니다.
2-2. 암복호화가 성립하는 이유 — 한 줄 증명
암호화 c = m^e mod n, 복호화 m = c^d mod n. 이어붙이면 m^(e·d) mod n입니다. 그런데 d는 e·d ≡ 1 (mod φ(n))인 역원이니 e·d = k·φ(n) + 1이고, 오일러 정리(Step 227)에 의해 m^(k·φ(n)) ≡ 1이라 결국 m^(e·d) ≡ m (mod n). 지난 챕터의 정리가 곧 오늘의 복호화 보증서입니다.
2-3. Miller-Rabin — 큰 소수를 찾는 법
소수를 어떻게 만드나요? "큰 홀수를 무작위로 뽑고, 소수인지 검사하고, 아니면 다시"입니다. 검사에는 Miller-Rabin 확률적 소수 판별을 씁니다 — 페르마 소정리(Step 227: 소수 p에서 a^(p-1) ≡ 1)를 여러 난수 a로 시험해, 모든 시험을 통과하면 소수일 확률이 압도적으로 높다고 판정합니다. 512비트 수에서도 1초 안에 끝납니다.
2-4. 디지털 서명 — 키를 거꾸로 쓴다
RSA의 멋진 대칭: 암호화는 "공개키로 잠그고 개인키로 열기"이고, 서명은 "개인키로 잠그고 공개키로 열기"입니다. 문서의 해시를 개인키로 거듭제곱(s = h^d mod n)하면 서명이 되고, 누구나 공개키로 s^e mod n을 계산해 문서 해시와 같은지 검증합니다. 개인키 소유자만 만들 수 있으므로 "본인이 썼다"와 "변조되지 않았다"가 동시에 증명됩니다.
3. 따라 하기
이 챕터의 모든 출력은 2026-09-09 파이썬 3.12.14 실측입니다. 소수가 매번 무작위로 생성되므로 수치 자체는 여러분 것과 다릅니다 — 구조만 확인하세요.
3-1. 소수 생성기 만들기
import secrets
def is_probable_prime(n, rounds=20):
if n < 2: return False
for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
if n % p == 0: return n == p # 작은 소수는 바로 처리
d, r = n - 1, 0
while d % 2 == 0:
d //= 2; r += 1 # n-1 = 2^r × d
for _ in range(rounds):
a = secrets.randbelow(n - 3) + 2
x = pow(a, d, n)
if x in (1, n - 1): continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1: break
else:
return False # 합성수 확정
return True # 소수일 확률 압도적
def gen_prime(bits):
while True:
c = secrets.randbits(bits) | (1 << (bits - 1)) | 1 # 최상위·최하위 비트 고정
if is_probable_prime(c):
return c
secrets.randbits(bits)로 무작위 수를 뽑고, 최상위 비트를 1로(정확히 bits짜리 수가 되게), 최하위 비트를 1로(홀수가 되게) 고정한 뒤 판별합니다. 실측에서 512비트 소수 하나는 1초 미만에 나왔습니다.
3-2. 키 생성
p = gen_prime(512)
q = gen_prime(512)
print(str(p)[:20], "...", p.bit_length(), "비트")
print("p != q:", p != q)
n = p * q
phi = (p - 1) * (q - 1)
e = 65537
d = pow(e, -1, phi) # Step 227의 역원
print("n 비트 수:", n.bit_length())
print("(e * d) % phi =", (e * d) % phi)
12570016984684578139 ... 512 비트
p != q: True
n 비트 수: 1024
(e * d) % phi = 1
출력 읽는 법: 512비트 소수 두 개가 만들어졌고, 곱은 1024비트. (e·d) mod φ(n) = 1 — Step 227의 역원 검산 그대로입니다. 이 여섯 변수가 RSA 키 한 벌의 전부입니다.
3-3. 암호화와 복호화 — 한글 문장으로
메시지는 정수여야 하므로 int.from_bytes로 바꿉니다.
msg = "Meet at dawn. 키 직접 구현!"
m = int.from_bytes(msg.encode(), "big")
print("m < n:", m < n, "(m 비트:", m.bit_length(), ")")
c = pow(m, e, n) # 암호화
m2 = pow(c, d, n) # 복호화
recovered = m2.to_bytes((m2.bit_length() + 7) // 8, "big").decode()
print("복호화 결과:", recovered)
print("원문과 일치:", recovered == msg)
m < n: True (m 비트: 255 )
복호화 결과: Meet at dawn. 키 직접 구현!
원문과 일치: True
출력 읽는 법: 1024비트 n에 한글 포함 문장이 정확히 왕복했습니다. (m2.bit_length() + 7) // 8은 정수를 바이트로 되돌릴 때 필요한 바이트 수 계산입니다. 교과서 RSA 완성입니다 — 하지만 3-5에서 곧바로 한계를 봅니다.
3-4. 서명과 변조 검출
import hashlib
doc = "이 계약서는 내가 썼다."
h = int.from_bytes(hashlib.sha256(doc.encode()).digest(), "big") % n
sig = pow(h, d, n) # 개인키로 서명
h_check = pow(sig, e, n) # 공개키로 검증
print("서명 검증:", h_check == h)
h_fake = int.from_bytes(hashlib.sha256("이 계약서는 네가 썼다.".encode()).digest(), "big") % n
print("변조 문서 검증:", h_check == h_fake)
서명 검증: True
변조 문서 검증: False
출력 읽는 법: 같은 키 한 벌로 반대 방향 연산을 했습니다. 원문 문서는 검증을 통과하고, 한 단어 바꾼 변조 문서는 실패합니다 — 서명은 문서의 해시에 묶여 있으므로 문서가 바뀌면 검증이 깨집니다. 이것이 부인 방지(서명자만 만들 수 있음)와 무결성(변조 검출)의 동시 달성입니다.
3-5. 검증 실험 — 한계를 내 손으로
big_m = n + 12345 # 일부러 n보다 큰 m
big_c = pow(big_m, e, n)
big_m2 = pow(big_c, d, n)
print("큰 m 복원:", big_m2 == big_m)
print("복원값 = m mod n:", big_m2 == big_m % n)
큰 m 복원: False
복원값 = m mod n: True
출력 읽는 법: m이 n을 넘으면 복호화 결과가 m mod n으로 잘립니다 — mod 세계는 n 밖을 기억하지 못합니다. 이것이 첫 번째 한계: RSA로는 n보다 큰 데이터를 직접 못 암호화합니다. 그래서 실무는 하이브리드입니다 — 긴 데이터는 AES(대칭키)로 암호화하고, 짧은 AES 키만 RSA로 암호화합니다.
두 번째 한계는 보이지 않는 곳에 있습니다. 같은 m은 언제나 같은 c가 됩니다(결정론적) — 공격자가 "후보 평문을 전부 암호화해 비교"할 수 있습니다. 실전 RSA가 OAEP 같은 패딩으로 매번 다른 c를 만드는 이유이며, 패딩 없는 오늘의 구현이 실전에 쓰면 안 되는 이유입니다. 이 약점들이 바로 다음 챕터들의 공격 소재입니다.
4. 미션과 연습문제
미션 — rsa.py 완성과 자기 검증
- 오늘의 코드를 하나의 파일
rsa.py로 정리합니다 — 함수gen_prime,generate_keys(bits)(반환:(n, e), d),encrypt(m, e, n),decrypt(c, d, n),sign(doc, d, n),verify(doc, sig, e, n)(반환: True/False) - 256비트 키(128비트 소수 둘)로 짧은 영문 문장을 암복호화하고, 서명·검증·변조 검출까지 한 번에 돌아가는
if __name__ == "__main__":데모를 씁니다 - 파일 맨 위 주석에 각 변수의 역할을 한 줄씩 씁니다 — p, q, n, φ(n), e, d 여섯 개
- (선택) 친구나 동료에게 공개키
(n, e)만 주고 암호문을 받아 내 개인키로 풀어 보세요 — 키 교환 없이도 성립하는 것이 공개키 암호의 요점입니다
연습문제
문제 1. 공격자가 공개키 (n, e)와 암호문 c를 가지고 있습니다. d를 구하려면 무엇을 해야 하고, 왜 그것이 어려운지를 φ(n)을 거쳐 설명해 보세요.
문제 2. 왜 e로 65537을 쓰나요? e의 두 가지 조건(φ(n)과 서로소, 작은 수 선호)으로 설명해 보세요.
문제 3. 서명 검증에서 문서 본문이 아니라 "해시"에 서명하는 이유를 두 가지(길이 제한, 효율)로 설명해 보세요.
문제 4. 실험 3-5에서 big_m = n + 12345의 복호화 결과는 얼마였나요? 이 한계가 실무의 "하이브리드 암호" 설계로 어떻게 이어지는지 설명해 보세요.
5. 모범 답안과 완료 기준
미션 모범 답안
generate_keys의 골격입니다 — 나머지 함수는 본문의 한 줄씩을 그대로 옮기면 됩니다.
def generate_keys(bits=1024):
half = bits // 2
p, q = gen_prime(half), gen_prime(half)
n = p * q
phi = (p - 1) * (q - 1)
e = 65537
if phi % e == 0: # 서로소 조건 점검 — 드물지만 필요
return generate_keys(bits)
d = pow(e, -1, phi)
return (n, e), d
데모의 판정 기준: ① 복호화 문장이 원문과 ==로 참 ② 서명 검증 True, 변조 문서 False ③ 주석의 변수 설명이 "역할"(예: "d — 개인키. e의 mod φ(n) 역원으로 복호화와 서명에 사용")이지 "값"이 아닐 것.
검증하는 법: 데모를 두 번 실행해 소수가 매번 바뀌는데도(무작위 생성) 결과 판정은 동일하게 참이어야 합니다 — 무작위성 위에서 수학이 성립한다는 것이 RSA의 본질입니다.
연습문제 해답
문제 1 해답. d는 e의 mod φ(n) 역원이므로 φ(n)을 알아야 합니다. φ(n) = (p-1)(q-1)은 n을 p, q로 소인수분해해야 구할 수 있습니다. 그런데 1024비트 이상의 n을 쪼개는 효율적 방법이 알려져 있지 않습니다 — 분해가 어려우니 φ(n)을 모르고, φ(n)을 모르니 d를 모릅니다. RSA의 안전성 전체가 이 사슬의 첫 고리(소인수분해의 어려움)에 매달려 있습니다.
문제 2 해답. 첫째, e는 φ(n)과 서로소여야 역원 d가 존재합니다 — 소수를 고르면 이 조건이 거의 자동으로 만족됩니다. 둘째, e는 공개키 연산(암호화·검증)의 지수라 작을수록 빠릅니다. 65537 = 2¹⁶ + 1은 이진수로 1이 두 개뿐이라 거듭제곱이 특히 빠르며, 3 같은 너무 작은 값의 공격(다음 챕터의 소재)을 피할 만큼은 큽니다.
문제 3 해답. 첫째, 서명 대상은 n보다 작아야 하는데(3-5의 한계) 문서는 얼마든지 길 수 있습니다 — 해시는 어떤 길이의 문서도 고정 크기로 압축합니다. 둘째, n 크기의 모듈러 거듭제곱은 문서 전체에 하면 느립니다 — 해시 한 번에만 하면 빠릅니다. 해시의 변조 감지 성질(한 글자만 바뀌어도 해시가 바뀜) 덕에 문서 무결성도 그대로 계승됩니다.
문제 4 해답. 복호화 결과는 m mod n = 12345였습니다(실측: 복원값 = m mod n: True). mod 세계는 n 이상을 표현하지 못하므로, RSA로 직접 암호화할 수 있는 데이터는 n 비트 이하로 제한됩니다. 실무는 이 제한을 피해 긴 데이터는 빠른 대칭키(AES)로 암호화하고, 그 AES 키(수백 비트, n보다 작음)만 RSA로 암호화해 함께 보냅니다 — TLS가 바로 이 구조입니다.
완료 기준 체크리스트
- [ ] Miller-Rabin으로 512비트 소수를 직접 생성했다
- [ ] n, φ(n), e, d를 계산하고
(e·d) mod φ(n) == 1을 확인했다 - [ ] 한글 포함 문장을 암호화·복호화해 원문 일치를 봤다
- [ ] 서명·검증·변조 검출 세 가지를 실측했다
- [ ] m > n일 때 잘리는 것을 실험으로 확인했다
- [ ] 각 변수의 역할을 한 줄씩 설명할 수 있다
- [ ] 패딩 없는 RSA를 실전에 쓰면 안 되는 이유를 두 가지 말할 수 있다
- [ ] 미션: rsa.py를 완성하고 데모의 판정이 모두 참임을 확인했다
6. 흔한 실수와 해결
벽 1. OverflowError: int too big to convert
증상: 복호화 후 to_bytes에서 OverflowError: int too big to convert (2026-09-09 실측, 바이트 수를 작게 지정한 경우).
원인: m2.to_bytes(길이, "big")의 길이가 m2를 담기에 부족합니다.
해결: 3-3처럼 (m2.bit_length() + 7) // 8로 필요한 바이트 수를 계산하세요. 하드코딩하면 m이 커졌을 때 깨집니다.
벽 2. pow(e, -1, phi)가 ValueError: base is not invertible
증상: ValueError: base is not invertible for the given modulus (Step 227에서 실측한 그 에러).
원인: e와 φ(n)이 서로소가 아닙니다 — φ(n)이 65537의 배수가 되는 소수 조합을 뽑은 것입니다. 드물지만 일어납니다.
해결: 미션 모범 답안처럼 phi % e == 0이면 키를 다시 생성하세요.
벽 3. 소수 생성이 안 끝난다
증상: gen_prime이 몇 분째 돕니다.
원인: 두 가지 — is_probable_prime의 pow(a, d, n)을 pow(a, d)로 써서 거대 수를 만들었거나(세 개짜리 pow 필수, Step 227 벽 3), 최상위 비트 고정을 빼먹어 계속 작은 수를 뽑는 중입니다.
해결: 모든 거듭제곱이 세 인자 pow인지 확인하고, | (1 << (bits-1)) | 1의 두 비트 고정을 확인하세요. 정상이면 512비트가 1초 미만입니다(2026-09-09 실측).
벽 4. 복호화 결과가 원문과 다른데 에러는 없다
증상: 원문과 일치: False인데 예외는 없습니다.
원인: 대부분 m ≥ n입니다 — 3-5의 잘림이 조용히 일어난 것입니다. 256비트 키에 긴 문장을 넣으면 재현됩니다.
해결: 암호화 전에 assert m < n을 넣으세요. 긴 메시지는 잘라서 여러 블록으로(교과서식) 나누거나, 그냥 메시지를 짧게 유지하세요 — 오늘은 원리 학습이 목적입니다.
벽 5. "완성했으니 이걸 쓰자"는 유혹
증상: 오늘 만든 rsa.py를 실제 프로젝트에 넣고 싶어집니다.
원인: 완성의 기쁨. 하지만 오늘의 구현에는 패딩이 없고, 타이밍 공격 방어도 없고, 검증된 수만 번의 감사도 없습니다.
해결: 이 파일의 용도는 학습입니다. 실전에서는 검증된 라이브러리를 씁니다 — 단, 이제 여러분은 그 라이브러리 안에서 무슨 일이 일어나는지 아는 사람입니다. 그것이 오늘의 수확입니다.
7. 정리
오늘의 개념
| 개념 | 한 줄 설명 |
|---|---|
| RSA 키 | p, q(비밀 소수) → n(공개), φ(n)(비밀), e(공개 지수), d(e의 역원, 비밀) |
| 암호화/복호화 | c = m^e mod n, m = c^d mod n — 오일러 정리가 왕복을 보증 |
| 디지털 서명 | 개인키로 해시를 거듭제곱 — 공개키로 누구나 검증, 변조 시 깨짐 |
| Miller-Rabin | 페르마 소정리 기반 확률적 소수 판별 — 큰 소수 생성의 엔진 |
| m < n 제한 | mod 세계는 n 밖을 못 담음 — 하이브리드 암호의 존재 이유 |
| 교과서 RSA | 패딩 없는 순수 구현 — 학습용, 실전 사용 금지(결정론적 취약) |
오늘의 명령어·코드
| 명령 | 하는 일 |
|---|---|
secrets.randbits(bits) |
암호용 난수 생성 |
pow(a, b, n) |
모듈러 거듭제곱 — 암호화·복호화·서명 전부 이것 |
pow(e, -1, phi) |
비밀키 d 계산 |
int.from_bytes(b, "big") |
바이트 → 정수 (메시지 준비) |
m.to_bytes((m.bit_length()+7)//8, "big") |
정수 → 바이트 (복원) |
hashlib.sha256(doc).digest() |
서명 대상 해시 만들기 |
명령어보다 중요한 감각
RSA의 전부는 여섯 변수와 거듭제곱 두 줄이었습니다. 어려운 것은 수식이 아니라 "왜 안전한가"의 사슬 — 분해의 어려움 → φ(n) 은닉 → d 은닉 — 이고, 그 사슬의 첫 고리가 꺾이는 순간들(작은 n, 작은 e, 키 재사용)이 다음 챕터부터의 공격입니다. 오늘 여러분은 성을 직접 지었습니다. 성을 지어 본 사람은 성의 약한 돌이 어디인지 압니다 — 다음 공격 챕터들이 훨씬 빠르게 이해될 것입니다.
전부 체크되면 Step 228 완료입니다. 사이드바의 체크박스를 눌러 진도를 저장하세요.