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
Anonymous (nobody@replay.com)
Tue, 4 Aug 1998 01:51:15 +0200
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.
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:55