61 views

Skip to first unread message

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

government. See www.nist.gov/encryption.

Also see www.certicom.com for Certicom's response.

Don Johnson

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

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

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

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.

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

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

to

In <19990616142640...@ng-ba1.aol.com> djohn...@aol.com (DJohn37050) writes:

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

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.

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

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

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

always one of (1,2,4), in other words very small and therefore efficient.

Don Johnson

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

>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

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.

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

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

X9.31. And RSA is patented.

Don Johnson

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu