[🥈 Silver 3] 2048비트 RSA가 0스텝에 갈라지는 이유 — DreamHack crt rsa 풀이

문제: DreamHack — crt rsa 분류: Crypto 난이도: 🥈 Silver 3 FLAG: DH{B45ic_Crt_R54_w1th_A_bit_0f_f3rmat_fact0r}

RSA 문제인데 주는 값이 평소와 다르다. 모듈러스 N, 그리고 dp, dq, qinv 세 개, 마지막으로 암호문 하나. 공개 지수 e 도, 개인키 d 도, 소수 p·q 도 없다. 이름이 "crt rsa"인 만큼 이 세 값은 RSA를 CRT(중국인의 나머지 정리)로 빠르게 복호할 때 쓰는 파라미터들이다.

포인트는 두 가지다. 하나는 이 dp·dq·qinv 가 소인수만 알면 그대로 복호에 쓸 수 있는 값이라는 것, 다른 하나는 출제자가 소수를 p = nextprime(q + 1) 로 뽑아 두 소수를 붙여 놓은 것. 2048비트 모듈러스라 겁을 주지만, 이 두 번째 사실이 인수분해를 통째로 열어 준다.

문제 개요

prob.py 는 flag 를 RSA 로 암호화하고 output.txt 에 공개값을 뱉는다. 소수 p·q 와 개인키 d 는 물론 숨겨져 있다. 우리가 해야 할 건 (1) N 을 인수분해하고, (2) 주어진 CRT 파라미터로 복호하는 것.

🧩 배경 — RSA-CRT 복호란

일반 RSA 복호는 m = c^d mod N 한 방이지만, d 가 2048비트라 이 거듭제곱은 느리다. 그래서 실제 구현은 모듈러스를 소수 단위로 쪼개는 CRT 최적화를 쓴다. 미리 다음 세 값을 준비해 둔다.

• dp = d mod (p - 1) — p 쪽 지수
• dq = d mod (q - 1) — q 쪽 지수
• qinv = q⁻¹ mod p — 두 결과를 합칠 때 쓰는 계수

복호는 각 소수에서 따로 거듭제곱한 뒤(모듈러가 절반 크기라 훨씬 빠르다) Garner 공식으로 합친다.

여기서 중요한 사실 하나. 이 복호 과정에는 공개 지수 e 도, 원래 개인키 d 도 등장하지 않는다. 필요한 건 소수 p·q 와 이미 주어진 dp·dq·qinv 뿐이다. 즉 이 문제는 "복호에 필요한 재료를 이미 다 줬는데, 딱 하나 소인수만 안 준" 상태다. 그렇다면 남은 일은 N 을 인수분해하는 것뿐이다.

🔬 코드 정찰

prob.py 부터 본다.

이 글의 명령은 모두 문제 폴더 최상위(extracted/ 의 부모) 에서 실행한다.

cat extracted/prob.py

핵심은 소수를 만드는 세 줄이다.

q = getPrime(1024)
p = nextprime(q + 1)     # ← q 바로 다음 소수. p 와 q 가 붙어 있다
N = p * q

getPrime(1024) 로 q 를 뽑은 뒤, p 를 nextprime(q + 1) — 즉 q 바로 다음 소수 — 로 잡는다. 1024비트 근처에서 연속한 소수 사이 간격은 평균 수백 정도라, p 와 q 는 사실상 딱 붙어 있다. 이게 이 문제의 급소다.

그리고 출력부는 N, dp, dq, qinv, encrypted flag 만 찍는다. e 와 d 는 화면에 없다. output.txt 가 실제로 무엇을 주는지 크기부터 확인해 봤다.

# inspect_params.py — output.txt 가 주는 값의 정체 확인
import re
raw = open("extracted/output.txt").read()
for k in ("N", "dp", "dq", "qinv"):
    v = int(re.search(rf"{k}\s*=\s*(\d+)", raw).group(1))
    print(f"{k:>4} : {v.bit_length():>4} bits")
c = int(re.search(r"encrypted flag\s*=\s*(\d+)", raw).group(1))
print(f"{'c':>4} : {c.bit_length():>4} bits  (encrypted flag)")

N 은 2048비트, dp·dq·qinv 는 소수 크기(1024비트급). 공개 지수도 개인키도 없다. 배경에서 정리한 대로, 주어진 세 값은 CRT 복호 파라미터 그 자체다.

🐛 삽질

▶🐛 삽질 — 그냥 인수분해부터 하려다 2048비트 벽에 막힘

CRT 파라미터가 복호에 쓰인다는 건 금방 보였지만, 그러려면 p·q 가 필요하다. 그래서 "일단 N 을 인수분해하자"로 달려들었다. 문제는 N 이 2048비트 반소수(semiprime)라는 것. 작은 소인수라도 있나 훑어봤다.

Copy

# naive_factor.py — 작은 소인수 스캔 후 일반 인수분해로 넘어가려던 시도
import re, time
from sympy import primerange
N = int(re.search(r"N\s*=\s*(\d+)", open("extracted/output.txt").read()).group(1))
print(f"N : {N.bit_length()} bits")
t = time.time()
small = None
for pr in primerange(2, 300000):
    if N % pr == 0:
        small = pr
        break
print(f"작은 소인수 (< 300000) : {small}")
print(f"스캔 시간 : {time.time() - t:.2f}s")

작은 소인수는 없다. trial division 도, Pollard rho·p-1 도 2048비트 반소수 앞에서는 사실상 멈춘다. 여기서 "e 가 없으니 dp·dq 로 d 를 복원한 다음 표준 복호를 하자"로 방향을 틀어 봤지만, d 를 복원하려 해도 결국 p-1, q-1 을 알아야 하니 다시 인수분해로 되돌아온다. 뱅뱅 돌다 prob.py 의 p = nextprime(q + 1) 한 줄로 돌아왔다 — 소수가 붙어 있으면 굳이 일반 인수분해가 필요 없다.

💣 핵심 — 연속 소수라 Fermat이 0스텝에 뚫린다

p 와 q 가 붙어 있다는 건 Fermat 인수분해가 딱 맞는 상황이라는 뜻이다. Fermat 인수분해는 홀수 N 을 두 제곱수의 차로 본다.

N = a² − b² = (a + b)(a − b)

여기서 a = (p + q) / 2, b = (p − q) / 2 다. 두 소수가 가까우면 b 가 아주 작고, a 는 √N 바로 위에 있다. 그래서 a 를 ⌈√N⌉ 부터 하나씩 올리며 a² − N 이 완전제곱(= b²)이 되는 순간을 찾으면 된다. 소수가 붙어 있을수록 그 순간이 빨리 온다.

이 문제에선 얼마나 가까운지 직접 확인해 봤다. sympy 로 나온 두 소수가 실제 소수인지, 그리고 정말 연속 소수(p == nextprime(q + 1))인지까지 검증했다.

# factor_check.py — Fermat 으로 갈라 보고 연속 소수인지 확인
from math import isqrt
from sympy import isprime, nextprime
import re
 
N = int(re.search(r"N\s*=\s*(\d+)", open("extracted/output.txt").read()).group(1))
a = isqrt(N)
if a * a < N:
    a += 1
steps = 0
while True:
    b2 = a * a - N
    b = isqrt(b2)
    if b * b == b2:
        break
    a += 1
    steps += 1
p, q = a + b, a - b
print(f"Fermat steps      : {steps}")
print(f"p * q == N        : {p * q == N}")
print(f"p, q 가 소수인가   : {isprime(p)}, {isprime(q)}")
print(f"p == nextprime(q+1): {p == nextprime(q + 1)}")
print(f"p - q             : {p - q}")

Fermat steps = 0. 즉 a = ⌈√N⌉ 그 값에서 이미 a² − N 이 완전제곱이었다. 두 소수 차이는 겨우 672. 2048비트 모듈러스가 단 한 번의 제곱근 계산으로 갈라진 것이다. p == nextprime(q + 1) 도 True 라, 우리가 복원한 소수가 출제자가 만든 그 소수 쌍이 맞다.

이제 소인수를 얻었으니 배경의 CRT 복호를 그대로 돌리면 된다.

m1 = c^dp mod p
m2 = c^dq mod q
h  = qinv · (m1 − m2) mod p     # qinv = q⁻¹ mod p
m  = m2 + h · q

🎯 Full Exploit

output.txt 에서 값을 파싱해 Fermat 인수분해 → CRT 복호까지 한 번에 하는 스크립트다. 값은 하드코딩하지 않고 문제 파일에서 그대로 읽는다.

# solve.py
from math import isqrt
from Crypto.Util.number import long_to_bytes
import re, os
 
here = os.path.dirname(os.path.abspath(__file__))
raw = open(os.path.join(here, "extracted", "output.txt")).read()
vals = {}
for key in ("N", "dp", "dq", "qinv"):
    vals[key] = int(re.search(rf"{key}\s*=\s*(\d+)", raw).group(1))
c = int(re.search(r"encrypted flag\s*=\s*(\d+)", raw).group(1))
N, dp, dq, qinv = vals["N"], vals["dp"], vals["dq"], vals["qinv"]
 
# 1) Fermat factorization: N = a^2 - b^2 = (a+b)(a-b)
a = isqrt(N)
if a * a < N:
    a += 1
steps = 0
while True:
    b2 = a * a - N
    b = isqrt(b2)
    if b * b == b2:
        break
    a += 1
    steps += 1
p, q = a + b, a - b
assert p * q == N and p > q
print(f"[+] Fermat steps = {steps}   (p-q = {p - q})")
print(f"[+] p = {p}")
print(f"[+] q = {q}")
 
# 2) RSA-CRT 복호 (e, d 불필요)
m1 = pow(c, dp, p)
m2 = pow(c, dq, q)
h = (qinv * (m1 - m2)) % p
m = m2 + h * q
 
flag = long_to_bytes(m)
print(f"[+] FLAG = {flag.decode()}")

출력된 p 와 q 를 보면 앞자리가 전부 같고 끝 세 자리만 다르다(...798109 vs ...797437). 눈으로 봐도 두 소수가 붙어 있다는 게 보인다. 그리고 마지막 줄에 플래그가 떨어진다.

DH{B45ic_Crt_R54_w1th_A_bit_0f_f3rmat_fact0r}

✅ 검증

플래그 문자열 자체가 풀이를 그대로 요약한다 — B45ic_Crt_R54_w1th_A_bit_0f_f3rmat_fact0r, 즉 "약간의 Fermat 인수분해를 곁들인 기본 CRT-RSA". 우리가 쓴 두 도구(연속 소수 Fermat 인수분해 + CRT 파라미터 복호)가 의도한 정답 경로였다는 확인이다. 이 문제는 needs_vm 이 없는 오프라인 문제라, 서버 없이 로컬에서 값을 복원해 그대로 제출했다.

📝 결론 — 무엇이 문제였나

RSA의 안전성은 "큰 모듈러스는 인수분해가 어렵다"에 기댄다. 하지만 그건 두 소수가 무작위로 멀리 떨어져 있을 때 얘기다. 이 문제는 두 곳에서 그 전제를 무너뜨렸다.

• 연속 소수: p = nextprime(q + 1) 은 편의상 그럴듯해 보이지만, 두 소수를 붙여 놓으면 √N 근처에 소인수가 몰려 Fermat 인수분해가 즉시 통한다. 비트 수(2048)는 방어가 되지 못한다. 소수는 반드시 독립적으로, 충분히 떨어지게 뽑아야 한다(그래서 표준 키 생성은 |p − q| 하한을 둔다).
• CRT 파라미터 노출: dp·dq·qinv 는 개인키의 일부다. 이 값들은 소인수만 확보되면 e·d 없이도 곧장 복호로 이어진다. CRT 최적화 값은 개인키와 동급으로 취급해 절대 공개하지 않아야 한다.

두 실수 중 하나만 있어도 위험한데, 이 문제는 둘을 겹쳐 놨다. 방어자의 교훈은 단순하다 — 소수는 독립·충분한 간격으로, CRT 파라미터는 개인키처럼.