07. Public Key Cryptography - Digital Signature

DSA : digital siganture algorithm

1. public parameter 생성

• p : prime number
  L bits ( 512 <= L <= 1024이면서 64의 배수여야 함)
• q : prime factor of p-1
• g : multiplicative order modulo p is q
  h는 (1<h<p-1)이며,
  $h^{p-1}$ mod $p=1$이다.
  

2. User key

• x (private key) : 0 < x < q
• y (public key) : $y=g^x$(mod) $p$

3. Signing

• ranom k를 고른다.
• signature (r, s) 생성
  - $r=(g^x$(mod) $p)$ mod $q$
  • s = $[k^{-1}(H(M)+xr)]$ mod q

4. Verificate (r,s)

• $v=(g^{u1}y^{u2}modp)$mod q
  - $u_1=(H(M)w)modq$
  • $u_2=rw$ mod $q$
  • $w=s^{-1}$(mod $q$)
• v=r인지 확인한다.

• 왜 r=v여야하는가?
  

example

RSA vs DSA signature

• DSA는 512-1024bit security의 320bit signature 생성 -> DSA보다 작은 크기의 signature
• DSA는 digital scheme만 제공하고, no encryption supported.
• DSA 는 q를 사용하여 signing 하는데 최적화되어있다. => RSA보다 signing은 빠르고, verification은 느리다.