I'm curious about the suggestion by many sources to use "random"
primes as the basis for ECC curves.
I'm trying to set-up a very fast ECC signature for a data storage
application. Existing ECC code that I've found would still be a
bottleneck for our suggested use.
I'd thought of using a Sophie-Germain prime of the form 2^256-k where
k>2^64 for faster reduction mod P. I can fit all of the intermediate
values into registers on an x86_64 processor. It runs very fast on a
P4 and should REALLY fly on an Opteron where mulq, adcq and cmovq are
much faster.
I'd also thought to select (using repeated CM) a curve of the form
y^2=x^3-3x+B such that the order of the curve and the twist were BOTH
prime.
Is there some reason why either or both of these constraints would be
unsafe? Or any less safe than using a "random" prime or a curve with
a non-prime twist?
For example:
$ ./cm -P8 -K4 -f '2#256-486617' -D760246
P mod 8 = 7
P is 256 bits long
precomputations...
precision in bits = 8192
finding a curve...
D= 760246
IEEE-1363 invariant
D mod 24 = 22
K= 2
class number= 328
Group order=
57896044618658097711785492504343953926835082532051768541511402735613617706147
....
Factoring polynomial of degree 328 .....
MOV condition OK
Curve and Point Found
A= -3
B=
10461052262067418432029296883110255337651535834336523137026837659014063179578
P=
115792089237316195423570985008687907853269984665640564039457584007913129153319
R=
57896044618658097711785492504343953926835082532051768541511402735613617706147
a 256 bit prime
X=
115792089237316195423570985008687907853269984665640564039457584007913129153317
Y=
107420487527028641091125152525469544946213297697233298362514191121927149860183
....
finding a curve...
D= 760246
IEEE-1363 invariant
D mod 24 = 22
K= 2
class number= 328
Group order=
57896044618658097711785492504343953926434902133588795497946181272299511447173
and the twist:
A= -3
B=
13335028199107769614354719600658899160201794809019996768801096716318835014890
P=
115792089237316195423570985008687907853269984665640564039457584007913129153319
R=
57896044618658097711785492504343953926434902133588795497946181272299511447173
a 255 bit prime
X=
115792089237316195423570985008687907853269984665640564039457584007913129153317
Y=
5000577050882402382523257384066484129098669552438136997044589908542598826867
Thanks.
Jeff Anderson-Lee
Petabyte Storage Infrastructure Project
University of California Berkeley
