1 load("secp256k1_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 secp256k1_ge secp256k1_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 secp256k1_ge secp256k1_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. */")
157