Knowlegde Through Fun Welcome To Mady's Site.

1. Specification of parameters.

The DSA (Digital Signature Algorithm) makes use of the following parameters:

1. p is a prime number, where 2L-1 < p < 2L for 512 <= L <= 1024 and
L a multiple of 64.
2. q is a prime divisor of p - 1, where 2159 < q < 2160 .
3. g = h(p-1)/q mod p, where h is any integer with 1 < h < p - 1 such that
h(p-1)/q mod p > 1 (g has order q mod p)
4. x = a randomly generated integer with 0 < x < q
5. y = gx mod p
6. k = a randomly or generated integer with 0 < k < q

The integers p, q, g can be public and they can be common to a group
of users. A user's private and public keys are x and y, respectively.
They are normally fixed for a period of time. Parameters x and k are
used for signature generation only, and must be kept secret. Parameter
k must be regenerated for each signature.

2. Signature Generation.

The signature of a message M is the pair of numbers r and s computed
according to the equations below.

r = (gk mod p) mod q and
s = (k-1(SHA (M) + xr)) mod q.

The value of SHA (M) is a 160-bit string output by the Secure Hash
Algorithm. For use in computing s, this string must be converted to an
integer. As an option, one may wish to check if r = 0 or s = 0. If
either r = 0 or s = 0, a new value of k should be generated and the
signature should be recalculated (it is extremely unlikely that r = 0
or s = 0 if signatures are generated properly).

The signature is transmitted along with the message to the verifier.

3. Signature Verification.

Prior to verifying the signature in a signed message, p, q and g plus
the sender's public key and identity are made available to the
verifier in an authenticated manner.

Let M', r' and s' be the received versions of M, r, and s,
respectively, and let y be the public key of the signatory. To
verifier first checks to see that 0 < r' < q and 0 < s' < q; if either
condition is violated the signature shall be rejected. If these two
conditions are satisfied, the verifier computes

w = (s')-1 mod q
u1 = ((SHA (M') w) mod q
u2 = ((r') w) mod q
v = (((g)u1 (y)u2 ) mod p) mod q.

If v = r', then the signature is verified and the verifier can have
high confidence that the received message was sent by the party
holding the secret key x corresponding to y. For a proof that v = r'
when M' = M, r' = r, and s' = s, see Appendix1.

If v does not equal r', then the message may have been modified, the
message may have been incorrectly signed by the signatory, or the
message may have been signed by an impostor. The message should be
considered invalid.

.