Step 227. 수학 기초: 모듈러 연산, 유클리드 호제법, 오일러 정리 — 암호의 최소 무장
Level 3 — CTF 실전과 공격 스킬 심화 | 난이도 ★★☆☆☆ | 예상 소요 시간 3시간
전제: Step 90(인코딩과 XOR) 정도의 파이썬 기초. 수학 배경은 중학교 나눗셈이면 충분합니다 — 나머지는 오늘 만듭니다.
⚠️ 이 챕터의 실습은 내 랩·합법 플랫폼 전용입니다. 허가 없는 시스템에 적용하면 범죄입니다.
- 준비물: 파이썬 3(실측: 3.12.14), 종이와 펜(손계산용).
- 주의: 오늘 실습은 100% 안전합니다. 계산만 합니다.
Crypto 트랙의 첫날입니다. 현대 암호는 전부 "mod n 세계의 산수"로 돼 있습니다 — 나머지만 남기는 세계에서 곱하고, 거듭제곱하고, "나누기"를 합니다. 오늘 배울 세 가지 — 모듈러 연산, 유클리드 호제법, 오일러 정리 — 는 다음 챕터의 RSA를 이루는 부품 전부입니다. 어렵게 느껴지면 정상입니다. 대신 오늘 모든 수식을 손으로 한 번, 파이썬으로 한 번, 총 두 번씩 확인합니다.
1. 학습 목표
이 챕터를 끝내면 다음을 할 수 있습니다:
- 모듈러 연산을 "시계 산수"로 이해하고 파이썬
%와pow(a, b, n)으로 계산한다 - 유클리드 호제법으로 최대공약수를 손으로, 코드로 구한다
- 확장 유클리드 호제법으로
ax + by = gcd(a,b)의 x, y를 구한다 - 모듈러 역원이 "mod 세계의 나눗셈"임을 설명하고
pow(a, -1, n)과 내 구현을 대조한다 - 오일러 정리
a^φ(n) ≡ 1 (mod n)을 실험으로 체감한다
2. 배경 지식 — 오늘의 도구와 개념
오늘의 도구 한눈에 보기
| 구분 | 내용 |
|---|---|
| 언어·환경 | 파이썬 3 (실측: 3.12.14) — 표준 라이브러리만, 설치 없음 |
| 오늘의 명령어 | %, pow(a, b, n), pow(a, -1, n), 직접 짜는 gcd() / egcd() |
| 필요한 개념 | mod 연산, 최대공약수(gcd), 서로소, 모듈러 역원, 오일러 φ(n), 오일러 정리 |
| 오늘의 산출물 | 손계산 노트 + 역원 계산기(내 구현) + 오일러 정리 실험 출력 |
2-1. mod 연산 — 시계 산수
a mod n은 "a를 n으로 나눈 나머지"입니다. 시계가 좋은 예입니다 — 13시에 2시간을 더하면 15시가 아니라 3시. (13 + 2) mod 12 = 3입니다. mod 세계에서는 더하기, 빼기, 곱하기가 전부 "하고 나서 n으로 나눈 나머지"입니다.
왜 암호에서 쓰나요? 두 가지 성질 때문입니다. ① 결과가 0~n-1에 갇혀 수가 폭발하지 않습니다. ② 되돌리기가 어려운 연산을 만들 수 있습니다 — a^k mod n은 빠르게 계산되지만, 결과만 보고 k를 찾는 것(이산 로그)은 큰 수에서 사실상 불가능합니다.
2-2. 유클리드 호제법 — 최대공약수의 고속도로
최대공약수(gcd)는 두 수를 모두 나누는 가장 큰 수입니다. 유클리드 호제법은 이걸 나눗셈 반복만으로 구합니다:
gcd(a, b) = gcd(b, a mod b) — b가 0이 되면 a가 답
2,300년 된 알고리즘이 지금도 모든 RSA 키 생성 안에서 돌아갑니다. 빠르고(수가 줄어드는 속도가 지수적), 항상 끝나기 때문입니다.
2-3. 모듈러 역원 — mod 세계의 나눗셈
평범한 산수에서 "3으로 나누기"는 "1/3 곱하기"입니다. mod 세계에도 이것이 있습니다. 모듈러 역원(modular inverse)이란 a × x ≡ 1 (mod n)이 되는 x — 곱하면 1이 되는 짝입니다. 3의 역원 mod 11은 4입니다 (3 × 4 = 12 ≡ 1).
역원은 a와 n이 서로소(gcd가 1)일 때만 존재합니다. 그리고 구하는 도구가 확장 유클리드 호제법 — gcd를 구하면서 보너스로 ax + by = gcd(a, b)를 만족하는 x, y를 찾아줍니다. 서로소면 gcd=1이니 ax + ny = 1, 즉 ax ≡ 1 (mod n) — x가 곧 역원입니다. RSA의 비밀키 d가 바로 이 역원으로 만들어집니다.
2-4. 오일러 정리 — 거듭제곱의 순환
오일러 φ(n)(파이 함수)는 "1~n 중 n과 서로소인 수의 개수"입니다. 소수 p에서는 φ(p) = p – 1 (1~p-1 전부 서로소), 두 소수의 곱 n = pq에서는 φ(n) = (p-1)(q-1)입니다.
오일러 정리: a와 n이 서로소이면 a^φ(n) ≡ 1 (mod n). 거듭제곱이 φ(n)번 돌면 반드시 1로 돌아온다는 뜻입니다. 소수 p에 적용한 특수형 a^(p-1) ≡ 1 (mod p)이 페르마 소정리입니다. RSA의 복호화가 성립하는 이유가 바로 이 정리입니다 — 다음 챕터에서 정확히 씁니다.
3. 따라 하기
이 챕터의 모든 출력은 2026-09-09 파이썬 3.12.14 실측입니다.
3-1. 모듈러 연산 감 잡기
print(17 % 5) # 17을 5로 나눈 나머지
print((-7) % 5) # 파이썬은 음수의 나머지도 양수로 준다
print((13 + 9) % 12) # 시계 산수: 13시 + 9시간
print(pow(7, 3, 11)) # 7^3 mod 11 — 세 개짜리 pow
print(7**3, 343 % 11) # 검산: 먼저 거듭제곱해도 같다
2
3
10
2
343 2
출력 읽는 법: 세 가지를 확인했습니다. ① 나머지는 항상 0~n-1. ② 파이썬은 -7 % 5도 양수 3을 줍니다 (언어마다 다르니 파이썬 기준으로 통일합니다). ③ pow(7, 3, 11)은 7<strong>3 % 11과 같지만, 큰 수에서는 전자만 가능합니다 — 중간에 7³ = 343을 만들지 않고 나머지를 유지하며 계산하기 때문입니다. 수백 자릿수 거듭제곱은 7</strong>e로는 메모리가 못 버팁니다. 암호에서는 언제나 세 개짜리 pow입니다.
3-2. 유클리드 호제법 — 손으로 한 번, 코드로 한 번
먼저 손으로. gcd(1071, 462)를 구합니다:
1071 = 462 × 2 + 147
462 = 147 × 3 + 21
147 = 21 × 7 + 0 ← 나머지 0 → 답은 21
이제 코드로:
def gcd(a, b):
while b:
a, b = b, a % b
return a
print(gcd(1071, 462))
21
읽는 법: 손계산 세 번의 나눗셈이 while 세 바퀴와 정확히 대응합니다. a, b = b, a % b 한 줄이 "큰 수 자리에 작은 수, 작은 수 자리에 나머지"를 반복하는 전부입니다. 종이의 계산을 그대로 옮긴 것 — 수학이 코드로 변하는 순간을 눈으로 확인하세요.
3-3. 확장 유클리드 — 역원의 원천
이제 ax + by = gcd(a, b)의 x, y까지 구하는 버전입니다.
def egcd(a, b):
if b == 0:
return (a, 1, 0)
g, x1, y1 = egcd(b, a % b)
return (g, y1, x1 - (a // b) * y1)
g, x, y = egcd(1071, 462)
print(f"g={g}, x={x}, y={y}")
print("검산:", 1071 * x + 462 * y)
g=21, x=-3, y=7
검산: 21
출력 읽는 법: 1071 × (-3) + 462 × 7 = 21이 성립합니다. 재귀가 "나머지가 0이 되는 순간까지 내려갔다가, 올라오며 x, y를 조립"합니다. 작동 원리가 안 잡혀도 괜찮습니다 — 지금 필요한 것은 "이 함수가 역원을 만든다"는 사실이고, 그것을 다음 단계에서 검증합니다.
3-4. 모듈러 역원 — 내 구현 vs 내장
3의 역원 mod 11을 구해 봅시다. egcd(3, 11)이 주는 x가 역원입니다 (3과 11은 서로소).
g, x, _ = egcd(3, 11)
inv = x % 11 # x가 음수로 나올 수 있어 양수로 정규화
print("내 구현:", inv)
print("검산: 3 ×", inv, "mod 11 =", (3 * inv) % 11)
print("내장:", pow(3, -1, 11)) # 파이썬 3.8+ 내장 역원
내 구현: 4
검산: 3 × 4 mod 11 = 1
내장: 4
출력 읽는 법: 내 egcd가 준 답(4)과 파이썬 내장 pow(3, -1, 11)이 일치하고, 3 × 4 = 12 ≡ 1 (mod 11)로 검산도 통과했습니다. 이제 여러분은 "mod 세계의 나눗셈"을 소유했습니다. RSA에서 비밀키 d를 만드는 계산이 정확히 이 한 줄입니다.
3-5. 오일러 정리 실험
정리를 믿지 말고 실험합니다. 소수 p = 11에서 페르마 소정리 형태(a^(p-1) ≡ 1)를, 합성수 n = 15(φ = 8)에서 일반형을 확인합니다.
p = 11
for a in [2, 5, 7, 10]:
print(f"pow({a}, 10, 11) =", pow(a, p - 1, p))
def gcd(a, b):
while b: a, b = b, a % b
return a
n = 15 # φ(15) = (3-1)(5-1) = 8
for a in [2, 4, 7, 8]:
if gcd(a, 15) == 1:
print(f"pow({a}, 8, 15) =", pow(a, 8, 15))
pow(2, 10, 11) = 1
pow(5, 10, 11) = 1
pow(7, 10, 11) = 1
pow(10, 10, 11) = 1
pow(2, 8, 15) = 1
pow(4, 8, 15) = 1
pow(7, 8, 15) = 1
pow(8, 8, 15) = 1
출력 읽는 법: a를 바꿔도 전부 1입니다. 서로소 조건만 지키면 거듭제곱이 φ(n)번에 순환한다는 것이 눈앞의 데이터입니다. 여기에 한 가지를 얹으면 RSA가 됩니다 — e와 d를 곱해 φ(n)의 배수 + 1이 되게 하면(e×d ≡ 1 (mod φ(n)), 즉 d는 e의 역원), m^(e×d) ≡ m (mod n). 암호화(e제곱)하고 복호화(d제곱)하면 원래 m으로 돌아오는 구조입니다. 다음 챕터에서 이 문장을 코드로 바꿉니다.
4. 미션과 연습문제
미션 — 나만의 역원 계산기
egcd()를 이용해 "역원 계산기" 함수modinv(a, n)을 완성합니다 — 역원이 있으면 양수로 정규화해 반환, 없으면(gcd ≠ 1) "역원 없음"을 반환- 다음 세 쌍에 대해 내 함수와
pow(a, -1, n)의 결과를 비교 표로 만듭니다: (3, 11), (7, 26), (6, 15) — 셋째는 역원이 없는 경우입니다 - 종이에 손으로
gcd(1071, 462)의 유클리드 과정을 다시 쓰고, 코드 출력과 한 줄씩 대조합니다
연습문제
문제 1. 38 mod 12를 시계 산수로 풀어 보세요. 그리고 파이썬에서 음수 -3 % 8의 결과를 예측하고 확인해 보세요.
문제 2. 유클리드 호제법으로 gcd(252, 105)를 손으로 구하세요. 나눗셈 몇 번이 필요한가요?
문제 3. "모듈러 역원은 mod 세계의 나눗셈"이라는 문장을, 7x ≡ 1 (mod 26)을 푸는 과정으로 설명해 보세요.
문제 4. φ(15) = 8임을 직접 세어 확인하고(1~15 중 15와 서로소인 수를 나열), φ(21)을 계산해 보세요. 힌트: 21 = 3 × 7.
5. 모범 답안과 완료 기준
미션 모범 답안
def egcd(a, b):
if b == 0:
return (a, 1, 0)
g, x1, y1 = egcd(b, a % b)
return (g, y1, x1 - (a // b) * y1)
def modinv(a, n):
g, x, _ = egcd(a % n, n)
if g != 1:
return "역원 없음"
return x % n
비교 표의 결과 (2026-09-09 실측): (3, 11) → 4 / 4 일치, (7, 26) → 15 / 15 일치, (6, 15) → "역원 없음" / 내장은 ValueError: base is not invertible for the given modulus. 6과 15는 gcd가 3이라 역원이 없습니다 — 서로소 조건의 의미가 실제로 걸리는 순간입니다.
검증하는 법: ① 세 쌍 모두 내 함수와 내장이 같은 결론인가. ② (6, 15)에서 "없음"의 이유를 gcd로 설명했는가. ③ 손계산 나눗셈이 코드의 while 반복과 일대일로 대응하는가.
연습문제 해답
문제 1 해답. 38시는 12를 두 바퀴(24) 돌고 14, 다시 한 바퀴 빼면 2 — 38 mod 12 = 2입니다. -3 % 8은 파이썬에서 5입니다 (파이썬은 나머지를 항상 0~n-1의 양수로 줍니다. -3 + 8 = 5).
문제 2 해답. 252 = 105×2 + 42 → 105 = 42×2 + 21 → 42 = 21×2 + 0. 나눗셈 세 번, gcd는 21입니다. 코드로 gcd(252, 105)를 확인해 보세요 — 같은 21이 나옵니다.
문제 3 해답. 평범한 산수에서 7x = 1이면 x = 1/7입니다. mod 26에서는 1/7 대신 "7에 곱하면 1이 되는 수"를 찾습니다 — 그것이 역원입니다. egcd(7, 26)은 7×15 + 26×(-4) = 1을 주므로 x = 15. 검산: 7×15 = 105 = 26×4 + 1 ≡ 1 (mod 26). 즉 mod 26 세계에서 7로 나누기는 15 곱하기입니다.
문제 4 해답. 15와 서로소인 수(1~15): 1, 2, 4, 7, 8, 11, 13, 14 — 8개, φ(15) = 8 = (3-1)(5-1)과 일치. φ(21) = (3-1)(7-1) = 2 × 6 = 12입니다.
완료 기준 체크리스트
- [ ] mod 연산을 시계 산수로 설명하고
pow(a, b, n)을 쓴다 - [ ] 파이썬에서 음수의 mod가 양수로 나옴을 안다
- [ ] gcd(1071, 462)를 손으로 구하고 코드와 대조했다
- [ ]
egcd로 역원을 구해pow(a, -1, n)과 일치를 확인했다 - [ ] 역원이 존재하는 조건(서로소)을 말할 수 있다
- [ ] 오일러 정리를 실험 출력으로 확인했다
- [ ] 미션: modinv 함수를 완성하고 세 쌍 비교 표를 만들었다
6. 흔한 실수와 해결
벽 1. pow(a, -1, n)에서 ValueError: base is not invertible
증상: ValueError: base is not invertible for the given modulus (2026-09-09 실측, pow(3, -1, 15)).
원인: a와 n이 서로소가 아닙니다 (gcd(3, 15) = 3). 역원은 서로소일 때만 존재합니다.
해결: 에러가 맞는 동작입니다 — "역원 없음"을 확인한 것입니다. 의도한 경우가 아니라면 a나 n을 잘못 고른 것이니 gcd부터 출력해 확인하세요.
벽 2. egcd의 x가 음수로 나온다
증상: egcd(7, 26)이 구현에 따라 x = -11을 줄 수 있습니다.
원인: ax + by = 1의 해는 무한히 많고, 재귀가 음수 해를 먼저 찾을 수 있습니다. -11도 정답입니다 (7 × (-11) + 26 × 3 = -77 + 78 = 1, 그리고 -77 ≡ 1 (mod 26)).
해결: % n으로 양수 범위로 정규화하세요 — -11 % 26 = 15로, 어느 해든 mod n에서는 같은 역원입니다. 중요한 것은 검산 (a * x) % n == 1의 통과뿐입니다.
벽 3. 7</strong>e % n으로 계산하다 멈춘다**
증상: 큰 지수를 넣으면 몇 분째 안 끝나거나 메모리 에러.
원인: 7**e가 먼저 통째로 계산됩니다 — e가 크면 중간 결과가 수만 자릿수로 폭발합니다.
해결: 처음부터 pow(7, e, n)만 씁니다. 세 개짜리 pow는 매 곱셈마다 나머지를 취해 수를 n 아래로 유지합니다.
벽 4. φ(n)을 "n보다 작은 수의 개수"로 착각한다
증상: φ(15)를 14로 답합니다.
원인: "서로소인" 조건을 빠뜨렸습니다. 3, 5, 6, 9, 10, 12, 15는 15와 공약수가 있어 제외됩니다.
해결: n = pq(소수 둘의 곱)이면 세지 말고 공식으로 — φ(n) = (p-1)(q-1). 오일러 정리 실험처럼 코드로 gcd를 돌려 세어 보면 검산이 됩니다.
벽 5. 수식을 외우려다 포기한다
증상: 오일러 정리 문장이 안 들어옵니다.
원인: 정리는 외우는 것이 아니라 쓰면서 체감하는 것입니다.
해결: 3-5의 실험을 a와 n을 바꿔 다섯 번 더 돌려 보세요. "항상 1이 나온다"를 눈으로 다섯 번 보면, 정리는 문장이 아니라 사실이 됩니다.
7. 정리
오늘의 개념
| 개념 | 한 줄 설명 |
|---|---|
| mod 연산 | 나머지만 취하는 산수 — 결과가 0~n-1에 갇힘 |
| 최대공약수(gcd) | 두 수를 모두 나누는 최대 수 — 유클리드 호제법으로 고속 계산 |
| 서로소 | gcd = 1인 두 수 — 역원 존재 조건 |
| 모듈러 역원 | a × x ≡ 1 (mod n)인 x — mod 세계의 나눗셈 |
| 확장 유클리드 | gcd와 함께 ax + by = gcd의 해 x, y를 구함 — 역원의 원천 |
| 오일러 φ(n) | 1~n 중 n과 서로소인 수의 개수 — pq에서는 (p-1)(q-1) |
| 오일러 정리 | 서로소면 a^φ(n) ≡ 1 (mod n) — RSA 복호화의 근거 |
오늘의 명령어·코드
| 명령 | 하는 일 |
|---|---|
a % n |
나머지 — 파이썬은 음수도 양수로 |
pow(a, b, n) |
모듈러 거듭제곱 — 큰 수는 이것만 |
pow(a, -1, n) |
모듈러 역원 (내장) |
gcd(a, b) (직접 구현) |
유클리드 호제법 |
egcd(a, b) (직접 구현) |
확장 유클리드 — 역원 계산의 심장 |
명령어보다 중요한 감각
오늘의 부품들 — 나머지, gcd, 역원, φ(n) — 는 각각은 초라해 보이지만, 조합하면 현대 인터넷을 지키는 RSA가 됩니다. 특히 "mod 세계에서 나눗셈 = 역원 곱셈"과 "거듭제곱이 φ(n)번에 순환한다"는 두 감각이 다음 챕터의 전부입니다. 수학이 추상적으로 느껴질 때마다 파이썬 한 줄로 실험하세요 — 오늘처럼, 정리는 실험으로 확인할 때 비로소 내 것이 됩니다.
전부 체크되면 Step 227 완료입니다. 사이드바의 체크박스를 눌러 진도를 저장하세요.