Affine Cipher Known Plaintext Attack

0. 3분 요약

Affine Cipher에서 모든 바이트가 같은 식으로 암호화된다면 key를 전부 브루트포스하지 않아도 됩니다.

c = key1 * p + key2 mod 251

평문에 들어간 문자열 일부를 알고 있다면, 서로 다른 두 바이트만으로 key1, key2를 계산할 수 있습니다.

문제 코드에는 다음 힌트가 있었습니다.

assert b'cryptography' in secret

따라서 암호문에서 cryptography가 들어갈 수 있는 위치만 훑고, 해당 위치의 앞 두 글자로 key를 계산하면 됩니다.

---

1. 문제 정보

• 문제: Dreamhack Affe!n
• 분야: crypto
• 난이도: Level 1
• 핵심 키워드: Byte-Affine cipher, Known Plaintext Attack

Dreamhack 설명은 “카이사르의 시대는 갔습니다. 이제는 Byte-Affine cipher의 시대입니다.”라고 되어 있습니다.

이 문제는 byte 단위 Affine Cipher를 사용하고, 평문에 들어 있는 단어 하나를 힌트로 key를 복원하는 실습 문제입니다.

---

2. 고등학생도 이해할 수 있는 원리

이 암호는 글자 하나하나를 아래 공식으로 바꿉니다.

암호문 = key1 * 평문 + key2 를 251로 나눈 나머지

코드로 보면 다음과 같습니다.

c = (key1 * p + key2) % 251

여기서 우리가 모르는 값은 key1, key2 두 개입니다.

그런데 문제 코드에는 이런 힌트가 있습니다.

assert b'cryptography' in secret

즉 원래 문장 안에 "cryptography"라는 단어가 반드시 들어 있습니다.

예를 들어 암호문 어딘가에 "cryptography"가 암호화된 결과가 있다고 생각해봅시다. 평문 첫 글자 'c', 두 번째 글자 'r'을 숫자로 보면 다음과 같습니다.

'c' = 99
'r' = 114

암호문에서 그 위치의 두 바이트가 각각 c0, c1이라고 하면 식이 두 개 생깁니다.

c0 = key1 * 99  + key2 mod 251
c1 = key1 * 114 + key2 mod 251

이제 두 식을 빼면 key2가 사라집니다.

c0 - c1 = key1 * (99 - 114) mod 251

남은 미지수는 key1 하나뿐입니다. 그래서 key1을 먼저 구하고, 원래 식에 다시 넣어서 key2도 구할 수 있습니다.

key1 = ((c0 - c1) * pow(99 - 114, -1, 251)) % 251
key2 = (c0 - key1 * 99) % 251

정리하면 다음 순서입니다.

1. 평문 안에 cryptography가 있다는 것을 안다.
2. 암호문에서 cryptography가 들어갈 수 있는 위치를 하나씩 맞춰본다.
3. 그 위치의 앞 두 글자로 key1을 계산한다.
4. key1로 key2도 계산한다.
5. 계산한 key로 cryptography 전체가 제대로 암호화되는지 확인한다.
6. 맞으면 그 key가 정답이다.

그래서 전체 key를 전부 때려 맞히는 brute force가 아니라, 알려진 단어 하나를 이용해서 방정식처럼 key를 푼 것입니다.

이런 방식을 Known Plaintext Attack, 즉 “알려진 평문 공격”이라고 부릅니다.

---

3. 문제 코드 핵심

key1, key2 = random.randint(1, 250), random.randint(1, 250)
 
def encrypt(self, msg):
    msg_enc = b""
    for b in msg:
        msg_enc = msg_enc + bytes([(self._key1 * b + self._key2) % 251])
    return msg_enc

각 byte p는 다음과 같이 암호문 byte c로 변환됩니다.

$$c\equiv key1\cdot p+key2(\mathrm{mod}251)$$

251은 소수이기 때문에, 0이 아닌 값은 모두 역원을 가집니다.

---

4. 브루트포스가 필요 없는 이유

평문과 암호문의 한 쌍을 알고 있으면 식은 다음처럼 됩니다.

$$c_0\equiv key1\cdot p_0+key2(\mathrm{mod}251)$$

하지만 unknown이 key1, key2 두 개라서 한 쌍만으로는 부족합니다.

서로 다른 평문 byte 두 개를 알면 됩니다.

$$c_0\equiv key1\cdot p_0+key2(\mathrm{mod}251)$$ $$c_1\equiv key1\cdot p_1+key2(\mathrm{mod}251)$$

두 식을 빼면 key2가 사라집니다.

$$c_0-c_1\equiv key1(p_0-p_1)(\mathrm{mod}251)$$

따라서 key1은 다음처럼 구할 수 있습니다.

$$key1\equiv (c_0-c_1)(p_0-p_1{)}^{-1}(\mathrm{mod}251)$$

그리고 key2는 다시 원래 식에 대입하면 됩니다.

$$key2\equiv c_0-key1\cdot p_0(\mathrm{mod}251)$$

---

5. 풀이 코드

from pathlib import Path
 
ct = bytes.fromhex(Path("output.txt").read_text().split("> ")[1].strip())
known = b"cryptography"
 
for off in range(len(ct) - len(known) + 1):
    p0, p1 = known[0], known[1]
    c0, c1 = ct[off], ct[off + 1]
 
    key1 = ((c0 - c1) * pow(p0 - p1, -1, 251)) % 251
    key2 = (c0 - key1 * p0) % 251
 
    if all((key1 * p + key2) % 251 == c for p, c in zip(known, ct[off:off + len(known)])):
        print("offset:", off)
        print("key1:", key1)
        print("key2:", key2)
 
        pt = bytes(pow(key1, -1, 251) * (c - key2) % 251 for c in ct)
        print(pt)
        break

---

6. 실행 결과

해당 문제의 output.txt 기준 결과는 다음과 같습니다.

offset: 74
key1: 79
key2: 87

즉 전체 key 공간을 도는 대신, cryptography가 시작될 수 있는 위치만 확인하면 됩니다.

---

7. 실습: Dreamhack Affe!n 풀이

실습 목표

Dreamhack Affe!n 문제에서 제공된 prob.py와 output.txt만 가지고 random으로 생성된 key1, key2를 구하고, 암호문을 복호화합니다.

이 문제에서 중요한 파일은 두 개입니다.

• prob.py: 암호화 로직이 들어 있는 문제 코드
• output.txt: 암호화된 문장이 들어 있는 출력 파일

---

1단계: 암호화 식 확인

prob.py의 핵심은 이 부분입니다.

bytes([(self._key1 * b + self._key2) % 251])

즉 byte 하나가 다음 식으로 암호화됩니다.

c = key1 * p + key2 mod 251

여기서 p는 평문 byte, c는 암호문 byte입니다.

---

2단계: 알려진 평문 찾기

문제 코드에는 다음 줄이 있습니다.

assert b'cryptography' in secret

따라서 원래 문장 안에는 cryptography라는 단어가 반드시 들어 있습니다.

이제 암호문 안에서 cryptography가 들어갈 수 있는 위치를 하나씩 가정하면 됩니다.

---

3단계: key 계산하기

cryptography의 첫 두 글자는 c, r입니다.

'c' = 99
'r' = 114

어떤 위치에서 암호문 byte 두 개가 c0, c1이라면 다음 식이 생깁니다.

c0 = key1 * 99  + key2 mod 251
c1 = key1 * 114 + key2 mod 251

두 식을 빼면 key2가 사라집니다.

c0 - c1 = key1 * (99 - 114) mod 251

그래서 key1을 먼저 구할 수 있습니다.

key1 = ((c0 - c1) * pow(99 - 114, -1, 251)) % 251

그 다음 key2는 원래 식에 대입합니다.

key2 = (c0 - key1 * 99) % 251

---

4단계: exploit.py 작성

from pathlib import Path
 
 
MOD = 251
KNOWN = b"cryptography"
 
 
def main():
    ct = bytes.fromhex(Path("output.txt").read_text().split("> ", 1)[1].strip())
 
    for off in range(len(ct) - len(KNOWN) + 1):
        p0, p1 = KNOWN[0], KNOWN[1]
        c0, c1 = ct[off], ct[off + 1]
 
        key1 = ((c0 - c1) * pow(p0 - p1, -1, MOD)) % MOD
        key2 = (c0 - key1 * p0) % MOD
 
        chunk = ct[off : off + len(KNOWN)]
        if all((key1 * p + key2) % MOD == c for p, c in zip(KNOWN, chunk)):
            pt = bytes(pow(key1, -1, MOD) * (c - key2) % MOD for c in ct)
            print(f"offset = {off}")
            print(f"key1 = {key1}")
            print(f"key2 = {key2}")
            print(pt.decode())
            return
 
    raise SystemExit("known plaintext not found")
 
 
if __name__ == "__main__":
    main()

---

5단계: 실행 결과 확인

python3 exploit.py

결과는 다음과 같습니다.

offset = 74
key1 = 79
key2 = 87

복호화된 문장 마지막에는 flag가 나옵니다.

DH{3fcd60d46ff03b6fcd3a6d4c71805b131f8f48af5ffdf4fb4b9ab7cf5a09a4ef}

---

실습에서 배운 점

random으로 key를 만들었다고 해서 항상 안전한 것은 아닙니다.

이 문제는 다음 조건 때문에 key를 쉽게 구할 수 있었습니다.

• 같은 key가 모든 byte에 반복 사용된다.
• 암호화 식이 선형이다.
• 평문 일부인 cryptography를 알고 있다.

즉 암호에서 randomness보다 중요한 것은 구조입니다. 구조가 단순하고 힌트가 있으면, key가 random이어도 수식으로 복원될 수 있습니다.

---

8. 핵심 정리

Affine Cipher는 선형식입니다.

$$c=ap+b$$

그래서 평문과 암호문 일부가 대응되는 순간 key가 수식으로 복원됩니다.

이 공격은 Known Plaintext Attack입니다.

• 평문 일부를 알고 있다.
• 같은 key가 모든 위치에 반복 사용된다.
• 암호화 식이 선형이다.

이 조건이 만족되면 random key라도 안전하지 않습니다.