Schnorr says DSA infringes on his patent – Codepunks mailing list

/ Alex Waltz

INTRO
Schnorr Signatures are the most elegant signature scheme we have, they almost come out naturally.
But until 2008 most of the world used DSA, because Claus P. Schnorr filled a patent and only licensed RSA and Siemens to use it.

As a response, NIST came out with DSA(Digital Signature Algorithm), which pretty much is Schnorr signatures modified enough so they don’t infringe on the patent.
They also filled a patent but released it royalty-free.
The patent was filed by David W. Kravitz a NSA[1]Btw if you think this is uncommon, it is not. The same is true for SHA256. contractor at the time.

Later Schnorr claimed that the patent he filled covered DSA.
You can find here the CSL Bulletins sent by NIST in November 1994 mentioning this.


Context of the emails
Below you will find the emails exchanged on the Coderpunks mailing list between Claus P. Schnorr and some other d00ds that disagree with him.

I reposted this here, as it was impossible to read in the original format.
The posts are linked here in chronological order be easier to follow.

It seems that Schnorr sent an email to a Burn from the IEEE Standard association on 27 March 1998 expressing his concerns.
The email, ends with “Enclosed is a study on the coverage of the DSA by EP-Patent 0384475 which links to http://grouper.ieee.org/groups/1363/letters/SchnorrMar98Study.ps .
However, this link is broken and I could not find any archives of it.
Luckly the relevant snipers are quoted by the people commenting on Schnorr’s remarks.

The 1st 2 emails were posted by Vin McLellan in the mailing list in 1998.

Vin McLellan comments
Fyi. This was posted to Coderpunks, a fairly elite mailing list for professional cryptographers. Because of rising interest in the AES process, several recent Coderpunks 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.

1. Anonymous <nobody@replay.com coments on Schnorrs remarks

Original:

Date: Wed, 29 Jul 1998 01:59:20 +0200

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

2. Schnorr’s response to nobody@replay.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 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

3. Ben Laurie ( ben@algroup.co.uk ) weighs in

Original:

Web archieve: http://web.archive.org/web/20010829222220/http://www.privacy.nb.ca/cryptography/archives/coderpunks/new/1998-08/0008.html
Archieve is link: https://archive.ph/pKoKp

Mon, 03 Aug 1998 23:10:00 +0100

schnorr wrote:
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.

At the risk of repeating Nobody, I have to say that I find this very difficult to buy. It seems to me that the logical consequence of this is that all equations are essentially the same. If division is really just addition in disguise, I’m sure we’ll all have no problem at all with the following statements:

1. Multiplication is addition.
2. Raising to a power is multiplication (and hence addition).
3. Subtraction is addition.
4. Taking a log is raising to a power (and hence multiplication, thus addition).

So, if I perform the patented operation a+b, I also cover all equations using multiplication, subtraction, division, powers and logs.

Proof:
a+b is just a+c+d, so I can add an extra operator without any trouble.
That operator can become *, /, ^, log or -. And, since I can add an infinite number of them, I guess we can include sin, cos, tan, etc.

Hence, any algebraic operation is just a+b in diguise. Q.E.D.

Cheers,
Ben.
— 
Ben Laurie            |Phone: +44 (181) 735 0686| Apache Group member
Freelance Consultant  |Fax:   +44 (181) 735 0689|http://www.apache.org/
and Technical Director|Email: ben@algroup.co.uk |
A.L. Digital Ltd,     |Apache-SSL author     http://www.apache-ssl.org/
London, England.      |”Apache: TDG” http://www.ora.com/catalog/apache/
WE’RE RECRUITING! http://www.aldigital.co.uk/recruit/

Nobodys (nobody@replay.com) replay back to Schnorr

Original:

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.

References

References
↑1 Btw if you think this is uncommon, it is not. The same is true for SHA256.

Leave a Reply