p-NEW digital signatures

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

Kent Briggs <kbriggs@execpc.com> wrote:
>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?

Yes.  In this case a fake signature can be forged by picking a random r, and
then z can be calculated as:

z=my^(-r) mod p

No security at all.