천천히, 제대로

타원 곡선 암호(Elliptic Curve Cryptography, ECC)는 현대 디지털 보안의 핵심 기술입니다. 비트코인과 같은 암호화폐는 물론, 우리가 매일 사용하는 메시징 앱의 종단간 암호화, 웹사이트 접속에 쓰이는 HTTPS 통신 등 수많은 곳에서 데이터를 안전하게 지키고 있죠. 이 기술의 심장에는 '타원 곡선'이라는 특별한 수학적 구조와 그것이 이루는 '순환 그룹(Cyclic Group)'이라는 특성이 자리 잡고 있습니다. 1. 타원 곡선: 점들의 특별한 덧셈 규칙 타원 곡선은 특정 방정식(보통 y² = x³ + ax + b 형태)을 만족하는 점(x, y)들의 집합입니다. 이 곡선 위의 점들은 매우 독특하고 강력한 덧셈 규칙을 가지고 있습니다. 타원 곡선 위에서 두 점의 덧셈 (출처: desmos ) 점 덧셈 (P + Q = R): 곡선 위의 서로 다른 두 점 P와 Q를 지나는 직선을 긋습니다. 이 직선은 곡선과 또 다른 한 점(-R)에서 만나게 됩니다. 이 점을 x축에 대해 대칭시킨 점이 바로 R, 즉 P와 Q의 합입니다. 점 두 배 (P + P = 2P): 한 점 P에서 곡선에 접선을 긋습니다. 이 접선은 곡선과 또 다른 한 점(-R)에서 만납니다. 이 점을 x축에 대칭시킨 점 R이 P를 두 배 한 결과(2P)입니다. 이 연산에는 중요한 '무한점(Point at Infinity)'이라는 항등원(숫자 0과 같은 역할)이 존재하여, 어떤 점 P와 그 역원(-P)을 더하면 무한점이 됩니다. 이러한 덧셈 규칙 덕분에, 타원 곡선 위의 점들은 '아벨 그룹(Abelian Group)', 즉 교환법칙이 성립하는 그룹을 형성합니다. 2. 순환 그룹: 생성점 G로 모든 것을 만들다 타원 곡선 그룹의 가장 중요한 특징은 바로 순환 그룹이라는 점입니다. 순환 그룹이란? 그룹 내의 생성점(Generator, G)이라는 특별한 점 하나를 반복해서 더하는 것만으로 그룹 안의 모든 점들을 만들어낼 수 있는 그룹...

영지식 증명, 특히 zk-SNARKs와 같은 시스템에서 설정(Setup) 단계는 전체 시스템의 보안과 신뢰성을 좌우하는 가장 중요한 첫 단추입니다. 이 단계의 주된 목적은 증명 생성(Proving)과 검증(Verifying) 과정에서 공통적으로 사용될 공개된 파라미터(Public Parameters)를 생성하는 것입니다. 이 파라미터를 CRS(Common Reference String) 또는 SRS(Structured Reference String)라고 부릅니다. 설정 단계의 핵심 목표 설정 단계의 목표는 명확합니다. 증명자와 검증자가 다항식에 대한 약속(Commitment)을 만들고, 특정 지점에서의 다항식 값을 공개하지 않으면서도 그 값이 올바르다는 것을 증명하고 검증할 수 있는 '암호학적 기반'을 마련하는 것입니다. 설정 단계의 세부 과정 설정 단계는 크게 두 가지 핵심 과정으로 나눌 수 있습니다. 1. 암호학적 기본 요소 선택 먼저, 다항식 약정 스킴에 사용할 기본적인 암호학적 환경을 결정합니다. 유한체(Finite Field) 선택: 다항식의 계수와 변수가 속할 숫자 체계를 정의합니다. 보통 매우 큰 소수 p를 사용하여 Fp​와 같은 유한체를 사용합니다. 타원 곡선 그룹(Elliptic Curve Group) 선택: 약속(Commitment)을 생성하기 위해 타원 곡선 암호(ECC)를 사용합니다. 특정 타원 곡선과 그 위의 생성점(Generator Point) G를 선택합니다. 이 그룹 연산은 이산 로그 문제(Discrete Logarithm Problem)의 어려움에 기반하여 보안성을 가집니다. 2. CRS(Common Reference String) 생성 이것이 설정 단계의 가장 핵심적인 부분입니다. CRS는 비밀 값(Secret Value)으로부터 파생된 일련의 암호화된 정보이며, 한번 생성되면 증명자와 검증자 모두가 사용하게 됩니다. 비밀 값(Toxic Waste) 생성: 아무도 알아서는 안 되는 비밀 값, τ (타우)를 ...

영지식 증명(Zero-Knowledge Proof, ZKP)을 공부하다 보면 '타원곡선 페어링(Elliptic Curve Pairing)'이라는 개념을 자주 접하게 됩니다. 페어링은 타원곡선이라는 '덧셈의 세계'와 또 다른 '곱셈의 세계'를 연결하는 마법 같은 다리 역할 을 합니다. 타원곡선 암호는 덧셈 연산에 기반하는데, 많은 영지식 증명은 '곱셈 관계'의 검증을 필요로 합니다. 페어링은 바로 이 간극을 메워, 덧셈의 세계에 있는 값들을 이용해 곱셈 관계가 성립하는지를 검증할 수 있게 해줍니다. 이 덕분에 zk-SNARKs와 같은 고급 암호화 프로토콜이 가능해집니다. 이 글에서는 타원곡선 페어링이 무엇인지, 그리고 어떻게 영지식 증명에 사용되는지 쉽게 풀어 설명해 보겠습니다. 1. 페어링이란 무엇인가요? (기본 개념) 페어링은 간단히 말해, 특정 수학적 구조(타원곡선 위의 점들의 그룹)에 있는 두 개의 원소를 입력으로 받아, 다른 수학적 구조(곱셈 순환 그룹)에 있는 하나의 원소로 매핑(mapping)하는 함수입니다. 이 함수를 e 라고 표현한다면, 다음과 같이 나타낼 수 있습니다. e(P, Q) -> n 여기서 P는 그룹 $G_1$의 원소(타원곡선 위의 점), Q는 그룹 $G_2$의 원소(또 다른 타원곡선 위의 점)이며, 페어링 함수 e 는 이 둘을 곱셈 연산이 정의된 대상 그룹 $G_T$의 원소 n으로 변환합니다. 즉, 두 개의 타원곡선 위 점을 입력받아 곱셈 세계의 원소 하나를 출력하는 함수라고 생각할 수 있습니다. 이 함수가 특별한 이유는 바로 '쌍선형성(Bilinearity)'이라는 독특한 성질 때문입니다. 2. 페어링의 핵심 성질: 쌍선형성(Bilinearity) 쌍선형성은 페어링을 암호학적으로 유용하게 만드는 가장 중요한 특징입니다. 수식으로 표현하면 조금 복잡해 보이지만, 그 의미는 생각보다 직관적입니다. e(aP, bQ) = e(P, Q)^(ab) 이 수식이 의미하는...

타원 곡선 암호에서 디지털 서명은 타원 곡선 디지털 서명 알고리즘(ECDSA)을 통해 이루어집니다. 이는 메시지를 보낸 사람이 정말 본인인지(인증), 메시지가 위변조되지 않았는지(무결성), 그리고 서명한 사실을 부인할 수 없도록(부인 방지) 보장하는 기술입니다. 핵심 원리는 공개 키로는 할 수 없지만 개인 키(비밀 키)로만 쉽게 할 수 있는 수학적 연산 을 이용하는 것입니다. 즉, 개인 키 소유자만이 유효한 서명을 생성할 수 있고, 다른 사람들은 해당 개인 키와 쌍을 이루는 공개 키를 이용해 그 서명이 올바른지 검증할 수 있습니다. 앨리스가 밥에게 메시지를 서명하여 보낸다고 가정해 보겠습니다. 1. 키 생성 먼저, 앨리스는 서명과 검증에 사용할 한 쌍의 키를 생성해야 합니다. 공통 정보 공유: 서명자와 검증자는 모두 동일한 타원 곡선($E$)과 그 위의 기준점($G$)을 미리 알고 있어야 합니다. 이 정보는 공개되어 있습니다. 개인 키 ($d_A$): 앨리스는 아무도 모르는 큰 정수 $d_A$를 자신의 개인 키로 선택합니다. 공개 키 ($Q_A$): 앨리스는 기준점 $G$에 자신의 개인 키 $d_A$를 곱하여(타원 곡선 덧셈 연산) 점 $Q_A = d_A \cdot G$를 계산합니다. 이 $Q_A$가 앨리스의 공개 키이며, 모든 사람에게 공개됩니다. 핵심 보안: 공개 키 $Q_A$와 기준점 $G$를 안다고 해도 개인 키 $d_A$를 역으로 계산하는 것은 '타원 곡선 이산 대수 문제'라는 수학적 난제 때문에 사실상 불가능합니다. 2. 서명 생성 앨리스는 보내려는 메시지($m$)에 대해 다음과 같은 과정으로 서명($r, s$)을 생성합니다. 해시 계산: 메시지($m$)를 해시 함수(예: SHA-256)에 넣어 일정한 길이의 해시 값($h$)을 계산합니다. 이는 메시지의 '지문'과 같아서, 메시지가 1비트만 바뀌어도 해시 값이 완전히 달라집니다. $h = \text{hash}(m)$ 임의의 수 선택: 서명할 때마다 새로운 임의...