문제 설명
There are common things between us... those common prime factors!
키워드
Common Modulus Attack, RSA
Common Modulus Attack
동일한 모듈러($N$) 값으로 각기 다른 공개지수 $e_1, e_2 (\text{gcd}(e_1, e_2) = 1)$를 사용하여 암호화 된 평문을 알아내는 공격이다.
$C_1 \equiv M^{e_1} \pmod{N}$
$C_2 \equiv M^{e_2} \pmod{N}$
$\text{gcd}(e_1, e_2) = 1$이므로 $s \cdot e_1 + t \cdot e_2 = 1$인 정수 $s,t$가 존재한다.
$s, t$는 Extended Euclidean Algorithm으로 구할 수 있다.
$C_1^s \equiv M^{e_1 \cdot s} \pmod{N}$
$C_2^t \equiv M^{e_2 \cdot t} \pmod{N}$
$C_1^s \times C_2^t \equiv M^{e_1 \cdot s} \times M^{e_2 \cdot t} \equiv M^{e_1 \cdot s + e_2 \cdot t} \equiv M \pmod{N}$
소스코드
from Crypto.Util.number import getPrime, GCD
import os
import random
random.seed(os.urandom(10))
with open("flag", "rb") as f:
flag = f.read()
assert 1 < len(flag) < 128
plaintexts = [os.urandom(len(flag)) for _ in range(999)]
last_pt = list(flag)
for i in range(999):
for j in range(len(flag)):
last_pt[j] ^= plaintexts[i][j]
plaintexts.append(bytes(last_pt))
mods = [[] for _ in range(1000)]
select = list(range(1000))
e = 0x10001
for _ in range(1000):
while True:
prime = getPrime(256)
if GCD(e, prime - 1) == 1:
break
random.shuffle(select)
choices = select[:4]
for ch in choices:
mods[ch].append(prime)
if len(mods[ch]) == 4:
select.remove(ch)
mods = [a[0] * a[1] * a[2] * a[3] for a in mods]
for pt, mod in zip(plaintexts, mods):
pt = int.from_bytes(pt, "big")
ct = pow(pt, e, mod)
print(ct, mod)소스코드 분석
1. 플래그 쪼개기
plaintexts = [os.urandom(len(flag)) for _ in range(999)]
last_pt = list(flag)
for i in range(999):
for j in range(len(flag)):
last_pt[j] ^= plaintexts[i][j] #
plaintexts.append(bytes(last_pt))- 랜덤한 평문 999개를 생성한다.
- 999개의 랜덤한 평문과 플래그를 XOR 연산한다.
- $P_{1000} = \text{Flag} \oplus P_1 \oplus P_2 \oplus \dots \oplus P_{999}$
- 앞 반복문에서 생성한 $P_{1000}$을 plaintexts 리스트에 붙여넣는다.
- plaintexts 리스트에는 1,000개의 데이터가 들어있게된다.
- 앞의 999개 ($R_1 \dots R_{999}$): 그냥 랜덤 값, 마지막 1개 ($R_{1000}$): 플래그와 앞의 모든 랜덤 값을 합친(XOR) 값
2. RSA 키 생성
mods = [[] for _ in range(1000)]
select = list(range(1000))- mods: 1,000개의 빈 리스트를 담고 있는 리스트
- select: 0부터 999까지의 숫자가 들어있는 리스트
e = 0x10001
for _ in range(1000):
while True:
prime = getPrime(256)
if GCD(e, prime - 1) == 1:
break
random.shuffle(select)
choices = select[:4]
for ch in choices:
mods[ch].append(prime)
if len(mods[ch]) == 4:
select.remove(ch)- 공개지수 : 0x10001
- 반복문은 1000번 반복된다.
- 새로운 256비트 소수 prime 하나를 생성한다.
- e와 p-1이 서로소인지 확인한다. (RSA 조건 검사)
- select 리스트를 무작위로 섞는다.
- 무작위로 섞인 select 리스트 앞의 4개를 뽑아서 choices 리스트에 저장한다.
- 뽑힌 4개의 인덱스(ch)에 해당하는 mods 리스트에 방금 만든 소수 prime을 추가한다.
- 서로 다른 4개의 mods 인덱스가 같은 소수를 하나씩 나눠 가지게 된다.
- 만약 어떤 인덱스(ch)의 리스트 길이가 4가 되었다면, select 리스트에서 그 인덱스를 지워버린다.
[예시]
[Loop 1회차]
1. 소수 생성: prime = $P_1$ 생성
2. 셔플 & 선택: select를 섞었더니 앞 4개가 [10, 55, 0, 999]가 나옴.
3. 할당 (mods 업데이트): mods[10] = [$P_1$], mods[55] = [$P_1$], mods[0] = [$P_1$], mods[999] = [$P_1$]
4. 제거 확인: 아무도 4개가 안 찼으므로 select에서 제거 안 함.
[Loop 2회차]
1. 소수 생성: prime = $P_2$ 생성
2. 셔플 & 선택: select를 다시 섞었더니 앞 4개가 [0, 55, 2, 3]이 나옴. (0번, 55번이 또 걸림)
3. 할당: mods[0] = [$P_1, P_2$] (누적됨), mods[55] = [$P_1, P_2$] (누적됨) , mods[2] = [$P_2$], mods[3] = [$P_2$]
4. 제거 확인: 아직 4개 꽉 찬 것 없음.
[...중략...]
[Loop N회차 (누군가 꽉 차는 순간)]
- 가정: 0번(mods[0])이 이미 [$P_1, P_2, P_{50}$] 3개를 가지고 있었음.
1. 소수 생성: prime = $P_{N}$ 생성
2. 셔플 & 선택: select에서 [0, 8, 12, 99]가 뽑힘.
3. 할당: mods[0] = [$P_1, P_2, P_{50}, P_{N}$], 나머지 8, 12, 99번도 $P_{N}$ 추가됨.
4. 제거 확인: len(mods[0])이 4가 됨. select.remove(0) 실행.이제 select 리스트에는 0이 영원히 사라짐. (더 이상 소수 안 받음)
3. 암호화 및 출력
mods = [a[0] * a[1] * a[2] * a[3] for a in mods]- mods 리스트에 들어있는 4개의 소수를 다 곱해서 모듈러스 $N$을 만든다.
- 모듈러스 $N4은 1024비트 크기가 된다 (256 x 4 = 1024)
for pt, mod in zip(plaintexts, mods):
pt = int.from_bytes(pt, "big")
ct = pow(pt, e, mod)
print(ct, mod)- plaintexts: 앞서 만든 1,000개의 평문 조각 리스트 (999개 랜덤 + 1개 XOR 합)
- mods: 앞서 만든 1,000개의 RSA 모듈러스($N$) 리스트
- zip: 두 리스트에서 하나씩 꺼내서 짝을 지어준다.
- 1번째 루프: pt = 0번 평문, mod = 0번 모듈러스($N_0$)
- 2번째 루프: pt = 1번 평문, mod = 1번 모듈러스($N_1$)
- ... (1,000번 반복)
- RSA는 숫자(정수)를 가지고 계산하는 수학 알고리즘입니다. 바이트 상태로는 계산할 수 없다.
- 따라서 바이트 형태인 pt를 빅 엔디안 방식으로 정수로 변환한다.
- pow 함수를 사용해 pt를 RSA 암호화해서 ct에 저장한다.
- 암호문과 공개키 모듈러스를 화면에 출력한다.
취약점 분석
보통 RSA는 $N$을 인수분해하는 것이 불가능에 가까워야 안전하지만, 이 코드는 모듈러스들이 소수를 서로 공유하고 있기 때문에 간단한 GCD 연산만으로 모든 $N$을 쉽게 박살낼 수 있다.
random.shuffle(select)
choices = select[:4]
for ch in choices:
mods[ch].append(prime)- 정상적인 RSA: $N_A = p_A \times q_A$, $N_B = p_B \times q_B$ (소수가 겹치지 않음).
- 이 코드의 RSA:
- $N_A = \mathbf{p} \times q \times r \times s$
- $N_B = \mathbf{p} \times x \times y \times z$
- 결과: $N_A$와 $N_B$가 소수 $\mathbf{p}$를 공유하고 있다.
공격
공격 시나리오
1. GCD로 소수 추출하기
우리는 총 1000개의 모듈러스 $N_0, N_1, \dots, N_{999}$를 가지고 있다. 이들 중 임의의 두 개, $N_i$와 $N_j$를 골라 GCD를 구해보자.
$\text{GCD}(N_i, N_j)$
- CASE 1: 두 모듈러스가 공유하는 소수가 없다 -> 결과는 1
- CASE 2: 두 모듈러스가 같은 소수 $p$를 받았다 -> 결과는 $p$
이 코드는 모든 소수를 모듈러스 4개씩과 공유하도록 짰기 때문에 1000개의 $N$을 서로서로 GCD를 해보면 모든 소인수를 찾을 수 있게된다.
2. 모듈러스 분해
GCD를 통해서 찾은 소수 $p$를 이용해서 $N$을 나눈다.
이 과정을 반복하면, 모든 사용자의 $N$을 구성하는 소수들을 전부 찾아낼 수 있다. 즉 소인수분해 문제가 단순 나눗셈 문제로 변하게 된다.
3. 개인키 복구 및 복호화
각 $i$에 대해 4개의 소수 $(p_i, q_i, r_i, s_i)$를 모두 찾았다면, 개인키를 만들 수 있다.
1. 오일러 피 함수 ($\phi$) 계산
$\phi(N_i) = (p_i - 1)(q_i - 1)(r_i - 1)(s_i - 1)$
2. 개인키 ($d$) 계산
$d_i = e^{-1} \pmod{\phi(N_i)}$
3. 복호화
$M_i = C_i^{d_i} \pmod{N_i}$
이 과정을 1000개에 대해 모두 수행하여, 평문 조각들을 전부 얻어 낸다.
4. 최종 플래그 계산
1,000개의 조각($P_1 \dots P_{1000}$)을 다 모았으면 이 조각들을 모두 XOR 한다.
$\text{Result} = P_1 \oplus P_2 \oplus \dots \oplus P_{999} \oplus P_{1000}$
$P_{1000}$은 아까 우리가 계산해둔 식($\text{Flag} \oplus P_1 \oplus \dots \oplus P_{999}$)과 같다.
$\text{Result} = P_1 \oplus P_2 \oplus \dots \oplus P_{999} \oplus (\text{Flag} \oplus P_1 \oplus P_2 \oplus \dots \oplus P_{999})$
XOR 연산은 순서를 바꿔도 상관없고(교환법칙), 같은 것을 두 번 하면 사라진다($A \oplus A = 0$).
식에서 같은 것끼리 짝을 지어보면...
$\text{Result} = (P_1 \oplus P_1) \oplus (P_2 \oplus P_2) \oplus \dots \oplus (P_{999} \oplus P_{999}) \oplus \text{Flag}$
$\text{Result} = 0 \oplus 0 \oplus \dots \oplus 0 \oplus \text{Flag}$
$\text{Result} = \text{Flag}$
공격 코드
import sys
from math import gcd
def solve():
filename = 'output.txt'
try:
with open(filename, 'r') as f:
content = f.read()
except FileNotFoundError:
print(f"Error: {filename} not found.")
return
# 숫자 파싱
tokens = content.split()
numbers = [int(t) for t in tokens if t.isdigit()]
pairs = []
for i in range(0, len(numbers), 2):
pairs.append((numbers[i], numbers[i+1]))
# 마지막 1000개 데이터 사용
if len(pairs) > 1000:
pairs = pairs[-1000:]
print(f"Loaded {len(pairs)} pairs.")
mods = [p[1] for p in pairs]
# 1. 공통 소인수 찾기 (Batch GCD)
primes = set()
n = len(mods)
for i in range(n):
if len(primes) >= 1000:
break
for j in range(i + 1, n):
g = gcd(mods[i], mods[j])
# 합성수(2개 이상의 소수 곱)를 거르기 위해 비트 길이 체크 추가
# 소수는 256비트이므로 300비트 미만인 것만 수집
if g > 1 and g < mods[i] and g.bit_length() < 300:
primes.add(g)
print(f"Found {len(primes)} unique prime factors.")
sorted_primes = sorted(list(primes))
# 2. 복호화
plaintexts = []
e = 0x10001
for i in range(len(pairs)):
ct, N = pairs[i]
# 내 모듈러스 N의 소인수 4개 찾기
factors = []
for p in sorted_primes:
if N % p == 0:
factors.append(p)
if len(factors) == 4:
break
if len(factors) == 4:
p, q, r, s = factors
phi = (p-1)*(q-1)*(r-1)*(s-1)
d = pow(e, -1, phi)
pt_int = pow(ct, d, N)
# 바이트 변환
byte_len = (pt_int.bit_length() + 7) // 8
plaintexts.append(pt_int.to_bytes(byte_len, 'big'))
else:
# 실패 시 빈 바이트 (XOR에 영향 없음, 하지만 하나라도 실패하면 플래그 깨짐)
plaintexts.append(b'')
# 3. 플래그 XOR 복구
if not plaintexts:
return
max_len = max(len(p) for p in plaintexts)
final_res = bytearray(max_len)
for pt in plaintexts:
if not pt: continue
padded = pt.rjust(max_len, b'\x00')
for k in range(max_len):
final_res[k] ^= padded[k]
try:
print(f"Flag: {final_res.decode('utf-8')}")
except:
print(f"Flag (hex): {final_res.hex()}")
if __name__ == "__main__":
solve()'Cryptography > Cryptography CTF' 카테고리의 다른 글
| [Dreamhack] uncommon e (0) | 2026.01.27 |
|---|---|
| [Dreamhack] TOP secret! (0) | 2026.01.22 |
| [Dreamhack] Textbook-RSA (0) | 2026.01.22 |
| [Dreamhack] safeprime (0) | 2026.01.18 |
| [Dreamhack] Padding Miracle Attack (0) | 2025.11.17 |
