타원곡선 모양 예시
타원곡선 모양 예시
\Delta = -16(4a^3+27b^2)
이 0이 되지 않도록(특이점이 없도록) 계수 $$a, b$$를 선택한다. ### 타원 곡선 상의 군 구조 타원 곡선 암호에서 우리가 사용하는 건 곡선 그 자체가 아니라, **곡선 위의 점들 + 점 덧셈 연산**으로 이루어진 아벨군 구조이다. #### **아벨군으로서의 타원곡선** 유한체 $$\mathbb{F}\_p$$ 위의 타원 곡선 $$E$$에 대해 곡선 위의 모든 점 $$(x, y) \in \mathbb{F^2}\_p$$, 무한대점 $$O$$를 모두 모아 $$E(\mathbb{F}\_p)$$를 만들고, 여기에 점 덧셈이라는 연산을 정의하면, 이는 아벨군이 된다. 군이라는 말은 집합 $$E(\mathbb{F}\_p)$$위의 두 점 $$P, Q$$ 가 다음 조건들을 만족한다는 의미이다. * **결합법칙**: $$(P + Q) + R = P + (Q + R)$$ * **교환법칙**: $$P + Q = Q + P$$ * **항등원**: 무한대점 $$O$$에 대해 $$P + O = O + P = P$$ * **역원**: 점 $$P = (x, y)$$에 대해 $$-P = (x, -y)$$가 존재하여 $$P + (-P) = O$$ * **닫혀있음**: $$P +Q$$도 집합 $$E(\mathbb{F}\_p)$$ 에 원소여야 한다. 이러한 구조 덕분에, 타원 곡선 위의 점들을 벡터처럼 더하고 빼고, 정수 배를 취하는 연산을 정의할 수 있다. #### 점의 덧셈 연산 타원 곡선 위에서 두 점 $$P, Q$$를 더한다는 건, 아래 규칙으로 새로운 점 $$R = P + Q$$를 만드는 것이다. * $$P ≠ Q$$**인 경우 (서로 다른 두 점의 덧셈)** * $$P$$와 $$Q$$를 잇는 직선을 그린다. * 그 직선이 곡선과 다시 만나는 점을 찾고, 그 점을 $$x$$축에 대해 대칭시킨 점을 $$R$$이라고 정의한다. * $$P = Q$$**인 경우 (점의 배가)** * $$P$$에서 곡선의 접선을 그린다. * 그 접선이 곡선과 다시 만나는 점을 찾고. 마찬가지로 $$x$$축에 대해 대칭시킨 점을 $$2P$$라고 정의한다. 수식으로 쓰면 다음과 같다. * $$P = (x\_1, y\_1), Q = (x\_2, y\_2), p \neq Q$$ 일 때,m = \frac{y_2 - y_1}{x_2 - x_1}, x_R = m^2 - x_1 - x_2, y_R = m(x_1 - x_R) - y_1
* $$P = Q$$ 일 때m = \frac{3x_P^2 + a}{2y_P}, x_R = m² - 2x_1, y_R = m(x_1 - x_2) - y_2
이렇게 정의된 덧셈 연산이 위에서 말한 군의 성질을 만족하도록 설계되어 있다. ### 스칼라 곱셈 및 ECDLP 가정 #### 스칼라 곱셈의 정의 스칼라 곱셈은 아래와 같이 점 $$P$$를 $$k$$번 더한 결과로 정의된다. $$ k \cdot P = \underbrace{P + P + \dots + P}\_{k\text{번}} $$ $$ -P = (Px, -Py) $$ ECC/ECDLP, 그리고 ZKP에서 쓰이는 기본 패턴은 다음과 같다. * 곡선 위의 고정된 생성점 $$G$$를 정의 * 비밀 정수 $$d$$(개인키)를 선택 * 점 $$Q = dG$$를 계산해서 공개키 계산 $$ Q = d \cdot G = \underbrace{G + G + \dots + G}\_{d\text{번}} $$ 여기서 핵심 가정은 $$G$$와 $$Q = dG$$는 알고 있지만, "몇 번 더해야 $$Q$$가 되는지"에 대한 답인 $$d$$를 구하는 건 현실적으로 불가능하다는 것이며, 이 가정이 ECDLP(Elliptic Curve Discrete Log Problem) 가정이다. 여기서 중요한 건, 현실적인 파라미터에서는 이 문제가 "사실상 풀 수 없다"는 점이다. 예를 들어 비트코인, 이더리움에서 쓰는 secp256k1(256bit) 수준이면, 현재 알려진 최선의 공격도 대략 $$2^{128}$$ 정도의 복잡도를 가져서 실질적으로 불가능하다고 본다. 이러한 ECDLP의 난이도 덕분에, ECC 위에서 정의된 서명(ECDSA)과 키 교환(ECDH), 그리고 zk-SNARK에서의 스칼라 곱셈, 페어링 기반 구성도 안전한 블록으로 취급할 수 있게 된다. ### ECDSA / ECDH 프로토콜 #### ECDSA (Elliptic Curve Digital Signature Algorithm) ECDSA는 "어떤 메시지를 내가 보냈다"는 부인 불가능한 증거를, 타원 곡선 위에서 만드는 서명 알고리즘이다. 구조 자체는 다음과 같다. * **키 생성**: 공개키 $$Q$$는 여전히 $$Q = dG$$ 꼴이다. * **서명**: 메시지 해시 $$h$$와 비밀키 $$d$$를 가지고 $$(r, s)$$라는 두 개의 정수를 만든다. * **검증**: 공개키 $$Q$$, 메시지 $$m$$, 서명 $$(r, s)$$만으로 "$$d$$를 아는 사람이 만든 값"인지를 확인한다. **키 생성** * 타원 곡선 $$E$$와 생성원 $$G$$ 선택 * 타원 곡선의 위수(타원곡선 위의 유한한 점들의 총 개수) $$n$$ 계산 * 개인 키 $$d$$ 선택 $$(1 < d < n)$$ * 공개 키 $$Q = dG$$ 계산 $$(Q, E, G, n)$$을 공개, $$d$$를 비공개로 보관 **서명 생성** Input: 메시지 $$m$$, 프라이빗 키 $$d$$ * 해시 함수 $$H$$를 사용하여 $$h = H(m)$$ 계산 * 랜덤 정수 $$k$$ 선택 $$(1 < k < n)$$ * 점 $$R = kG$$ 계산 * $$r = R$$의 $$x$$좌표 $$(mod$$ $$n)$$ * $$s = k⁻¹(h + dr)$$ $$(mod$$ $$n)$$ * $$r ≠ 0$$이고 $$s ≠ 0$$인지 확인 서명 $$(r, s)$$ 반환 **서명 검증** Input: 메시지 $$m$$, 서명 $$(r, s)$$, 공개 키 $$Q$$ * $$(r, s)$$가 $$\[1, n-1]$$ 범위에 있는지 확인 * 해시 함수 $$H$$를 사용하여 $$h = H(m)$$ 계산 * $$w = s⁻¹$$ $$(mod$$ $$n)$$ 계산 * $$u₁ = hw$$ $$(mod$$ $$n)$$ 계산 * $$u₂ = rw$$ $$(mod$$ $$n)$$ 계산 * 점 $$P = u₁G + u₂Q$$ 계산 * $$v = P$$의 $$x$$좌표 $$(mod$$ $$n)$$ 계산 * $$v = r$$이면 서명 유효, 아니면 무효 핵심은 검증자가 보는건 오직 $$G, Q, r, s, h$$ 뿐인데, 이 값들 사이의 관계가 $$d$$"$$d$$를 알고 있는 사람만 만들 수 있는 구조"이면서 $$d$$ 자체는 노출되지 않도록 설계되어 있다는 점이다. 여기서도 역시 스칼라 곱셈과 덧셈이 쓰이고, 안전성은 전부 ECDLP 가정위에 존재한다. **보안 고려사항 - 랜덤성의 중요성** ECDSA에서는 서명마다 새로운 난수 $$k$$를 사용해야 한다. 만약 같은 $$k$$를 두 번 재사용할 경우, 두 서명 $$(r, s\_1), (r, s\_2)$$와 메시지 해시만으로 비밀 키 $$d$$를 역산할 수 있다. 실제로 Sony PlayStation 3의 ECDSA 구현에서 이 문제가 발생해, 잘못된 난수 사용으로 서명 키가 노출된 사례가 있다. #### ECDH (Elliptic Curve Diffie-Hellman) ECDH는 타원 곡선 위의 스칼라 곱셈을 기반으로, 공개된 네트워크 상에서 서로 비밀값을 직접 주고 받지 않고도, 동일한 공유 키를 합의해서 만들어내는 키 교환 프로토콜이다. ECDH의 아이디어는 다음과 같다. * 서로 각자 자기만 아는 스칼라 값 선택 * 상대방에게 그 스칼라를 곱한 점을 공개 * 이후 서로의 점에 다시 자신의 스칼라 값을 한 번 더 곱해서 같은 점 공유 **키 교환 과정** * Alice * 개인 키 $$a$$ 선택 $$1 < a < n$$ * 공개 키 $$A = aG$$ 계산 * $$A$$를 Bob에게 전송 * Bob * 개인 키 $$b$$ 선택 $$1 < b < n$$ * 공개 키 $$B = bG$$ 계산 * $$B$$를 Alice에게 전송 Alice의 공유 키 계산 $$ K\_A = aB = a(bG) = (ab)G $$ Bob도 공유키 계산 $$ K\_B = bA = b(aG) = (ab)G $$ 따라서 $$K\_A = K\_B = K$$가 되고, 점 $$K$$를 대칭키 암호의 키로 사용한다. 공격자는 네트워크 상에서 $$G, A, B$$는 모두 볼 수 있지만, $$A$$에서 $$a$$를, $$B$$에서 $$b$$를 구하기 위해 ECDLP를 풀어야하고 이는 현재 알려진 방법으로 현실적인 파라미터에서 불가능하다고 여겨진다. 결과적으로 ECDH는 메시지 내용을 직접 암호화하는 프로토콜이라기 보다, 이후 실제 통신을 보호할 대칭 키를 안전하게 합의하기 위한 준비 단계에 가깝다. 타원 곡선 위에서 이런 키 합의를 구현한 덕분에 여러 보안 프로토콜에서 기본 빌딩 블록으로 많이 사용된다. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://upsidezkp.gitbook.io/upside-zkp-docs/step-0/prerequisite/ecc.md?ask=