jandersonlee

2007-02-07 14:05:28 UTC

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

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