Re: Verifying Elliptic Curve Cryptography

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* James Cloos [2017-02-15 23:27]:
> I've read examples in sage, but pari/gp is more readily available
> on my systems, so:
> 
> Does anyone have any sample code in gp for working with modern curves?
> 
> I'm interested in the math for things like ecdh or eddsa using
> "safe" curves (cf: http://safecurves.cr.yp.to).
> 
> I take it that sage's EllipticCurve() uses pari's ellinit(), yes?
> 
> I haven't done much with pari's elliptic curve support.
> 
> In particular, how can one use a curve like e:521:
> 
>   x^2+y^2 = 1-376014x^2y^2
>   modulo p = 2^521 - 1
> 
> given that ellinit doesn't take an x²y² coefficient?

You can't directly, but you can replace that curve by an equivalent
model and work there :

  p = 2^521-1;
  e = ellfromeqn(x^2+y^2 - (1 - 376014*x^2*y^2));
  E = ellinit(e, p);

  N = ellcard(E)   \\ this requires the 'seadata' package
  time = 1min, 25,056 ms.
  %4 = 6864797660130609714981900799081393217269435300143305409394463459185543183397654701903506606654631398546774636260936570417277131794810169271973685174680434092
  factor(N)
  time = 10 ms.
  %5 = 
  [2 2]

  [1716199415032652428745475199770348304317358825035826352348615864796385795849413675475876651663657849636693659065234142604319282948702542317993421293670108523
  1]

N.B. In current PARI inplementation, you can't easily
1) find a *map* from one model to the other (you just get a Weistrass model)
2) use special properties of the original model (e.g. unified formula
on Edwards curve)

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`