[🥈 Silver 3] 같은 N, 두 지수로 암호화된 RSA — DreamHack uncommon e 풀이

문제: DreamHack — uncommon e 분류: Crypto 난이도: 🥈 Silver 3 FLAG: DH{7e532757ebddde149f45c32156e58421e95b5c691b668f1681677af9495f7e36}

RSA 문제인데 주는 게 좀 특이하다. 모듈러스 N 하나에, 지수가 e1, e2 두 개, 그리고 같은 플래그를 각각으로 암호화한 암호문 c1, c2 가 전부다. 소수도, 개인키도 없다.

지수를 두 개나 준다는 게 실마리다. 같은 N, 같은 평문을 서로 다른 지수로 두 번 암호화했다면 공통 모듈러스 공격(Common Modulus Attack) 이 바로 떠오른다. 여기에 이 문제는 "e 가 uncommon 하다"는 이름값을 하는 함정을 하나 더 얹었다.

문제 개요

파일만으로 끝나는 오프라인 문제라 서버는 필요 없다. 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 의 지수 선택 로직을 그대로 재현해서 확인해 봤다.

Copy

# 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 처럼 매번 임의 패딩을 섞으면 "같은 평문"이라는 전제 자체가 깨져 이런 공격이 통하지 않는다.