문제: DreamHack — Affe!n 분류: Crypto 난이도: 🥉 Bronze 4 FLAG:
DH{3fcd60d46ff03b6fcd3a6d4c71805b131f8f48af5ffdf4fb4b9ab7cf5a09a4ef}
"아핀 암호? 꽤 괜찮은데 :>"라며 비밀 문장을 가려 놓은 문제다. 하지만 아핀 암호의 키는 상수 두 개뿐이고, 이 문제는 그 둘의 범위마저 좁다. 열쇠 꾸러미가 6만 개면 그냥 다 넣어 보면 된다.

문제 개요
| 항목 | 내용 |
|---|---|
| 문제명 | 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 251key1⁻¹은 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"))
key1=79, key2=87에서 복호가 맞아떨어진다. 나온 문장은 아핀 암호를 설명하는 지문이고, 그 끝에 플래그가 붙어 있다.
... Now, here comes the flag- DH{3fcd60d46ff03b6fcd3a6d4c71805b131f8f48af5ffdf4fb4b9ab7cf5a09a4ef}FLAG: DH{3fcd60d46ff03b6fcd3a6d4c71805b131f8f48af5ffdf4fb4b9ab7cf5a09a4ef}
📝 결론
키 공간이 작으면 암호가 아니다.
아핀 암호 자체는 멀쩡한 치환이지만, 키가 두 상수뿐이라 전체가 6만 가지밖에 안 된다. 아무리 잘 섞어도 경우의 수가 이 정도면 그냥 다 시도하는 게 답이다.
알려진 평문 한 조각이 전수조사를 끝낸다.
cryptography라는 단어 하나가 "어느 복호가 맞는지" 판별해 준다. 전수조사는 후보를 만드는 것보다 정답을 알아보는 게 관건인데, 평문의 일부를 알면 그 판별이 공짜로 해결된다.
Comments
댓글
댓글을 남기려면 로그인이 필요해요. (네이버 · 구글 계정)
댓글 불러오는 중…