Step 230. RSA 공격 2: 페르마 인수분해, Wiener’s attack — 키 생성이 엉터리면 수학이 무너진다
Level 3 — CTF 실전과 공격 스킬 심화 | 난이도 ★★★★☆ | 예상 소요 시간 4시간
전제: Step 229(RSA 공격 1) — 지난 챕터는 "쓰는 법"의 실수, 오늘은 "만드는 법"의 실수입니다.
⚠️ 이 챕터의 실습은 내 랩·합법 플랫폼 전용입니다. 허가 없는 시스템에 적용하면 범죄입니다.
- 준비물: 파이썬 3(실측: 3.12.14), Step 228의 소수 생성 코드, Step 229의
iroot감각. - 주의: factordb.com 조회는 오늘 "개념 소개"만 합니다 — 이 챕터의 실행 환경은 외부 네트워크를 쓰지 않습니다.
RSA의 안전성은 "n을 인수분해하기 어렵다"에 걸려 있습니다. 그런데 이 어려움은 키 생성이 정상일 때만 성립합니다. p와 q가 너무 가까우면 n의 제곱근 근처를 훑는 것만으로 인수분해가 끝나고(페르마), 비밀 지수 d가 너무 작으면 공개값 (n, e)만으로 d가 수학적으로 계산됩니다(Wiener). 오늘은 두 공격을 직접 구현하고, 취약한 키를 만들어 직접 깨봅니다. CTF에서 "이 n 뭔가 이상하다"의 대표 2종입니다.
1. 학습 목표
이 챕터를 끝내면 다음을 할 수 있습니다:
- 페르마 인수분해를 구현하고, p와 q의 거리와 반복 횟수의 관계를 설명한다
- 가까운 소수로 만든 n을 인수분해해 d를 계산하고 암호문을 복호화한다
- 연분수 전개를 직접 구현해 Wiener’s attack으로 작은 d를 복구한다
- 낯선 RSA 공개키를 볼 때 "페르마 → 작은 d 의심 → factordb" 순서의 진단 습관을 갖는다
2. 배경 지식 — 오늘의 도구와 개념
오늘의 도구 한눈에 보기
| 구분 | 내용 |
|---|---|
| 언어·환경 | 파이썬 3 (실측: 3.12.14) — 표준 라이브러리만, 설치 없음 |
| 오늘의 명령어 | math.isqrt(), 직접 짜는 fermat_factor(), convergents()(연분수), wiener() |
| 필요한 개념 | Step 227~228 전부 + 완전제곱수 판별, 연분수(continued fraction) |
| 오늘의 산출물 | fermat_factor()와 wiener() — 취약 키 2종을 실제로 깨는 공격기 |
2-1. 페르마 인수분해 — 제곱의 차이
모든 홀수 합성수 n은 제곱의 차이로 씁니다: n = a² - b² = (a-b)(a+b). 그러면 p = a-b, q = a+b입니다. 방법은 단순합니다 — a = isqrt(n) + 1부터 시작해 a² - n이 완전제곱수인지 검사하고, 아니면 a를 1 올려 반복합니다.
반복 횟수는 a - √n ≈ (p-q)² / (8√n)에 비례합니다. 즉 p와 q가 가까울수록 압도적으로 빠릅니다. 정상적인 키 생성(독립적인 무작위 소수)에서는 차이가 √n 스케일이라 사실상 영원히 돌지만, "이전 소수 + 작은 오프셋" 같은 엉터리 생성에서는 한 번의 반복으로 끝납니다 — 오늘 실측에서 확인합니다.
2-2. Wiener’s attack — 작은 d는 숨을 곳이 없다
RSA에서 e·d ≡ 1 (mod φ(n))이니 e·d = k·φ(n) + 1인 정수 k가 있습니다. 양변을 정리하면 e/n ≈ k/d — e/n의 근삿값으로 k/d가 나타납니다. d가 충분히 작으면(d < n^0.25 / 3이 고전 조건) k/d는 반드시 e/n의 연분수 전개 수렴값 목록에 들어 있습니다.
연분수(continued fraction)는 분수를 a0 + 1/(a1 + 1/(a2 + ...)) 꼴로 전개한 것이고, 그 앞부분만 자른 수렴값(convergent)들이 "분모가 작은 최고의 근사"를 순서대로 줍니다. 각 수렴값의 분모를 d 후보로 삼아 φ(n) = (e·d - 1)/k를 계산하고, 그 φ(n)으로 만든 이차방정식 x² - (n-φ(n)+1)x + n = 0의 판별식이 완전제곱수면 p, q가 확정 — d 발견입니다. 전부 빠른 정수 연산뿐이라 1024비트 키에서도 밀리초면 끝납니다.
2-3. 진단 습관 — n을 받으면 무엇을 보나
CTF에서 공개키 (n, e)를 받으면: ① factordb.com에 n을 조회(이미 누가 인수분해해 둔 수가 수두룩합니다 — 외부 서비스라 오늘은 개념만), ② 페르마를 잠깐 돌려 봅니다(가까운 소수면 즉시 깨짐), ③ e가 n과 비슷한 크기로 비정상적으로 크면 d가 작다는 강한 힌트 — Wiener를 돌립니다. 오늘은 ②③을 직접 만듭니다.
3. 따라 하기
이 챕터의 모든 출력은 2026-09-09 파이썬 3.12.14 실측입니다.
3-1. 페르마 인수분해 구현
from math import isqrt
def fermat_factor(n, limit=10_000_000):
a = isqrt(n)
if a * a < n:
a += 1
for i in range(limit):
b2 = a * a - n
b = isqrt(b2)
if b * b == b2: # a² - n이 완전제곱수면 n = (a-b)(a+b)
return a - b, a + b, i + 1
a += 1
return None, None, limit
isqrt는 정수 제곱근을 정확히 줍니다 — float ** 0.5는 Step 229 벽 1과 같은 정밀도 함정이 있으니 금지입니다.
3-2. 가까운 소수로 만든 키 깨기
일부러 "이전 소수에 작은 오프셋을 더한 다음 소수"라는 엉터리 생성을 재현합니다.
def next_prime(n):
n |= 1
while not is_probable_prime(n):
n += 2
return n
p = gen_prime(512)
q = next_prime(p + secrets.randbelow(2000) * 2) # 아주 가까운 소수
n = p * q
print("p와 q의 차이 (비트):", (q - p).bit_length(), "비트")
fp, fq, iters = fermat_factor(n)
print("인수분해 성공:", fp * fq == n, "| 반복 횟수:", iters)
phi = (fp - 1) * (fq - 1)
d = pow(65537, -1, phi)
m = int.from_bytes(b"weak key!", "big")
c = pow(m, 65537, n)
rec = pow(c, d, n)
print("복호화:", rec.to_bytes((rec.bit_length()+7)//8, "big"))
p와 q의 차이 (비트): 9 비트
인수분해 성공: True | 반복 횟수: 1
복호화: b'weak key!'
출력 읽는 법: 1024비트 RSA 모듈러스가 반복 1 회에 인수분해됐습니다. 차이가 9비트(수백)뿐이라 a = isqrt(n) + 1이 이미 정답이었습니다. 인수분해 → φ(n) → d → 복호화까지, 공개키 하나로 비밀키 전체를 재계산했습니다.
3-3. 거리와 반복 횟수의 관계 — 언제까지 깨지나
차이를 키워 가며 같은 실험을 했습니다(실측):
p,q 차이 ~2^200: 반복 1회, 성공=True, 0.00초
p,q 차이 ~2^264: 반복 1908회, 성공=True, 0.00초
차이가 2^200이어도 단번에 깨집니다 — 512비트 소수에게 2^200은 "같은 동네"입니다. 반면 정상적으로 독립 생성한 소수 둘(256비트씩)은:
정상 키(256비트 소수 둘): 20만 번 반복 후 성공? False | 0.11초
읽는 법: 반복 횟수는 (p-q)² / (8√n)에 비례하므로, 차이가 조금만 커져도 급격히 늘어납니다. 판정 기준은 "반복 횟수가 폭발하기 시작하는가" — 수만 회 안에 안 끝나면 이 키는 페르마의 대상이 아닙니다. 페르마는 "빠른 진단"이지 만능 인수분해기가 아닙니다.
3-4. Wiener’s attack — 연분수로 d 계산
연분수 수렴값 생성기와 공격 함수를 만듭니다.
def convergents(num, den):
# num/den의 연분수 수렴값 (분자, 분모)을 순서대로 생성
h_prev, h_cur = 0, 1
k_prev, k_cur = 1, 0
a, b = num, den
while b:
q_, r_ = divmod(a, b)
yield q_ * h_cur + h_prev, q_ * k_cur + k_prev
h_prev, h_cur = h_cur, q_ * h_cur + h_prev
k_prev, k_cur = k_cur, q_ * k_cur + k_prev
a, b = b, r_
def wiener(e, n):
for k, d_cand in convergents(e, n):
if k == 0 or (e * d_cand - 1) % k != 0:
continue
phi_cand = (e * d_cand - 1) // k
s = n - phi_cand + 1 # s = p + q
disc = s * s - 4 * n # 판별식
if disc < 0:
continue
t = isqrt(disc)
if t * t == disc and (s + t) % 2 == 0:
return d_cand # p, q 확정 → 이 d가 진짜
return None
취약한 키를 만듭니다 — d를 먼저 작게 뽑고 e를 역으로 계산합니다(실제 사고 사례와 같은 구조):
p3, q3 = gen_prime(512), gen_prime(512)
n3 = p3 * q3
phi3 = (p3 - 1) * (q3 - 1)
while True:
d_small = secrets.randbits(240) | 1 # n^(1/4) ≈ 256비트보다 작게
if math.gcd(d_small, phi3) == 1:
break
e_big = pow(d_small, -1, phi3)
print("취약 키: d 비트 =", d_small.bit_length(), ", e 비트 =", e_big.bit_length())
d_found = wiener(e_big, n3)
print("Wiener 공격으로 복구한 d == 원래 d:", d_found == d_small)
print("복구된 d의 비트 수:", d_found.bit_length() if d_found else None)
취약 키: d 비트 = 238 , e 비트 = 1021 (n은 1024비트)
Wiener 공격으로 복구한 d == 원래 d: True
복구된 d의 비트 수: 238
출력 읽는 법: 공개값 (n, e)만으로 238비트 비밀키 d가 0.002초 만에 계산됐습니다. 그리고 진단 힌트가 출력에 그대로 보입니다 — e가 n과 거의 같은 1021비트로 비정상적으로 큽니다. d가 작으면 e는 φ(n) 스케일로 커질 수밖에 없어서, 거대한 e는 작은 d의 간접 증거입니다.
3-5. 진단 순서 실습
오늘 만든 도구로 낯선 (n, e)를 진단하는 순서를 몸에 익힙니다: ① fermat_factor(n, limit=100_000)을 잠깐 돌려 본다 → 실패하면 ② e.bit_length()가 n과 비슷하게 크면 wiener(e, n) → 둘 다 실패하면 ③ factordb 조회(외부, 개념만) → 그래도 안 되면 이 문제는 다른 공격의 대상입니다. 각 단계가 수 초를 넘지 않으니, 돌려 보지 않을 이유가 없습니다.
4. 미션과 연습문제
미션 — 약한 키 진단기 rsa_triage.py
- 함수
triage(n, e)를 만듭니다 — ① 페르마 10만 회 시도, ② e가 크면 Wiener 시도, 순서로 돌리고 결과를"fermat","wiener","unknown"중 하나와 함께 반환합니다 - 취약 키 두 벌(가까운 소수, 작은 d)과 정상 키 한 벌을 생성해 진단기가 셋을 올바르게 구분하는지 시연합니다
- 깨진 키에 대해서는 d를 계산하고
"flag{weak_key}"암호문을 복호화하는 것까지 이어 붙입니다 — 진단은 복구로 끝나야 완료입니다 - (선택) 정상 키에서 두 공격이 각각 몇 초 만에 포기하는지 시간을 출력해 보세요
연습문제
문제 1. 페르마 인수분해의 반복 횟수가 (p-q)² / (8√n)에 비례하는 이유를, a = (p+q)/2와 √n의 관계로 설명해 보세요.
문제 2. 왜 키 생성 라이브러리는 p와 q를 "완전히 독립적으로" 뽑아야 하나요? q = next_prime(p + K) 꼴의 생성이 오늘 어떤 실측으로 깨졌는지 근거를 대며 답해 보세요.
문제 3. Wiener 공격에서 각 수렴값 k/d를 어떻게 검증했나요? φ(n) 후보에서 p+q를 얻고 이차방정식으로 확인하는 흐름을 설명해 보세요.
문제 4. e가 n과 비슷한 크기로 큰 공개키를 봤습니다. 왜 이것이 작은 d의 힌트인지, e·d ≡ 1 (mod φ(n))에서 출발해 설명해 보세요.
5. 모범 답안과 완료 기준
미션 모범 답안
def triage(n, e):
fp, fq, iters = fermat_factor(n, limit=100_000)
if fp:
d = pow(e, -1, (fp - 1) * (fq - 1))
return "fermat", d
if e.bit_length() > n.bit_length() * 3 // 4: # e가 n 스케일로 크면 작은 d 의심
d = wiener(e, n)
if d:
return "wiener", d
return "unknown", None
판정 기준: ① 취약 키 두 벌이 각각 올바른 라벨로 깨지고 ② 정상 키가 "unknown"을 반환하고 ③ 깨진 키의 d로 pow(c, d, n) 복호화가 원문과 일치할 것. e.bit_length() 임계값은 절대 기준이 아닌 휴리스틱입니다 — 본문처럼 "e가 크면 Wiener를 ‘시도’한다"가 본질입니다.
검증하는 법: 세 키를 새로 생성해 재실행하고 라벨이 안정적인지 확인합니다. 특히 정상 키가 "unknown"으로 나와야 합니다 — 정상 키를 깨는 진단기는 오탐이 있는 것입니다.
연습문제 해답
문제 1 해답. n = pq에서 a = (p+q)/2로 두면 a² - n = ((p-q)/2)²이 되어 페르마의 종료 조건을 정확히 만족합니다. 시작점 √n과 종료점 (p+q)/2의 거리가 반복 횟수이고, 테일러 근사로 (p+q)/2 - √n ≈ (p-q)²/(8√n)입니다. 차이에 제곱으로 민감하므로 가까운 소수는 즉시, 먼 소수는 사실상 영원히 걸립니다 — 실측(차이 9비트 → 1회, 2^264 → 1908회, 정상 → 20만 회 실패)이 그대로 대응됩니다.
문제 2 해답. p를 기준으로 q를 파생시키면 둘의 차이가 생성 파라미터에 의해 결정되어, 공격자에게 "n의 제곱근 근처만 훑으면 된다"는 지도를 줍니다. 3-2에서 차이 9비트짜리 키가 반복 1회에 깨졌고, 3-3에서 차이 2^264까지도 1908회에 깨졌습니다. 독립 생성이 유일하게 차이를 √n 스케일로 유지하는 방법입니다.
문제 3 해답. 수렴값 k/d는 "후보"일 뿐이라 검증이 필요합니다. e·d = k·φ(n) + 1 관계에서 φ(n) = (e·d - 1)/k를 계산하고(나누어떨어지지 않으면 탈락), p + q = n - φ(n) + 1과 p·q = n을 근과 계수의 관계로 세운 이차방정식의 판별식 s² - 4n이 완전제곱수인지 확인합니다. 완전제곱수면 p, q가 정수로 확정되므로 그 d는 진짜입니다.
문제 4 해답. e·d = k·φ(n) + 1이고 k < d이므로(Wiener 조건에서), d가 작으면 k도 작아 e ≈ k·φ(n)/d가 φ(n) — 즉 n 스케일까지 커집니다. 반대로 d가 n 스케일로 크면 e는 작게 유지될 수 있습니다. 그래서 "1024비트 n에 1021비트 e"(3-4 실측)는 작은 d의 존재를 강하게 시사합니다.
완료 기준 체크리스트
- [ ]
fermat_factor()를 구현하고isqrt를 쓰는 이유를 안다 - [ ] 가까운 소수 키를 반복 1~수천 회에 인수분해해 d까지 복구했다
- [ ] 차이-반복 횟수 관계를 실측 세 쌍으로 설명할 수 있다
- [ ]
convergents()생성기와wiener()를 구현해 238비트 d를 복구했다 - [ ] "큰 e = 작은 d 힌트"를 수식으로 설명할 수 있다
- [ ] 진단 순서(페르마 → Wiener → factordb)를 외워 적용할 수 있다
- [ ] 미션: triage가 취약 2종을 올바른 라벨로 깨고 정상 키를 unknown 처리했다
6. 흔한 실수와 해결
벽 1. ValueError: isqrt() argument must be nonnegative
증상: ValueError: isqrt() argument must be nonnegative (2026-09-09 실측).
원인: 두 가지 경로로 옵니다 — fermat_factor에서 n이 완전제곱수일 때 처리를 빼먹었거나, wiener에서 판별식 disc < 0 검사를 생략했을 때입니다.
해결: wiener의 if disc < 0: continue를 확인하세요. 후보 수렴값 대부분은 판별식이 음수라 이 분기가 정상 동작입니다.
벽 2. 페르마가 안 끝난다
증상: 몇 분째 반복 중입니다.
원인: 그 키는 페르마로 안 깨지는 정상 키입니다 — 3-3에서 정상 키는 20만 회에도 실패했습니다(실측). 반복 횟수는 차이의 제곱에 비례하므로 "조금 더 돌리면"이 없습니다.
해결: limit을 두고 초과하면 포기하세요. 페르마는 10만 회 안에 답이 나오거나 영원히 안 나오거나 둘 중 하나입니다.
벽 3. Wiener가 None을 반환한다
증상: 분명 작은 d로 만들었는데 wiener가 None입니다.
원인: d가 조건 밖입니다 — d < n^0.25 / 3이 고전 상한이라, 1024비트 n에서는 d가 대략 250비트를 넘으면 실패할 수 있습니다. 또는 convergents의 수렴값 갱신 순서가 뒤집혔을 수 있습니다.
해결: 3-4처럼 d를 240비트 이하로 뽑아 조건 안에서 먼저 성공을 확인한 뒤, 경계를 실험해 보세요.
벽 4. phi_cand가 나누어떨어지지 않는 후보까지 통과시켰다
증상: 틀린 d가 "발견"됐다고 나오거나, 끝까지 돌아도 발견이 없습니다.
원인: (e * d_cand - 1) % k != 0 필터 생략 — 나누어떨어지지 않으면 φ(n)이 정수가 아니므로 그 후보는 물리적으로 불가능합니다.
해결: 3-4의 두 필터(k == 0, 나머지 검사)와 판별식 완전제곱수 검사 세 개가 모두 있어야 합니다. 검증 없는 연분수는 추측일 뿐입니다.
벽 5. float 제곱근으로 완전제곱수를 판별했다
증상: int((a*a - n) <strong> 0.5) </strong> 2 == a*a - n 검사가 가끔 틀립니다.
원인: Step 229 벽 1과 같은 float 정밀도 문제 — 큰 수에서 ** 0.5는 정확하지 않습니다.
해결: 모든 제곱근은 math.isqrt. 이 챕터의 두 공격 모두 정수 연산만으로 완결되어야 합니다.
7. 정리
오늘의 개념
| 개념 | 한 줄 설명 |
|---|---|
| 페르마 인수분해 | n = a² - b²를 제곱근 위쪽에서 탐색 — p,q 가까우면 즉시 깨짐 |
| 반복 횟수 공식 | (p-q)²/(8√n) — 차이의 제곱에 비례, 정상 키엔 무력 |
| Wiener’s attack | 작은 d는 e/n의 연분수 수렴값에 반드시 등장 — 공개키만으로 d 계산 |
| 연분수 수렴값 | 분모가 작은 최고의 근사를 순서대로 주는 분수 전개 |
| 진단 습관 | 페르마(잠깐) → 큰 e면 Wiener → factordb 조회 순서 |
오늘의 명령어·코드
| 명령 | 하는 일 |
|---|---|
math.isqrt(n) |
정확한 정수 제곱근 — 완전제곱수 판별의 기초 |
fermat_factor(n, limit) |
a = isqrt(n)+1부터 완전제곱수 탐색 |
convergents(e, n) |
e/n의 연분수 수렴값 (k, d) 후보 생성 |
wiener(e, n) |
수렴값 → φ(n) 후보 → 판별식 검증 → d 확정 |
e.bit_length() |
작은 d 의심 휴리스틱(큰 e 탐지) |
명령어보다 중요한 감각
어제는 "쓰는 법의 실수"(작은 e, n 재사용), 오늘은 "만드는 법의 실수"(가까운 소수, 작은 d)였습니다. 공통점은 하나 — 검증이 추측을 이깁니다. 페르마의 완전제곱수 검사, Wiener의 판별식 검사 모두 "맞아 보이는 후보"를 "확정된 답"으로 바꾸는 장치였습니다. 공격자의 도구상자는 커졌고, 이제 낯선 n을 보면 손이 먼저 isqrt로 갈 것입니다.
전부 체크되면 Step 230 완료입니다. 사이드바의 체크박스를 눌러 진도를 저장하세요.