문제: DreamHack — uncommon e 분류: Crypto 난이도: 🥈 Silver 3 FLAG:
DH{7e532757ebddde149f45c32156e58421e95b5c691b668f1681677af9495f7e36}
RSA 문제인데 주는 게 좀 특이하다. 모듈러스 N 하나에, 지수가 e1, e2 두 개, 그리고 같은 플래그를 각각으로 암호화한 암호문 c1, c2 가 전부다. 소수도, 개인키도 없다.
지수를 두 개나 준다는 게 실마리다. 같은 N, 같은 평문을 서로 다른 지수로 두 번 암호화했다면 공통 모듈러스 공격(Common Modulus Attack) 이 바로 떠오른다. 여기에 이 문제는 "e 가 uncommon 하다"는 이름값을 하는 함정을 하나 더 얹었다.
문제 개요
| 항목 | 내용 |
|---|---|
| 문제명 | uncommon e |
| 난이도 | 🥈 Silver 3 |
| 분류 | Crypto (RSA) |
| 제공 파일 | prob.py, output.txt |
| 핵심 취약점 | 같은 N·평문을 gcd 가 1인 두 지수로 암호화 → 공통 모듈러스 공격 |
파일만으로 끝나는 오프라인 문제라 서버는 필요 없다. output.txt 에 박힌 N, e1, e2, c1, c2 만으로 평문을 복원한다.
풀이 흐름은 짧다. 소스에서 왜 개별 복호가 막혀 있는지 확인하고 → gcd(e1, e2) = 1 을 근거로 확장 유클리드를 돌려 → c1^a · c2^b 로 평문을 바로 뽑는다.
🧩 배경 — RSA 와 공개 지수 e
RSA 는 공개키 (N, e) 로 암호화하고 개인키 d 로 복호한다.
암호화 : c = m^e mod N
복호화 : m = c^d mod N여기서 d 는 e 의 모듈러 역원, 즉 d = e⁻¹ mod φ(N) 이다. φ(N) = (p-1)(q-1) 은 오일러 파이 함수고, 이 역원이 존재하려면 gcd(e, φ(N)) = 1 이어야 한다. 그래서 보통 e = 65537 같은 소수를 쓴다 — φ 와 서로소일 확률이 높으니까.
이 조건이 깨지면 어떻게 될까. gcd(e, φ(N)) > 1 이면 e 는 φ 에서 역원이 없다. 개인키 d 자체를 만들 수 없으니, 그 지수로 암호화된 암호문은 표준적인 방법으로는 복호가 안 된다.

이 문제 이름이 "uncommon e" 인 이유가 여기 있다. 흔한(common) e = 65537 을 안 쓰고, 일부러 φ 와 공약수를 갖는 지수를 골랐다. 개별 복호를 막으려는 장치다.
🔬 코드 정찰
prob.py 를 열어 지수를 어떻게 고르는지 본다.
from Crypto.Util.number import getPrime, GCD, bytes_to_long
FLAG = b"DH{????????????????????????}"
FLAG = bytes_to_long(FLAG)
while True:
p = getPrime(1024)
q = getPrime(1024)
N = p * q
for e1 in range(0x100, 0x10001):
if GCD(p - 1, e1) >= 0x100: # much better!
break
for e2 in range(0x100, 0x10001):
if GCD(q - 1, e2) >= 0x100: # This is nice!!
break
if GCD(e1, e2) == 1: # UN-UN common == common :P
break
FLAG_enc1 = pow(FLAG, e1, N)
FLAG_enc2 = pow(FLAG, e2, N)
주석의 능청스러운 말투("Stop generating that stupid COMMON e")와 달리, 코드가 하는 일은 명확하다.
e1은gcd(p-1, e1) ≥ 0x100인 첫 값 — 즉p-1과 256 이상의 공약수를 갖는다.e2는gcd(q-1, e2) ≥ 0x100인 첫 값 —q-1과 256 이상의 공약수를 갖는다.φ(N) = (p-1)(q-1)이므로 두 지수 모두 φ 와 큰 공약수를 갖는다. 개별 복호는 막혔다.- 그런데 마지막 조건,
gcd(e1, e2) == 1을 만족할 때까지 소수를 다시 뽑는다.
마지막 줄이 스스로 문을 열어 준다. output.txt 의 공개값 크기와 지수의 정체를 확인해 보자.
# peek.py — output.txt 정찰
from Crypto.Util.number import GCD
# ... N, e1, e2, c1, c2 를 읽어 크기와 소인수분해 출력 ...
print(f"N : {N.bit_length()} bit")
print(f"e1 : {e1} = {factor(e1)}")
print(f"e2 : {e2} = {factor(e2)}")
print(f"GCD(e1, e2) : {GCD(e1, e2)}")
N 은 2048비트(1024비트 소수 두 개의 곱), e1 = 26107 은 소수, e2 = 416 = 2⁵·13. 그리고 gcd(e1, e2) = 1. 같은 N 과 같은 평문을 서로소인 두 지수로 암호화한 그림이 완성됐다. 공통 모듈러스 공격이 그대로 들어맞는 조건이다.
🐛 삽질 — 개별 복호부터 시도
▶🐛 삽질 — 한 암호문만 붙잡고 d 를 구하려다 막힘
처음엔 습관대로 "일단 하나만 풀자" 싶었다. c1 하나만 있어도 d1 = e1⁻¹ mod φ 만 구하면 복호되니까. 문제는 두 가지다.
N을 인수분해해야 φ 를 아는데, 1024비트 소수 두 개라 인수분해는 불가능하다.- 설령 φ 를 안다 쳐도,
gcd(e1, φ) ≥ 0x100이라e1의 역원 자체가 존재하지 않는다.
두 번째가 진짜 벽이다. 작은 소수로 prob.py 의 지수 선택 로직을 그대로 재현해서 확인해 봤다.
# toy_uncommon.py — 작은 소수로 prob.py 키 생성을 재현
while True:
p = getPrime(256); q = getPrime(256)
for e1 in range(0x100, 0x10001):
if GCD(p - 1, e1) >= 0x100: break
for e2 in range(0x100, 0x10001):
if GCD(q - 1, e2) >= 0x100: break
if GCD(e1, e2) == 1: break
phi = (p - 1) * (q - 1)
print("GCD(e1, phi) =", GCD(e1, phi)) # 1 이 아니다
inverse(e1, phi) # ValueError
inverse(e1, phi) 는 base is not invertible for the given modulus 로 죽는다. 단일 지수로는 복호 키 d 를 못 만든다. c1, c2 를 따로따로 붙잡는 접근은 원천적으로 막혀 있다는 뜻이다.
그러니 두 암호문을 함께 써야 한다.
💣 핵심 — Common Modulus Attack
같은 모듈러스 N, 같은 평문 m, 서로소인 두 지수. 이 세 조건이 모이면 개인키 없이 평문이 나온다.
gcd(e1, e2) = 1 이면 확장 유클리드 알고리즘으로 다음을 만족하는 정수 a, b 를 구할 수 있다(베주 항등식).
a·e1 + b·e2 = 1이제 두 암호문을 각각 a, b 제곱해 곱하면 지수가 더해진다.
c1^a · c2^b = (m^e1)^a · (m^e2)^b
= m^(a·e1 + b·e2)
= m^1
= m (mod N)φ(N) 도, 개별 지수의 역원 d 도 등장하지 않는다. 오직 지수의 정수 선형결합만 이용하기 때문에, 앞에서 개별 복호를 막았던 "e 와 φ 의 공약수" 장치가 여기선 아무 영향을 못 준다. 출제자가 걸어 둔 자물쇠와 무관한 문으로 들어가는 셈이다.
한 가지 실무 포인트. a, b 중 하나는 음수가 나온다(여기선 a = -173). 음의 지수는 그대로 계산할 수 없으니, 해당 암호문의 모듈러 역원을 취한 뒤 양의 지수로 바꿔 거듭제곱한다. c1^(-173) 은 (c1⁻¹ mod N)^173 으로 처리한다.

🎯 Full Exploit
공격을 그대로 스크립트로 옮긴다. 확장 유클리드로 계수를 구하고, 음의 지수는 역원으로 처리해 c1^a · c2^b mod N 을 계산하면 끝이다.
from Crypto.Util.number import long_to_bytes
# output.txt 의 공개값 (일부 생략)
N = 18564839028340970630632687927085732690660...978989538340075110803 # 2048-bit
e1 = 26107
e2 = 416
c1 = 75270794888358245501765894323847809211380...194072814312710
c2 = 55534679163927793023196503211616823602913...257879728088984
def egcd(a, b):
if b == 0:
return a, 1, 0
g, x, y = egcd(b, a % b)
return g, y, x - (a // b) * y
def signed_pow(c, e, n):
if e < 0: # 음의 지수는 모듈러 역원으로
c = pow(c, -1, n)
e = -e
return pow(c, e, n)
g, a, b = egcd(e1, e2) # a·e1 + b·e2 = gcd(e1,e2) = 1
assert g == 1
m = (signed_pow(c1, a, N) * signed_pow(c2, b, N)) % N
print(long_to_bytes(m).decode())
a = -173, b = 10857. 두 암호문을 조합하니 평문이 그대로 떨어진다.
DH{7e532757ebddde149f45c32156e58421e95b5c691b668f1681677af9495f7e36}✅ 검증
서버가 없는 문제라 "정말 이게 맞나" 싶으면 스스로 확인할 수 있다. 복원한 평문을 다시 e1, e2 로 암호화해서 output.txt 의 c1, c2 와 같은지 보면 된다.
from Crypto.Util.number import bytes_to_long
FLAG = b"DH{7e532757ebddde149f45c32156e58421e95b5c691b668f1681677af9495f7e36}"
m = bytes_to_long(FLAG)
print("m^e1 mod N == c1 :", pow(m, e1, N) == c1)
print("m^e2 mod N == c2 :", pow(m, e2, N) == c2)
둘 다 True. 복원한 평문이 두 암호문을 모두 재현하니, 서버에 물어보지 않아도 정답이 확실하다. 실제로 이 플래그를 제출해 통과했다.
📝 결론
같은 모듈러스로 같은 평문을 두 번 암호화하면 안 된다.
이 문제의 방어 장치는 "e 를 φ 와 공약수를 갖게 골라 개별 복호를 막는다"였다. 발상 자체는 나쁘지 않다. 그 지수 하나만 놓고 보면 정말로 d 가 존재하지 않으니까. 하지만 같은 N, 같은 m 으로 암호문을 하나 더 내주는 순간, 공격자는 개인키를 구할 필요가 없어진다. 두 지수가 서로소이기만 하면 지수의 선형결합으로 평문이 나온다.
공통 모듈러스 공격은 e 나 φ 의 성질과 무관하다.
베주 계수 a·e1 + b·e2 = 1 만 있으면 성립한다. 그래서 "e 를 이상하게 골랐으니 안전하겠지"라는 직관이 통하지 않는다. 지수를 아무리 특이하게 잡아도, 같은 평문을 서로소인 두 지수로 노출하는 구조 자체가 취약점이다.
실무에서의 교훈은 단순하다. 여러 수신자에게 같은 메시지를 보낼 때 모듈러스를 재사용하지 말 것, 그리고 같은 키 재료로 같은 평문을 여러 번 암호화하지 말 것. 표준 RSA-OAEP 처럼 매번 임의 패딩을 섞으면 "같은 평문"이라는 전제 자체가 깨져 이런 공격이 통하지 않는다.
Comments
댓글
댓글을 남기려면 로그인이 필요해요. (네이버 · 구글 계정)
댓글 불러오는 중…