Re: The curve NIST forgot


"Mark Wooding" <mdw@xxxxxxxxxxxxxxxx> wrote in message news:slrnevcub0.7lh.mdw@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Michael Scott <mscott@xxxxxxxxx> wrote:

Might I therefore suggest the prime p=2^160-2^112+2^64+1, and the curve
y^2=x^3-3x+157, which has prime order (so does its twist).

The curve looks fine to me.

For reference, the curve has

n = 1461501637330897725906824301401491257823677986243

points; n is indeed prime. The twist has

n' = 1461501637330897725906828294412711208642947762753
= 11 * 131 * 1014227368029769414230970363922769749231747233

which (as you corrected) isn't prime, but does at least have a large
subgroup.

The curve's embedding degree is

k = 730750818665448862953412150700745628911838993121

which doesn't seem especially pairing-friendly ;-).

Finally, the point

P = (1379503692774293168437708444156773627598629810694,
902946743485719274016882346771599421261933499314)

is on the curve, and (obviously) has order n.

(Computations performed by Sage, largely using PARI underneath; point
counting using Schoof-Elkies-Atkin implemented by Doche and Duquesne.)

Do you mind if I add this curve to the collection in my crypto library
(probably as `scott-p160')?


Yes of course you can add it.

One problem with a modulus like this is that calculating modular square roots is "annoying" to use Dan Bernstein's description http://citeseer.ist.psu.edu/462632.html, as p-1 has 2^64 as a factor. This is an important issue if using point compression. However I found a nice algorithm for modular square roots by Siguna Mueller (Designs, Codes and Crypto 2004) http://www.springerlink.com/content/jr028wl3m6036741/, which seems to be very efficient in these cases. It requires Jacobi symbol calculations and the calculation of a Lucas sequence V_{(p-1)/4}(P,1), but this is pretty standard stuff.


Mike


-- [mdw]

.

Relevant Pages

  • Re: EC-PRNG
    ... > Cristiano wrote: ... Grab a point, any point, from a curve of order n ... > prime order, is a most egregious and elementary mistake. ... You are rude without any reason because we are talking about the generator ...
    (sci.crypt)
  • Re: How does spin improve an arrows perfomance?
    ... >>>Has anyone got a formula for calculating the area of shaped fletchings then? ... >>>Or am I being dull and everyone but me is using square fletchings? ... develop a formula for the curve of the vane and graph ...
    (rec.sport.archery)
  • Re: ECC point at infinity
    ... p. That's not universally true for all fields/representations so your ... The curve has a prime order. ... since the order of the prime field curves ...
    (sci.crypt)
  • Re: Elliptic Curves and Orders
    ... > in elliptic curve cryptography, we need the order of the field (we choose ... Every point on the curve (except the point at infinity) is a generator ... prime order than curves with order prime times a small cofactor (I can ... Plus, if the cofactor is small, essentially all points ...
    (sci.crypt)
  • Re: ECC
    ... >> This is with reference to Elliptic Curve Cryptography in polynomial ... >> Could any one tell me weather the ORDER of points on the curve is same ... You may be confusing this with use of a prime order ... There is a point that is normally called the "point at infinity". ...
    (sci.crypt)