Cryptographic Applications - Introduction to Cryptography with Java Applets - page 334

prime, g is a generator modulo p , and y is the lnr of g a modulo p . Suppose d is a public mes-
sage digest function. To generate a signed digest of a message P , A must do the following:

1. Select a random integer k between 1 and p 2 (inclusive), such that k is relatively prime

to p 1.

Calculate r , the lnr of g k modulo p .

2.

3. Find k , an inverse of k modulo p 1. (This inverse exists due to our choice of k .)

4. Calculate s , the lnr of k ( d ( P ) ar ) modulo ( p 1). (Only A can do this step, as only A

knows the private key a .)

5. The signature is the pair of integers, r and s .

To verify that this signature is valid, the recipient B must do this:

1. Verify that r is between 1 and p 1; if not, reject the signature.

2. Using A's public information, calculate v , the lnr of y r r s modulo p .

3. Calculate d ( P ), the digest of the message P .

4. Compute w , the lnr of g d ( P ) modulo p .

5. If v = w , accept the signature as valid; otherwise, reject it.

Why does this work? Well, because

s k ( d ( P ) ar ) (mod p 1),

we have

ks k k ( d ( P ) ar )

d ( P )

ar (mod p 1).

Thus, by subtracting ar from both sides, we have

d ( P ) ar + ks (mod p 1).
Because of the properties of discrete logarithms, this then yields
g d ( P )

g ar ks (mod p ).
But note that by construction of v and w , and because of the previous congruence, we must
have

w g d ( P )

g ar ks ( g a ) r r s y r r s

v (mod p ).

Thus, the signature is valid iff v = w .

E XAMPLE . For this example, we will use a simple hash function, but unsuitable for crypto-
graphic purposes. For simplicity's sake, we will not use salt, or CBC. Suppose A is using
the public prime

p = 768416655531999472553972503490662169854881508111468141690052585033772
353811145704262633807570477286149198100781782215658227986987692047241181
534570445703122494213057666371119117944205153516492397844122051887566688