[Cryptography] Digital Signature

이민기·2022년 5월 13일
0

BlockChain & Cryptography

목록 보기
7/12
post-thumbnail

Digital Signature

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

전자 서명 & 일반 서명

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

전자서명 특징

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

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


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 일 경우 검증 완료 📝
profile
블로그를 옮기는 중입니다. https://min71.dev

0개의 댓글