gen_exhaustive_groups.sage (5972B)
1 load("haskellsecp256k1_v0_1_0_params.sage") 2 3 MAX_ORDER = 1000 4 5 # Set of (curve) orders we have encountered so far. 6 orders_done = set() 7 8 # Map from (subgroup) orders to [b, int(gen.x), int(gen.y), gen, lambda] for those subgroups. 9 solutions = {} 10 11 # Iterate over curves of the form y^2 = x^3 + B. 12 for b in range(1, P): 13 # There are only 6 curves (up to isomorphism) of the form y^2 = x^3 + B. Stop once we have tried all. 14 if len(orders_done) == 6: 15 break 16 17 E = EllipticCurve(F, [0, b]) 18 print("Analyzing curve y^2 = x^3 + %i" % b) 19 n = E.order() 20 21 # Skip curves with an order we've already tried 22 if n in orders_done: 23 print("- Isomorphic to earlier curve") 24 print() 25 continue 26 orders_done.add(n) 27 28 # Skip curves isomorphic to the real secp256k1 29 if n.is_pseudoprime(): 30 assert E.is_isomorphic(C) 31 print("- Isomorphic to secp256k1") 32 print() 33 continue 34 35 print("- Finding prime subgroups") 36 37 # Map from group_order to a set of independent generators for that order. 38 curve_gens = {} 39 40 for g in E.gens(): 41 # Find what prime subgroups of group generated by g exist. 42 g_order = g.order() 43 for f, _ in g.order().factor(): 44 # Skip subgroups that have bad size. 45 if f < 4: 46 print(f" - Subgroup of size {f}: too small") 47 continue 48 if f > MAX_ORDER: 49 print(f" - Subgroup of size {f}: too large") 50 continue 51 52 # Construct a generator for that subgroup. 53 gen = g * (g_order // f) 54 assert(gen.order() == f) 55 56 # Add to set the minimal multiple of gen. 57 curve_gens.setdefault(f, set()).add(min([j*gen for j in range(1, f)])) 58 print(f" - Subgroup of size {f}: ok") 59 60 for f in sorted(curve_gens.keys()): 61 print(f"- Constructing group of order {f}") 62 cbrts = sorted([int(c) for c in Integers(f)(1).nth_root(3, all=true) if c != 1]) 63 gens = list(curve_gens[f]) 64 sol_count = 0 65 no_endo_count = 0 66 67 # Consider all non-zero linear combinations of the independent generators. 68 for j in range(1, f**len(gens)): 69 gen = sum(gens[k] * ((j // f**k) % f) for k in range(len(gens))) 70 assert not gen.is_zero() 71 assert (f*gen).is_zero() 72 73 # Find lambda for endomorphism. Skip if none can be found. 74 lam = None 75 for l in cbrts: 76 if l*gen == E(BETA*gen[0], gen[1]): 77 lam = l 78 break 79 80 if lam is None: 81 no_endo_count += 1 82 else: 83 sol_count += 1 84 solutions.setdefault(f, []).append((b, int(gen[0]), int(gen[1]), gen, lam)) 85 86 print(f" - Found {sol_count} generators (plus {no_endo_count} without endomorphism)") 87 88 print() 89 90 def output_generator(g, name): 91 print(f"#define {name} SECP256K1_GE_CONST(\\") 92 print(" 0x%08x, 0x%08x, 0x%08x, 0x%08x,\\" % tuple((int(g[0]) >> (32 * (7 - i))) & 0xffffffff for i in range(4))) 93 print(" 0x%08x, 0x%08x, 0x%08x, 0x%08x,\\" % tuple((int(g[0]) >> (32 * (7 - i))) & 0xffffffff for i in range(4, 8))) 94 print(" 0x%08x, 0x%08x, 0x%08x, 0x%08x,\\" % tuple((int(g[1]) >> (32 * (7 - i))) & 0xffffffff for i in range(4))) 95 print(" 0x%08x, 0x%08x, 0x%08x, 0x%08x\\" % tuple((int(g[1]) >> (32 * (7 - i))) & 0xffffffff for i in range(4, 8))) 96 print(")") 97 98 def output_b(b): 99 print(f"#define SECP256K1_B {int(b)}") 100 101 print() 102 print("To be put in src/group_impl.h:") 103 print() 104 print("/* Begin of section generated by sage/gen_exhaustive_groups.sage. */") 105 for f in sorted(solutions.keys()): 106 # Use as generator/2 the one with lowest b, and lowest (x, y) generator (interpreted as non-negative integers). 107 b, _, _, HALF_G, lam = min(solutions[f]) 108 output_generator(2 * HALF_G, f"SECP256K1_G_ORDER_{f}") 109 print("/** Generator for secp256k1, value 'g' defined in") 110 print(" * \"Standards for Efficient Cryptography\" (SEC2) 2.7.1.") 111 print(" */") 112 output_generator(G, "SECP256K1_G") 113 print("/* These exhaustive group test orders and generators are chosen such that:") 114 print(" * - The field size is equal to that of secp256k1, so field code is the same.") 115 print(" * - The curve equation is of the form y^2=x^3+B for some small constant B.") 116 print(" * - The subgroup has a generator 2*P, where P.x is as small as possible.") 117 print(f" * - The subgroup has size less than {MAX_ORDER} to permit exhaustive testing.") 118 print(" * - The subgroup admits an endomorphism of the form lambda*(x,y) == (beta*x,y).") 119 print(" */") 120 print("#if defined(EXHAUSTIVE_TEST_ORDER)") 121 first = True 122 for f in sorted(solutions.keys()): 123 b, _, _, _, lam = min(solutions[f]) 124 print(f"# {'if' if first else 'elif'} EXHAUSTIVE_TEST_ORDER == {f}") 125 first = False 126 print() 127 print(f"static const haskellsecp256k1_v0_1_0_ge haskellsecp256k1_v0_1_0_ge_const_g = SECP256K1_G_ORDER_{f};") 128 output_b(b) 129 print() 130 print("# else") 131 print("# error No known generator for the specified exhaustive test group order.") 132 print("# endif") 133 print("#else") 134 print() 135 print("static const haskellsecp256k1_v0_1_0_ge haskellsecp256k1_v0_1_0_ge_const_g = SECP256K1_G;") 136 output_b(7) 137 print() 138 print("#endif") 139 print("/* End of section generated by sage/gen_exhaustive_groups.sage. */") 140 141 142 print() 143 print() 144 print("To be put in src/scalar_impl.h:") 145 print() 146 print("/* Begin of section generated by sage/gen_exhaustive_groups.sage. */") 147 first = True 148 for f in sorted(solutions.keys()): 149 _, _, _, _, lam = min(solutions[f]) 150 print("# %s EXHAUSTIVE_TEST_ORDER == %i" % ("if" if first else "elif", f)) 151 first = False 152 print("# define EXHAUSTIVE_TEST_LAMBDA %i" % lam) 153 print("# else") 154 print("# error No known lambda for the specified exhaustive test group order.") 155 print("# endif") 156 print("/* End of section generated by sage/gen_exhaustive_groups.sage. */")