Step 237. CTF Crypto 기출 10문제 — 배운 무기를 실전에 투입하는 날

Level 3 — CTF 실전과 공격 스킬 심화 | 난이도 ★★★★☆ | 예상 소요 시간 8시간 이상(며칠에 나눠 진행)

전제: Step 227~236의 Crypto 트랙 전체 — 모듈러 연산, RSA 공격, 블록 모드, 해시 공격, DH/ECC.

⚠️ 이 챕터의 실습은 내 랩·합법 플랫폼 전용입니다. 허가 없는 시스템에 적용하면 범죄입니다. 드림핵·picoCTF 같은 CTF 아카이브는 운영자가 공식 개방한 합법 학습 플랫폼입니다.

준비물: CTF 아카이브 계정(드림핵 또는 picoCTF), 파이썬, 기록용 문서.
주의: 오늘부터 "문제를 보고 유형을 분류하는 눈"을 만듭니다. 풀이 수보다 분류 정확도가 목표입니다.

Crypto 문제 풀이의 절반은 계산이 아니라 분류입니다. output.txt만 덩그러니 주어진 문제에서 "이건 작은 e 문제다"라고 감잡는 순간 풀이의 80%가 끝납니다. 오늘은 기출 10문제를 선정해 분류 루틴을 적용하고, 그 전에 먼저 — 이 챕터에서 직접 만든 미니 문제 3개를 실측 풀이해 "분류 → 공격"의 감각을 예열합니다.

1. 학습 목표

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

주어진 수치(파라미터 크기·형태)를 보고 Crypto 문제의 유형 후보를 2개로 좁힌다
RSA 문제에 표준 체크리스트(factordb → 작은 e → 페륾마 → Wiener → 공통 n)를 순서대로 적용한다
단일 바이트 XOR, 작은 e RSA, 작은 n RSA를 공격 코드로 푼다
풀이마다 "분류 단서 → 사용 공격"을 한 줄로 기록해 자기만의 분류표를 만든다
모르는 유형을 만났을 때 기법 문서까지만 리서치하는 경계를 지킨다

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

오늘의 도구 한눈에 보기

구분	내용
언어·환경	파이썬 3 (실측: 3.12.14), CTF 아카이브(드림핵/picoCTF), factordb.com
오늘의 절차	수치 관찰 → 유형 후보 2개 → 검증 실험 → 공격 코드 → 기록
필요한 개념	Crypto 문제 유형 지도, RSA 공격 체크리스트, XOR 계열, 분류 기록법
오늘의 산출물	10문제 풀이 기록 + 분류표 v1 (미니 문제 3개 실측 포함)

2-1. Crypto 문제 유형 지도

드림핵~picoCTF 수준에서 반복 출제되는 유형은 크게 여섯 갈래입니다.

유형	대표 단서	첫 공격
인코딩/XOR	짧은 16진수 문자열, "key는 1바이트"	256회 전수 XOR
RSA 파라미터	n, e, c 세 개만 주어짐	factordb에 n 조회
RSA 구조 공격	e가 3, 평문이 짧음 / e가 비정상적으로 큼	세제곱근 / Wiener
블록 모드	같은 평문 반복 시 같은 암호문	ECB 패턴 관찰
해시 오용	`H(secret + msg)` 형태 인증	길이 확장
DH/ECC 파라미터	p가 작음, 곡선이 비표준	전수 탐색 이산 대수

2-2. 분류 루틴 — 수치가 힌트 전부다

output.txt형 문제는 주어진 수치의 크기와 형태가 힌트의 전부입니다. 순서를 정해 둡니다:

1단계: 뭐가 주어졌나? (n, e, c? hex 문자열? p, g, A?)
2단계: 크기 관찰 — n이 짧다? e가 3이다? e가 n만큼 크다? p가 작다?
3단계: 유형 후보 2개를 적는다
4단계: 각 후보에 1분 검증 실험 (factordb 조회, 세제곱근 시도 등)

2-3. RSA 표준 체크리스트

RSA 문제를 만나면 이 순서로 소거합니다 (Step 229~230의 무기들):

factordb: n을 조회 — 이미 인수분해가 올라와 있는 n이 의외로 많습니다
작은 e: e = 3이고 평문이 짧으면 m^3이 n을 넘지 않거나 조금 넘는 정도 — 정수 세제곱근
페륾마 인수분해: p와 q가 가까우면(비슷한 비트 길이) n 근처에서 빠르게 분해
Wiener 공격: d가 작으면(n의 4제곱근 미만) 연분수로 d 복구
공통 모듈러스: 같은 n, 다른 e로 암호화된 같은 평문이 둘 — 확장 유클리드로 복구

2-4. 리서치의 경계

모르는 유형을 만나면 기법 문서까지는 허용입니다 — "RSA 작은 d 공격이 뭐지?"를 배우는 것은 도구 상자 채우기입니다. 금지는 그 문제의 풀이입니다. 경계는 Step 202와 같습니다: "일반 기법을 배우는가" 허용, "이 문제의 답을 얻는가" 금지.

3. 따라 하기

아래 미니 문제 3개는 이 챕터에서 직접 만든 것으로, 2026-09-09 파이썬 3.12.14로 실제 풀이를 실측했습니다. 기출 10문제 본편 앞의 예열입니다.

3-1. 미니 문제 1 — 단일 바이트 XOR

[문제] 암호문(hex): 242e2325393a72301d73311d27383f
       힌트: 평문은 flag{...} 형식, 키는 1바이트

분류: 16진수 문자열 + 1바이트 키 → 단일 바이트 XOR (유형표 1행). 풀이:

ct = bytes.fromhex("242e2325393a72301d73311d27383f")
for k in range(256):
    pt = bytes(c ^ k for c in ct)
    if pt.startswith(b"flag{"):
        print(f"키 k={k:#04x} -> {pt}")
        break

키 k=0x42 -> b'flag{x0r_1s_ez}'

읽는 법: 256회 전수 시도 + 정답 판별자(flag{ 접두사)가 XOR 유형의 정석 골격입니다. 판별자가 없으면 "출력이 출력 가능한 영문자인가"로 대체합니다.

3-2. 미니 문제 2 — 작은 e의 RSA

[문제] n = 1000036000099, e = 3, c = 95567816608
       힌트: 평문은 짧은 ASCII 2글자

분류: n, e, c 세 개 + e = 3 → 작은 e 공격 후보. factordb 생략 없이 먼저 e를 봅니다. m³을 계산해 보면:

n, e, c = 1000036000099, 3, 95567816608
m_true = int.from_bytes(b"hi", "big")
print(m_true**3, m_true**3 // n)   # 19096251818489, 약 19 — n보다 19배 커서 감겼다

19096251818489 19

감겨도 포기하지 않습니다 — m³ = c + k·n 꼴이므로 k를 올리며 정수 세제곱근을 시험합니다:

def iroot3(x):
    r = round(x ** (1/3))
    for cand in range(max(0, r-2), r+3):
        if cand**3 == x:
            return cand
for k in range(30):
    r = iroot3(c + k * n)
    if r is not None:
        print(f"k={k}: m={r} -> {r.to_bytes(2, 'big')}")
        break

k=19: m=26729 -> b'hi'

읽는 법: e = 3일 때 m^e < n이면 바로 세제곱근, 살짝 넘으면 k·n을 더해 가며 시험 — 실측에서 k = 19에서 복구됐습니다. "감겼다"가 곧 "후보가 유한 개"라는 뜻입니다.

3-3. 미니 문제 3 — n이 작은 RSA

[문제] n = 3233, e = 17, c = 2557

분류: n이 4자릿수 → 소인수분해 (실전에선 factordb 조회에 해당). 풀이:

def factor(n):
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return i, n // i
p, q = factor(3233)
phi = (p - 1) * (q - 1)
d = pow(17, -1, phi)
m = pow(2557, d, 3233)
print(f"n = {p} x {q}, phi = {phi}, d = {d}, m = {m}")

n = 53 x 61, phi = 3120, d = 2753, m = 42

읽는 법: Step 228의 RSA 복호화 절차 그대로입니다 — φ(n)을 구하고 d = e⁻¹ (mod φ), c^d mod n. n이 작다는 것 하나로 "공개키 암호"가 장난감이 됩니다. 실전에서는 이 n을 factordb에 넣는 것이 첫 행동입니다.

3-4. 본편 — 기출 10문제 선정과 기록

이제 아카이브로 갑니다. 선정 기준:

Crypto 카테고리에서 안 푼 문제 10개, 유형이 치우치지 않게 (인코딩 1, XOR 2, RSA 3, 블록 모드 1, 해시 1, DH/수학 2 정도)
각 문제에 2-2의 분류 루틴을 적용하고, 풀리기 전에 후보 2개를 먼저 기록합니다
풀이 후에는 반드시 한 줄 기록을 남깁니다

[출력 예시 — 분류 기록표]
문제        | 주어진 것        | 후보 2개          | 실제 유형   | 사용 공격
mini-xor   | hex 16바이트     | XOR / 치환        | 단일XOR     | 256 전수
small-e    | n,e=3,c          | 작은e / 소인수분해 | 작은e       | 세제곱근+k·n
dreamhack-A| n 256비트,e=65537| factordb / 페륾마 | factordb 히트| d 복구 후 복호화
...

완료 기준은 10개 중 7개 이상 + 분류표 v1입니다. 분류표의 "후보 2개"가 "실제 유형"과 얼마나 자주 겹치는지가 실력 지표입니다.

4. 미션과 연습문제

미션 — 기출 10문제와 분류표 v1

드림핵 또는 picoCTF에서 Crypto 문제 10개를 선정하고 선정 기록을 남깁니다
각 문제에 분류 루틴(수치 관찰 → 후보 2개 → 검증 실험)을 적용합니다
RSA 문제에는 2-3의 체크리스트를 순서대로 적용하고 어느 단계에서 풀렸는지 기록합니다
풀이마다 "분류 단서 → 사용 공격" 한 줄을 모아 분류표 v1을 완성합니다
7개 미만이면 남은 문제의 유형을 분류표에 "미해결 — 재훈련 주소"로 추가합니다

연습문제

문제 1. output.txt에 n(1024비트), e = 3, c만 있습니다. 첫 1분에 해야 할 일 두 가지를 순서대로 적어 보세요.

문제 2. 16진수 문자열 하나만 주어진 문제에서 "단일 바이트 XOR"과 "치환 암호"를 구분하는 실험을 설계해 보세요.

문제 3. e가 65537도 3도 아니고 이상하게 큽니다(n과 비슷한 자릿수). 어떤 공격 후보가 떠오르나요? 그 공격이 성립하는 조건도 함께.

문제 4. 분류표의 "후보 2개" 칸을 비워 두고 풀면 안 되는 이유를 측정 관점에서 설명해 보세요.

5. 모범 답안과 완료 기준

미션 모범 답안

완성된 분류표의 골격입니다 (미니 3개는 실측, 기출 부분은 형식 예시):

[분류표 v1]
문제     | 단서                  | 후보 2개           | 실제 유형  | 공격              | 결과
mini-xor | hex, flag{ 형식 힌트  | 단일XOR/치환       | 단일XOR    | 256 전수           | 풀이
small-e  | e=3, 짧은 평문        | 작은e/factordb     | 작은e      | 세제곱근(k=19)     | 풀이
small-n  | n이 4자리             | 소인수분해/…       | 작은n      | 시제 나눗셈→d 복구 | 풀이
기출1~10 | (각 문제 단서 기록)   |                    |            |                    |

검증하는 법: ① 10문제 선정 기록이 있는가. ② 각 행에 "후보 2개"가 풀이 전에 기록됐는가(사후 작성 흔적이 없는가). ③ RSA 문제마다 체크리스트의 어느 단계에서 멈췄는지 표시됐는가. ④ 7개 이상 풀이 + 미해결 행에 재훈련 주소가 있는가.

연습문제 해답

문제 1 해답. 첫째, factordb.com에 n을 조회합니다 — 이미 인수분해된 n이면 5초 만에 끝납니다. 둘째, 안 올라와 있으면 e = 3이므로 "m³ < n?" 검증 — c의 정수 세제곱근이 정확히 떨어지는지, 안 되면 c + k·n을 올려 가며 시험합니다. 이 순서가 2-3 체크리스트의 1·2단계입니다.

문제 2 해답. 빈도 분석이 답입니다. 단일 바이트 XOR은 알파벳의 출현 빈도 분포를 보존한 채 문자만 바꿉니다 — 가장 흔한 바이트가 공백이나 ‘e’에 대응하는지 보면 됩니다. 치환 암호도 빈도를 보존하므로 헷갈릴 수 있지만, XOR는 바이트 값 전체에 대한 연산이라 256회 전수 시도로 정답을 기계적으로 찾을 수 있습니다 — 전수 시도 중 "모두 출력 가능한 영문 + flag{ 접두사"가 나오면 XOR, 안 나오면 치환 계열로 후보를 바꿉니다.

문제 3 해답. Wiener 공격 후보입니다 — e가 크다는 것은 d가 작다는 뜻일 가능성이 높고(ed ≡ 1 (mod φ)에서 e가 크면 d가 작아질 수밖에 없는 구조), d < n^(1/4)/3 조건이면 연분수 전개로 d를 복구할 수 있습니다. e의 자릿수가 n에 가깝다는 단서는 이 유형의 간판입니다.

문제 4 해답. 사후에 후보를 적으면 "맞은 것만 기록"하는 오염이 생겨 분류표가 실력 지표로서 죽기 때문입니다. 풀이 전에 적힌 후보 2개와 실제 유형의 일치율이야말로 "수치를 보고 유형을 읽는 눈"의 측정값입니다. 틀린 후보도 기록입니다 — 틀린 패턴이 모이면 그것이 다음 훈련 목차입니다.

완료 기준 체크리스트

[ ] Crypto 유형 지도(6갈래)의 대표 단서를 말할 수 있다
[ ] 분류 루틴 4단계를 순서대로 적용한다
[ ] 미니 문제 3개를 공격 코드로 풀었다 (실측 출력 확인)
[ ] RSA 체크리스트 5단계를 순서대로 열거할 수 있다
[ ] 기출 10문제를 선정하고 분류 기록을 남겼다
[ ] 리서치 허용 범위(기법 문서 O / 문제 풀이 X)를 지켰다
[ ] 미션: 7개 이상 풀이 + 분류표 v1 완성

6. 흔한 실수와 해결

벽 1. output.txt를 보고 손이 얼어붙는다

증상: 숫자 나열만 있고 어디서 시작할지 모르겠습니다.
원인: 분류 루틴을 건너뛰고 바로 공격을 찾으려 했기 때문입니다.
해결: 1단계로 돌아가세요 — "뭐가 주어졌나"를 종이에 씁니다. n, e, c 세 개면 RSA이고, 그다음은 크기 관찰입니다. 수치의 자릿수가 힌트 전부입니다.

벽 2. 세제곱근이 안 떨어진다

증상: round(c ** (1/3))의 3제곱이 c와 다릅니다.
원인: 둘 중 하나 — m³이 n을 넘어 감겼거나, 부동소수점 오차.
해결: 감긴 경우 k·n을 더해 가며 시험(3-2 실측에서 k = 19). 부동소수점은 큰 수에서 정밀도가 무너지니, 실전에서는 정수 전용 근사 루트(이진 탐색 또는 sympy integer_nthroot)를 쓰세요.

벽 3. factordb에 없는 n에서 멈춘다

증상: 조회 실패 후 다음 수를 모릅니다.
원인: 체크리스트 1단계만 기억한 것.
해결: 2~5단계를 순서대로 — e 크기 확인(작은 e/Wiener), p·q 근접 확인(페륾마), 같은 n의 다른 암호문 확인(공통 모듈러스). 어느 것도 아니면 문제의 다른 재료(서비스 접속, 힌트 문구)를 다시 봅니다.

벽 4. 풀이 검색의 유혹

증상: 30분 막히면 문제 번호를 검색하고 싶어집니다.
원인: 목표를 "풀이 수"로 잡았기 때문입니다. 오늘의 목표는 분류 눈입니다.
해결: 검색 욕구가 생긴 시각을 기록에 적고, 대신 기법 문서(예: "RSA attacks list")를 찾으세요. 문제 풀이가 아니라 무기 목록을 보는 것은 허용됩니다.

벽 5. 분류표가 "풀었다/못 풀었다"만 된다

증상: 기록이 결과뿐이라 나중에 복습 재료가 안 됩니다.
원인: 후보와 단서를 풀기 전에 안 적은 것.
해결: 행 하나를 열 때 "단서"와 "후보 2개" 칸부터 채우는 순서를 강제하세요. 못 푼 문제일수록 단서 기록이 값어치 있습니다.

7. 정리

오늘의 개념

개념	한 줄 설명
분류 루틴	수치 관찰 → 후보 2개 → 검증 실험 → 공격
유형 지도	인코딩/XOR, RSA 파라미터, RSA 구조, 블록 모드, 해시, DH/ECC
RSA 체크리스트	factordb → 작은 e → 페륾마 → Wiener → 공통 n
판별자	전수 시도에서 정답을 알아보는 기준 (flag{ 접두사 등)
분류표	단서·후보·실제 유형·공격의 기록 — 실력 지표
리서치 경계	기법 문서 허용, 문제 풀이 금지

오늘의 명령어·코드

명령	하는 일
`bytes.fromhex(...)`	16진수 암호문을 바이트로
256회 XOR 전수 루프	단일 바이트 XOR 정석 풀이
`iroot3(c + k*n)` (직접 구현)	작은 e RSA — 감긴 세제곱 복구
`factor(n)` + `pow(e, -1, phi)`	작은 n RSA 소인수분해 풀이
factordb.com	n의 기인수분해 조회 (실전 1단계)

명령어보다 중요한 감각

Crypto 문제는 암호학 시험이 아니라 독해 시험에 가깝습니다 — 주어진 수치의 크기와 형태가 출제자의 메시지입니다. e가 3인 것, n이 짧은 것, e가 이상하게 큰 것, 전부 "여기로 오세요"라는 표지판입니다. 오늘부터 10문제를 지나며 이 표지판 읽기가 몸에 배면, Step 238의 독립 해결 점검은 분류 루틴의 검증일 뿐입니다.

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