Lines Matching +full:3 +full:- +full:point
1 /* ec.c - Elliptic Curve functions
21 #include "mpi-internal.h"
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
50 /* Release the point object P. P may be NULL. */
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()
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()
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()
569 static int use_barrett = -1 /* TODO: 1 or -1 */; 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->d = NULL; in mpi_ec_init()
588 ctx->t.two_inv_p = NULL; in mpi_ec_init()
590 ctx->t.p_barrett = use_barrett > 0 ? mpi_barrett_init(ctx->p, 0) : NULL; in mpi_ec_init()
597 int match_p = !mpi_cmp(ctx->p, p_candidate); in mpi_ec_init()
604 for (j = 0; i < DIM(ctx->t.scratch) && bad_points_table[i][j]; j++) in mpi_ec_init()
605 ctx->t.scratch[j] = mpi_scanval(bad_points_table[i][j]); in mpi_ec_init()
609 for (i = 0; i < DIM(ctx->t.scratch); i++) in mpi_ec_init()
610 ctx->t.scratch[i] = mpi_alloc_like(ctx->p); in mpi_ec_init()
613 ctx->addm = ec_addm; in mpi_ec_init()
614 ctx->subm = ec_subm; in mpi_ec_init()
615 ctx->mulm = ec_mulm; in mpi_ec_init()
616 ctx->mul2 = ec_mul2; in mpi_ec_init()
617 ctx->pow2 = ec_pow2; in mpi_ec_init()
627 ctx->addm = field_table[i].addm; in mpi_ec_init()
628 ctx->subm = field_table[i].subm; in mpi_ec_init()
629 ctx->mulm = field_table[i].mulm; in mpi_ec_init()
630 ctx->mul2 = field_table[i].mul2; in mpi_ec_init()
631 ctx->pow2 = field_table[i].pow2; in mpi_ec_init()
634 mpi_resize(ctx->a, ctx->p->nlimbs); in mpi_ec_init()
635 ctx->a->nlimbs = ctx->p->nlimbs; in mpi_ec_init()
637 mpi_resize(ctx->b, ctx->p->nlimbs); in mpi_ec_init()
638 ctx->b->nlimbs = ctx->p->nlimbs; in mpi_ec_init()
640 for (i = 0; i < DIM(ctx->t.scratch) && ctx->t.scratch[i]; i++) in mpi_ec_init()
641 ctx->t.scratch[i]->nlimbs = ctx->p->nlimbs; in mpi_ec_init()
655 mpi_barrett_free(ctx->t.p_barrett); in mpi_ec_deinit()
658 mpi_free(ctx->p); in mpi_ec_deinit()
659 mpi_free(ctx->a); in mpi_ec_deinit()
660 mpi_free(ctx->b); in mpi_ec_deinit()
661 mpi_point_release(ctx->G); in mpi_ec_deinit()
662 mpi_free(ctx->n); in mpi_ec_deinit()
665 mpi_point_release(ctx->Q); in mpi_ec_deinit()
666 mpi_free(ctx->d); in mpi_ec_deinit()
669 mpi_free(ctx->t.two_inv_p); in mpi_ec_deinit()
671 for (i = 0; i < DIM(ctx->t.scratch); i++) in mpi_ec_deinit()
672 mpi_free(ctx->t.scratch[i]); in mpi_ec_deinit()
677 * POINT. Set them into X and Y. If one coordinate is not required,
679 * on success or !0 if POINT is at infinity.
681 int mpi_ec_get_affine(MPI x, MPI y, MPI_POINT point, struct mpi_ec_ctx *ctx) in mpi_ec_get_affine() argument
683 if (!mpi_cmp_ui(point->z, 0)) in mpi_ec_get_affine()
684 return -1; in mpi_ec_get_affine()
686 switch (ctx->model) { in mpi_ec_get_affine()
693 ec_invm(z1, point->z, ctx); /* z1 = z^(-1) mod p */ in mpi_ec_get_affine()
694 ec_mulm(z2, z1, z1, ctx); /* z2 = z^(-2) mod p */ in mpi_ec_get_affine()
697 ec_mulm(x, point->x, z2, ctx); in mpi_ec_get_affine()
701 ec_mulm(z3, z2, z1, ctx); /* z3 = z^(-3) mod p */ in mpi_ec_get_affine()
702 ec_mulm(y, point->y, z3, ctx); in mpi_ec_get_affine()
714 mpi_set(x, point->x); in mpi_ec_get_affine()
717 log_fatal("%s: Getting Y-coordinate on %s is not supported\n", in mpi_ec_get_affine()
719 return -1; in mpi_ec_get_affine()
729 ec_invm(z, point->z, ctx); in mpi_ec_get_affine()
731 mpi_resize(z, ctx->p->nlimbs); in mpi_ec_get_affine()
732 z->nlimbs = ctx->p->nlimbs; in mpi_ec_get_affine()
735 mpi_resize(x, ctx->p->nlimbs); in mpi_ec_get_affine()
736 x->nlimbs = ctx->p->nlimbs; in mpi_ec_get_affine()
737 ctx->mulm(x, point->x, z, ctx); in mpi_ec_get_affine()
740 mpi_resize(y, ctx->p->nlimbs); in mpi_ec_get_affine()
741 y->nlimbs = ctx->p->nlimbs; in mpi_ec_get_affine()
742 ctx->mulm(y, point->y, z, ctx); in mpi_ec_get_affine()
750 return -1; in mpi_ec_get_affine()
755 /* RESULT = 2 * POINT (Weierstrass version). */
757 MPI_POINT point, struct mpi_ec_ctx *ctx) in dup_point_weierstrass() argument
759 #define x3 (result->x) in dup_point_weierstrass()
760 #define y3 (result->y) in dup_point_weierstrass()
761 #define z3 (result->z) in dup_point_weierstrass()
762 #define t1 (ctx->t.scratch[0]) in dup_point_weierstrass()
763 #define t2 (ctx->t.scratch[1]) in dup_point_weierstrass()
764 #define t3 (ctx->t.scratch[2]) in dup_point_weierstrass()
765 #define l1 (ctx->t.scratch[3]) in dup_point_weierstrass()
766 #define l2 (ctx->t.scratch[4]) in dup_point_weierstrass()
767 #define l3 (ctx->t.scratch[5]) in dup_point_weierstrass()
769 if (!mpi_cmp_ui(point->y, 0) || !mpi_cmp_ui(point->z, 0)) { in dup_point_weierstrass()
777 /* L1 = 3(X - Z^2)(X + Z^2) */ in dup_point_weierstrass()
780 ec_pow2(t1, point->z, ctx); in dup_point_weierstrass()
781 ec_subm(l1, point->x, t1, ctx); in dup_point_weierstrass()
783 ec_addm(t2, point->x, t1, ctx); in dup_point_weierstrass()
787 /* L1 = 3X^2 + aZ^4 */ in dup_point_weierstrass()
789 ec_pow2(l1, point->x, ctx); in dup_point_weierstrass()
791 ec_powm(t1, point->z, mpi_const(MPI_C_FOUR), ctx); in dup_point_weierstrass()
792 ec_mulm(t1, t1, ctx->a, ctx); in dup_point_weierstrass()
796 ec_mulm(z3, point->y, point->z, ctx); in dup_point_weierstrass()
801 ec_pow2(t2, point->y, ctx); in dup_point_weierstrass()
802 ec_mulm(l2, t2, point->x, ctx); in dup_point_weierstrass()
805 /* X3 = L1^2 - 2L2 */ in dup_point_weierstrass()
816 /* Y3 = L1(L2 - X3) - L3 */ in dup_point_weierstrass()
833 /* RESULT = 2 * POINT (Montgomery version). */
835 MPI_POINT point, struct mpi_ec_ctx *ctx) in dup_point_montgomery() argument
838 (void)point; in dup_point_montgomery()
844 /* RESULT = 2 * POINT (Twisted Edwards version). */
846 MPI_POINT point, struct mpi_ec_ctx *ctx) in dup_point_edwards() argument
848 #define X1 (point->x) in dup_point_edwards()
849 #define Y1 (point->y) in dup_point_edwards()
850 #define Z1 (point->z) in dup_point_edwards()
851 #define X3 (result->x) in dup_point_edwards()
852 #define Y3 (result->y) in dup_point_edwards()
853 #define Z3 (result->z) in dup_point_edwards()
854 #define B (ctx->t.scratch[0]) in dup_point_edwards()
855 #define C (ctx->t.scratch[1]) in dup_point_edwards()
856 #define D (ctx->t.scratch[2]) in dup_point_edwards()
857 #define E (ctx->t.scratch[3]) in dup_point_edwards()
858 #define F (ctx->t.scratch[4]) in dup_point_edwards()
859 #define H (ctx->t.scratch[5]) in dup_point_edwards()
860 #define J (ctx->t.scratch[6]) in dup_point_edwards()
865 ctx->addm(B, X1, Y1, ctx); in dup_point_edwards()
866 ctx->pow2(B, B, ctx); in dup_point_edwards()
870 ctx->pow2(C, X1, ctx); in dup_point_edwards()
871 ctx->pow2(D, Y1, ctx); in dup_point_edwards()
874 if (ctx->dialect == ECC_DIALECT_ED25519) in dup_point_edwards()
875 ctx->subm(E, ctx->p, C, ctx); in dup_point_edwards()
877 ctx->mulm(E, ctx->a, C, ctx); in dup_point_edwards()
880 ctx->addm(F, E, D, ctx); in dup_point_edwards()
883 ctx->pow2(H, Z1, ctx); in dup_point_edwards()
885 /* J = F - 2H */ in dup_point_edwards()
886 ctx->mul2(J, H, ctx); in dup_point_edwards()
887 ctx->subm(J, F, J, ctx); in dup_point_edwards()
889 /* X_3 = (B - C - D) · J */ in dup_point_edwards()
890 ctx->subm(X3, B, C, ctx); in dup_point_edwards()
891 ctx->subm(X3, X3, D, ctx); in dup_point_edwards()
892 ctx->mulm(X3, X3, J, ctx); in dup_point_edwards()
894 /* Y_3 = F · (E - D) */ in dup_point_edwards()
895 ctx->subm(Y3, E, D, ctx); in dup_point_edwards()
896 ctx->mulm(Y3, Y3, F, ctx); in dup_point_edwards()
899 ctx->mulm(Z3, F, J, ctx); in dup_point_edwards()
916 /* RESULT = 2 * POINT */
918 mpi_ec_dup_point(MPI_POINT result, MPI_POINT point, struct mpi_ec_ctx *ctx) in mpi_ec_dup_point() argument
920 switch (ctx->model) { in mpi_ec_dup_point()
922 dup_point_weierstrass(result, point, ctx); in mpi_ec_dup_point()
925 dup_point_montgomery(result, point, ctx); in mpi_ec_dup_point()
928 dup_point_edwards(result, point, ctx); in mpi_ec_dup_point()
938 #define x1 (p1->x) in add_points_weierstrass()
939 #define y1 (p1->y) in add_points_weierstrass()
940 #define z1 (p1->z) in add_points_weierstrass()
941 #define x2 (p2->x) in add_points_weierstrass()
942 #define y2 (p2->y) in add_points_weierstrass()
943 #define z2 (p2->z) in add_points_weierstrass()
944 #define x3 (result->x) in add_points_weierstrass()
945 #define y3 (result->y) in add_points_weierstrass()
946 #define z3 (result->z) in add_points_weierstrass()
947 #define l1 (ctx->t.scratch[0]) in add_points_weierstrass()
948 #define l2 (ctx->t.scratch[1]) in add_points_weierstrass()
949 #define l3 (ctx->t.scratch[2]) in add_points_weierstrass()
950 #define l4 (ctx->t.scratch[3]) in add_points_weierstrass()
951 #define l5 (ctx->t.scratch[4]) in add_points_weierstrass()
952 #define l6 (ctx->t.scratch[5]) in add_points_weierstrass()
953 #define l7 (ctx->t.scratch[6]) in add_points_weierstrass()
954 #define l8 (ctx->t.scratch[7]) in add_points_weierstrass()
955 #define l9 (ctx->t.scratch[8]) in add_points_weierstrass()
956 #define t1 (ctx->t.scratch[9]) in add_points_weierstrass()
957 #define t2 (ctx->t.scratch[10]) in add_points_weierstrass()
960 /* Same point; need to call the duplicate function. */ in add_points_weierstrass()
964 mpi_set(x3, p2->x); in add_points_weierstrass()
965 mpi_set(y3, p2->y); in add_points_weierstrass()
966 mpi_set(z3, p2->z); in add_points_weierstrass()
969 mpi_set(x3, p1->x); in add_points_weierstrass()
970 mpi_set(y3, p1->y); in add_points_weierstrass()
971 mpi_set(z3, p1->z); in add_points_weierstrass()
990 /* l3 = l1 - l2 */ in add_points_weierstrass()
992 /* l4 = y1 z2^3 */ in add_points_weierstrass()
995 /* l5 = y2 z1^3 */ in add_points_weierstrass()
998 /* l6 = l4 - l5 */ in add_points_weierstrass()
1003 /* P1 and P2 are the same - use duplicate function. */ in add_points_weierstrass()
1019 /* x3 = l6^2 - l7 l3^2 */ in add_points_weierstrass()
1024 /* l9 = l7 l3^2 - 2 x3 */ in add_points_weierstrass()
1027 /* y3 = (l9 l6 - l8 l3^3)/2 */ in add_points_weierstrass()
1076 #define X1 (p1->x) in add_points_edwards()
1077 #define Y1 (p1->y) in add_points_edwards()
1078 #define Z1 (p1->z) in add_points_edwards()
1079 #define X2 (p2->x) in add_points_edwards()
1080 #define Y2 (p2->y) in add_points_edwards()
1081 #define Z2 (p2->z) in add_points_edwards()
1082 #define X3 (result->x) in add_points_edwards()
1083 #define Y3 (result->y) in add_points_edwards()
1084 #define Z3 (result->z) in add_points_edwards()
1085 #define A (ctx->t.scratch[0]) in add_points_edwards()
1086 #define B (ctx->t.scratch[1]) in add_points_edwards()
1087 #define C (ctx->t.scratch[2]) in add_points_edwards()
1088 #define D (ctx->t.scratch[3]) in add_points_edwards()
1089 #define E (ctx->t.scratch[4]) in add_points_edwards()
1090 #define F (ctx->t.scratch[5]) in add_points_edwards()
1091 #define G (ctx->t.scratch[6]) in add_points_edwards()
1092 #define tmp (ctx->t.scratch[7]) in add_points_edwards()
1099 ctx->mulm(A, Z1, Z2, ctx); in add_points_edwards()
1102 ctx->pow2(B, A, ctx); in add_points_edwards()
1105 ctx->mulm(C, X1, X2, ctx); in add_points_edwards()
1108 ctx->mulm(D, Y1, Y2, ctx); in add_points_edwards()
1111 ctx->mulm(E, ctx->b, C, ctx); in add_points_edwards()
1112 ctx->mulm(E, E, D, ctx); in add_points_edwards()
1114 /* F = B - E */ in add_points_edwards()
1115 ctx->subm(F, B, E, ctx); in add_points_edwards()
1118 ctx->addm(G, B, E, ctx); in add_points_edwards()
1120 /* X_3 = A · F · ((X_1 + Y_1) · (X_2 + Y_2) - C - D) */ in add_points_edwards()
1121 ctx->addm(tmp, X1, Y1, ctx); in add_points_edwards()
1122 ctx->addm(X3, X2, Y2, ctx); in add_points_edwards()
1123 ctx->mulm(X3, X3, tmp, ctx); in add_points_edwards()
1124 ctx->subm(X3, X3, C, ctx); in add_points_edwards()
1125 ctx->subm(X3, X3, D, ctx); in add_points_edwards()
1126 ctx->mulm(X3, X3, F, ctx); in add_points_edwards()
1127 ctx->mulm(X3, X3, A, ctx); in add_points_edwards()
1129 /* Y_3 = A · G · (D - aC) */ in add_points_edwards()
1130 if (ctx->dialect == ECC_DIALECT_ED25519) { in add_points_edwards()
1131 ctx->addm(Y3, D, C, ctx); in add_points_edwards()
1133 ctx->mulm(Y3, ctx->a, C, ctx); in add_points_edwards()
1134 ctx->subm(Y3, D, Y3, ctx); in add_points_edwards()
1136 ctx->mulm(Y3, Y3, G, ctx); in add_points_edwards()
1137 ctx->mulm(Y3, Y3, A, ctx); in add_points_edwards()
1140 ctx->mulm(Z3, F, G, ctx); in add_points_edwards()
1162 /* Compute a step of Montgomery Ladder (only use X and Z in the point).
1163 * Inputs: P1, P2, and x-coordinate of DIF = P1 - P1.
1170 ctx->addm(sum->x, p2->x, p2->z, ctx); in montgomery_ladder()
1171 ctx->subm(p2->z, p2->x, p2->z, ctx); in montgomery_ladder()
1172 ctx->addm(prd->x, p1->x, p1->z, ctx); in montgomery_ladder()
1173 ctx->subm(p1->z, p1->x, p1->z, ctx); in montgomery_ladder()
1174 ctx->mulm(p2->x, p1->z, sum->x, ctx); in montgomery_ladder()
1175 ctx->mulm(p2->z, prd->x, p2->z, ctx); in montgomery_ladder()
1176 ctx->pow2(p1->x, prd->x, ctx); in montgomery_ladder()
1177 ctx->pow2(p1->z, p1->z, ctx); in montgomery_ladder()
1178 ctx->addm(sum->x, p2->x, p2->z, ctx); in montgomery_ladder()
1179 ctx->subm(p2->z, p2->x, p2->z, ctx); in montgomery_ladder()
1180 ctx->mulm(prd->x, p1->x, p1->z, ctx); in montgomery_ladder()
1181 ctx->subm(p1->z, p1->x, p1->z, ctx); in montgomery_ladder()
1182 ctx->pow2(sum->x, sum->x, ctx); in montgomery_ladder()
1183 ctx->pow2(sum->z, p2->z, ctx); in montgomery_ladder()
1184 ctx->mulm(prd->z, p1->z, ctx->a, ctx); /* CTX->A: (a-2)/4 */ in montgomery_ladder()
1185 ctx->mulm(sum->z, sum->z, dif_x, ctx); in montgomery_ladder()
1186 ctx->addm(prd->z, p1->x, prd->z, ctx); in montgomery_ladder()
1187 ctx->mulm(prd->z, prd->z, p1->z, ctx); in montgomery_ladder()
1195 switch (ctx->model) { in mpi_ec_add_points()
1209 /* Scalar point multiplication - the main function for ECC. If takes
1210 * an integer SCALAR and a POINT as well as the usual context CTX.
1211 * RESULT will be set to the resulting point.
1214 MPI scalar, MPI_POINT point, in mpi_ec_mul_point() argument
1221 if (ctx->model == MPI_EC_EDWARDS) { in mpi_ec_mul_point()
1227 * publisher = {Springer-Verlag New York, Inc.}} in mpi_ec_mul_point()
1232 if (mpi_cmp(scalar, ctx->p) >= 0) in mpi_ec_mul_point()
1235 nbits = mpi_get_nbits(ctx->p); in mpi_ec_mul_point()
1237 mpi_set_ui(result->x, 0); in mpi_ec_mul_point()
1238 mpi_set_ui(result->y, 1); in mpi_ec_mul_point()
1239 mpi_set_ui(result->z, 1); in mpi_ec_mul_point()
1240 point_resize(point, ctx); in mpi_ec_mul_point()
1243 point_resize(point, ctx); in mpi_ec_mul_point()
1245 for (j = nbits-1; j >= 0; j--) { in mpi_ec_mul_point()
1248 mpi_ec_add_points(result, result, point, ctx); in mpi_ec_mul_point()
1251 } else if (ctx->model == MPI_EC_MONTGOMERY) { in mpi_ec_mul_point()
1259 /* Compute scalar point multiplication with Montgomery Ladder. in mpi_ec_mul_point()
1260 * Note that we don't use Y-coordinate in the points at all. in mpi_ec_mul_point()
1261 * RESULT->Y will be filled by zero. in mpi_ec_mul_point()
1271 p2.x = mpi_copy(point->x); in mpi_ec_mul_point()
1279 mpi_resize(point->x, ctx->p->nlimbs); in mpi_ec_mul_point()
1280 point->x->nlimbs = ctx->p->nlimbs; in mpi_ec_mul_point()
1287 for (j = nbits-1; j >= 0; j--) { in mpi_ec_mul_point()
1292 montgomery_ladder(prd, sum, q1, q2, point->x, ctx); in mpi_ec_mul_point()
1298 mpi_clear(result->y); in mpi_ec_mul_point()
1302 rsize = p1.z->nlimbs; in mpi_ec_mul_point()
1303 MPN_NORMALIZE(p1.z->d, rsize); in mpi_ec_mul_point()
1305 mpi_set_ui(result->x, 1); in mpi_ec_mul_point()
1306 mpi_set_ui(result->z, 0); in mpi_ec_mul_point()
1310 ec_mulm(result->x, p1.x, z1, ctx); in mpi_ec_mul_point()
1311 mpi_set_ui(result->z, 1); in mpi_ec_mul_point()
1322 x1 = mpi_alloc_like(ctx->p); in mpi_ec_mul_point()
1323 y1 = mpi_alloc_like(ctx->p); in mpi_ec_mul_point()
1324 h = mpi_alloc_like(ctx->p); in mpi_ec_mul_point()
1326 yy = mpi_copy(point->y); in mpi_ec_mul_point()
1329 k->sign = 0; in mpi_ec_mul_point()
1333 if (!mpi_cmp_ui(point->z, 1)) { in mpi_ec_mul_point()
1334 mpi_set(x1, point->x); in mpi_ec_mul_point()
1339 z2 = mpi_alloc_like(ctx->p); in mpi_ec_mul_point()
1340 z3 = mpi_alloc_like(ctx->p); in mpi_ec_mul_point()
1341 ec_mulm(z2, point->z, point->z, ctx); in mpi_ec_mul_point()
1342 ec_mulm(z3, point->z, z2, ctx); in mpi_ec_mul_point()
1344 ec_mulm(x1, point->x, z2, ctx); in mpi_ec_mul_point()
1352 mpi_mul(h, k, mpi_const(MPI_C_THREE)); /* h = 3k */ in mpi_ec_mul_point()
1360 mpi_clear(result->x); in mpi_ec_mul_point()
1361 mpi_clear(result->y); in mpi_ec_mul_point()
1362 mpi_clear(result->z); in mpi_ec_mul_point()
1364 mpi_set(result->x, point->x); in mpi_ec_mul_point()
1365 mpi_set(result->y, yy); in mpi_ec_mul_point()
1366 mpi_set(result->z, point->z); in mpi_ec_mul_point()
1376 /* Invert point: y = p - y mod p */ in mpi_ec_mul_point()
1378 ec_subm(p1inv.y, ctx->p, p1inv.y, ctx); in mpi_ec_mul_point()
1380 for (i = loops-2; i > 0; i--) { in mpi_ec_mul_point()
1400 /* Return true if POINT is on the curve described by CTX. */
1401 int mpi_ec_curve_point(MPI_POINT point, struct mpi_ec_ctx *ctx) in mpi_ec_curve_point() argument
1410 /* Check that the point is in range. This needs to be done here and in mpi_ec_curve_point()
1413 if (mpi_cmpabs(point->x, ctx->p) >= 0) in mpi_ec_curve_point()
1415 if (mpi_cmpabs(point->y, ctx->p) >= 0) in mpi_ec_curve_point()
1417 if (mpi_cmpabs(point->z, ctx->p) >= 0) in mpi_ec_curve_point()
1420 switch (ctx->model) { in mpi_ec_curve_point()
1425 if (mpi_ec_get_affine(x, y, point, ctx)) in mpi_ec_curve_point()
1430 /* y^2 == x^3 + a·x + b */ in mpi_ec_curve_point()
1434 ec_mulm(w, ctx->a, x, ctx); in mpi_ec_curve_point()
1435 ec_addm(w, w, ctx->b, ctx); in mpi_ec_curve_point()
1448 /* With Montgomery curve, only X-coordinate is valid. */ in mpi_ec_curve_point()
1449 if (mpi_ec_get_affine(x, NULL, point, ctx)) in mpi_ec_curve_point()
1452 /* The equation is: b * y^2 == x^3 + a · x^2 + x */ in mpi_ec_curve_point()
1456 /* CTX->A has (a-2)/4 and CTX->B has b^-1 */ in mpi_ec_curve_point()
1457 ec_mulm(w, ctx->a, mpi_const(MPI_C_FOUR), ctx); in mpi_ec_curve_point()
1464 ec_mulm(w, w, ctx->b, ctx); in mpi_ec_curve_point()
1466 /* Compute Euler's criterion: w^(p-1)/2 */ in mpi_ec_curve_point()
1468 ec_subm(p_minus1, ctx->p, mpi_const(MPI_C_ONE), ctx); in mpi_ec_curve_point()
1479 if (mpi_ec_get_affine(x, y, point, ctx)) in mpi_ec_curve_point()
1482 mpi_resize(w, ctx->p->nlimbs); in mpi_ec_curve_point()
1483 w->nlimbs = ctx->p->nlimbs; in mpi_ec_curve_point()
1485 /* a · x^2 + y^2 - 1 - b · x^2 · y^2 == 0 */ in mpi_ec_curve_point()
1486 ctx->pow2(x, x, ctx); in mpi_ec_curve_point()
1487 ctx->pow2(y, y, ctx); in mpi_ec_curve_point()
1488 if (ctx->dialect == ECC_DIALECT_ED25519) in mpi_ec_curve_point()
1489 ctx->subm(w, ctx->p, x, ctx); in mpi_ec_curve_point()
1491 ctx->mulm(w, ctx->a, x, ctx); in mpi_ec_curve_point()
1492 ctx->addm(w, w, y, ctx); in mpi_ec_curve_point()
1493 ctx->mulm(x, x, y, ctx); in mpi_ec_curve_point()
1494 ctx->mulm(x, x, ctx->b, ctx); in mpi_ec_curve_point()
1495 ctx->subm(w, w, x, ctx); in mpi_ec_curve_point()