Skip to main content

Elliptic Curve Cryptography

타원곡선을 쓰는 이유​

블록체인에서 자산의 소유권은 개인키로 증명된다. 개인키를 가진 사람만이 해당 주소의 자산을 사용할 수 있고, 이를 위해 공개키 암호학이 사용된다. 공개키 암호학의 핵심은 공개키로부터 개인키를 역산할 수 없어야 한다는 점이다.

1977년에 발명된 RSA는 오랫동안 공개키 암호학의 표준이었다. 하지만 비트코인과 이더리움은 RSA가 아닌 타원곡선 암호학(ECC, Elliptic Curve Cryptography)을 선택했다.

같은 보안, 더 작은 키​

동일한 보안 수준을 달성하는 데 필요한 키 크기를 비교해보자.

보안 수준 (비트)RSA 키 크기ECC 키 크기RSA/ECC 비율
801,0241606.4x
1122,0482249.1x
1283,07225612x
1927,68038420x
25615,36051230x

비트코인과 이더리움이 사용하는 secp256k1은 256비트 키를 사용한다. 동등한 보안을 RSA로 구현하려면 3,072비트 키가 필요하다. 블록체인은 모든 트랜잭션에 서명이 포함되고, 전 세계 노드가 이를 저장하고 전파한다. 따라서 키 크기의 증가는 저장 공간, 네트워크 대역폭, 검증 시간에 직접적인 비용으로 반영된다.

서로 다른 난제​

두 알고리즘은 서로 다른 수학적 문제에 기반한다.

RSA: 소인수분해 문제

두 개의 큰 소수 p와 q를 곱하면 N을 얻는다. p = 61, q = 53이면 N = 3233이다. 곱셈은 쉽지만, N만 보고 p와 q를 찾는 것(소인수분해)은 매우 어렵다.

순방향: p × q = N  (쉬움)
역방향: N → p, q   (어려움)

ECC: 타원곡선 이산 로그 문제

곡선 위의 점 P를 k번 더하면 점 Q를 얻는다. 이 연산은 빠르게 계산할 수 있지만, P와 Q만 보고 k를 찾는 것은 사실상 불가능하다.

순방향: k × P = Q  (쉬움)
역방향: P, Q → k   (어려움)

타원곡선 이산 로그 문제는 소인수분해 문제보다 더 어려운 문제로 알려져 있다. 이것이 ECC가 더 적은 비트로 동등한 보안을 달성할 수 있는 이유다.

타원곡선의 기하학적 이해​

타원곡선이란?​

타원곡선은 다음 형태의 방정식을 만족하는 점들의 집합이다:

y² = x³ + ax + b

여기서 a와 b는 곡선의 모양을 결정하는 상수다. 비트코인과 이더리움이 사용하는 secp256k1 곡선은 a = 0, b = 7이다.

이 형태를 쓰는 이유

타원곡선이 암호학에 적합한 이유는 이 방정식이 가진 성질 덕분이다.

  1. 3차 곡선이다: x³ 항 덕분에 직선과 곡선이 최대 3점에서 만난다. 이 성질이 "점 덧셈"을 정의하는 데 핵심적으로 사용된다.
  2. x축 대칭이다: 방정식에 y²이 있으므로, (x, y)가 곡선 위의 점이면 (x, -y)도 곡선 위의 점이다. 이 대칭성이 점 덧셈 연산을 정의하는 데 활용된다.
  3. 부드러운 곡선이다: 곡선의 모든 점에서 접선이 유일하게 존재한다. 이를 위해 판별식 조건 4a³ + 27b² ≠ 0을 만족해야 한다. secp256k1의 경우 4(0)³ + 27(7)² = 1323 ≠ 0이므로 이 조건을 충족한다.

"부드럽지 않은" 곡선에는 뾰족점이나 자기 교차점 같은 특이점이 존재한다. 특이점에서는 접선이 유일하게 정의되지 않아서 점 연산이 모호해지므로 암호학에 사용할 수 없다.

"타원"이라는 이름의 유래

"타원곡선"이라는 이름 때문에 타원처럼 생겼다고 생각하기 쉽지만, 실제로 타원과는 기하학적 유사성이 없다. 이 이름은 타원의 둘레를 계산할 때 사용하는 타원 적분(elliptic integral)과의 수학적 연관에서 비롯되었다.

점 덧셈: 두 점을 더한다는 것​

타원곡선 암호학의 핵심은 곡선 위의 점들에 대해 정의되는 특별한 덧셈 연산이다. 일반적인 숫자 덧셈(1 + 2 = 3)과는 완전히 다른, 기하학적 규칙으로 정의된 연산이다.

이 점 덧셈은 군(Group) 구조를 이룬다. 즉, 곡선 위의 점을 아무리 더해도 결과가 항상 곡선 위에 남고(닫힘), 0 역할을 하는 점 O가 있으며, 각 점마다 반대 점(역원)이 존재한다. 또한 덧셈 순서를 바꿔도 결과가 같고(교환법칙), 괄호를 바꿔도 결과가 같다(결합법칙). 이런 성질 덕분에 예측 가능한 연산 규칙을 만들 수 있어 암호학에 적합하다.

점 덧셈의 절차

두 점 P와 Q를 더해서 새로운 점 R을 만드는 방법:

  1. P와 Q를 지나는 직선을 긋는다
  2. 직선이 곡선과 만나는 세 번째 점 X를 찾는다
    • 3차 곡선이므로 직선은 최대 세 점에서 곡선과 만난다
  3. X를 x축 대칭시킨 점이 P + Q다
    • X가 (a, b)라면, P + Q = (a, -b)

점 두 배: 같은 점을 더할 때​

P + P = 2P를 계산하려면 어떻게 해야 할까? 점 덧셈에서는 "P와 Q를 지나는 직선"을 그었는데, P = Q이면 한 점만으로는 직선이 무수히 많다.

해결책: 접선을 사용한다

곡선 위의 한 점에서 곡선에 접하는 직선(접선)은 유일하게 하나만 존재한다.

  1. P에서 곡선의 접선을 긋는다
  2. 접선이 곡선과 만나는 다른 점 X를 찾는다
  3. X를 x축 대칭시킨 점이 2P다

점 두 배의 의미

점 두 배는 효율적인 계산을 가능하게 한다.

8P를 구한다고 하자.

단순한 방법: P + P + P + P + P + P + P + P (7번의 덧셈)
점 두 배 활용: P → 2P → 4P → 8P (3번의 두 배)

이것이 나중에 설명할 "Double-and-Add" 알고리즘의 핵심 아이디어다.

무한원점: 덧셈의 0​

숫자 덧셈에는 0이라는 특별한 수가 있다. 5 + 0 = 5처럼, 어떤 수에 0을 더해도 그 수 자체가 된다. 타원곡선에서도 이런 역할을 하는 점이 필요한데, 이를 무한원점(Point at Infinity)이라 하고 O로 표기한다.

무한원점이 필요한 상황

점 P와 그 x축 대칭점 -P를 더하면 어떻게 될까? P가 (3, 5)라면 -P는 (3, -5)다.

점 덧셈 규칙대로 P와 -P를 지나는 직선을 그으면, 이 직선은 수직선이 된다. 문제는 이 수직선이 타원곡선과 P, -P 두 점에서만 만나고 세 번째 교점이 없다는 것이다.

이 경우를 처리하기 위해, "세 번째 교점이 무한히 먼 곳에 있다"고 간주하고 이 가상의 점을 무한원점 O라고 정의한다.

P + (-P) = O     (점과 그 반대점을 더하면 O)
P + O = P        (어떤 점에 O를 더해도 그대로)

무한원점은 실제 좌표가 없는 추상적인 점이다. 프로그래밍에서는 null이나 특수 플래그로 표현한다.

스칼라 곱셈: 암호학의 핵심 연산​

점 P를 k번 더하는 연산을 스칼라 곱셈이라고 한다.

k × P = P + P + P + ... + P (k번)

이것이 타원곡선 암호학에서 가장 중요한 연산이다.

공개키 암호학의 핵심 아이디어​

  • 개인키 = k (비밀로 유지하는 정수)
  • 공개키 = Q = k × P (세상에 공개해도 안전)
  • 생성점 P = 모든 사람이 알고 있는 표준 점
개인키 k → (k × P) → 공개키 Q

Q를 공개해도 k를 역산할 수 없기 때문에, 개인키를 안전하게 숨기면서 공개키를 세상에 공개할 수 있다.

Double-and-Add 알고리즘​

실제 암호학에서 k는 256비트 정수다. 이는 약 10⁷⁷이라는 엄청나게 큰 수인데, P를 10⁷⁷번 더하는 것은 불가능하다.

Double-and-Add 알고리즘은 k를 이진수로 표현하여 이 문제를 해결한다.

예시: 13 × P 계산

1. 13을 이진수로 변환: 13 = 1101₂ = 8 + 4 + 1

2. 2의 거듭제곱 형태의 점들을 계산 (점 두 배 연산)
   P → 2P → 4P → 8P (3번의 두 배)

3. 필요한 것들만 더한다
   13P = 8P + 4P + P (2번의 덧셈)

총 5번의 연산으로 완료 (단순 덧셈이면 12번 필요)

이 알고리즘 덕분에 k가 256비트여도 최대 512번의 연산(256번의 두 배 + 256번의 덧셈)으로 계산할 수 있다.

일방향성: 역산이 어려운 이유​

스칼라 곱셈 k × P = Q에서:

연산난이도필요한 연산 횟수
k × P = Q 계산쉬움~512번
P와 Q로부터 k 역산사실상 불가능~2¹²⁸번

이것이 타원곡선 이산 로그 문제(ECDLP, Elliptic Curve Discrete Logarithm Problem)다. 256비트 타원곡선이 128비트 보안 수준을 제공한다고 말하는 이유가 바로 이것이다.

ECDSA에서의 활용​

이 일방향성이 다음 글에서 다룰 ECDSA(디지털 서명)의 보안 기반이 된다.

서명 생성: 개인키 k를 사용하여 서명 (r, s) 생성
서명 검증: 공개키 Q만으로 서명의 유효성 확인

서명을 검증하는 사람은 k를 알 수 없지만, 서명이 k로 생성되었음을 수학적으로 확인할 수 있다.

개인키를 직접 공개하지 않으면서도 개인키를 알고 있다는 사실을 증명할 수 있다. 이것이 블록체인에서 트랜잭션의 소유권을 증명하는 방식이다.

유한체​

지금까지 설명한 타원곡선은 실수(real number) 위에서 정의된 것이다. 실수 위에서는 연속적인 곡선이 되지만, 실제 암호학에서는 실수가 아닌 유한체(Finite Field) 위의 타원곡선을 사용한다.

컴퓨터는 실수를 근사값으로 저장하므로 정확한 계산이 불가능하다. 같은 연산을 해도 환경에 따라 미세한 차이가 발생할 수 있기 때문에 유한체를 사용한다.

유한체란?​

유한체는 유한한 개수의 원소만 가진 수 체계다. 가장 단순한 형태는 소수 p에 대해 0부터 p-1까지의 정수만 사용하고, 모든 연산 결과를 p로 나눈 나머지로 표현하는 것이다.

유한체 GF(7) = {0, 1, 2, 3, 4, 5, 6}

덧셈: 3 + 5 = 8 → 8 mod 7 = 1
곱셈: 3 × 4 = 12 → 12 mod 7 = 5
뺄셈: 2 - 5 = -3 → -3 mod 7 = 4

유한체를 사용하면:

  • 모든 연산 결과가 정수이므로 정확하다
  • 결과가 항상 0 ~ p-1 범위 내에 있으므로 크기가 예측 가능하다
  • 컴퓨터가 효율적으로 처리할 수 있다

유한체 위의 타원곡선​

유한체 위의 타원곡선은 다음 방정식을 만족하는 점들의 집합이다:

y² ≡ x³ + ax + b (mod p)

실수 위의 타원곡선은 연속적인 곡선이지만, 유한체 위의 타원곡선은 이산적인 점들의 집합이 된다. 시각적으로는 점들이 흩어져 있어 곡선처럼 보이지 않지만, 점 덧셈의 수학적 규칙은 동일하게 적용된다.

위수(Order)​

유한체 위의 타원곡선은 유한한 개수의 점을 가진다. 이 점의 개수를 곡선의 위수(order)라 하고 n으로 표기한다.

위수가 중요한 이유:

  1. 순환성: 점 P를 n번 더하면 무한원점 O로 돌아온다 (n × P = O)
  2. 개인키 범위: 개인키는 1부터 n-1 사이의 값만 의미가 있다
  3. 보안성: 위수가 클수록 개인키를 추측하기 어려워진다

secp256k1​

비트코인과 이더리움이 사용하는 타원곡선은 secp256k1이다.

이름의 의미​

sec   : Standards for Efficient Cryptography (효율적 암호학 표준)
p     : prime field (소수 유한체)
256   : 키 크기 256비트
k     : Koblitz 곡선 (특별한 형태의 곡선)
1     : 해당 카테고리의 첫 번째 곡선

곡선 파라미터​

secp256k1은 매우 단순한 형태의 타원곡선이다:

방정식: y² = x³ + 7 (mod p)

a = 0, b = 7

p = 2²⁵⁶ - 2³² - 977 (약 78자리의 매우 큰 소수)
n ≈ 2²⁵⁶ (위수, 곡선 위의 점 개수)

secp256k1 선택 배경​

비트코인과 이더리움이 secp256k1을 선택한 이유는 여러 가지가 있다.

  • 효율성: a = 0이어서 점 연산에서 ax 항 계산이 필요 없다. 계산이 단순해지고 구현이 효율적이다.
  • 투명성: NIST가 표준화한 곡선들(P-256 등)은 미국 NSA가 설계했고, 일부 파라미터가 설명 없이 선택되었다. 이 때문에 파라미터 선택의 투명성에 대한 논의가 있어 왔다. 반면 secp256k1의 파라미터는 선택 이유가 명확하다.
    • a = 0: 가장 단순한 형태
    • b = 7: 조건을 만족하는 가장 작은 정수 중 하나
    • p: 효율적인 모듈러 연산을 위해 선택된 메르센 소수에 가까운 형태
  • 검증된 보안: secp256k1은 비트코인 출시 이전부터 암호학 커뮤니티에서 연구된 곡선이었다. 이후 장기간 사용되면서도 실질적인 취약점이 보고되지 않았다.

생성점 G​

생성점 G는 곡선 위의 특별한 점으로, 모든 공개키 생성의 기준이 된다. secp256k1 표준에서 G의 좌표는 미리 정해져 있고, 전 세계 모든 비트코인/이더리움 구현체가 동일한 G를 사용한다.

공개키 Q = d × G

d: 개인키 (비밀)
G: 생성점 (표준에서 정한 값, 공개)
Q: 공개키 (공개)

공개키와 개인키 생성​

타원곡선을 사용한 키 생성 과정을 살펴보자.

개인키​

개인키는 1부터 n-1 사이의 랜덤 정수다. secp256k1에서 n은 약 2²⁵⁶이므로, 개인키는 256비트(32바이트) 크기의 숫자다.

개인키 d: 1 ≤ d < n

예시: 0x4c0883a69102937d6231471b5dbb6204fe5129617082792ae468d01a3f362318

개인키가 예측 가능하면 누군가 같은 개인키를 생성해서 자산을 탈취할 수 있으므로 반드시 암호학적으로 안전한 난수 생성기(CSPRNG)를 사용해야 한다.

공개키​

공개키는 개인키와 생성점 G의 스칼라 곱이다:

공개키 Q = d × G

d: 개인키 (256비트 정수)
G: 생성점 (표준에서 정한 곡선 위의 점)
Q: 공개키 (곡선 위의 점, x좌표와 y좌표로 구성)

Q는 타원곡선 위의 점이므로 (x, y) 좌표로 표현된다.

공개키 형식​

공개키는 두 가지 형식으로 표현할 수 있다.

비압축 형식 (65바이트):

04 || x좌표(32바이트) || y좌표(32바이트)

접두사 0x04는 "비압축 형식"을 의미한다.

압축 형식 (33바이트):

02 || x좌표  (y가 짝수인 경우)
03 || x좌표  (y가 홀수인 경우)

압축이 가능한 이유는 타원곡선의 x축 대칭 성질 때문이다. x좌표를 알면 y² = x³ + 7 (mod p)에서 y를 계산할 수 있는데, 해는 +y와 -y 두 개다. 접두사(02 또는 03)로 어떤 y인지 구분하면 된다.

주소​

공개키에서 주소를 생성하는 과정은 체인마다 다르다. 주소는 공개키를 해시 함수로 압축한 것으로, 더 짧고 사용하기 편리하다. 자세한 주소 생성 과정은 다음 글 ECDSA에서 다룬다.

코드로 보는 타원곡선​

실제 코드로 타원곡선 연산과 키 생성을 확인해보자.

예제 코드

전체 테스트 코드는 crypto-examples/cryptography-examples/02-elliptic-curve에서 확인할 수 있다.

ec-math.ts
// y² = x³ + ax + b (mod p)
const p = 17n; // finite field size
const a = 0n;
const b = 7n;

// Point type (null = point at infinity O)
type Point = { x: bigint; y: bigint } | null;

// Modular arithmetic: normalize to 0 ~ p-1 range
function mod(n: bigint): bigint {
  return ((n % p) + p) % p;
}

// Modular inverse: n * inv ≡ 1 (mod p)
function inverse(n: bigint): bigint {
  const nMod = mod(n);
  for (let i = 1n; i < p; i++) {
    if (mod(nMod * i) === 1n) return i;
  }
  throw new Error("inverse not found");
}

// Check if point is on curve
function isOnCurve(P: Point): boolean {
  if (P === null) return true;
  const left = mod(P.y * P.y);
  const right = mod(P.x * P.x * P.x + a * P.x + b);
  return left === right;
}

// Point addition: P + Q
function pointAdd(P: Point, Q: Point): Point {
  if (P === null) return Q;
  if (Q === null) return P;

  const { x: x1, y: y1 } = P;
  const { x: x2, y: y2 } = Q;

  // P + (-P) = O
  if (x1 === x2 && mod(y1 + y2) === 0n) return null;

  let slope: bigint;
  if (x1 === x2 && y1 === y2) {
    // Point doubling: tangent line slope
    slope = mod((3n * x1 * x1 + a) * inverse(2n * y1));
  } else {
    // General addition: secant line slope
    slope = mod((y2 - y1) * inverse(x2 - x1));
  }

  const x3 = mod(slope * slope - x1 - x2);
  const y3 = mod(slope * (x1 - x3) - y1);
  return { x: x3, y: y3 };
}

// Scalar multiplication: k * P (Double-and-Add)
function scalarMultiply(k: bigint, P: Point): Point {
  if (P === null || k === 0n) return null;

  let result: Point = null;
  let addend: Point = P;
  let n = k;

  while (n > 0n) {
    if (n & 1n) {
      result = pointAdd(result, addend);
    }
    addend = pointAdd(addend, addend);
    n >>= 1n;
  }

  return result;
}

// Find all points on curve
function findAllPoints(): Point[] {
  const points: Point[] = [null];
  for (let x = 0n; x < p; x++) {
    const rhs = mod(x * x * x + a * x + b);
    for (let y = 0n; y < p; y++) {
      if (mod(y * y) === rhs) points.push({ x, y });
    }
  }
  return points;
}

console.log("=== Elliptic Curve y² = x³ + 7 (mod 17) ===\n");

const allPoints = findAllPoints();
console.log(`Points on curve (order): ${allPoints.length}`);
console.log("Point list:");
allPoints.forEach((pt, i) => {
  if (pt === null) {
    console.log(`  [${i}] O (point at infinity)`);
  } else {
    console.log(`  [${i}] (${pt.x}, ${pt.y})`);
  }
});

// Generator point and scalar multiplication
const G: Point = { x: 6n, y: 11n };
console.log(`\nGenerator G = (${G.x}, ${G.y})`);
console.log(`On curve: ${isOnCurve(G)}`);

console.log("\n=== Scalar Multiplication (k × G) ===");
for (let k = 1n; k <= 10n; k++) {
  const result = scalarMultiply(k, G);
  if (result === null) {
    console.log(`${k}G = O (point at infinity)`);
  } else {
    console.log(`${k}G = (${result.x}, ${result.y})`);
  }
}

위 코드들의 실행 결과:

=== Elliptic Curve y² = x³ + 7 (mod 17) ===

Points on curve (order): 18
Point list:
  [0] O (point at infinity)
  [1] (1, 5)
  [2] (1, 12)
  [3] (2, 7)
  [4] (2, 10)
  [5] (3, 0)
  [6] (5, 8)
  [7] (5, 9)
  [8] (6, 6)
  [9] (6, 11)
  [10] (8, 3)
  [11] (8, 14)
  [12] (10, 2)
  [13] (10, 15)
  [14] (12, 1)
  [15] (12, 16)
  [16] (15, 4)
  [17] (15, 13)

Generator G = (6, 11)
On curve: true

=== Scalar Multiplication (k × G) ===
1G = (6, 11)
2G = (1, 12)
3G = (8, 3)
4G = (2, 7)
5G = (10, 2)
6G = (5, 8)
7G = (15, 13)
8G = (12, 16)
9G = (3, 0)
10G = (12, 1)
=== Ethereum Key Generation ===

Private Key (256-bit integer):
  0x4c0883a69102937d6231471b5dbb6204fe5129617082792ae468d01a3f362318
  Length: 64 hex chars = 256 bits

Public Key (uncompressed, 512 bits = x + y):
  0x044e3b81af9c2234cad09d679ce6035ed1392347ce64ce405f5dcd36228a25de6e47fd35c4215d1edf53e6f83de344615ce719bdb0fd878f6ed76f06dd277956de
  Prefix: 0x04 (0x04 = uncompressed)
  x: 4e3b81af9c2234cad09d679ce6035ed1392347ce64ce405f5dcd36228a25de6e
  y: 47fd35c4215d1edf53e6f83de344615ce719bdb0fd878f6ed76f06dd277956de

Public Key (compressed, 264 bits):
  0x024e3b81af9c2234cad09d679ce6035ed1392347ce64ce405f5dcd36228a25de6e
  Prefix: 0x02 (y even)

Address (last 20 bytes of Keccak256(pubkey)):
  0x2c7536E3605D9C16a7a3D7b1898e529396a65c23

첫 번째 예제에서 GF(17) 위의 타원곡선은 18개의 점을 가진다(위수 = 18). 스칼라 곱셈 결과를 보면, 같은 생성점 G에서 시작해도 k 값에 따라 완전히 다른 점에 도달한다. 결과 점 Q만 보고 k를 역산하는 것은 작은 유한체에서는 전부 탐색하여 가능하지만 secp256k1처럼 2²⁵⁶ 크기의 유한체에서는 사실상 불가능하다.

정리​

요약​

  • 타원곡선 암호학(ECC)은 RSA보다 훨씬 짧은 키로 동등한 보안을 제공한다. (256비트 vs 3,072비트)
  • 점 덧셈은 기하학적으로 정의되며, 점들은 군(Group) 구조를 형성한다.
  • 스칼라 곱셈 k × P = Q에서 Q를 계산하는 것은 쉽지만, k를 역산하는 것은 사실상 불가능하다. (일방향성)
  • 유한체를 사용하여 컴퓨터에서 정확하고 효율적인 연산을 수행한다.
  • secp256k1은 비트코인과 이더리움이 사용하는 곡선으로, 투명하고 효율적인 파라미터를 가진다.

키 생성 흐름​

랜덤 256비트 정수
    ↓
개인키 (d)
    ↓ d × G (스칼라 곱셈)
공개키 (Q)
    ↓ 해시 함수
주소

참고 자료​