[🥉 Bronze 4] 키 공간이 62,500뿐인 아핀 암호 — DreamHack Affe!n 풀이

2026-07-13·1분 읽기·

[🥉 Bronze 4] 키 공간이 62,500뿐인 아핀 암호 — DreamHack Affe!n 풀이

비밀 문장을 GF(251) 위 아핀 암호로 가린 문제. 키가 두 바이트(각 1~250)뿐이라 가능한 키쌍이 62,500개에 불과하고, 평문에 "cryptography"가 들어 있다는 조건으로 유일 키를 특정할 수 있다. 전수조사로 키를 찾아 복호하면 문장 끝에 플래그가 나온다.

문제: DreamHack — Affe!n 분류: Crypto 난이도: 🥉 Bronze 4 FLAG: DH{3fcd60d46ff03b6fcd3a6d4c71805b131f8f48af5ffdf4fb4b9ab7cf5a09a4ef}

"아핀 암호? 꽤 괜찮은데 :>"라며 비밀 문장을 가려 놓은 문제다. 하지만 아핀 암호의 키는 상수 두 개뿐이고, 이 문제는 그 둘의 범위마저 좁다. 열쇠 꾸러미가 6만 개면 그냥 다 넣어 보면 된다.

아핀 암호 — 키쌍이 62,500개뿐이라 전수조사, 알려진 평문으로 유일 키(79,87)를 특정해 복호
아핀 암호 — 키쌍이 62,500개뿐이라 전수조사, 알려진 평문으로 유일 키(79,87)를 특정해 복호

문제 개요

항목내용
문제명Affe!n
난이도🥉 Bronze 4
분류Crypto
제공 파일prob.py, output.txt (암호문 hex)
핵심 취약점키 공간 250×250=62,500 + 알려진 평문(cryptography) → 전수조사

output.txt의 암호문만으로 오프라인에서 풀 수 있다. 키를 전수조사로 찾아 복호하면 된다.



🔬 코드 정찰 — 상수 두 개짜리 치환

prob.py의 암호화는 GF(251) 위의 아핀 변환이다.

class Affine:
    def __init__(self, key1, key2):
        assert 1 <= key1 <= 250        # 곱하는 상수
        assert 1 <= key2 <= 250        # 더하는 상수
    def encrypt(self, msg):
        return bytes([(self._key1 * b + self._key2) % 251 for b in msg])
 
secret = open("secret", "rb").read()
assert b'cryptography' in secret       # ← 평문에 대한 힌트
secret_enc = Affine(random(1,250), random(1,250)).encrypt(secret)

각 바이트를 enc = (key1·b + key2) mod 251로 바꾼다. 251은 소수라 key1은 항상 역원이 있어 복호도 잘 정의된다. 우리에게 주어진 건 output.txt의 암호문 hex뿐이고 key1, key2는 모른다.

그런데 결정적인 힌트가 코드에 그대로 있다. assert b'cryptography' in secret — 원문 어딘가에 cryptography가 들어 있다는 것이다.


💣 핵심 — 키가 6만 개면 다 넣어 본다

아핀 암호의 키는 (key1, key2) 두 상수뿐이고, 각각 1~250이다. 그러니 가능한 키쌍은 250 × 250 = 62,500개에 불과하다. 요즘 컴퓨터로는 눈 깜짝할 사이다.

전수조사에서 "맞는 키"를 어떻게 알아볼까. 여기서 알려진 평문이 쓰인다. 어떤 키로 복호했을 때 결과에 cryptography라는 문자열이 나타나면, 그게 정답 키다. 6만 개 중 이 조건을 만족하는 건 사실상 하나뿐이다.

복호식은 암호화의 역이다. enc = key1·b + key2를 b에 대해 풀면 이렇게 된다.

b = key1⁻¹ · (enc − key2) mod 251

key1⁻¹은 251이 소수라 pow(key1, -1, 251)로 바로 구한다.



🎯 풀이 — 전수조사 한 바퀴

키쌍 62,500개를 전부 돌며 복호하고, 결과에 cryptography가 있으면 출력한다.

# solve.py
ct = bytes.fromhex(open("output.txt").read().split(">")[1].strip())
 
for k1 in range(1, 251):
    inv = pow(k1, -1, 251)              # 251은 소수 → 항상 역원 존재
    for k2 in range(1, 251):
        dec = bytes((inv * (b - k2)) % 251 for b in ct)
        if b"cryptography" in dec:       # 알려진 평문으로 정답 키 판별
            print(f"key1={k1} key2={k2}")
            print("secret:", dec.decode(errors="replace"))
solve.py 실행 — key1=79 key2=87 복원, 복호한 비밀 문장 끝에 플래그가 붙어 나온다
solve.py 실행 — key1=79 key2=87 복원, 복호한 비밀 문장 끝에 플래그가 붙어 나온다

key1=79, key2=87에서 복호가 맞아떨어진다. 나온 문장은 아핀 암호를 설명하는 지문이고, 그 끝에 플래그가 붙어 있다.

... Now, here comes the flag- DH{3fcd60d46ff03b6fcd3a6d4c71805b131f8f48af5ffdf4fb4b9ab7cf5a09a4ef}

FLAG: DH{3fcd60d46ff03b6fcd3a6d4c71805b131f8f48af5ffdf4fb4b9ab7cf5a09a4ef}



📝 결론

키 공간이 작으면 암호가 아니다.

아핀 암호 자체는 멀쩡한 치환이지만, 키가 두 상수뿐이라 전체가 6만 가지밖에 안 된다. 아무리 잘 섞어도 경우의 수가 이 정도면 그냥 다 시도하는 게 답이다.

알려진 평문 한 조각이 전수조사를 끝낸다.

cryptography라는 단어 하나가 "어느 복호가 맞는지" 판별해 준다. 전수조사는 후보를 만드는 것보다 정답을 알아보는 게 관건인데, 평문의 일부를 알면 그 판별이 공짜로 해결된다.

이 글이 도움이 됐나요?

Comments

댓글

0개

댓글을 남기려면 로그인이 필요해요. (네이버 · 구글 계정)

댓글 불러오는 중…

Related

관련 글

3개
[🥉 Bronze 3] 16비트 시드짜리 스트림 암호 전수조사 — DreamHack STREAMer-Prototype 풀이
blog

[🥉 Bronze 3] 16비트 시드짜리 스트림 암호 전수조사 — DreamHack STREAMer-Prototype 풀이

16비트 상태를 비트 회전시켜 키스트림을 만드는 스트림 암호로 플래그를 XOR한 문제. 시드가 getrandbits(16)이라 경우의 수가 65,536개뿐이고, 플래그가 DH로 시작한다는 조건으로 정답 시드를 가려낸다. 실제로 전수조사를 돌려보면 65536개 중 접두사 조건을 만족하는 시드는 정확히 하나뿐이라, 우연히 걸릴 위험 없이 확실하게 정답이 가려진다.
#dreamhack#ctf#crypto+3
2026-07-13#dreamhack +4
[🥉 Bronze 1] 두 순열로 만든 clock 키스트림 되맞추기 — DreamHack Basic of crypto 풀이
blog

[🥉 Bronze 1] 두 순열로 만든 clock 키스트림 되맞추기 — DreamHack Basic of crypto 풀이

플래그 64바이트를 clock 제너레이터가 만든 키스트림과 XOR한 문제. 키스트림 값은 두 순열 H, M으로 keystream[i] = 8·H[i//8] + M[i%8] 처럼 결정되는데, 알려진 평문(DH{, }, 대문자와 밑줄만) 제약이 강해 순열을 전수조사하면 유일한 플래그가 복원된다. 실제로 40320가지 H 순열 중 39092번째에서 정답이 나오고, 걸린 시간은 0.14초뿐이다.
#dreamhack#ctf#crypto+4
2026-07-14#dreamhack +4
[🥉 Bronze 2] 거듭제곱 차이 한 줄로 평문을 되돌리다 — DreamHack ICM2022 풀이
blog

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

평문을 두 키의 거듭제곱 차이에 곱해 암호문 하나로 내보내는 crypto 문제. 키가 두 개지만 하나는 공개되고 다른 하나는 좁은 범위라, 암호문이 정수로 떨어지는 키를 전수조사하면 평문 정수 p가 그대로 복원된다. 그 p 자체가 플래그이며, ord 값을 이어 붙인 형태라 사람이 읽을 수도 있다.
#dreamhack#ctf#crypto+3
2026-07-14#dreamhack +4