From: Kent Briggs <72124.3234@compuserve.com>
Date: Sat, 13 Jan 1996 08:43:48 +0800
To: cypherpunks <cypherpunks@toad.com>
Subject: p-NEW digital signatures
Message-ID: <960112182626_72124.3234_EHJ93-1@CompuServe.COM>
MIME-Version: 1.0
Content-Type: text/plain


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