Schnorr 서명

작성자

익명

작성일

2026.08.09

조회수

버전

Schnorr 서명 디지털 서명 이산 로그 문제 타원 곡선 암호 서명 집계 BIP340 비트코인 Taproot 암호학 중급

Schnorr 서명 (Schnorr Signature)

1. 개요

Schnorr 서명은 클라우스 슈노어(Claus Schnorr)가 1989년에 제안한 디지털 서명 알고리즘으로, 이산 로그 문제의 난해함에 기반하여 메시지의 무결성과 송신자의 신원을 증명하는 암호화 방식이다.

디지털 서명은 전자 문서에 서명자의 고유한 표식을 남겨 위변조를 방지하는 기술이다. Schnorr 서명은 기존의 ECDSA(Elliptic Curve Digital Signature Algorithm)와 비교하여 수학적 구조가 단순하며, 특히 선형성(Linearity)이라는 특성을 가지고 있어 여러 개의 서명을 하나로 합치는 서명 집계(Aggregation)가 가능하다는 강력한 장점을 가진다.

2. 작동 원리 및 수학적 배경

Schnorr 서명은 이산 로그 문제(Discrete Logarithm Problem, DLP)를 기반으로 한다. 이는 $g^x = y$일 때, $g$와 $y$를 알고 있어도 $x$를 찾는 것이 계산적으로 매우 어렵다는 원리를 이용한다.

2.1. 기본 설정

$G$: 타원 곡선의 생성자(Generator)
$n$: 곡선의 위수(Order)
$d$: 서명자의 개인키 (임의의 정수)
$P = dG$: 서명자의 공개키 (타원 곡선 상의 점)

2.2. 서명 생성 및 검증 절차

서명 생성 과정

임시 키 생성: 서명자는 무작위 수 $k$ (nonce)를 선택하고, $R = kG$를 계산한다.
챌린지 계산: 메시지 $m$과 $R$, 공개키 $P$를 해시 함수 $H$에 넣어 챌린지 값 $e$를 생성한다.
$e = H(R || P || m)$
여기서 $R$은 일반적으로 $R$의 $x$좌표를 의미하며, $||$는 데이터의 연결(Concatenation)을 의미한다.
서명 값 계산: 개인키 $d$를 사용하여 서명 값 $s$를 계산한다.
$s = k + e \cdot d \pmod n$
최종 서명: 서명 결과물은 $(R, s)$ 또는 $(e, s)$의 쌍으로 구성된다.

서명 검증 과정

검증자는 공개키 $P$, 메시지 $m$, 그리고 서명 $(R, s)$를 받아 다음 식을 확인한다. - $sG = R + eP$ - 위 식이 성립하면 서명은 유효한 것으로 간주된다. (이유: $sG = (k + ed)G = kG + e(dG) = R + eP$)

2.3. 절차 흐름도

graph TD
    A[시작: 메시지 m] --> B[임시키 k 선택 및 R=kG 계산]
    B --> C[해시값 e = H(R || P || m) 계산]
    C --> D[서명값 s = k + ed 계산]
    D --> E[서명 (R, s) 전송]
    E --> F{검증: sG == R + eP ?}
    F -- Yes --> G[서명 유효]
    F -- No --> H[서명 무효]

3. 주요 특징 및 장점

3.1. 선형성(Linearity)과 서명 집계

Schnorr 서명의 가장 큰 특징은 선형성이다. 두 서명 $(R_1, s_1)$과 $(R_2, s_2)$가 있을 때, 이들을 단순히 더함으로써 여러 명의 서명자가 참여한 하나의 통합 서명을 만들 수 있다.

수학적으로, 각 서명자가 $s_i = k_i + e \cdot d_i$를 생성했을 때, 이들의 합은 다음과 같다. $$\sum s_i = \sum k_i + e \cdot (\sum d_i)$$ 이는 합산된 임시 키 $\sum R_i$와 합산된 공개키 $\sum P_i$에 대해 유효한 단일 서명이 됨을 의미한다. 이를 통해 데이터 크기를 획기적으로 줄이고 검증 속도를 높인다.

3.2. 배치 검증 (Batch Verification)

선형성 덕분에 여러 개의 서명을 개별적으로 검증하는 대신, 한 번에 묶어서 검증하는 배치 검증이 가능하다. 검증자는 각 서명에 무작위 가중치 $z_i$를 곱하여 다음과 같은 단일 식을 확인한다. $$\left(\sum z_i s_i\right)G = \sum z_i R_i + \sum (z_i e_i) P_i$$ 이 방식은 개별 검증 시 반복되는 타원 곡선 점 곱셈(Point Multiplication) 횟수를 줄여 전체 검증 시간을 크게 단축시킨다.

3.3. 보안성 증명

Schnorr 서명은 랜덤 오라클 모델(Random Oracle Model) 하에서 포지(Forge) 불가능함이 수학적으로 증명되었다. 이는 적절한 해시 함수를 사용할 경우, 개인키 없이 유효한 서명을 생성하는 것이 계산적으로 불가능함을 의미한다.

3.4. ECDSA vs Schnorr 비교

비교 항목	ECDSA	Schnorr
수학적 구조	복잡함 (역원 계산 필요)	단순함 (선형 결합)
서명 집계	불가능	가능 (Aggregation)
검증 속도	상대적으로 느림	빠름 (배치 검증 가능)
보안성 증명	표준 모델에서 증명 어려움	랜덤 오라클 모델에서 증명됨
결정론적 서명	RFC 6979 등으로 구현 가능	기본 구조에서 구현 용이

4. 고급 활용 사례

4.1. 다중 서명 (MuSig)

MuSig는 여러 참여자가 각자의 공개키를 합쳐 하나의 '공통 공개키'를 만들고, 공동으로 서명하는 방식이다. 외부 관찰자는 이것이 단일 서명인지, 수십 명이 합의한 다중 서명인지 구분할 수 없어 프라이버시가 강화되며, 블록체인 상의 저장 공간을 절약한다.

4.2. 적응형 서명 (Adaptor Signatures)

서명 값에 특정 오프셋을 추가하여, 서명을 공개하는 행위 자체가 특정 비밀 정보(Secret)를 유출하게 만드는 방식이다. 이는 원자적 스왑(Atomic Swaps)이나 라이트닝 네트워크의 채널 닫기 등에 활용되어 신뢰 없는 교환을 가능하게 한다.

5. 보안 취약점 및 공격 사례

Schnorr 서명 자체는 견고하지만, 구현 단계에서 치명적인 취약점이 발생할 수 있다.

Nonce 재사용 공격 (Nonce Reuse Attack):
동일한 임시 키 $k$를 사용하여 서로 다른 두 메시지 $m_1, m_2$에 서명할 경우, 공격자는 두 서명 값 $s_1, s_2$의 차이를 통해 개인키 $d$를 즉시 계산할 수 있다.
수식 예시: $s_1 = k + e_1 d \pmod n$ $s_2 = k + e_2 d \pmod n$ $s_1 - s_2 = (e_1 - e_2)d \pmod n$ $\implies d = (s_1 - s_2)(e_1 - e_2)^{-1} \pmod n$ (여기서 $(e_1 - e_2)^{-1}$은 모듈로 역원 연산을 의미한다.)
편향된 Nonce (Biased Nonce):
$k$가 완전히 무작위가 아니거나 특정 비트가 고정되어 있을 경우, 격자 기반 공격(Lattice-based attack)을 통해 개인키가 노출될 위험이 있다.

6. 구현 예시 및 표준

6.1. BIP340 표준 (Bitcoin Schnorr Signatures)

비트코인의 Taproot 업데이트에 도입된 BIP340은 Schnorr 서명을 비트코인 네트워크에 맞게 최적화한 표준이다.

결정론적 Nonce: Nonce 재사용 공격을 방지하기 위해 $k = H(d || m)$ 방식으로 Nonce를 생성한다. (실제로는 개인키와 메시지뿐만 아니라 공개키 등을 조합하여 생성)
X-only 공개키: 타원 곡선 점의 $y$ 좌표를 생략하고 $x$ 좌표만 사용하여 공개키 크기를 33바이트에서 32바이트로 줄였다.
정규화(Normalization): 공개키 $P$의 $y$ 좌표가 짝수여야 한다는 제약을 두어, $x$ 좌표만으로도 $y$ 좌표를 유일하게 결정할 수 있게 하여 모호성을 제거했다.
서명 형식: 서명은 $(r, s)$ 형태로 구성되며, $r$은 $R$의 $x$좌표이다.

6.2. 의사코드 (Pseudocode)

# Schnorr Signature Simplified Implementation
import hashlib

def schnorr_sign(private_key, message, G, n):
    # 0. 공개키 계산
    public_key = private_key * G
    
    # 1. Deterministic Nonce generation (BIP340 style)
    # 실제로는 더 복잡한 해시 조합을 사용함
    k = int(hashlib.sha256(str(private_key + message).encode()).hexdigest(), 16) % n
    R = k * G
    
    # 2. Challenge calculation
    # R.x는 R의 x좌표를 의미함
    e = int(hashlib.sha256(str(R.x + public_key + message).encode()).hexdigest(), 16) % n
    
    # 3. Signature value
    s = (k + e * private_key) % n
    return (R, s)

def schnorr_verify(public_key, message, signature, G, n):
    R, s = signature
    e = int(hashlib.sha256(str(R.x + public_key + message).encode()).hexdigest(), 16) % n
    
    # Verification: sG == R + eP
    return (s * G) == (R + e * public_key)

6.3. 실제 적용 사례

Bitcoin Taproot: BIP340을 통해 다중 서명 효율성을 높이고, 복잡한 스마트 컨트랙트 스크립트를 단일 서명처럼 보이게 하여 프라이버시를 향상시켰다.
Polkadot/Substrate: 네트워크의 기본 서명 체계로 Schnorr 기반의 알고리즘을 채택하여 확장성을 확보했다.

📝 마크다운 원본

이 문서의 마크다운 원본 내용입니다.

# Schnorr 서명 (Schnorr Signature)

## 1. 개요
**Schnorr 서명**은 클라우스 슈노어(Claus Schnorr)가 1989년에 제안한 디지털 서명 알고리즘으로, 이산 로그 문제의 난해함에 기반하여 메시지의 무결성과 송신자의 신원을 증명하는 암호화 방식이다. 

디지털 서명은 전자 문서에 서명자의 고유한 표식을 남겨 위변조를 방지하는 기술이다. Schnorr 서명은 기존의 ECDSA(Elliptic Curve Digital Signature Algorithm)와 비교하여 수학적 구조가 단순하며, 특히 **선형성(Linearity)**이라는 특성을 가지고 있어 여러 개의 서명을 하나로 합치는 서명 집계(Aggregation)가 가능하다는 강력한 장점을 가진다.

---

## 2. 작동 원리 및 수학적 배경

Schnorr 서명은 **이산 로그 문제(Discrete Logarithm Problem, DLP)**를 기반으로 한다. 이는 $g^x = y$일 때, $g$와 $y$를 알고 있어도 $x$를 찾는 것이 계산적으로 매우 어렵다는 원리를 이용한다.

### 2.1. 기본 설정
- $G$: 타원 곡선의 생성자(Generator)
- $n$: 곡선의 위수(Order)
- $d$: 서명자의 개인키 (임의의 정수)
- $P = dG$: 서명자의 공개키 (타원 곡선 상의 점)

### 2.2. 서명 생성 및 검증 절차

#### 서명 생성 과정
1. **임시 키 생성**: 서명자는 무작위 수 $k$ (nonce)를 선택하고, $R = kG$를 계산한다.
2. **챌린지 계산**: 메시지 $m$과 $R$, 공개키 $P$를 해시 함수 $H$에 넣어 챌린지 값 $e$를 생성한다.
   - $e = H(R || P || m)$
   - 여기서 $R$은 일반적으로 $R$의 $x$좌표를 의미하며, $||$는 데이터의 연결(Concatenation)을 의미한다.
3. **서명 값 계산**: 개인키 $d$를 사용하여 서명 값 $s$를 계산한다.
   - $s = k + e \cdot d \pmod n$
4. **최종 서명**: 서명 결과물은 $(R, s)$ 또는 $(e, s)$의 쌍으로 구성된다.

#### 서명 검증 과정
검증자는 공개키 $P$, 메시지 $m$, 그리고 서명 $(R, s)$를 받아 다음 식을 확인한다.
- $sG = R + eP$
- 위 식이 성립하면 서명은 유효한 것으로 간주된다. (이유: $sG = (k + ed)G = kG + e(dG) = R + eP$)

### 2.3. 절차 흐름도
```mermaid
graph TD
    A[시작: 메시지 m] --> B[임시키 k 선택 및 R=kG 계산]
    B --> C[해시값 e = H(R || P || m) 계산]
    C --> D[서명값 s = k + ed 계산]
    D --> E[서명 (R, s) 전송]
    E --> F{검증: sG == R + eP ?}
    F -- Yes --> G[서명 유효]
    F -- No --> H[서명 무효]
```

---

## 3. 주요 특징 및 장점

### 3.1. 선형성(Linearity)과 서명 집계
Schnorr 서명의 가장 큰 특징은 **선형성**이다. 두 서명 $(R_1, s_1)$과 $(R_2, s_2)$가 있을 때, 이들을 단순히 더함으로써 여러 명의 서명자가 참여한 하나의 통합 서명을 만들 수 있다.

수학적으로, 각 서명자가 $s_i = k_i + e \cdot d_i$를 생성했을 때, 이들의 합은 다음과 같다.
$$\sum s_i = \sum k_i + e \cdot (\sum d_i)$$
이는 합산된 임시 키 $\sum R_i$와 합산된 공개키 $\sum P_i$에 대해 유효한 단일 서명이 됨을 의미한다. 이를 통해 데이터 크기를 획기적으로 줄이고 검증 속도를 높인다.

### 3.2. 배치 검증 (Batch Verification)
선형성 덕분에 여러 개의 서명을 개별적으로 검증하는 대신, 한 번에 묶어서 검증하는 **배치 검증**이 가능하다. 
검증자는 각 서명에 무작위 가중치 $z_i$를 곱하여 다음과 같은 단일 식을 확인한다.
$$\left(\sum z_i s_i\right)G = \sum z_i R_i + \sum (z_i e_i) P_i$$
이 방식은 개별 검증 시 반복되는 타원 곡선 점 곱셈(Point Multiplication) 횟수를 줄여 전체 검증 시간을 크게 단축시킨다.

### 3.3. 보안성 증명
Schnorr 서명은 **랜덤 오라클 모델(Random Oracle Model)** 하에서 포지(Forge) 불가능함이 수학적으로 증명되었다. 이는 적절한 해시 함수를 사용할 경우, 개인키 없이 유효한 서명을 생성하는 것이 계산적으로 불가능함을 의미한다.

### 3.4. ECDSA vs Schnorr 비교

| 비교 항목 | ECDSA | Schnorr |
| :--- | :--- | :--- |
| **수학적 구조** | 복잡함 (역원 계산 필요) | 단순함 (선형 결합) |
| **서명 집계** | 불가능 | 가능 (Aggregation) |
| **검증 속도** | 상대적으로 느림 | 빠름 (배치 검증 가능) |
| **보안성 증명** | 표준 모델에서 증명 어려움 | 랜덤 오라클 모델에서 증명됨 |
| **결정론적 서명** | RFC 6979 등으로 구현 가능 | 기본 구조에서 구현 용이 |

---

## 4. 고급 활용 사례

### 4.1. 다중 서명 (MuSig)
MuSig는 여러 참여자가 각자의 공개키를 합쳐 하나의 '공통 공개키'를 만들고, 공동으로 서명하는 방식이다. 외부 관찰자는 이것이 단일 서명인지, 수십 명이 합의한 다중 서명인지 구분할 수 없어 **프라이버시가 강화**되며, 블록체인 상의 저장 공간을 절약한다.

### 4.2. 적응형 서명 (Adaptor Signatures)
서명 값에 특정 오프셋을 추가하여, 서명을 공개하는 행위 자체가 특정 비밀 정보(Secret)를 유출하게 만드는 방식이다. 이는 원자적 스왑(Atomic Swaps)이나 라이트닝 네트워크의 채널 닫기 등에 활용되어 신뢰 없는 교환을 가능하게 한다.

---

## 5. 보안 취약점 및 공격 사례

Schnorr 서명 자체는 견고하지만, 구현 단계에서 치명적인 취약점이 발생할 수 있다.

1. **Nonce 재사용 공격 (Nonce Reuse Attack)**:
   - 동일한 임시 키 $k$를 사용하여 서로 다른 두 메시지 $m_1, m_2$에 서명할 경우, 공격자는 두 서명 값 $s_1, s_2$의 차이를 통해 개인키 $d$를 즉시 계산할 수 있다.
   - **수식 예시**:
     $s_1 = k + e_1 d \pmod n$
     $s_2 = k + e_2 d \pmod n$
     $s_1 - s_2 = (e_1 - e_2)d \pmod n$
     $\implies d = (s_1 - s_2)(e_1 - e_2)^{-1} \pmod n$
     (여기서 $(e_1 - e_2)^{-1}$은 모듈로 역원 연산을 의미한다.)
2. **편향된 Nonce (Biased Nonce)**:
   - $k$가 완전히 무작위가 아니거나 특정 비트가 고정되어 있을 경우, 격자 기반 공격(Lattice-based attack)을 통해 개인키가 노출될 위험이 있다.

---

## 6. 구현 예시 및 표준

### 6.1. BIP340 표준 (Bitcoin Schnorr Signatures)
비트코인의 Taproot 업데이트에 도입된 **BIP340**은 Schnorr 서명을 비트코인 네트워크에 맞게 최적화한 표준이다.

- **결정론적 Nonce**: Nonce 재사용 공격을 방지하기 위해 $k = H(d || m)$ 방식으로 Nonce를 생성한다. (실제로는 개인키와 메시지뿐만 아니라 공개키 등을 조합하여 생성)
- **X-only 공개키**: 타원 곡선 점의 $y$ 좌표를 생략하고 $x$ 좌표만 사용하여 공개키 크기를 33바이트에서 32바이트로 줄였다.
- **정규화(Normalization)**: 공개키 $P$의 $y$ 좌표가 짝수여야 한다는 제약을 두어, $x$ 좌표만으로도 $y$ 좌표를 유일하게 결정할 수 있게 하여 모호성을 제거했다.
- **서명 형식**: 서명은 $(r, s)$ 형태로 구성되며, $r$은 $R$의 $x$좌표이다.

### 6.2. 의사코드 (Pseudocode)

```python
# Schnorr Signature Simplified Implementation
import hashlib

def schnorr_sign(private_key, message, G, n):
    # 0. 공개키 계산
    public_key = private_key * G
    
    # 1. Deterministic Nonce generation (BIP340 style)
    # 실제로는 더 복잡한 해시 조합을 사용함
    k = int(hashlib.sha256(str(private_key + message).encode()).hexdigest(), 16) % n
    R = k * G
    
    # 2. Challenge calculation
    # R.x는 R의 x좌표를 의미함
    e = int(hashlib.sha256(str(R.x + public_key + message).encode()).hexdigest(), 16) % n
    
    # 3. Signature value
    s = (k + e * private_key) % n
    return (R, s)

def schnorr_verify(public_key, message, signature, G, n):
    R, s = signature
    e = int(hashlib.sha256(str(R.x + public_key + message).encode()).hexdigest(), 16) % n
    
    # Verification: sG == R + eP
    return (s * G) == (R + e * public_key)
```

### 6.3. 실제 적용 사례
- **Bitcoin Taproot**: BIP340을 통해 다중 서명 효율성을 높이고, 복잡한 스마트 컨트랙트 스크립트를 단일 서명처럼 보이게 하여 프라이버시를 향상시켰다.
- **Polkadot/Substrate**: 네트워크의 기본 서명 체계로 Schnorr 기반의 알고리즘을 채택하여 확장성을 확보했다.

AI 생성 콘텐츠 안내

이 문서는 AI 모델(gemma-4-31b)에 의해 생성된 콘텐츠입니다.

주의사항: AI가 생성한 내용은 부정확하거나 편향된 정보를 포함할 수 있습니다. 중요한 결정을 내리기 전에 반드시 신뢰할 수 있는 출처를 통해 정보를 확인하시기 바랍니다.

위키너와나