[Cryptography] Digital Signature

Digital Signature

전자 문서의 데이터 무결성과 출처 증명을 위한 암호화 알고리즘

전자 서명 & 일반 서명

	일반 서명	전자 서명
특징	문서에 포함한다 (낱인, 서명 등..)	문서와 서명이 분리된 파일로 존재
관계	1:n 관계	1:1 관계
복제	서명된 문서의 복사본과 원본은 구분이 가능	원본과 복사된 문서를 구분할 수 없으며 구분해야하는 경우 문서에 타임스탬프를 추가

전자서명 특징

• Message Authentication (인증)
  ↪발신자의 공개키를 통해 검증되므로 발신자가 보낸 것을 인증가능 하다
• Message Integrity (무결성)
  ↪ 메세지가 수정될 경우 서명이 변경되기 때문에 무결성이 검증된다
• Nonrepudiation (부인 방지)
  ↪ 신뢰가능한 제 3자를 있다면 발신자가 보낸 메세지를 발신자가 보내지 않았다고 주장하기 어렵다

𖤐전자서명은 기밀성유지를 위해 사용되지 않는다.
↪ Plain Text를 이용하여 서명할 경우에는 검증과정에서 PlainText가 그대로 노출 될 수도 있다. 이와 같은 이유와 비대칭 키 암호화의 특징을 고려해 PlainText를 해싱하여 Digest로 만든 후 서명한다

---

RSA 디지털 서명

키 생성방법 🔑

🖋 키 생성방법은 전에 정리한RSA의 키 생성방법과 동일하다! 😏

검증 🧐

검증부분 역시 RSA 검증 부분과 비슷하다 🥲
$S$ : Signature
$M$ : Message

• $S = M^d mod n$
• $S^e = (M^e mod n)^d = M^{ed} mod n$
• $ed = k × φ⒩ + 1$
• $S^e = M^{ed} mod n= M^{k × φ⒩ + 1} mod n$
• $S^e = M^{k × φ⒩ + 1} mod n = M mod n$
  ⤷ 𖤐 φ⒩ 오일러의 정리 마지막 부분 😉

---

ECDSA (타원곡선 디지털 서명 구조)

키 생성 방법 🔑

1. 타원 곡선 $E_p (a,b)$ 를 선택
   ⤷📌 $p$는 prime Number,소수이다
   ⤷ $Y^2 mod p = (x^3 + ax + b) mod p$
2. 다른 소수 $q$와 개인 키로 사용할 정수 $d$ 선택
3. 타원 곡선 상 한 점 $e_1$를 선택한다
   ⤷이 점을 generator라고도 한다
4. 선택한 $e_1$와 개인 키로 사용하는 정수 $d$를 이용해 다른 한 점 $e_2$를 계산 한다
   ⤷$e_2(... , ...) = d×e_1(... , ...)$
5. 개인키는 선택한 정수 $d$가 되고, 공개키는 $e_2$가 된다
   ⤷ 그러나 공개된 값이 $a, b, p, q, e_1, e_2$이기 때문에 모두 공개키라고 볼 수도 있다

검증 🧐

Sign

Temporary Private Key : $r$
⤷ 1 < $r$ < $q$ -1
Temporary Public Key : $P(u,v) = r×e_1(... , ...)$

• $S_1$ : $u mod q$
• $S_2$ : $(h(M) + d×S_1) × r^{-1} mod q$
  ⤷ ∴ Signature : ($S_1$, $S_2$)

Verify

1. 먼저 아래와 같이 가정한다
   $A$ = $h(M)×S_2^{-1} mod q$
   $B$ = $S_1×S_2^{-1} mod q$
2. Sign할 때 $S_2$를 만든 알고리즘을 통해 $r$의 값을 구한다
   $S_2$ : $(h(M) + d×S_1) × r^{-1} mod q$
   ⤷ ✏️ $r$ : $(h(M) + d×S_1) × S_2^{-1} mod q$
3. Public Key를 이용하여 식을 간소화
   ⤷ $P(u,v) = r×e_1 = (h(M) + d × S_1) × S_2^{-1} mod q$
   = $(h(M)× S_2^{-1}) + (d × S_1× S_2^{-1}) mod q$
   = $A× e_1 + d × B × e_1 mod q$
   = $A× e_1 + B × e_2 mod q$
4. 타원 곡선 상 점 $T$의 좌표를 생성
   ⤷$T(x, y)$ = $A × e_1 + B × e_2$
5. $S_1 = u mod q$ 이므로 $S_1 = x mod q$ 일 경우 검증 완료 📝