Schnorr 식별 체계는 영지식을 기반으로 한 인증 프로토콜입니다. 이 프로토콜은 사용자가 자신이 특정 비밀 키를 알고 있음을 증명하지만, 그 비밀 키를 제삼자 또는 검증자에게 노출하지 않습니다.
기존의 비밀번호 기반 인증 방식은 사용자가 비밀 키를 직접 공유해야 하므로, 이를 도청하거나 서버의 정보가 유출되면 비밀 키가 손쉽게 노출될 수 있습니다. 반면, Schnorr 식별 체계는 비밀 키를 직접적으로 전송하지 않으며 이산 로그에 기반한 보안을 활용합니다.
수학적 기초
군과 순환군
군은 숫자 집합과 이진 연산으로 구성된 대수적 구조입니다. 군은 다음 성질을 만족합니다.
폐쇄성
집합 내의 임의의 두 요소 a, b에 대해 연산의 결과도 집합 내에 속합니다.
\forall a, b \in S,\; a \cdot b \in S
집합 S {1, 2, 3, 4, 5, 6} 에서 임의의 요소 a와 요소 b를 곱한 값을 7으로 나눈 나머지 값을 구하는 연산의 결과는 집합 S에 속합니다.
(a \cdot b) \bmod 7\\ (2 \cdot 4) \bmod 7 = 1
결합 법칙
연산 순서가 결과에 영향을 미치지 않습니다.
\forall a, b, c \in S, \; (a \cdot b) \cdot c = a \cdot (b \cdot c)
집합 S {1, 2, 3, 4, 5, 6} 에서 임의의 요소 a와 요소 b를 곱한 값을 임의의 요소 c와 곱한 연산의 결과는 임의의 요소 b와 요소 c를 곱한 값에 임의의 요소 a를 곱한 연산의 결과와 동일합니다.
(a \cdot b) \cdot c = a \cdot (b \cdot c)\\ (2 \cdot 4)\cdot 5 = 2 \cdot (4 \cdot 5)\\ 8\cdot 5 = 2 \cdot 20 = 40
항등원
특정 항등원 e와 요소 a를 연산한 결과는 연산 전과 동일합니다.
\exists e \in S \; \text{such that} \; \forall a \in S, \; a \cdot e = a실수 집합 S에서 1은 어떤 요소와 곱하더라도 연산 결과과 이전 요소의 값과 동일하여 항등원 e의 역할을 합니다.
역원
각 요소 a에는 항등원을 만들어내는 요소가 존재합니다.
\forall a \in G,\; \exists a^{-1} \in G \text{ such that } a^{-1}a = e집합 S {1, 2, 3, 4, 5, 6}에서 임의의 요소 a에는 대응되는 특정 요소 b가 존재하며, a와 b를 곱한 값을 7으로 나눈 나머지 값을 구하는 연산 결과가 항등원인 1이 되는 관계를 보여줍니다.
( a \cdot b ) \bmod 7 = 1\\
\begin{align*}
(3 \cdot 5) \bmod 7 = 1 \quad \Rightarrow \text{then } 3^{-1} = 5\\
(2 \cdot 4) \bmod 7 = 1 \quad \Rightarrow \text{then } 2^{-1} = 4\\
(6 \cdot 6) \bmod 7 = 1 \quad \Rightarrow \text{then } 6^{-1} = 6
\end{align*}각 원소가 자신과 특정 원소를 곱했을 때 항등원인 1이 되는 관계를 보여줍니다.
순환군
순환군은 단일 생성자 g를 사용하여 집합 G의 모든 원소를 생성할 수 있는 군입니다. 집합 G의 모든 원소는 단일 생성자 g의 거듭제곱으로 표현될 수 있습니다.
차수 q는 집합 G가 가진 원소의 개수를 나타냅니다.
G = \{ {g^0, g^1, g^2, \dots, g^{q-1}} \} \bmod p집합 G {1, 2, 3, 4, 5, 6}에서 g가 5인 경우 다음과 같은 계산으로 전체 집합을 생성합니다.
\begin{aligned}
5^1 &\equiv 5 \bmod 7= 5 \\
5^2 &\equiv 25 \bmod 7 = 4, \\
5^3 &\equiv 125 \bmod 7 = 6, \\
5^4 &\equiv 625 \bmod 7 = 2, \\
5^5 &\equiv 3125 \bmod 7 = 3, \\
5^6 &\equiv 15625 \bmod 7 =1
\end{aligned}이산 로그 문제
이산 로그 문제는 암호학에서 중요한 보안 개념입니다.
g^x \bmod p =h
g는 군의 생성자이고, p는 소수입니다.
h를 계산하는 것은 상대적으로 간단하지만, h가 주어졌을 때 큰 p를 사용할 경우 x를 구하는 것은 매우 어려워집니다. 공격자가 x를 추측할 확률은 1/p에 불과하며, 이는 Schnorr 식별 체계의 안전성을 제공할 수 있습니다.
프로토콜 단계
Schnorr 식별 체계는 Commitment, Challenge, Response로 구성됩니다. 이 과정을 통해 사용자는 비밀 키를 노출하지 않고도 자신을 인증할 수 있습니다.
Commitment
사용자는 임의의 값 v를 선택하고, 이를 사용해 커밋 값 V를 계산합니다.
V = g^v \bmod p
이 V는 사용자의 비밀 키 x와 독립적이며, v가 랜덤하게 선택되므로 V만으로 x를 유추할 수 없습니다. V는 검증자에게 전송됩니다.
Challenge
검증자는 임의의 도전 값 c를 생성하고 이를 사용자에게 전송합니다. c는 인증 과정에서 사용자의 응답이 올바른지 확인하기 위해 사용합니다. c는 차수 q 안에서 무작위로 선택됩니다.
Response
사용자는 v, c, 자신의 비밀 키 x를 사용해 응답 값 b를 계산합니다.
b = v + c \cdot x \bmod q
b는 x를 암시적으로 포함하지만, 직접적으로 노출되지 않으므로 안전합니다. b는 검증자에게 전송됩니다.
최종 증명
검증자는 사용자가 전송한 V, b, c를 사용해 x를 알고 있음을 확인합니다.
g^b \stackrel{?}{=} V \cdot X^c \bmod p\\
g^b = g^{v + c \cdot x} = g^v \cdot g^{c \cdot x} = V \cdot X^c \bmod p여기서 X는 사용자의 공개 키입니다. 위 식이 성립하면, 검증자는 사용자가 비밀 키 x를 알고 있음을 확신합니다.
Fiat-Shamir Heuristic
Schnorr 식별 체계는 기본적으로 사용자와 검증자의 상호작용 방식이지만, Fiat-Shamir Heuristic을 사용하여 비상호작용 방식으로 변환할 수 있습니다. 이를 통해 검증자가 필요 없는 디지털 서명 프로토콜로 확장됩니다.
도전 값 c는 검증자가 아닌 해시 함수 H를 사용하여 생성됩니다.
c = H(g, V, X)\\ b = v + c \cdot x \bmod q\\ X = g^x \bmod p\\ V = g^v \bmod p
도전 값 c는 해시 함수의 보안성에 의존하며, c가 항상 무작위로 생성되도록 보장합니다. 이후 검증자는 사용자에게 c, b, X, V 값을 받아서 증명이 유효한지 검사합니다. 이를 통해 사용자의 검증자 간의 상호작용 없이도 Schnorr 식별 체계를 활용할 수 있습니다.
Schnorr 식별 체계의 한계
Schnorr 식별 체계는 이론적으로 매우 깔끔합니다. Commitment Challenge Response의 단순한 구성은 제로 지식 증명의 교과서적인 예로 자주 소개되며 여전히 많은 후속 프로토콜의 기초가 되기도 합니다.
그렇다면 Schnorr 식별 체계는 왜 오랫동안 실제 시스템에 채택되지 못했을까요?
위 알고리즘은 개발자인 Claus Schnorr가 특허를 가지고 있었기 때문에, 자유 소프트웨어 진영이나 표준화 기구에서 이를 자유롭게 활용할 수 없었습니다. 이 특허는 2008년에 만료되었지만, 이미 그 시점에서 시장은 RSA와 ECDSA 위주로 고착되어 있었습니다.
사용자와 서버 간의 응답 왕복이 필요한 대화형 프로토콜이라는 점에서도 그 한계가 나타납니다. 증명자와 검증자 간에 최소 3번의 메시지 교환이 필요하며, 이는 네트워크 지연이나 연결 불안정성이 있는 환경에서 인증 실패로 이어질 수 있습니다. 이는 REST API처럼 요청-응답 1회성 구조가 기본이 된 웹 환경에서는 자연스럽게 외면당할 수밖에 없습니다. 특히 모바일 환경이나 IoT 기기처럼 간헐적 연결이 발생하는 시스템에서는 대화형 특성이 사용자 경험을 저하시킬 수 있습니다. 물론 Fiat–Shamir Heuristic을 이용해 이를 비대화식 구조로 바꿀 수 있으나 해시 함수를 사용함으로 발생하는 랜덤 오라클 모델에 의존해야 합니다.
서버는 각 인증 세션마다 Challenge 값을 생성하고 저장해야 하며, 동시에 여러 클라이언트의 진행 중인 인증 요청을 추적해야 하므로 서버 내의 세션 상태 관리가 복잡해질 수 있습니다. 복잡한 세션은 기존의 Stateless 인증 방식에 비해 서버 리소스 사용량을 증가시킵니다.
또한 인증 과정을 진행하는 Challenge-Response 구조에서 도전 값 c의 관리가 제대로 이루어지지 않거나 랜덤성이 낮은 값 혹은 주기적인 형태를 보이는 값을 사용한다면, 공격자는 이전 인증 과정에서 캡처한 메시지를 공격을 위하여 재사용할 수도 있습니다. 이를 방지하기 위한 타임스탬프나 시퀀스 번호 관리와 같은 추가적인 페이로드를 필요로 합니다.
현실적인 대체 가능 영역
보안을 필요로 하는 관리자 인증 시스템에서는 대화형 프로토콜의 복잡성보다 보안성이 우선시되므로, 기존 패스워드 기반 관리자 로그인을 대체할 수 있습니다. 데이터베이스 관리자나 시스템 관리자처럼 높은 권한을 가진 사용자의 인증에서는 몇 초의 추가 지연보다 영지식 증명 기반의 강력한 인증이 더 가치가 있습니다.
배치 처리 시스템 간 인증에서는 대화형 특성이 큰 문제가 되지 않습니다. 예를 들어, 야간 배치 작업이나 정기적인 데이터 동기화 과정에서 시스템 간 인증을 할 때, 실시간 응답성보다는 인증 과정에서 비밀키가 노출되지 않는 것이 더 중요합니다.
제한된 네트워크 환경에서의 기기 인증에서도 유용합니다. 공장 내부나 폐쇄형 네트워크에서 디바이스 간 인증을 수행할 때, 안정적인 네트워크 연결이 보장되고 동시 접속자 수가 제한적이므로 세션 관리 부담이 적습니다.
Schnorr 식별 체계는 보안이 성능보다 우선시되고, 안정적인 네트워크 환경에서 제한된 수의 사용자가 인증하는 상황에서 기존 시스템을 대체할 수 있는 현실적인 선택지입니다.
대체 불가능한 영역
반면, 대규모 웹 서비스의 일반 사용자 로그인은 대체하기 어렵습니다. 수백만 명의 동시 사용자가 있는 환경에서 각 인증 세션의 상태를 관리하는 것은 현실적으로 불가능하며, 모바일 네트워크의 불안정성으로 인한 인증 실패가 빈번하게 발생할 수 있습니다.
API 인증 토큰 발급도 마찬가지로 부적합합니다. REST API는 무상태 특성을 기본으로 하므로, 대화형 인증 과정을 도입하면 API 설계 원칙과 충돌합니다. 특히 마이크로서비스 아키텍처에서는 서비스 간 빠른 인증이 필요한데, 3-Round 프로토콜은 전체 시스템 성능을 저하시킬 수 있습니다.
그렇다고 이 체계가 사라지거나 무시된 것은 아닙니다. 오히려 최근 들어 다시 주목받고 있습니다. 대표적인 예가 비트코인입니다. Taproot 업그레이드를 통해 Schnorr 서명 방식이 공식 채택되었고, 이는 프라이버시와 다중 서명의 효율성 측면에서 큰 전환점이었습니다. 또한 zk-SNARK, zk-STARK와 같은 제로 지식 구조가 점점 실용화되면서, 그 뿌리에 있는 Schnorr 계열 프로토콜도 자연스럽게 다시 조명되고 있습니다.
INAS의 블LOG에 오신 것을 환영합니다