sage/gen_exhaustive_groups.sage

   1 load("secp256k1_params.sage")
   2
   3 orders_done = set()
   4 results = {}
   5 first = True
   6 for b in range(1, P):
   7     # There are only 6 curves (up to isomorphism) of the form y^2=x^3+B. Stop once we have tried all.
   8     if len(orders_done) == 6:
   9         break
  10
  11     E = EllipticCurve(F, [0, b])
  12     print("Analyzing curve y^2 = x^3 + %i" % b)
  13     n = E.order()
  14     # Skip curves with an order we've already tried
  15     if n in orders_done:
  16         print("- Isomorphic to earlier curve")
  17         continue
  18     orders_done.add(n)
  19     # Skip curves isomorphic to the real secp256k1
  20     if n.is_pseudoprime():
  21         print(" - Isomorphic to secp256k1")
  22         continue
  23
  24     print("- Finding subgroups")
  25
  26     # Find what prime subgroups exist
  27     for f, _ in n.factor():
  28         print("- Analyzing subgroup of order %i" % f)
  29         # Skip subgroups of order >1000
  30         if f < 4 or f > 1000:
  31             print("  - Bad size")
  32             continue
  33
  34         # Iterate over X coordinates until we find one that is on the curve, has order f,
  35         # and for which curve isomorphism exists that maps it to X coordinate 1.
  36         for x in range(1, P):
  37             # Skip X coordinates not on the curve, and construct the full point otherwise.
  38             if not E.is_x_coord(x):
  39                 continue
  40             G = E.lift_x(F(x))
  41
  42             print("  - Analyzing (multiples of) point with X=%i" % x)
  43
  44             # Skip points whose order is not a multiple of f. Project the point to have
  45             # order f otherwise.
  46             if (G.order() % f):
  47                 print("    - Bad order")
  48                 continue
  49             G = G * (G.order() // f)
  50
  51             # Find lambda for endomorphism. Skip if none can be found.
  52             lam = None
  53             for l in Integers(f)(1).nth_root(3, all=True):
  54                 if int(l)*G == E(BETA*G[0], G[1]):
  55                     lam = int(l)
  56                     break
  57             if lam is None:
  58                 print("    - No endomorphism for this subgroup")
  59                 break
  60
  61             # Now look for an isomorphism of the curve that gives this point an X
  62             # coordinate equal to 1.
  63             # If (x,y) is on y^2 = x^3 + b, then (a^2*x, a^3*y) is on y^2 = x^3 + a^6*b.
  64             # So look for m=a^2=1/x.
  65             m = F(1)/G[0]
  66             if not m.is_square():
  67                 print("    - No curve isomorphism maps it to a point with X=1")
  68                 continue
  69             a = m.sqrt()
  70             rb = a^6*b
  71             RE = EllipticCurve(F, [0, rb])
  72
  73             # Use as generator twice the image of G under the above isormorphism.
  74             # This means that generator*(1/2 mod f) will have X coordinate 1.
  75             RG = RE(1, a^3*G[1]) * 2
  76             # And even Y coordinate.
  77             if int(RG[1]) % 2:
  78                 RG = -RG
  79             assert(RG.order() == f)
  80             assert(lam*RG == RE(BETA*RG[0], RG[1]))
  81
  82             # We have found curve RE:y^2=x^3+rb with generator RG of order f. Remember it
  83             results[f] = {"b": rb, "G": RG, "lambda": lam}
  84             print("    - Found solution")
  85             break
  86
  87     print("")
  88
  89 print("")
  90 print("")
  91 print("/* To be put in src/group_impl.h: */")
  92 first = True
  93 for f in sorted(results.keys()):
  94     b = results[f]["b"]
  95     G = results[f]["G"]
  96     print("#  %s EXHAUSTIVE_TEST_ORDER == %i" % ("if" if first else "elif", f))
  97     first = False
  98     print("static const secp256k1_ge secp256k1_ge_const_g = SECP256K1_GE_CONST(")
  99     print("    0x%08x, 0x%08x, 0x%08x, 0x%08x," % tuple((int(G[0]) >> (32 * (7 - i))) & 0xffffffff for i in range(4)))
 100     print("    0x%08x, 0x%08x, 0x%08x, 0x%08x," % tuple((int(G[0]) >> (32 * (7 - i))) & 0xffffffff for i in range(4, 8)))
 101     print("    0x%08x, 0x%08x, 0x%08x, 0x%08x," % tuple((int(G[1]) >> (32 * (7 - i))) & 0xffffffff for i in range(4)))
 102     print("    0x%08x, 0x%08x, 0x%08x, 0x%08x" % tuple((int(G[1]) >> (32 * (7 - i))) & 0xffffffff for i in range(4, 8)))
 103     print(");")
 104     print("static const secp256k1_fe secp256k1_fe_const_b = SECP256K1_FE_CONST(")
 105     print("    0x%08x, 0x%08x, 0x%08x, 0x%08x," % tuple((int(b) >> (32 * (7 - i))) & 0xffffffff for i in range(4)))
 106     print("    0x%08x, 0x%08x, 0x%08x, 0x%08x" % tuple((int(b) >> (32 * (7 - i))) & 0xffffffff for i in range(4, 8)))
 107     print(");")
 108 print("#  else")
 109 print("#    error No known generator for the specified exhaustive test group order.")
 110 print("#  endif")
 111
 112 print("")
 113 print("")
 114 print("/* To be put in src/scalar_impl.h: */")
 115 first = True
 116 for f in sorted(results.keys()):
 117     lam = results[f]["lambda"]
 118     print("#  %s EXHAUSTIVE_TEST_ORDER == %i" % ("if" if first else "elif", f))
 119     first = False
 120     print("#    define EXHAUSTIVE_TEST_LAMBDA %i" % lam)
 121 print("#  else")
 122 print("#    error No known lambda for the specified exhaustive test group order.")
 123 print("#  endif")
 124 print("")