[🥉 Bronze 2] 공유 소수가 GCD로 새는 1000개의 RSA — DreamHack Common things between us 풀이

2026-07-14·1분 읽기·

[🥉 Bronze 2] 공유 소수가 GCD로 새는 1000개의 RSA — DreamHack Common things between us 풀이

1000개의 RSA 암호문과 모듈러를 주는 문제. 각 모듈러는 네 소수의 곱이고, 각 소수는 정확히 네 개의 모듈러에 공유된다. 두 모듈러의 최대공약수로 공유 소수를 캐내 전부 인수분해하고, 모든 평문을 복호해 XOR하면 플래그가 나온다. 단, 모든 쌍을 O(n²)으로 대조하면 1000개 기준으로 실제 20초 넘게 걸린다 — 실무에서 대규모 키 집합을 감사할 때는 이 방식이 그대로는 안 통한다.

문제: 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 문제 페이지 — "우리 사이엔 공통점이 있다... 바로 그 공통 소인수!"라는 설명이 이미 스포일러다
Common things between us 문제 페이지 — "우리 사이엔 공통점이 있다... 바로 그 공통 소인수!"라는 설명이 이미 스포일러다

문제 개요

항목내용
문제명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
chal.py 핵심부 — 소수 1000개를 뽑아 매번 무작위 4칸에 나눠 담고, 각 모듈러는 4개의 소수가 모이면 곱해서 완성. output.txt는 1000줄
chal.py 핵심부 — 소수 1000개를 뽑아 매번 무작위 4칸에 나눠 담고, 각 모듈러는 4개의 소수가 모이면 곱해서 완성. output.txt는 1000줄
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를 인수분해하기 어렵다는 데 있다. 하지만 서로 다른 두 모듈러가 같은 소수를 나눠 쓰면, 그 둘의 최대공약수가 곧 공유 소수가 된다.

RSA — 소인수를 알면 개인키를 만들 수 있어, 공유 소수가 드러나면 복호가 가능하다
RSA — 소인수를 알면 개인키를 만들 수 있어, 공유 소수가 드러나면 복호가 가능하다

출처: 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())
solve.py 실행 — 499500쌍을 20.54초에 대조해 공유 소수 1000개 발견, 복호+XOR 5.24초 후 플래그
solve.py 실행 — 499500쌍을 20.54초에 대조해 공유 소수 1000개 발견, 복호+XOR 5.24초 후 플래그

모듈러 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()))
분포 확인 — 공유 소수 1000개 전부가 예외 없이 정확히 4개의 모듈러에 들어간다
분포 확인 — 공유 소수 1000개 전부가 예외 없이 정확히 4개의 모듈러에 들어간다

{4: 1000} — 1000개의 소수 전부가 예외 없이 정확히 4개의 모듈러에 들어간다. chal.py가 설계한 그대로다.

모든 쌍의 gcd로 공유 소수를 캐내 1000개 모듈러를 인수분해하고, 복호한 평문 전부를 XOR하면 플래그가 떨어진다.

두 모듈러의 gcd 로 공유 소수를 캐 인수분해하고 모든 평문을 XOR 한다
두 모듈러의 gcd 로 공유 소수를 캐 인수분해하고 모든 평문을 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

댓글

0개

댓글을 남기려면 로그인이 필요해요. (네이버 · 구글 계정)

댓글 불러오는 중…

Related

관련 글

3개
[🥇 Gold 3] 교과서 RSA 실수 9종 세트로 그림 퍼즐 풀기 — DreamHack EZ-RSA-PZ 풀이
blog

[🥇 Gold 3] 교과서 RSA 실수 9종 세트로 그림 퍼즐 풀기 — DreamHack EZ-RSA-PZ 풀이

오프라인 HTML 퍼즐 게임 하나에 RSA 공격 아홉 개가 숨어 있다. 개인키 노출·소수 노출·서명 악용·저지수·공통 소인수·공통 모듈러스·CRT 정수근·Coppersmith·Franklin-Reiter 로 아홉 서브플래그를 뽑고, 각각을 SHA256 해 AES-CBC 키로 직소 조각을 복호한 뒤 9장을 겹쳐 그림 속 최종 플래그를 읽는다.
#dreamhack#ctf#crypto+6
2026-10-10#dreamhack +4
[🥉 Bronze 4] RSA-2048 을 아홉 가지로 두들기고 돌아오니 답은 소스에 있었다 — DreamHack fakeday revenge 풀이
blog

[🥉 Bronze 4] RSA-2048 을 아홉 가지로 두들기고 돌아오니 답은 소스에 있었다 — DreamHack fakeday revenge 풀이

만우절에 올라온 문제. 배포본 prob.py 가 2048비트 RSA 로 flag 를 암호화하고 N, e, c 만 남기는데 소스의 flag 자리에는 가짜로 보이는 리터럴이 박혀 있다. Fermat, Pollard p-1, rho, 저지수, factordb 까지 아홉 항목을 돌려도 흠집이 없고, 설명이 가리킨 Shor 는 4099 큐빗이 필요하다. 답은 그 리터럴 자체였다.
#dreamhack#ctf#crypto+7
2026-08-22#dreamhack +4
[🥈 Silver 4] e 가 (p-1) 을 나누는 RSA — AMM 으로 e차근 구하기 — DreamHack special_rsa_parameter 풀이
blog

[🥈 Silver 4] e 가 (p-1) 을 나누는 RSA — AMM 으로 e차근 구하기 — DreamHack special_rsa_parameter 풀이

공개지수 e=257 이 (p-1) 을 딱 한 번 나눈다. gcd(e, φ(N)) 이 1 이 아니라 d=e⁻¹ mod φ 가 존재하지 않아 평범한 RSA 복호가 막힌다. p·q 가 이미 주어졌으니 CRT 로 mod p / mod q 로 쪼갠 뒤, e차근이 유일한 mod q 는 그대로 풀고, e차근이 257개인 mod p 는 AMM(Adleman-Manders-Miller) 으로 전부 구해 CRT 로 다시 합친다. 257개 후보 중 BISC 로 시작하는 평문이 flag.
#dreamhack#ctf#crypto+6
2026-07-23#dreamhack +4