1 #include <ctype.h>
2 #include <stdarg.h>
3 #include <stdio.h>
4 #include <stdint.h> // for intptr_t
5 #include <stdlib.h>
6 #include <string.h>
7 #include <gmp.h>
8 #include "pbc_utils.h"
9 #include "pbc_field.h"
10 #include "pbc_multiz.h"
11 #include "pbc_poly.h"
12 #include "pbc_curve.h"
13 #include "pbc_memory.h"
14 #include "pbc_random.h"
15 #include "misc/darray.h"
16
17 // Per-field data.
18 typedef struct {
19 field_ptr field; // The field where the curve is defined.
20 element_t a, b; // The curve is E: Y^2 = X^3 + a X + b.
21 // cofac == NULL means we're using the whole group of points.
22 // otherwise we're working in the subgroup of order #E / cofac,
23 // where #E is the number of points in E.
24 mpz_ptr cofac;
25 // A generator of E.
26 element_t gen_no_cofac;
27 // A generator of the subgroup.
28 element_t gen;
29 // A non-NULL quotient_cmp means we are working with the quotient group of
30 // order #E / quotient_cmp, and the points are actually coset
31 // representatives. Thus for a comparison, we must multiply by quotient_cmp
32 // before comparing.
33 mpz_ptr quotient_cmp;
34 } *curve_data_ptr;
35
36 // Per-element data. Elements of this group are points on the elliptic curve.
37 typedef struct {
38 int inf_flag; // inf_flag == 1 means O, the point at infinity.
39 element_t x, y; // Otherwise we have the finite point (x, y).
40 } *point_ptr;
41
curve_init(element_ptr e)42 static void curve_init(element_ptr e) {
43 curve_data_ptr cdp = e->field->data;
44 point_ptr p = e->data = pbc_malloc(sizeof(*p));
45 element_init(p->x, cdp->field);
46 element_init(p->y, cdp->field);
47 p->inf_flag = 1;
48 }
49
curve_clear(element_ptr e)50 static void curve_clear(element_ptr e) {
51 point_ptr p = e->data;
52 element_clear(p->x);
53 element_clear(p->y);
54 pbc_free(e->data);
55 }
56
curve_is_valid_point(element_ptr e)57 static int curve_is_valid_point(element_ptr e) {
58 element_t t0, t1;
59 int result;
60 curve_data_ptr cdp = e->field->data;
61 point_ptr p = e->data;
62
63 if (p->inf_flag) return 1;
64
65 element_init(t0, cdp->field);
66 element_init(t1, cdp->field);
67 element_square(t0, p->x);
68 element_add(t0, t0, cdp->a);
69 element_mul(t0, t0, p->x);
70 element_add(t0, t0, cdp->b);
71 element_square(t1, p->y);
72 result = !element_cmp(t0, t1);
73
74 element_clear(t0);
75 element_clear(t1);
76 return result;
77 }
78
curve_invert(element_ptr c,element_ptr a)79 static void curve_invert(element_ptr c, element_ptr a) {
80 point_ptr r = c->data, p = a->data;
81
82 if (p->inf_flag) {
83 r->inf_flag = 1;
84 return;
85 }
86 r->inf_flag = 0;
87 element_set(r->x, p->x);
88 element_neg(r->y, p->y);
89 }
90
curve_set(element_ptr c,element_ptr a)91 static void curve_set(element_ptr c, element_ptr a) {
92 point_ptr r = c->data, p = a->data;
93 if (p->inf_flag) {
94 r->inf_flag = 1;
95 return;
96 }
97 r->inf_flag = 0;
98 element_set(r->x, p->x);
99 element_set(r->y, p->y);
100 }
101
double_no_check(point_ptr r,point_ptr p,element_ptr a)102 static inline void double_no_check(point_ptr r, point_ptr p, element_ptr a) {
103 element_t lambda, e0, e1;
104 field_ptr f = r->x->field;
105
106 element_init(lambda, f);
107 element_init(e0, f);
108 element_init(e1, f);
109
110 //lambda = (3x^2 + a) / 2y
111 element_square(lambda, p->x);
112 element_mul_si(lambda, lambda, 3);
113 element_add(lambda, lambda, a);
114
115 element_double(e0, p->y);
116
117 element_invert(e0, e0);
118 element_mul(lambda, lambda, e0);
119 //x1 = lambda^2 - 2x
120 //element_add(e1, p->x, p->x);
121 element_double(e1, p->x);
122 element_square(e0, lambda);
123 element_sub(e0, e0, e1);
124 //y1 = (x - x1)lambda - y
125 element_sub(e1, p->x, e0);
126 element_mul(e1, e1, lambda);
127 element_sub(e1, e1, p->y);
128
129 element_set(r->x, e0);
130 element_set(r->y, e1);
131 r->inf_flag = 0;
132
133 element_clear(lambda);
134 element_clear(e0);
135 element_clear(e1);
136 return;
137 }
138
curve_double(element_ptr c,element_ptr a)139 static void curve_double(element_ptr c, element_ptr a) {
140 curve_data_ptr cdp = a->field->data;
141 point_ptr r = c->data, p = a->data;
142 if (p->inf_flag) {
143 r->inf_flag = 1;
144 return;
145 }
146 if (element_is0(p->y)) {
147 r->inf_flag = 1;
148 return;
149 }
150 double_no_check(r, p, cdp->a);
151 }
152
curve_mul(element_ptr c,element_ptr a,element_ptr b)153 static void curve_mul(element_ptr c, element_ptr a, element_ptr b) {
154 curve_data_ptr cdp = a->field->data;
155 point_ptr r = c->data, p = a->data, q = b->data;
156
157 if (p->inf_flag) {
158 curve_set(c, b);
159 return;
160 }
161 if (q->inf_flag) {
162 curve_set(c, a);
163 return;
164 }
165 if (!element_cmp(p->x, q->x)) {
166 if (!element_cmp(p->y, q->y)) {
167 if (element_is0(p->y)) {
168 r->inf_flag = 1;
169 return;
170 } else {
171 double_no_check(r, p, cdp->a);
172 return;
173 }
174 }
175 //points are inverses of each other
176 r->inf_flag = 1;
177 return;
178 } else {
179 element_t lambda, e0, e1;
180
181 element_init(lambda, cdp->field);
182 element_init(e0, cdp->field);
183 element_init(e1, cdp->field);
184
185 //lambda = (y2-y1)/(x2-x1)
186 element_sub(e0, q->x, p->x);
187 element_invert(e0, e0);
188 element_sub(lambda, q->y, p->y);
189 element_mul(lambda, lambda, e0);
190 //x3 = lambda^2 - x1 - x2
191 element_square(e0, lambda);
192 element_sub(e0, e0, p->x);
193 element_sub(e0, e0, q->x);
194 //y3 = (x1-x3)lambda - y1
195 element_sub(e1, p->x, e0);
196 element_mul(e1, e1, lambda);
197 element_sub(e1, e1, p->y);
198
199 element_set(r->x, e0);
200 element_set(r->y, e1);
201 r->inf_flag = 0;
202
203 element_clear(lambda);
204 element_clear(e0);
205 element_clear(e1);
206 }
207 }
208
209 //compute c_i=a_i+a_i at one time.
multi_double(element_ptr c[],element_ptr a[],int n)210 static void multi_double(element_ptr c[], element_ptr a[], int n) {
211 int i;
212 element_t* table = pbc_malloc(sizeof(element_t)*n); //a big problem?
213 element_t e0, e1, e2;
214 point_ptr q, r;
215 curve_data_ptr cdp = a[0]->field->data;
216
217 q=a[0]->data;
218 element_init(e0,q->y->field);
219 element_init(e1,q->y->field);
220 element_init(e2,q->y->field);
221
222 for(i=0; i<n; i++){
223 q=a[i]->data; r=c[i]->data;
224 element_init(table[i],q->y->field);
225
226 if (q->inf_flag) {
227 r->inf_flag = 1;
228 continue;
229 }
230 if (element_is0(q->y)) {
231 r->inf_flag = 1;
232 continue;
233 }
234 }
235 //to compute 1/2y multi. see Cohen's GTM139 Algorithm 10.3.4
236 for(i=0; i<n; i++){
237 q=a[i]->data;
238 element_double(table[i],q->y);
239 if(i>0) element_mul(table[i],table[i],table[i-1]);
240 }
241 element_invert(e2,table[n-1]); //ONLY ONE inv is required now.
242 for(i=n-1; i>0; i--){
243 q=a[i]->data;
244 element_mul(table[i],table[i-1],e2);
245 element_mul(e2,e2,q->y);
246 element_double(e2,e2); //e2=e2*2y_j
247 }
248 element_set(table[0],e2); //e2 no longer used.
249
250 for(i=0; i<n; i++){
251 q=a[i]->data;
252 r=c[i]->data;
253 if(r->inf_flag) continue;
254
255 //e2=lambda = (3x^2 + a) / 2y
256 element_square(e2, q->x);
257 element_mul_si(e2, e2, 3);
258 element_add(e2, e2, cdp->a);
259
260 element_mul(e2, e2, table[i]); //Recall that table[i]=1/2y_i
261 //x1 = lambda^2 - 2x
262 element_double(e1, q->x);
263 element_square(e0, e2);
264 element_sub(e0, e0, e1);
265 //y1 = (x - x1)lambda - y
266 element_sub(e1, q->x, e0);
267 element_mul(e1, e1, e2);
268 element_sub(e1, e1, q->y);
269 element_set(r->x, e0);
270 element_set(r->y, e1);
271 r->inf_flag = 0;
272 }
273
274 element_clear(e0);
275 element_clear(e1);
276 element_clear(e2);
277 for(i=0; i<n; i++){
278 element_clear(table[i]);
279 }
280 pbc_free(table);
281 }
282
283 //compute c_i=a_i+b_i at one time.
multi_add(element_ptr c[],element_ptr a[],element_ptr b[],int n)284 static void multi_add(element_ptr c[], element_ptr a[], element_ptr b[], int n){
285 int i;
286 element_t* table = pbc_malloc(sizeof(element_t)*n); //a big problem?
287 point_ptr p, q, r;
288 element_t e0, e1, e2;
289 curve_data_ptr cdp = a[0]->field->data;
290
291 p = a[0]->data;
292 q = b[0]->data;
293 element_init(e0, p->x->field);
294 element_init(e1, p->x->field);
295 element_init(e2, p->x->field);
296
297 element_init(table[0], p->x->field);
298 element_sub(table[0], q->x, p->x);
299 for(i=1; i<n; i++){
300 p = a[i]->data;
301 q = b[i]->data;
302 element_init(table[i], p->x->field);
303 element_sub(table[i], q->x, p->x);
304 element_mul(table[i], table[i], table[i-1]);
305 }
306 element_invert(e2, table[n-1]);
307 for(i=n-1; i>0; i--){
308 p = a[i]->data;
309 q = b[i]->data;
310 element_mul(table[i], table[i-1], e2);
311 element_sub(e1, q->x, p->x);
312 element_mul(e2,e2,e1); //e2=e2*(x2_j-x1_j)
313 }
314 element_set(table[0],e2); //e2 no longer used.
315
316 for(i=0; i<n; i++){
317 p = a[i]->data;
318 q = b[i]->data;
319 r = c[i]->data;
320 if (p->inf_flag) {
321 curve_set(c[i], b[i]);
322 continue;
323 }
324 if (q->inf_flag) {
325 curve_set(c[i], a[i]);
326 continue;
327 }
328 if (!element_cmp(p->x, q->x)) { //a[i]=b[i]
329 if (!element_cmp(p->y, q->y)) {
330 if (element_is0(p->y)) {
331 r->inf_flag = 1;
332 continue;
333 } else {
334 double_no_check(r, p, cdp->a);
335 continue;
336 }
337 }
338 //points are inverses of each other
339 r->inf_flag = 1;
340 continue;
341 } else {
342 //lambda = (y2-y1)/(x2-x1)
343 element_sub(e2, q->y, p->y);
344 element_mul(e2, e2, table[i]);
345 //x3 = lambda^2 - x1 - x2
346 element_square(e0, e2);
347 element_sub(e0, e0, p->x);
348 element_sub(e0, e0, q->x);
349 //y3 = (x1-x3)lambda - y1
350 element_sub(e1, p->x, e0);
351 element_mul(e1, e1, e2);
352 element_sub(e1, e1, p->y);
353 element_set(r->x, e0);
354 element_set(r->y, e1);
355 r->inf_flag = 0;
356 }
357 }
358 element_clear(e0);
359 element_clear(e1);
360 element_clear(e2);
361 for(i=0; i<n; i++){
362 element_clear(table[i]);
363 }
364 pbc_free(table);
365 }
366
367
point_cmp(point_ptr p,point_ptr q)368 static inline int point_cmp(point_ptr p, point_ptr q) {
369 if (p->inf_flag || q->inf_flag) {
370 return !(p->inf_flag && q->inf_flag);
371 }
372 return element_cmp(p->x, q->x) || element_cmp(p->y, q->y);
373 }
374
curve_cmp(element_ptr a,element_ptr b)375 static int curve_cmp(element_ptr a, element_ptr b) {
376 if (a == b) {
377 return 0;
378 } else {
379 // If we're working with a quotient group we must account for different
380 // representatives of the same coset.
381 curve_data_ptr cdp = a->field->data;
382 if (cdp->quotient_cmp) {
383 element_t e;
384 element_init_same_as(e, a);
385 element_div(e, a, b);
386 element_pow_mpz(e, e, cdp->quotient_cmp);
387 int result = !element_is1(e);
388 element_clear(e);
389 return result;
390 }
391 return point_cmp(a->data, b->data);
392 }
393 }
394
curve_set1(element_ptr x)395 static void curve_set1(element_ptr x) {
396 point_ptr p = x->data;
397 p->inf_flag = 1;
398 }
399
curve_is1(element_ptr x)400 static int curve_is1(element_ptr x) {
401 point_ptr p = x->data;
402 return p->inf_flag;
403 }
404
curve_random_no_cofac_solvefory(element_ptr a)405 static void curve_random_no_cofac_solvefory(element_ptr a) {
406 //TODO: with 0.5 probability negate y-coord
407 curve_data_ptr cdp = a->field->data;
408 point_ptr p = a->data;
409 element_t t;
410
411 element_init(t, cdp->field);
412 p->inf_flag = 0;
413 do {
414 element_random(p->x);
415 element_square(t, p->x);
416 element_add(t, t, cdp->a);
417 element_mul(t, t, p->x);
418 element_add(t, t, cdp->b);
419 } while (!element_is_sqr(t));
420 element_sqrt(p->y, t);
421 element_clear(t);
422 }
423
curve_random_solvefory(element_ptr a)424 static void curve_random_solvefory(element_ptr a) {
425 curve_data_ptr cdp = a->field->data;
426 curve_random_no_cofac_solvefory(a);
427 if (cdp->cofac) element_mul_mpz(a, a, cdp->cofac);
428 }
429
curve_random_pointmul(element_ptr a)430 static void curve_random_pointmul(element_ptr a) {
431 curve_data_ptr cdp = a->field->data;
432 mpz_t x;
433 mpz_init(x);
434
435 pbc_mpz_random(x, a->field->order);
436 element_mul_mpz(a, cdp->gen, x);
437 mpz_clear(x);
438 }
439
field_curve_use_random_solvefory(field_ptr f)440 void field_curve_use_random_solvefory(field_ptr f) {
441 f->random = curve_random_solvefory;
442 }
443
curve_set_gen_no_cofac(element_ptr a)444 void curve_set_gen_no_cofac(element_ptr a) {
445 curve_data_ptr cdp = a->field->data;
446 element_set(a, cdp->gen_no_cofac);
447 }
448
curve_sign(element_ptr e)449 static int curve_sign(element_ptr e) {
450 point_ptr p = e->data;
451 if (p->inf_flag) return 0;
452 return element_sign(p->y);
453 }
454
curve_from_hash(element_t a,void * data,int len)455 static void curve_from_hash(element_t a, void *data, int len) {
456 element_t t, t1;
457 point_ptr p = a->data;
458 curve_data_ptr cdp = a->field->data;
459
460 element_init(t, cdp->field);
461 element_init(t1, cdp->field);
462 p->inf_flag = 0;
463 element_from_hash(p->x, data, len);
464 for(;;) {
465 element_square(t, p->x);
466 element_add(t, t, cdp->a);
467 element_mul(t, t, p->x);
468 element_add(t, t, cdp->b);
469 if (element_is_sqr(t)) break;
470 // Compute x <- x^2 + 1 and try again.
471 element_square(p->x, p->x);
472 element_set1(t);
473 element_add(p->x, p->x, t);
474 }
475 element_sqrt(p->y, t);
476 if (element_sgn(p->y) < 0) element_neg(p->y, p->y);
477
478 if (cdp->cofac) element_mul_mpz(a, a, cdp->cofac);
479
480 element_clear(t);
481 element_clear(t1);
482 }
483
curve_out_str(FILE * stream,int base,element_ptr a)484 static size_t curve_out_str(FILE *stream, int base, element_ptr a) {
485 point_ptr p = a->data;
486 size_t result, status;
487 if (p->inf_flag) {
488 if (EOF == fputc('O', stream)) return 0;
489 return 1;
490 }
491 if (EOF == fputc('[', stream)) return 0;
492 result = element_out_str(stream, base, p->x);
493 if (!result) return 0;
494 if (EOF == fputs(", ", stream)) return 0;
495 status = element_out_str(stream, base, p->y);
496 if (!status) return 0;
497 if (EOF == fputc(']', stream)) return 0;
498 return result + status + 4;
499 }
500
curve_snprint(char * s,size_t n,element_ptr a)501 static int curve_snprint(char *s, size_t n, element_ptr a) {
502 point_ptr p = a->data;
503 size_t result = 0, left;
504 int status;
505
506 #define clip_sub() { \
507 result += status; \
508 left = result >= n ? 0 : n - result; \
509 }
510
511 if (p->inf_flag) {
512 status = snprintf(s, n, "O");
513 if (status < 0) return status;
514 return 1;
515 }
516
517 status = snprintf(s, n, "[");
518 if (status < 0) return status;
519 clip_sub();
520 status = element_snprint(s + result, left, p->x);
521 if (status < 0) return status;
522 clip_sub();
523 status = snprintf(s + result, left, ", ");
524 if (status < 0) return status;
525 clip_sub();
526 status = element_snprint(s + result, left, p->y);
527 if (status < 0) return status;
528 clip_sub();
529 status = snprintf(s + result, left, "]");
530 if (status < 0) return status;
531 return result + status;
532 #undef clip_sub
533 }
534
curve_set_multiz(element_ptr a,multiz m)535 static void curve_set_multiz(element_ptr a, multiz m) {
536 if (multiz_is_z(m)) {
537 if (multiz_is0(m)) {
538 element_set0(a);
539 return;
540 }
541 pbc_warn("bad multiz");
542 return;
543 } else {
544 if (multiz_count(m) < 2) {
545 pbc_warn("multiz has too few coefficients");
546 return;
547 }
548 point_ptr p = a->data;
549 p->inf_flag = 0;
550 element_set_multiz(p->x, multiz_at(m, 0));
551 element_set_multiz(p->y, multiz_at(m, 1));
552 }
553 }
554
curve_set_str(element_ptr e,const char * s,int base)555 static int curve_set_str(element_ptr e, const char *s, int base) {
556 point_ptr p = e->data;
557 const char *cp = s;
558 element_set0(e);
559 while (*cp && isspace(*cp)) cp++;
560 if (*cp == 'O') {
561 return cp - s + 1;
562 }
563 p->inf_flag = 0;
564 if (*cp != '[') return 0;
565 cp++;
566 cp += element_set_str(p->x, cp, base);
567 while (*cp && isspace(*cp)) cp++;
568 if (*cp != ',') return 0;
569 cp++;
570 cp += element_set_str(p->y, cp, base);
571 if (*cp != ']') return 0;
572
573 if (!curve_is_valid_point(e)) {
574 element_set0(e);
575 return 0;
576 }
577 return cp - s + 1;
578 }
579
field_clear_curve(field_t f)580 static void field_clear_curve(field_t f) {
581 curve_data_ptr cdp;
582 cdp = f->data;
583 element_clear(cdp->gen);
584 element_clear(cdp->gen_no_cofac);
585 if (cdp->cofac) {
586 mpz_clear(cdp->cofac);
587 pbc_free(cdp->cofac);
588 }
589 if (cdp->quotient_cmp) {
590 mpz_clear(cdp->quotient_cmp);
591 pbc_free(cdp->quotient_cmp);
592 }
593 element_clear(cdp->a);
594 element_clear(cdp->b);
595 pbc_free(cdp);
596 }
597
curve_length_in_bytes(element_ptr x)598 static int curve_length_in_bytes(element_ptr x) {
599 point_ptr p = x->data;
600 return element_length_in_bytes(p->x) + element_length_in_bytes(p->y);
601 }
602
curve_to_bytes(unsigned char * data,element_t e)603 static int curve_to_bytes(unsigned char *data, element_t e) {
604 point_ptr P = e->data;
605 int len;
606 len = element_to_bytes(data, P->x);
607 len += element_to_bytes(data + len, P->y);
608 return len;
609 }
610
curve_from_bytes(element_t e,unsigned char * data)611 static int curve_from_bytes(element_t e, unsigned char *data) {
612 point_ptr P = e->data;
613 int len;
614
615 P->inf_flag = 0;
616 len = element_from_bytes(P->x, data);
617 len += element_from_bytes(P->y, data + len);
618 //if point does not lie on curve, set it to O
619 if (!curve_is_valid_point(e)) {
620 element_set0(e);
621 }
622 return len;
623 }
624
curve_out_info(FILE * out,field_t f)625 static void curve_out_info(FILE *out, field_t f) {
626 int len;
627 fprintf(out, "elliptic curve");
628 if ((len = f->fixed_length_in_bytes)) {
629 fprintf(out, ", bits per coord = %d", len * 8 / 2);
630 } else {
631 fprintf(out, "variable-length");
632 }
633 }
634
odd_curve_is_sqr(element_ptr e)635 static int odd_curve_is_sqr(element_ptr e) {
636 UNUSED_VAR(e);
637 return 1;
638 }
639
640 //TODO: untested
even_curve_is_sqr(element_ptr e)641 static int even_curve_is_sqr(element_ptr e) {
642 mpz_t z;
643 element_t e1;
644 int result;
645
646 mpz_init(z);
647 element_init(e1, e->field);
648 mpz_sub_ui(z, e->field->order, 1);
649 mpz_fdiv_q_2exp(z, z, 1);
650 element_pow_mpz(e1, e, z);
651 result = element_is1(e1);
652
653 mpz_clear(z);
654 element_clear(e1);
655 return result;
656 }
657
curve_item_count(element_ptr e)658 static int curve_item_count(element_ptr e) {
659 if (element_is0(e)) {
660 return 0;
661 }
662 return 2;
663 }
664
curve_item(element_ptr e,int i)665 static element_ptr curve_item(element_ptr e, int i) {
666 if (element_is0(e)) return NULL;
667 point_ptr P = e->data;
668 switch(i) {
669 case 0:
670 return P->x;
671 case 1:
672 return P->y;
673 default:
674 return NULL;
675 }
676 }
677
curve_get_x(element_ptr e)678 static element_ptr curve_get_x(element_ptr e) {
679 point_ptr P = e->data;
680 return P->x;
681 }
682
curve_get_y(element_ptr e)683 static element_ptr curve_get_y(element_ptr e) {
684 point_ptr P = e->data;
685 return P->y;
686 }
687
field_init_curve_ab(field_ptr f,element_ptr a,element_ptr b,mpz_t order,mpz_t cofac)688 void field_init_curve_ab(field_ptr f, element_ptr a, element_ptr b, mpz_t order, mpz_t cofac) {
689 /*
690 if (element_is0(a)) {
691 c->double_nocheck = cc_double_no_check_ais0;
692 } else {
693 c->double_nocheck = cc_double_no_check;
694 }
695 */
696 curve_data_ptr cdp;
697 field_init(f);
698 mpz_set(f->order, order);
699 cdp = f->data = pbc_malloc(sizeof(*cdp));
700 cdp->field = a->field;
701 element_init(cdp->a, cdp->field);
702 element_init(cdp->b, cdp->field);
703 element_set(cdp->a, a);
704 element_set(cdp->b, b);
705
706 f->init = curve_init;
707 f->clear = curve_clear;
708 f->neg = f->invert = curve_invert;
709 f->square = f->doub = curve_double;
710 f->multi_doub = multi_double;
711 f->add = f->mul = curve_mul;
712 f->multi_add = multi_add;
713 f->mul_mpz = element_pow_mpz;
714 f->cmp = curve_cmp;
715 f->set0 = f->set1 = curve_set1;
716 f->is0 = f->is1 = curve_is1;
717 f->sign = curve_sign;
718 f->set = curve_set;
719 f->random = curve_random_pointmul;
720 //f->random = curve_random_solvefory;
721 f->from_hash = curve_from_hash;
722 f->out_str = curve_out_str;
723 f->snprint = curve_snprint;
724 f->set_multiz = curve_set_multiz;
725 f->set_str = curve_set_str;
726 f->field_clear = field_clear_curve;
727 if (cdp->field->fixed_length_in_bytes < 0) {
728 f->length_in_bytes = curve_length_in_bytes;
729 } else {
730 f->fixed_length_in_bytes = 2 * cdp->field->fixed_length_in_bytes;
731 }
732 f->to_bytes = curve_to_bytes;
733 f->from_bytes = curve_from_bytes;
734 f->out_info = curve_out_info;
735 f->item_count = curve_item_count;
736 f->item = curve_item;
737 f->get_x = curve_get_x;
738 f->get_y = curve_get_y;
739
740 if (mpz_odd_p(order)) {
741 f->is_sqr = odd_curve_is_sqr;
742 } else {
743 f->is_sqr = even_curve_is_sqr;
744 }
745
746 element_init(cdp->gen_no_cofac, f);
747 element_init(cdp->gen, f);
748 curve_random_no_cofac_solvefory(cdp->gen_no_cofac);
749 if (cofac) {
750 cdp->cofac = pbc_malloc(sizeof(mpz_t));
751 mpz_init(cdp->cofac);
752 mpz_set(cdp->cofac, cofac);
753 element_mul_mpz(cdp->gen, cdp->gen_no_cofac, cofac);
754 } else{
755 cdp->cofac = NULL;
756 element_set(cdp->gen, cdp->gen_no_cofac);
757 }
758 cdp->quotient_cmp = NULL;
759 }
760
761 // Requires e to be a point on an elliptic curve.
element_to_bytes_compressed(unsigned char * data,element_ptr e)762 int element_to_bytes_compressed(unsigned char *data, element_ptr e) {
763 point_ptr P = e->data;
764 int len;
765 len = element_to_bytes(data, P->x);
766 if (element_sign(P->y) > 0) {
767 data[len] = 1;
768 } else {
769 data[len] = 0;
770 }
771 len++;
772 return len;
773 }
774
775 // Computes a point on the elliptic curve Y^2 = X^3 + a X + b given its
776 // x-coordinate.
777 // Requires a solution to exist.
point_from_x(point_ptr p,element_t x,element_t a,element_t b)778 static void point_from_x(point_ptr p, element_t x, element_t a, element_t b) {
779 element_t t;
780
781 element_init(t, x->field);
782 p->inf_flag = 0;
783 element_square(t, x);
784 element_add(t, t, a);
785 element_mul(t, t, x);
786 element_add(t, t, b);
787 element_sqrt(p->y, t);
788 element_set(p->x, x);
789
790 element_clear(t);
791 }
792
curve_from_x(element_ptr e,element_t x)793 void curve_from_x(element_ptr e, element_t x) {
794 curve_data_ptr cdp = e->field->data;
795 point_from_x(e->data, x, cdp->a, cdp->b);
796 }
797
798 // Requires e to be a point on an elliptic curve.
element_from_bytes_compressed(element_ptr e,unsigned char * data)799 int element_from_bytes_compressed(element_ptr e, unsigned char *data) {
800 curve_data_ptr cdp = e->field->data;
801 point_ptr P = e->data;
802 int len;
803 len = element_from_bytes(P->x, data);
804 point_from_x(P, P->x, cdp->a, cdp->b);
805
806 if (data[len]) {
807 if (element_sign(P->y) < 0) element_neg(P->y, P->y);
808 } else if (element_sign(P->y) > 0) {
809 element_neg(P->y, P->y);
810 }
811 len++;
812 return len;
813 }
814
element_length_in_bytes_compressed(element_ptr e)815 int element_length_in_bytes_compressed(element_ptr e) {
816 point_ptr P = e->data;
817 return element_length_in_bytes(P->x) + 1;
818 }
819
820 // Requires e to be a point on an elliptic curve.
element_to_bytes_x_only(unsigned char * data,element_ptr e)821 int element_to_bytes_x_only(unsigned char *data, element_ptr e) {
822 point_ptr P = e->data;
823 int len;
824 len = element_to_bytes(data, P->x);
825 return len;
826 }
827
828 // Requires e to be a point on an elliptic curve.
element_from_bytes_x_only(element_ptr e,unsigned char * data)829 int element_from_bytes_x_only(element_ptr e, unsigned char *data) {
830 curve_data_ptr cdp = e->field->data;
831 point_ptr P = e->data;
832 int len;
833 len = element_from_bytes(P->x, data);
834 point_from_x(P, P->x, cdp->a, cdp->b);
835 return len;
836 }
837
element_length_in_bytes_x_only(element_ptr e)838 int element_length_in_bytes_x_only(element_ptr e) {
839 point_ptr P = e->data;
840 return element_length_in_bytes(P->x);
841 }
842
curve_x_coord(element_t e)843 inline element_ptr curve_x_coord(element_t e) {
844 return ((point_ptr) e->data)->x;
845 }
846
curve_y_coord(element_t e)847 inline element_ptr curve_y_coord(element_t e) {
848 return ((point_ptr) e->data)->y;
849 }
850
curve_a_coeff(element_t e)851 inline element_ptr curve_a_coeff(element_t e) {
852 return ((curve_data_ptr) e->field->data)->a;
853 }
854
curve_b_coeff(element_t e)855 inline element_ptr curve_b_coeff(element_t e) {
856 return ((curve_data_ptr) e->field->data)->b;
857 }
858
curve_field_a_coeff(field_t f)859 inline element_ptr curve_field_a_coeff(field_t f) {
860 return ((curve_data_ptr) f->data)->a;
861 }
862
curve_field_b_coeff(field_t f)863 inline element_ptr curve_field_b_coeff(field_t f) {
864 return ((curve_data_ptr) f->data)->b;
865 }
866
field_init_curve_ab_map(field_t cnew,field_t c,fieldmap map,field_ptr mapdest,mpz_t ordernew,mpz_t cofacnew)867 void field_init_curve_ab_map(field_t cnew, field_t c,
868 fieldmap map, field_ptr mapdest,
869 mpz_t ordernew, mpz_t cofacnew) {
870 element_t a, b;
871 curve_data_ptr cdp = c->data;
872
873 element_init(a, mapdest);
874 element_init(b, mapdest);
875
876 map(a, cdp->a);
877 map(b, cdp->b);
878
879 field_init_curve_ab(cnew, a, b, ordernew, cofacnew);
880 element_clear(a);
881 element_clear(b);
882 }
883
884 // Existing points are invalidated as this mangles c.
field_reinit_curve_twist(field_ptr c)885 void field_reinit_curve_twist(field_ptr c) {
886 curve_data_ptr cdp = c->data;
887 element_ptr nqr = field_get_nqr(cdp->field);
888 element_mul(cdp->a, cdp->a, nqr);
889 element_mul(cdp->a, cdp->a, nqr);
890 element_mul(cdp->b, cdp->b, nqr);
891 element_mul(cdp->b, cdp->b, nqr);
892 element_mul(cdp->b, cdp->b, nqr);
893
894 // Recompute generators.
895 curve_random_no_cofac_solvefory(cdp->gen_no_cofac);
896 if (cdp->cofac) {
897 element_mul_mpz(cdp->gen, cdp->gen_no_cofac, cdp->cofac);
898 } else{
899 element_set(cdp->gen, cdp->gen_no_cofac);
900 }
901 }
902
903 // I could generalize this for all fields, but is there any point?
field_curve_set_quotient_cmp(field_ptr c,mpz_t quotient_cmp)904 void field_curve_set_quotient_cmp(field_ptr c, mpz_t quotient_cmp) {
905 curve_data_ptr cdp = c->data;
906 cdp->quotient_cmp = pbc_malloc(sizeof(mpz_t));
907 mpz_init(cdp->quotient_cmp);
908 mpz_set(cdp->quotient_cmp, quotient_cmp);
909 }
910
911 // Requires j != 0, 1728.
field_init_curve_j(field_ptr f,element_ptr j,mpz_t order,mpz_t cofac)912 void field_init_curve_j(field_ptr f, element_ptr j, mpz_t order, mpz_t cofac) {
913 element_t a, b;
914 element_init(a, j->field);
915 element_init(b, j->field);
916
917 element_set_si(a, 1728);
918 element_sub(a, a, j);
919 element_invert(a, a);
920 element_mul(a, a, j);
921
922 //b = 2 j / (1728 - j)
923 element_add(b, a, a);
924 //a = 3 j / (1728 - j)
925 element_add(a, a, b);
926 field_init_curve_ab(f, a, b, order, cofac);
927
928 element_clear(a);
929 element_clear(b);
930 }
931
field_init_curve_b(field_ptr f,element_ptr b,mpz_t order,mpz_t cofac)932 void field_init_curve_b(field_ptr f, element_ptr b, mpz_t order, mpz_t cofac) {
933 element_t a;
934 element_init(a, b->field);
935 field_init_curve_ab(f, a, b, order, cofac);
936
937 element_clear(a);
938 }
939
940 // Compute trace of Frobenius at q^n given trace at q.
941 // See p.105 of Blake, Seroussi and Smart.
pbc_mpz_trace_n(mpz_t res,mpz_t q,mpz_t trace,int n)942 void pbc_mpz_trace_n(mpz_t res, mpz_t q, mpz_t trace, int n) {
943 int i;
944 mpz_t c0, c1, c2;
945 mpz_t t0;
946
947 mpz_init(c0);
948 mpz_init(c1);
949 mpz_init(c2);
950 mpz_init(t0);
951 mpz_set_ui(c2, 2);
952 mpz_set(c1, trace);
953 for (i=2; i<=n; i++) {
954 mpz_mul(c0, trace, c1);
955 mpz_mul(t0, q, c2);
956 mpz_sub(c0, c0, t0);
957 mpz_set(c2, c1);
958 mpz_set(c1, c0);
959 }
960 mpz_set(res, c1);
961 mpz_clear(t0);
962 mpz_clear(c2);
963 mpz_clear(c1);
964 mpz_clear(c0);
965 }
966
967 // Given q, t such that #E(F_q) = q - t + 1, compute #E(F_q^k).
pbc_mpz_curve_order_extn(mpz_t res,mpz_t q,mpz_t t,int k)968 void pbc_mpz_curve_order_extn(mpz_t res, mpz_t q, mpz_t t, int k) {
969 mpz_t z;
970 mpz_t tk;
971 mpz_init(z);
972 mpz_init(tk);
973 mpz_pow_ui(z, q, k);
974 mpz_add_ui(z, z, 1);
975 pbc_mpz_trace_n(tk, q, t, k);
976 mpz_sub(z, z, tk);
977 mpz_set(res, z);
978 mpz_clear(z);
979 mpz_clear(tk);
980 }
981
curve_set_si(element_t R,long int x,long int y)982 void curve_set_si(element_t R, long int x, long int y) {
983 point_ptr p = R->data;
984 element_set_si(p->x, x);
985 element_set_si(p->y, y);
986 p->inf_flag = 0;
987 }
988