[Cryptography] About Digital Signature and RSA, ECC

• Digital Signature
• 전자 서명 & 일반 서명의 차이점
• 전자서명 특징
• RSA 디지털 서명
• 키 생성방법 🔑
• 검증 🧐
• ECDSA (타원곡선 디지털 서명 구조)
• 키 생성 방법 🔑
• 검증 🧐

Digital Signature

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

전자 서명 & 일반 서명의 차이점

전자서명 특징

• Message Authentication (인증)

  ✓ 발신자의 공개키를 통해 검증되므로 발신자가 보낸 것을 인증 가능합니다.

• Message Integrity (무결성)

  ✓ 메세지가 수정될 경우 서명이 변경되기 때문에 무결성이 검증됩니다.

• Nonrepudiation (부인 방지)

  ✓ 신뢰가능한 제 3자를 있다면 발신자가 보낸 메세지를 발신자가 보내지 않았다고 주장하기 어렵습니다.

𖤐 전자서명은 기밀성유지를 위해 사용되지 않습니다.

⤷ Plain Text를 이용하여 서명할 경우에는 검증과정에서 PlainText가 그대로 노출 될 수 있으며, 이와 같은 이유와 비대칭 키 암호화의 특징을 고려해 PlainText를 해싱하여 Digest로 만든 후 서명합니다

RSA 디지털 서명

✓ RSA 알고리즘은 암호화에 수신자의 공개 키와 복호화에 수신자의 개인 키를 사용하는 반면, 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$ 일 경우 검증 완료!! 🥳 📝