문제: DreamHack — Common things between us 분류: Crypto 난이도: 🥉 Bronze 2 FLAG:
DH{36e999d28e15c1a508f6d28fe3574cc5cc5b87c934411e844b172ce8494ef2d3}
문제 설명이 대놓고 스포일러다. "There are common things between us... those common prime factors!"(우리 사이엔 공통점이 있다... 바로 그 공통 소인수!) 1000개의 (암호문, 모듈러) 쌍을 주는 문제로, DreamHack CTF Season 7 공식 출제작이다. 모듈러들이 소수를 서로 나눠 쓰고 있어서, 공통 소수는 최대공약수 한 번이면 드러난다.

문제 개요
| 항목 | 내용 |
|---|---|
| 문제명 | Common things between us |
| 난이도 | 🥉 Bronze 2 |
| 분류 | Crypto |
| 제공 파일 | chal.py, output.txt (1000줄, 각 줄 ct mod) |
| 핵심 취약점 | 모듈러들이 소수를 공유 → gcd로 인수분해 |
각 모듈러는 네 소수의 곱이고, 코드상 각 소수는 정확히 네 개의 모듈러에 들어간다.
🔬 코드 정찰 — 소수를 어떻게 나눠 담았나
chal.py를 보면 256비트 소수를 1000개 뽑아, 매번 무작위로 고른 4개의 "칸(모듈러)"에 그 소수를 하나씩 나눠 담는다.
sed -n '20,33p' chal.py
wc -l output.txt
select = list(range(1000))
for _ in range(1000):
prime = getPrime(256) # 소수 하나 생성
random.shuffle(select)
choices = select[:4] # 무작위로 4개의 모듈러 칸을 고름
for ch in choices:
mods[ch].append(prime) # 그 칸들에 같은 소수를 나눠 담음
if len(mods[ch]) == 4:
select.remove(ch) # 4개가 다 차면 더 이상 고르지 않음
mods = [a[0]*a[1]*a[2]*a[3] for a in mods] # 모듈러 = 네 소수의 곱1000개의 소수를 1000개의 모듈러(각각 4개의 소수로 구성)에 나눠 담다 보니, 결과적으로 소수 하나가 평균 4개의 서로 다른 모듈러에 걸쳐 들어간다. 이게 바로 "우리 사이의 공통점"이다.
또 하나, 999개의 무작위 평문과 그것들을 전부 XOR한 마지막 평문(즉 플래그를 나머지와 XOR한 값)을 합쳐 1000개를 만든다.
plaintexts[999] = flag XOR plaintexts[0] XOR ... XOR plaintexts[998]
⇒ flag = plaintexts[0] XOR plaintexts[1] XOR ... XOR plaintexts[999]그래서 모든 평문을 XOR하면 플래그가 된다.
🧱 배경 — 공유 소수와 최대공약수
RSA의 안전성은 모듈러 n = p·q를 인수분해하기 어렵다는 데 있다. 하지만 서로 다른 두 모듈러가 같은 소수를 나눠 쓰면, 그 둘의 최대공약수가 곧 공유 소수가 된다.

출처: Wikimedia Commons, public domain
gcd(n_i, n_j)가 1보다 크면 두 모듈러가 소수를 공유한다는 뜻이고, 그 값이 공유 소수다. 모든 모듈러 쌍의 gcd를 모으면 소수들이 드러나고, 각 모듈러를 그 소수들로 나눠 네 인수를 얻는다. φ = ∏(p-1)로 개인키를 만들어 복호한 뒤, 1000개 평문을 전부 XOR한다.
🎯 풀이 — GCD 인수분해 후 전부 XOR
모든 쌍을 순서대로 대조하는 O(n²) 방식으로 풀었다.
# solve.py
from math import gcd
from Crypto.Util.number import inverse, long_to_bytes, isPrime
primes = set()
for i in range(n):
for j in range(i+1, n):
g = gcd(mods[i], mods[j])
if g > 1 and isPrime(g): primes.add(g) # 공유 소수 수집
e = 0x10001
flag = 0
for ct, mod in zip(cts, mods):
fs = [p for p in primes if mod % p == 0] # 이 모듈러의 소인수
phi = 1
for p in fs: phi *= (p - 1)
d = inverse(e, phi)
flag ^= pow(ct, d, mod) # 복호해 XOR 누적
print("FLAG:", long_to_bytes(flag).decode())
모듈러 1000개면 쌍의 수는 1000×999/2 = 499,500쌍. 이 문제 규모에서는 실제로 20.54초가 걸렸고, 정확히 1000개의 공유 소수를 찾아냈다(소수 1000개가 각각 정확히 4개의 모듈러에 들어간다는 설계와 맞아떨어진다). 복호와 XOR 누적에 5.24초가 더 걸려, 총 25초 정도면 풀린다.
찾아낸 소수 하나하나가 정말 정확히 4개의 모듈러에만 들어가는지도 세어봤다.
cnt = {p: sum(1 for m in mods if m % p == 0) for p in primes}
print("소수 하나가 몇 개 모듈러에 들어가는지 분포:", Counter(cnt.values()))
{4: 1000} — 1000개의 소수 전부가 예외 없이 정확히 4개의 모듈러에 들어간다. chal.py가 설계한 그대로다.
모든 쌍의 gcd로 공유 소수를 캐내 1000개 모듈러를 인수분해하고, 복호한 평문 전부를 XOR하면 플래그가 떨어진다.

FLAG: DH{36e999d28e15c1a508f6d28fe3574cc5cc5b87c934411e844b172ce8494ef2d3}
📝 결론
소수를 나눠 쓰면 RSA는 무너진다. 모듈러를 인수분해하기 어렵다는 전제는, 각 모듈러의 소수가 서로 독립일 때만 유효하다. 여러 인스턴스가 소수를 공유하는 순간 gcd 한 번에 인수가 드러난다. 실제로 2012년 대규모 인터넷 스캔 연구(“Ron was wrong, Whit is right”)에서, 임베디드 기기들이 부팅 직후 엔트로피가 부족한 상태로 RSA 키를 생성하면서 서로 다른 기기끼리 소수를 공유하는 사례가 대량으로 발견된 적이 있다. 이 문제의 설정은 그 실제 사고를 축소해 재현한 셈이다.
O(n²) 방식은 규모가 커지면 그대로 못 쓴다. 이 문제의 1000개 규모에서도 쌍대조에 20초 넘게 걸렸다. 위에서 언급한 실제 연구는 수백만 개의 공개키를 감사해야 했는데, 그 규모에서 모든 쌍을 순서대로 gcd하는 건 현실적으로 불가능하다. 대신 모든 모듈러의 곱을 트리 구조로 미리 계산해두고, 각 모듈러를 그 트리와 한 번씩만 비교하는 배치 GCD(batch GCD, product tree) 기법을 쓰면 n log n에 가까운 시간에 같은 결과를 얻을 수 있다. 이 문제 규모에서는 O(n²)로도 충분하지만, 그 이유(전체 쌍 개수가 아직 감당할 만한 수준이라는 것)를 실제로 시간을 재보며 확인해두면 "언제부터 이 방식이 안 통하는가"에 대한 감이 생긴다.
전체 XOR 구조를 먼저 읽는다. 모든 평문을 XOR하면 플래그가 되는 구조라, 개별 평문의 의미를 몰라도 전부 복호해 XOR만 하면 된다. 암호화 코드가 만든 관계(여기서는 XOR 누적)를 먼저 파악하면 불필요한 계산을 줄일 수 있다.
Comments
댓글
댓글을 남기려면 로그인이 필요해요. (네이버 · 구글 계정)
댓글 불러오는 중…