**Anonymous** (*nobody@replay.com*)

*Tue, 4 Aug 1998 01:51:15 +0200*

**Next message:**Enzo Michelangeli: "RSA chips from Japan?"**Previous message:**Ben Laurie: "Re: <fyi> Rebutal to Schnorr's Patent Claims re DSA - Anon."**Next in thread:**Mok-Kong Shen: "Re: <fyi> Rebutal to Schnorr's Patent Claims re DSA - Anon."**Reply:**Mok-Kong Shen: "Re: <fyi> Rebutal to Schnorr's Patent Claims re DSA - Anon."**Reply:**Mok-Kong Shen: "Re: <fyi> Rebutal to Schnorr's Patent Claims re DSA - Anon."

Dr. Schnorr's argument for coverage of the DSS by his patent is at:

http://grouper.ieee.org/groups/1363/letters/SchnorrMar98Study.ps

His U.S. patent is at

http://www.patents.ibm.com/details?patent_number=4995082

*>From here you can read the claims in textual form or look at photographs of
*

the patent pages, where the claims are on the last two pages.

As is typical, the patent is structured such that later claims depend

on earlier ones. Specifically we have, after claim 1:

2. A method for generating a signature according to the method of

claim 1, wherein...

3. A method for generating an abbreviated signature for a message to

be transmitted in a data exchange system according to the method of

claim 1, and further comprising steps defined as...

4. The method of claim 3, and further comprising the steps of...

5. The method of claim 4, and further defined as comprising...

6. The method of claim 5, and further defined as...

7. The method of claim 6, and further defined as...

etc.

Each of these encryption claims builds on earlier ones, all going back to

claim 1.

Claim 1 starts with:

1. In a method for mutual identification of subscribers in a data

exchange system working with processor chip cards and using

identification data coded into the cards by a card-issuing center

including subscriber-related public keys and stored in the respective

chip cards along with private keys which have a logical relationship

to the public keys, whereby random number-dependent check data are

exchanged between the subscribers...

It appears that claim 1, and hence all the dependent signature claims, only

apply to processor chip cards, aka smart cards. None of the signature

claims attempt to expand coverage to general purpose computers. (The last

two claims, 10 and 11, relate to signature verification and are not

conditional on claim 1 and not specific to smart cards, but they may not be

so easy to transform into something close to the DSS verification.)

The claim which covers using a subgroup of order q such that q divides

p-1 is claim 6. However note from the above that claim 6 is based on

claims 1, 3, 4, and 5. Hence it only applies to a system which uses

features from those earlier claims.

Claims 4 and 5 cover the use of a specific optimization to save the

chip card the effort of computing exponentiations. Instead the card

holds a series of r_i values along with g^r_i, all precomputed. It

uses one of those values and replaces that r_i with a combination of

the other r_i values (a process Schnorr calls "rejuvenation"). In

this way the chip card never has to exponentiate.

However, this optimization is usually unnecessary for general purpose

computers, and is not likely to be widely used in chip cards because there

is an attack against it by de Rooij published in J. Cryptology, v10 n1,

Winter, 1997, improving an earlier attack he presented at Eurocrypt 91.

For the case where 8 r_i values are stored, a parameter suggested

originally by Schnorr, de Rooij shows how to retrieve the secret key with

2^31 steps by examining 700 signatures. So a larger number of r_i values

would have to be stored, which may begin to cause memory problems on a

smart card.

An implementation which does not use this rejuvenation optimization is

not covered by claims 4-5, and hence not by claim 6, the one which covers

the use of a subgroup. Therefore DSS would not be covered unless it uses

rejuvenation.

An implementation which is not used on a smart card is not covered by

any of the signature claims.

The European patent may be different; Dr. Schnorr indicates that it does

not require that the chain of claims be set up precisely as in the U.S.

patent.

Dr. Schnorr writes, regarding the fact that DSS divides by k where his

signature scheme adds k,

*> 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.
*

It is clearly incorrect to say that because division contains many

additions, the DSS still infringes the patent. Schnorr's patent does

not cover just any addition. It covers a specific mathematical formula,

where k is added to the sum of the hash and x*r. That is the specific

addition step which must be present in order to infringe the claim.

DSS divides that same sum by k instead of adding. It is not true that this

division infringes the claim, because it does not involve an addition of k

to the sum of hash and x*r. In fact, the way modular division is usually

implemented is that the inverse of k mod q is found using the extended

Euclidean algorithm, such that k_inv * k = 1 mod q. This k_inv is then

multiplied by the sum of hash and x*r, mod q. Neither this multiplication

step nor the Euclidean algorithm involves adding k to the sum of hash and

x*r at any point. Therefore the Schnorr sequence of operations never

occurs during the DSS and the claim that the DSS does not cancel any of the

Schnorr steps is wrong.

Schnorr also argues:

*> 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."
*

People may differ in their opinions about the degree of novelty in the

change from addition to modular division. It is not obvious a priori that

such a change is acceptable. (Perhaps it is obvious to Dr. Schnorr, one of

the top cryptographers in the world, but the usual test is whether a

typical professional in the field would view the change as obvious).

Certainly it is the case that not every step in the signature calculation

can freely change between addition and division. Rather, any such change

must be carefully analyzed, bearing in mind the mathematical relationships

as well as cryptographic considerations. The verification formula changes,

and there has to be study as to whether it becomes possible to forge new

signatures from a collection of old ones.

If Dr. Schnorr really wanted to claim variants on the arithmetic formula,

he could have done so within the patent. He already claims many minor

variations, such as claim 7 which specifies that the bit lengths of the

various values can be chosen to be less than the bit length of p, a

seemingly obvious consideration given that he has already pointed out that

they can be chosen mod q where q divides p-1. Given that he has gone to

some effort to cast a wide net with his patent, it seems reasonable to

suppose that he would have included those variants on the mathematical

formula which he was aware of at the time.

Last, a couple of relatively minor nit-picks regarding the claimed

equivalence:

Schnorr patents a system in which there are certain s_j values used in

his formulas in a specific way, such that the s_j values are secret,

and not known to the verifier. In order to achieve DSS equivalence he

must assume that one of the s_j values is publicly known to be the value

1. This is not a secret value and hence the information relationships

described in the Schnorr patent do not apply.

Schnorr's patent requires that the hash value be sent as part of the

signature. In order to achieve DSS equivalence he must modify this so

that only half of the hash is sent as the signature. This departs from

the claim of his patent.

Dr. Schnorr offers the challenge:

*> 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.
*

The problem is that his patent is written broadly so that it is not clear

which of the claims represents "Schnorr signatures". If we look at the

simplest form as described in claims 1-3, the signatures are about as

similar to ElGamal signatures as they are to DSS. However if we take

the signatures as described in claims 6-7, which use subgroups, then that

is a genuinely novel aspect.

No one is claiming that the patent is invalid or that it covers old ground.

But by the same token it cannot be taken to cover every signature algorithm

that uses a subgroup.

**Next message:**Enzo Michelangeli: "RSA chips from Japan?"**Previous message:**Ben Laurie: "Re: <fyi> Rebutal to Schnorr's Patent Claims re DSA - Anon."**Next in thread:**Mok-Kong Shen: "Re: <fyi> Rebutal to Schnorr's Patent Claims re DSA - Anon."**Reply:**Mok-Kong Shen: "Re: <fyi> Rebutal to Schnorr's Patent Claims re DSA - Anon."**Reply:**Mok-Kong Shen: "Re: <fyi> Rebutal to Schnorr's Patent Claims re DSA - Anon."

*
This archive was generated by hypermail 2.0b3
on Sat Apr 10 1999 - 01:10:55
*