- 디지털 서명의 핵심 개념
- 신뢰받는 발신자가 메시지를 작성했음을 보장한다.
- 발신자가 메시지를 작성하지 않았다고 부인할 수 없도록 한다. (인증(Authentication)과 부인 방지(Non-repudiation))
- 메시지가 전송 중 변경되지 않았음을 보장한다. (무결성(Integrity))
- 구체적인 정의
- 키 생성 알고리즘: 가능한 비밀키 중에서 무작위로 비밀키를 선택하고, 이와 대응되는 공개키를 생성한다.
- 서명 알고리즘: 메시지와 비밀키를 입력으로 받아 서명을 생성한다.
- 검증 알고리즘: 메시지, 공개키, 서명을 입력으로 받아 해당 메시지가 인증된 것인지 확인한다.
디지털 서명 알고리즘 구성
- 키 생성 알고리즘 (Key Generation Algorithm)
- 랜덤화된 알고리즘을 사용하여 공개키(PK)와 비밀키(SK)를 생성한다.
예: (pk, sk)
- 랜덤화된 알고리즘을 사용하여 공개키(PK)와 비밀키(SK)를 생성한다.
- 서명 알고리즘 (Signing Algorithm)
- 비밀키(SK)와 메시지(M)를 입력으로 받아 서명(S)을 생성한다.
수식: s=Sign(sk,m)
- 비밀키(SK)와 메시지(M)를 입력으로 받아 서명(S)을 생성한다.
- 검증 알고리즘 (Verification Algorithm)
- 공개키(PK), 메시지(M), 서명(S)를 입력으로 받아 메시지의 진위성을 판단한다.
결과: 메시지가 유효하면 Y, 유효하지 않으면 N을 반환한다.
수식: Vrfy(pk,m,s)=Y/N
- 공개키(PK), 메시지(M), 서명(S)를 입력으로 받아 메시지의 진위성을 판단한다.
Generic Model of Digital Signature Process
RSA 서명 프로세스
- 키 생성 알고리즘 (Key Generation Algorithm)
- RSA 암호화와 동일한 방법으로 키를 생성.
- 공개키 (Public Key): (e,n)
- 비밀키 (Private Key): (d,n)
- 서명 알고리즘 (Signing Algorithm)
- 입력: 비밀키 (d,n)와 메시지 m
- 서명을 생성: s=H(m)^d m 여기서 H는 암호학적 해시 함수이다.
- 검증 알고리즘 (Verification Algorithm)
- 입력: 공개키 (e,n), 메시지 m, 서명 s
- 검증 과정: H(m) = s^e mod n 메시지가 유효하면 H(m) 값이 일치한다.
추가 주의 사항
- RSA 서명에만 적용.
- 서명(Sign): 비밀키로 암호화하는 과정
- 검증(Verify): 공개키로 복호화하여 확인하는 과정
* PSS(Probabilistic Signature Scheme)
DSS (Digital Signature Standard)
- 정의
- DSS는 디지털 서명을 생성하기 위한 암호화 알고리즘을 설명하는 미국 정부 표준입니다.
- FIPS(Federal Information Processing Standard) 186로 정의.
- 버전
- 4번의 개정이 이루어졌다.
- FIPS 186-1 (1996)
- FIPS 186-2 (2000)
- FIPS 186-3 (2009)
- FIPS 186-4 (2013)
- 4번의 개정이 이루어졌다.
- 알고리즘 포함
- DSS는 DSA, RSA, EC-DSA(타원 곡선 디지털 서명 알고리즘)를 포함.
DSA (Digital Signature Algorithm)
- 정의 및 역사
- 1991년 NIST(National Institute of Standards and Technology)에서 제안되었다.
- DSS의 일부로 1993년 FIPS 186에 채택되었다.
- 특허
- DSA는 미국 특허(U.S. Patent 5,231,668)로 보호되었으며, 특허 소유자인 David W. Kravitz(NSA 소속)이 전 세계적으로 로열티 없이 사용할 수 있도록 공개했다.
DSA의 주요 구성 요소 및 과정
1. 매개변수 (p,q,g)
- : 큰 소수(Prime Number)
- : p−1p-1을 나누는 소수
- :
2. 키 생성 알고리즘 (Key Generation Algorithm)
- 비밀키 x를 무작위로 생성 ().
- 공개키 를 계산: y=g^xmod p
3. 서명 알고리즘 (Signing Algorithm)
- 메시지 m마다 랜덤 값 kk를 생성 ().
- 서명 값 계산:
- r=(gkmod p)mod q
- s=k−1(H(m)+xr)mod q
- 서명은 (r,s)로 구성됩니다.
4. 검증 알고리즘 (Verification Algorithm)
- 값 w=s−1mod q 계산.
- 두 개의 값 계산:
- u1=H(m)⋅wmod q
- u2=
- 검증 값 계산: v=(gu1⋅yu2mod p)mod qv = (g^{u_1} \cdot y^{u_2} \mod p) \mod q
- 서명 유효성 검증:
- v=rv = r일 경우 서명이 유효
Zero-Knowledge Proof (ZKP)의 정의
- ZKP는 한 당사자(Prover, Peggy)가 다른 당사자(Verifier, Victor)에게 어떤 값 xx를 알고 있음을 증명하는 방법입니다.
- 단, 이 과정에서 xx에 대한 정보 자체는 전혀 전달되지 않으며, xx를 알고 있다는 사실만 증명됩니다.
ZKP의 주요 속성 (Properties)
- Completeness (완전성)
- 명제가 참이라면, 정직한 검증자(Victor)는 정직한 증명자(Peggy)에 의해 설득됩니다.
- Soundness (건전성)
- 명제가 거짓이라면, 속이는 증명자(Peggy)는 검증자(Victor)를 설득할 수 없습니다.
- 단, 아주 낮은 확률로 잘못된 명제가 참이라고 오인될 수 있습니다.
- Zero-knowledge (제로-지식)
- 명제가 참이라면, 검증자는 그 명제가 참이라는 사실 외에는 아무런 추가 정보를 얻지 못합니다.
예시 응용
- 암호학: 블록체인, 디지털 서명
- 보안 프로토콜: 비밀번호 검증, 인증 시스템
