From: "Michael Scott"
Subject: Re: NIST annouces set of Elliptic Curves
Date: 1999/06/17
Message-ID: #1/1
X-Deja-AN: 490770216
References: <7k9hti$aia$1@nntp.ucs.ubc.ca> <19990617083729.23150.00000685@ng-bh1.aol.com>
X-Priority: 3
X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2014.211
X-Complaints-To: ne...@indigo.ie
X-Trace: news.indigo.ie 929644382 194.125.134.3 (Thu, 17 Jun 1999 19:33:02 BST)
Organization: Indigo
X-MSMail-Priority: Normal
NNTP-Posting-Date: Thu, 17 Jun 1999 19:33:02 BST
Newsgroups: sci.crypt
DJohn37050 wrote in message
news:19990617083729.23150.00000685@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