[🥉 Bronze 2] 거듭제곱 차이 한 줄로 평문을 되돌리다 — DreamHack ICM2022 풀이

문제: DreamHack — ICM2022 분류: Crypto 난이도: 🥉 Bronze 2 FLAG: DH{10112210997116104}

암호문 딱 하나(q)와 공개된 파라미터 일부만 주고 평문을 복원하라는 문제다. 겉보기엔 두 개의 키가 얽힌 복잡한 식이지만, 실제로 비밀은 키 하나의 좁은 범위뿐이다. 정수라는 제약 하나가 그 범위를 정답 하나로 좁혀 준다.

문제 개요

readme.txt가 절반쯤 공개된 파라미터를 알려 주고, "복호한 p를 DH{여기}에 넣으라"고 안내한다. 즉 우리가 구할 건 평문 정수 p 그 자체다.

🧩 배경 — 거듭제곱의 차이에 평문을 실었다

암호화 함수는 평문 p를 두 키의 거듭제곱 차이에 곱해 하나의 유리수 q로 만든다.

def enc(p, n, key1, key2):
    q = (Fraction(p, n+1) * key1**(n+1)) - (Fraction(p, n+1) * key2**(n+1))
    return q

Fraction(p, n+1)을 공통으로 묶으면 식이 단순해진다.

q = (p / (n+1)) · ( key1^(n+1) − key2^(n+1) )

n, key1, key2가 모두 상수라면 q는 p에 어떤 정해진 유리수를 곱한 값일 뿐이다. 그 곱하는 상수만 알면 나눗셈 한 번으로 p가 돌아온다. 이 문제의 전부는 "그 상수, 특히 key1을 어떻게 특정하느냐"다.

🔬 코드 정찰 — 무엇이 공개됐나

readme.txt가 알려 주는 값은 이렇다.

n = 3
key1 = #cencored#
key2 = 95
q = -200640142664324295933714
p = #cencored# (p is number)

n = 3이니 n+1 = 4다. key2 = 95는 공개, q도 공개, 그런데 key1과 p는 가려져 있다. 키 생성 코드를 보면 key1의 범위에 결정적 힌트가 있다.

def key_make():
    n, key1, key2 = 0, 1, 0
    while key2 < key1:            # key2 < key1 인 동안 계속 다시 뽑음
        n = random.randrange(1, 10)
        key1 = random.randrange(1, 100)
        key2 = random.randrange(1, 100)
    return n, key1, key2

while key2 < key1은 조건이 참인 동안 반복하므로, 루프를 빠져나오는 순간엔 key2 >= key1 이다. 즉 key1 <= key2 = 95. 게다가 주어진 q가 음수라는 사실이 범위를 더 좁힌다. q = (p/4)(key1^4 − 95^4)에서 p는 양수(문자들의 ord를 이어 붙인 수)이니, q가 음수이려면 key1^4 − 95^4 < 0, 곧 key1 < 95 여야 한다. 후보는 고작 1..94다.

🧱 배경 — 평문 p는 ASCII 코드를 이어 붙인 수

main.py는 입력 문자열을 이렇게 숫자로 바꾼다.

p = ""
for character in emp:
    p += str(ord(character))     # 각 글자의 ord 를 문자열로 이어 붙임

ord('e') = 101, ord('z') = 122 … 이런 값을 그대로 문자열로 붙여 하나의 큰 정수로 만든다. 그래서 복원한 p를 두세 자리씩 끊어 chr로 되돌리면 원문이 나온다. 아래는 ASCII 코드표로, 우리가 복원할 숫자들이 어떤 문자에 대응하는지 보여 준다.

출처: Wikimedia Commons, public domain

이 사실은 정답 검증에도 쓰인다. 전수조사로 나온 p 후보가 실제 평문이라면, 그 숫자는 반드시 유효한 ASCII 코드(대략 32~126)들로 깔끔하게 쪼개져야 한다. 아무 정수나 되는 게 아니라 "ASCII로 읽히는 정수"라는 조건이 정답을 한 번 더 걸러 준다.

💣 핵심 — 부정방정식을 정수 조건으로 닫는다

식을 p에 대해 풀면 이렇다.

p = 4·q / ( key1^4 − 95^4 )

key1 하나를 모르니 미지수가 둘(값이 하나로 안 정해지는 부정방정식)처럼 보이지만, 여기엔 강한 제약이 두 개 붙는다.

• p는 양의 정수여야 한다 (나눗셈이 딱 떨어져야 한다).
• 그 정수는 ASCII 코드의 나열이어야 한다.

key1을 1..94로 훑으며 4q가 (key1^4 − 95^4)로 나누어떨어지는 경우만 남기면 후보가 확 준다. 거기에 "ASCII로 읽히는가"를 더하면 정답 key1이 유일하게 남는다. 좁은 키 공간 + 정수/포맷 제약의 조합이 이런 부정방정식형 문제를 푸는 전형적인 열쇠다.

🎯 풀이 — key1 전수조사

key1을 1..94로 돌리며 p가 양의 정수인지, ASCII로 쪼개지는지 확인한다.

# solve.py
from fractions import Fraction
n, key2 = 3, 95
q = -200640142664324295933714
for key1 in range(1, 95):
    denom = key1**(n+1) - key2**(n+1)
    p = Fraction(q*(n+1), denom)
    if p.denominator == 1 and p.numerator > 0:      # 정수 & 양수
        s = str(p.numerator)
        dec, i, ok = "", 0, True
        while i < len(s):                           # 2~3자리 ord 로 그리디 디코드
            for L in (2, 3):
                if i+L <= len(s) and 32 <= int(s[i:i+L]) <= 126:
                    dec += chr(int(s[i:i+L])); i += L; break
            else:
                ok = False; break
        print(f"key1={key1}  p={p.numerator}")
        if ok: print(f"  decodes-> {dec!r}")

key1 = 38에서 p = 10112210997116104가 나오고, 이를 두세 자리씩 끊으면 101 122 109 97 116 104 = ord('e','z','m','a','t','h') = "ezmath"로 깔끔하게 읽힌다. readme.txt는 "복호한 p를 넣으라"고 했으니, 플래그는 그 숫자 p 자체다.

FLAG: DH{10112210997116104}

📝 결론

키가 두 개라도 하나가 공개되고 하나가 좁으면 끝이다.

암호식은 두 키의 거듭제곱 차이라는 그럴싸한 모양을 하고 있지만, 한 키가 공개되고 다른 키는 100 미만이라는 순간 실제 비밀은 100가지도 안 된다. 키 공간이 작으면 구조가 복잡해도 전수조사가 답이다.

정수·포맷 제약은 그 자체로 방정식이다.

미지수가 하나 남은 부정방정식이라도, "정수로 떨어져야 한다", "ASCII로 읽혀야 한다" 같은 제약을 걸면 해가 하나로 닫힌다. 자연어 평문이라는 성질과 정수 나눗셈이라는 성질을 판별자로 쓰는 것은 crypto 문제에서 두고두고 통하는 지름길이다.