I've been experimenting with discrete logarithm digital signatures. Schneier describes a scheme call p-NEW on page 498 of "AP" (2nd ed). It has the advantage of not requiring an inverse calculation via the extended Euclid algorithm. The signature is shown as: r=mg^(-k) mod p s=k-r'x mod q The verification equation is m=(g^s)(y^r')r mod p r'=r mod q. If p is a strong prime then q=p-1 and r'=r. The public key is y=g^x mod p. x is the private key. k is a random number less than q. m is the message being signed. I'm confused about the negative k value in the r equation. This would lead to 1/g^k which is a fractional number. It seems the equation should be: r=mg^(q-k) mod p Or, I can rearrange both equations like this: r=mg^k mod p s=-k-rx mod p To avoid using negative numbers in the mod function, I can calc s as: s=q-((k+rx) mod q) I tried this with some small integers and the numbers work out. The s calculation will be quick since there is no exponentiation. Most of the time spent in signing a message will be the r calculation. However, the the verification equation [m=(g^s)(y^r)r mod p] has two exponentiation calculations and will take more time. Since a message is only signed once but could be verified many times, I could precompute rg^s during the signing: r=mg^k mod p s=q-((k+rx) mod q) z=rg^s mod p s is discarded and the signature is r and z. The verification is: m=zy^r mod p This slows down the signing but speeds up the verification. Here's the $64K question: Does this compromise the signature's security? Kent Briggs kbriggs@execpc.com CIS: 72124,3234