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.

It is interesting to see that both RSA and DSA are based on "Fermat's little theorem".