Computer Exercise 3

We make use of the mathematical fact

ab mod p (a mod p) (b mod p) mod p

(define (verify message signature public-key)
  (let ((r (signature-r signature))
        (s (signature-s signature))
        (p (public-key-p public-key))
        (g (public-key-g public-key))
        (y (public-key-y public-key)))
    (and (< 0 r p)                     
	 (let ((h (modulo (message-digest message) p)))
	   (= (expmod g h p)
	      (modulo (* (expmod y r p)        ;; here is where we use the 
                         (expmod r s p))       ;; mathematical fact.
		      p))))))

Now let's verify the two example messages:

(verify m1-ex-3 s1-ex-3 pk-ex-3)
;Value: #f

(verify m2-ex-3 s2-ex-3 pk-ex-3)
;Value: #t