Back to home page

OSCL-LXR
 
 

     

0001 /* ec.c -  Elliptic Curve functions
0002  * Copyright (C) 2007 Free Software Foundation, Inc.
0003  * Copyright (C) 2013 g10 Code GmbH
0004  *
0005  * This file is part of Libgcrypt.
0006  *
0007  * Libgcrypt is free software; you can redistribute it and/or modify
0008  * it under the terms of the GNU Lesser General Public License as
0009  * published by the Free Software Foundation; either version 2.1 of
0010  * the License, or (at your option) any later version.
0011  *
0012  * Libgcrypt is distributed in the hope that it will be useful,
0013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
0014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
0015  * GNU Lesser General Public License for more details.
0016  *
0017  * You should have received a copy of the GNU Lesser General Public
0018  * License along with this program; if not, see <http://www.gnu.org/licenses/>.
0019  */
0020 
0021 #include "mpi-internal.h"
0022 #include "longlong.h"
0023 
0024 #define point_init(a)  mpi_point_init((a))
0025 #define point_free(a)  mpi_point_free_parts((a))
0026 
0027 #define log_error(fmt, ...) pr_err(fmt, ##__VA_ARGS__)
0028 #define log_fatal(fmt, ...) pr_err(fmt, ##__VA_ARGS__)
0029 
0030 #define DIM(v) (sizeof(v)/sizeof((v)[0]))
0031 
0032 
0033 /* Create a new point option.  NBITS gives the size in bits of one
0034  * coordinate; it is only used to pre-allocate some resources and
0035  * might also be passed as 0 to use a default value.
0036  */
0037 MPI_POINT mpi_point_new(unsigned int nbits)
0038 {
0039     MPI_POINT p;
0040 
0041     (void)nbits;  /* Currently not used.  */
0042 
0043     p = kmalloc(sizeof(*p), GFP_KERNEL);
0044     if (p)
0045         mpi_point_init(p);
0046     return p;
0047 }
0048 EXPORT_SYMBOL_GPL(mpi_point_new);
0049 
0050 /* Release the point object P.  P may be NULL. */
0051 void mpi_point_release(MPI_POINT p)
0052 {
0053     if (p) {
0054         mpi_point_free_parts(p);
0055         kfree(p);
0056     }
0057 }
0058 EXPORT_SYMBOL_GPL(mpi_point_release);
0059 
0060 /* Initialize the fields of a point object.  gcry_mpi_point_free_parts
0061  * may be used to release the fields.
0062  */
0063 void mpi_point_init(MPI_POINT p)
0064 {
0065     p->x = mpi_new(0);
0066     p->y = mpi_new(0);
0067     p->z = mpi_new(0);
0068 }
0069 EXPORT_SYMBOL_GPL(mpi_point_init);
0070 
0071 /* Release the parts of a point object. */
0072 void mpi_point_free_parts(MPI_POINT p)
0073 {
0074     mpi_free(p->x); p->x = NULL;
0075     mpi_free(p->y); p->y = NULL;
0076     mpi_free(p->z); p->z = NULL;
0077 }
0078 EXPORT_SYMBOL_GPL(mpi_point_free_parts);
0079 
0080 /* Set the value from S into D.  */
0081 static void point_set(MPI_POINT d, MPI_POINT s)
0082 {
0083     mpi_set(d->x, s->x);
0084     mpi_set(d->y, s->y);
0085     mpi_set(d->z, s->z);
0086 }
0087 
0088 static void point_resize(MPI_POINT p, struct mpi_ec_ctx *ctx)
0089 {
0090     size_t nlimbs = ctx->p->nlimbs;
0091 
0092     mpi_resize(p->x, nlimbs);
0093     p->x->nlimbs = nlimbs;
0094     mpi_resize(p->z, nlimbs);
0095     p->z->nlimbs = nlimbs;
0096 
0097     if (ctx->model != MPI_EC_MONTGOMERY) {
0098         mpi_resize(p->y, nlimbs);
0099         p->y->nlimbs = nlimbs;
0100     }
0101 }
0102 
0103 static void point_swap_cond(MPI_POINT d, MPI_POINT s, unsigned long swap,
0104         struct mpi_ec_ctx *ctx)
0105 {
0106     mpi_swap_cond(d->x, s->x, swap);
0107     if (ctx->model != MPI_EC_MONTGOMERY)
0108         mpi_swap_cond(d->y, s->y, swap);
0109     mpi_swap_cond(d->z, s->z, swap);
0110 }
0111 
0112 
0113 /* W = W mod P.  */
0114 static void ec_mod(MPI w, struct mpi_ec_ctx *ec)
0115 {
0116     if (ec->t.p_barrett)
0117         mpi_mod_barrett(w, w, ec->t.p_barrett);
0118     else
0119         mpi_mod(w, w, ec->p);
0120 }
0121 
0122 static void ec_addm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
0123 {
0124     mpi_add(w, u, v);
0125     ec_mod(w, ctx);
0126 }
0127 
0128 static void ec_subm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ec)
0129 {
0130     mpi_sub(w, u, v);
0131     while (w->sign)
0132         mpi_add(w, w, ec->p);
0133     /*ec_mod(w, ec);*/
0134 }
0135 
0136 static void ec_mulm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
0137 {
0138     mpi_mul(w, u, v);
0139     ec_mod(w, ctx);
0140 }
0141 
0142 /* W = 2 * U mod P.  */
0143 static void ec_mul2(MPI w, MPI u, struct mpi_ec_ctx *ctx)
0144 {
0145     mpi_lshift(w, u, 1);
0146     ec_mod(w, ctx);
0147 }
0148 
0149 static void ec_powm(MPI w, const MPI b, const MPI e,
0150         struct mpi_ec_ctx *ctx)
0151 {
0152     mpi_powm(w, b, e, ctx->p);
0153     /* mpi_abs(w); */
0154 }
0155 
0156 /* Shortcut for
0157  * ec_powm(B, B, mpi_const(MPI_C_TWO), ctx);
0158  * for easier optimization.
0159  */
0160 static void ec_pow2(MPI w, const MPI b, struct mpi_ec_ctx *ctx)
0161 {
0162     /* Using mpi_mul is slightly faster (at least on amd64).  */
0163     /* mpi_powm(w, b, mpi_const(MPI_C_TWO), ctx->p); */
0164     ec_mulm(w, b, b, ctx);
0165 }
0166 
0167 /* Shortcut for
0168  * ec_powm(B, B, mpi_const(MPI_C_THREE), ctx);
0169  * for easier optimization.
0170  */
0171 static void ec_pow3(MPI w, const MPI b, struct mpi_ec_ctx *ctx)
0172 {
0173     mpi_powm(w, b, mpi_const(MPI_C_THREE), ctx->p);
0174 }
0175 
0176 static void ec_invm(MPI x, MPI a, struct mpi_ec_ctx *ctx)
0177 {
0178     if (!mpi_invm(x, a, ctx->p))
0179         log_error("ec_invm: inverse does not exist:\n");
0180 }
0181 
0182 static void mpih_set_cond(mpi_ptr_t wp, mpi_ptr_t up,
0183         mpi_size_t usize, unsigned long set)
0184 {
0185     mpi_size_t i;
0186     mpi_limb_t mask = ((mpi_limb_t)0) - set;
0187     mpi_limb_t x;
0188 
0189     for (i = 0; i < usize; i++) {
0190         x = mask & (wp[i] ^ up[i]);
0191         wp[i] = wp[i] ^ x;
0192     }
0193 }
0194 
0195 /* Routines for 2^255 - 19.  */
0196 
0197 #define LIMB_SIZE_25519 ((256+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB)
0198 
0199 static void ec_addm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
0200 {
0201     mpi_ptr_t wp, up, vp;
0202     mpi_size_t wsize = LIMB_SIZE_25519;
0203     mpi_limb_t n[LIMB_SIZE_25519];
0204     mpi_limb_t borrow;
0205 
0206     if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
0207         log_bug("addm_25519: different sizes\n");
0208 
0209     memset(n, 0, sizeof(n));
0210     up = u->d;
0211     vp = v->d;
0212     wp = w->d;
0213 
0214     mpihelp_add_n(wp, up, vp, wsize);
0215     borrow = mpihelp_sub_n(wp, wp, ctx->p->d, wsize);
0216     mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL));
0217     mpihelp_add_n(wp, wp, n, wsize);
0218     wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));
0219 }
0220 
0221 static void ec_subm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
0222 {
0223     mpi_ptr_t wp, up, vp;
0224     mpi_size_t wsize = LIMB_SIZE_25519;
0225     mpi_limb_t n[LIMB_SIZE_25519];
0226     mpi_limb_t borrow;
0227 
0228     if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
0229         log_bug("subm_25519: different sizes\n");
0230 
0231     memset(n, 0, sizeof(n));
0232     up = u->d;
0233     vp = v->d;
0234     wp = w->d;
0235 
0236     borrow = mpihelp_sub_n(wp, up, vp, wsize);
0237     mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL));
0238     mpihelp_add_n(wp, wp, n, wsize);
0239     wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));
0240 }
0241 
0242 static void ec_mulm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
0243 {
0244     mpi_ptr_t wp, up, vp;
0245     mpi_size_t wsize = LIMB_SIZE_25519;
0246     mpi_limb_t n[LIMB_SIZE_25519*2];
0247     mpi_limb_t m[LIMB_SIZE_25519+1];
0248     mpi_limb_t cy;
0249     int msb;
0250 
0251     (void)ctx;
0252     if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
0253         log_bug("mulm_25519: different sizes\n");
0254 
0255     up = u->d;
0256     vp = v->d;
0257     wp = w->d;
0258 
0259     mpihelp_mul_n(n, up, vp, wsize);
0260     memcpy(wp, n, wsize * BYTES_PER_MPI_LIMB);
0261     wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));
0262 
0263     memcpy(m, n+LIMB_SIZE_25519-1, (wsize+1) * BYTES_PER_MPI_LIMB);
0264     mpihelp_rshift(m, m, LIMB_SIZE_25519+1, (255 % BITS_PER_MPI_LIMB));
0265 
0266     memcpy(n, m, wsize * BYTES_PER_MPI_LIMB);
0267     cy = mpihelp_lshift(m, m, LIMB_SIZE_25519, 4);
0268     m[LIMB_SIZE_25519] = cy;
0269     cy = mpihelp_add_n(m, m, n, wsize);
0270     m[LIMB_SIZE_25519] += cy;
0271     cy = mpihelp_add_n(m, m, n, wsize);
0272     m[LIMB_SIZE_25519] += cy;
0273     cy = mpihelp_add_n(m, m, n, wsize);
0274     m[LIMB_SIZE_25519] += cy;
0275 
0276     cy = mpihelp_add_n(wp, wp, m, wsize);
0277     m[LIMB_SIZE_25519] += cy;
0278 
0279     memset(m, 0, wsize * BYTES_PER_MPI_LIMB);
0280     msb = (wp[LIMB_SIZE_25519-1] >> (255 % BITS_PER_MPI_LIMB));
0281     m[0] = (m[LIMB_SIZE_25519] * 2 + msb) * 19;
0282     wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));
0283     mpihelp_add_n(wp, wp, m, wsize);
0284 
0285     m[0] = 0;
0286     cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize);
0287     mpih_set_cond(m, ctx->p->d, wsize, (cy != 0UL));
0288     mpihelp_add_n(wp, wp, m, wsize);
0289 }
0290 
0291 static void ec_mul2_25519(MPI w, MPI u, struct mpi_ec_ctx *ctx)
0292 {
0293     ec_addm_25519(w, u, u, ctx);
0294 }
0295 
0296 static void ec_pow2_25519(MPI w, const MPI b, struct mpi_ec_ctx *ctx)
0297 {
0298     ec_mulm_25519(w, b, b, ctx);
0299 }
0300 
0301 /* Routines for 2^448 - 2^224 - 1.  */
0302 
0303 #define LIMB_SIZE_448 ((448+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB)
0304 #define LIMB_SIZE_HALF_448 ((LIMB_SIZE_448+1)/2)
0305 
0306 static void ec_addm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
0307 {
0308     mpi_ptr_t wp, up, vp;
0309     mpi_size_t wsize = LIMB_SIZE_448;
0310     mpi_limb_t n[LIMB_SIZE_448];
0311     mpi_limb_t cy;
0312 
0313     if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
0314         log_bug("addm_448: different sizes\n");
0315 
0316     memset(n, 0, sizeof(n));
0317     up = u->d;
0318     vp = v->d;
0319     wp = w->d;
0320 
0321     cy = mpihelp_add_n(wp, up, vp, wsize);
0322     mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL));
0323     mpihelp_sub_n(wp, wp, n, wsize);
0324 }
0325 
0326 static void ec_subm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
0327 {
0328     mpi_ptr_t wp, up, vp;
0329     mpi_size_t wsize = LIMB_SIZE_448;
0330     mpi_limb_t n[LIMB_SIZE_448];
0331     mpi_limb_t borrow;
0332 
0333     if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
0334         log_bug("subm_448: different sizes\n");
0335 
0336     memset(n, 0, sizeof(n));
0337     up = u->d;
0338     vp = v->d;
0339     wp = w->d;
0340 
0341     borrow = mpihelp_sub_n(wp, up, vp, wsize);
0342     mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL));
0343     mpihelp_add_n(wp, wp, n, wsize);
0344 }
0345 
0346 static void ec_mulm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
0347 {
0348     mpi_ptr_t wp, up, vp;
0349     mpi_size_t wsize = LIMB_SIZE_448;
0350     mpi_limb_t n[LIMB_SIZE_448*2];
0351     mpi_limb_t a2[LIMB_SIZE_HALF_448];
0352     mpi_limb_t a3[LIMB_SIZE_HALF_448];
0353     mpi_limb_t b0[LIMB_SIZE_HALF_448];
0354     mpi_limb_t b1[LIMB_SIZE_HALF_448];
0355     mpi_limb_t cy;
0356     int i;
0357 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
0358     mpi_limb_t b1_rest, a3_rest;
0359 #endif
0360 
0361     if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
0362         log_bug("mulm_448: different sizes\n");
0363 
0364     up = u->d;
0365     vp = v->d;
0366     wp = w->d;
0367 
0368     mpihelp_mul_n(n, up, vp, wsize);
0369 
0370     for (i = 0; i < (wsize + 1) / 2; i++) {
0371         b0[i] = n[i];
0372         b1[i] = n[i+wsize/2];
0373         a2[i] = n[i+wsize];
0374         a3[i] = n[i+wsize+wsize/2];
0375     }
0376 
0377 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
0378     b0[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1;
0379     a2[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1;
0380 
0381     b1_rest = 0;
0382     a3_rest = 0;
0383 
0384     for (i = (wsize + 1) / 2 - 1; i >= 0; i--) {
0385         mpi_limb_t b1v, a3v;
0386         b1v = b1[i];
0387         a3v = a3[i];
0388         b1[i] = (b1_rest << 32) | (b1v >> 32);
0389         a3[i] = (a3_rest << 32) | (a3v >> 32);
0390         b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1);
0391         a3_rest = a3v & (((mpi_limb_t)1UL << 32)-1);
0392     }
0393 #endif
0394 
0395     cy = mpihelp_add_n(b0, b0, a2, LIMB_SIZE_HALF_448);
0396     cy += mpihelp_add_n(b0, b0, a3, LIMB_SIZE_HALF_448);
0397     for (i = 0; i < (wsize + 1) / 2; i++)
0398         wp[i] = b0[i];
0399 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
0400     wp[LIMB_SIZE_HALF_448-1] &= (((mpi_limb_t)1UL << 32)-1);
0401 #endif
0402 
0403 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
0404     cy = b0[LIMB_SIZE_HALF_448-1] >> 32;
0405 #endif
0406 
0407     cy = mpihelp_add_1(b1, b1, LIMB_SIZE_HALF_448, cy);
0408     cy += mpihelp_add_n(b1, b1, a2, LIMB_SIZE_HALF_448);
0409     cy += mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448);
0410     cy += mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448);
0411 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
0412     b1_rest = 0;
0413     for (i = (wsize + 1) / 2 - 1; i >= 0; i--) {
0414         mpi_limb_t b1v = b1[i];
0415         b1[i] = (b1_rest << 32) | (b1v >> 32);
0416         b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1);
0417     }
0418     wp[LIMB_SIZE_HALF_448-1] |= (b1_rest << 32);
0419 #endif
0420     for (i = 0; i < wsize / 2; i++)
0421         wp[i+(wsize + 1) / 2] = b1[i];
0422 
0423 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
0424     cy = b1[LIMB_SIZE_HALF_448-1];
0425 #endif
0426 
0427     memset(n, 0, wsize * BYTES_PER_MPI_LIMB);
0428 
0429 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
0430     n[LIMB_SIZE_HALF_448-1] = cy << 32;
0431 #else
0432     n[LIMB_SIZE_HALF_448] = cy;
0433 #endif
0434     n[0] = cy;
0435     mpihelp_add_n(wp, wp, n, wsize);
0436 
0437     memset(n, 0, wsize * BYTES_PER_MPI_LIMB);
0438     cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize);
0439     mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL));
0440     mpihelp_add_n(wp, wp, n, wsize);
0441 }
0442 
0443 static void ec_mul2_448(MPI w, MPI u, struct mpi_ec_ctx *ctx)
0444 {
0445     ec_addm_448(w, u, u, ctx);
0446 }
0447 
0448 static void ec_pow2_448(MPI w, const MPI b, struct mpi_ec_ctx *ctx)
0449 {
0450     ec_mulm_448(w, b, b, ctx);
0451 }
0452 
0453 struct field_table {
0454     const char *p;
0455 
0456     /* computation routines for the field.  */
0457     void (*addm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx);
0458     void (*subm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx);
0459     void (*mulm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx);
0460     void (*mul2)(MPI w, MPI u, struct mpi_ec_ctx *ctx);
0461     void (*pow2)(MPI w, const MPI b, struct mpi_ec_ctx *ctx);
0462 };
0463 
0464 static const struct field_table field_table[] = {
0465     {
0466         "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED",
0467         ec_addm_25519,
0468         ec_subm_25519,
0469         ec_mulm_25519,
0470         ec_mul2_25519,
0471         ec_pow2_25519
0472     },
0473     {
0474         "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE"
0475         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
0476         ec_addm_448,
0477         ec_subm_448,
0478         ec_mulm_448,
0479         ec_mul2_448,
0480         ec_pow2_448
0481     },
0482     { NULL, NULL, NULL, NULL, NULL, NULL },
0483 };
0484 
0485 /* Force recomputation of all helper variables.  */
0486 static void mpi_ec_get_reset(struct mpi_ec_ctx *ec)
0487 {
0488     ec->t.valid.a_is_pminus3 = 0;
0489     ec->t.valid.two_inv_p = 0;
0490 }
0491 
0492 /* Accessor for helper variable.  */
0493 static int ec_get_a_is_pminus3(struct mpi_ec_ctx *ec)
0494 {
0495     MPI tmp;
0496 
0497     if (!ec->t.valid.a_is_pminus3) {
0498         ec->t.valid.a_is_pminus3 = 1;
0499         tmp = mpi_alloc_like(ec->p);
0500         mpi_sub_ui(tmp, ec->p, 3);
0501         ec->t.a_is_pminus3 = !mpi_cmp(ec->a, tmp);
0502         mpi_free(tmp);
0503     }
0504 
0505     return ec->t.a_is_pminus3;
0506 }
0507 
0508 /* Accessor for helper variable.  */
0509 static MPI ec_get_two_inv_p(struct mpi_ec_ctx *ec)
0510 {
0511     if (!ec->t.valid.two_inv_p) {
0512         ec->t.valid.two_inv_p = 1;
0513         if (!ec->t.two_inv_p)
0514             ec->t.two_inv_p = mpi_alloc(0);
0515         ec_invm(ec->t.two_inv_p, mpi_const(MPI_C_TWO), ec);
0516     }
0517     return ec->t.two_inv_p;
0518 }
0519 
0520 static const char *const curve25519_bad_points[] = {
0521     "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed",
0522     "0x0000000000000000000000000000000000000000000000000000000000000000",
0523     "0x0000000000000000000000000000000000000000000000000000000000000001",
0524     "0x00b8495f16056286fdb1329ceb8d09da6ac49ff1fae35616aeb8413b7c7aebe0",
0525     "0x57119fd0dd4e22d8868e1c58c45c44045bef839c55b1d0b1248c50a3bc959c5f",
0526     "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec",
0527     "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffee",
0528     NULL
0529 };
0530 
0531 static const char *const curve448_bad_points[] = {
0532     "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
0533     "ffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
0534     "0x00000000000000000000000000000000000000000000000000000000"
0535     "00000000000000000000000000000000000000000000000000000000",
0536     "0x00000000000000000000000000000000000000000000000000000000"
0537     "00000000000000000000000000000000000000000000000000000001",
0538     "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
0539     "fffffffffffffffffffffffffffffffffffffffffffffffffffffffe",
0540     "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
0541     "00000000000000000000000000000000000000000000000000000000",
0542     NULL
0543 };
0544 
0545 static const char *const *bad_points_table[] = {
0546     curve25519_bad_points,
0547     curve448_bad_points,
0548 };
0549 
0550 static void mpi_ec_coefficient_normalize(MPI a, MPI p)
0551 {
0552     if (a->sign) {
0553         mpi_resize(a, p->nlimbs);
0554         mpihelp_sub_n(a->d, p->d, a->d, p->nlimbs);
0555         a->nlimbs = p->nlimbs;
0556         a->sign = 0;
0557     }
0558 }
0559 
0560 /* This function initialized a context for elliptic curve based on the
0561  * field GF(p).  P is the prime specifying this field, A is the first
0562  * coefficient.  CTX is expected to be zeroized.
0563  */
0564 void mpi_ec_init(struct mpi_ec_ctx *ctx, enum gcry_mpi_ec_models model,
0565             enum ecc_dialects dialect,
0566             int flags, MPI p, MPI a, MPI b)
0567 {
0568     int i;
0569     static int use_barrett = -1 /* TODO: 1 or -1 */;
0570 
0571     mpi_ec_coefficient_normalize(a, p);
0572     mpi_ec_coefficient_normalize(b, p);
0573 
0574     /* Fixme: Do we want to check some constraints? e.g.  a < p  */
0575 
0576     ctx->model = model;
0577     ctx->dialect = dialect;
0578     ctx->flags = flags;
0579     if (dialect == ECC_DIALECT_ED25519)
0580         ctx->nbits = 256;
0581     else
0582         ctx->nbits = mpi_get_nbits(p);
0583     ctx->p = mpi_copy(p);
0584     ctx->a = mpi_copy(a);
0585     ctx->b = mpi_copy(b);
0586 
0587     ctx->t.p_barrett = use_barrett > 0 ? mpi_barrett_init(ctx->p, 0) : NULL;
0588 
0589     mpi_ec_get_reset(ctx);
0590 
0591     if (model == MPI_EC_MONTGOMERY) {
0592         for (i = 0; i < DIM(bad_points_table); i++) {
0593             MPI p_candidate = mpi_scanval(bad_points_table[i][0]);
0594             int match_p = !mpi_cmp(ctx->p, p_candidate);
0595             int j;
0596 
0597             mpi_free(p_candidate);
0598             if (!match_p)
0599                 continue;
0600 
0601             for (j = 0; i < DIM(ctx->t.scratch) && bad_points_table[i][j]; j++)
0602                 ctx->t.scratch[j] = mpi_scanval(bad_points_table[i][j]);
0603         }
0604     } else {
0605         /* Allocate scratch variables.  */
0606         for (i = 0; i < DIM(ctx->t.scratch); i++)
0607             ctx->t.scratch[i] = mpi_alloc_like(ctx->p);
0608     }
0609 
0610     ctx->addm = ec_addm;
0611     ctx->subm = ec_subm;
0612     ctx->mulm = ec_mulm;
0613     ctx->mul2 = ec_mul2;
0614     ctx->pow2 = ec_pow2;
0615 
0616     for (i = 0; field_table[i].p; i++) {
0617         MPI f_p;
0618 
0619         f_p = mpi_scanval(field_table[i].p);
0620         if (!f_p)
0621             break;
0622 
0623         if (!mpi_cmp(p, f_p)) {
0624             ctx->addm = field_table[i].addm;
0625             ctx->subm = field_table[i].subm;
0626             ctx->mulm = field_table[i].mulm;
0627             ctx->mul2 = field_table[i].mul2;
0628             ctx->pow2 = field_table[i].pow2;
0629             mpi_free(f_p);
0630 
0631             mpi_resize(ctx->a, ctx->p->nlimbs);
0632             ctx->a->nlimbs = ctx->p->nlimbs;
0633 
0634             mpi_resize(ctx->b, ctx->p->nlimbs);
0635             ctx->b->nlimbs = ctx->p->nlimbs;
0636 
0637             for (i = 0; i < DIM(ctx->t.scratch) && ctx->t.scratch[i]; i++)
0638                 ctx->t.scratch[i]->nlimbs = ctx->p->nlimbs;
0639 
0640             break;
0641         }
0642 
0643         mpi_free(f_p);
0644     }
0645 }
0646 EXPORT_SYMBOL_GPL(mpi_ec_init);
0647 
0648 void mpi_ec_deinit(struct mpi_ec_ctx *ctx)
0649 {
0650     int i;
0651 
0652     mpi_barrett_free(ctx->t.p_barrett);
0653 
0654     /* Domain parameter.  */
0655     mpi_free(ctx->p);
0656     mpi_free(ctx->a);
0657     mpi_free(ctx->b);
0658     mpi_point_release(ctx->G);
0659     mpi_free(ctx->n);
0660 
0661     /* The key.  */
0662     mpi_point_release(ctx->Q);
0663     mpi_free(ctx->d);
0664 
0665     /* Private data of ec.c.  */
0666     mpi_free(ctx->t.two_inv_p);
0667 
0668     for (i = 0; i < DIM(ctx->t.scratch); i++)
0669         mpi_free(ctx->t.scratch[i]);
0670 }
0671 EXPORT_SYMBOL_GPL(mpi_ec_deinit);
0672 
0673 /* Compute the affine coordinates from the projective coordinates in
0674  * POINT.  Set them into X and Y.  If one coordinate is not required,
0675  * X or Y may be passed as NULL.  CTX is the usual context. Returns: 0
0676  * on success or !0 if POINT is at infinity.
0677  */
0678 int mpi_ec_get_affine(MPI x, MPI y, MPI_POINT point, struct mpi_ec_ctx *ctx)
0679 {
0680     if (!mpi_cmp_ui(point->z, 0))
0681         return -1;
0682 
0683     switch (ctx->model) {
0684     case MPI_EC_WEIERSTRASS: /* Using Jacobian coordinates.  */
0685         {
0686             MPI z1, z2, z3;
0687 
0688             z1 = mpi_new(0);
0689             z2 = mpi_new(0);
0690             ec_invm(z1, point->z, ctx);  /* z1 = z^(-1) mod p  */
0691             ec_mulm(z2, z1, z1, ctx);    /* z2 = z^(-2) mod p  */
0692 
0693             if (x)
0694                 ec_mulm(x, point->x, z2, ctx);
0695 
0696             if (y) {
0697                 z3 = mpi_new(0);
0698                 ec_mulm(z3, z2, z1, ctx);      /* z3 = z^(-3) mod p */
0699                 ec_mulm(y, point->y, z3, ctx);
0700                 mpi_free(z3);
0701             }
0702 
0703             mpi_free(z2);
0704             mpi_free(z1);
0705         }
0706         return 0;
0707 
0708     case MPI_EC_MONTGOMERY:
0709         {
0710             if (x)
0711                 mpi_set(x, point->x);
0712 
0713             if (y) {
0714                 log_fatal("%s: Getting Y-coordinate on %s is not supported\n",
0715                         "mpi_ec_get_affine", "Montgomery");
0716                 return -1;
0717             }
0718         }
0719         return 0;
0720 
0721     case MPI_EC_EDWARDS:
0722         {
0723             MPI z;
0724 
0725             z = mpi_new(0);
0726             ec_invm(z, point->z, ctx);
0727 
0728             mpi_resize(z, ctx->p->nlimbs);
0729             z->nlimbs = ctx->p->nlimbs;
0730 
0731             if (x) {
0732                 mpi_resize(x, ctx->p->nlimbs);
0733                 x->nlimbs = ctx->p->nlimbs;
0734                 ctx->mulm(x, point->x, z, ctx);
0735             }
0736             if (y) {
0737                 mpi_resize(y, ctx->p->nlimbs);
0738                 y->nlimbs = ctx->p->nlimbs;
0739                 ctx->mulm(y, point->y, z, ctx);
0740             }
0741 
0742             mpi_free(z);
0743         }
0744         return 0;
0745 
0746     default:
0747         return -1;
0748     }
0749 }
0750 EXPORT_SYMBOL_GPL(mpi_ec_get_affine);
0751 
0752 /*  RESULT = 2 * POINT  (Weierstrass version). */
0753 static void dup_point_weierstrass(MPI_POINT result,
0754         MPI_POINT point, struct mpi_ec_ctx *ctx)
0755 {
0756 #define x3 (result->x)
0757 #define y3 (result->y)
0758 #define z3 (result->z)
0759 #define t1 (ctx->t.scratch[0])
0760 #define t2 (ctx->t.scratch[1])
0761 #define t3 (ctx->t.scratch[2])
0762 #define l1 (ctx->t.scratch[3])
0763 #define l2 (ctx->t.scratch[4])
0764 #define l3 (ctx->t.scratch[5])
0765 
0766     if (!mpi_cmp_ui(point->y, 0) || !mpi_cmp_ui(point->z, 0)) {
0767         /* P_y == 0 || P_z == 0 => [1:1:0] */
0768         mpi_set_ui(x3, 1);
0769         mpi_set_ui(y3, 1);
0770         mpi_set_ui(z3, 0);
0771     } else {
0772         if (ec_get_a_is_pminus3(ctx)) {
0773             /* Use the faster case.  */
0774             /* L1 = 3(X - Z^2)(X + Z^2) */
0775             /*                          T1: used for Z^2. */
0776             /*                          T2: used for the right term. */
0777             ec_pow2(t1, point->z, ctx);
0778             ec_subm(l1, point->x, t1, ctx);
0779             ec_mulm(l1, l1, mpi_const(MPI_C_THREE), ctx);
0780             ec_addm(t2, point->x, t1, ctx);
0781             ec_mulm(l1, l1, t2, ctx);
0782         } else {
0783             /* Standard case. */
0784             /* L1 = 3X^2 + aZ^4 */
0785             /*                          T1: used for aZ^4. */
0786             ec_pow2(l1, point->x, ctx);
0787             ec_mulm(l1, l1, mpi_const(MPI_C_THREE), ctx);
0788             ec_powm(t1, point->z, mpi_const(MPI_C_FOUR), ctx);
0789             ec_mulm(t1, t1, ctx->a, ctx);
0790             ec_addm(l1, l1, t1, ctx);
0791         }
0792         /* Z3 = 2YZ */
0793         ec_mulm(z3, point->y, point->z, ctx);
0794         ec_mul2(z3, z3, ctx);
0795 
0796         /* L2 = 4XY^2 */
0797         /*                              T2: used for Y2; required later. */
0798         ec_pow2(t2, point->y, ctx);
0799         ec_mulm(l2, t2, point->x, ctx);
0800         ec_mulm(l2, l2, mpi_const(MPI_C_FOUR), ctx);
0801 
0802         /* X3 = L1^2 - 2L2 */
0803         /*                              T1: used for L2^2. */
0804         ec_pow2(x3, l1, ctx);
0805         ec_mul2(t1, l2, ctx);
0806         ec_subm(x3, x3, t1, ctx);
0807 
0808         /* L3 = 8Y^4 */
0809         /*                              T2: taken from above. */
0810         ec_pow2(t2, t2, ctx);
0811         ec_mulm(l3, t2, mpi_const(MPI_C_EIGHT), ctx);
0812 
0813         /* Y3 = L1(L2 - X3) - L3 */
0814         ec_subm(y3, l2, x3, ctx);
0815         ec_mulm(y3, y3, l1, ctx);
0816         ec_subm(y3, y3, l3, ctx);
0817     }
0818 
0819 #undef x3
0820 #undef y3
0821 #undef z3
0822 #undef t1
0823 #undef t2
0824 #undef t3
0825 #undef l1
0826 #undef l2
0827 #undef l3
0828 }
0829 
0830 /*  RESULT = 2 * POINT  (Montgomery version). */
0831 static void dup_point_montgomery(MPI_POINT result,
0832                 MPI_POINT point, struct mpi_ec_ctx *ctx)
0833 {
0834     (void)result;
0835     (void)point;
0836     (void)ctx;
0837     log_fatal("%s: %s not yet supported\n",
0838             "mpi_ec_dup_point", "Montgomery");
0839 }
0840 
0841 /*  RESULT = 2 * POINT  (Twisted Edwards version). */
0842 static void dup_point_edwards(MPI_POINT result,
0843         MPI_POINT point, struct mpi_ec_ctx *ctx)
0844 {
0845 #define X1 (point->x)
0846 #define Y1 (point->y)
0847 #define Z1 (point->z)
0848 #define X3 (result->x)
0849 #define Y3 (result->y)
0850 #define Z3 (result->z)
0851 #define B (ctx->t.scratch[0])
0852 #define C (ctx->t.scratch[1])
0853 #define D (ctx->t.scratch[2])
0854 #define E (ctx->t.scratch[3])
0855 #define F (ctx->t.scratch[4])
0856 #define H (ctx->t.scratch[5])
0857 #define J (ctx->t.scratch[6])
0858 
0859     /* Compute: (X_3 : Y_3 : Z_3) = 2( X_1 : Y_1 : Z_1 ) */
0860 
0861     /* B = (X_1 + Y_1)^2  */
0862     ctx->addm(B, X1, Y1, ctx);
0863     ctx->pow2(B, B, ctx);
0864 
0865     /* C = X_1^2 */
0866     /* D = Y_1^2 */
0867     ctx->pow2(C, X1, ctx);
0868     ctx->pow2(D, Y1, ctx);
0869 
0870     /* E = aC */
0871     if (ctx->dialect == ECC_DIALECT_ED25519)
0872         ctx->subm(E, ctx->p, C, ctx);
0873     else
0874         ctx->mulm(E, ctx->a, C, ctx);
0875 
0876     /* F = E + D */
0877     ctx->addm(F, E, D, ctx);
0878 
0879     /* H = Z_1^2 */
0880     ctx->pow2(H, Z1, ctx);
0881 
0882     /* J = F - 2H */
0883     ctx->mul2(J, H, ctx);
0884     ctx->subm(J, F, J, ctx);
0885 
0886     /* X_3 = (B - C - D) · J */
0887     ctx->subm(X3, B, C, ctx);
0888     ctx->subm(X3, X3, D, ctx);
0889     ctx->mulm(X3, X3, J, ctx);
0890 
0891     /* Y_3 = F · (E - D) */
0892     ctx->subm(Y3, E, D, ctx);
0893     ctx->mulm(Y3, Y3, F, ctx);
0894 
0895     /* Z_3 = F · J */
0896     ctx->mulm(Z3, F, J, ctx);
0897 
0898 #undef X1
0899 #undef Y1
0900 #undef Z1
0901 #undef X3
0902 #undef Y3
0903 #undef Z3
0904 #undef B
0905 #undef C
0906 #undef D
0907 #undef E
0908 #undef F
0909 #undef H
0910 #undef J
0911 }
0912 
0913 /*  RESULT = 2 * POINT  */
0914 static void
0915 mpi_ec_dup_point(MPI_POINT result, MPI_POINT point, struct mpi_ec_ctx *ctx)
0916 {
0917     switch (ctx->model) {
0918     case MPI_EC_WEIERSTRASS:
0919         dup_point_weierstrass(result, point, ctx);
0920         break;
0921     case MPI_EC_MONTGOMERY:
0922         dup_point_montgomery(result, point, ctx);
0923         break;
0924     case MPI_EC_EDWARDS:
0925         dup_point_edwards(result, point, ctx);
0926         break;
0927     }
0928 }
0929 
0930 /* RESULT = P1 + P2  (Weierstrass version).*/
0931 static void add_points_weierstrass(MPI_POINT result,
0932         MPI_POINT p1, MPI_POINT p2,
0933         struct mpi_ec_ctx *ctx)
0934 {
0935 #define x1 (p1->x)
0936 #define y1 (p1->y)
0937 #define z1 (p1->z)
0938 #define x2 (p2->x)
0939 #define y2 (p2->y)
0940 #define z2 (p2->z)
0941 #define x3 (result->x)
0942 #define y3 (result->y)
0943 #define z3 (result->z)
0944 #define l1 (ctx->t.scratch[0])
0945 #define l2 (ctx->t.scratch[1])
0946 #define l3 (ctx->t.scratch[2])
0947 #define l4 (ctx->t.scratch[3])
0948 #define l5 (ctx->t.scratch[4])
0949 #define l6 (ctx->t.scratch[5])
0950 #define l7 (ctx->t.scratch[6])
0951 #define l8 (ctx->t.scratch[7])
0952 #define l9 (ctx->t.scratch[8])
0953 #define t1 (ctx->t.scratch[9])
0954 #define t2 (ctx->t.scratch[10])
0955 
0956     if ((!mpi_cmp(x1, x2)) && (!mpi_cmp(y1, y2)) && (!mpi_cmp(z1, z2))) {
0957         /* Same point; need to call the duplicate function.  */
0958         mpi_ec_dup_point(result, p1, ctx);
0959     } else if (!mpi_cmp_ui(z1, 0)) {
0960         /* P1 is at infinity.  */
0961         mpi_set(x3, p2->x);
0962         mpi_set(y3, p2->y);
0963         mpi_set(z3, p2->z);
0964     } else if (!mpi_cmp_ui(z2, 0)) {
0965         /* P2 is at infinity.  */
0966         mpi_set(x3, p1->x);
0967         mpi_set(y3, p1->y);
0968         mpi_set(z3, p1->z);
0969     } else {
0970         int z1_is_one = !mpi_cmp_ui(z1, 1);
0971         int z2_is_one = !mpi_cmp_ui(z2, 1);
0972 
0973         /* l1 = x1 z2^2  */
0974         /* l2 = x2 z1^2  */
0975         if (z2_is_one)
0976             mpi_set(l1, x1);
0977         else {
0978             ec_pow2(l1, z2, ctx);
0979             ec_mulm(l1, l1, x1, ctx);
0980         }
0981         if (z1_is_one)
0982             mpi_set(l2, x2);
0983         else {
0984             ec_pow2(l2, z1, ctx);
0985             ec_mulm(l2, l2, x2, ctx);
0986         }
0987         /* l3 = l1 - l2 */
0988         ec_subm(l3, l1, l2, ctx);
0989         /* l4 = y1 z2^3  */
0990         ec_powm(l4, z2, mpi_const(MPI_C_THREE), ctx);
0991         ec_mulm(l4, l4, y1, ctx);
0992         /* l5 = y2 z1^3  */
0993         ec_powm(l5, z1, mpi_const(MPI_C_THREE), ctx);
0994         ec_mulm(l5, l5, y2, ctx);
0995         /* l6 = l4 - l5  */
0996         ec_subm(l6, l4, l5, ctx);
0997 
0998         if (!mpi_cmp_ui(l3, 0)) {
0999             if (!mpi_cmp_ui(l6, 0)) {
1000                 /* P1 and P2 are the same - use duplicate function. */
1001                 mpi_ec_dup_point(result, p1, ctx);
1002             } else {
1003                 /* P1 is the inverse of P2.  */
1004                 mpi_set_ui(x3, 1);
1005                 mpi_set_ui(y3, 1);
1006                 mpi_set_ui(z3, 0);
1007             }
1008         } else {
1009             /* l7 = l1 + l2  */
1010             ec_addm(l7, l1, l2, ctx);
1011             /* l8 = l4 + l5  */
1012             ec_addm(l8, l4, l5, ctx);
1013             /* z3 = z1 z2 l3  */
1014             ec_mulm(z3, z1, z2, ctx);
1015             ec_mulm(z3, z3, l3, ctx);
1016             /* x3 = l6^2 - l7 l3^2  */
1017             ec_pow2(t1, l6, ctx);
1018             ec_pow2(t2, l3, ctx);
1019             ec_mulm(t2, t2, l7, ctx);
1020             ec_subm(x3, t1, t2, ctx);
1021             /* l9 = l7 l3^2 - 2 x3  */
1022             ec_mul2(t1, x3, ctx);
1023             ec_subm(l9, t2, t1, ctx);
1024             /* y3 = (l9 l6 - l8 l3^3)/2  */
1025             ec_mulm(l9, l9, l6, ctx);
1026             ec_powm(t1, l3, mpi_const(MPI_C_THREE), ctx); /* fixme: Use saved value*/
1027             ec_mulm(t1, t1, l8, ctx);
1028             ec_subm(y3, l9, t1, ctx);
1029             ec_mulm(y3, y3, ec_get_two_inv_p(ctx), ctx);
1030         }
1031     }
1032 
1033 #undef x1
1034 #undef y1
1035 #undef z1
1036 #undef x2
1037 #undef y2
1038 #undef z2
1039 #undef x3
1040 #undef y3
1041 #undef z3
1042 #undef l1
1043 #undef l2
1044 #undef l3
1045 #undef l4
1046 #undef l5
1047 #undef l6
1048 #undef l7
1049 #undef l8
1050 #undef l9
1051 #undef t1
1052 #undef t2
1053 }
1054 
1055 /* RESULT = P1 + P2  (Montgomery version).*/
1056 static void add_points_montgomery(MPI_POINT result,
1057         MPI_POINT p1, MPI_POINT p2,
1058         struct mpi_ec_ctx *ctx)
1059 {
1060     (void)result;
1061     (void)p1;
1062     (void)p2;
1063     (void)ctx;
1064     log_fatal("%s: %s not yet supported\n",
1065             "mpi_ec_add_points", "Montgomery");
1066 }
1067 
1068 /* RESULT = P1 + P2  (Twisted Edwards version).*/
1069 static void add_points_edwards(MPI_POINT result,
1070         MPI_POINT p1, MPI_POINT p2,
1071         struct mpi_ec_ctx *ctx)
1072 {
1073 #define X1 (p1->x)
1074 #define Y1 (p1->y)
1075 #define Z1 (p1->z)
1076 #define X2 (p2->x)
1077 #define Y2 (p2->y)
1078 #define Z2 (p2->z)
1079 #define X3 (result->x)
1080 #define Y3 (result->y)
1081 #define Z3 (result->z)
1082 #define A (ctx->t.scratch[0])
1083 #define B (ctx->t.scratch[1])
1084 #define C (ctx->t.scratch[2])
1085 #define D (ctx->t.scratch[3])
1086 #define E (ctx->t.scratch[4])
1087 #define F (ctx->t.scratch[5])
1088 #define G (ctx->t.scratch[6])
1089 #define tmp (ctx->t.scratch[7])
1090 
1091     point_resize(result, ctx);
1092 
1093     /* Compute: (X_3 : Y_3 : Z_3) = (X_1 : Y_1 : Z_1) + (X_2 : Y_2 : Z_3) */
1094 
1095     /* A = Z1 · Z2 */
1096     ctx->mulm(A, Z1, Z2, ctx);
1097 
1098     /* B = A^2 */
1099     ctx->pow2(B, A, ctx);
1100 
1101     /* C = X1 · X2 */
1102     ctx->mulm(C, X1, X2, ctx);
1103 
1104     /* D = Y1 · Y2 */
1105     ctx->mulm(D, Y1, Y2, ctx);
1106 
1107     /* E = d · C · D */
1108     ctx->mulm(E, ctx->b, C, ctx);
1109     ctx->mulm(E, E, D, ctx);
1110 
1111     /* F = B - E */
1112     ctx->subm(F, B, E, ctx);
1113 
1114     /* G = B + E */
1115     ctx->addm(G, B, E, ctx);
1116 
1117     /* X_3 = A · F · ((X_1 + Y_1) · (X_2 + Y_2) - C - D) */
1118     ctx->addm(tmp, X1, Y1, ctx);
1119     ctx->addm(X3, X2, Y2, ctx);
1120     ctx->mulm(X3, X3, tmp, ctx);
1121     ctx->subm(X3, X3, C, ctx);
1122     ctx->subm(X3, X3, D, ctx);
1123     ctx->mulm(X3, X3, F, ctx);
1124     ctx->mulm(X3, X3, A, ctx);
1125 
1126     /* Y_3 = A · G · (D - aC) */
1127     if (ctx->dialect == ECC_DIALECT_ED25519) {
1128         ctx->addm(Y3, D, C, ctx);
1129     } else {
1130         ctx->mulm(Y3, ctx->a, C, ctx);
1131         ctx->subm(Y3, D, Y3, ctx);
1132     }
1133     ctx->mulm(Y3, Y3, G, ctx);
1134     ctx->mulm(Y3, Y3, A, ctx);
1135 
1136     /* Z_3 = F · G */
1137     ctx->mulm(Z3, F, G, ctx);
1138 
1139 
1140 #undef X1
1141 #undef Y1
1142 #undef Z1
1143 #undef X2
1144 #undef Y2
1145 #undef Z2
1146 #undef X3
1147 #undef Y3
1148 #undef Z3
1149 #undef A
1150 #undef B
1151 #undef C
1152 #undef D
1153 #undef E
1154 #undef F
1155 #undef G
1156 #undef tmp
1157 }
1158 
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.
1161  * Outputs: PRD = 2 * P1 and  SUM = P1 + P2.
1162  */
1163 static void montgomery_ladder(MPI_POINT prd, MPI_POINT sum,
1164         MPI_POINT p1, MPI_POINT p2, MPI dif_x,
1165         struct mpi_ec_ctx *ctx)
1166 {
1167     ctx->addm(sum->x, p2->x, p2->z, ctx);
1168     ctx->subm(p2->z, p2->x, p2->z, ctx);
1169     ctx->addm(prd->x, p1->x, p1->z, ctx);
1170     ctx->subm(p1->z, p1->x, p1->z, ctx);
1171     ctx->mulm(p2->x, p1->z, sum->x, ctx);
1172     ctx->mulm(p2->z, prd->x, p2->z, ctx);
1173     ctx->pow2(p1->x, prd->x, ctx);
1174     ctx->pow2(p1->z, p1->z, ctx);
1175     ctx->addm(sum->x, p2->x, p2->z, ctx);
1176     ctx->subm(p2->z, p2->x, p2->z, ctx);
1177     ctx->mulm(prd->x, p1->x, p1->z, ctx);
1178     ctx->subm(p1->z, p1->x, p1->z, ctx);
1179     ctx->pow2(sum->x, sum->x, ctx);
1180     ctx->pow2(sum->z, p2->z, ctx);
1181     ctx->mulm(prd->z, p1->z, ctx->a, ctx); /* CTX->A: (a-2)/4 */
1182     ctx->mulm(sum->z, sum->z, dif_x, ctx);
1183     ctx->addm(prd->z, p1->x, prd->z, ctx);
1184     ctx->mulm(prd->z, prd->z, p1->z, ctx);
1185 }
1186 
1187 /* RESULT = P1 + P2 */
1188 void mpi_ec_add_points(MPI_POINT result,
1189         MPI_POINT p1, MPI_POINT p2,
1190         struct mpi_ec_ctx *ctx)
1191 {
1192     switch (ctx->model) {
1193     case MPI_EC_WEIERSTRASS:
1194         add_points_weierstrass(result, p1, p2, ctx);
1195         break;
1196     case MPI_EC_MONTGOMERY:
1197         add_points_montgomery(result, p1, p2, ctx);
1198         break;
1199     case MPI_EC_EDWARDS:
1200         add_points_edwards(result, p1, p2, ctx);
1201         break;
1202     }
1203 }
1204 EXPORT_SYMBOL_GPL(mpi_ec_add_points);
1205 
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.
1208  * RESULT will be set to the resulting point.
1209  */
1210 void mpi_ec_mul_point(MPI_POINT result,
1211             MPI scalar, MPI_POINT point,
1212             struct mpi_ec_ctx *ctx)
1213 {
1214     MPI x1, y1, z1, k, h, yy;
1215     unsigned int i, loops;
1216     struct gcry_mpi_point p1, p2, p1inv;
1217 
1218     if (ctx->model == MPI_EC_EDWARDS) {
1219         /* Simple left to right binary method.  Algorithm 3.27 from
1220          * {author={Hankerson, Darrel and Menezes, Alfred J. and Vanstone, Scott},
1221          *  title = {Guide to Elliptic Curve Cryptography},
1222          *  year = {2003}, isbn = {038795273X},
1223          *  url = {http://www.cacr.math.uwaterloo.ca/ecc/},
1224          *  publisher = {Springer-Verlag New York, Inc.}}
1225          */
1226         unsigned int nbits;
1227         int j;
1228 
1229         if (mpi_cmp(scalar, ctx->p) >= 0)
1230             nbits = mpi_get_nbits(scalar);
1231         else
1232             nbits = mpi_get_nbits(ctx->p);
1233 
1234         mpi_set_ui(result->x, 0);
1235         mpi_set_ui(result->y, 1);
1236         mpi_set_ui(result->z, 1);
1237         point_resize(point, ctx);
1238 
1239         point_resize(result, ctx);
1240         point_resize(point, ctx);
1241 
1242         for (j = nbits-1; j >= 0; j--) {
1243             mpi_ec_dup_point(result, result, ctx);
1244             if (mpi_test_bit(scalar, j))
1245                 mpi_ec_add_points(result, result, point, ctx);
1246         }
1247         return;
1248     } else if (ctx->model == MPI_EC_MONTGOMERY) {
1249         unsigned int nbits;
1250         int j;
1251         struct gcry_mpi_point p1_, p2_;
1252         MPI_POINT q1, q2, prd, sum;
1253         unsigned long sw;
1254         mpi_size_t rsize;
1255 
1256         /* Compute scalar point multiplication with Montgomery Ladder.
1257          * Note that we don't use Y-coordinate in the points at all.
1258          * RESULT->Y will be filled by zero.
1259          */
1260 
1261         nbits = mpi_get_nbits(scalar);
1262         point_init(&p1);
1263         point_init(&p2);
1264         point_init(&p1_);
1265         point_init(&p2_);
1266         mpi_set_ui(p1.x, 1);
1267         mpi_free(p2.x);
1268         p2.x = mpi_copy(point->x);
1269         mpi_set_ui(p2.z, 1);
1270 
1271         point_resize(&p1, ctx);
1272         point_resize(&p2, ctx);
1273         point_resize(&p1_, ctx);
1274         point_resize(&p2_, ctx);
1275 
1276         mpi_resize(point->x, ctx->p->nlimbs);
1277         point->x->nlimbs = ctx->p->nlimbs;
1278 
1279         q1 = &p1;
1280         q2 = &p2;
1281         prd = &p1_;
1282         sum = &p2_;
1283 
1284         for (j = nbits-1; j >= 0; j--) {
1285             MPI_POINT t;
1286 
1287             sw = mpi_test_bit(scalar, j);
1288             point_swap_cond(q1, q2, sw, ctx);
1289             montgomery_ladder(prd, sum, q1, q2, point->x, ctx);
1290             point_swap_cond(prd, sum, sw, ctx);
1291             t = q1;  q1 = prd;  prd = t;
1292             t = q2;  q2 = sum;  sum = t;
1293         }
1294 
1295         mpi_clear(result->y);
1296         sw = (nbits & 1);
1297         point_swap_cond(&p1, &p1_, sw, ctx);
1298 
1299         rsize = p1.z->nlimbs;
1300         MPN_NORMALIZE(p1.z->d, rsize);
1301         if (rsize == 0) {
1302             mpi_set_ui(result->x, 1);
1303             mpi_set_ui(result->z, 0);
1304         } else {
1305             z1 = mpi_new(0);
1306             ec_invm(z1, p1.z, ctx);
1307             ec_mulm(result->x, p1.x, z1, ctx);
1308             mpi_set_ui(result->z, 1);
1309             mpi_free(z1);
1310         }
1311 
1312         point_free(&p1);
1313         point_free(&p2);
1314         point_free(&p1_);
1315         point_free(&p2_);
1316         return;
1317     }
1318 
1319     x1 = mpi_alloc_like(ctx->p);
1320     y1 = mpi_alloc_like(ctx->p);
1321     h  = mpi_alloc_like(ctx->p);
1322     k  = mpi_copy(scalar);
1323     yy = mpi_copy(point->y);
1324 
1325     if (mpi_has_sign(k)) {
1326         k->sign = 0;
1327         ec_invm(yy, yy, ctx);
1328     }
1329 
1330     if (!mpi_cmp_ui(point->z, 1)) {
1331         mpi_set(x1, point->x);
1332         mpi_set(y1, yy);
1333     } else {
1334         MPI z2, z3;
1335 
1336         z2 = mpi_alloc_like(ctx->p);
1337         z3 = mpi_alloc_like(ctx->p);
1338         ec_mulm(z2, point->z, point->z, ctx);
1339         ec_mulm(z3, point->z, z2, ctx);
1340         ec_invm(z2, z2, ctx);
1341         ec_mulm(x1, point->x, z2, ctx);
1342         ec_invm(z3, z3, ctx);
1343         ec_mulm(y1, yy, z3, ctx);
1344         mpi_free(z2);
1345         mpi_free(z3);
1346     }
1347     z1 = mpi_copy(mpi_const(MPI_C_ONE));
1348 
1349     mpi_mul(h, k, mpi_const(MPI_C_THREE)); /* h = 3k */
1350     loops = mpi_get_nbits(h);
1351     if (loops < 2) {
1352         /* If SCALAR is zero, the above mpi_mul sets H to zero and thus
1353          * LOOPs will be zero.  To avoid an underflow of I in the main
1354          * loop we set LOOP to 2 and the result to (0,0,0).
1355          */
1356         loops = 2;
1357         mpi_clear(result->x);
1358         mpi_clear(result->y);
1359         mpi_clear(result->z);
1360     } else {
1361         mpi_set(result->x, point->x);
1362         mpi_set(result->y, yy);
1363         mpi_set(result->z, point->z);
1364     }
1365     mpi_free(yy); yy = NULL;
1366 
1367     p1.x = x1; x1 = NULL;
1368     p1.y = y1; y1 = NULL;
1369     p1.z = z1; z1 = NULL;
1370     point_init(&p2);
1371     point_init(&p1inv);
1372 
1373     /* Invert point: y = p - y mod p  */
1374     point_set(&p1inv, &p1);
1375     ec_subm(p1inv.y, ctx->p, p1inv.y, ctx);
1376 
1377     for (i = loops-2; i > 0; i--) {
1378         mpi_ec_dup_point(result, result, ctx);
1379         if (mpi_test_bit(h, i) == 1 && mpi_test_bit(k, i) == 0) {
1380             point_set(&p2, result);
1381             mpi_ec_add_points(result, &p2, &p1, ctx);
1382         }
1383         if (mpi_test_bit(h, i) == 0 && mpi_test_bit(k, i) == 1) {
1384             point_set(&p2, result);
1385             mpi_ec_add_points(result, &p2, &p1inv, ctx);
1386         }
1387     }
1388 
1389     point_free(&p1);
1390     point_free(&p2);
1391     point_free(&p1inv);
1392     mpi_free(h);
1393     mpi_free(k);
1394 }
1395 EXPORT_SYMBOL_GPL(mpi_ec_mul_point);
1396 
1397 /* Return true if POINT is on the curve described by CTX.  */
1398 int mpi_ec_curve_point(MPI_POINT point, struct mpi_ec_ctx *ctx)
1399 {
1400     int res = 0;
1401     MPI x, y, w;
1402 
1403     x = mpi_new(0);
1404     y = mpi_new(0);
1405     w = mpi_new(0);
1406 
1407     /* Check that the point is in range.  This needs to be done here and
1408      * not after conversion to affine coordinates.
1409      */
1410     if (mpi_cmpabs(point->x, ctx->p) >= 0)
1411         goto leave;
1412     if (mpi_cmpabs(point->y, ctx->p) >= 0)
1413         goto leave;
1414     if (mpi_cmpabs(point->z, ctx->p) >= 0)
1415         goto leave;
1416 
1417     switch (ctx->model) {
1418     case MPI_EC_WEIERSTRASS:
1419         {
1420             MPI xxx;
1421 
1422             if (mpi_ec_get_affine(x, y, point, ctx))
1423                 goto leave;
1424 
1425             xxx = mpi_new(0);
1426 
1427             /* y^2 == x^3 + a·x + b */
1428             ec_pow2(y, y, ctx);
1429 
1430             ec_pow3(xxx, x, ctx);
1431             ec_mulm(w, ctx->a, x, ctx);
1432             ec_addm(w, w, ctx->b, ctx);
1433             ec_addm(w, w, xxx, ctx);
1434 
1435             if (!mpi_cmp(y, w))
1436                 res = 1;
1437 
1438             mpi_free(xxx);
1439         }
1440         break;
1441 
1442     case MPI_EC_MONTGOMERY:
1443         {
1444 #define xx y
1445             /* With Montgomery curve, only X-coordinate is valid. */
1446             if (mpi_ec_get_affine(x, NULL, point, ctx))
1447                 goto leave;
1448 
1449             /* The equation is: b * y^2 == x^3 + a · x^2 + x */
1450             /* We check if right hand is quadratic residue or not by
1451              * Euler's criterion.
1452              */
1453             /* CTX->A has (a-2)/4 and CTX->B has b^-1 */
1454             ec_mulm(w, ctx->a, mpi_const(MPI_C_FOUR), ctx);
1455             ec_addm(w, w, mpi_const(MPI_C_TWO), ctx);
1456             ec_mulm(w, w, x, ctx);
1457             ec_pow2(xx, x, ctx);
1458             ec_addm(w, w, xx, ctx);
1459             ec_addm(w, w, mpi_const(MPI_C_ONE), ctx);
1460             ec_mulm(w, w, x, ctx);
1461             ec_mulm(w, w, ctx->b, ctx);
1462 #undef xx
1463             /* Compute Euler's criterion: w^(p-1)/2 */
1464 #define p_minus1 y
1465             ec_subm(p_minus1, ctx->p, mpi_const(MPI_C_ONE), ctx);
1466             mpi_rshift(p_minus1, p_minus1, 1);
1467             ec_powm(w, w, p_minus1, ctx);
1468 
1469             res = !mpi_cmp_ui(w, 1);
1470 #undef p_minus1
1471         }
1472         break;
1473 
1474     case MPI_EC_EDWARDS:
1475         {
1476             if (mpi_ec_get_affine(x, y, point, ctx))
1477                 goto leave;
1478 
1479             mpi_resize(w, ctx->p->nlimbs);
1480             w->nlimbs = ctx->p->nlimbs;
1481 
1482             /* a · x^2 + y^2 - 1 - b · x^2 · y^2 == 0 */
1483             ctx->pow2(x, x, ctx);
1484             ctx->pow2(y, y, ctx);
1485             if (ctx->dialect == ECC_DIALECT_ED25519)
1486                 ctx->subm(w, ctx->p, x, ctx);
1487             else
1488                 ctx->mulm(w, ctx->a, x, ctx);
1489             ctx->addm(w, w, y, ctx);
1490             ctx->mulm(x, x, y, ctx);
1491             ctx->mulm(x, x, ctx->b, ctx);
1492             ctx->subm(w, w, x, ctx);
1493             if (!mpi_cmp_ui(w, 1))
1494                 res = 1;
1495         }
1496         break;
1497     }
1498 
1499 leave:
1500     mpi_free(w);
1501     mpi_free(x);
1502     mpi_free(y);
1503 
1504     return res;
1505 }
1506 EXPORT_SYMBOL_GPL(mpi_ec_curve_point);
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!