Digital Signature Algorithm(DSA)

DIGITAL SIGNATURE STANDARD (DSS)

o   US Govt approved signature scheme

o   designed by NIST & NSA in early 90's

o   published as FIPS-186 in 1991

o   revised in 1993, 1996 & then 2000

o   uses the SHA hash algorithm

o   DSS is the standard, DSA is the algorithm

o   FIPS 186-2 (2000) includes alternative RSA & elliptic curve signature variants

DIGITAL SIGNATURE ALGORITHM(DSA)

o   creates a 320 bit signature

o   with 512-1024 bit security

o   smaller and faster than RSA

o   a digital signature scheme only

o   security depends on difficulty of computing discrete logarithms

o   variant of ElGamal & Schnorr schemes

1. DSA Key Generation

o   have shared global public key values (p,q,g):

o   choose q, a 160 bit

o   choose a large prime p = 2L

^o     where L= 512 to 1024 bits and is a multiple of 64 and q is a prime factor of (p-1)

o   choose g = h(p-1)/q

^o     where h<p-1, h(pp-11)//q (mod p) > 1

o   users choose private & compute public key:

^o     choose x<q

^o     compute y = gx (mod p)

2. DSA Signature Creation

o   to sign a message M the sender:

^o     generates a random signature key k, k<q

^o     nb. k must be random, be destroyed after use, and never be reused

o   then computes signature pair:

§  r = (gk(mod p))(mod q)

§  s = (k-1.H(M)+ x.r)(mod q)

o   sends signature (r,s) with message M

3. DSA Signature Verification

o   having received M & signature (r,s)

o   to verify a signature, recipient computes:

§  w = s-1(mod q)

§  u1= (H(M).w)(mod q) u2= (r.w)(mod q)

§  v = (gu1.yu2(mod p)) (mod q)

o   if v=r then signature is verified