Code Poetry
and Text Adventures

by catid posted (>30 days ago) 12:34am Fri. Oct 11th 2013 PDT
Here's my MAGMA script (first I've ever written, and all from scratch, and it worked! :) to test the claim of http://www.chesworkshop.org/ches2010/presentations/CHES2010_Session02_Talk03.pdf that the curve they specify for "ted1271gls" on slide 20 has secure group order (though not on its twist):

p := 2^127-1;
K<w> := GF(p^2);

mu := 2 + w;
aa := -mu;
dd := 109*mu;

A2 := 2 * (aa + dd) / (aa - dd);
A4 := 4 / (aa - dd);
A := 1 / (A4 * A4) - A2 * A2 / (3 * A4 * A4);
B := -A2 * A2 * A2 / (27 * A4 * A4 * A4) - A2 * A / (3 * A4);

E := EllipticCurve([K | A, B]);
ETwists := Twists(E);
print ETwists;
time [ SEA(F : MaxSmooth := 1) : F in ETwists ];

EP := $1[1];
TP := $1[2];

if EP mod 8 eq 0 then
   TEST := IsPrime(EP div 8);
else
   if EP mod 4 eq 0 then
      TEST := IsPrime(EP div 4);
   else
      if EP mod 2 eq 0 then
           TEST := IsPrime(EP div 2);
      else
           TEST := IsPrime(EP);
      end if;
   end if;
end if;

if TEST eq true then
   print "TWISTED EDWARDS CURVE IS GOOD";
else
   print "TWISTED EDWARDS CURVE SUCKS";
end if;

Factorization(EP):Hex;

if TP mod 8 eq 0 then
   TTEST := IsPrime(TP div 8);
else
   if TP mod 4 eq 0 then
      TTEST := IsPrime(TP div 4);
   else
      if TP mod 2 eq 0 then
           TTEST := IsPrime(TP div 2);
      else
           TTEST := IsPrime(TP);
      end if;
   end if;
end if;

if TTEST eq true then
   print "QUADRATIC TWIST IS GOOD";
else
   print "QUADRATIC TWIST SUCKS";
end if;

Factorization(TP):Hex;

You can plug it into the Wolfram Alpha-like web calculator for free!

http://magma.maths.usyd.edu.au/calc/

The result?

[
   Elliptic Curve defined by y^2 = x^3 + (170141183460469231731687303715884104\
      864*w + 127605887595351923798765477786913078648)*x +
      (85070591730234615865843651857942031430*w +
      170141183460469231731687303715884101830) over
   GF(170141183460469231731687303715884105727^2),
   Elliptic Curve defined by y^2 = x^3 + (108862929589523551023699670699203009\
      961*w + 21468635481913102246467482002211501024)*x +
      (17218003551755020253627573229434217032*w +
      98219829738602315410342339074910081680) over
   GF(170141183460469231731687303715884105727^2)
]
[ 28948022309329048855892746252171976962839764946219840790663900086538002237076\
, 28948022309329048855892746252171976963114662652758564302138142702555026159984
]
Time: 0.700
TWISTED EDWARDS CURVE IS GOOD
[ <0x2, 0x2>, <0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA6261414C0DC87D3CE9B68E3B09E01A\
5, 0x1> ]
QUADRATIC TWIST SUCKS
[ <0x2, 0x4>, <0x3, 0x1>, <0xB, 0x1>, <0xB5, 0x1>, <0x1BB, 0x1>, <0x6FD, 0x1>,
<0xBE1, 0x1>, <0x13A3F, 0x1>, <0x8A0294E0A83BD, 0x1>, <0xB70D128AE7CDB, 0x1>,
<0xA549F5E1958F2FA60EBE25, 0x1> ]

This indicates that the group order is 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA6261414C0DC87D3CE9B68E3B09E01A5 (a large prime) * 4, which is just perfect.

This makes it indeed suitable for use as expected.  I read in another paper that GLS curves always have insecure twists, though I haven't looked into it much.  I'm not worried about twist security since I can just test if a point is on MY curve with a few cheap field operations.

Also as a side comment..  0.7 SECONDS?  Man, the MIRACL version of SEA runs in like 10+ seconds to do an Fp field with several minutes of pre-calculation based on my choice of p.  MAGMA is an amazing piece of work.
last edit by catid edited (>30 days ago) 12:44am Fri. Oct 11th 2013 PDT