[🥉 Bronze 3] 주기 16 비제네르를 열별 빈도로 깨다 — DreamHack EVER-igen 풀이

문제: DreamHack — EVER-igen 분류: Crypto 난이도: 🥉 Bronze 3 FLAG: DH{10587bd243d302e95d4b4b0fe331166605b85dd6660e18a305e1fc3db72bf3be}

비제네르 암호로 문장을 가린 문제다. 키가 16글자라 그냥 전부 시도할 수는 없지만, 비제네르의 구조상 같은 키가 규칙적으로 반복된다. 그 반복을 열로 쪼개면 어려운 다중치환이 쉬운 단일치환 16개로 분해된다.

문제 개요

output.txt의 암호문만으로 오프라인에서 풀 수 있다.

🔬 코드 정찰 — 62자 알파벳 비제네르

prob.py의 암호는 대문자·소문자·숫자 62자를 한 알파벳으로 쓰는 비제네르다.

words = ascii_uppercase + ascii_lowercase + digits   # 62자
 
class Vigenere:
    def shift(self, a, d):
        if a not in words: return a                  # 공백·문장부호는 그대로
        return words[(words.index(a) + d) % len(words)]
 
    def encrypt(self, pt):
        return "".join(self.shift(pt[i], self._key[i % len(self._key)]) for i in range(len(pt)))
 
key = [random.randint(0, len(words)) for _ in range(16)]   # 16글자 키

각 글자를 key[i % 16]만큼 시프트한다. words에 없는 문자(공백, 마침표 등)는 시프트하지 않고 통과시키지만, 키 인덱스 i는 전체 위치를 따라 계속 증가한다. 키는 16글자, 각 값은 0~62이라 키공간이 62^16이다. 통째로 전수조사하기엔 너무 크다.

💣 핵심 — 주기를 열로 쪼갠다

비제네르의 약점은 키가 주기적으로 반복된다는 것이다. 키 길이가 16이니, 전체 문자열에서 위치 i가 i mod 16으로 같은 자리들은 전부 같은 키 값으로 시프트됐다.

그래서 암호문을 i mod 16 기준으로 16개 열로 나누면, 각 열은 단 하나의 시프트만 적용된 단일치환(카이사르) 암호가 된다. 62가지 시프트만 시도하면 되는 문제 16개로 쪼개진 것이다.

맞는 시프트는 어떻게 고를까. 평문이 영어 문장이라는 점을 쓴다. 영어는 소문자가 압도적으로 많다(e, t, a, o …). 어떤 시프트로 복호했을 때 그 열의 문자들이 소문자 영어 글자에 몰리면, 그게 정답 시프트다. 열마다 소문자 빈도 점수가 최대인 시프트를 고르면 키 한 글자가 정해진다.

🎯 풀이 — 열별 빈도로 키 16글자 복원

각 열에 대해 62가지 시프트를 돌리고, 복호 결과의 소문자 영어 빈도 점수가 가장 높은 시프트를 그 자리 키로 삼는다.

# solve.py (핵심)
ct = open("output.txt").read().split(">",1)[1].strip()
 
def score(chars):                                   # 영어다움 로그가능도
    s = 0.0
    for c in chars:
        if c in ascii_lowercase: s += math.log(freq.get(c, 0.05) / 100 * 0.90)
        elif c in ascii_uppercase: s += math.log(0.02)
        else: s += math.log(0.01)                   # 숫자
    return s
 
key = []
for col in range(16):
    col_chars = [ct[i] for i in range(len(ct)) if i % 16 == col and ct[i] in words]
    best = max(range(62), key=lambda sh: score(
        [words[(words.index(c) - sh) % 62] for c in col_chars]))
    key.append(best)
 
pt = "".join(words[(words.index(c) - key[i % 16]) % 62] if c in words else c
             for i, c in enumerate(ct))
print(f"key: {key}")
print(pt)

복호하면 비제네르 암호의 유래를 설명하는 영어 문단이 나오고, 그 끝에 플래그가 붙어 있다.

... OK, here comes the flag. DH{10587bd243d302e95d4b4b0fe331166605b85dd6660e18a305e1fc3db72bf3be}

FLAG: DH{10587bd243d302e95d4b4b0fe331166605b85dd6660e18a305e1fc3db72bf3be}

📝 결론

주기가 드러나면 비제네르는 카이사르 여러 개다.

비제네르가 단일치환보다 강한 이유는 자리마다 키가 바뀌기 때문이다. 하지만 키가 반복되는 순간, 같은 키를 쓰는 자리끼리 모으면 각 묶음은 다시 단일치환으로 무너진다. 키 길이만 알면(또는 가정하면) 다중치환이 그만큼의 단순 문제로 분해된다.

언어 통계가 판별자다.

62가지 후보 중 정답을 고르는 건 빈도가 해 준다. 평문이 자연어라는 사실 하나로, 소문자 비중이라는 값싼 지표가 각 열의 정답 시프트를 짚어 준다. 키를 몰라도 평문의 성질을 알면 열쇠가 스스로 드러나는 셈이다.