Lines Matching +full:a +full:- +full:z
1 /* ec.c - Elliptic Curve functions
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * You should have received a copy of the GNU Lesser General Public
21 #include "mpi-internal.h"
24 #define point_init(a) mpi_point_init((a)) argument
25 #define point_free(a) mpi_point_free_parts((a)) argument
33 /* Create a new point option. NBITS gives the size in bits of one
34 * coordinate; it is only used to pre-allocate some resources and
35 * might also be passed as 0 to use a default value.
60 /* Initialize the fields of a point object. gcry_mpi_point_free_parts
65 p->x = mpi_new(0); in mpi_point_init()
66 p->y = mpi_new(0); in mpi_point_init()
67 p->z = mpi_new(0); in mpi_point_init()
71 /* Release the parts of a point object. */
74 mpi_free(p->x); p->x = NULL; in mpi_point_free_parts()
75 mpi_free(p->y); p->y = NULL; in mpi_point_free_parts()
76 mpi_free(p->z); p->z = NULL; in mpi_point_free_parts()
83 mpi_set(d->x, s->x); in point_set()
84 mpi_set(d->y, s->y); in point_set()
85 mpi_set(d->z, s->z); in point_set()
90 size_t nlimbs = ctx->p->nlimbs; in point_resize()
92 mpi_resize(p->x, nlimbs); in point_resize()
93 p->x->nlimbs = nlimbs; in point_resize()
94 mpi_resize(p->z, nlimbs); in point_resize()
95 p->z->nlimbs = nlimbs; in point_resize()
97 if (ctx->model != MPI_EC_MONTGOMERY) { in point_resize()
98 mpi_resize(p->y, nlimbs); in point_resize()
99 p->y->nlimbs = nlimbs; in point_resize()
106 mpi_swap_cond(d->x, s->x, swap); in point_swap_cond()
107 if (ctx->model != MPI_EC_MONTGOMERY) in point_swap_cond()
108 mpi_swap_cond(d->y, s->y, swap); in point_swap_cond()
109 mpi_swap_cond(d->z, s->z, swap); in point_swap_cond()
116 if (ec->t.p_barrett) in ec_mod()
117 mpi_mod_barrett(w, w, ec->t.p_barrett); in ec_mod()
119 mpi_mod(w, w, ec->p); in ec_mod()
131 while (w->sign) in ec_subm()
132 mpi_add(w, w, ec->p); in ec_subm()
152 mpi_powm(w, b, e, ctx->p); in ec_powm()
163 /* mpi_powm(w, b, mpi_const(MPI_C_TWO), ctx->p); */ in ec_pow2()
173 mpi_powm(w, b, mpi_const(MPI_C_THREE), ctx->p); in ec_pow3()
176 static void ec_invm(MPI x, MPI a, struct mpi_ec_ctx *ctx) in ec_invm() argument
178 if (!mpi_invm(x, a, ctx->p)) in ec_invm()
186 mpi_limb_t mask = ((mpi_limb_t)0) - set; in mpih_set_cond()
195 /* Routines for 2^255 - 19. */
197 #define LIMB_SIZE_25519 ((256+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB)
206 if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) in ec_addm_25519()
210 up = u->d; in ec_addm_25519()
211 vp = v->d; in ec_addm_25519()
212 wp = w->d; in ec_addm_25519()
215 borrow = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); in ec_addm_25519()
216 mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); in ec_addm_25519()
218 wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); in ec_addm_25519()
228 if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) in ec_subm_25519()
232 up = u->d; in ec_subm_25519()
233 vp = v->d; in ec_subm_25519()
234 wp = w->d; in ec_subm_25519()
237 mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); in ec_subm_25519()
239 wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); in ec_subm_25519()
252 if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) in ec_mulm_25519()
255 up = u->d; in ec_mulm_25519()
256 vp = v->d; in ec_mulm_25519()
257 wp = w->d; in ec_mulm_25519()
261 wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); in ec_mulm_25519()
263 memcpy(m, n+LIMB_SIZE_25519-1, (wsize+1) * BYTES_PER_MPI_LIMB); in ec_mulm_25519()
280 msb = (wp[LIMB_SIZE_25519-1] >> (255 % BITS_PER_MPI_LIMB)); in ec_mulm_25519()
282 wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); in ec_mulm_25519()
286 cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); in ec_mulm_25519()
287 mpih_set_cond(m, ctx->p->d, wsize, (cy != 0UL)); in ec_mulm_25519()
301 /* Routines for 2^448 - 2^224 - 1. */
303 #define LIMB_SIZE_448 ((448+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB)
313 if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) in ec_addm_448()
317 up = u->d; in ec_addm_448()
318 vp = v->d; in ec_addm_448()
319 wp = w->d; in ec_addm_448()
322 mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL)); in ec_addm_448()
333 if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) in ec_subm_448()
337 up = u->d; in ec_subm_448()
338 vp = v->d; in ec_subm_448()
339 wp = w->d; in ec_subm_448()
342 mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); in ec_subm_448()
361 if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) in ec_mulm_448()
364 up = u->d; in ec_mulm_448()
365 vp = v->d; in ec_mulm_448()
366 wp = w->d; in ec_mulm_448()
378 b0[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1; in ec_mulm_448()
379 a2[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1; in ec_mulm_448()
384 for (i = (wsize + 1) / 2 - 1; i >= 0; i--) { in ec_mulm_448()
390 b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1); in ec_mulm_448()
391 a3_rest = a3v & (((mpi_limb_t)1UL << 32)-1); in ec_mulm_448()
400 wp[LIMB_SIZE_HALF_448-1] &= (((mpi_limb_t)1UL << 32)-1); in ec_mulm_448()
404 cy = b0[LIMB_SIZE_HALF_448-1] >> 32; in ec_mulm_448()
413 for (i = (wsize + 1) / 2 - 1; i >= 0; i--) { in ec_mulm_448()
416 b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1); in ec_mulm_448()
418 wp[LIMB_SIZE_HALF_448-1] |= (b1_rest << 32); in ec_mulm_448()
424 cy = b1[LIMB_SIZE_HALF_448-1]; in ec_mulm_448()
430 n[LIMB_SIZE_HALF_448-1] = cy << 32; in ec_mulm_448()
438 cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); in ec_mulm_448()
439 mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL)); in ec_mulm_448()
488 ec->t.valid.a_is_pminus3 = 0; in mpi_ec_get_reset()
489 ec->t.valid.two_inv_p = 0; in mpi_ec_get_reset()
497 if (!ec->t.valid.a_is_pminus3) { in ec_get_a_is_pminus3()
498 ec->t.valid.a_is_pminus3 = 1; in ec_get_a_is_pminus3()
499 tmp = mpi_alloc_like(ec->p); in ec_get_a_is_pminus3()
500 mpi_sub_ui(tmp, ec->p, 3); in ec_get_a_is_pminus3()
501 ec->t.a_is_pminus3 = !mpi_cmp(ec->a, tmp); in ec_get_a_is_pminus3()
505 return ec->t.a_is_pminus3; in ec_get_a_is_pminus3()
511 if (!ec->t.valid.two_inv_p) { in ec_get_two_inv_p()
512 ec->t.valid.two_inv_p = 1; in ec_get_two_inv_p()
513 if (!ec->t.two_inv_p) in ec_get_two_inv_p()
514 ec->t.two_inv_p = mpi_alloc(0); in ec_get_two_inv_p()
515 ec_invm(ec->t.two_inv_p, mpi_const(MPI_C_TWO), ec); in ec_get_two_inv_p()
517 return ec->t.two_inv_p; in ec_get_two_inv_p()
550 static void mpi_ec_coefficient_normalize(MPI a, MPI p) in mpi_ec_coefficient_normalize() argument
552 if (a->sign) { in mpi_ec_coefficient_normalize()
553 mpi_resize(a, p->nlimbs); in mpi_ec_coefficient_normalize()
554 mpihelp_sub_n(a->d, p->d, a->d, p->nlimbs); in mpi_ec_coefficient_normalize()
555 a->nlimbs = p->nlimbs; in mpi_ec_coefficient_normalize()
556 a->sign = 0; in mpi_ec_coefficient_normalize()
560 /* This function initialized a context for elliptic curve based on the
561 * field GF(p). P is the prime specifying this field, A is the first
566 int flags, MPI p, MPI a, MPI b) in mpi_ec_init() argument
569 static int use_barrett = -1 /* TODO: 1 or -1 */; in mpi_ec_init()
571 mpi_ec_coefficient_normalize(a, p); in mpi_ec_init()
574 /* Fixme: Do we want to check some constraints? e.g. a < p */ in mpi_ec_init()
576 ctx->model = model; in mpi_ec_init()
577 ctx->dialect = dialect; in mpi_ec_init()
578 ctx->flags = flags; in mpi_ec_init()
580 ctx->nbits = 256; in mpi_ec_init()
582 ctx->nbits = mpi_get_nbits(p); in mpi_ec_init()
583 ctx->p = mpi_copy(p); in mpi_ec_init()
584 ctx->a = mpi_copy(a); in mpi_ec_init()
585 ctx->b = mpi_copy(b); in mpi_ec_init()
587 ctx->t.p_barrett = use_barrett > 0 ? mpi_barrett_init(ctx->p, 0) : NULL; in mpi_ec_init()
594 int match_p = !mpi_cmp(ctx->p, p_candidate); in mpi_ec_init()
601 for (j = 0; i < DIM(ctx->t.scratch) && bad_points_table[i][j]; j++) in mpi_ec_init()
602 ctx->t.scratch[j] = mpi_scanval(bad_points_table[i][j]); in mpi_ec_init()
606 for (i = 0; i < DIM(ctx->t.scratch); i++) in mpi_ec_init()
607 ctx->t.scratch[i] = mpi_alloc_like(ctx->p); in mpi_ec_init()
610 ctx->addm = ec_addm; in mpi_ec_init()
611 ctx->subm = ec_subm; in mpi_ec_init()
612 ctx->mulm = ec_mulm; in mpi_ec_init()
613 ctx->mul2 = ec_mul2; in mpi_ec_init()
614 ctx->pow2 = ec_pow2; in mpi_ec_init()
624 ctx->addm = field_table[i].addm; in mpi_ec_init()
625 ctx->subm = field_table[i].subm; in mpi_ec_init()
626 ctx->mulm = field_table[i].mulm; in mpi_ec_init()
627 ctx->mul2 = field_table[i].mul2; in mpi_ec_init()
628 ctx->pow2 = field_table[i].pow2; in mpi_ec_init()
631 mpi_resize(ctx->a, ctx->p->nlimbs); in mpi_ec_init()
632 ctx->a->nlimbs = ctx->p->nlimbs; in mpi_ec_init()
634 mpi_resize(ctx->b, ctx->p->nlimbs); in mpi_ec_init()
635 ctx->b->nlimbs = ctx->p->nlimbs; in mpi_ec_init()
637 for (i = 0; i < DIM(ctx->t.scratch) && ctx->t.scratch[i]; i++) in mpi_ec_init()
638 ctx->t.scratch[i]->nlimbs = ctx->p->nlimbs; in mpi_ec_init()
652 mpi_barrett_free(ctx->t.p_barrett); in mpi_ec_deinit()
655 mpi_free(ctx->p); in mpi_ec_deinit()
656 mpi_free(ctx->a); in mpi_ec_deinit()
657 mpi_free(ctx->b); in mpi_ec_deinit()
658 mpi_point_release(ctx->G); in mpi_ec_deinit()
659 mpi_free(ctx->n); in mpi_ec_deinit()
662 mpi_point_release(ctx->Q); in mpi_ec_deinit()
663 mpi_free(ctx->d); in mpi_ec_deinit()
666 mpi_free(ctx->t.two_inv_p); in mpi_ec_deinit()
668 for (i = 0; i < DIM(ctx->t.scratch); i++) in mpi_ec_deinit()
669 mpi_free(ctx->t.scratch[i]); in mpi_ec_deinit()
680 if (!mpi_cmp_ui(point->z, 0)) in mpi_ec_get_affine()
681 return -1; in mpi_ec_get_affine()
683 switch (ctx->model) { in mpi_ec_get_affine()
690 ec_invm(z1, point->z, ctx); /* z1 = z^(-1) mod p */ in mpi_ec_get_affine()
691 ec_mulm(z2, z1, z1, ctx); /* z2 = z^(-2) mod p */ in mpi_ec_get_affine()
694 ec_mulm(x, point->x, z2, ctx); in mpi_ec_get_affine()
698 ec_mulm(z3, z2, z1, ctx); /* z3 = z^(-3) mod p */ in mpi_ec_get_affine()
699 ec_mulm(y, point->y, z3, ctx); in mpi_ec_get_affine()
711 mpi_set(x, point->x); in mpi_ec_get_affine()
714 log_fatal("%s: Getting Y-coordinate on %s is not supported\n", in mpi_ec_get_affine()
716 return -1; in mpi_ec_get_affine()
723 MPI z; in mpi_ec_get_affine() local
725 z = mpi_new(0); in mpi_ec_get_affine()
726 ec_invm(z, point->z, ctx); in mpi_ec_get_affine()
728 mpi_resize(z, ctx->p->nlimbs); in mpi_ec_get_affine()
729 z->nlimbs = ctx->p->nlimbs; in mpi_ec_get_affine()
732 mpi_resize(x, ctx->p->nlimbs); in mpi_ec_get_affine()
733 x->nlimbs = ctx->p->nlimbs; in mpi_ec_get_affine()
734 ctx->mulm(x, point->x, z, ctx); in mpi_ec_get_affine()
737 mpi_resize(y, ctx->p->nlimbs); in mpi_ec_get_affine()
738 y->nlimbs = ctx->p->nlimbs; in mpi_ec_get_affine()
739 ctx->mulm(y, point->y, z, ctx); in mpi_ec_get_affine()
742 mpi_free(z); in mpi_ec_get_affine()
747 return -1; in mpi_ec_get_affine()
756 #define x3 (result->x) in dup_point_weierstrass()
757 #define y3 (result->y) in dup_point_weierstrass()
758 #define z3 (result->z) in dup_point_weierstrass()
759 #define t1 (ctx->t.scratch[0]) in dup_point_weierstrass()
760 #define t2 (ctx->t.scratch[1]) in dup_point_weierstrass()
761 #define t3 (ctx->t.scratch[2]) in dup_point_weierstrass()
762 #define l1 (ctx->t.scratch[3]) in dup_point_weierstrass()
763 #define l2 (ctx->t.scratch[4]) in dup_point_weierstrass()
764 #define l3 (ctx->t.scratch[5]) in dup_point_weierstrass()
766 if (!mpi_cmp_ui(point->y, 0) || !mpi_cmp_ui(point->z, 0)) { in dup_point_weierstrass()
774 /* L1 = 3(X - Z^2)(X + Z^2) */ in dup_point_weierstrass()
775 /* T1: used for Z^2. */ in dup_point_weierstrass()
777 ec_pow2(t1, point->z, ctx); in dup_point_weierstrass()
778 ec_subm(l1, point->x, t1, ctx); in dup_point_weierstrass()
780 ec_addm(t2, point->x, t1, ctx); in dup_point_weierstrass()
786 ec_pow2(l1, point->x, ctx); in dup_point_weierstrass()
788 ec_powm(t1, point->z, mpi_const(MPI_C_FOUR), ctx); in dup_point_weierstrass()
789 ec_mulm(t1, t1, ctx->a, ctx); in dup_point_weierstrass()
793 ec_mulm(z3, point->y, point->z, ctx); in dup_point_weierstrass()
798 ec_pow2(t2, point->y, ctx); in dup_point_weierstrass()
799 ec_mulm(l2, t2, point->x, ctx); in dup_point_weierstrass()
802 /* X3 = L1^2 - 2L2 */ in dup_point_weierstrass()
813 /* Y3 = L1(L2 - X3) - L3 */ in dup_point_weierstrass()
845 #define X1 (point->x) in dup_point_edwards()
846 #define Y1 (point->y) in dup_point_edwards()
847 #define Z1 (point->z) in dup_point_edwards()
848 #define X3 (result->x) in dup_point_edwards()
849 #define Y3 (result->y) in dup_point_edwards()
850 #define Z3 (result->z) in dup_point_edwards()
851 #define B (ctx->t.scratch[0]) in dup_point_edwards()
852 #define C (ctx->t.scratch[1]) in dup_point_edwards()
853 #define D (ctx->t.scratch[2]) in dup_point_edwards()
854 #define E (ctx->t.scratch[3]) in dup_point_edwards()
855 #define F (ctx->t.scratch[4]) in dup_point_edwards()
856 #define H (ctx->t.scratch[5]) in dup_point_edwards()
857 #define J (ctx->t.scratch[6]) in dup_point_edwards()
862 ctx->addm(B, X1, Y1, ctx); in dup_point_edwards()
863 ctx->pow2(B, B, ctx); in dup_point_edwards()
867 ctx->pow2(C, X1, ctx); in dup_point_edwards()
868 ctx->pow2(D, Y1, ctx); in dup_point_edwards()
871 if (ctx->dialect == ECC_DIALECT_ED25519) in dup_point_edwards()
872 ctx->subm(E, ctx->p, C, ctx); in dup_point_edwards()
874 ctx->mulm(E, ctx->a, C, ctx); in dup_point_edwards()
877 ctx->addm(F, E, D, ctx); in dup_point_edwards()
880 ctx->pow2(H, Z1, ctx); in dup_point_edwards()
882 /* J = F - 2H */ in dup_point_edwards()
883 ctx->mul2(J, H, ctx); in dup_point_edwards()
884 ctx->subm(J, F, J, ctx); in dup_point_edwards()
886 /* X_3 = (B - C - D) · J */ in dup_point_edwards()
887 ctx->subm(X3, B, C, ctx); in dup_point_edwards()
888 ctx->subm(X3, X3, D, ctx); in dup_point_edwards()
889 ctx->mulm(X3, X3, J, ctx); in dup_point_edwards()
891 /* Y_3 = F · (E - D) */ in dup_point_edwards()
892 ctx->subm(Y3, E, D, ctx); in dup_point_edwards()
893 ctx->mulm(Y3, Y3, F, ctx); in dup_point_edwards()
896 ctx->mulm(Z3, F, J, ctx); in dup_point_edwards()
917 switch (ctx->model) { in mpi_ec_dup_point()
935 #define x1 (p1->x) in add_points_weierstrass()
936 #define y1 (p1->y) in add_points_weierstrass()
937 #define z1 (p1->z) in add_points_weierstrass()
938 #define x2 (p2->x) in add_points_weierstrass()
939 #define y2 (p2->y) in add_points_weierstrass()
940 #define z2 (p2->z) in add_points_weierstrass()
941 #define x3 (result->x) in add_points_weierstrass()
942 #define y3 (result->y) in add_points_weierstrass()
943 #define z3 (result->z) in add_points_weierstrass()
944 #define l1 (ctx->t.scratch[0]) in add_points_weierstrass()
945 #define l2 (ctx->t.scratch[1]) in add_points_weierstrass()
946 #define l3 (ctx->t.scratch[2]) in add_points_weierstrass()
947 #define l4 (ctx->t.scratch[3]) in add_points_weierstrass()
948 #define l5 (ctx->t.scratch[4]) in add_points_weierstrass()
949 #define l6 (ctx->t.scratch[5]) in add_points_weierstrass()
950 #define l7 (ctx->t.scratch[6]) in add_points_weierstrass()
951 #define l8 (ctx->t.scratch[7]) in add_points_weierstrass()
952 #define l9 (ctx->t.scratch[8]) in add_points_weierstrass()
953 #define t1 (ctx->t.scratch[9]) in add_points_weierstrass()
954 #define t2 (ctx->t.scratch[10]) in add_points_weierstrass()
961 mpi_set(x3, p2->x); in add_points_weierstrass()
962 mpi_set(y3, p2->y); in add_points_weierstrass()
963 mpi_set(z3, p2->z); in add_points_weierstrass()
966 mpi_set(x3, p1->x); in add_points_weierstrass()
967 mpi_set(y3, p1->y); in add_points_weierstrass()
968 mpi_set(z3, p1->z); in add_points_weierstrass()
987 /* l3 = l1 - l2 */ in add_points_weierstrass()
995 /* l6 = l4 - l5 */ in add_points_weierstrass()
1000 /* P1 and P2 are the same - use duplicate function. */ in add_points_weierstrass()
1016 /* x3 = l6^2 - l7 l3^2 */ in add_points_weierstrass()
1021 /* l9 = l7 l3^2 - 2 x3 */ in add_points_weierstrass()
1024 /* y3 = (l9 l6 - l8 l3^3)/2 */ in add_points_weierstrass()
1073 #define X1 (p1->x) in add_points_edwards()
1074 #define Y1 (p1->y) in add_points_edwards()
1075 #define Z1 (p1->z) in add_points_edwards()
1076 #define X2 (p2->x) in add_points_edwards()
1077 #define Y2 (p2->y) in add_points_edwards()
1078 #define Z2 (p2->z) in add_points_edwards()
1079 #define X3 (result->x) in add_points_edwards()
1080 #define Y3 (result->y) in add_points_edwards()
1081 #define Z3 (result->z) in add_points_edwards()
1082 #define A (ctx->t.scratch[0]) in add_points_edwards() macro
1083 #define B (ctx->t.scratch[1]) in add_points_edwards()
1084 #define C (ctx->t.scratch[2]) in add_points_edwards()
1085 #define D (ctx->t.scratch[3]) in add_points_edwards()
1086 #define E (ctx->t.scratch[4]) in add_points_edwards()
1087 #define F (ctx->t.scratch[5]) in add_points_edwards()
1088 #define G (ctx->t.scratch[6]) in add_points_edwards()
1089 #define tmp (ctx->t.scratch[7]) in add_points_edwards()
1095 /* A = Z1 · Z2 */ in add_points_edwards()
1096 ctx->mulm(A, Z1, Z2, ctx); in add_points_edwards()
1098 /* B = A^2 */ in add_points_edwards()
1099 ctx->pow2(B, A, ctx); in add_points_edwards()
1102 ctx->mulm(C, X1, X2, ctx); in add_points_edwards()
1105 ctx->mulm(D, Y1, Y2, ctx); in add_points_edwards()
1108 ctx->mulm(E, ctx->b, C, ctx); in add_points_edwards()
1109 ctx->mulm(E, E, D, ctx); in add_points_edwards()
1111 /* F = B - E */ in add_points_edwards()
1112 ctx->subm(F, B, E, ctx); in add_points_edwards()
1115 ctx->addm(G, B, E, ctx); in add_points_edwards()
1117 /* X_3 = A · F · ((X_1 + Y_1) · (X_2 + Y_2) - C - D) */ in add_points_edwards()
1118 ctx->addm(tmp, X1, Y1, ctx); in add_points_edwards()
1119 ctx->addm(X3, X2, Y2, ctx); in add_points_edwards()
1120 ctx->mulm(X3, X3, tmp, ctx); in add_points_edwards()
1121 ctx->subm(X3, X3, C, ctx); in add_points_edwards()
1122 ctx->subm(X3, X3, D, ctx); in add_points_edwards()
1123 ctx->mulm(X3, X3, F, ctx); in add_points_edwards()
1124 ctx->mulm(X3, X3, A, ctx); in add_points_edwards()
1126 /* Y_3 = A · G · (D - aC) */ in add_points_edwards()
1127 if (ctx->dialect == ECC_DIALECT_ED25519) { in add_points_edwards()
1128 ctx->addm(Y3, D, C, ctx); in add_points_edwards()
1130 ctx->mulm(Y3, ctx->a, C, ctx); in add_points_edwards()
1131 ctx->subm(Y3, D, Y3, ctx); in add_points_edwards()
1133 ctx->mulm(Y3, Y3, G, ctx); in add_points_edwards()
1134 ctx->mulm(Y3, Y3, A, ctx); in add_points_edwards()
1137 ctx->mulm(Z3, F, G, ctx); in add_points_edwards()
1149 #undef A in add_points_edwards()
1159 /* Compute a step of Montgomery Ladder (only use X and Z in the point).
1160 * Inputs: P1, P2, and x-coordinate of DIF = P1 - P1.
1167 ctx->addm(sum->x, p2->x, p2->z, ctx); in montgomery_ladder()
1168 ctx->subm(p2->z, p2->x, p2->z, ctx); in montgomery_ladder()
1169 ctx->addm(prd->x, p1->x, p1->z, ctx); in montgomery_ladder()
1170 ctx->subm(p1->z, p1->x, p1->z, ctx); in montgomery_ladder()
1171 ctx->mulm(p2->x, p1->z, sum->x, ctx); in montgomery_ladder()
1172 ctx->mulm(p2->z, prd->x, p2->z, ctx); in montgomery_ladder()
1173 ctx->pow2(p1->x, prd->x, ctx); in montgomery_ladder()
1174 ctx->pow2(p1->z, p1->z, ctx); in montgomery_ladder()
1175 ctx->addm(sum->x, p2->x, p2->z, ctx); in montgomery_ladder()
1176 ctx->subm(p2->z, p2->x, p2->z, ctx); in montgomery_ladder()
1177 ctx->mulm(prd->x, p1->x, p1->z, ctx); in montgomery_ladder()
1178 ctx->subm(p1->z, p1->x, p1->z, ctx); in montgomery_ladder()
1179 ctx->pow2(sum->x, sum->x, ctx); in montgomery_ladder()
1180 ctx->pow2(sum->z, p2->z, ctx); in montgomery_ladder()
1181 ctx->mulm(prd->z, p1->z, ctx->a, ctx); /* CTX->A: (a-2)/4 */ in montgomery_ladder()
1182 ctx->mulm(sum->z, sum->z, dif_x, ctx); in montgomery_ladder()
1183 ctx->addm(prd->z, p1->x, prd->z, ctx); in montgomery_ladder()
1184 ctx->mulm(prd->z, prd->z, p1->z, ctx); in montgomery_ladder()
1192 switch (ctx->model) { in mpi_ec_add_points()
1206 /* Scalar point multiplication - the main function for ECC. If takes
1207 * an integer SCALAR and a POINT as well as the usual context CTX.
1218 if (ctx->model == MPI_EC_EDWARDS) { in mpi_ec_mul_point()
1224 * publisher = {Springer-Verlag New York, Inc.}} in mpi_ec_mul_point()
1229 if (mpi_cmp(scalar, ctx->p) >= 0) in mpi_ec_mul_point()
1232 nbits = mpi_get_nbits(ctx->p); in mpi_ec_mul_point()
1234 mpi_set_ui(result->x, 0); in mpi_ec_mul_point()
1235 mpi_set_ui(result->y, 1); in mpi_ec_mul_point()
1236 mpi_set_ui(result->z, 1); in mpi_ec_mul_point()
1242 for (j = nbits-1; j >= 0; j--) { in mpi_ec_mul_point()
1248 } else if (ctx->model == MPI_EC_MONTGOMERY) { in mpi_ec_mul_point()
1257 * Note that we don't use Y-coordinate in the points at all. in mpi_ec_mul_point()
1258 * RESULT->Y will be filled by zero. in mpi_ec_mul_point()
1268 p2.x = mpi_copy(point->x); in mpi_ec_mul_point()
1269 mpi_set_ui(p2.z, 1); in mpi_ec_mul_point()
1276 mpi_resize(point->x, ctx->p->nlimbs); in mpi_ec_mul_point()
1277 point->x->nlimbs = ctx->p->nlimbs; in mpi_ec_mul_point()
1284 for (j = nbits-1; j >= 0; j--) { in mpi_ec_mul_point()
1289 montgomery_ladder(prd, sum, q1, q2, point->x, ctx); in mpi_ec_mul_point()
1295 mpi_clear(result->y); in mpi_ec_mul_point()
1299 rsize = p1.z->nlimbs; in mpi_ec_mul_point()
1300 MPN_NORMALIZE(p1.z->d, rsize); in mpi_ec_mul_point()
1302 mpi_set_ui(result->x, 1); in mpi_ec_mul_point()
1303 mpi_set_ui(result->z, 0); in mpi_ec_mul_point()
1306 ec_invm(z1, p1.z, ctx); in mpi_ec_mul_point()
1307 ec_mulm(result->x, p1.x, z1, ctx); in mpi_ec_mul_point()
1308 mpi_set_ui(result->z, 1); in mpi_ec_mul_point()
1319 x1 = mpi_alloc_like(ctx->p); in mpi_ec_mul_point()
1320 y1 = mpi_alloc_like(ctx->p); in mpi_ec_mul_point()
1321 h = mpi_alloc_like(ctx->p); in mpi_ec_mul_point()
1323 yy = mpi_copy(point->y); in mpi_ec_mul_point()
1326 k->sign = 0; in mpi_ec_mul_point()
1330 if (!mpi_cmp_ui(point->z, 1)) { in mpi_ec_mul_point()
1331 mpi_set(x1, point->x); in mpi_ec_mul_point()
1336 z2 = mpi_alloc_like(ctx->p); in mpi_ec_mul_point()
1337 z3 = mpi_alloc_like(ctx->p); in mpi_ec_mul_point()
1338 ec_mulm(z2, point->z, point->z, ctx); in mpi_ec_mul_point()
1339 ec_mulm(z3, point->z, z2, ctx); in mpi_ec_mul_point()
1341 ec_mulm(x1, point->x, z2, ctx); in mpi_ec_mul_point()
1357 mpi_clear(result->x); in mpi_ec_mul_point()
1358 mpi_clear(result->y); in mpi_ec_mul_point()
1359 mpi_clear(result->z); in mpi_ec_mul_point()
1361 mpi_set(result->x, point->x); in mpi_ec_mul_point()
1362 mpi_set(result->y, yy); in mpi_ec_mul_point()
1363 mpi_set(result->z, point->z); in mpi_ec_mul_point()
1369 p1.z = z1; z1 = NULL; in mpi_ec_mul_point()
1373 /* Invert point: y = p - y mod p */ in mpi_ec_mul_point()
1375 ec_subm(p1inv.y, ctx->p, p1inv.y, ctx); in mpi_ec_mul_point()
1377 for (i = loops-2; i > 0; i--) { in mpi_ec_mul_point()
1410 if (mpi_cmpabs(point->x, ctx->p) >= 0) in mpi_ec_curve_point()
1412 if (mpi_cmpabs(point->y, ctx->p) >= 0) in mpi_ec_curve_point()
1414 if (mpi_cmpabs(point->z, ctx->p) >= 0) in mpi_ec_curve_point()
1417 switch (ctx->model) { in mpi_ec_curve_point()
1427 /* y^2 == x^3 + a·x + b */ in mpi_ec_curve_point()
1431 ec_mulm(w, ctx->a, x, ctx); in mpi_ec_curve_point()
1432 ec_addm(w, w, ctx->b, ctx); in mpi_ec_curve_point()
1445 /* With Montgomery curve, only X-coordinate is valid. */ in mpi_ec_curve_point()
1449 /* The equation is: b * y^2 == x^3 + a · x^2 + x */ in mpi_ec_curve_point()
1453 /* CTX->A has (a-2)/4 and CTX->B has b^-1 */ in mpi_ec_curve_point()
1454 ec_mulm(w, ctx->a, mpi_const(MPI_C_FOUR), ctx); in mpi_ec_curve_point()
1461 ec_mulm(w, w, ctx->b, ctx); in mpi_ec_curve_point()
1463 /* Compute Euler's criterion: w^(p-1)/2 */ in mpi_ec_curve_point()
1465 ec_subm(p_minus1, ctx->p, mpi_const(MPI_C_ONE), ctx); in mpi_ec_curve_point()
1479 mpi_resize(w, ctx->p->nlimbs); in mpi_ec_curve_point()
1480 w->nlimbs = ctx->p->nlimbs; in mpi_ec_curve_point()
1482 /* a · x^2 + y^2 - 1 - b · x^2 · y^2 == 0 */ in mpi_ec_curve_point()
1483 ctx->pow2(x, x, ctx); in mpi_ec_curve_point()
1484 ctx->pow2(y, y, ctx); in mpi_ec_curve_point()
1485 if (ctx->dialect == ECC_DIALECT_ED25519) in mpi_ec_curve_point()
1486 ctx->subm(w, ctx->p, x, ctx); in mpi_ec_curve_point()
1488 ctx->mulm(w, ctx->a, x, ctx); in mpi_ec_curve_point()
1489 ctx->addm(w, w, y, ctx); in mpi_ec_curve_point()
1490 ctx->mulm(x, x, y, ctx); in mpi_ec_curve_point()
1491 ctx->mulm(x, x, ctx->b, ctx); in mpi_ec_curve_point()
1492 ctx->subm(w, w, x, ctx); in mpi_ec_curve_point()