Schnorr 서명

Schnorr 서명(슈노르 서명)은 큰 소수 p 의 곱셈군에서 p-1 의 소인수 q 를 위수로 갖는 원소를 골라 그 원소가 만드는 작은 부분군 안에서 키를 만들고 서명·검증하는, 이산대수 문제의 어려움에 기댄 전자서명 방식이다. 1989년 클라우스 슈노르(Claus-Peter Schnorr)가 제안했다.

개요

ElGamal 서명은 위수가 p-1 인 원시근을 써서 지수와 서명 값이 모두 p 크기(수천 비트)가 된다. Schnorr 는 p-1 을 나누는 소수 q(예: 256비트)를 위수로 갖는 원소 g 를 쓰면, 이산대수의 어려움은 p 크기로 유지하면서 지수 연산과 서명은 q 크기로 줄일 수 있다는 점을 이용했다. 서명이 짧고 계산이 빠르다.

미국 DSA 는 이 위수 q 부분군을 그대로 가져와 ElGamal 형태의 서명식에 붙인 것이다. Schnorr 방식에 특허가 걸려 있어(2008년 만료) 표준이 이 구조를 피해 갔다는 평이 많다.

알고리즘

키 생성

소수 p 와, p-1 을 나누는 소수 q 를 고른다
위수가 q 인 원소 g 를 구한다. 임의의 h 에 대해 g = h^(p-1)/q mod p 가 1 이 아니면 된다
개인키 x 를 1 ~ q-1 에서 고르고, 공개키 y = g^x mod p 를 공개한다

서명 (메시지 M)

난수 k 를 1 ~ q-1 에서 고르고 r = g^k mod p 를 구한다
e = H(M ∥ r) (해시)
s = (k + x·e) mod q
서명은 (e, s)

검증

r' = g^s · y^-e mod p 를 구한다
H(M ∥ r') 가 e 와 같으면 올바른 서명이다

g^s·y^-e = g^k+xe·g^-xe = g^k = r 이므로 맞는 서명이면 같은 값이 나온다.

특징

짧은 서명 : 서명 값이 q 크기 두 개다
안전성 증명 : 이산대수 문제가 어렵다는 가정과 랜덤 오라클 모형에서 위조 불가능성이 증명되어 있다
선형성 : 서명식이 일차식이라 여러 사람의 서명을 하나로 합치는 다중 서명(MuSig)과 임계 서명을 만들기 쉽다
난수 k 를 다시 쓰거나 예측할 수 있으면 개인키가 계산된다. DSA·ECDSA 도 같다

비트코인은 2021년 탭루트 업그레이드(BIP 340)에서 secp256k1 타원 곡선 위의 Schnorr 서명을 ECDSA 와 함께 쓰게 했다.

이산대수·소인수분해 기반 서명 비교

방식	어려운 문제	키·연산의 군	특징
RSA	소인수분해	n = pq 의 나머지 연산	개인키로 서명, 공개키로 검증. 서명 길이 = n 의 길이
ElGamal	이산대수	위수 p-1 인 원시근	서명이 p 크기 값 두 개라 길다
Schnorr	이산대수	p-1 의 소인수 q 를 위수로 갖는 원소	짧은 서명, 안전성 증명, 서명 합치기 쉬움
DSA	이산대수	Schnorr 와 같은 위수 q 부분군	NIST 표준(FIPS 186). ElGamal 형태의 서명식
ECDSA	타원 곡선 이산대수	타원 곡선 위의 점	DSA 를 타원 곡선으로 옮겼다. 키가 짧다

같이 보기