[🥉 Bronze 3] 8827비트 RSA가 0.004초에 갈라지는 이유 — DreamHack many primes 풀이

문제: DreamHack — many primes 분류: Crypto 난이도: 🥉 Bronze 3 FLAG: DH{607bf0b239c83a8ff069bd619c9b47c69471207e74ca9cf68cef274891f544f9}

RSA 문제라고 해서 output.txt 를 열었더니 모듈러스 N 이 2658자리다. 화면을 한참 스크롤해야 끝나는 숫자. 처음엔 "2048비트도 못 깨는데 이건 8827비트라고?" 싶어 손이 잠깐 멈췄다. 그런데 문제 제목이 many primes 다. 소수가 두 개(p, q)가 아니라 많다는 뜻이고, 실제로 출제 스크립트를 열어 보면 소수를 777개나 곱해 놓았다. 그리고 그 777개가 전부 우스울 만큼 작다. 여기서 게임이 끝난다.

RSA의 안전성은 "충분히 큰 소수 두 개의 곱은 되돌리기 어렵다"에 전적으로 기댄다. 소인수가 작으면 — 아무리 많이 곱해서 모듈러스를 크게 부풀려도 — 시행나눗셈 한 번에 전부 되짚을 수 있다.

문제 개요

제공 파일은 딱 두 개다. 암호화 로직이 담긴 prob.sage 와 그 실행 결과 output.txt.

이 글의 명령은 모두 extracted/ 에서 실행한다.

ls -la

풀이 흐름은 단순하다. (1) N 을 작은 소수들로 시행나눗셈해 완전분해하고, (2) 서로 다른 소수의 곱이라는 성질로 φ(N) 을 구한 뒤, (3) d = e⁻¹ mod φ 로 개인키를 복원해 복호한다.

🧩 배경 — multi-prime RSA와 smooth 모듈러스

교과서 RSA는 큰 소수 두 개 p, q 를 골라 N = p·q 를 만든다. 공개키는 (N, e), 개인키는 d = e⁻¹ mod φ(N) 이고 φ(N) = (p−1)(q−1) 이다. 여기서 개인키를 얻으려면 φ(N) 을 알아야 하고, φ(N) 을 알려면 N 을 인수분해해 p, q 를 알아야 한다. 1024비트짜리 두 소수의 곱을 인수분해하는 것이 곧 RSA를 깨는 것이고, 그게 현존 알고리즘으로는 수만 년이 걸리기에 안전하다.

multi-prime RSA 는 소수를 셋 이상 쓴다. N = p1·p2·…·pk. 이러면 같은 비트 수에서 복호가 조금 빨라지는 이점이 있지만, 각 소수가 작아지면 인수분해 난이도도 같이 낮아진다. 극단적으로, 모든 소수가 어떤 작은 한계 B 미만이면 그 수를 B-smooth 라고 부르고, B 까지의 소수로 시행나눗셈만 돌려도 전부 분해된다. 모듈러스가 8827비트든 88270비트든 상관없다 — 크기가 아니라 가장 큰 소인수의 크기가 안전성을 정한다.

서로 다른 소수의 곱이라는 점도 중요하다. N = p1·p2·…·pk 처럼 소수가 모두 다르면(제곱이 없으면) φ(N) 은 그냥 각 (pᵢ − 1) 의 곱, 즉 φ(N) = ∏(pᵢ − 1) 이다. 소인수만 손에 넣으면 φ 는 곧바로 따라 나온다.

🔬 코드 정찰

prob.sage 를 그대로 읽어 본다. SageMath 스크립트다.

cat prob.sage

set_random_seed(777)
 
p = list(prime_range(11, 8296))   # 11 이상 8296 미만의 모든 소수 (1037개)
primes = sample(p, 777)           # 그 중 777개를 무작위로 뽑는다
n = prod(primes)                  # 곱한 것이 모듈러스 N
phi = prod(p - 1 for p in primes) # φ = ∏(pᵢ − 1)
e = 65537
d = inverse_mod(e, phi)
 
flag = "DH{REDACTED}"
m = int.from_bytes(flag.encode('utf-8'), 'big')
c = pow(m, e, n)
 
print(e); print(n); print(c)

정찰의 핵심은 prime_range(11, 8296) 한 줄이다. 후보 소수 풀 자체가 11부터 8296 미만으로 갇혀 있다. 여기서 뽑은 777개를 곱했으니, N 의 모든 소인수는 예외 없이 8296보다 작다. sample() 은 중복 없이 뽑으므로 소수는 전부 서로 다르고(제곱 항 없음), 따라서 φ(N) = ∏(pᵢ − 1) 공식이 그대로 성립한다.

output.txt 의 공개값 규모를 확인해 본다.

# inspect.py — output.txt 의 공개값(e, N, c) 규모 확인
import re
v = dict(re.findall(r"(\w+)\s*=\s*(\d+)", open("extracted/output.txt").read()))
e, n, c = int(v["e"]), int(v["n"]), int(v["c"])
print(f"e = {e}")
print(f"N : {n.bit_length()} bits, {len(str(n))} digits")
print(f"c : {c.bit_length()} bits")

N 이 8827비트, 무려 2658자리다. 보통 RSA 모듈러스가 2048~4096비트인 걸 생각하면 두 배가 넘는다. 겉보기엔 오히려 더 어려워 보인다 — 바로 이게 이 문제가 걸어 놓은 심리적 함정이다.

💣 핵심 — smooth 모듈러스는 시행나눗셈으로 갈라진다

소인수가 전부 8296 미만이라는 걸 알았으니, 8296까지의 소수로 하나씩 나눠 보면 된다. 이론이 맞는지 SageMath로 N 을 그냥 인수분해시켜 확인해 본다. Sage의 factor() 는 작은 소인수부터 훑기 때문에, smooth한 수라면 순식간에 끝난다.

# factor_check.sage — '8827비트 RSA 모듈러스'를 Sage 로 그냥 인수분해
import re, time
v = dict(re.findall(r"(\w+)\s*=\s*(\d+)", open("extracted/output.txt").read()))
n = Integer(v["n"])
t = time.time()
f = factor(n)
print("factor(n) 소요 시간 : %.3f초" % (time.time() - t))
print("소인수 개수         : %d" % len(list(f)))
print("가장 큰 소인수      : %d" % max(p for p, _ in f))
print("전부 지수 1 (제곱 없음) :", all(k == 1 for _, k in f))

0.004초. 2658자리 숫자가 눈 깜짝할 새에 777개 소인수로 갈라졌고, 가장 큰 소인수는 8293(8296 미만 최대 소수), 전부 지수 1이라 제곱 항도 없다. prob.sage 의 구조와 정확히 일치한다.

Sage에 의존하고 싶지 않다면 순수 파이썬으로도 똑같이 된다. 8296까지 에라토스테네스 체로 소수를 만든 뒤 하나씩 나눠 보면, 나누어떨어질 때마다 소인수로 챙기면 된다. 소인수 분포를 눈으로 확인해 보자.

# factor_stats.py — N 의 소인수 분포 (전부 작은 소수 = smooth 임을 확인)
import re
v = dict(re.findall(r"(\w+)\s*=\s*(\d+)", open("extracted/output.txt").read()))
n = int(v["n"])
def sieve(L):
    s = bytearray([1]) * L; s[0] = s[1] = 0
    for i in range(2, int(L ** .5) + 1):
        if s[i]: s[i*i::i] = bytearray(len(s[i*i::i]))
    return [i for i in range(L) if s[i]]
cand = [p for p in sieve(8296) if p >= 11]
facs = [p for p in cand if n % p == 0]
print(f"후보 소수 풀 (11 <= p < 8296) : {len(cand)}개")
print(f"N 을 나누는 소수            : {len(facs)}개  (최소={min(facs)}, 최대={max(facs)})")
prod = 1
for p in facs: prod *= p
print(f"소수들의 곱 == N : {prod == n}")

1037개 후보 소수 중 정확히 777개가 N 을 나눴고, 이 777개의 곱이 다시 N 과 정확히 같다. 나머지 없이 통째로 분해됐다는 뜻이다. 이제 이 소인수들로 φ 를 만들고 개인키를 복원하면 된다.

🎯 풀이 — φ 복원 → 개인키 → 복호

서로 다른 소수의 곱이므로 φ(N) = ∏(pᵢ − 1). 여기에 e = 65537 이 서로소인지만 확인하면 d = e⁻¹ mod φ 로 개인키가 나오고, m = c^d mod N 으로 평문을 얻는다. 평문 정수를 바이트로 되돌리면 플래그다.

시드(777)를 재현하지 않아도, 오직 공개값 N 만으로 시행나눗셈해서 푸는 자체 완결 스크립트다.

# solve.py — 시드 재현 없이 N 만으로 완전분해 후 복호
import re
from math import gcd
 
txt = open("extracted/output.txt").read()
vals = dict(re.findall(r"(\w+)\s*=\s*(\d+)", txt))
e, n, c = int(vals["e"]), int(vals["n"]), int(vals["c"])
print(f"[+] e = {e}")
print(f"[+] N: {n.bit_length()} bits, {len(str(n))} digits")
print(f"[+] c: {c.bit_length()} bits")
 
def sieve(limit):
    s = bytearray([1]) * limit; s[0] = s[1] = 0
    for i in range(2, int(limit ** 0.5) + 1):
        if s[i]: s[i*i::i] = bytearray(len(s[i*i::i]))
    return [i for i in range(limit) if s[i]]
 
# prob.sage 의 후보 소수 풀: prime_range(11, 8296)
candidates = [p for p in sieve(8296) if p >= 11]
print(f"[+] 후보 소수 개수 (11 <= p < 8296): {len(candidates)}")
 
factors = []
rem = n
for p in candidates:
    if rem % p == 0:
        factors.append(p)
        rem //= p            # sample() 이라 각 소수는 1회만 등장(제곱 없음)
print(f"[+] 발견한 소인수 개수: {len(factors)}   나머지 rem = {rem}")
assert rem == 1, "완전 분해 실패"
 
phi = 1
for p in factors:
    phi *= (p - 1)           # φ(N) = ∏(pᵢ − 1)
 
assert gcd(e, phi) == 1
d = pow(e, -1, phi)
m = pow(c, d, n)
mb = m.to_bytes((m.bit_length() + 7) // 8, "big")
print(f"[+] 소인수 {len(factors)}개로 phi 계산 → d 복원 → 복호")
print(f"[+] FLAG = {mb.decode()}")

플래그가 그대로 떨어진다.

DH{607bf0b239c83a8ff069bd619c9b47c69471207e74ca9cf68cef274891f544f9}

✅ 교차검증 — 시드 재현과 재암호화

풀이가 우연이 아니라는 걸 두 가지로 못 박았다.

하나는 출제 스크립트의 시드 재현이다. set_random_seed(777) 은 결정적이라, 같은 시드로 sample(p, 777) 을 돌리면 출제자가 뽑은 소수 집합이 그대로 재현된다. 그 곱이 N 과 같은지 확인하면 인수분해가 정확했다는 강한 증거가 된다.

# verify_sage.sage — 동일 시드로 소수 집합 재현 후 곱 == N 확인
import re
v = dict(re.findall(r"(\w+)\s*=\s*(\d+)", open("extracted/output.txt").read()))
e, n, c = Integer(v["e"]), Integer(v["n"]), Integer(v["c"])
 
set_random_seed(777)
p = list(prime_range(11, 8296))
primes = sample(p, 777)
print("재현한 소수 곱 == N :", prod(primes) == n)
print("min/max 소수 :", min(primes), max(primes))
 
phi = prod(pi - 1 for pi in primes)
d = inverse_mod(e, phi)
m = Integer(pow(c, d, n))
mb = int(m).to_bytes((int(m).bit_length() + 7) // 8, "big")
print("FLAG :", mb.decode())

prod(primes) == n 이 True. 우리가 시행나눗셈으로 찾은 소인수 집합이 출제자가 실제로 뽑은 것과 완전히 같다는 뜻이다. 그리고 나온 플래그도 동일하다.

다른 하나는 재암호화다. 복원한 평문 m 을 다시 pow(m, e, N) 으로 암호화하면 주어진 c 와 같아야 한다. 실제로 pow(m, e, n) == c 가 True 로 확인됐다 — 개인키 d 를 제대로 복원했다는 결정적 증거다.

📝 결론

RSA의 안전성은 모듈러스의 크기가 아니라 가장 큰 소인수의 크기에서 나온다.

이 문제는 소수 777개를 곱해 모듈러스를 8827비트까지 부풀렸지만, 그 소수들이 전부 8296 미만이라 아무 의미가 없었다. 8296까지 시행나눗셈 한 번이면 통째로 갈라지고, 서로 다른 소수의 곱이라 φ(N)=∏(pᵢ−1) 로 개인키까지 곧장 복원된다. "커 보이는 숫자"는 심리적 미끼였을 뿐이다.

• 소인수는 충분히 커야 한다. multi-prime RSA를 쓰더라도 각 소수가 최소 수백 비트는 되어야 안전하다. 작은 소수를 많이 곱해 크기만 키운 모듈러스는 smooth해서 시행나눗셈·Pollard p−1·ECM 같은 방법에 즉시 무너진다.
• 모듈러스의 비트 수를 안전성으로 착각하지 말자. 8827비트라도 B-smooth면 B까지의 시행나눗셈으로 끝난다. 실무의 RSA 키 생성 라이브러리가 "서로 다른 큰 소수 두 개"를 고집하는 데는 이유가 있다.
• 암호 CTF에서는 생성 스크립트부터 읽자. 숫자의 크기가 아니라 그 숫자가 어떻게 만들어졌는지 가 취약점을 결정한다. 여기서도 prime_range(11, 8296) 한 줄이 문제 전체를 열어 줬다.
• 랜덤 시드 고정은 그 자체로 취약점이다. set_random_seed(777) 처럼 시드가 코드에 박혀 있으면 소수 선택 과정을 그대로 재현할 수 있다. 이 문제는 시드 없이도 풀리지만, 시드 고정은 별개의 재현 공격 표면을 만든다.