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

문제: DreamHack — special_rsa_parameter 분류: Crypto 난이도: 🥈 Silver 4 FLAG: BISC{special_parameter_for_https://crypto.stackexchange.com/questions/81949/how-to-compute-m-value-from-rsa-if-phin-is-not-relative-prime-with-the-e_ed9fd3b21b8190eb2bd91c56c996e362bfbeeeccdc5ff9692f521127e6193d1f}

제목이 "special parameter" 다. RSA 문제인데 파라미터 하나가 평범하지 않게 잡혀 있고, 그 한 끗 때문에 교과서대로 복호가 안 된다.

문제 파일은 암호화 스크립트 한 개와 출력값 한 개가 전부다. 소수 p, q 까지 그대로 출력돼 있어서 인수분해는 이미 끝나 있는 셈인데, 정작 그걸로 개인키 d 를 못 만든다. 왜 못 만드는지, 그럼 어떻게 뚫는지가 이 문제의 전부다.

cat extracted/special_rsa_parameter.py

문제 개요

풀이 흐름은 간단하다. p, q 가 주어졌으니 CRT 로 mod p 와 mod q 로 나눈다.

mod q 는 gcd(e, q-1)=1 이라 e차근이 하나뿐이라 그냥 풀리고, mod p 는 e | (p-1) 이라 e차근이 257개다. 이 257개를 AMM 알고리즘으로 전부 구한 뒤 mod q 근과 CRT 로 합치면 257개 평문 후보가 나온다. 그중 flag 형식인 것을 고르면 끝이다.

🧩 배경 — RSA 복호는 왜 e⁻¹ mod φ 를 요구하나

RSA 암호화는 C = P^e mod N. 복호는 개인키 d 로 P = C^d mod N 을 계산하는데, 이 d 가 존재하려면 조건이 하나 있다.

P = C^d = (P^e)^d = P^(e·d) mod N
→ e·d ≡ 1 (mod φ(N)) 이어야 P^(e·d) = P^1 = P
→ 즉 d = e⁻¹ mod φ(N)  이 존재해야 함
→ 그러려면 gcd(e, φ(N)) = 1

e 와 φ(N) 이 서로소가 아니면 e 의 역원이 아예 없다. 이 문제는 바로 그 지점을 노렸다.

암호화 스크립트를 보면 p 를 뽑을 때 (p - 1) % e == 0 인 소수만 통과시킨다. 즉 e | (p-1) 이고, p-1 은 φ(N)=(p-1)(q-1) 의 약수이므로 e | φ(N) 이다. 그래서 gcd(e, φ(N)) = e = 257 ≠ 1 이 되고, d 를 만들 수 없다.

while True:
    p = getPrime(1024)
    if (p - 1) % e**2 != 0 and (p - 1) % e == 0:   # ← e | (p-1), 단 e^2 는 아님
        break
q = getPrime(1024)
n = p * q
C = pow(P, e, n)                                    # P = bytes_to_long(flag)

여기서 조건이 두 개인 게 중요하다. (p-1) % e == 0 (나눠떨어짐) 이면서 (p-1) % e**2 != 0 (e² 로는 안 나눠짐). 즉 e 가 p-1 을 딱 한 번 나눈다. 이 "한 번"이 뒤에서 e차근을 구하는 방식을 단순하게 만들어 준다.

🔬 코드 정찰 — 무엇이 주어졌나

parameter.txt 에는 p, q, e, n, C 가 전부 찍혀 있다. 소수까지 공개돼 있으니 인수분해는 공짜다. 진짜 문제는 그 뒤다.

주어진 값이 정말 그 특수조건을 만족하는지, 그리고 표준 RSA 복호가 실제로 막히는지 스크립트로 확인해 봤다.

# check_params.py — 취약 조건 확인 + 표준 RSA 복호 시도
import re
from math import gcd
 
v = {}
for line in open('extracted/parameter.txt'):
    m = re.match(r'\s*(\w+)\s*=\s*(\d+)', line)
    if m:
        v[m.group(1)] = int(m.group(2))
p, q, e, n, C = v['p'], v['q'], v['e'], v['n'], v['C']
phi = (p - 1) * (q - 1)
 
print(f"(p-1) % e    = {(p-1) % e}")       # 0    → e | p-1
print(f"(p-1) % e^2  = {(p-1) % (e*e)}")   # !=0  → 딱 한 번
print(f"(q-1) % e    = {(q-1) % e}")       # !=0  → mod q 는 서로소
print(f"gcd(e, p-1) = {gcd(e, p-1)}")      # 257
print(f"gcd(e, q-1) = {gcd(e, q-1)}")      # 1
try:
    d = pow(e, -1, phi)                     # 표준 복호: 여기서 실패해야 정상
    print("d =", d)
except ValueError as ex:
    print(f"[표준 RSA 복호 불가] pow(e,-1,phi) -> {ex}")

gcd(e, p-1) = 257, gcd(e, q-1) = 1. 그리고 마지막 줄, pow(e, -1, phi) 가 base is not invertible for the given modulus 로 죽는다. 개인키 d 는 정말로 존재하지 않는다. 여기서 멈추면 문제가 끝나 버리니, 다른 길을 찾아야 한다.

정리하면 이렇다.

• mod q : gcd(e, q-1)=1 이라 보통 RSA 처럼 e차근이 유일하다. 쉽게 풀린다.

• mod p : e | (p-1) 이라 e차근이 여러 개(257개) 존재한다. 이 여러 개를 다 구해야 한다.

N 은 이미 p·q 로 갈라져 있으니, 두 경우를 따로 풀고 CRT 로 합치면 된다.

🧱 배경 — e차근이 왜 257개인가

핵심은 곱셈군 (Z/pZ)* 의 구조다. 이 군은 위수 p-1 인 순환군이다.

x^e = C (mod p) 의 해가 몇 개인지는 gcd(e, p-1) 로 정해진다. C 가 e차 잉여(즉 실제로 e제곱수)일 때, 해의 개수는 정확히 gcd(e, p-1) 개다.

• mod q : gcd(e, q-1)=1 → 해 1개. 그래서 dq = e⁻¹ mod (q-1) 로 바로 유일한 근을 구한다.

• mod p : gcd(e, p-1)=257 → 해 257개.

257개가 생기는 이유를 한 줄로 말하면, 근 하나 x₀ 를 찾았을 때 거기에 e차 단위근(ζ^e = 1 인 ζ)을 곱한 x₀·ζ^j 도 전부 근이기 때문이다. (x₀·ζ^j)^e = x₀^e · (ζ^e)^j = C · 1 = C. 이 e차 단위근들은 위수 257(소수)인 순환군을 이루므로 정확히 257개다.

그러니 할 일은 두 가지다. ① mod p 에서 근 하나 x₀ 를 구하고, ② 원시 e차 단위근 ζ 를 하나 찾아 x₀·ζ^j 로 257개를 전부 펼친다. 이게 AMM 알고리즘이 하는 일이다.

💣 핵심 — AMM 으로 mod p 의 257개 e차근

e 가 p-1 을 딱 한 번만 나누는(e² ∤ (p-1)) 덕에 AMM 이 아주 단순해진다. p-1 = e·t 이고 gcd(e, t) = 1 이다.

① 근 하나 x₀ 구하기. t 에 대한 e 의 역원 d = e⁻¹ mod t 를 잡으면, e·d = 1 + k·t 꼴이다. 그러면

C^d = (P^e)^d = P^(e·d) = P^(1 + k·t) = P · (P^t)^k  (mod p)

여기서 (P^t)^e = P^(t·e) = P^(p-1) = 1 이므로 (P^t)^k 는 어떤 e차 단위근이다. 즉 x₀ = C^d mod p 는 "진짜 P 에 단위근 하나가 곱해진" 값 — 257개 근 중 하나다.

② 원시 e차 단위근 ζ 찾기. 아무 g 나 잡아 ζ = g^t mod p 를 계산한다. ζ^e = g^(t·e) = g^(p-1) = 1 이므로 ζ 는 e차 단위근이다. g 가 e차 잉여가 아니면 ζ ≠ 1 이고, 단위근 군의 위수가 소수 257 이라 ζ ≠ 1 이기만 하면 자동으로 원시근(위수 257)이다. g=2,3,… 순서로 g^t ≠ 1 인 첫 값을 쓰면 된다.

③ 257개 전부 펼치기. 모든 e차근은 { x₀·ζ^j : j = 0 … 256 } 이다.

이 mod p 근 257개를 mod q 유일근과 CRT 로 합치면, 원래 평문 P 를 포함한 257개 후보가 나온다. 아래 그림이 전체 흐름이다.

🎯 풀이 / Full Exploit

위 논리를 그대로 옮긴 solve.py 다. 외부 라이브러리 없이 파이썬 표준만으로 돈다.

#!/usr/bin/env python3
import re, sys
from math import gcd
 
def parse_params(path):
    v = {}
    for line in open(path):
        m = re.match(r'\s*(\w+)\s*=\s*(\d+)', line)
        if m:
            v[m.group(1)] = int(m.group(2))
    return v['p'], v['q'], v['e'], v['n'], v['C']
 
def long_to_bytes(a):
    return a.to_bytes((a.bit_length() + 7) // 8, 'big')
 
def crt(r1, m1, r2, m2):                    # x ≡ r1 (mod m1), x ≡ r2 (mod m2)
    inv = pow(m1, -1, m2)
    return r1 + m1 * (((r2 - r1) * inv) % m2)
 
def amm_all_eth_roots(c, e, p):
    """e|(p-1), e^2∤(p-1) 일 때 C 의 mod p e차근 e개 전부."""
    t = (p - 1) // e                        # p-1 = e·t, gcd(e,t)=1
    d = pow(e, -1, t)
    x0 = pow(c, d, p)                        # 근 하나 (P·단위근)
    g = 2                                    # 원시 e차 단위근 ζ = g^t (≠1)
    while pow(g, t, p) == 1:
        g += 1
    zeta = pow(g, t, p)
    roots, cur = [], x0
    for _ in range(e):
        roots.append(cur)
        cur = (cur * zeta) % p
    return roots
 
def main():
    path = sys.argv[1] if len(sys.argv) > 1 else 'extracted/parameter.txt'
    p, q, e, n, C = parse_params(path)
    assert n == p * q
 
    dq = pow(e, -1, q - 1)                   # mod q: 유일근
    Pq = pow(C % q, dq, q)
    roots_p = amm_all_eth_roots(C % p, e, p) # mod p: 257개
    print(f"[*] mod p e차근 개수 = {len(roots_p)}")
 
    flag_re = re.compile(rb'^[A-Za-z0-9_]+\{.*\}$')
    for i, Rp in enumerate(roots_p):
        P = crt(Rp, p, Pq, q) % n
        b = long_to_bytes(P)
        if all(32 <= x < 127 for x in b) and flag_re.match(b):
            print(f"[+] j={i} 후보가 flag 형식과 일치")
            print("[+] FLAG =", b.decode())
            break
 
if __name__ == '__main__':
    main()

돌리면 257개 근 중 j=131 후보가 flag 형식과 맞아떨어진다.

BISC{special_parameter_for_https://crypto.stackexchange.com/questions/81949/
how-to-compute-m-value-from-rsa-if-phin-is-not-relative-prime-with-the-e_...}

flag 안에 대놓고 이 기법을 설명하는 StackExchange 질문 URL 이 박혀 있다 — "how to compute m value from RSA if phi(n) is not relative prime with the e". 문제가 노린 지점을 flag 가 그대로 자백한다.

🚀 검증 — 재암호화 & SageMath 교차확인

복원한 값이 정말 원래 평문인지, 두 가지로 못 박았다.

① 재암호화. 찾은 flag 를 다시 P^e mod n 해서 주어진 C 와 같은지 본다. 같으면 이게 진짜 평문이다.

# verify.py
import re
from Crypto.Util.number import bytes_to_long
 
v = {}
for line in open('extracted/parameter.txt'):
    m = re.match(r'\s*(\w+)\s*=\s*(\d+)', line)
    if m:
        v[m.group(1)] = int(m.group(2))
p, q, e, n, C = v['p'], v['q'], v['e'], v['n'], v['C']
 
flag = open('flag.txt', 'rb').read().rstrip(b'\n')
P = bytes_to_long(flag)
print(f"P^e mod n == C ? {pow(P, e, n) == C}")

P^e mod n == C ? True. 확정이다.

② SageMath 로 e차근 교차검증. 직접 짠 AMM 이 맞는지, Sage 의 nth_root(e, all=True) 로 독립적으로 mod p e차근을 전부 뽑아 개수와 flag 를 비교했다.

# sage_roots.sage
Fp = GF(p)
roots = Fp(C).nth_root(e, all=True)      # mod p 의 모든 e차근
print("mod p e차근 개수 :", len(roots))   # 257
 
Fq = GF(q)
Pq = Fq(C).nth_root(e)                    # mod q 유일근
from sage.arith.misc import CRT
for Rp in roots:
    P = CRT([Integer(Rp), Integer(Pq)], [p, q])
    b = int(P).to_bytes((int(P).bit_length()+7)//8, 'big')
    if b.startswith(b'BISC{'):
        print("FLAG :", b.decode()); break

Sage 도 mod p 근 257개, mod q 유일근, 그리고 같은 flag 를 내놓는다. 직접 구현한 AMM 과 결과가 완전히 일치한다.

📝 결론

e 와 φ(N) 이 서로소가 아니면 표준 RSA 복호가 막힌다.

d = e⁻¹ mod φ(N) 은 gcd(e, φ(N))=1 일 때만 존재한다. 이 문제는 소수 생성 단계에서 (p-1) % e == 0 인 p 만 골라 그 조건을 일부러 깨뜨렸다. 그래서 개인키 자체가 만들어지지 않는다.

막혔으면 e차근 문제로 바꿔 본다.

P 를 구하는 건 결국 x^e = C 의 e차근을 찾는 일이다. N 이 p·q 로 갈라져 있으니 CRT 로 소수 modulus 로 내리면, 각 소수에서 e차근 개수는 gcd(e, p-1) 로 정해진다. 서로소인 쪽은 유일근이라 그냥 풀리고, 나눠떨어지는 쪽은 근이 여러 개라 AMM 으로 전부 구한 뒤 CRT 로 되붙이면 된다.

e² ∤ (p-1) 이 풀이를 쉽게 만든다.

e 가 p-1 을 딱 한 번만 나누면, 근 하나는 C^(e⁻¹ mod t) 로 바로 나오고 나머지는 원시 e차 단위근을 곱해 펼치기만 하면 된다. 만약 e², e³ … 으로 여러 번 나눴다면 일반형 AMM(단위근 지수를 e진 전개로 한 자리씩 맞춰가는 형태)을 써야 하지만, 이 문제는 조건을 한 번으로 못박아 뒀다.

방어 관점. RSA 파라미터는 gcd(e, φ(N))=1 을 반드시 보장해야 한다. e=65537 같은 표준 지수를 쓰고 소수를 무작위로 뽑으면 이 조건은 사실상 항상 성립한다. 문제처럼 소수에 e | (p-1) 같은 인위적 제약을 걸면 개인키가 아예 성립하지 않거나, 성립하더라도 e차근 다중성 때문에 평문 후보가 여러 개로 새어 버린다.