Discrete Logarithm Signatures

A digital signature system based on the Discrete Logarithms problem. I'll start by explaining the interactive version of this technique, as this is easier to understand, and then show how to convert it into a noninteractive version.

Remember: Discrete logarithms is the problem of calculating e from the value of (g^e mod p) where g and p are known.

If you are not familiar with modular arithmetic, there is a single "trick" you need to know to make the below description possible to understand: (a mod p)*(b mod p) = a*b mod p.

1. Select a random, reasonably large number 'e'. This is your secret key. Your public key is g, p and g^e mod p. (g and p can be the same for everybody, but using different ones protect against attackers using birthday attacks to try to find somebody they can impersonate.)
2. Let m be a message digest (secure hash value of your message).
3. Calculate (m^e mod p). This is your signature, which you attach to the message.
4. When somebody want to check your signature, they create a random number 'r' and send it to you.
5. You create a random number 's', which you keep secret, and calculate (g^s mod p), (m^s mod p) and the verifier v = (re + s). This is your response to the random challenge r. Due to s being random, this does not give out any information.
6. The person verifying your signature check that
   g^v mod p = (g^e)^r*(g^s) mod p and
   m^v mod p = (m^e)^r*(m^s) mod p

   Values that have this property can only be made by somebody in possession of e (assuming Discrete Logarithms are hard to calculate - if they are not, most digital signature schemes are screwed.)

In order to transform the above challenge into a noninteractive signature, we use a secure hash to create the random number r used as a challenge (from 4. above), as follows:

1. You create (m^e mod p) as above, and also immediately select a secret number s, and compute the values (g^s mod p) and (m^s mod p).
2. You create r by doing a secure hash over (m, (m^e mod p), (g^s mod p), (m^s mod p)) in a standard format. The output value of this cannot be controlled in any useable fashion, which makes it as good as a random number supplied by a challenger.
3. You calculate v as above.
4. You attach v, m^e mod p, g^s mod p and m^s mod p to the message as your signature. This can now be verified the same way as above.

Note the use of a random, secret number 's' in the signatures here. This means that more than one signature is valid for a particular message; in other words, the signature contains a subliminal channel, which can be used to send other information in the signature. This is unfortunate for e.g. Digital Cash, and might be a problem if you are using an untrusted implementation of Discrete Logarithm signatures - the implementation could be leaking other information, for instance bits from your private key.

DSS is based on Discrete Logarithm Signatures.