Knowlegde Through Fun Welcome To Mady's Site.

The purpose of this is to show that if M' = M, r' = r and s' = s in
the signature verification, then v = r'. Where, M is the sent message,
the pair of numbers r and s is signature of the message M. M' is the
received message, r' and s' is the received signature.
Before proving the final result, we state and prove following lemma.

Lemma:
Let p and q be primes so that q divides p – 1, h a positive integer
less than p, and
g = h (p-1)/q mod p.
Then g q mod p = 1, and if m mod q = n mod q, then g m mod p = g n mod p.
Proof:
We have,
g q mod p = (h (p- 1)/ q mod p) q mod p
= h (p-1) mod p
= 1 by Fermat's Little Theorem.

Now let m mod q = n mod q, i.e., m = n + k.q for some integer k. Then
g m mod p = g (n+k.q) mod p
= (g n .g k.q) mod p
= ((g n mod p) . (g q mod p) k) mod p
= g n mod p

Since, g q mod p = 1.
We are now ready to prove the main result.

THEOREM:
If M' = M, r' = r, and s' = s in the signature verification, then v = r'.
Proof: We have,
w = ( s' ) -1 mod q = s-1 mod q
u1 = ( ( SHA(M') ) w ) mod q = ( (SHA(M) ) w ) mod q
u2 = ( r' . w ) mod q = ( r . w ) mod q.
Now y = g x mod p,

So that by the lemma,

v = ( ( g u1 y u2 ) mod p ) mod q

= ( ( g SHA(M) . w . y r . w ) mod p) mod q

= ( ( g SHA(M) . w . g x .r. w ) mod p) mod q

= ( ( g ( SHA(M)+x.r ) . w ) mod p ) mod q.

Also,
s = ( k-1( SHA(M) + x.r ) ) mod q.

Hence,
w = ( k . ( SHA(M) + x.r )-1 ) mod q

( SHA(M) + x.r ) .w mod q = k mod q.

Thus by the lemma,
v = (gk mod p) mod q = r = r'.

Hence the theorem is proved.