Chapter 11. 서명(Signatures)¶
1절. 디지털 서명(Digital Signatures)
2절. RSA 서명
3절. DSS / DSA
4절. 0-지식 증명(Zero-Knowledge Proof)
5절. Schnorr
1절. 디지털 서명(Digital Signatures)¶
디지털 서명(Digital Signatures) 정의¶
- 디지털 메시지나 문서의 진위를 증명하는 수학적 방식
- 인증 및 부인 방지
- 유효한 디지털 서명에 대한 수신자와 발신자의 정보
- 수신자 : 메시지가 발신자에 의해 생성되었음을 믿을 수 있는 이유 제공
- 발신자 : 메시지를 보낸 사실을 부인 불가
- 무결성
- 메시지가 전송 중에 변경되지 않음을 보장
디지털 서명(Digital Signatures) 알고리즘¶
키 생성 알고리즘(Key Generation Algorithm)¶
- 무작위 알고리즘
- \((pk, sk)\) 출력
서명 알고리즘(Signing Algorithm)¶
- 개인 키와 메시지를 받아 서명 출력
- \(s = Sign(sk, m)\)
검증 알고리즘(Verification Algorithm)¶
- 공개 키, 메시지, 서명 입력
- 메시지의 진위 주장에 수락 or 거부
- \(Vrfy(pk, m, s) = Y/N\)
일반적인 디지털 서명 과정¶
2절. RSA 서명¶
RSA 서명 (해쉬된 RSA 또는 FDH-RSA) 알고리즘¶
키 생성 알고리즘¶
- RSA 암호화와 동일
- 공개 키 = \((e, n)\)
- 개인 키 = \((d, n)\)
서명 알고리즘¶
- 입력
- 개인 키 = \((d, n)\)
- 메시지 = \(m\)
- 서명 \(s = H(m)^d\) \(mod\) \(n\) 계산
- \(H : {0, 1}^* → Z_n^*\)는 암호학적 해쉬 함수
검증 알고리즘¶
- 입력
- 공개 키 = \((e, n)\)
- 메시지 = \(m\)
- 서명 = \(s\)
- \(H(m) = s^e\) \(mod\) \(n\) 확인
번외) RSA 서명에만 해당되는 조건¶
- 서명(Sign) = 개인 키로 암호화
- 검증(Vrfy) = 공개 키로 복호화
RSA-PSS(Probabilistic Signature Scheme)¶
3절. DSS / DSA¶
디지털 서명 표준(DSS : Digital Signature Standard)¶
- 디지털 서명을 생성하기 위한 암호화 알고리즘을 설명하는 미국 정부의 FIPS(연방 정보 처리 표준) 186
- 총 네 번의 개정판
- FIPS 186-1 (1996)
- FIPS 186-2 (2000)
- FIPS 186-3 (2009)
- DSA, RSA 및 EC-DSA 포함
- FIPS 186-4 (2013)
DSA(Digital Signature Algorithm)¶
디지털 서명 알고리즘(DSA) 알고리즘¶
-
매개변수 : \((p, q, g)\)
-
키 생성 알고리즘
-
\(0 < x < q\) 범위에서 무작위 방법으로 비밀 키 \(x\) 선택
-
공개 키 \(y = g^x\) \(mod\) \(p\) 계산
-
서명 알고리즘
-
\(0 < k < q\) 범위에서 메시지 별 무작위 값 \(k\) 생성
- \(r = (g^k mod\) \(p)\) \(mod\) \(q\)와 \(s = k^−1(H(m) + xr)\) \(mod\) \(q\) 계산
-
메시지 \(m\)에 대한 서명 : \((r, s)\)
-
검증 알고리즘
- \(w = s^{−1}\) \(mod\) \(q, u_1 = H(m)w\) \(mod\) \(q, u_2 = rw\) \(mod\) \(q\) 계산
- \(v = (g^{u_1} y^{u_2}\) \(mod\) \(p)\) \(mod\) \(q\) 계산
- 서명 유효성 : \(v = r\)
4절. 0-지식 증명(Zero-Knowledge Proof)¶
ZKP¶
- 제로-지식 증명(Zero-Knowledge Proof)
- 제로-지식 프로토콜
- 한 당사자(증명자 Peggy)가 다른 당사자(검증자 Victor)에게 특정 값 \(x\)를 알고 있음 증명
- 해당 값 \(x\)를 알고 있다는 사실 외 어떠한 정보도 전달하지 않는 방법
속성¶
-
완전성(Completeness)
-
명제가 참일 경우
- 정직한 증명자가 정직한 검증자에게 사실 납득
-
건전성(Soundness)
-
명제가 거짓일 경우
- 부정직한 증명자가 정직한 검증자에게 그것이 참이라고 납득시킬 확률 매우 낮음
-
제로-지식(Zero-knowledge)
-
명제가 참일 경우
- 검증자는 명제가 참이라는 사실 외에 아무것도 알 수 없음
예시¶
- 루빅 큐브(Rubik Cube)
- 할로윈 사탕(Halloween Candy)
- 알리바바 동굴(AliBaba Cave)
5절. Schnorr¶
슈노르 식별(Schnorr Identification)¶
-
특별 정직-검증자 제로-지식
-
\((r, e, s)\)는 \(x\)를 알지 않고도 시뮬레이션 가능
-
특별 건전성 – \(e1 ≠ e2\)일 때, \((r, e_1, s_1)\)과 \((r, e_2, s_2)\)로부터 \(x\) 계산 가능
슈노르 서명(Schnorr Signature)¶
-
매개변수 : \((p, q, g)\)
-
키 생성 알고리즘
-
\(0 < x < q\) 범위에서 무작위 방법으로 비밀키 \(x\) 선택
-
공개키 \(y\)를 \(y = g^x\) \(mod\) \(p\)로 계산
-
서명 알고리즘
-
메시지마다 고유한 무작위 값 \(k\)를 \(0 < k < q\) 범위에서 생성
- \(r = g^k\) \(mod\) \(p,\) \(e = H(r,m), s=k−xe\) \(mod\) \(q\) 계산
-
메시지 \(m\)에 대한 서명 : \((s, e)\)
-
검증 알고리즘
- \(𝑟̂ = g^sy^e\) \(mod\) \(p\) 과 \(𝑒̂ = H(𝑟̂, m)\) 계산
- 서명은 \(𝑒̂ = e\)일 때 유효