Step 179. CTF 맛보기 4: Crypto 입문 3개 — 수학 퍼즐로서의 암호

Level 3 — CTF 실전과 공격 스킬 심화 | 난이도 ★★★☆☆ | 예상 소요 시간 5시간

전제: Step 90(인코딩과 XOR), Step 176~178(CTF 형식과 풀이 습관). 파이썬 기초 문법을 쓸 수 있습니다.

⚠️ 이 챕터의 실습은 내 랩·합법 플랫폼 전용입니다. 허가 없는 시스템에 적용하면 범죄입니다. 드림핵(dreamhack.io)은 풀라고 만들어진 합법 학습 플랫폼입니다.

준비물: 파이썬 3(실측: 3.12.14), 메모장. 외부 플랫폼 접속 없이 로컬에서 진행합니다.
주의: 플랫폼 문제 화면은 "화면 예시"로만 안내하고, 문제의 뼈대가 되는 세 개의 미니 문제는 직접 만들어 파이썬으로 풀이 실측합니다.

CTF의 Crypto(암호) 종목은 수학 퍼즐에 가깝습니다. 주어진 암호문과 힌트(키 일부, 파라미터, 소스 코드)에서 출제자의 실수나 약한 수치를 찾아 평문을 복구합니다. 침해 흔적을 찾는 다른 종목과 달리, 여기서 무기는 파이썬 한 줄과 "이 문자열 어딘가 이상한데?" 하는 눈입니다. 오늘은 입문 Crypto의 세 가지 고전 — 인코딩 탐지, XOR, 장난감 RSA — 을 직접 만들고 직접 부숩니다.

1. 학습 목표

이 챕터를 끝내면 다음을 할 수 있습니다:

인코딩(encoding)과 암호화(encryption)의 차이를 설명한다
문자열의 모양(끝의 =, 0-9a-f만 사용 등)으로 인코딩 종류를 추정한다
알려진 평문(플래그 형식 DH{)으로 한 바이트 XOR 키를 역산한다
작은 n의 RSA를 소인수분해해 개인키 d를 복구하고 pow(c, d, n)으로 복호화한다
"왜 뚫리는가"를 수식 없이 한 문장으로 정리한다

2. 배경 지식 — 오늘의 도구와 개념

오늘의 도구 한눈에 보기

구분	내용
언어·환경	파이썬 3 (실측: 3.12.14) — 대화형 셸 또는 스크립트
오늘의 명령어	`bytes.fromhex()`, `base64.b64decode()`, `codecs.decode(s, "rot13")`, `pow(c, d, n)`
필요한 개념	인코딩 vs 암호화, Base64/hex/rot13의 모양 단서, XOR의 자기 역변환, RSA의 공개키·개인키
오늘의 산출물	미니 문제 3개의 풀이 + 각 문제의 "왜 뚫리는가" 한 줄

2-1. 인코딩은 암호가 아니다

인코딩은 "표기법 바꾸기"입니다. 키가 없고, 규칙을 아는 사람은 누구나 되돌릴 수 있습니다. Base64, hex, rot13이 모두 여기 속합니다. 암호화는 키 없이는 못 여는 것입니다.

CTF 입문 문제의 절반은 인코딩입니다. 암호처럼 보이지만 사실 겉모습만 바뀐 문자열 — 그래서 첫 질문은 언제나 "이건 암호인가, 인코딩인가"입니다.

2-2. 문자열의 모양이 말해 주는 것

단서	추정
끝에 `=` 또는 `==`	Base64 (패딩 문자)
0-9와 a-f만 등장, 짝수 길이	hex (16진수 표기)
단어 모양인데 철자가 이상	rot13 또는 시저(알파벳 밀기)
알 수 없는 바이트 덩어리	XOR 또는 진짜 암호

완벽한 규칙은 아니지만, 입문 문제에서는 이 표만으로 첫 시도가 정해집니다. 틀리면 다음 후보로 넘어가면 됩니다 — 추정과 검증의 반복이 Crypto 풀이의 일상입니다.

2-3. XOR — 한 번 더 하면 원래대로

XOR(배타적 논리합)은 같은 키로 두 번 하면 원래 값이 됩니다. 평문 XOR 키 = 암호문, 암호문 XOR 키 = 평문. 그래서 평문의 일부를 알면 키를 역산할 수 있습니다:

암호문[0] XOR 평문[0] = 키

CTF 플래그는 DH{처럼 정해진 머리말로 시작하니, 암호문 첫 바이트와 D를 XOR하면 키가 나옵니다. 이것이 알려진 평문 공격(known-plaintext attack)의 가장 작은 형태입니다.

2-4. RSA 한 바퀴 — 자전거로 배우는 비행기 원리

RSA는 두 소수 p, q의 곱 n을 공개하고, n을 다시 쪼개지 못하면 비밀키 d를 모른다는 아이디어의 공개키 암호입니다. 흐름은 이렇습니다:

n = p × q,  공개키 (n, e),  개인키 d = e의 역수 (mod (p-1)(q-1))
암호화: c = m^e mod n     복호화: m = c^d mod n

실전의 n은 수백 자릿수라 못 쪼갭니다. 그런데 문제의 n이 작으면 — 직접 나눠 보면 쪼개집니다. 파이썬의 pow(c, d, n)이 복호화 전부라는 것을 오늘 실측합니다. 실전에서는 factordb.com에 n을 검색해 이미 쪼개진 수인지 확인하는 것이 표준 수법입니다(화면 예시로만 봅니다).

3. 따라 하기

3-1. 실험실 준비 — 문제 생성기

드림핵 Crypto 난이도 1 문제의 뼈대를 그대로 옮긴 미니 문제 세 개를 만듭니다. 아래 스크립트를 crypto_lab.py로 저장하고 실행하세요 (이 챕터의 모든 출력은 2026-09-09 파이썬 3.12.14 실측입니다).

입력 (crypto_lab.py — 문제 생성 부분)

import base64

# 문제 1: hex 안에 Base64
flag1 = "DH{hex_4nd_b4se64_l4y3rs}"
b64 = base64.b64encode(flag1.encode()).decode()
hexed = b64.encode().hex()
print("문제 1 암호문:", hexed)

# 문제 2: 한 바이트 XOR
flag2 = "DH{x0r_k3y_1s_0n3_byt3}"
key = 0x5A
cipher = bytes(b ^ key for b in flag2.encode())
print("문제 2 암호문(hex):", cipher.hex())

# 문제 3: 장난감 RSA
p, q, e = 61, 53, 17
n = p * q
d = pow(e, -1, (p - 1) * (q - 1))
c = pow(ord("A"), e, n)
print(f"문제 3: n={n}, e={e}, c={c}")

출력

문제 1 암호문: 5245683761475634587a52755a4639694e484e6c4e6a5266624452354d334a7a66513d3d
문제 2 암호문(hex): 1e1221226a2805316923056b29056a34690538232e6927
문제 3: n=3233, e=17, c=2790

지금부터 여러분은 이 세 암호문만 받은 풀이자입니다. 출제자의 마음(위 코드)은 잊고, 암호문의 모양만 보고 풀어 봅시다.

3-2. 문제 1: 인코딩 탐지 — hex인가, Base64인가

암호문을 봅니다: 5245683761475634...66513d3d. 0-9와 a-f로만 이뤄졌고 길이도 짝수 — 2-2 표의 둘째 줄, hex가 첫 후보입니다.

s = "5245683761475634587a52755a4639694e484e6c4e6a5266624452354d334a7a66513d3d"
step1 = bytes.fromhex(s).decode()
print(step1)

REh7aGV4XzRuZF9iNHNlNjRfbDR5M3JzfQ==

출력 읽는 법: hex를 풀었더니 플래그가 아니라 또 다른 문자열이 나왔습니다. 그런데 끝이 == — 표의 첫째 줄, Base64입니다. 인코딩이 두 겹이었습니다.

import base64
print(base64.b64decode(step1).decode())

DH{hex_4nd_b4se64_l4y3rs}

왜 뚫리는가 한 줄: "인코딩은 키가 없는 변환이라, 몇 겹이든 규칙만 알면 전부 되돌아온다."

3-3. 문제 2: 한 바이트 XOR — 플래그 머리말로 키 역산

두 번째 암호문 1e1221226a28...을 hex로 풀어 봐도 글자가 안 됩니다 — bytes.fromhex 결과가 깨진 바이트입니다. 이번엔 진짜 변환이 있습니다: XOR입니다. 키를 모르지만, 플래그가 DH{로 시작한다는 것은 압니다.

cipher = bytes.fromhex("1e1221226a2805316923056b29056a34690538232e6927")
key = cipher[0] ^ ord("D")   # 암호문[0] XOR 평문[0] = 키
print(hex(key))
print(bytes(c ^ key for c in cipher).decode())

0x5a
DH{x0r_k3y_1s_0n3_byt3}

출력 읽는 법: 첫 바이트 0x1e와 D(0x44)를 XOR하니 0x5a가 나왔고, 그 키 하나로 전체가 풀렸습니다. 확인 차 둘째 바이트도 검산해 보세요 — 0x12 ^ ord("H")도 0x5a여야 합니다.

왜 뚫리는가 한 줄: "XOR은 같은 키로 두 번 하면 풀리고, 평문 한 글자를 알면 키가 역산된다 — 머리말이 정해진 플래그에겐 치명적이다."

예측: 키가 한 바이트가 아니라 0x5A 0x3C 두 바이트를 번갈아 썼다면? 첫 글자로는 키의 절반밖에 못 구합니다. 이때 단서는 "같은 바이트 패턴이 규칙적으로 반복"되는 것입니다 — 키 길이 추정은 Crypto의 다음 단계 과제입니다.

3-4. 문제 3: 장난감 RSA — n이 작으면 끝

세 번째 문제는 파라미터를 통째로 줍니다: n=3233, e=17, c=2790. RSA의 공개키와 암호문입니다. 여기서 "이상한 점"을 찾으세요 — n이 너무 작습니다. 네 자릿수면 손으로도 쪼갤 수 있습니다.

n, e, c = 3233, 17, 2790

# n 소인수분해 — 작으니 전부 나눠 보기
for i in range(2, n):
    if n % i == 0:
        p = i
        break
q = n // p
print(f"{n} = {p} x {q}")

# 개인키 d 복구 후 복호화
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)     # e의 모듈러 역수
m = pow(c, d, n)        # 복호화 = 이 한 줄
print(f"d = {d}, m = {m} → '{chr(m)}'")

3233 = 53 x 61
d = 2753, m = 65 → 'A'

(2026-09-09 실측. 53과 61은 순서가 바뀌어 나올 수 있지만 곱은 같습니다.)

출력 읽는 법: n을 쪼개는 순간 (p-1)(q-1)을 계산할 수 있고, e의 역수 d를 구해 pow(c, d, n)으로 복호화했습니다. 평문은 한 글자 A(65)였습니다. 실전 문제는 n이 조금 더 크지만 원리는 같고, 그때 쓰는 치트키가 factordb.com — 이미 누군가 쪼개 둔 n이면 즉답입니다 (화면 예시):

# 화면 예시 — factordb.com에 3233을 검색한 결과 형태
3233 = 53 * 61   (FF, fully factored)

왜 뚫리는가 한 줄: "RSA의 안전성은 ‘n을 못 쪼갠다’에 서 있다 — n이 작거나 이미 쪼개진 수면 개인키는 공짜로 복구된다."

3-5. 실제 플랫폼에서의 모습 — 화면 예시

로컬에서 익힌 흐름을 드림핵 Crypto 카테고리에 적용하면 이런 모습입니다 (화면 예시 — 이 환경에서는 접속하지 않았습니다):

# 화면 예시 — 플랫폼 문제 페이지의 전형적 구성
[Crypto] baby-rsa        난이도: 1
첨부: chal.py, output.txt   ← 소스와 파라미터를 준다
플래그 제출: DH{ ... }

플랫폼 문제도 결국 오늘의 세 유형의 확장입니다. 소스를 읽고 → "이상한 점"(작은 n, 재사용된 키, 인코딩만 한 것)을 찾고 → 파이썬으로 풉니다. 새로 배우는 것이 아니라, 오늘의 눈을 그대로 가져가는 것입니다.

4. 미션과 연습문제

미션 — 나만의 Crypto 문제 만들고 풀기

오늘의 세 유형을 하나씩 변형해, "출제자 → 풀이자"를 모두 경험하세요:

인코딩 문제: 여러분만의 플래그(DH{...} 형식)를 Base64로, 그 결과를 다시 hex로 두 겹 인코딩한 문제를 만든다
XOR 문제: 다른 키 바이트(예: 0x42)로 암호화한 문제를 만들고, 암호문만 보고 DH{ 머리말로 키를 역산해 푼다
RSA 문제: p, q를 다른 소수(각각 100 미만)로 골라 n, e, c를 만들고, n만 보고 쪼개서 복호화한다
각 문제에 "왜 뚫리는가" 한 줄을 붙여 노트에 정리한다

연습문제

문제 1. 문자열 aGVsbG8=를 보세요. 어떤 인코딩으로 추정되며, 근거는 무엇인가요? 디코딩 결과는?

문제 2. XOR 암호문의 첫 바이트가 0x37이고 평문 첫 글자가 D(0x44)입니다. 키는? 그리고 그 키로 0x37 0x2d 0x22를 복호화하세요.

문제 3. n = 143, e = 7, c = 48인 장난감 RSA입니다. n을 소인수분해하고 d를 구해 복호화해 보세요.

문제 4. rot13은 "알파벳을 13칸 미는" 인코딩입니다. uryyb frphevgl를 풀어 보세요. 그런데 왜 rot13은 두 번 적용하면 원래 문자열로 돌아오나요?

5. 모범 답안과 완료 기준

미션 모범 답안

변형 문제의 예 (2026-09-09 실측 — XOR 키를 0x42로 바꾼 경우):

flag = "DH{m1ss10n_cl34r}"
key = 0x42
cipher = bytes(b ^ key for b in flag.encode())
print(cipher.hex())
# 풀이: cipher[0] ^ ord('D') = 0x42 → 전체 복호화 성공

RSA 변형은 p=67, q=71 같은 새 소수를 고르면 됩니다. 단, 두 소수 모두 100 미만으로 골라야 손쉬운 전체 나눗셈으로 쪼개집니다. 그리고 평문 m은 n보다 작은 수(한 글자)로 유지하세요 — m이 n을 넘으면 나머지 연산에서 정보가 잘립니다.

검증하는 법: ① 세 문제 모두 "암호문(파라미터)만 보고" 풀었는가 — 생성 코드를 보지 않고. ② XOR 문제의 키 역산이 첫 글자뿐 아니라 둘째 글자 검산도 통과했는가. ③ "왜 뚫리는가"가 기법 이름이 아니라 구멍의 내용(키 없음, 키 역산 가능, n이 작음)을 말하는가.

연습문제 해답

문제 1 해답. Base64로 추정됩니다. 끝의 =(패딩)이 단서입니다. base64.b64decode("aGVsbG8=") → hello. Base64는 알파벳·숫자·+//만 쓰고 4자 단위로 끊기는 모양도 힌트입니다.

문제 2 해답. 키는 0x37 ^ 0x44 = 0x73입니다. 복호화: 0x37^0x73=0x44(D), 0x2d^0x73=0x5e(^), 0x22^0x73=0x51(Q) → D^Q. 평문이 플래그가 아닌 경우에도 역산 절차는 같습니다.

문제 3 해답. 143 = 11 × 13. phi = 10 × 12 = 120, d = pow(7, -1, 120) = 103. 복호화: pow(48, 103, 143) = 80 → 문자 P. (파이썬으로 직접 확인해 보세요.)

문제 4 해답. codecs.decode("uryyb frphevgl", "rot13") → hello security. 알파벳은 26글자라 13칸을 두 번 밀면 26칸, 즉 제자리입니다. rot13이 "자기 자신이 역함수"라 암호화와 복호화가 같은 동작인 이유입니다.

완료 기준 체크리스트

[ ] 인코딩과 암호화의 차이(키의 유무)를 설명할 수 있다
[ ] = 패딩, hex 문자 집합 등 모양 단서로 인코딩을 추정한다
[ ] hex + Base64 두 겹 문제를 bytes.fromhex와 base64.b64decode로 풀었다
[ ] DH{ 머리말로 XOR 키를 역산해 복호화했다
[ ] 작은 n의 RSA를 소인수분해하고 pow(c, d, n)으로 복호화했다
[ ] 세 문제의 "왜 뚫리는가"를 한 줄씩 정리했다
[ ] 미션: 세 유형을 변형한 나만의 문제를 만들어 풀었다

6. 흔한 실수와 해결

벽 1. bytes.fromhex()가 ValueError를 뱉는다

증상: ValueError: non-hexadecimal number found in fromhex() arg at position 4 (2026-09-09 실측).
원인: 문자열에 0-9a-f가 아닌 문자(공백, 0x 접두사, 오탈자)가 섞여 있습니다. 위치(position)가 범인을 알려 줍니다.
해결: 공백을 제거(s.replace(" ", ""))하고, 0x 접두사를 떼고, 길이가 짝수인지 확인하세요. 그래도 안 되면 그 문자열은 hex가 아닙니다 — 2-2 표의 다음 후보로 넘어가세요.

벽 2. Base64 디코딩이 Incorrect padding을 뱉는다

증상: binascii.Error: Incorrect padding (2026-09-09 실측).
원인: Base64 문자열 길이는 4의 배수여야 하는데, 복사 과정에서 끝의 =이 잘렸습니다.
해결: 원문을 다시 복사해 =을 살리세요. 급하면 부족한 만큼 =을 붙여 보세요 — s + "=" * (-len(s) % 4).

벽 3. pow(e, -1, phi)가 ValueError: base is not invertible을 뱉는다

증상: ValueError: base is not invertible for the given modulus (2026-09-09 실측).
원인: e와 phi가 서로소가 아닙니다. 역수는 서로소일 때만 존재합니다. 미션에서 e를 임의로 고르다가 걸립니다.
해결: e를 소수(3, 5, 7, 17 등)로 고르고, phi가 그 배수가 아닌지 확인하세요. 실전 RSA가 e=65537 같은 소수를 쓰는 이유이기도 합니다.

벽 4. XOR 복호화 결과가 일부만 깨진다

증상: 앞부분은 읽히는데 뒤가 깨집니다.
원인: 키가 한 바이트가 아니라 여러 바이트(키 길이 > 1)인 문제입니다. 첫 글자로 구한 키는 키의 일부일 뿐입니다.
해결: 알려진 평문이 DH{ 세 글자라면 세 바이트까지 역산할 수 있습니다. 그래도 모자라면 키의 반복 주기를 추정하는 단계 — 입문 범위를 넘으니, 오늘은 "한 바이트 키인 문제"만 다룬다는 것을 확인하세요.

벽 5. 파이썬에서 ^를 거듭제곱으로 쓴다

증상: 2 ^ 3이 8이 아니라 1이 나옵니다.
원인: 파이썬에서 ^는 XOR이고, 거듭제곱은 ** 또는 pow()입니다.
해결: XOR이 필요할 때만 ^. RSA 계산은 pow(m, e, n) — 세 개짜리 pow가 모듈러 거듭제곱입니다.

7. 정리

오늘의 개념

개념	한 줄 설명
인코딩	키 없는 표기 변환 — Base64, hex, rot13. 규칙만 알면 누구나 역변환
알려진 평문 공격	평문 일부(플래그 머리말)로 키를 역산하는 기법
XOR의 자기 역변환	같은 키로 두 번 XOR하면 원래 값 — 그래서 키 역산이 가능
RSA	n=p×q를 못 쪼개면 안전한 공개키 암호 — 쪼개지면 끝
모듈러 역수	`pow(e, -1, phi)` — 개인키 d를 구하는 파이썬 한 줄
모양 단서	`=`은 Base64, 0-9a-f는 hex — 문자열의 겉모습이 첫 가설

오늘의 명령어

명령	하는 일
`bytes.fromhex(s)`	16진수 문자열 → 바이트
`base64.b64decode(s)`	Base64 디코딩
`codecs.decode(s, "rot13")`	rot13 풀기
`bytes(b ^ key for b in cipher)`	한 바이트 XOR 복호화
`pow(e, -1, phi)`	모듈러 역수(개인키 d) 계산
`pow(c, d, n)`	RSA 복호화

명령어보다 중요한 감각

Crypto 문제의 출발점은 계산이 아니라 관찰입니다. "이 문자열의 모양은 무엇을 말하는가", "이 파라미터 중 이상한 것은 무엇인가." 오늘의 세 문제는 모두 출제자의 타협 — 인코딩으로 때우기, 한 바이트 키, 작은 n — 를 찾는 게임이었습니다.

실전 암호학은 오늘의 장난감과 결이 다릅니다. 하지만 "구현과 수치에서 약한 곳을 찾는 눈"은 그대로입니다. Step 181에서 주력 분야를 고를 때, 오늘 세 문제 중 "수학 퍼즐이 제일 재미있었다"고 느꼈다면 그것이 중요한 신호입니다.

전부 체크되면 Step 179 완료입니다. 사이드바의 체크박스를 눌러 진도를 저장하세요.