Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:55
schnorr (schnorr@research.bell-labs.com)
Mon, 03 Aug 1998 13:59:26 -0400
Dear Vin McLellan:
I am most gratefull for the comments that you send concerning my
letter
"Coverage of the DSA by EP-Patent 0384475".
Some people asked on the difference of the US and the European
patent.
Here it is:
At two instances the claim in the US patent reads: "A method according
to the preceding claim...." while the European patent says: "A method
according to one of the preceding claims...."
A formulation "according to one of the preceding claims" is not
acceptable for US patents.
Here are my comments to the anonymous email from <nobody@replay.com>
on my patent claims. Nobody writes:
"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."
The claim in the second sentence is clearly wrong. I have shown that the
DSS is a reformulation of Schnorr signatures. On the other hand, no
scheme of discrete log signatures published prior to Schnorr signatures
can be recast to be quite similar to Schnorr signatures. The reason is
that Schnorr signatures use small subgroups of prime order q, a feature
that is not present in any previous signature scheme. On the other hand
the DSS does not introduce any new feature. It reformulates Schnorr
signatures and goes one step back to ElGamal signatures by using a
division where a simple addition is sufficient.
I offer an award of $ 1.000 ( one thousand USD ) for the first who can
recast Schnorr signatures to be quite similar to a previously published
scheme of discrete log signatures.
Nobody writes:
Schnorr's signature, in one of the variants from the European
patent
("apparently not a variant in the U.S. patent"):
This claim is wrong. The variant of signature that I presented is also
contained in the U.S. patent. Therefore the US patent covers the use of
the DSS in the corresponding implementations.
Nobody writes:
"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."
What Nobody calls a "specially chosen mathematical transformation" is
merely a particular choice of the parameters.
It is correct that I do not turn an addition into a division which is
actually more complicated. But that is not necessary. You do not escape
patent coverage by simply complicating or repeating some step. If you
apply RSA twice and add further scrambling you still use RSA.
The point is that the DSS performs step by step the same or equivalent
operations as the Schnorr signature algorithm. The DSS performs the same
steps throughout and at one point performs a division instead of an
addition. At that point the DSS performs a more complicated but
equivalent operation. Most importantly, the DSS does not cancel out a
single step of Schnorr signatures. Even the addition step is still
there, it is part of the division which contains many additions.
In summary, DSS signatures perform the same steps as Schnorr signatures
for a particular choice of parameters except that one addition is
replaced by a division.
Replacing an addition by a division is certainly not a novel
invention, in particular as the division was already present in the
previous ElGamal signatures. This modification is fully covered by lines
65 - 68, page 10, lines 1-5, page 11 of the US filing of my patent:
"Although I have described my invention by reference to particular
illustrative embodiments thereof, many changes and modifications of the
invention may become apparent to those skilled in the art without
departing from the spirit and scope of the invention. I therefore intend
to include within the patent warranted hereon all such changes and
modifications as may reasonably and properly be included within the
scope of my contribution of the art."
Sincerely
Claus P. Schnorr
Vin McLellan wrote:
>
> Fyi. This was posted to CodherPlunks, a fairly elite mailing list for
> professional cryptographers. Because of rising interest in the AES process,
> several recent CodherPlunks discussions are being widely echoed across the
> Net. On the AES mailing list out of Australia, there are probably a half
> dozen messages commenting on each message in these threads. I've not seen
> any worth passing on.
>
> I had mentioned Dr. Schnorr's patents in a message to this List a
> few days ago (part of an ongoing discussion of DSA as an alternative to
> RSA.) I also posted a URL for Dr. Schnorr's March letter to the IEEE and
> his technical report on the relevance of his patents -- especially the
> European and Japanese patents --to the DSA. This is the first serious
> comment I have seen on the Schnorr paper.
>
> _Vin
>
> -------
>
> Date: Wed, 29 Jul 1998 01:59:20 +0200
> From: Anonymous <nobody@replay.com>
> Comments: This message did not originate from the Sender address above.
> It was remailed automatically by anonymizing remailer software.
> Please report problems or inappropriate use to the
> remailer administrator at <abuse@replay.com>.
> Subject: Schnorr patent and DSS
> To: CodherPlunks@toad.com
> Sender: owner-CodherPlunks@toad.com
> Precedence: bulk
>
> 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.
>
> -----
> Vin McLellan + The Privacy Guild + <vin@shore.net>
> 53 Nichols St., Chelsea, MA 02150 USA <617> 884-5548
> -- <@><@> --
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:55