Subject: Re: [dnsext] Re: DNSCurve and alternative cryptosystems

From: Matthew Dempsky <[email-masked]>
Date: Thu, 25 Mar 2010 00:09:47 -0700

On Wed, Mar 24, 2010 at 6:12 PM, Alfred HÎnes <[email-masked]> wrote:
> (1)  Look at RFC 5639 for further alternatives wrt curves with
>     nice properties and an open process in the background,
>     (_not_ from the U.S.!) and for point compression arguments.

I'll need to review RFC 5639 in more detail, but my initial impression
at least is they seem like fine curves as well, though off hand I'm
not certain what the advantage of using one over either Curve25519
and/or NIST P-256 would be.  It doesn't seem like they would be
competitive with Curve25519 in terms of computational performance, and
at least the argument I've heard for NIST P-256 is that it has
received more peer review.

It seems there's more information about the curves at
ecc-brainpool.org, though unfortunately (for me, at least) only in
German.

> (2)  It's a rather old story that a quadratic equation has (at most)
>     two solutions, so that you can disambiguate them by a single bit.
>     The number theoretic / arithmetical arguments regarding
>     for which primes (and elliptic curves over GF(p)) squareroot
>     calculations are easier to perform have been exercised by humans
>     (students of algebra / number theory) for many decades, because
>     for manual calculations -- even for small (ridiculously small,
>     from a crypto pov) primes -- this makes the difference on whether
>     you can (construct or) solve an exercise or not (at all).
>     That's undergraduate Math, at best, from the 17th century;
>     cf. RFC 5639, Section 2.2, item 2. = bottom paragraph on page 6.)
>
>     IANAL, yet I can't believe that textbook knowledge can be
>     patented without fake claims, and I assume that most of the
>     patent blur in ECC is only relevant for specific hardware
>     implementations; but hardware technology advances much faster
>     than patent applications get accepted. ;-)

Certainly, though it seems law is a non-deterministic process, so I'd
hate to rely on that.

That said, the better argument seems to be that the point compression
needed for Diffie-Hellman was already pointed out in Miller's 1985
paper on ECC, which is prior art on Certicom's patent by several
years.  (Diffie-Hellman only uses the resulting x-coordinate, which is
independent of which y-coordinate was used anyway, so it's not
necessary to recover the sender's point; just some point with the same
x-coordinate.)

> (3)  For further reading, I suggest draft-mcgrew-fundamental-ecc ;
>     a new revision should be out soon, but the basic conclusions
>     are worked out well in the current -02 : all the math behind the
>     scene on elliptic curves and the specific application to
>     fundamental EC crypto have been scholarly published before (and
>     sometimes *long* before) said patent applications have been filed.
>     See Appendix C there for the elementary argument for why even the
>     compact point representation works in the GF(p) case, and look
>     for the algorithms reported by Donald Knuth in his famous 3-vol.
>     "Art of Computer Programming", written in the end-1960s !

Yeah, I've received a few suggestions to look at McGrew's ECC draft.
Very positively, it seems to have reversed a few people's concerns
about Certicom's point compression patent (at least with regards to
Diffie-Hellman).

> (4)  Patent laywers/judges should be advised to study the (roughly 700)
>     references listed on 39 small-font pages (pp.737-775) of:
>
>     [CFDA]   Cohen, H., Frey, G., Doche, C., Avanzi, R., Lange, T.,
>              Nguyen, K., and F. Vercauteren, "Handbook of Elliptic and
>              Hyperelliptic Curve Cryptography", Chapman & Hall CRC
>              Press, 2006.
>
>     ... and come back when they have understood the prior art.
>     (The questionable patents might have expired long ago, at
>     that point in time.)  :-)

:-)

Thanks for the feedback.