[47069] in Cypherpunks
p-NEW digital signatures
daemon@ATHENA.MIT.EDU (Kent Briggs)
Fri Jan 12 13:50:17 1996
Date: 12 Jan 96 13:26:26 EST
From: Kent Briggs <72124.3234@compuserve.com>
To: cypherpunks <cypherpunks@toad.com>
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
