[정보보안] 전자서명 / RSA Signature / DSA

1. 전자서명

• S=Sig(M,개인키)
• M=Verify(S,공개키)
• 문서의 내용과 서명자에 대한 인증
• 전자서명의 보안 요구사항
  • 위조불가(Unforgeable)
    • 서명자만이 전자 서명 생성
  • 인증(Autentication)
    • 전자 서명의 서명자를 확인 가능
  • 재사용 불가(Not Resuable)
    • 한 번 생성된 서명을 다른 문서의 서명으로 사용 불가
  • 변경 불가(Unalterable)
    • 서명된 문서의 내용 변경 불가
    • 데이터의 무결성(Integrity) 보장
  • 부인방지(Non Repudiation)
    • 서명자가 나중에 서명한 사실을 부인할 수 없음

 

2. 전자서명 생성

• 원본의 해시 값
  • 메시지 크기 축소
  • 메시지 무결성 제공
  • 재사용 방지
• 해시 값을 생성자의 비밀키로 암호화

3. 전자서명 검증

철수의 M을 영희가 검증

M+S

• 영희가 H(M) - M을 해시함
• Verify (S, 철수 공개키) = H(M)

3. RSA Signature

• Public Key
  • n= p*q
  • e mod (p-1)(q-1)
• Private key
  • p , q
  • d = e^-1 mod (p-1)(q-1)
• Signature
  • S=M^d mod n
• Verification
  • M=S^e mod n  =M^de mod n = M^{demod(p-1)(q-1)} mod n = M mod n

 

4. DSA (Digital Signature Algorithm)

• For two primes p,q(q<p)
• Key Generation
  • private key : choose x at random, 0<x<q
  • public key : y=g^x mod p
• Signing
  • for a random k , 0<k<q
  • r = (g^k mod p) mod q
  • s = (k^-1(H(M)+xr)) mod q
  • Signature : <M,r,s>
• Verifying
  • w=s^-1 mod q
  • u1=H(M)w mod q
  • u2=rw mod q
  • v=((g^u1y^u2)mod p) mod q
  • check if v=r