Step 229. RSA 공격 1: 작은 e, 공통 모듈러스 — 구현 실수가 수학적 약점이 되는 순간
Level 3 — CTF 실전과 공격 스킬 심화 | 난이도 ★★★☆☆ | 예상 소요 시간 4시간
전제: Step 228(RSA 완전 구현) — 오늘은 그 챕터에서 만든 "교과서 RSA"를 직접 부숩니다.
⚠️ 이 챕터의 실습은 내 랩·합법 플랫폼 전용입니다. 허가 없는 시스템에 적용하면 범죄입니다.
- 준비물: 파이썬 3(실측: 3.12.14), Step 228의 소수 생성 코드. 표준 라이브러리만 씁니다.
- 주의: 오늘 공격의 대상은 여러분이 직접 생성한 키뿐입니다. 남의 키에 이 코드를 돌리는 것과, 내 키가 어떻게 깨지는지 아는 것은 완전히 다른 일입니다.
Step 228에서 RSA 성을 지었습니다. 오늘은 그 성의 약한 돌 두 개를 찾아 뽑습니다. 첫째, 공개 지수 e가 작고 메시지도 작으면 m^e가 n을 넘지 못해 mod 연산이 아예 걸리지 않습니다 — 암호문의 세제곱근이 곧 평문입니다. 둘째, 같은 n을 재사용해 다른 e로 같은 메시지를 암호화하면, 확장 유클리드 호제법(Step 227) 하나로 평문이 복구됩니다. 둘 다 수학이 아니라 "구현 습관"이 만든 취약점이며, CTF Crypto 문제의 단골 소재입니다.
1. 학습 목표
이 챕터를 끝내면 다음을 할 수 있습니다:
- e=3이고
m^3 < n일 때 정수 세제곱근으로 평문을 복구한다 m^e가 n을 조금 넘는 경우c + k·n탐색으로 공격을 확장한다- 같은 n, 다른 e로 암호화된 두 암호문에서 확장 유클리드 호제법으로 평문을 복구한다(공통 모듈러스 공격)
- 이 공격들이 성립하는 조건을 정확히 말하고, 패딩(OAEP)이 왜 방어가 되는지 설명한다
2. 배경 지식 — 오늘의 도구와 개념
오늘의 도구 한눈에 보기
| 구분 | 내용 |
|---|---|
| 언어·환경 | 파이썬 3 (실측: 3.12.14) — 표준 라이브러리만, 설치 없음 |
| 오늘의 명령어 | pow(c, a, n)(음수 지수 포함), 직접 짜는 iroot()(정수 k제곱근), egcd() |
| 필요한 개념 | Step 227(확장 유클리드 호제법, 역원) + Step 228(RSA 키 구조) 전부 |
| 오늘의 산출물 | 작은 e 공격기 + 공통 모듈러스 공격기, 둘 다 실측으로 평문 복구 성공 |
2-1. 작은 e 공격 — mod가 안 걸리면 암호가 아니다
RSA 암호화는 c = m^e mod n입니다. 그런데 m^e < n이면 나머지를 구해도 그대로입니다 — c = m^e, 끝. 공격자는 c의 정수 e제곱근을 구하면 됩니다. e=3에 짧은 메시지(예: 30바이트 플래그)를 패딩 없이 암호화하면 1024비트 n에서는 이 조건이 쉽게 성립합니다.
m^3이 n을 조금 넘는 경우에도 공격은 확장됩니다. c = m^3 - k·n인 k가 작다면, c + k·n을 더해 가며 세제곱근이 정수가 되는 k를 찾으면 됩니다. k가 수백 이하라면 몇 밀리초의 일입니다.
2-2. 공통 모듈러스 공격 — 같은 자물쇠에 열쇠 두 개
같은 n을 쓰는 두 수신자(또는 두 시스템)가 같은 메시지 m을 각자의 e로 암호화했다고 합시다:
c1 = m^e1 mod n
c2 = m^e2 mod n
gcd(e1, e2) = 1이면 확장 유클리드 호제법으로 a·e1 + b·e2 = 1인 정수 a, b를 구할 수 있습니다. 그러면:
c1^a × c2^b ≡ m^(a·e1 + b·e2) ≡ m^1 ≡ m (mod n)
비밀키 d 없이, 공개된 정보만으로 m이 나옵니다. Step 227에서 배운 egcd가 그대로 공격 코드가 됩니다.
2-3. 왜 실무에서는 안 깨지나 — 패딩
실전 RSA는 평문을 그대로 지수에 올리지 않습니다. OAEP 패딩이 평문에 무작위 비트를 섞어 m을 n에 가까운 큰 수로 만들고, 매번 다른 값으로 바꿉니다. m^e < n 조건이 물리적으로 성립할 수 없고, "같은 메시지"라는 전제 자체가 사라집니다. 오늘 공격은 "패딩 없는 교과서 RSA"와 "설계 실수"에만 통합니다 — 그리고 CTF는 정확히 그 실수를 문제로 냅니다.
3. 따라 하기
이 챕터의 모든 출력은 2026-09-09 파이썬 3.12.14 실측입니다. 키는 매번 무작위 생성이므로 수치는 다르게 나옵니다.
3-1. 준비: 키 생성과 정수 k제곱근
Step 228의 is_probable_prime, gen_prime을 그대로 가져옵니다. 공격 도구로 정수 k제곱근 함수를 하나 만듭니다 — 부동소수점 c ** (1/3)은 큰 수에서 정밀도가 무너지므로(벽 1) 이진 탐색으로 구합니다.
def iroot(c, k):
# 정수 k제곱근: 이진 탐색. (근, 정확히 떨어지는지) 반환
lo, hi = 1, 1 << ((c.bit_length() + k - 1) // k + 1)
while lo < hi:
mid = (lo + hi + 1) // 2
if mid ** k <= c:
lo = mid
else:
hi = mid - 1
return lo, lo ** k == c
p, q = gen_prime(512), gen_prime(512)
n = p * q
print("n 비트 수:", n.bit_length())
n 비트 수: 1024
3-2. 공격 1: e=3, 세제곱근으로 평문 복구
e = 3
msg = b"flag{tiny_e}"
m = int.from_bytes(msg, "big")
c = pow(m, e, n)
print("m^3 == c (mod 없이 같나?):", m**3 == c) # n보다 작아 mod가 안 걸림
root, exact = iroot(c, 3)
print("정수 세제곱근 정확?:", exact)
rec = root.to_bytes((root.bit_length() + 7)//8, "big")
print("복구된 평문:", rec)
m^3 == c (mod 없이 같나?): True
정수 세제곱근 정확?: True
복구된 평문: b'flag{tiny_e}'
출력 읽는 법: m^3 == c가 True라는 것은 mod n 연산이 한 번도 적용되지 않았다는 뜻입니다 — 암호문이 그냥 평문의 세제곱입니다. 세제곱근을 구하니 플래그가 그대로 나왔습니다. 키를 몰라도, n을 인수분해하지 않아도 됩니다. 암호학이 아니라 산수입니다.
3-3. 공격 1b: n을 살짝 넘는 경우 — c + k·n 탐색
메시지를 조금 키워 m^3이 n을 넘게 만들면(실측: 43바이트 메시지) 세제곱근이 정확히 떨어지지 않습니다. 이때는 k를 더해 가며 찾습니다.
msg2 = b"A" * 26 + b"a tiny bit longer" # 43바이트
m2 = int.from_bytes(msg2, "big")
print("m2^3 < n ?", m2**3 < n, " / m2^3 // n =", m2**3 // n)
c2 = m2**3 % n
for k in range(200):
root, exact = iroot(c2 + k*n, 3)
if exact:
print("찾은 k:", k)
print("복구:", root.to_bytes((root.bit_length()+7)//8, "big"))
break
m2^3 < n ? False / m2^3 // n = 7
찾은 k: 7
복구: b'AAAAAAAAAAAAAAAAAAAAAAAAAAa tiny bit longer'
출력 읽는 법: m^3이 n의 7배를 살짝 넘는 크기였고, k=7에서 정확한 세제곱수가 나왔습니다. m^3 = c + k·n이므로 이 공격은 "k가 작을 때"만 실용적입니다 — 실측처럼 m^3 // n이 수백 이하일 때. 메시지가 n에 가까워지면 k가 천문학적으로 커져 이 방법은 무력해집니다.
3-4. 공격 2: 공통 모듈러스
같은 n, e1=3과 e2=65537로 같은 메시지를 암호화한 두 암호문을 가로챘다고 가정합니다.
def egcd(a, b):
if b == 0:
return a, 1, 0
g, x, y = egcd(b, a % b)
return g, y, x - (a // b) * y
e1, e2 = 3, 65537
m3 = int.from_bytes(b"same message, same n", "big")
c1 = pow(m3, e1, n)
c2 = pow(m3, e2, n)
g, a, b = egcd(e1, e2)
print("gcd(e1,e2) =", g, "| a =", a, "| b =", b)
print("a*e1 + b*e2 =", a*e1 + b*e2)
m3r = (pow(c1, a, n) * pow(c2, b, n)) % n # b<0 → pow가 역원 자동 처리
print("공통 모듈러스 복구:", m3r.to_bytes((m3r.bit_length()+7)//8, "big"))
print("원문 일치:", m3r == m3)
gcd(e1,e2) = 1 | a = 21846 | b = -1
a*e1 + b*e2 = 1
공통 모듈러스 복구: b'same message, same n'
원문 일치: True
출력 읽는 법: a·e1 + b·e2 = 21846×3 + (-1)×65537 = 1 — Step 227의 확장 유클리드 호제법 그대로입니다. b가 음수인데, 파이썬 3.8+의 pow(c2, -1, n)은 모듈러 역원을 자동으로 계산해 줍니다(버전 요구사항, 벽 2). 공개값 (n, e1, e2, c1, c2)만으로 평문이 복구됐습니다.
3-5. 방어 확인 — 왜 실무는 안 깨지나
두 공격의 공통 전제를 정리하면 ① 패딩 없음(작은 m), ② n 재사용, ③ 같은 메시지 반복입니다. OAEP 패딩은 평문을 매번 다른, n에 가까운 큰 수로 만들어 셋을 한꺼번에 깨뜨립니다. 방어는 "더 큰 키"가 아니라 "규칙을 지키는 구현"입니다.
4. 미션과 연습문제
미션 — RSA 공격 도구상자 rsa_attacks.py
- 오늘의 두 공격을 함수로 정리합니다 —
small_e_attack(c, e, n, max_k=1000)(3-2와 3-3 통합, 못 찾으면 None 반환)과common_modulus_attack(c1, c2, e1, e2, n)(복구된 m 반환) - 각 함수에 실패 조건을
assert나 반환값으로 명확히 합니다 — 어떤 조건에서 왜 실패하는지 주석으로 - 시연 스크립트를 씁니다: 취약한 키를 생성하고, 두 공격이 각각 성공하는 장면과, m이 큰 경우 small_e_attack이 None을 반환하는 장면을 출력합니다
- (선택)
time으로 각 공격의 실행 시간을 측정해 출력에 붙여 보세요 — 둘 다 1초 미만이 나오는 것이 포인트입니다
연습문제
문제 1. e=3일 때 평문 m이 몇 비트 이하여야 m^3 < n(1024비트 n)이 성립하나요? 바이트로 환산해 보세요.
문제 2. 공통 모듈러스 공격에서 gcd(e1, e2) = 1이 아니라 3이라면 어떻게 되나요? m이 아니라 m의 무엇이 복구되는지 설명해 보세요.
문제 3. 같은 n을 공유하는 게 왜 생기나요? "회사 전체가 하나의 n을 공유하고 직원마다 다른 (e, d)를 발급"하는 설계의 근본 문제를 공통 모듈러스 공격과 별개로 한 가지 더 짚어 보세요(힌트: d를 아는 직원이 할 수 있는 일).
문제 4. OAEP 패딩이 오늘의 두 공격을 각각 어떤 메커니즘으로 막는지, 공격의 전제 조건과 짝지어 설명해 보세요.
5. 모범 답안과 완료 기준
미션 모범 답안
def small_e_attack(c, e, n, max_k=1000):
"""c + k*n이 정확한 e제곱수가 되는 k를 찾아 m을 반환. 없으면 None."""
for k in range(max_k):
root, exact = iroot(c + k * n, e)
if exact:
return root
return None
def common_modulus_attack(c1, c2, e1, e2, n):
g, a, b = egcd(e1, e2)
if g != 1:
return None # gcd가 1이 아니면 m^g까지만 복구 가능
return (pow(c1, a, n) * pow(c2, b, n)) % n
판정 기준: ① 취약 키에서 두 공격 모두 원문과 == ② 큰 m에서 small_e_attack이 None 반환(조용히 틀린 값을 주는 게 아니라 실패를 보고하는 것이 핵심) ③ 주석의 실패 조건이 본문 조건(m^e 크기, gcd(e1,e2))과 일치할 것.
검증하는 법: 키를 새로 생성해 두 번 실행하고, 둘 다 성공/실패 판정이 같은지 확인합니다. 무작위 키 위에서 판정이 안정적이어야 공격기가 조건을 정확히 구현한 것입니다.
연습문제 해답
문제 1 해답. m^3 < 2^1024이려면 m < 2^(1024/3) ≈ 2^341.3, 즉 약 341비트 이하입니다. 바이트로는 42바이트(336비트) 정도가 상한입니다 — 실측에서 43바이트 메시지는 이미 m^3 // n = 7로 조건을 벗어났습니다. 짧은 플래그나 세션키(16~32바이트)는 e=3에서 무조건 이 범위 안입니다.
문제 2 해답. a·e1 + b·e2 = 3이 되므로 c1^a × c2^b ≡ m^3 (mod n이 복구됩니다. m이 작아서 m^3 < n이면 3-2처럼 세제곱근으로 m까지 갈 수 있고, 크면 m^3 mod n만 얻은 채 멈춥니다. 두 공격이 이렇게 연결되는 것이 Crypto 문제의 묘미입니다.
문제 3 해답. n을 아는 직원 중 한 명이라도 자기 (e, d)를 알면 e·d - 1이 φ(n)의 배수라는 사실을 이용해 n을 인수분해할 수 있습니다(알려진 확률적 기법). 즉 n 공유는 "내 비밀키를 아는 모든 사람이 전사 비밀을 여는 마스터키를 갖는 것"과 같습니다. 공통 모듈러스 공격은 암호문만 필요하지만, 이 문제는 키 하나만 새어도 전체가 무너집니다 — 둘 다 n 재사용이 원인입니다.
문제 4 해답. 작은 e 공격의 전제는 m^e < n인데, OAEP는 평문 앞에 무작위 시드와 패딩을 붙여 인코딩된 m을 n에 가까운 크기로 만들므로 전제가 성립 불가능합니다. 공통 모듈러스 공격의 전제는 "두 암호문의 m이 동일"인데, OAEP의 무작위 시드 때문에 같은 평문도 매번 다른 인코딩 m이 되어 c1^a × c2^b가 아무 의미 없는 값이 됩니다. 패딩은 "수학을 바꾸는 것"이 아니라 "공격의 전제를 제거하는 것"입니다.
완료 기준 체크리스트
- [ ]
iroot()를 이진 탐색으로 구현하고c ** (1/3)이 왜 위험한지 설명할 수 있다 - [ ] e=3,
m^3 < n조건에서 세제곱근으로 평문을 복구했다 - [ ]
c + k·n탐색으로 n을 살짝 넘는 경우까지 복구했다 - [ ]
egcd로 a, b를 구해 공통 모듈러스 공격을 실측 성공했다 - [ ]
pow(x, 음수, n)이 파이썬 3.8+에서 역원을 자동 처리함을 안다 - [ ] 두 공격의 성립 조건을 각각 한 문장으로 말할 수 있다
- [ ] OAEP가 각 공격의 어떤 전제를 깨는지 설명할 수 있다
- [ ] 미션: rsa_attacks.py 완성, 성공·실패 판정 모두 출력 확인
6. 흔한 실수와 해결
벽 1. c </strong> (1/3)으로 세제곱근을 구했다가 틀린 값이 나온다**
증상: int(10<strong>60 </strong> (1/3))이 99999999999999737856 — 끝자리가 어긋납니다(2026-09-09 실측).
원인: 파이썬 float는 53비트 정밀도라 수십 자릿수 정수를 담지 못합니다. 결과가 정수가 아니므로 lo ** k == c 검사에서 영원히 실패하거나 틀린 평문이 나옵니다.
해결: 3-1의 iroot()처럼 정수 이진 탐색을 쓰세요. 부동소수점은 암호학에서 금지입니다.
벽 2. pow(c2, b, n)에서 ValueError: base is not invertible for the given modulus
증상: ValueError: base is not invertible for the given modulus (2026-09-09 실측).
원인: b가 음수일 때 pow(c2, b, n)은 pow(c2, -1, n)의 역원을 먼저 구합니다 — c2와 n이 서로소가 아니면 이 에러가 납니다. 또는 파이썬 3.7 이하에서는 음수 지수 자체가 지원되지 않습니다.
해결: 정상 RSA에서 c2와 n이 인수를 공유할 확률은 무시할 수준이니, 에러가 나면 파이썬 버전(3.8+ 필수)부터 확인하세요. 수동으로는 pow(pow(c2, -1, n), -b, n)과 같습니다.
벽 3. 공통 모듈러스 복구값이 이상한 바이트열이다
증상: 복구된 m을 to_bytes하면 원문이 아닙니다.
원인: 대부분 두 암호문이 같은 m에서 나온 게 아닙니다 — 한쪽만 패딩을 했거나, 메시지가 미묘하게 다르면 공격은 조용히 실패합니다. 이 공격에는 "실패했다"는 신호가 없는 것이 특징입니다.
해결: 복구 결과가 사람이 읽을 수 있는지로 검증하세요. 실전 CTF에서는 두 암호문이 "같은 평문"이라는 힌트가 문제에 함께 주어집니다.
벽 4. small_e_attack이 k를 끝까지 돌고도 못 찾는다
증상: max_k까지 다 돌고 None 반환.
원인: m^e // n이 max_k보다 큽니다 — 메시지가 생각보다 깁니다. 실측에서 43바이트 메시지도 k=7이었지만, 50바이트면 k가 수천 단위로 뜁니다.
해결: 공격 가능 조건을 먼저 계산하세요 — m.bit_length() * e가 n의 비트 수를 얼마나 넘는지. 많이 넘으면 이 공격의 대상이 아닙니다.
벽 5. int.from_bytes와 to_bytes의 방향 실수
증상: 복구된 정수를 바이트로 바꾸니 앞이 깨지거나 순서가 뒤집힙니다.
원인: "big" / "little" 혼용, 또는 바이트 수 계산 생략.
해결: Step 228 규칙 그대로 — 변환은 항상 "big", 바이트 수는 (m.bit_length() + 7) // 8. 오늘 공격 코드는 전부 이 변환 위에서 돌아갑니다.
7. 정리
오늘의 개념
| 개념 | 한 줄 설명 |
|---|---|
| 작은 e 공격 | m^e < n이면 mod가 안 걸려 암호문의 e제곱근이 곧 평문 |
| c + k·n 탐색 | m^e가 n을 조금 넘을 때 k를 더해 정확한 제곱수를 찾는 확장 |
| 공통 모듈러스 공격 | 같은 n, 다른 e, 같은 m → c1^a × c2^b ≡ m (확장 유클리드) |
| 정수 k제곱근 | iroot — 부동소수점 금지, 이진 탐색 필수 |
| OAEP 패딩 | 평문을 크고 매번 다른 값으로 만들어 두 공격의 전제를 제거 |
오늘의 명령어·코드
| 명령 | 하는 일 |
|---|---|
iroot(c, k) |
정수 k제곱근(이진 탐색) — 작은 e 공격의 핵심 도구 |
egcd(e1, e2) |
a·e1 + b·e2 = gcd의 a, b 계산 — 공통 모듈러스의 열쇠 |
pow(c, a, n) |
음수 a도 역원 자동 처리(3.8+) — c1^a × c2^b mod n 조합 |
m.bit_length() |
공격 가능 조건(m^e와 n의 크기 비교) 점검 |
(m.bit_length()+7)//8 |
정수 → 바이트 변환 길이 계산 |
명령어보다 중요한 감각
오늘 깨진 것은 RSA라는 수학이 아니라 "수학의 전제를 무시한 구현"입니다. m^e < n 검사 한 줄, n 재사용 금지 규칙 하나면 두 공격은 전부 막힙니다. CTF에서 RSA 문제를 받으면 첫 질문은 언제나 같습니다 — "e가 작나? n이 공유됐나? m이 작나?" 이 체크리스트가 오늘의 진짜 산출물입니다.
전부 체크되면 Step 229 완료입니다. 사이드바의 체크박스를 눌러 진도를 저장하세요.