[암호학 기본 06] ECC(Elliptic Curve Cryptography)

omin·2025년 8월 14일

암호학 기본

목록 보기

6/6

RSA와 같은 전통적인 공개키 암호는 보안 수준을 높이기 위해 키 크기를 지수적으로 늘려야 하는 한계가 있으며, 이로 인해 매우 큰 정수에 대한 지수 연산이 필요해 연산 복잡도와 성능 저하가 발생한다. 커진 키는 메모리 사용량을 증가시켜 오버헤드를 유발하고, 특히 모바일 기기에서는 높은 연산량과 메모리 사용으로 인해 전력 소모가 커져 배터리 효율이 떨어진다. 이러한 한계를 극복하기 위해 등장한 기술이 바로 타원 곡선을 활용한 ECC(Elliptic Curve Cryptography)이다.

ECC의 수학적 기반 및 이론

1. 실수체에서의 타원 곡선

실수체 $\mathbb{R}$ 에서의 타원 곡선은 Weierstrass(바이어슈트라스) 표준형으로 정의된다.

𝑦^2=𝑥^3+𝑎𝑥+𝑏

여기서 $a, b \in \mathbb{R}$ 이며, 다음 판별식 조건을 만족해야 한다.

Δ=−16(4𝑎^3+27𝑏^2) \neq 0

이 조건은 곡선이 특이점(singular point)을 가지지 않도록 보장한다.

곡선이 자기 자신과 교차하지 않음
뾰족한 점(cusp)이 없음
모든 점에서 접선이 정의됨

2. 유한체에서의 타원 곡선

암호학에서는 계산 효율성과 보안성을 모두 확보하기 위해 실수체 대신 유한체(finite field) 위에서 타원 곡선을 정의한다.

소수체 $\mathrm{GF}(p)$ 에서의 타원 곡선

y^2≡x^3+ax+b \pmod{n}

$p$ 는 소수
$a, b \in \mathrm{GF}(p)$

특이점이 없을 조건:

4a^3+27b^2\neq0 \pmod{n}

$p > 16$ 일 때 위 조건은 $\Delta \not\equiv 0 \pmod{p}$ 와 동일하며, $p \leq 16$ 인 경우는 $p = 2$ 만 고려하면 된다.

3. 타원 곡선 상의 군 구조

군의 성질
타원 곡선 상의 점들과 덧셈 연산은 아벨군(Abelian group)을 형성한다. 아벨군의 조건은 아래의 그림과 같다.

아벨군은 연산에 대해 닫힘, 결합법칙, 항등원, 역원, 교환법칙을 모두 만족하는 대수적 구조를 가진 집합이다. 이 조건들을 충족한다는 것은, 집합 내의 어떤 두 원소를 연산해도 결과가 다시 집합 안에 있으며(닫힘), 연산 순서를 바꿔도 결과가 같고(교환법칙), 괄호의 위치를 바꿔도 결과가 동일하며(결합법칙), 연산에 영향을 주지 않는 특별한 원소(항등원)가 존재하고, 모든 원소에 대해 연산 결과를 항등원으로 만드는 짝(역원)이 존재한다는 것을 의미한다.

점의 덧셈 연산

1) $P \neq Q$ 인 경우(점의 덧셈)

기울기 계산 $m = \frac{y_2 - y_1}{x_2 - x_1}$
새로운 점 계산 $x_3 = m^2 - x_1 - x_2$ $y_3 = m(x_1 - x_3) - y_1$

2) $P = Q$ 인 경우 (점의 곱셈)

기울기 계산 $m = \frac{3x_1^2 + a}{2y_1}$
새로운 점 계산 $x_3 = m^2 - 2x_1$ $y_3 = m(x_1 - x_3) - y_1$

스칼라 곱셈과 이산 로그 문제
1) 스칼라 곱셈
타원 곡선 위 점 P에 정수 k를 곱하는 연산은 점 P를 k번 더하는 것을 의미한다.

kP = \underbrace{P + P + \cdots + P}_{k\text{번}}

2) 음수 연산
점 P의 역원인 −P는 P의 y좌표에 부호를 바꾸어 얻을 수 있다.

−P=(P_x,−P_y)

3) 관련 보안 문제
스칼라 곱셈의 역연산은 ECC 보안의 핵심 기반이다. 타원 곡선 위 점 $P$ 와 $Q=kP$ 가 주어졌을 때, 정수 k를 찾는 문제는 타원 곡선 이산 로그 문제(ECDLP, Elliptic Curve Discrete Logarithm Problem)라고 불린다. 이 문제가 계산적으로 매우 어렵기 때문에 ECC의 보안성이 보장된다.

타원 곡선 이산 로그 문제 (ECDLP)

ECDLP(Elliptic Curve Discrete Logarithm Problem)는 타원 곡선 암호 시스템(ECC)의 보안을 지탱하는 핵심적인 문제이다.

입력: 타원 곡선 E 위에서 정의된 기준점 P와 P를 여러 번 더해 얻은 점 Q (Q=kP).
출력: Q=kP를 만족하는 정수 k를 찾는 것이다.
어려움: 점 P와 Q가 주어졌을 때 k를 찾는 것은 매우 어렵지만, P와 k가 주어졌을 때 Q를 계산하는 것은 상대적으로 쉽다.

현재 보안 수준
ECDLP의 난이도는 곡선의 비트 수에 따라 결정된다. 256비트 타원 곡선의 경우, 공격 복잡도는 약 $O(2^{128})$ 이다. 이는 현재 기술로는 계산이 불가능한 수준이다.

실제 사용 예시:

비트코인: secp256k1 (256비트)
이더리움: secp256k1 (256비트)
TLS/SSL: P-256 (256비트)

ECDLP는 일반적인 이산 로그 문제(DLP)보다 더 높은 보안 효율성을 제공한다. 예를 들어, 256비트 ECC 키는 약 3072비트 RSA 키와 동등한 보안 수준을 갖는다. 이는 더 짧은 키를 사용하면서도 높은 보안을 유지할 수 있다는 장점이 있다.

주요 타원 곡선 암호 시스템

ECDSA (Elliptic Curve Digital Signature Algorithm)

ECDSA는 타원 곡선 암호(ECC)를 기반으로 하는 디지털 서명 알고리즘이다.

키 생성 과정

타원 곡선 $E$ 와 생성원 $G$ 를 선택한다.
타원 곡선 위의 유한한 점들의 총 개수인 위수 n을 계산한다.
$1<d<n$ 범위의 정수 d를 프라이빗 키로 선택한다.
$Q=dG$ 를 계산하여 점 $Q$ 를 퍼블릭 키로 설정한다.
$(Q, E, G, n)$ 을 공개하고, d는 비공개로 보관한다.

서명 생성 알고리즘

입력: 메시지 m, 프라이빗 키 d
출력: 서명 (r,s)

메시지 m을 해시하여 $h = H(m)$ 를 계산한다.
$1<k<n$ 범위의 임의의 정수 k를 선택한다.
점 $R=kG$ 를 계산한다.
$r=R$ 의 x좌표 $\pmod {n}$ 을 계산한다.( $r=P_x \pmod{n}$ 계산)
$s=k^{−1}(h+dr) \pmod {n}$ 을 계산한다.
$r\neq0$ 이고 $s\neq0$ 인지 확인하고, 그렇지 않으면 2단계로 돌아간다.
서명 $(r, s)$ 를 반환한다.

서명 검증 알고리즘

입력: 메시지 m, 서명 (r,s), 퍼블릭 키 Q
출력: 서명의 유효성

$r$ 과 $s$ 가 $[1,n−1]$ 범위에 있는지 확인한다.
메시지 m을 해시하여 $h = H(m)$ 를 계산한다.
$w=s^{−1} \pmod{n}$ , $u_1=hw\pmod{n}$ , $u_2=rw\pmod{n}$ 을 계산한다.
점 $P=u_1G+u_2Q$ 를 계산한다.
$v=P$ 의 x좌표 $\pmod{n}$ 을 계산한다.( $x = X_x \pmod{n}$ )
$v=r$ 이면 서명이 유효하고, 아니면 무효하다.

보안 고려사항

랜덤성의 중요성: 서명 생성 시 사용되는 랜덤 정수 k가 재사용되면 프라이빗 키 d가 노출될 수 있다.

Sony PlayStation 3 사례: ECDSA 구현 시 k 값을 고정적으로 사용하여 프라이빗 키가 노출되는 보안 취약점이 발생한 사례가 있다. 이는 k의 랜덤성이 ECDSA의 보안에 얼마나 중요한지 보여준다.

package ecdsa

import (
	"errors"
	"github.com/decred/dcrd/dcrec/secp256k1/v4"
	"github.com/ffddz/upside-homework/crypto"
	"math/big"
)

var (
	order     = new(big.Int).Set(secp256k1.S256().N)
	halforder = new(big.Int).Rsh(order, 1)
	// 안전하지 않게 k를 동일한 것을 사용
	k = new(big.Int).SetUint64(0x123456789abcdef)
)

func Sign(privateKey *secp256k1.PrivateKey, hash []byte) (*big.Int, *big.Int, error) {
	privkey := privateKey.ToECDSA()
	N := order
	inv := new(big.Int).ModInverse(k, N)
	r, _ := privkey.Curve.ScalarBaseMult(k.Bytes())
	r.Mod(r, N)

	if r.Sign() == 0 {
		return nil, nil, errors.New("calculated R is zero")
	}

	e := crypto.HashToInt(hash)
	s := new(big.Int).Mul(privkey.D, r)
	s.Add(s, e)
	s.Mul(s, inv)
	s.Mod(s, N)

	// enforce low S values, see bip62
	// bip62을 반영하지 않은 ECDSA 서명을 만들기 위해 주석처리
	//if s.Cmp(halforder) == 1 {
	//	s.Sub(N, s)
	//}

	if s.Sign() == 0 {
		return nil, nil, errors.New("calculated S is zero")
	}
	return r, s, nil
}

다음과 같이 k값을 고정하였을 경우, 같은 k값을 이용한 서명 두개를 이용하여 프라이빗 키 획득할 수 있다.

package ecdsa

import (
	"math/big"

	"github.com/decred/dcrd/dcrec/secp256k1/v4"
	"github.com/ffddz/upside-homework/crypto"
)

func AttackGetPrivateKey(r1, s1, r2, s2 *big.Int, msg1, msg2 []byte) (*secp256k1.PrivateKey, error) {
	n := new(big.Int).Set(secp256k1.S256().N)
	hash1 := crypto.HashToInt(msg1)
	hash2 := crypto.HashToInt(msg2)
	t1 := new(big.Int).Mul(s2, hash1)
	t2 := new(big.Int).Mul(s1, hash2)
	t3 := new(big.Int).Sub(t1, t2)
	r_inv := new(big.Int).ModInverse(r1, n)
	t4 := new(big.Int).Sub(s1, s2)
	t4 = new(big.Int).ModInverse(t4, n)
	tp := new(big.Int).Mul(t3, r_inv)
	tp.Mul(tp, t4)
	tp.Mod(tp, n)
	var modNScalar secp256k1.ModNScalar
	modNScalar.SetByteSlice(tp.Bytes())
	p := secp256k1.NewPrivateKey(&modNScalar)

	return p, nil

}