NIST annouces set of Elliptic Curves

60 views
Skip to first unread message

DJohn37050

unread,
Jun 15, 1999, 3:00:00 AM6/15/99
to
NIST has recently announced a set of Elliptic Curves for use with U.S.
government. See www.nist.gov/encryption.
Also see www.certicom.com for Certicom's response.
Don Johnson

DJohn37050

unread,
Jun 16, 1999, 3:00:00 AM6/16/99
to
The curves annouced by NIST fall into 3 classes:
1. Random curves over a prime order field (Fp).
2. Random curves over a field of characteristic 2 with a prime power (F2**p).
3. Koblitz curves (binary anomalous curves) over a field of characteristic 2
with a prime power (F2**p).

Some interesting observations:
1. Curves over both prime fields and characteristic 2 fields are included.
2. There are no curves over a field of characteristic 2 with a composite power
(F2**m, with m composite).
3. Koblitz curves are included.
Don Johnson

Medical Electronics Lab

unread,
Jun 16, 1999, 3:00:00 AM6/16/99
to

Thanks Don. It certainly adds a nice stamp
of approval.

There are 2 formats, ascii and postscript.
The postscript form has a lot of explanation,
the ascii is just the curve data.

Patience, persistence, truth,
Dr. mike

DJohn37050

unread,
Jun 16, 1999, 3:00:00 AM6/16/99
to
Yes, perhaps the most interesting thing is that this can be seen as an
endorsement of the security of ECC (at least for the curves provided) by an
agency of the US government.

The postscript file also gives an (approximate) security level appropriateness
of the curves to various symmetric key sizes.

All in all, good stuff.
Don Johnson

Bill Unruh

unread,
Jun 17, 1999, 3:00:00 AM6/17/99
to

>Yes, perhaps the most interesting thing is that this can be seen as an
>endorsement of the security of ECC (at least for the curves provided) by an
>agency of the US government.

Of course if you are paranoid, this means that these are the curves for
which they have found a crack. But of course none of us is paranoid.

DJohn37050

unread,
Jun 17, 1999, 3:00:00 AM6/17/99
to
These are curves which are approved for use by the US Federal Government to
protect their sensitive but unclassified data. This is an endorsement.

Also, the random curves should help alleviate some fears. I am sure all the
published curves will be studied.

And the random curves would present an interesting question to someone trying
to create a random weak curve. Namely, how prevalent can a (otherwise
unknown) "weak" curve be and still be found via a random seed? If it is too
rare, it is difficult to find using a seed, if it is too common, it will likely
be discovered by someone else.
Don Johnson

John Savard

unread,
Jun 17, 1999, 3:00:00 AM6/17/99
to
Medical Electronics Lab <ros...@physiology.wisc.edu> wrote, in part:

>There are 2 formats, ascii and postscript.
>The postscript form has a lot of explanation,
>the ascii is just the curve data.

Thanks for the info: since I find postscript somewhat awkward to read,
I hesitated to download it. Now I'll take the time to deal with this.

John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/crypto.htm

DJohn37050

unread,
Jun 17, 1999, 3:00:00 AM6/17/99
to
Another interesting point about all the NIST curves is that the cofactor is
always one of (1,2,4), in other words very small and therefore efficient.
Don Johnson

Michael Scott

unread,
Jun 17, 1999, 3:00:00 AM6/17/99
to

DJohn37050 <djohn...@aol.com> wrote in message
news:19990617083729...@ng-bh1.aol.com...

> These are curves which are approved for use by the US Federal Government
> to protect their sensitive but unclassified data. This is an endorsement.
> Also, the random curves should help alleviate some fears. I am sure all
the
> published curves will be studied.
>
> And the random curves would present an interesting question to someone
> trying to create a random weak curve. Namely, how prevalent can a
>otherwise unknown) "weak" curve be and still be found via a random seed?

>If it is too rare, it is difficult to find using a seed, if it is too
common,
>it will likely be discovered by someone else.

And thats the problem....

These curves are generated by passing a random seed S through a one-way
process which creates the B parameter for the curve y^2=x^3-3x+B mod p. (I
am talking about the GF(p) curves but my remarks apply to GF(2^m) as well.).
Where the random seed S came from, nobody knows.

Now if the idea is to increase our confidence that these curves are
therefore completely randomly selected from the vast number of possible
elliptic curves and hence likely to be secure, I think this process fails.
The underlying assumption is that the vast majority of curves are "good".
Consider now the possibility that one in a million of all curves have an
exploitable structure that "they" know about, but we don't.. Then "they"
simply generate a million random seeds until they find one that generates
one of "their" curves. Then they get us to use them. And remember the
standard paranoia assumptions apply - "they" have computing power way beyond
what we can muster. So maybe that could be 1 billion.

A much simpler approach would generate more trust. Simply select B as an
integer formed from the maximum number of digits of pi that provide a number
B which is less that p.Then keep incrementing B until the number of points
on the curve is prime. Such a curve will be accepted as "random" as all
would accept that the decimal digits of pi have no unfortunate interaction
with elliptic curves. We would all accept that such a curve had not been
specially "cooked".

So, sigh, why didn't they do it that way? Do they want to be distrusted?


--
Mike Scott
-----------------------------------------
Fastest is best. MIRACL multiprecision C/C++ library for big number
cryptography
ftp://ftp.compapp.dcu.ie/pub/crypto/miracl.zip

> Don Johnson

John Savard

unread,
Jun 17, 1999, 3:00:00 AM6/17/99
to
"Michael Scott" <msc...@indigo.ie> wrote, in part:

>So, sigh, why didn't they do it that way? Do they want to be distrusted?

I suppose they feel that they are not distrusted, and therefore are
free to select optimal curves, just as the S-boxes in DES were
optimal, rather than being generated from pi or something. One notes
that many of the AES candidates had their S-boxes generated in ways
that were intended to show that nothing funny was going on.

John Savard

unread,
Jun 17, 1999, 3:00:00 AM6/17/99
to
djohn...@aol.com (DJohn37050) wrote, in part:

>NIST has recently announced a set of Elliptic Curves for use with U.S.
>government. See www.nist.gov/encryption.
>Also see www.certicom.com for Certicom's response.

And, although the basic idea of using elliptic curves
cryptographically is not patented, there are patents covering the
efficient algorithms that are used in practice to implement ECC.

Which shows that NIST is not averse to using patented technology,
_when doing so is indicated by the state of the market_.

DJohn37050

unread,
Jun 18, 1999, 3:00:00 AM6/18/99
to
NIST has also said it will extend DSS to include an RSA signature based on
X9.31. And RSA is patented.
Don Johnson

Reply all
Reply to author
Forward
0 new messages