한양과기고 에듀테크 수업도구 대시보드

타원곡선 암호 (ECC / Elliptic Curve Cryptography)

RSA는 "큰 수를 소인수분해하기 어렵다"에 기댄다. 타원곡선 암호는 전혀 다른 어려운 문제를 쓴다: 곡선 y² = x³ + ax + b 위의 점 G를 k번 더한 점 kG는 쉽게 구하지만, G와 kG만 보고 k를 되찾는 것(이산로그)은 사실상 불가능하다. 그래서 256비트 ECC 키가 3072비트 RSA 키와 맞먹는 안전성을 낸다. 비트코인 지갑, 요즘 TLS, 휴대폰 보안칩이 모두 이 곡선 위에서 돈다.

1. 곡선 위의 "덧셈" — 현과 접선

타원곡선의 덧셈은 좌표를 더하는 게 아니다. 기하학적 규칙이다: 두 점 P, Q를 잇는 직선을 긋고, 그 직선이 곡선과 만나는 세 번째 점을 찾은 뒤, x축에 대해 뒤집으면 그게 P + Q다. P와 Q가 같은 점이면 직선 대신 접선을 쓴다(→ 2P, "두 배"). 수직선이 되면 세 번째 교점이 없다고 보고 무한원점 O(덧셈의 0)로 간다.

P 의 x좌표 -1.00 Q 의 x좌표 1.40

P와 Q를 움직여 보세요.

2. 유한체 위의 곡선 — 점들의 흩어짐

암호에서는 실수 대신 유한체 F_p를 쓴다. 아래는 y² ≡ x³ + 2x + 3 (mod 97) 위의 모든 점이다(총 –개 + 무한원점). 매끈한 곡선이 격자 위에 흩어진 점들로 바뀐다. 점 덧셈은 1번과 똑같은 공식을 나눗셈만 모듈러 역원으로 바꿔 계산한다. 기준점 G를 정하고 k를 늘리면 kG가 어디로 튈지 전혀 예측되지 않는다.

k = 1

G (기준점)

–

G 의 위수(order)

–

k = 1 → 1·G = G

3. ECDH — 공개된 채널에서 같은 비밀 만들기

Alice는 비밀 정수 a, Bob은 비밀 정수 b를 고른다. 서로 aG, bG만 공개로 교환한다. 그러면 Alice는 a·(bG), Bob은 b·(aG)를 계산 → 둘 다 같은 점 abG에 도착! 도청자는 G, aG, bG를 다 봐도 abG를 못 만든다(이산로그를 풀어야 해서). 이 공유점의 x좌표가 곧 세션 키가 된다.

Alice 의 비밀 a = 6 Bob 의 비밀 b = 11

공개: aG (Alice→Bob)

–

공개: bG (Bob→Alice)

–

Alice 계산 a·(bG)

–

Bob 계산 b·(aG)

–

4. 파이썬으로 보는 점 덧셈 & double-and-add

# 곡선 y^2 = x^3 + a*x + b  (mod p),  O 는 None 으로 표현
def add(P, Q, a, p):
    if P is None: return Q          # O + Q = Q
    if Q is None: return P
    (x1, y1), (x2, y2) = P, 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)

def mul(k, P, a, p):                 # kP 를 O(log k) 번의 덧셈으로
    R, base = None, P
    while k:
        if k & 1: R = add(R, base, a, p)
        base = add(base, base, a, p)   # 더블링
        k >>= 1
    return R

# ECDH
G = (3, 6); a_priv, b_priv = 6, 11
A, B = mul(a_priv, G, 2, 97), mul(b_priv, G, 2, 97)   # 공개
assert mul(a_priv, B, 2, 97) == mul(b_priv, A, 2, 97)   # 같은 공유 비밀

pow(x, -1, p) 는 모듈러 역원 — 유한체에서 "나눗셈"이다(페르마 소정리로 x^(p-2) mod p).
double-and-add: k를 이진수로 보고 비트마다 더블링, 1인 비트에서만 누적. k가 2²⁵⁶이어도 약 256번의 점 덧셈이면 끝. ← 빠른 거듭제곱과 같은 아이디어.
역방향(kG에서 k 찾기)은 지름길이 없다. 이게 타원곡선 이산로그 문제(ECDLP)다.

5. 왜 ECC인가 — RSA와 비교

대칭키 기준 안전성	RSA / DH 키 길이	ECC 키 길이	비율
80비트	1024	160	약 6배
112비트	2048	224	약 9배
128비트	3072	256	약 12배
256비트	15360	512	약 30배

ECDLP는 알려진 최선의 공격이 √n 수준(Pollard rho)이라, 키가 조금만 커도 안전성이 급격히 오른다. RSA는 준지수 시간 인수분해 알고리즘 때문에 키를 훨씬 크게 키워야 한다.
짧은 키 = 더 빠른 서명·적은 대역폭·적은 전력 → 스마트카드·IoT·모바일에 유리.
실제 곡선: 비트코인·이더리움은 secp256k1, 최신 TLS 키 교환은 X25519(Curve25519), 신분증·여권 칩은 P-256.
주의: 양자컴퓨터의 쇼어 알고리즘은 RSA와 ECC를 모두 깬다 → 이후엔 격자 기반 등 PQC로 이동 중.