13장. 전자서명 (Digital Signatures)

학습 목표

• 전자서명 프로세스의 개요를 제시한다.
• Elgamal 전자서명 방식을 이해한다.
• Schnorr 전자서명 방식을 이해한다.
• NIST DSA를 이해하고 Elgamal/Schnorr와 비교한다.
• ECDSA(타원곡선 전자서명)를 이해한다.
• RSA-PSS 전자서명을 이해한다.

---

13.1 전자서명 개요

전자서명의 필요성

MAC은 두 당사자를 제3자로부터 보호하지만, 두 당사자 간의 분쟁은 해결하지 못한다:

1. 수신자 Mary가 메시지를 위조하고 송신자 John에게서 왔다고 주장할 수 있다 — 양쪽이 동일한 키를 공유하므로 Mary도 유효한 MAC을 생성 가능.
2. 송신자 John이 메시지를 보낸 사실을 부인할 수 있다 — Mary의 위조 가능성 때문에 John이 보냈다는 증거가 없다.

전자서명은 이를 해결하며 다음 속성을 가져야 한다:

• 서명자의 신원과 서명 시각을 검증 가능
• 서명 시점의 메시지 내용을 인증
• 제3자가 검증 가능 (분쟁 해결)

전자서명의 일반적 과정

1. Bob이 메시지 $M$의 해시값 $h = H(M)$을 계산 (SHA-512 등)
2. $h$와 Bob의 개인키를 서명 생성 알고리즘에 입력 → 서명 $S$ 생성
3. Bob이 $M \| S$를 전송
4. Alice가 $M$의 해시값을 재계산하고, Bob의 공개키로 서명 검증 알고리즘을 실행
5. 검증 성공 → 메시지가 Bob에 의해 서명되었고 변조되지 않았음을 확인

공격 유형 (심각도 순)

공격	설명
Key-only attack	C는 A의 공개키만 알고 있음
Known message attack	C는 메시지-서명 쌍 집합에 접근
Generic chosen message attack	A의 공개키와 무관하게 메시지 목록을 선택하고 서명을 획득
Directed chosen message attack	A의 공개키를 안 후 서명 전에 메시지를 선택
Adaptive chosen message attack	C가 A를 "오라클"로 사용 — 이전 결과에 따라 메시지 선택

위조 성공 수준

수준	설명
Total break	A의 개인키 발견
Universal forgery	임의 메시지에 서명 가능한 동등 알고리즘 발견
Selective forgery	C가 선택한 특정 메시지에 대한 서명 위조
Existential forgery	최소 하나의 메시지에 대한 서명 위조 (메시지 선택 불가)

전자서명 요구사항

• 서명은 메시지에 의존하는 비트 패턴이어야 한다.
• 서명은 송신자만 아는 정보를 사용해야 한다 (위조·부인 방지).
• 서명 생성과 검증이 비교적 쉬워야 한다.
• 서명 위조가 계산적으로 불가능해야 한다.
• 서명의 사본을 저장하는 것이 실용적이어야 한다.

직접 전자서명 (Direct Digital Signature)

통신 당사자만 관여. 수신자가 송신자의 공개키를 알고 있다고 가정한다.

서명과 암호화의 순서

기밀성이 필요하면 서명을 먼저 수행하고 그 위에 암호화를 적용해야 한다. 분쟁 해결 시 제3자가 서명을 검증하려면 평문과 서명에 접근해야 하기 때문이다.

직접 서명의 위협: 개인키 도난/분실 → 공격자가 과거 시점의 서명을 위조할 수 있다. 대응: 타임스탬프 + 인증서 폐기의 즉시 보고.

---

13.2 Elgamal 전자서명

이산대수에 기반. Elgamal 암호화(10장)는 공개키로 암호화/개인키로 복호화하는 반면, Elgamal 서명은 개인키로 서명/공개키로 검증한다.

키 생성

• 공개 파라미터: 소수 $q$, 원시근 $\alpha$
• 비밀키: 랜덤 $X_A$ ($1 < X_A < q - 1$)
• 공개키: $\{q, \alpha, Y_A\}$ 여기서 $Y_A = \alpha^{X_A} \bmod q$

서명 생성 (메시지 해시 $m = H(M)$)

1. $\gcd(K, q - 1) = 1$인 랜덤 $K$ 선택
2. $S_1 = \alpha^K \bmod q$
3. $K^{-1} \bmod (q - 1)$ 계산
4. $S_2 = K^{-1}(m - X_A \cdot S_1) \bmod (q - 1)$
5. 서명 = $(S_1, S_2)$

서명 검증

1. $V_1 = \alpha^m \bmod q$
2. $V_2 = (Y_A)^{S_1} \cdot (S_1)^{S_2} \bmod q$
3. $V_1 = V_2$이면 유효

검증이 성립하는 이유

$\alpha^m \bmod q = (Y_A)^{S_1} \cdot (S_1)^{S_2} \bmod q = \alpha^{X_A S_1} \cdot \alpha^{K S_2} \bmod q = \alpha^{X_A S_1 + K S_2} \bmod q$

원시근의 성질에 의해 $m \equiv X_A S_1 + K S_2 \pmod{q-1}$이고, $S_2$의 정의를 대입하면 $K K^{-1}(m - X_A S_1) = m - X_A S_1$이므로 등식이 성립한다.

예시 ($q = 19$, $\alpha = 10$, $X_A = 16$)

$Y_A = 10^{16} \bmod 19 = 4, \quad \text{공개키} = \{19, 10, 4\}$

해시값 $m = 14$, $K = 5$ 선택:

$S_1 = 10^5 \bmod 19 = 3, \quad K^{-1} \bmod 18 = 11$

$S_2 = 11 \cdot (14 - 16 \times 3) \bmod 18 = 11 \cdot (-34) \bmod 18 = -374 \bmod 18 = 4$

검증: $V_1 = 10^{14} \bmod 19 = 16$, $V_2 = 4^3 \cdot 3^4 \bmod 19 = 5184 \bmod 19 = 16$ → 유효

---

13.3 Schnorr 전자서명

Elgamal과 마찬가지로 이산대수 기반이지만, 메시지 의존적 계산을 최소화한다. 서명 생성의 주요 계산($x = \alpha^r \bmod p$)이 메시지에 무관하므로 프로세서 유휴 시간에 사전 계산 가능하다.

파라미터

• 소수 $p \approx 2^{1024}$, $q \approx 2^{160}$ ($q | (p - 1)$)
• $\alpha$: $\alpha^q \equiv 1 \pmod{p}$
• 비밀키 $s$ ($0 < s < q$), 공개키 $v = \alpha^{-s} \bmod p$

서명 생성

1. 랜덤 $r$ ($0 < r < q$), $x = \alpha^r \bmod p$ 계산 (사전 계산 가능)
2. $e = H(M \| x)$
3. $y = (r + s \cdot e) \bmod q$
4. 서명 = $(e, y)$

서명 검증

1. $x' = \alpha^y \cdot v^e \bmod p$
2. $e = H(M \| x')$인지 확인

$x' \equiv \alpha^y \cdot v^e \equiv \alpha^y \cdot \alpha^{-se} \equiv \alpha^{y - se} \equiv \alpha^r \equiv x \pmod{p}$

따라서 $H(M \| x') = H(M \| x) = e$.

---

13.4 NIST DSA (Digital Signature Algorithm)

FIPS 186 표준 (최신: FIPS 186-4, 2013). DSA는 서명 전용 알고리즘으로, RSA와 달리 암호화나 키 교환에 사용할 수 없다. Elgamal과 Schnorr 방식에 기반한다.

DSA vs RSA 서명 접근법의 차이

구분	RSA 접근법	DSA 접근법
서명 생성	$H(M)$을 개인키로 암호화	$H(M)$과 랜덤 $k$를 서명 함수에 입력
서명 검증	공개키로 복호화하여 해시값 비교	검증 함수 출력을 서명 성분 $r$과 비교
서명 형태	단일 값	쌍 $(r, s)$

DSA 파라미터

파라미터	설명
$p$	소수, 512~1024비트 (64비트 단위)
$q$	$(p - 1)$의 소인수, $N$비트
$g$	$g = h^{(p-1)/q} \bmod p$, $g > 1$
$x$ (비밀)	랜덤, $0 < x < q$
$y$ (공개)	$y = g^x \bmod p$
$k$ (메시지별)	랜덤, $0 < k < q$

서명 생성

$r = (g^k \bmod p) \bmod q$

$s = [k^{-1}(H(M) + x \cdot r)] \bmod q$

서명 = $(r, s)$

서명 검증

$w = (s')^{-1} \bmod q$

$u_1 = [H(M') \cdot w] \bmod q, \quad u_2 = r' \cdot w \bmod q$

$v = [(g^{u_1} \cdot y^{u_2}) \bmod p] \bmod q$

$v = r'$이면 유효

DSA의 특징

$r$은 메시지에 무관하고 $k$와 공개 파라미터만의 함수이므로, $g^k \bmod p$를 사전 계산 가능하다. 서명 생성에서 계산 집약적인 부분은 지수 연산뿐이며, $k^{-1}$도 사전 계산할 수 있다.

---

13.5 ECDSA (Elliptic Curve Digital Signature Algorithm)

FIPS 186에 포함. 타원곡선 암호의 **효율성(작은 키 크기)**을 전자서명에 활용한다.

글로벌 도메인 파라미터

• 소수 $q$, 타원곡선 파라미터 $a$, $b$ ($y^2 = x^3 + ax + b$ over $\mathbb{Z}_q$)
• 베이스 포인트 $G = (x_g, y_g)$, $G$의 위수 $n$

키 생성

• 비밀키: 랜덤 $d \in [1, n - 1]$
• 공개키: $Q = d \cdot G$ (타원곡선 위의 점)

서명 생성

1. 랜덤 $k \in [1, n - 1]$
2. $P = kG = (x, y)$, $r = x \bmod n$. $r = 0$이면 1로 복귀
3. $e = H(m)$
4. $s = k^{-1}(e + d \cdot r) \bmod n$. $s = 0$이면 1로 복귀
5. 서명 = $(r, s)$

서명 검증

1. $r$, $s$가 $[1, n - 1]$ 범위인지 확인
2. $e = H(m)$
3. $w = s^{-1} \bmod n$
4. $u_1 = e \cdot w$, $u_2 = r \cdot w$
5. $X = u_1 G + u_2 Q = (x_1, y_1)$
6. $v = x_1 \bmod n$
7. $v = r$이면 유효

검증이 성립하는 이유

$s = k^{-1}(e + dr) \;\Rightarrow\; k = s^{-1}(e + dr) = we + wdr = u_1 + u_2 d$

$u_1 G + u_2 Q = u_1 G + u_2 dG = (u_1 + u_2 d)G = kG$

따라서 $v = x_1 \bmod n$은 $kG$의 $x$ 좌표 $\bmod n = r$과 동일하다.

---

13.6 RSA-PSS (Probabilistic Signature Scheme)

RSA 기반 서명 중 가장 최신이며 가장 안전한 방식. RSA Laboratories가 권장한다. 이전 RSA 서명 방식들과 달리, 서명 방식의 보안이 RSA 알고리즘 자체의 보안에 수학적으로 귀결됨을 증명 가능하다.

핵심 특징: 랜덤 솔트 (Salt)

동일 메시지를 같은 키로 두 번 서명해도 다른 서명이 생성된다 — DSA/ECDSA에서 랜덤 $k$가 하는 역할과 동일.

MGF (Mask Generation Function)

$\text{MGF1}(X, \text{maskLen}) = H(X \| 0) \| H(X \| 1) \| \cdots \| H(X \| k)$

해시 함수를 반복 적용하여 가변 길이 의사난수 마스크를 생성. 출력 길이가 $\text{maskLen}$에 도달하면 절단.

EM 인코딩 (서명 생성 — 1단계)

1. $\text{mHash} = H(M)$
2. 랜덤 솔트 생성, $M' = \text{padding1} \| \text{mHash} \| \text{salt}$
3. $\mathcal{H} = H(M')$
4. $DB = \text{padding2} \| \text{salt}$
5. $\text{dbMask} = \text{MGF}(\mathcal{H},\; \text{emLen} - \text{hLen} - 1)$
6. $\text{maskedDB} = DB \oplus \text{dbMask}$
7. $EM = \text{maskedDB} \| \mathcal{H} \| \texttt{0xBC}$

여기서 padding1 = $0^{64}$ (64 제로 비트), padding2 = 적절한 수의 0x00 바이트 + 0x01.

서명 생성 (2단계)

$EM$을 정수 $m$으로 취급한 뒤, 개인키 $\{d, n\}$으로 암호화:

$s = m^d \bmod n$

서명 검증

1. 복호화: $m = s^e \bmod n$ → $EM$ 복원
2. EM 분해: $\text{maskedDB}$와 $\mathcal{H}$ 분리
3. 마지막 바이트가 0xBC인지 확인
4. $\text{dbMask} = \text{MGF}(\mathcal{H},\; \text{emLen} - \text{hLen} - 1)$
5. $DB = \text{maskedDB} \oplus \text{dbMask}$
6. $DB$에서 padding2가 올바른지 확인
7. $DB$의 마지막 $\text{sLen}$ 바이트에서 salt 추출
8. $M' = \text{padding1} \| \text{mHash} \| \text{salt}$ → $\mathcal{H}' = H(M')$
9. $\mathcal{H} = \mathcal{H}'$이면 유효

검증 시 세 가지 검사

1. 상수 검사: 0xBC 확인, padding2 확인 → 구조적 무결성
2. 해시 비교: $\mathcal{H} = \mathcal{H}'$ → 메시지 무결성 + 서명 진정성
3. 솔트: 검증자는 솔트 값을 모르며 비교하지 않음. 솔트는 매번 다른 서명을 생성하기 위한 것

상수는 위조를 어렵게 하고, 솔트는 동일 메시지에 대한 서명의 고유성을 보장한다.

---

핵심 용어 정리

한글	영문
전자서명	digital signature
전자서명 알고리즘	Digital Signature Algorithm (DSA)
직접 전자서명	direct digital signature
Elgamal 전자서명	Elgamal digital signature
타원곡선 전자서명	Elliptic Curve Digital Signature Algorithm (ECDSA)
마스크 생성 함수	mask generation function (MGF)
확률적 서명 방식	RSA Probabilistic Signature Scheme (RSA-PSS)
Schnorr 전자서명	Schnorr digital signature
타임스탬프	timestamp