/* ec.c - Elliptic Curve functions * Copyright (C) 2007 Free Software Foundation, Inc. * Copyright (C) 2013 g10 Code GmbH * * This file is part of Libgcrypt. * * Libgcrypt is free software; you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * * Libgcrypt is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this program; if not, see <http://www.gnu.org/licenses/>. */ #include "mpi-internal.h"#include "longlong.h" #define point_init(a) mpi_point_init((a))#define point_free(a) mpi_point_free_parts((a)) #define log_error(fmt, ...) pr_err(fmt, ##__VA_ARGS__)#define log_fatal(fmt, ...) pr_err(fmt, ##__VA_ARGS__) #define DIM(v) (sizeof(v)/sizeof((v)[0])) /* Create a new point option. NBITS gives the size in bits of one * coordinate; it is only used to pre-allocate some resources and * might also be passed as 0 to use a default value. */MPI_POINT mpi_point_new(unsigned int nbits){ MPI_POINT p; (void)nbits; /* Currently not used. */ p = kmalloc(sizeof(*p), GFP_KERNEL); if (p) mpi_point_init(p); return p;}EXPORT_SYMBOL_GPL(mpi_point_new); /* Release the point object P. P may be NULL. */void mpi_point_release(MPI_POINT p){ if (p) { mpi_point_free_parts(p); kfree(p); }}EXPORT_SYMBOL_GPL(mpi_point_release); /* Initialize the fields of a point object. gcry_mpi_point_free_parts * may be used to release the fields. */void mpi_point_init(MPI_POINT p){ p->x = mpi_new(0); p->y = mpi_new(0); p->z = mpi_new(0);}EXPORT_SYMBOL_GPL(mpi_point_init); /* Release the parts of a point object. */void mpi_point_free_parts(MPI_POINT p){ mpi_free(p->x); p->x = NULL; mpi_free(p->y); p->y = NULL; mpi_free(p->z); p->z = NULL;}EXPORT_SYMBOL_GPL(mpi_point_free_parts); /* Set the value from S into D. */static void point_set(MPI_POINT d, MPI_POINT s){ mpi_set(d->x, s->x); mpi_set(d->y, s->y); mpi_set(d->z, s->z);} static void point_resize(MPI_POINT p, struct mpi_ec_ctx *ctx){ size_t nlimbs = ctx->p->nlimbs; mpi_resize(p->x, nlimbs); p->x->nlimbs = nlimbs; mpi_resize(p->z, nlimbs); p->z->nlimbs = nlimbs; if (ctx->model != MPI_EC_MONTGOMERY) { mpi_resize(p->y, nlimbs); p->y->nlimbs = nlimbs; }} static void point_swap_cond(MPI_POINT d, MPI_POINT s, unsigned long swap, struct mpi_ec_ctx *ctx){ mpi_swap_cond(d->x, s->x, swap); if (ctx->model != MPI_EC_MONTGOMERY) mpi_swap_cond(d->y, s->y, swap); mpi_swap_cond(d->z, s->z, swap);} /* W = W mod P. */static void ec_mod(MPI w, struct mpi_ec_ctx *ec){ if (ec->t.p_barrett) mpi_mod_barrett(w, w, ec->t.p_barrett); else mpi_mod(w, w, ec->p);} static void ec_addm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx){ mpi_add(w, u, v); ec_mod(w, ctx);} static void ec_subm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ec){ mpi_sub(w, u, v); while (w->sign) mpi_add(w, w, ec->p); /*ec_mod(w, ec);*/} static void ec_mulm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx){ mpi_mul(w, u, v); ec_mod(w, ctx);} /* W = 2 * U mod P. */static void ec_mul2(MPI w, MPI u, struct mpi_ec_ctx *ctx){ mpi_lshift(w, u, 1); ec_mod(w, ctx);} static void ec_powm(MPI w, const MPI b, const MPI e, struct mpi_ec_ctx *ctx){ mpi_powm(w, b, e, ctx->p); /* mpi_abs(w); */} /* Shortcut for * ec_powm(B, B, mpi_const(MPI_C_TWO), ctx); * for easier optimization. */static void ec_pow2(MPI w, const MPI b, struct mpi_ec_ctx *ctx){ /* Using mpi_mul is slightly faster (at least on amd64). */ /* mpi_powm(w, b, mpi_const(MPI_C_TWO), ctx->p); */ ec_mulm(w, b, b, ctx);} /* Shortcut for * ec_powm(B, B, mpi_const(MPI_C_THREE), ctx); * for easier optimization. */static void ec_pow3(MPI w, const MPI b, struct mpi_ec_ctx *ctx){ mpi_powm(w, b, mpi_const(MPI_C_THREE), ctx->p);} static void ec_invm(MPI x, MPI a, struct mpi_ec_ctx *ctx){ if (!mpi_invm(x, a, ctx->p)) log_error("ec_invm: inverse does not exist:\n");} static void mpih_set_cond(mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, unsigned long set){ mpi_size_t i; mpi_limb_t mask = ((mpi_limb_t)0) - set; mpi_limb_t x; for (i = 0; i < usize; i++) { x = mask & (wp[i] ^ up[i]); wp[i] = wp[i] ^ x; }} /* Routines for 2^255 - 19. */ #define LIMB_SIZE_25519 ((256+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB) static void ec_addm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx){ mpi_ptr_t wp, up, vp; mpi_size_t wsize = LIMB_SIZE_25519; mpi_limb_t n[LIMB_SIZE_25519]; mpi_limb_t borrow; if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) log_bug("addm_25519: different sizes\n"); memset(n, 0, sizeof(n)); up = u->d; vp = v->d; wp = w->d; mpihelp_add_n(wp, up, vp, wsize); borrow = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); mpihelp_add_n(wp, wp, n, wsize); wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));} static void ec_subm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx){ mpi_ptr_t wp, up, vp; mpi_size_t wsize = LIMB_SIZE_25519; mpi_limb_t n[LIMB_SIZE_25519]; mpi_limb_t borrow; if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) log_bug("subm_25519: different sizes\n"); memset(n, 0, sizeof(n)); up = u->d; vp = v->d; wp = w->d; borrow = mpihelp_sub_n(wp, up, vp, wsize); mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); mpihelp_add_n(wp, wp, n, wsize); wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));} static void ec_mulm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx){ mpi_ptr_t wp, up, vp; mpi_size_t wsize = LIMB_SIZE_25519; mpi_limb_t n[LIMB_SIZE_25519*2]; mpi_limb_t m[LIMB_SIZE_25519+1]; mpi_limb_t cy; int msb; (void)ctx; if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) log_bug("mulm_25519: different sizes\n"); up = u->d; vp = v->d; wp = w->d; mpihelp_mul_n(n, up, vp, wsize); memcpy(wp, n, wsize * BYTES_PER_MPI_LIMB); wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); memcpy(m, n+LIMB_SIZE_25519-1, (wsize+1) * BYTES_PER_MPI_LIMB); mpihelp_rshift(m, m, LIMB_SIZE_25519+1, (255 % BITS_PER_MPI_LIMB)); memcpy(n, m, wsize * BYTES_PER_MPI_LIMB); cy = mpihelp_lshift(m, m, LIMB_SIZE_25519, 4); m[LIMB_SIZE_25519] = cy; cy = mpihelp_add_n(m, m, n, wsize); m[LIMB_SIZE_25519] += cy; cy = mpihelp_add_n(m, m, n, wsize); m[LIMB_SIZE_25519] += cy; cy = mpihelp_add_n(m, m, n, wsize); m[LIMB_SIZE_25519] += cy; cy = mpihelp_add_n(wp, wp, m, wsize); m[LIMB_SIZE_25519] += cy; memset(m, 0, wsize * BYTES_PER_MPI_LIMB); msb = (wp[LIMB_SIZE_25519-1] >> (255 % BITS_PER_MPI_LIMB)); m[0] = (m[LIMB_SIZE_25519] * 2 + msb) * 19; wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); mpihelp_add_n(wp, wp, m, wsize); m[0] = 0; cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); mpih_set_cond(m, ctx->p->d, wsize, (cy != 0UL)); mpihelp_add_n(wp, wp, m, wsize);} static void ec_mul2_25519(MPI w, MPI u, struct mpi_ec_ctx *ctx){ ec_addm_25519(w, u, u, ctx);} static void ec_pow2_25519(MPI w, const MPI b, struct mpi_ec_ctx *ctx){ ec_mulm_25519(w, b, b, ctx);} /* Routines for 2^448 - 2^224 - 1. */ #define LIMB_SIZE_448 ((448+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB)#define LIMB_SIZE_HALF_448 ((LIMB_SIZE_448+1)/2) static void ec_addm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx){ mpi_ptr_t wp, up, vp; mpi_size_t wsize = LIMB_SIZE_448; mpi_limb_t n[LIMB_SIZE_448]; mpi_limb_t cy; if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) log_bug("addm_448: different sizes\n"); memset(n, 0, sizeof(n)); up = u->d; vp = v->d; wp = w->d; cy = mpihelp_add_n(wp, up, vp, wsize); mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL)); mpihelp_sub_n(wp, wp, n, wsize);} static void ec_subm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx){ mpi_ptr_t wp, up, vp; mpi_size_t wsize = LIMB_SIZE_448; mpi_limb_t n[LIMB_SIZE_448]; mpi_limb_t borrow; if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) log_bug("subm_448: different sizes\n"); memset(n, 0, sizeof(n)); up = u->d; vp = v->d; wp = w->d; borrow = mpihelp_sub_n(wp, up, vp, wsize); mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); mpihelp_add_n(wp, wp, n, wsize);} static void ec_mulm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx){ mpi_ptr_t wp, up, vp; mpi_size_t wsize = LIMB_SIZE_448; mpi_limb_t n[LIMB_SIZE_448*2]; mpi_limb_t a2[LIMB_SIZE_HALF_448]; mpi_limb_t a3[LIMB_SIZE_HALF_448]; mpi_limb_t b0[LIMB_SIZE_HALF_448]; mpi_limb_t b1[LIMB_SIZE_HALF_448]; mpi_limb_t cy; int i;#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) mpi_limb_t b1_rest, a3_rest;#endif if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) log_bug("mulm_448: different sizes\n"); up = u->d; vp = v->d; wp = w->d; mpihelp_mul_n(n, up, vp, wsize); for (i = 0; i < (wsize + 1) / 2; i++) { b0[i] = n[i]; b1[i] = n[i+wsize/2]; a2[i] = n[i+wsize]; a3[i] = n[i+wsize+wsize/2]; } #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) b0[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1; a2[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1; b1_rest = 0; a3_rest = 0; for (i = (wsize + 1) / 2 - 1; i >= 0; i--) { mpi_limb_t b1v, a3v; b1v = b1[i]; a3v = a3[i]; b1[i] = (b1_rest << 32) | (b1v >> 32); a3[i] = (a3_rest << 32) | (a3v >> 32); b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1); a3_rest = a3v & (((mpi_limb_t)1UL << 32)-1); }#endif cy = mpihelp_add_n(b0, b0, a2, LIMB_SIZE_HALF_448); cy += mpihelp_add_n(b0, b0, a3, LIMB_SIZE_HALF_448); for (i = 0; i < (wsize + 1) / 2; i++) wp[i] = b0[i];#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) wp[LIMB_SIZE_HALF_448-1] &= (((mpi_limb_t)1UL << 32)-1);#endif #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) cy = b0[LIMB_SIZE_HALF_448-1] >> 32;#endif cy = mpihelp_add_1(b1, b1, LIMB_SIZE_HALF_448, cy); cy += mpihelp_add_n(b1, b1, a2, LIMB_SIZE_HALF_448); cy += mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448); cy += mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448);#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) b1_rest = 0; for (i = (wsize + 1) / 2 - 1; i >= 0; i--) { mpi_limb_t b1v = b1[i]; b1[i] = (b1_rest << 32) | (b1v >> 32); b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1); } wp[LIMB_SIZE_HALF_448-1] |= (b1_rest << 32);#endif for (i = 0; i < wsize / 2; i++) wp[i+(wsize + 1) / 2] = b1[i]; #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) cy = b1[LIMB_SIZE_HALF_448-1];#endif memset(n, 0, wsize * BYTES_PER_MPI_LIMB); #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) n[LIMB_SIZE_HALF_448-1] = cy << 32;#else n[LIMB_SIZE_HALF_448] = cy;#endif n[0] = cy; mpihelp_add_n(wp, wp, n, wsize); memset(n, 0, wsize * BYTES_PER_MPI_LIMB); cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL)); mpihelp_add_n(wp, wp, n, wsize);} static void ec_mul2_448(MPI w, MPI u, struct mpi_ec_ctx *ctx){ ec_addm_448(w, u, u, ctx);} static void ec_pow2_448(MPI w, const MPI b, struct mpi_ec_ctx *ctx){ ec_mulm_448(w, b, b, ctx);} struct field_table { const char *p; /* computation routines for the field. */ void (*addm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); void (*subm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); void (*mulm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); void (*mul2)(MPI w, MPI u, struct mpi_ec_ctx *ctx); void (*pow2)(MPI w, const MPI b, struct mpi_ec_ctx *ctx);}; static const struct field_table field_table[] = { { "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED", ec_addm_25519, ec_subm_25519, ec_mulm_25519, ec_mul2_25519, ec_pow2_25519 }, { "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE" "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", ec_addm_448, ec_subm_448, ec_mulm_448, ec_mul2_448, ec_pow2_448 }, { NULL, NULL, NULL, NULL, NULL, NULL },}; /* Force recomputation of all helper variables. */static void mpi_ec_get_reset(struct mpi_ec_ctx *ec){ ec->t.valid.a_is_pminus3 = 0; ec->t.valid.two_inv_p = 0;} /* Accessor for helper variable. */static int ec_get_a_is_pminus3(struct mpi_ec_ctx *ec){ MPI tmp; if (!ec->t.valid.a_is_pminus3) { ec->t.valid.a_is_pminus3 = 1; tmp = mpi_alloc_like(ec->p); mpi_sub_ui(tmp, ec->p, 3);Lines 1–500 of 1506. Load more
/* ec.c - Elliptic Curve functions * Copyright (C) 2007 Free Software Foundation, Inc. * Copyright (C) 2013 g10 Code GmbH * * This file is part of Libgcrypt. * * Libgcrypt is free software; you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * * Libgcrypt is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this program; if not, see <http://www.gnu.org/licenses/>. */ #include "mpi-internal.h" #include "longlong.h" #define point_init(a) mpi_point_init((a)) #define point_free(a) mpi_point_free_parts((a)) #define log_error(fmt, ...) pr_err(fmt, ##__VA_ARGS__) #define log_fatal(fmt, ...) pr_err(fmt, ##__VA_ARGS__) #define DIM(v) (sizeof(v)/sizeof((v)[0])) /* Create a new point option. NBITS gives the size in bits of one * coordinate; it is only used to pre-allocate some resources and * might also be passed as 0 to use a default value. */ MPI_POINT mpi_point_new(unsigned int nbits) { MPI_POINT p; (void)nbits; /* Currently not used. */ p = kmalloc(sizeof(*p), GFP_KERNEL); if (p) mpi_point_init(p); return p; } EXPORT_SYMBOL_GPL(mpi_point_new); /* Release the point object P. P may be NULL. */ void mpi_point_release(MPI_POINT p) { if (p) { mpi_point_free_parts(p); kfree(p); } } EXPORT_SYMBOL_GPL(mpi_point_release); /* Initialize the fields of a point object. gcry_mpi_point_free_parts * may be used to release the fields. */ void mpi_point_init(MPI_POINT p) { p->x = mpi_new(0); p->y = mpi_new(0); p->z = mpi_new(0); } EXPORT_SYMBOL_GPL(mpi_point_init); /* Release the parts of a point object. */ void mpi_point_free_parts(MPI_POINT p) { mpi_free(p->x); p->x = NULL; mpi_free(p->y); p->y = NULL; mpi_free(p->z); p->z = NULL; } EXPORT_SYMBOL_GPL(mpi_point_free_parts); /* Set the value from S into D. */ static void point_set(MPI_POINT d, MPI_POINT s) { mpi_set(d->x, s->x); mpi_set(d->y, s->y); mpi_set(d->z, s->z); } static void point_resize(MPI_POINT p, struct mpi_ec_ctx *ctx) { size_t nlimbs = ctx->p->nlimbs; mpi_resize(p->x, nlimbs); p->x->nlimbs = nlimbs; mpi_resize(p->z, nlimbs); p->z->nlimbs = nlimbs; if (ctx->model != MPI_EC_MONTGOMERY) { mpi_resize(p->y, nlimbs); p->y->nlimbs = nlimbs; } } static void point_swap_cond(MPI_POINT d, MPI_POINT s, unsigned long swap, struct mpi_ec_ctx *ctx) { mpi_swap_cond(d->x, s->x, swap); if (ctx->model != MPI_EC_MONTGOMERY) mpi_swap_cond(d->y, s->y, swap); mpi_swap_cond(d->z, s->z, swap); } /* W = W mod P. */ static void ec_mod(MPI w, struct mpi_ec_ctx *ec) { if (ec->t.p_barrett) mpi_mod_barrett(w, w, ec->t.p_barrett); else mpi_mod(w, w, ec->p); } static void ec_addm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) { mpi_add(w, u, v); ec_mod(w, ctx); } static void ec_subm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ec) { mpi_sub(w, u, v); while (w->sign) mpi_add(w, w, ec->p); /*ec_mod(w, ec);*/ } static void ec_mulm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) { mpi_mul(w, u, v); ec_mod(w, ctx); } /* W = 2 * U mod P. */ static void ec_mul2(MPI w, MPI u, struct mpi_ec_ctx *ctx) { mpi_lshift(w, u, 1); ec_mod(w, ctx); } static void ec_powm(MPI w, const MPI b, const MPI e, struct mpi_ec_ctx *ctx) { mpi_powm(w, b, e, ctx->p); /* mpi_abs(w); */ } /* Shortcut for * ec_powm(B, B, mpi_const(MPI_C_TWO), ctx); * for easier optimization. */ static void ec_pow2(MPI w, const MPI b, struct mpi_ec_ctx *ctx) { /* Using mpi_mul is slightly faster (at least on amd64). */ /* mpi_powm(w, b, mpi_const(MPI_C_TWO), ctx->p); */ ec_mulm(w, b, b, ctx); } /* Shortcut for * ec_powm(B, B, mpi_const(MPI_C_THREE), ctx); * for easier optimization. */ static void ec_pow3(MPI w, const MPI b, struct mpi_ec_ctx *ctx) { mpi_powm(w, b, mpi_const(MPI_C_THREE), ctx->p); } static void ec_invm(MPI x, MPI a, struct mpi_ec_ctx *ctx) { if (!mpi_invm(x, a, ctx->p)) log_error("ec_invm: inverse does not exist:\n"); } static void mpih_set_cond(mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, unsigned long set) { mpi_size_t i; mpi_limb_t mask = ((mpi_limb_t)0) - set; mpi_limb_t x; for (i = 0; i < usize; i++) { x = mask & (wp[i] ^ up[i]); wp[i] = wp[i] ^ x; } } /* Routines for 2^255 - 19. */ #define LIMB_SIZE_25519 ((256+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB) static void ec_addm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) { mpi_ptr_t wp, up, vp; mpi_size_t wsize = LIMB_SIZE_25519; mpi_limb_t n[LIMB_SIZE_25519]; mpi_limb_t borrow; if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) log_bug("addm_25519: different sizes\n"); memset(n, 0, sizeof(n)); up = u->d; vp = v->d; wp = w->d; mpihelp_add_n(wp, up, vp, wsize); borrow = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); mpihelp_add_n(wp, wp, n, wsize); wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); } static void ec_subm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) { mpi_ptr_t wp, up, vp; mpi_size_t wsize = LIMB_SIZE_25519; mpi_limb_t n[LIMB_SIZE_25519]; mpi_limb_t borrow; if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) log_bug("subm_25519: different sizes\n"); memset(n, 0, sizeof(n)); up = u->d; vp = v->d; wp = w->d; borrow = mpihelp_sub_n(wp, up, vp, wsize); mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); mpihelp_add_n(wp, wp, n, wsize); wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); } static void ec_mulm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) { mpi_ptr_t wp, up, vp; mpi_size_t wsize = LIMB_SIZE_25519; mpi_limb_t n[LIMB_SIZE_25519*2]; mpi_limb_t m[LIMB_SIZE_25519+1]; mpi_limb_t cy; int msb; (void)ctx; if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) log_bug("mulm_25519: different sizes\n"); up = u->d; vp = v->d; wp = w->d; mpihelp_mul_n(n, up, vp, wsize); memcpy(wp, n, wsize * BYTES_PER_MPI_LIMB); wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); memcpy(m, n+LIMB_SIZE_25519-1, (wsize+1) * BYTES_PER_MPI_LIMB); mpihelp_rshift(m, m, LIMB_SIZE_25519+1, (255 % BITS_PER_MPI_LIMB)); memcpy(n, m, wsize * BYTES_PER_MPI_LIMB); cy = mpihelp_lshift(m, m, LIMB_SIZE_25519, 4); m[LIMB_SIZE_25519] = cy; cy = mpihelp_add_n(m, m, n, wsize); m[LIMB_SIZE_25519] += cy; cy = mpihelp_add_n(m, m, n, wsize); m[LIMB_SIZE_25519] += cy; cy = mpihelp_add_n(m, m, n, wsize); m[LIMB_SIZE_25519] += cy; cy = mpihelp_add_n(wp, wp, m, wsize); m[LIMB_SIZE_25519] += cy; memset(m, 0, wsize * BYTES_PER_MPI_LIMB); msb = (wp[LIMB_SIZE_25519-1] >> (255 % BITS_PER_MPI_LIMB)); m[0] = (m[LIMB_SIZE_25519] * 2 + msb) * 19; wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); mpihelp_add_n(wp, wp, m, wsize); m[0] = 0; cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); mpih_set_cond(m, ctx->p->d, wsize, (cy != 0UL)); mpihelp_add_n(wp, wp, m, wsize); } static void ec_mul2_25519(MPI w, MPI u, struct mpi_ec_ctx *ctx) { ec_addm_25519(w, u, u, ctx); } static void ec_pow2_25519(MPI w, const MPI b, struct mpi_ec_ctx *ctx) { ec_mulm_25519(w, b, b, ctx); } /* Routines for 2^448 - 2^224 - 1. */ #define LIMB_SIZE_448 ((448+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB) #define LIMB_SIZE_HALF_448 ((LIMB_SIZE_448+1)/2) static void ec_addm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) { mpi_ptr_t wp, up, vp; mpi_size_t wsize = LIMB_SIZE_448; mpi_limb_t n[LIMB_SIZE_448]; mpi_limb_t cy; if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) log_bug("addm_448: different sizes\n"); memset(n, 0, sizeof(n)); up = u->d; vp = v->d; wp = w->d; cy = mpihelp_add_n(wp, up, vp, wsize); mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL)); mpihelp_sub_n(wp, wp, n, wsize); } static void ec_subm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) { mpi_ptr_t wp, up, vp; mpi_size_t wsize = LIMB_SIZE_448; mpi_limb_t n[LIMB_SIZE_448]; mpi_limb_t borrow; if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) log_bug("subm_448: different sizes\n"); memset(n, 0, sizeof(n)); up = u->d; vp = v->d; wp = w->d; borrow = mpihelp_sub_n(wp, up, vp, wsize); mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); mpihelp_add_n(wp, wp, n, wsize); } static void ec_mulm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) { mpi_ptr_t wp, up, vp; mpi_size_t wsize = LIMB_SIZE_448; mpi_limb_t n[LIMB_SIZE_448*2]; mpi_limb_t a2[LIMB_SIZE_HALF_448]; mpi_limb_t a3[LIMB_SIZE_HALF_448]; mpi_limb_t b0[LIMB_SIZE_HALF_448]; mpi_limb_t b1[LIMB_SIZE_HALF_448]; mpi_limb_t cy; int i; #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) mpi_limb_t b1_rest, a3_rest; #endif if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) log_bug("mulm_448: different sizes\n"); up = u->d; vp = v->d; wp = w->d; mpihelp_mul_n(n, up, vp, wsize); for (i = 0; i < (wsize + 1) / 2; i++) { b0[i] = n[i]; b1[i] = n[i+wsize/2]; a2[i] = n[i+wsize]; a3[i] = n[i+wsize+wsize/2]; } #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) b0[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1; a2[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1; b1_rest = 0; a3_rest = 0; for (i = (wsize + 1) / 2 - 1; i >= 0; i--) { mpi_limb_t b1v, a3v; b1v = b1[i]; a3v = a3[i]; b1[i] = (b1_rest << 32) | (b1v >> 32); a3[i] = (a3_rest << 32) | (a3v >> 32); b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1); a3_rest = a3v & (((mpi_limb_t)1UL << 32)-1); } #endif cy = mpihelp_add_n(b0, b0, a2, LIMB_SIZE_HALF_448); cy += mpihelp_add_n(b0, b0, a3, LIMB_SIZE_HALF_448); for (i = 0; i < (wsize + 1) / 2; i++) wp[i] = b0[i]; #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) wp[LIMB_SIZE_HALF_448-1] &= (((mpi_limb_t)1UL << 32)-1); #endif #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) cy = b0[LIMB_SIZE_HALF_448-1] >> 32; #endif cy = mpihelp_add_1(b1, b1, LIMB_SIZE_HALF_448, cy); cy += mpihelp_add_n(b1, b1, a2, LIMB_SIZE_HALF_448); cy += mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448); cy += mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448); #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) b1_rest = 0; for (i = (wsize + 1) / 2 - 1; i >= 0; i--) { mpi_limb_t b1v = b1[i]; b1[i] = (b1_rest << 32) | (b1v >> 32); b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1); } wp[LIMB_SIZE_HALF_448-1] |= (b1_rest << 32); #endif for (i = 0; i < wsize / 2; i++) wp[i+(wsize + 1) / 2] = b1[i]; #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) cy = b1[LIMB_SIZE_HALF_448-1]; #endif memset(n, 0, wsize * BYTES_PER_MPI_LIMB); #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) n[LIMB_SIZE_HALF_448-1] = cy << 32; #else n[LIMB_SIZE_HALF_448] = cy; #endif n[0] = cy; mpihelp_add_n(wp, wp, n, wsize); memset(n, 0, wsize * BYTES_PER_MPI_LIMB); cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL)); mpihelp_add_n(wp, wp, n, wsize); } static void ec_mul2_448(MPI w, MPI u, struct mpi_ec_ctx *ctx) { ec_addm_448(w, u, u, ctx); } static void ec_pow2_448(MPI w, const MPI b, struct mpi_ec_ctx *ctx) { ec_mulm_448(w, b, b, ctx); } struct field_table { const char *p; /* computation routines for the field. */ void (*addm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); void (*subm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); void (*mulm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); void (*mul2)(MPI w, MPI u, struct mpi_ec_ctx *ctx); void (*pow2)(MPI w, const MPI b, struct mpi_ec_ctx *ctx); }; static const struct field_table field_table[] = { { "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED", ec_addm_25519, ec_subm_25519, ec_mulm_25519, ec_mul2_25519, ec_pow2_25519 }, { "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE" "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", ec_addm_448, ec_subm_448, ec_mulm_448, ec_mul2_448, ec_pow2_448 }, { NULL, NULL, NULL, NULL, NULL, NULL }, }; /* Force recomputation of all helper variables. */ static void mpi_ec_get_reset(struct mpi_ec_ctx *ec) { ec->t.valid.a_is_pminus3 = 0; ec->t.valid.two_inv_p = 0; } /* Accessor for helper variable. */ static int ec_get_a_is_pminus3(struct mpi_ec_ctx *ec) { MPI tmp; if (!ec->t.valid.a_is_pminus3) { ec->t.valid.a_is_pminus3 = 1; tmp = mpi_alloc_like(ec->p); mpi_sub_ui(tmp, ec->p, 3);