13장-Digital Signature

Figure 13.1: 디지털 서명 절차 요약

🔹 디지털 서명의 핵심 흐름

1. 메시지 M ->  해시 함수 -> 해시값 h 생성
2. h를 개인키로 서명 -> 서명값 S
3. M과 S를 함께 전송
4. 수신자는:
   • M에서 해시값 h' 계산
   • S를 공개키로 복호화 -> h 복원
   • h == h'인지 비교하여 서명 유효성 검증

📌 요점:

• 해시 함수를 먼저 적용해서 효율성을 높이고
• 개인키는 서명에, 공개키는 검증에 사용됨

🔹 우측 박스: RSA 기반 서명 생성/검증

• 서명 생성: S = M^d mod n
• 서명 검증: M' = S^e mod n -> M' == M이면 OK

---

Figure 13.2: 디지털 서명 2가지 방식

🔹(a) RSA 방식

• 서명자 Alice
  1. 메시지 M -> 해시값 H(M) 계산
  2. 개인키 PRₐ로 H(M)을 RSA 서명 -> E(PRₐ, H(M))
  3. M과 서명을 함께 전송
• 검증자 Bob
  1. 메시지 M으로 H(M) 재계산
  2. 서명 E(PRₐ, H(M))을 공개키 PUₐ로 복호화 -> H(M)'
  3. 두 해시값이 같으면 서명 유효

🔹(b) DSA 방식 (Digital Signature Algorithm)

• RSA와 달리 서명 전용 알고리즘
• 결과는 (r, s)라는 두 값의 쌍
• 서명자 Alice
  1. 메시지 M -> H(M) 계산
  2. 임의의 수 k 사용하여 서명 생성 -> Sig(H(M), k)
  3. 결과 (r, s)와 메시지를 전송
• 검증자 Bob
  1. PU_G, PUₐ를 사용해 서명 (r, s) 검증
  2. 해시와 서명값을 비교하여 유효성 판단

📌 DSA는 보통 RSA보다 서명 생성이 빠르고, 검증은 약간 느리다.

 

🔹요약

항목	RSA 서명 방식	DSA 서명 방식
사용 알고리즘	RSA (암호화 알고리즘 재활용)	DSA (서명 전용 알고리즘)
서명 형식	하나의 값 (S)	두 값의 쌍 (r, s)
서명 생성	느림	빠름
서명 검증	빠름	느림
사용 키	개인키로 서명, 공개키로 검증	동일

---

Digital Signature Properties

디지털 서명의 “기본적인 성질” (무엇을 보장해야 하나?)

1. 작성자 및 시점 검증
   -> 서명을 통해 누가, 언제 했는지를 확인할 수 있어야 한다.
2. 내용의 인증
   ->  서명 당시의 메시지 내용이 변경되지 않았음을 보장해야 한다.
3. 제3자 검증 가능성(공개키 기반 구조 덕분에 제3자도 검증 가능)
   ->  법적 분쟁 등에서 누구나 서명의 유효성을 검증할 수 있어야 함.

---

Digital Signature Requirements

디지털 서명이 “기술적으로 만족해야 할 조건들”

1. 메시지에 따라 달라지는 비트 패턴이어야 함
   -> 메시지가 바뀌면 서명도 반드시 달라져야 함.
2. 서명에 발신자 고유 정보 포함
   -> 위조와 부인을 방지하려면 개인키 기반으로 만들어져야 함
3. 생성 용이성
   -> 송신자가 서명을 쉽게 계산할 수 있어야 한다.
4. 검증 용이성
   -> 수신자는 서명을 쉽게 확인할 수 있어야 한다.
5. 위조 불가능성
   -> 해커가 새로운 메시지나 서명을 조작해 만드는 게 계산적으로 매우 어렵거나 불가능해야 한다.
6. 보관의 실용성
   -> 서명을 파일처럼 저장하거나 아카이빙할 수 있어야 한다.

"이 문서를 내가 이 날짜에 진짜 작성했음을, 누구나, 언제든, 위조 불가능한 방식으로 확인할 수 있어야 한다."

-> 디지털 서명이 지켜야 할 기본 원칙.

---

Discrete Logarithm Problem(DLP) & 순환군 리뷰

개념	핵심 정리
DLP	주어진 α, p, y 에서 y = α^x mod p 를 만족하는 x 를 찾기 → 계산적으로 어려움
⟨α⟩ = 순환군 mod p	α (generator)의 거듭제곱만으로 만든 집합 { α⁰, α¹, ..., α^(p-2) }
부분군 (subgroup)	p-1 의 약수 q 에 대해 크기가 q 인 α^x mod p 의 부분집합. DLP 계산 효율화를 위해 사용

 

---

왜 부분군(q) 을 쓰나?

측면	이유
연산 복잡도 ↓	지수 x의 범위가 p−1 대신 q (보통 160~256 비트) -> 지수 연산 및 Pollard-rho 알고리즘 연산 횟수 대폭 감소
보안 균형	• GNFS (일반수체 필드 체) : p 크기에만 의존, q가 작아도 영향 없음 • Pollard-rho : q 후보 개수에 비례, q는 너무 작지 않게(≥ 2²⁵⁶ 권장)
효율 vs 안전	큰 p (예: 3072 비트) + 중간 크기 q (예: 256 비트) -> RSA의 3072 비트 공개키 수준 보안 확보, 하지만 계산은 q 범위(256비트)로 훨씬 빠름

 

알고리즘별 공격 방식

알고리즘	공격 유형	복잡도 지표 설명
GNFS	정수 인수분해 (→ RSA 공격에 사용, 부분군과 무관함)	- p의 크기에만 의존함 - 예: p = 3072비트이면 약 2¹²⁸ 수준 복잡도
Pollard-rho	이산 로그 문제 (→ DSA / ElGamal 공격)	- q의 크기에 따라 공격 가능 - 예: q = 256비트이면 약 2¹²⁸ 연산 필요

• RSA는 3072비트 키를 사용하면, GNFS에 기반한 공격에도 안전하다.
• DSA는 q = 256비트일 경우, Pollard-rho 알고리즘 기반의 DLP 공격에 대해 충분한 보안을 제공한다.

---

NIST 권장 키 길이

보안레벨 (bits)	FFC(DH/DSA) LL	RSA k	ECC f
80	1024	1024	160-223
112	2048	2048	224-255
128	3072	3072	256-383
192	7680	7680	384-511
256	15360	15360	≥ 512

 

비교 요약:

알고리즘	키 구조	연산 효율	보안 달성 방식
RSA	키 전부 큼 (3072비트)	느림	정수 인수분해 어려움
DSA/DH	큰 p + 작은 q	중간	DLP (부분군 q 내 연산)
ECC	키 전체 작음 (256비트도 가능)	가장 빠름	타원곡선 위 DLP

---

추가 메모

• ECDLP(타원곡선 DLP)에는 GNFS가 적용되지 않음 → ECC가 DLP/RSA보다 효율적임.
• q는 반드시 소수여야 함. q가 합성수일 경우 Pohlig-Hellman 공격으로 DLP 계산이 빨라짐.

▶ 요약: 

큰 소수 p로 GNFS 공격을 막고, 적당히 큰 소수 q로 Pollard-rho 공격을 막으면서도 계산량을 줄이기 위해 DLP 기반 프로토콜은 “적당히 작은 부분군(subgroup)”을 사용한다.

---

Schnorr Identification Protocol (1989)

• 목적: Alice(사용자)가 자신의 개인키 a(= DL 지수)를 알고 있음을 Bob(검증자)에게 대화형-무지식(Zero–Knowledge) 방식으로 증명

단계	Alice(증명자)	Bob(검증자)	비고
Key	개인키 a (비밀), 공개키 v = α^(–a) mod p	v를 미리 보유	α : 원시근, p : 소수, `q
1. Commitment	무작위 k ∈ [0,q–1] 선택 → γ = α^k mod p 를 Bob에게 전송	γ 를 Alice에게 수신받음	1024-bit 수준
2. Challenge	–	무작위 도전 값 r 선택 (≈ 40 bits) → Alice에게 전송	“질문”
3. Response	y = k + a·r mod q 를 Bob에게 전송	α^y = γ × v^r mod p 검사	“답변”

• 통과: 동등식이 성립 → Alice가 a를 안다는 증거
• 무지식: y에는 a가 직접 드러나지 않아, Bob은 a를 알 수 없음
  ⇒ Alice가 나중에 보낸 y와, 처음에 보낸 γ = α^k mod p가 검증식 "α^y ≡ γ * v^r mod p" 를 만족한다면, 이 관계는 오직 비밀키 a를 알고 있어야 만들 수 있는 것이므로, Alice는 비밀키를 실제로 갖고 있음을 증명하는 것이다.

항목	설명
보안 근거	이산 로그 문제(DLP)의 어려움
무지식 성질	검증자는 개인키 a에 대한 아무 정보도 얻지 못함
효율	서명 크기가 작고, 계산이 빠름
응용	블록체인(비트코인 Taproot), 전자여권, 토큰 기반 인증 등

 

한 줄 요약: Schnorr Identification은 “내가 개인키를 안다”를 대화형으로 증명하고, Fiat–Shamir를 적용하면 짧고 빠른 비대화형 Schnorr Signature가 된다.

---

Schnorr Signature (Fiat–Shamir 변환)

• Schnorr Signature는 원래 사용자의 비밀키 소유를 증명하는 Schnorr Identification이라는 대화형 무지식 증명 프로토콜에서 유도된 서명 방식.
• 이 대화형 절차는 Fiat–Shamir 기법을 적용해, 메시지 M과 커밋 γ의 해시값 r = H(M || γ)를 무작위 챌린지 대신 사용함으로써 비대화형 서명으로 전환된다.
• 이때 서명자는 γ는 공개하지 않고, 해시로 생성한 r만 전송
• 결과적으로 Schnorr 서명은 짧고 계산이 빠르며, ECDSA의 기반이 되는 중요한 서명 방식

 

Schnorr Signature – 서명 생성과 검증 과정

 

🔹 Alice (서명 생성자)

1. 임의의 정수 k를 선택함
2. γ = α의 k제곱을 p로 나눈 나머지를 계산함 (즉, γ = α^k mod p)
3. 메시지 M과 γ를 이어붙여 해시 → r = H(M || γ)
4. y = k + a × r (mod q) 계산 (a는 Alice의 비밀키)
5. 서명 (r, y)를 Bob에게 보냄

🔹 Bob (검증자)

1. Alice로부터 서명 (r, y)를 받음
2. γ' = α^y × v^r mod p 계산 (v는 Alice의 공개키)
3. r' = H(M || γ') 계산
4. 받은 r와 계산된 r'를 비교함
   • 같으면 → 서명 유효
   • 다르면 → 서명 위조됨

 

Schnorr Identification vs Schnorr Signature

항목	Schnorr Identification (대화형)	Schnorr Signature (비대화형)
커밋 값 전송	Alice가 γ = α^k mod p 를 계산해 Bob에게 전송	γ는 외부로 전송하지 않고, 내부에서만 사용됨
챌린지 r	Bob이 무작위 r 값을 선택하여 Alice에게 전송	Alice가 r = H(M || γ) 로 직접 생성
응답값 y	Alice가 y = k + a·r mod q 를 계산하여 Bob에게 전송	동일
전송되는 값	Alice가 (γ, r, y)를 전송	Alice는 (r, y)만 전송. γ는 포함되지 않음
검증 방법	Bob은 α^y ≡ γ × v^r mod p 인지 확인함	Bob은 γ′ = α^y × v^r mod p 를 계산한 뒤, r′ = H(M || γ′) 확인 후, 수신한 r과 비교

 

---

NIST Digital Signature Algorithm (DSA) 관련

• NIST (미국 국가표준기술연구소)에서 디지털 서명 표준인 FIPS 186을 발표.
• SHA (Secure Hash Algorithm)를 해시 함수로 사용한다.
• 예전 버전인 FIPS 186-3 대신, 2023년 2월에 나온 최신 버전 FIPS 186-5가 현재 표준이다.
• 최신 버전에서는 DSA(디지털 서명 알고리즘)를 공식 승인 디지털 서명 알고리즘 목록에서 제거했다.
• 이유는 산업 현장에서 사용이 줄었고, DSA 구현 시 도메인 파라미터가 적절히 생성되지 않으면 공격에 취약할 수 있다는 학술 분석 때문.
• 다만, DSA는 기존에 생성된 서명 검증에는 여전히 사용 가능하다.

---

DSA 상세 구조 (Figure 13.3 & 13.4)

🔹 전역 공개키 구성 요소 (공통 파라미터)

• p: 큰 소수, 512 ~ 1024비트 (64비트 단위 증가)
• q: p − 1의 소인수이며, 보통 160~256비트 크기의 소수
• g: 생성자,
• 계산식: g = h^((p−1)/q) mod p (h는 1 < h < p − 1인 임의의 정수, g > 1)

🔹 사용자 키 쌍

• 개인키 x: 0 < x < q인 무작위 정수
• 공개키 y: y = g^x mod p

🔹 서명 생성 (Alice)

1. 메시지 M 해싱 → H(M) 계산
2. 임의의 수 k 선택 (0 < k < q) → 매 서명마다 새로 선택
3. 서명값 계산:
   • r = (g^k mod p) mod q
   • s = (k⁻¹ × (H(M) + x × r)) mod q
4. 서명 결과 (r, s) 와 메시지 M 전송

🔹 서명 검증 (Bob)

1. r, s, 메시지 M 수신 → H(M) 계산
2. w = s⁻¹ mod q (s의 역원)
3. u₁ = H(M) × w mod q
4. u₂ = r × w mod q
5. v = ((g^u₁ × y^u₂) mod p) mod q
6. 검증: v ≟ r → 같으면 서명 유효

💡 요약

• DSA는 서명 생성 시마다 k를 새로 생성함으로써 공격자 추적을 어렵게 하고 보안성 강화.
• 검증자는 공개키, 해시값, 서명값으로 간접적으로 서명의 유효성을 확인한다.
• v ≟ r 검사가 핵심 비교 조건.

---

Figure 13.4 & 13.5: DSA, Schnorr, ECDSA 서명 알고리즘 비교

 

1. DSA (Digital Signature Algorithm)
   • 전통적인 디지털 서명 알고리즘으로, 큰 소수 p, q, 생성자 g를 이용한다.
   • 메시지 해시 H(M)과 비밀키 x, 그리고 임의 비밀수 k를 사용해 서명 (r, s)를 생성.
   • 검증은 공개키 y와 해시값 등을 활용해 서명의 유효성을 확인.
2. Schnorr Signature
   • DSA와 비슷한 원리이지만, 무작위 challenge r 대신 해시 함수 H(M||γ)를 사용하여 비대화형 서명으로 만든다 (Fiat-Shamir heuristic).
   • 서명은 (γ, y) 형태이며, 훨씬 짧고 빠른 서명 생성이 가능하다.
   • ECDSA(타원 곡선 DSA)의 전신으로 알려져 있으며, 현재도 안전하게 쓰임.
3. ECDSA (Elliptic Curve DSA)
   • DSA를 타원 곡선 위에서 동작하도록 변형한 버전이다.
   • 더 작은 키 크기로 동일한 보안 수준을 제공한다.
   • 대부분 현대 암호 시스템에서 널리 사용된다.

이 세 가지를 함께 비교하는 이유는:

• DSA는 표준 디지털 서명 알고리즘의 기본 구조이고,
• Schnorr는 이를 개선해 서명을 짧고 빠르게 하면서 보안성을 유지하는 프로토콜이며,
• ECDSA는 실제 산업 현장에서 널리 사용되는, 타원 곡선 기반으로 최적화된 버전이기 때문.

정리

알고리즘	특징	서명 형태	현재 사용
DSA	전통적 방식, 소수 필드 기반	(r, s)	과거부터 사용, 지금은 줄어듦
Schnorr	Fiat-Shamir 적용한 비대화형 서명	(γ, y)	빠르고 짧음, ECDSA 전신
ECDSA	타원 곡선 기반 DSA	(r, s)	현대 주류 표준

---

RSA-PSS

• 확률적 서명 (Probabilistic Signature): 서명 생성 과정에서 무작위성을 도입하여 동일 메시지라도 서명이 매번 달라진다. 이는 서명 위조를 어렵게 만든다.
• 수학적 안전성: PSS 방식은 RSA 암호화/복호화 원시 알고리즘의 안전성에 근거한 엄밀한 보안 증명이 가능하며, 이전의 RSA 서명 방식들이 갖지 못한 보안 증명 체계를 제공한다.
• Bellare와 Rogaway가 제안: 최초로 이 방식을 제안한 학자들이다.

🔹RSA-PSS 인코딩 (Figure 13.6)

1. 메시지 M에 대해 해시 함수(H)를 적용하여 메시지 해시 mHash를 생성.
2. 임의의 랜덤 소금값(salt)을 생성하여 메시지 해시와 결합 → M′ = padding₁ || mHash || salt
3. 검증 시 salt를 전달하기 위해 DB = padding₂ || salt 를 생성
4. H = Hash(M′) maskedDB = DB ⊕ MGF(H) 로 마스킹 처리
5. 최종 인코딩 메시지(EM) 구성 → EM = maskedDB || H || bc

🟠 DB는 왜 필요한가?

DB는 단순히 padding₂ || salt 이지만, M′을 구성하기 위해 반드시 필요한 값 salt를 전달하는 중간 매개체 역할을 한다.

• 우리가 검증에 필요한 것은 M′ = padding₁ || mHash || salt
• 그런데 mHash는 메시지 M으로부터 해시해서 얻을 수 있으니 남는 건 salt
• 이 salt를 검증자에게 안전하게 전달해야 M′을 재구성하고 해시해서 H′를 만들 수 있음

🔹RSA-PSS 서명 검증 (Figure 13.7)

1. M, EM을 받는다
2. 받은 메시지 M으로 mHash = H(M) 계산
3. EM에서 maskedDB와 H(= H(M′)) 분리
4. maskedDB에서 MGF를 통해 salt 추출
5. 앞에서 구한 mHash, salt로 M′ = padding₁ || mHash || salt 구성 → H′ = Hash(M′) 계산
6. H′와 EM에서 분리한 H 비교 → 일치하면 서명 유효

요약

• RSA-PSS는 기존 RSA 서명보다 보안성이 뛰어나고 수학적 증명이 가능한 최신 서명 방식.
• 랜덤 소금값(salt)과 마스킹을 통해 서명 위조를 어렵게 만들고, 서명 메시지를 안전하게 보호한다.
• 현재 표준 RSA 서명 알고리즘으로 널리 사용되고 있다.

---

전체요약

항목	설명
Diffie–Hellman 키 교환	비밀키 없이 공개키를 교환하여 공통 키를 생성. 보안은 이산 로그 문제(DLP)에 기반.
ElGamal 암호	DH 기반 공개키 암호화. 무작위성을 추가하여 비결정적 암호화 구현.
순환군	하나의 원소로 모든 원소를 생성 가능 (예: G = <a>). 암호학에서 생성자 사용.
이산 로그 문제 (DLP)	a^k mod p = x 계산은 쉽지만, x와 a, p가 주어졌을 때 k를 구하는 문제는 매우 어려움.
ECC (타원 곡선 암호)	작은 키 크기로 동일한 보안 수준 제공 (예: 256비트 ECC ≈ 3072비트 RSA). 점 덧셈과 곱셈 사용.
ECDLP	타원 곡선 위에서 Q = kP일 때 k를 찾는 문제는 매우 어려움. ECC 보안의 핵심 기반.
ECC-DH 키 교환	K = n_A * P_B = n_B * P_A (n_A, n_B는 개인키, P_A, P_B는 공개키 점).
ECC 장점	짧은 키, 빠른 연산, 낮은 전력 소모로 IoT 및 모바일 환경에 적합.