Step 236. ECC 맛보기: 타원곡선 위의 덧셈 — 점을 더해서 암호를 만든다
Level 3 — CTF 실전과 공격 스킬 심화 | 난이도 ★★★★☆ | 예상 소요 시간 4시간
전제: Step 227(모듈러 역원 —
pow(x, -1, p)가 오늘 기울기 공식의 분모입니다), Step 235(DH의 이산 대수 문제).
⚠️ 이 챕터의 실습은 내 랩·합법 플랫폼 전용입니다. 허가 없는 시스템에 적용하면 범죄입니다.
- 준비물: 파이썬 3(실측: 3.12.14). 설치 없이 표준 라이브러리만 씁니다.
- 주의: 처음에는 "덧셈인데 왜 이렇게 복잡하지"라는 생각이 듭니다. 정상입니다 — 오늘의 덧셈은 좌표 위의 덧셈입니다.
RSA와 DH가 "mod 세계의 거듭제곱"으로 만든 암호라면, 타원곡선 암호(ECC)는 "곡선 위의 점 덧셈"으로 만드는 암호입니다. 문법은 바뀌지만 함정 함수의 구조는 같습니다 — 점 P를 k번 더한 Q는 계산이 빠른데, P와 Q만 보고 k를 찾는 것(ECDLP)은 어렵습니다. 그리고 이 버전의 이산 대수 문제는 지수 시간보다 좋은 공격이 알려지지 않아, 훨씬 짧은 키(256비트 ≈ RSA 3072비트)로 같은 강도를 냅니다. 비트코인 서명도, 현대 TLS의 키 교환(ECDHE)도 이것입니다. 오늘은 점 덧셈을 직접 구현하고, 작은 곡선을 실제로 깨 봅니다.
1. 학습 목표
이 챕터를 끝내면 다음을 할 수 있습니다:
- 유한체 위 타원곡선
y² = x³ + ax + b (mod p)의 점을 전부 나열한다 - 점 덧셈의 기하학적 의미(할선·접선)와 대수 공식을 연결한다
- 모듈러 역원을 쓴 점 덧셈 함수와 더블 앤드 애드 스칼라 곱을 구현한다
- 스칼라 곱의 순환 구조(점의 위수)를 출력으로 확인한다
- 작은 곡선에서 ECDLP를 전수 탐색으로 풀고, 실제 곡선이 왜 안전한지 말할 수 있다
2. 배경 지식 — 오늘의 도구와 개념
오늘의 도구 한눈에 보기
| 구분 | 내용 |
|---|---|
| 언어·환경 | 파이썬 3 (실측: 3.12.14) — 표준 라이브러리만, 설치 없음 |
| 오늘의 명령어 | pow(x, -1, p) (모듈러 역원), 직접 짜는 add() / mul() |
| 필요한 개념 | 유한체 위 타원곡선, 점 덧셈, 무한원점 O, 배점, 스칼라 곱, ECDLP |
| 오늘의 산출물 | 점 목록 + 점 연산 구현 + ECDLP 전수 탐색 성공 출력 |
2-1. 유한체 위의 타원곡선 — 연속 곡선이 아니라 점의 집합
학교에서 본 타원곡선 y² = x³ + ax + b는 실수 위의 매끄러운 곡선입니다. ECC가 쓰는 것은 이 식을 mod p 세계(유한체)로 옮긴 것 — x, y를 0~p-1에서만 찾으므로 곡선은 "띄엄띄엄 있는 유한개의 점"이 됩니다. 오늘 쓸 곡선은 y² = x³ + 2x + 2 (mod 17)입니다. 점이 18개뿐이라 눈으로 전부 볼 수 있습니다.
2-2. 점 덧셈 — 기하가 규칙이 되는 순간
실수 곡선에서의 덧셈 규칙: 점 P와 Q를 잇는 직선이 곡선과 만나는 세 번째 점을 찾아, x축 대칭시킨 점이 P + Q. P + P(배점)는 P에서의 접선을 씁니다. 이 기하 규칙을 대수로 옮기면 기울기 공식이 됩니다:
P ≠ Q: s = (y2 - y1) / (x2 - x1) (할선의 기울기)
P = Q: s = (3x1² + a) / (2y1) (접선의 기울기)
x3 = s² - x1 - x2, y3 = s(x1 - x3) - y1
mod p 세계에서 나눗셈은 전부 모듈러 역원입니다 — 분모에 pow(분모, -1, p)가 들어갑니다. 여기에 특별한 점 무한원점 O(덧셈의 항등원, 0의 역할)를 더하면 점들은 덧셈에 대해 닫힌 구조(군)를 이룹니다.
2-3. ECDLP — ECC의 함정 함수
점 P를 k번 더한 Q = kP는 더블 앤드 애드로 빠르게 계산됩니다(k가 256비트여도 256번 안쪽 연산). 반대로 P와 Q가 주어졌을 때 k를 찾는 문제가 ECDLP(타원곡선 이산 대수 문제)입니다. mod p의 이산 대수(DH)에는 지수 시간보다 빠른 공격(인덱스 계산법)이 있지만, ECDLP에는 그런 범용 공격이 알려져 있지 않습니다 — 그래서 같은 안전도를 훨씬 작은 수로 얻습니다. 이것이 "ECC = 짧은 키"의 이유 전부입니다.
2-4. 실제 곡선의 존재
오늘의 mod 17 곡선은 장난감입니다. 실전은 표준 곡선 — 비트코인의 secp256k1, TLS의 P-256 — 를 씁니다. 점의 개수가 약 2²⁵⁶개라 전수 탐색은 무의미하고(효율적 공격도 2¹²⁸ 연산), 파라미터는 공개 표준으로 검증됩니다. 곡선을 직접 설계하는 일은 없습니다 — 표준 곡선을 라이브러리로 씁니다.
3. 따라 하기
이 챕터의 모든 출력은 2026-09-09 파이썬 3.12.14 실측입니다. 곡선은 y² = x³ + 2x + 2 (mod 17)입니다.
3-1. 곡선 위의 점 전부 나열하기
x에 0~16을 대입하고, 우변 값이 제곱수(mod 17)인 y를 찾습니다:
p, a, b = 17, 2, 2
points = []
for x in range(p):
rhs = (x**3 + a * x + b) % p
for y in range(p):
if (y * y) % p == rhs:
points.append((x, y))
print(f"점의 개수: {len(points)} + 무한원점 O")
print(points)
점의 개수: 18 + 무한원점 O
[(0, 6), (0, 11), (3, 1), (3, 16), (5, 1), (5, 16), (6, 3), (6, 14), (7, 6), (7, 11), (9, 1), (9, 16), (10, 6), (10, 11), (13, 7), (13, 10), (16, 4), (16, 13)]
출력 읽는 법: 세 가지 관찰 포인트가 있습니다. ① 점이 18개뿐 — 유한합니다. ② 같은 x에 y가 두 개씩 붙습니다 ((5,1)과 (5,16) — 16 ≡ -1 mod 17, 즉 x축 대칭). ③ x=1, 2, 4 등에는 점이 없습니다 — 우변이 mod 17의 제곱수가 아닌 경우입니다.
3-2. 점 덧셈 구현
def add(P, Q, a=2, p=17):
if P is None: return Q # O + Q = Q
if Q is None: return P
x1, y1 = P; x2, y2 = Q
if x1 == x2 and (y1 + y2) % p == 0:
return None # P + (-P) = O
if P == Q: # 배점: 접선 기울기
s = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p
else: # 할선 기울기
s = (y2 - y1) * pow(x2 - x1, -1, p) % p
x3 = (s * s - x1 - x2) % p
y3 = (s * (x1 - x3) - y1) % p
return (x3, y3)
P, Q = (5, 1), (6, 3)
print("P + Q =", add(P, Q))
print("P + P =", add(P, P)) # 배점
print("P + O =", add(P, None)) # 항등원
P + Q = (10, 6)
P + P = (6, 3)
P + O = (5, 1)
출력 읽는 법: (10, 6)과 (6, 3) 모두 3-1의 목록에 있습니다 — 덧셈 결과가 다시 곡선 위의 점입니다(닫혀 있다). pow(2 * y1, -1, p)가 분모의 역원입니다 — mod 세계의 나눗셈은 전부 이 한 줄입니다(Step 227의 역원이 여기서 쓰입니다).
3-3. 스칼라 곱 — 더블 앤드 애드
k·P를 "P를 k번 더하기"로 하면 k가 크면 못 씁니다. 이진 전개로 합니다 — 13P = 8P + 4P + P처럼 배점과 덧셈만으로:
def mul(k, P, a=2, p=17):
R = None
while k:
if k & 1:
R = add(R, P, a, p)
P = add(P, P, a, p)
k >>= 1
return R
for k in range(1, 20):
print(f"{k:2d}*P =", mul(k, (5, 1)))
1*P = (5, 1)
2*P = (6, 3)
3*P = (10, 6)
4*P = (3, 1)
5*P = (9, 16)
6*P = (16, 13)
7*P = (0, 6)
8*P = (13, 7)
9*P = (7, 6)
10*P = (7, 11)
11*P = (13, 10)
12*P = (0, 11)
13*P = (16, 4)
14*P = (9, 1)
15*P = (3, 16)
16*P = (10, 11)
17*P = (6, 14)
18*P = (5, 16)
19*P = None
출력 읽는 법: 19·P가 O(무한원점, 여기선 None)입니다 — P의 위수(order)가 19라는 뜻이고, 20·P부터는 다시 (5, 1)로 순환합니다. 유한개 점 위의 덧셈이므로 반드시 순환합니다. 이 순환 구조가 "거듭제곱의 순환"(Step 227의 오일러 정리)과 정확히 평행한, ECC판의 뼈대입니다.
3-4. ECDLP 깨기 — 작은 곡선의 비극
Q = 13P = (16, 4)가 주어졌고 k를 모른다고 합시다. 점이 18개뿐이니 전수 탐색:
Q_target = mul(13, (5, 1)) # = (16, 4)
for k in range(1, 20):
if mul(k, (5, 1)) == Q_target:
print("전수 탐색 성공: k =", k)
break
전수 탐색 성공: k = 13
읽는 법: 즉시 풀렸습니다. DH의 작은 p와 같은 구조입니다 — 함정 함수는 "공간이 충분히 클 때"만 함정입니다. 실제 곡선 secp256k1은 점이 약 2²⁵⁶개고, 최선의 범용 공격도 약 2¹²⁸ 연산 — 같은 2¹²⁸ 안전도를 RSA로 얻으려면 약 3072비트 키가 필요합니다. 256 대 3072, 이것이 ECC의 존재 이유입니다.
4. 미션과 연습문제
미션 — 미니 ECC 키 교환
- 오늘의 곡선(
mod 17, P = (5, 1)) 위에서 ECC판 DH를 완성합니다 — Alice가 비밀 a, Bob이 비밀 b를 골라 공개값 aP, bP를 교환하고, 각자 abP를 계산해 일치를 확인합니다 (3-3의mul재사용) - 공격자 시나리오: 공개값 aP, bP만 주어졌을 때 전수 탐색으로 a, b를 복구해 공유 비밀을 재계산합니다
- 계산 과정에서 배점(
P == Q분기)이 최소 한 번은 실제로 실행됐음을 확인하는 출력을 넣습니다 (힌트: k의 이진 전개)
연습문제
문제 1. 점 덧셈 공식에서 분모 2y1 또는 x2 - x1에 pow(분모, -1, p)를 쓰는 이유를 "mod 세계의 나눗셈" 관점에서 설명해 보세요.
문제 2. 3-1의 목록에서 (5, 1)의 "반대편 점"(덧셈 역원)은 무엇인가요? 그리고 둘을 더하면 어떤 점이 되나요?
문제 3. P = (5, 1)의 위수가 19라는 것이 3-3 출력에서 어떻게 드러나나요? 위수가 큰 점이 암호에 유리한 이유도 함께 답해 보세요.
문제 4. ECC가 RSA보다 짧은 키로 같은 안전도를 내는 이유를 "알려진 공격의 차이"로 설명해 보세요.
5. 모범 답안과 완료 기준
미션 모범 답안
P = (5, 1)
a_sec, b_sec = 7, 11 # Alice, Bob의 비밀
A_pub = mul(a_sec, P) # (0, 6)
B_pub = mul(b_sec, P) # (13, 10)
shared_A = mul(a_sec, B_pub) # a(bP) = abP
shared_B = mul(b_sec, A_pub) # b(aP) = abP
print("공개값:", A_pub, B_pub)
print("공유 비밀:", shared_A, shared_B, "일치:", shared_A == shared_B)
실측 결과: 공개값 (0, 6), (13, 10) — 공유 비밀은 둘 다 3-3 표에서 77·P 위치의 값, 즉 mul(77, P)와 같습니다 (77 = 7×11, 위수 19 기준으로 77 mod 19 = 1이므로 결과는 (5, 1)입니다 — 순환 덕에 이런 검산도 됩니다).
공격자 부분: for k in range(1, 19): if mul(k, P) == A_pub: ...로 a = 7을 복구한 뒤 mul(7, B_pub)로 공유 비밀 획득. 배점 실행 확인은 mul 안의 add(P, P)에 카운터를 달거나, k = 13(이진 1101)에서 배점이 3회 일어남을 지적하면 됩니다.
검증하는 법: ① 공유 비밀 일치 출력. ② 전수 탐색 복구 성공 출력. ③ 배점 분기가 실제로 탔다는 근거(카운트 또는 이진 전개 설명).
연습문제 해답
문제 1 해답. mod p 세계에는 나눗셈이 없고 "곱하면 1이 되는 짝(모듈러 역원)"을 곱하는 것이 나눗셈입니다. 기울기의 분모를 역원으로 바꿔 곱해야 결과가 0~p-1 안의 점 좌표로 닫힙니다. pow(분모, -1, p)가 그 역원 계산입니다.
문제 2 해답. (5, 16)입니다 — 16 ≡ -1 (mod 17), 같은 x에 y 부호만 반대인 점이 덧셈 역원입니다. 둘을 더하면 무한원점 O가 됩니다 (x1 == x2 and (y1+y2) % p == 0 분기).
문제 3 해답. 19·P = O(None)이고 1~18·P가 전부 다르게 나열된 것으로 드러납니다. 위수가 크면 k의 후보 공간이 커져 ECDLP의 전수 탐색이 어려워지므로, 기저점 P는 위수가 큰 점으로 고릅니다 (실제 곡선에서는 위수가 소수에 가까운 큰 점을 씁니다).
문제 4 해답. RSA의 근거(정수 소인수분해)와 DH의 근거(유한체 이산 대수)에는 지수 시간보다 빠른 공격(체 체법, 인덱스 계산법)이 알려져 있어 키를 크게 키워야 합니다. ECDLP에는 그런 범용 공격이 없어서 최선이 제곱근 수준(약 2¹²⁸)이라, 훨씬 작은 파라미터(256비트)로 같은 안전도에 도달합니다.
완료 기준 체크리스트
- [ ] 유한체 위 타원곡선의 점을 전부 나열하는 코드를 썼다
- [ ] 점 덧셈의 할선·접선 공식과 mod 역원의 역할을 설명할 수 있다
- [ ]
add()와 더블 앤드 애드mul()을 직접 구현했다 - [ ] 스칼라 곱의 순환(위수)을 출력으로 확인했다
- [ ] 작은 곡선의 ECDLP를 전수 탐색으로 풀었다
- [ ] ECC의 키 길이 장점을 "공격 난이도 차이"로 설명할 수 있다
- [ ] 미션: 미니 ECC 키 교환 + 공격자 복구 완성
6. 흔한 실수와 해결
벽 1. ValueError: base is not invertible for the given modulus
증상: pow(2 * y1, -1, p)에서 이 에러.
원인: 분모가 p와 서로소가 아닙니다 — p가 소수가 아니거나, 2 * y1이 0(mod p)인 특수한 점(y1 = 0, 접선이 수직)을 배점하려 한 경우.
해결: 오늘 곡선에서는 p = 17이 소수라 분모만 0이 아니면 됩니다. y1 = 0인 점의 배점은 O가 되는 게 정답이니, 구현에 그 분기를 추가하세요.
벽 2. 덧셈 결과가 곡선 위에 없다
증상: add(P, Q)의 결과가 3-1 목록에 없는 좌표.
원인: 10중 9는 mod 누락입니다 — s * s - x1 - x2에 % p를 안 붙였거나, 음수를 % p 없이 둔 경우 (파이썬은 음수의 %도 양수를 주니 붙이기만 하면 됩니다).
해결: 매 단계(기울기, x3, y3)마다 % p를 확인하고, 결과가 목록에 있는지로 매번 검증하세요 — 그 목록이 오늘 최고의 테스트 코드입니다.
벽 3. 배점과 일반 덧셈 분기를 반대로 썼다
증상: P + P를 할선 공식으로 계산하다 pow(0, -1, p) 에러.
원인: P == Q이면 분모 x2 - x1이 0이라 역원이 없습니다 — 그래서 접선 공식이 따로 있는 것입니다.
해결: 분기 순서를 ① O 처리 ② P + (-P) = O ③ P == Q(배점) ④ 일반 덧셈으로 고정하세요.
벽 4. 위수가 19인데 왜 점은 18개?
증상: 3-1의 18개와 3-3의 위수 19가 어긋나 보입니다.
원인: 어긋나지 않았습니다 — O를 포함하면 전체 점은 19개(18 + 무한원점)이고, 이 곡선에서는 P 하나가 19개 전부를 생성합니다.
해결: 점 셀 때 O를 빼먹지 마세요. "유한체 위 타원곡선의 점"은 항상 무한원점을 포함합니다.
벽 5. mul이 k번 반복 덧셈보다 느린 것 같다
증상: k = 13인데 왜 굳이 이진 전개인가 싶습니다.
원인: 오늘 범위에서는 맞는 말입니다. 차이는 k가 256비트일 때 나옵니다 — 반복 덧셈은 2²⁵⁶회(불가능), 더블 앤드 애드는 256회.
해결: 지금은 작은 k로 정답 검증(반복 덧셈과 결과 비교)을 하고, "왜 이 방법인가"는 큰 k의 세계관으로 이해하세요.
7. 정리
오늘의 개념
| 개념 | 한 줄 설명 |
|---|---|
| 유한체 위 타원곡선 | y² = x³ + ax + b (mod p)를 만족하는 유한개의 점 집합 |
| 점 덧셈 | 할선/접선과 곡선의 교점을 x축 대칭 — mod 역원으로 계산 |
| 무한원점 O | 덧셈의 항등원(0의 역할) — 점 목록에 항상 포함 |
| 배점 | P + P — 접선 공식 사용, 분기 필수 |
| 스칼라 곱 | k·P — 더블 앤드 애드로 256비트 k도 256회 연산 |
| 위수 | k·P = O가 되는 최소 k — 클수록 ECDLP 후보 공간이 큼 |
| ECDLP | Q = kP에서 k 찾기 — 범용 고속 공격이 없어 짧은 키 허용 |
오늘의 명령어·코드
| 명령 | 하는 일 |
|---|---|
pow(x, -1, p) |
모듈러 역원 — 기울기 공식의 분모 처리 |
add(P, Q) (직접 구현) |
점 덧셈 — O/역점/배점/일반 4분기 |
mul(k, P) (직접 구현) |
스칼라 곱 — 더블 앤드 애드 |
| 점 나열 이중 루프 | 곡선 위 모든 점 수집 — 검증용 목록 |
명령어보다 중요한 감각
ECC의 수식은 복잡해 보이지만 뼈대는 Step 235와 같습니다 — "가기 쉽고 돌아오기 어려운 연산" 하나와, 그 위의 키 교환. 다른 것은 무대가 mod 곱셈에서 곡선 위 덧셈으로 바뀌었다는 것, 그리고 그 덕분에 키가 열 배 이상 짧아졌다는 것뿐입니다. 오늘 18개짜리 점 집합을 전부 나열하고 깨 본 경험이, secp256k1이라는 거대한 점 바다를 신뢰하는 근거가 됩니다 — 구조는 오늘 본 것과 같고, 크기만 다릅니다.
전부 체크되면 Step 236 완료입니다. 사이드바의 체크박스를 눌러 진도를 저장하세요.