Cringely Gives KnowNow Some Unbelievable Free Press...

Robert Harley
Sun, 27 Jan 2002 21:10:09 +0100 (CET)

Adam Beberg wrote:
>I'm preaty sure the reason we're all using RSA _now_ is the same reason we
>were using DH a couple years ago - the patents are all expired. ECC has a
>bunch of patents still living, and the word among the crypto crowd I know is
>still "avoid like the plague".

I usually have no particular desire to respond to Beberg's negativism,
but I suppose that I should do so this time.

The basic patent on RSA has expired (RSA was widely used before that
too - you might have noticed).  An equivalent basic patent on ECC
never existed.

There are various other patents to be aware of, and this is the case
whether you're working with ECC or RSA, or making paper clips.  You
can avoid them if you know what you're doing, and walk right into them
if you don't.

For instance RSA Security holds a patent on fast exponentiation, which
can be used for RSA or ECC (but not paper clips, AFAIK).

Various protocols, whether used over RSA or ECC, are patented.  The
Diffie-Hellman patent expired (before that people often used El Gamal
instead).  Other protocols such as Nyberg-Rueppel or
Menezes-Qu-Vanstone are still covered.

Specific to ECC:

There are Crandall's patents on using certain primes of a special
form.  So don't use them.  I recommend using random primes anyway
(patent or no patent) or else binary fields.

The NSA has patented a particular exponentiation algorithm for Koblitz
curves.  So don't use it.  However they will probably place it in the
public domain like their DSA patent.  I recommend not using Koblitz
curves anyway (patent or no patent).

Certicom has some patents on fast arithmetic (whether for ECC or other
stuff) but they cover circuit designs for finite-field multipliers,
with low transistor count and/or using normal bases.  They are
irrelevant for software and irrelevant for polynomial bases which I
recommend anyway.  For hardware they can be avoided e.g., Siemens has
ECC hardware which doesn't infringe.

I think the only patents of particular note for ECC are Certicom and
H.P.'s ones on point-compression.

For DH, you just use the x-coordinate so you don't need points, never
mind point-compression.  For signatures such as ECDSA, you need points
so just use them uncompressed.  It makes very little difference.

The issue is if you want to verify signatures produced by somebody
else who used point-compression.  I would hazard a guess that in such
a situation it would be OK to check the x-coordinate and ignore the
one bit of extra information in y (but I would have to study the
details to be sure).

Patents are a pain in the ass but, in this instance at least, they
hardly constitute a minefield.

>We wont be touching ECC for a very long time.


     .-.                              .-.
    /   \           .-.      Software Development       .-.           /   \
   /     \         /   \       .-.     _     .-.       /   \         /     \
  /       \       /     \     /   \   / \   /   \     /     \       /       \
 /         \     /       \   /     `-'   `-'     \   /       \     /         \
            \   /         `-'       ArgoTech      `-'         \   /
             `-'                    `-'