Logo
Published on

About Digital Signature and RSA, ECC

Authors

Digital Signature

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

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

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

전자서명 특징

  • Message Authentication (인증)

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

  • Message Integrity (무결성)

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

  • Nonrepudiation (부인 방지)

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

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

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


RSA 디지털 서명

RSA 알고리즘은 암호화에 수신자의 공개 키와 복호화에 수신자의 개인 키를 사용하는 반면, RSA 디지털 서명은 발신자의 개인 키로 서명을 생성하고 발신자의 공개 키로 그것을 검증합니다.

키 생성방법 🔑

키 생성방법은 전에 정리한RSA 알고리즘의 키 생성방법과 동일합니다! 😏

검증 🧐

검증부분 역시 RSA 검증 부분과 비슷합니다.🥲

SS : Signature MM : Message

  • S=MdmodnS = M^d mod n

  • Se=(Memodn)d=MedmodnS^e = (M^e  mod  n)^d = M^{ed}  mod  n

  • ed=k×φ+1ed = k × φ⒩ + 1

  • Se=Medmodn=Mk×φ+1modnS^e = M^{ed}  mod  n= M^{k × φ⒩ + 1}  mod  n

  • Se=Mk×φ+1modn=MmodnS^e = M^{k × φ⒩ + 1}  mod  n = M  mod  n

    ⤷ 𖤐 φ⒩ 오일러의 정리 마지막 부분 😉


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

키 생성 방법 🔑

  1. 타원 곡선 Ep(a,b)E_p (a,b) 를 선택합니다.

    pp는 prime Number,소수입니다.

    Y2modp=(x3+ax+b)modpY^2 mod p = (x^3 + ax + b) mod p

  2. 다른 소수 qq와 개인 키로 사용할 정수 dd 선택합니다.

  3. 타원 곡선 상 한 점 e1e_1를 선택합니다.

    이 점을 generator라고도 합니다.

  4. 선택한 e1e_1와 개인 키로 사용하는 정수 dd를 이용해 다른 한 점 e2e_2를 계산 합니다.

    e2(...,...)=d×e1(...,...)e_2(... , ...) = d×e_1(... , ...)

  5. 개인키는 선택한 정수 dd가 되고, 공개키는 e2e_2가 됩니다.

    그러나 공개된 값이 a,b,p,q,e1,e2a, b, p, q, e_1, e_2이기 때문에 모두 공개키라고 볼 수도 있습니다.

검증 🧐

✓ Sign

Temporary Private Key : rr

1 < rr < qq -1

Temporary Public Key : P(u,v)=r×e1(...,...)P(u,v) = r×e_1(... , ...)

  • S1S_1 : umodqu  mod  q

  • S2S_2 : (h(M)+d×S1)×r1modq(h(M) + d×S_1) × r^{-1}  mod  q

    ⤷ ∴ Signature : (S1S_1, S2S_2)

✓ Verify

  1. 먼저 아래와 같이 가정합니다.

    AA = h(M)×S21modqh(M)×S_2^{-1} mod q

    BB = S1×S21modqS_1×S_2^{-1} mod q

  2. Sign할 때 S2S_2를 만든 알고리즘을 통해 rr의 값을 구합니다.

    S2S_2 : (h(M)+d×S1)×r1modq(h(M) + d×S_1) × r^{-1}  mod  q

    rr : (h(M)+d×S1)×S21modq(h(M) + d×S_1) × S_2^{-1}  mod  q

  3. Public Key를 이용하여 식을 간소화합니다.

    P(u,v)=r×e1=(h(M)+d×S1)×S21modqP(u,v) = r×e_1 = (h(M) + d × S_1) × S_2^{-1}  mod  q

    = (h(M)×S21)+(d×S1×S21)modq(h(M)× S_2^{-1}) + (d × S_1× S_2^{-1})  mod  q

    = A×e1+d×B×e1modqA× e_1 + d × B × e_1  mod  q

    = A×e1+B×e2modqA× e_1 + B × e_2  mod  q

  4. 타원 곡선 상 점 TT의 좌표를 생성합니다, ⤷T(x,y)T(x, y) = A×e1+B×e2A × e_1 + B × e_2

  5. S1=umodqS_1 = u  mod  q 이므로 S1=xmodqS_1 = x  mod  q 일 경우 검증 완료!! 🥳 📝