Schnorr patent and DSS

Anonymous (nobody@replay.com)
Wed, 29 Jul 1998 01:59:20 +0200

• Next message: Enzo Michelangeli: "Re: RNG in a Smart Card"
• Previous message: Enzo Michelangeli: "Re: DSA alternative to RSA"

Schnorr's argument in
http://grouper.ieee.org/groups/1363/letters/SchnorrMar98Study.ps
is a nice try, but ultimately fails to convince.

What it does show is how closely related many of the discrete log
signatures are, that with sufficient algebraic ingenuity you can
recast one to be quite similar to another.

DSS:

    Private key: x; Public key: g^x mod p.

    r = (g^k mod p) mod q
    s = k^-1 (SHA(M) + xr) mod q

    Signature is (r, s).

    k is a random value chosen for this signature, and SHA(M) is the
    message hash.

Schnorr's signature, in one of the variants from the European patent
(apparently not a variant in the U.S. patent):

    Private key: s1, s2; Public key: g^-s1 mod p, g^-s2 mod p

    r = g^k mod p

    h(r,m) is a double-width hash; call two halves LH(r,m) and RH(r,m)

    s = k + s1*LH(r,m) + s2*RH(r,m) mod q

    Signature is (h(r,m), s).

    k is a random value chosen for this signature.

Not too similar, huh? Schnorr has two secret exponents, not just one;
he uses a double width hash, which is part of the signature; the
arithmetic in the choice of s doesn't look too similar to the
arithmetic in DSS, there is none of the "mod p mod q" which is so
distinctive in DSS.

Now he begins to transform it.

h(r,m) becomes defined as (SHA(m), (-r) mod q). This means that
LH(r,m) is just SHA(m), while RH(r,m) is -r mod q. Then the equation
for s becomes:

    s = k + s1*SHA(m) - s2*r mod q.

That's starting to look a little more like DSA's equation for s. Now he
says, we don't really need two private exponents. Just set s1=1 and
rely solely on s2, which we will rename as -x. This produces:

    s = k + SHA(m) + x*r mod q.

Pretty close now.

Then he says, the signature is (h(r,m), s) which is SHA(m), -r mod q,
s. But you don't really need SHA(m) to be part of it, that can be
calculated from the message. So it leaves (-r mod q, s). The first
term is now -g^k mod p mod q, just like DSS except for the negative
sign, and the second term is like DSS except instead of dividing by k
it adds k.

That's the best Schnorr can do. He can't turn a division into an
addition, so he says, "A division modulo q is... equivalent to a
sequence of additions and shifts modulo q. Thus the division modulo q
in the DSA iterates operations of the same type as the addition modulo
q...".

Sorry, I don't buy it. Everything is ands and ors when you come right
down to it, but that doesn't mean that the XOR patent covers RSA.

In summary, Schnorr has to turn his two key system into one key, and
has to take his double width hash and set it up as SHA appended to a
specially chosen mathematical transformation. Once he's done that, he
is pretty close to DSS. But he is left with an addition where DSS has
a division, and that can't be substituted out.

• Next message: Enzo Michelangeli: "Re: RNG in a Smart Card"
• Previous message: Enzo Michelangeli: "Re: DSA alternative to RSA"