MATH-03. 타원 곡선과 순환 그룹: 암호 기술의 핵심 원리

타원 곡선 암호(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)이라는 특별한 점 하나를 반복해서 더하는 것만으로 그룹 안의 모든 점들을 만들어낼 수 있는 그룹을 의미합니다.

레고 세트를 생각해 보세요. '생성점 G'는 가장 기본이 되는 단 하나의 블록입니다. '점 덧셈'이라는 단 하나의 조립 규칙만을 반복 적용하여, 세트 안에 있는 상상 가능한 모든 복잡한 구조물(그룹 내 다른 모든 점)을 만들어내는 것과 같습니다.

G (생성점)
2G = G + G
3G = G + G + G...
kG = G + ... + G (k번 더하기)

이 kG 연산을 스칼라 곱셈(Scalar Multiplication)이라고 부릅니다.

암호학의 핵심: 타원 곡선 이산 대수 문제 (ECDLP)

순환 그룹의 특성은 암호학적으로 매우 중요한 '단방향성'을 만들어냅니다.

쉬운 문제: 정수 k와 생성점 G가 주어졌을 때, P = kG를 계산하는 것은 매우 쉽고 빠릅니다. (스칼라 곱셈)
어려운 문제: 하지만 그 역은 다릅니다. 결과점 P와 생성점 G를 보고 'P를 만들려면 G를 몇 번 더해야 하는가?' 즉, k를 찾는 것은 현대의 가장 강력한 슈퍼컴퓨터로도 우주의 나이보다 긴 시간이 걸릴 수 있는, 계산적으로 거의 불가능한 문제입니다. 이를 타원 곡선 이산 대수 문제(Elliptic Curve Discrete Logarithm Problem, ECDLP)라고 합니다.

k를 아는 것은 쉽지만, P를 보고 k를 역추적하는 것은 지극히 어렵다는 이 비대칭성이 바로 타원 곡선 암호의 안전성의 근간입니다.

3. 응용 분야: ECC와 영지식 증명

ECDLP의 강력한 단방향성은 두 가지 놀라운 응용 기술의 문을 엽니다. 첫째는 더 효율적이고 안전한 암호 통신을 가능하게 하는 '타원 곡선 암호(ECC)'이며, 둘째는 이 원리를 더욱 확장하여 비밀을 공개하지 않고도 지식을 증명하는 '영지식 증명(ZKP)'입니다.

타원 곡선 암호 (ECC)

ECC는 공개키 암호 방식의 한 종류로, 기존의 RSA 암호 방식보다 훨씬 작은 키 크기로도 동일한 수준의 보안을 제공하여 효율성이 매우 높습니다.

키 생성:

개인키 (Private Key): 아주 큰 임의의 정수 k를 선택합니다. 이것은 절대 외부에 노출되면 안 되는 나만의 비밀 값입니다.

공개키 (Public Key): P = kG를 계산합니다. 이 P 값은 누구에게나 공개해도 안전한 나의 공개키가 됩니다. P와 G를 알아도 k를 알아낼 수 없기 때문이죠 (ECDLP).

활용 (디피-헬만 키 교환 예시):

앨리스와 밥이 안전하게 비밀키를 공유하고 싶다고 가정해 봅시다.
앨리스: 개인키 a를 선택하고, 공개키 A = aG를 계산하여 밥에게 전달합니다.
밥: 개인키 b를 선택하고, 공개키 B = bG를 계산하여 앨리스에게 전달합니다.
공유 비밀키 생성:

앨리스는 밥의 공개키 B와 자신의 개인키 a를 이용해 S = aB = a(bG) = (ab)G를 계산합니다.
밥은 앨리스의 공개키 A와 자신의 개인키 b를 이용해 S = bA = b(aG) = (ab)G를 계산합니다.

둘은 중간에서 통신을 엿듣는 공격자가 A와 B를 가로채도 절대 알 수 없는, 동일한 공유 비밀키 S를 갖게 됩니다.

영지식 증명 (Zero-Knowledge Proofs, ZKP)

영지식 증명은 "자신이 무언가를 알고 있다는 사실을, 그 내용 자체는 전혀 노출하지 않으면서 상대방에게 증명하는 기술"입니다. 타원 곡선은 이 기술, 특히 zk-SNARKs에서 핵심적인 역할을 합니다.

증명의 원리: 증명하고 싶은 비밀 정보(k와 같은)를 타원 곡선 위의 점으로 변환(인코딩)하여 숨깁니다.
동형 암호 속성 활용: 타원 곡선 연산은 k₁G + k₂G = (k₁+k₂)G와 같이 스칼라 값의 덧셈이 점들의 덧셈으로 변환되는 동형(Homomorphic) 특성이 있습니다. 이를 이용하면, 실제 비밀 값을 공개하지 않고도 그 값들이 특정 관계(예: a + b = c)를 만족하는지를 곡선 위의 점들의 관계로 검증할 수 있습니다.
예시 (간략화된 슈노르 프로토콜):

증명자(Prover): 자신이 개인키 k를 알고 있음을 증명하고 싶어 합니다 (P = kG는 공개되어 있음).
1단계: 증명자는 임의의 숫자 r을 선택하고, R = rG를 계산하여 검증자에게 보냅니다.
2단계: 검증자(Verifier)는 임의의 c 값을 증명자에게 보냅니다.
3단계: 증명자는 s = r + ck를 계산하여 검증자에게 보냅니다.
4단계: 검증자는 전달받은 s를 이용해 sG를 계산하고, 이 값이 자신이 가지고 있던 R과 cP를 더한 값(R + cP)과 일치하는지 확인합니다. 이 등식이 성립하는 이유는 sG = (r + ck)G = rG + c(kG) = R + cP 이기 때문이며, 이 계산이 맞다는 것은 증명자가 올른 k를 알고 있어야만 s를 만들 수 있었다는 강력한 증거가 됩니다.
이 등식이 성립하면, 검증자는 증명자가 k를 알고 있다고 확신할 수 있습니다. 이 과정에서 k와 r은 전혀 노출되지 않습니다.

결론: 작은 키, 강력한 보안의 비밀

타원 곡선이 순환 그룹을 이룬다는 수학적 특성은 '스칼라 곱셈은 쉽지만, 그 역은 지극히 어렵다'는 ECDLP를 탄생시켰습니다. 이 강력한 단방향 함수는 더 작은 키로도 높은 보안성을 달성하게 해주어, 제한된 컴퓨팅 자원을 가진 모바일 기기나 IoT 장치에서도 효율적인 암호 통신을 가능하게 합니다. 나아가 비밀 정보를 전혀 노출하지 않고도 데이터의 유효성을 증명하는 '영지식 증명'의 문을 활짝 열어, 디지털 세상의 신뢰와 프라이버시를 한 차원 높은 수준으로 끌어올리는 혁신을 주도하고 있습니다.

천천히, 제대로

이 블로그 검색