Proof of DSA Digital Signature Algorithm

Cryptography Tutorials - Herong's Tutorial Examples

∟Introduction of DSA (Digital Signature Algorithm)

∟Proof of DSA Digital Signature Algorithm

This section describes steps to prove DSA digital signature algorithm. Fermat's little theorem is the key part of the proof.

To proof the DSA digital signature algorithm, we need to proof the following:

Given: 
   p is a prime number                     (1)
   q is a prime number                     (2)
   (p-1) mod q = 0                         (3)
   1 < g < p                               (4)
   g = h**((p–1)/q) mod p                (5.1)
   g**q mod p = 1                        (5.2)
   0 < x < q                               (6)
   y = g**x mod p                          (7)
   h                                       (8)
   0 < k < q                               (9)
   r = (g**k mod p) mod q                 (10)
   r > 0                                  (11)
   k*i mod q = 1                          (12)
   s = i*(h+r*x) mod q                    (13)
   s > 0                                  (14)
   s*w mod q = 1                          (15)
   u1 = h*w mod q                         (16)
   u2 = r*w mod q                         (17)
   v = (((g**u1)*(y**u2)) mod p) mod q    (18)
   
prove: 
   v = r

One way to prove this is to use steps presented by William Stallings at http://mercury.webster.edu/aleshunas/COSC%205130/K-DSA.pdf

Fermat's little theorem: 
   h**(p-1) mod p = 1                                       # as (21)

Rewrite expression:
   g**(f*q) mod p 
      = (h**((p–1)/q) mod p)**(f*q) mod p                   # by (5.1)
      = h**(f*q*(p-1)/q) mod p
      = h**(f*(p-1)) mod p
      = (h**(p-1) mod p)**f mod p     
      = 1**f mod p                                          # by (21)
      = 1                                                   # as (22)

Rewrite expression:
   y**u2 mod p 
      = y**(r*w mod q) mod p                                # by (17)
      = (g**x mod p)**(r*w mod q) mod p                     # by (7)
      = g**(x*(r*w mod q)) mod p
      = g**(x*(r*w-f1*q) mod p
      = g**(x*r*w-x*f1*q) mod p
      = g**((x*r*w mod q)+f2*q-x*f1*q) mod p
      = (g**(x*r*w mod q)*(g**(f*q)) mod p
      = (g**(x*r*w mod q)*1) mod p                          # by (22)
      = g**(x*r*w mod q) mod p                              # as (24)


Rewrite expression:
   v = (((g**u1)*(y**u2)) mod p) mod q                      # by (18)
      = (((g**(h*w mod q))*(y**u2)) mod p) mod q            # by (16)
      = (((g**(h*w mod q))*(g**(x*r*w mod q))) mod p) mod q # by (24)
      = ((g**((h*w mod q)+(x*r*w mod q))) mod p) mod q  
      = ((g**(((h*w+x*r*w) mod q)+f*q)) mod p) mod q  
      = (((g**((h*w+x*r*w) mod q))*(g**(f*q))) mod p) mod q 
      = (((g**((h*w+x*r*w) mod q))*1)) mod p) mod q         # by (22)
      = ((g**((h*w+x*r*w) mod q)) mod p) mod q            
      = ((g**(((h+x*r)*w) mod q)) mod p) mod q              # as (25)

Rewrite expression:
   k*s mod q 
      = k*(i*(h+r*x) mod q) mod q                           # by (13)
      = (k*i mod q)*((h+r*x) mod q) mod q
      = 1*((h+r*x) mod q) mod q                             # by (12)
      = (h+r*x) mod q                                       # as (26)

Apply (26) to (25):
   v = ((g**((k*s*w) mod q)) mod p) mod q         
      = (g**((k mod q)*(s*w mod q) mod q) mod p) mod q 
      = (g**((k mod q)*(1) mod q) mod p) mod q              # by (15)
      = (g**(k mod q) mod p) mod q     
      = (g**(k + f*q) mod p) mod q     
      = (g**k mod p)*(g**(f*q) mod p) mod q     
      = (g**k mod p)*1 mod q                                # by (22)
      = (g**k mod p) mod q
      = r                                                   # by (10)

Done.

See you can see, the key part of the proof process is the "Fermat's little theorem", which says that if p is a prime number, then for any integer a, the number "a**p - a" is an integer multiple of p. See http://en.wikipedia.org/wiki/Fermat%27s_little_theorem for more details.