1 /*
2
3 curve.c - code for computing cm curves
4
5 Copyright (C) 2009 Andreas Enge
6
7 This file is part of CM.
8
9 CM is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the
11 Free Software Foundation; either version 3 of the license, or (at your
12 option) any later version.
13
14 CM is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 for more details.
18
19 You should have received a copy of the GNU General Public License along
20 with CM; see the file COPYING. If not, write to the Free Software
21 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
22 */
23
24 #include "cm_class-impl.h"
25
26 static bool curve_is_crypto (mpz_t l, mpz_t c, mpz_t n, int_cl_t d,
27 mpz_t p, bool verbose);
28 static void curve_compute_param (mpz_t p, mpz_t n, mpz_t l, mpz_t c,
29 int_cl_t d, int fieldsize, bool verbose);
30
31 /*****************************************************************************/
32
curve_is_crypto(mpz_t l,mpz_t c,mpz_t n,int_cl_t d,mpz_t p,bool verbose)33 static bool curve_is_crypto (mpz_t l, mpz_t c, mpz_t n, int_cl_t d,
34 mpz_t p, bool verbose)
35 /* checks whether n might be a cryptographically secure cardinality for a */
36 /* curve over F_p with discriminant d */
37 /* first tests if n, divided by a small cofactor, becomes a prime; if */
38 /* yes, the prime is returned via l, and the cofactor via c */
39 /* The cofactor which must be admitted depends on the discriminant; */
40 /* 4 : d = 1 (8); 4 | d and d/4 = 0 or 1 (4) */
41 /* 2 : 4 | d and d/4 = 2 or 3 (4); */
42 /* 1 : d = 5 (8) */
43 /* Watch out: Divisibility by the cofactor itself is not tested! */
44 /* Then tests for supersingular, anomalous and MOV curves. */
45
46 {
47 mpz_t t, rem;
48 int k;
49
50 if (d % 4 == 0)
51 {
52 if (d % 16 == 0 || ((d / 4) - 1) % 4 == 0)
53 {
54 mpz_tdiv_q_2exp (l, n, 2);
55 mpz_set_ui (c, 4);
56 }
57 else
58 {
59 mpz_tdiv_q_2exp (l, n, 1);
60 mpz_set_ui (c, 2);
61 }
62 }
63 else if ((d - 1) % 8 == 0)
64 {
65 mpz_tdiv_q_2exp (l, n, 2);
66 mpz_set_ui (c, 4);
67 }
68 else
69 {
70 mpz_set (l, n);
71 mpz_set_ui (c, 1);
72 }
73
74 if (!cm_nt_is_prime (l)) {
75 if (verbose)
76 printf (".");
77 return false;
78 }
79
80 mpz_init (t);
81 mpz_init (rem);
82 mpz_sub (t, n, p);
83 mpz_sub_ui (t, t, 1);
84 mpz_abs (t, t);
85
86 if (mpz_cmp_ui (t, 0) == 0)
87 {
88 printf ("S");
89 return false;
90 }
91 else if (mpz_cmp_ui (t, 1) == 0)
92 {
93 printf ("A");
94 return false;
95 }
96
97 /* testing the MOV condition that q does not divide p^k - 1 for small */
98 /* values of k */
99 k = 1;
100 mpz_set (t, p);
101 mpz_mod (rem, t, l);
102 while (k <= 9 && mpz_cmp_ui (rem, 1) != 0)
103 {
104 k++;
105 mpz_mul (t, t, p);
106 mpz_mod (rem, t, l);
107 }
108 if (k <= 9)
109 {
110 printf ("M%i", k);
111 return false;
112 }
113
114 mpz_clear (t);
115 mpz_clear (rem);
116
117 return true;
118 }
119
120 /*****************************************************************************/
121
curve_compute_param(mpz_t p,mpz_t n,mpz_t l,mpz_t c,int_cl_t d,int fieldsize,bool verbose)122 static void curve_compute_param (mpz_t p, mpz_t n, mpz_t l, mpz_t c,
123 int_cl_t d, int fieldsize, bool verbose)
124 /* computes the curve parameters p (size of prime field), n (cardinality */
125 /* of curve), l (prime order of point) and c (n/l) */
126 /* Try u and v until u^2 - v^2 d is 4 times a prime. Congruences of u and */
127 /* v modulo 2 and 4 are taken into account, also to make sure that the */
128 /* cofactor of the curve cardinality can be as small as possible. */
129 /* Conditions: */
130 /* d = 5 (8): u odd, v odd (cofactor 1) */
131 /* d = 1 (8): u = 2 (4), v = 0 (4) (cofactor 4) */
132 /* or u = 0 (4), v = 2 (4) (cofactor 4, sometimes even higher) */
133 /* 4 | d, d/4 = 2 (4): u = 2 (4), v odd (cofactor 2) */
134 /* 4 | d, d/4 = 3 (4): u = 0 (4), v odd (cofactor 2) */
135 /* 4 | d, d/4 = 1 (4): u = 2 (4), v even (cofactor 4) */
136 /* or u = 0 (4), v odd (cofactor 8) */
137 /* 4 | d, d/4 = 0 (4): u = 2 (4) (cofactor 4) */
138 /* To simplify the implementation, we step through the u and v in steps */
139 /* of 4. */
140 {
141 mpz_t u, v, tmp;
142 long unsigned int v_start;
143 bool found = false;
144 int deltav = 1000;
145
146 if (fieldsize % 2 != 0)
147 fieldsize++;
148
149 mpz_init (u);
150 mpz_init (v);
151 mpz_init (tmp);
152
153 mpz_set_ui (u, 1);
154 mpz_mul_2exp (u, u, (fieldsize + 2) / 4);
155 mpz_sub_ui (u, u, 2);
156 mpz_mul_2exp (u, u, (fieldsize + 4) / 4);
157 v_start = 1;
158
159 /* so far, u is divisible by 4; update */
160 if ((d - 5) % 8 == 0)
161 mpz_add_ui (u, u, 1);
162 else if (d % 8 == 0)
163 mpz_add_ui (u, u, 2);
164 else if ((d - 1) % 8 == 0 || (d % 4 == 0 && (d / 4 - 1) % 4 == 0))
165 {
166 mpz_add_ui (u, u, 2);
167 v_start = 4;
168 }
169
170 while (!found)
171 {
172 if (deltav == 1000)
173 {
174 mpz_add_ui (u, u, 4);
175 mpz_set_ui (v, v_start);
176 deltav = 0;
177 }
178 else
179 {
180 mpz_add_ui (v, v, 4);
181 deltav++;
182 }
183
184 mpz_mul (tmp, u, u);
185 mpz_pow_ui (p, v, 2);
186 mpz_mul_si (p, p, d);
187 mpz_sub (p, tmp, p);
188 /* should be divisible by 4... */
189 mpz_tdiv_q_2exp (p, p, 2);
190 if (cm_nt_is_prime (p))
191 {
192 mpz_add_ui (n, p, 1);
193 mpz_sub (n, n, u);
194 if (curve_is_crypto (l, c, n, d, p, verbose))
195 found = true;
196 else
197 {
198 mpz_add_ui (n, p, 1);
199 mpz_add (n, n, u);
200 if (curve_is_crypto (l, c, n, d, p, verbose))
201 found = true;
202 }
203 }
204 }
205
206 if (verbose) {
207 printf ("p = "); mpz_out_str (stdout, 10, p); printf ("\n");
208 printf ("u = "); mpz_out_str (stdout, 10, u); printf ("\n");
209 printf ("v = "); mpz_out_str (stdout, 10, v); printf ("\n");
210 printf ("n = "); mpz_out_str (stdout, 10, n); printf ("\n");
211 printf ("l = "); mpz_out_str (stdout, 10, l); printf ("\n");
212 printf ("N/l = "); mpz_out_str (stdout, 10, c); printf ("\n");
213 }
214
215 mpz_clear (u);
216 mpz_clear (v);
217 mpz_clear (tmp);
218 }
219
220 /*****************************************************************************/
221
cm_curve_compute_curve(int_cl_t d,char inv,int fieldsize,const char * modpoldir,bool readwrite,bool print,bool verbose)222 void cm_curve_compute_curve (int_cl_t d, char inv, int fieldsize,
223 const char* modpoldir, bool readwrite, bool print, bool verbose)
224 /* computes a curve with the good number of points, using the given */
225 /* invariant */
226 /* If readwrite is true, tries to read the polynomial from a file, and */
227 /* computes it and writes it to the file if it is not yet present. */
228 /* print indicates whether the curve parameters shall be displayed on */
229 /* screen */
230 {
231 mpz_t p;
232 /* the size of the base field */
233 mpz_t n, l, c;
234 /* the cardinality of the curve, the prime order of a base point and */
235 /* the cofactor C = N/Q */
236 mpz_t* j;
237 mpz_t nonsquare;
238 /* a quadratic non-residue modulo P to compute quadratic twists */
239 mpz_t a, b, k, P_x, P_y, x, y;
240 /* the curve parameters mod P, an auxiliary variable and point */
241 /* coordinates of a random point on the curve (twice) */
242 mpz_t tmp;
243 bool P_infty;
244 int i, no_j;
245 bool ok = false;
246 /* true if at least one suitable curve could be found */
247 int count = 0;
248 /* number of suitable curves */
249 cm_timer clock;
250
251 mpz_init (p);
252 mpz_init (n);
253 mpz_init (l);
254 mpz_init (c);
255 mpz_init (tmp);
256 mpz_init (a);
257 mpz_init (b);
258 mpz_init (k);
259 mpz_init (P_x);
260 mpz_init (P_y);
261 mpz_init (x);
262 mpz_init (y);
263 mpz_init_set_ui (nonsquare, 2);
264
265 cm_timer_start (clock);
266 curve_compute_param (p, n, l, c, d, fieldsize, verbose);
267 cm_timer_stop (clock);
268 while (mpz_jacobi (nonsquare, p) != -1)
269 mpz_add_ui (nonsquare, nonsquare, 1);
270 if (verbose)
271 printf ("--- Time for P: %.1f\n\n", cm_timer_get (clock));
272
273 j = cm_class_get_j_mod_P (d, inv, p, &no_j, modpoldir, readwrite, verbose);
274
275 cm_timer_start (clock);
276 for (i = 0; i < no_j && !ok; i++)
277 {
278 /* construct one curve with the given j-invariant */
279 if (mpz_cmp_ui (j [i], 1728) == 0)
280 /* may occur with spurious roots of modular polynomials */
281 {
282 mpz_set_ui (a, 1);
283 mpz_set_ui (b, 0);
284 }
285 else if (mpz_cmp_ui (j [i], 0) == 0)
286 /* should not occur as d \not= -3 */
287 {
288 mpz_set_ui (a, 0);
289 mpz_set_ui (b, 1);
290 }
291 else
292 {
293 /* k = j [i] / (1728 - j_mod) */
294 mpz_sub_ui (k, j [i], 1728);
295 mpz_neg (k, k);
296 mpz_invert (tmp, k, p);
297 mpz_mul (k, tmp, j [i]);
298 /* b = 2 * k; */
299 mpz_mul_2exp (b, k, 1);
300 mpz_mod (b, b, p);
301 /* a = 3 * k; */
302 mpz_add (a, b, k);
303 mpz_mod (a, a, p);
304 }
305
306 cm_nt_elliptic_curve_random (P_x, P_y, c, a, b, p);
307 mpz_set (x, P_x);
308 mpz_set (y, P_y);
309 P_infty = false;
310 cm_nt_elliptic_curve_multiply (P_x, P_y, &P_infty, l, a, p);
311 if (P_infty) {
312 ok = true;
313 count++;
314 }
315 else {
316 /* consider the quadratic twist */
317 mpz_pow_ui (tmp, nonsquare, 2);
318 mpz_mul (a, a, tmp);
319 mpz_mod (a, a, p);
320 mpz_mul (b, b, tmp);
321 mpz_mul (b, b, nonsquare);
322 mpz_mod (b, b, p);
323 cm_nt_elliptic_curve_random (P_x, P_y, c, a, b, p);
324 mpz_set (x, P_x);
325 mpz_set (y, P_y);
326 P_infty = false;
327 cm_nt_elliptic_curve_multiply (P_x, P_y, &P_infty, l, a, p);
328 if (P_infty) {
329 ok = true;
330 count++;
331 }
332 }
333 }
334
335 if (!ok) {
336 printf ("\n*** No suitable curve found!\n");
337 exit (1);
338 }
339
340 cm_timer_stop (clock);
341 if (print) {
342 printf ("p = "); mpz_out_str (stdout, 10, p); printf ("\n");
343 printf ("n = "); mpz_out_str (stdout, 10, n); printf ("\n");
344 printf (" = "); mpz_out_str (stdout, 10, c);
345 printf (" * "); mpz_out_str (stdout, 10, l); printf ("\n");
346 printf ("j = "); mpz_out_str (stdout, 10, j [i-1]); printf ("\n");
347 printf ("a = "); mpz_out_str (stdout, 10, a); printf ("\n");
348 printf ("b = "); mpz_out_str (stdout, 10, b); printf ("\n");
349 }
350 if (verbose)
351 printf ("--- Time for curve: %.1f\n", cm_timer_get (clock));
352
353 for (i = 0; i < no_j; i++)
354 mpz_clear (j [i]);
355 free (j);
356 mpz_clear (p);
357 mpz_clear (n);
358 mpz_clear (l);
359 mpz_clear (c);
360 mpz_clear (tmp);
361 mpz_clear (a);
362 mpz_clear (b);
363 mpz_clear (k);
364 mpz_clear (P_x);
365 mpz_clear (P_y);
366 mpz_clear (x);
367 mpz_clear (y);
368 mpz_clear (nonsquare);
369 }
370
371 /*****************************************************************************/
372 /*****************************************************************************/
373