1 /* ec.c - Elliptic Curve functions 2 * Copyright (C) 2007 Free Software Foundation, Inc. 3 * Copyright (C) 2013 g10 Code GmbH 4 * 5 * This file is part of Libgcrypt. 6 * 7 * Libgcrypt is free software; you can redistribute it and/or modify 8 * it under the terms of the GNU Lesser General Public License as 9 * published by the Free Software Foundation; either version 2.1 of 10 * the License, or (at your option) any later version. 11 * 12 * Libgcrypt is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * GNU Lesser General Public License for more details. 16 * 17 * You should have received a copy of the GNU Lesser General Public 18 * License along with this program; if not, see <http://www.gnu.org/licenses/>. 19 */ 20 21 #include "mpi-internal.h" 22 #include "longlong.h" 23 24 #define point_init(a) mpi_point_init((a)) 25 #define point_free(a) mpi_point_free_parts((a)) 26 27 #define log_error(fmt, ...) pr_err(fmt, ##__VA_ARGS__) 28 #define log_fatal(fmt, ...) pr_err(fmt, ##__VA_ARGS__) 29 30 #define DIM(v) (sizeof(v)/sizeof((v)[0])) 31 32 33 /* Create a new point option. NBITS gives the size in bits of one 34 * coordinate; it is only used to pre-allocate some resources and 35 * might also be passed as 0 to use a default value. 36 */ 37 MPI_POINT mpi_point_new(unsigned int nbits) 38 { 39 MPI_POINT p; 40 41 (void)nbits; /* Currently not used. */ 42 43 p = kmalloc(sizeof(*p), GFP_KERNEL); 44 if (p) 45 mpi_point_init(p); 46 return p; 47 } 48 EXPORT_SYMBOL_GPL(mpi_point_new); 49 50 /* Release the point object P. P may be NULL. */ 51 void mpi_point_release(MPI_POINT p) 52 { 53 if (p) { 54 mpi_point_free_parts(p); 55 kfree(p); 56 } 57 } 58 EXPORT_SYMBOL_GPL(mpi_point_release); 59 60 /* Initialize the fields of a point object. gcry_mpi_point_free_parts 61 * may be used to release the fields. 62 */ 63 void mpi_point_init(MPI_POINT p) 64 { 65 p->x = mpi_new(0); 66 p->y = mpi_new(0); 67 p->z = mpi_new(0); 68 } 69 EXPORT_SYMBOL_GPL(mpi_point_init); 70 71 /* Release the parts of a point object. */ 72 void mpi_point_free_parts(MPI_POINT p) 73 { 74 mpi_free(p->x); p->x = NULL; 75 mpi_free(p->y); p->y = NULL; 76 mpi_free(p->z); p->z = NULL; 77 } 78 EXPORT_SYMBOL_GPL(mpi_point_free_parts); 79 80 /* Set the value from S into D. */ 81 static void point_set(MPI_POINT d, MPI_POINT s) 82 { 83 mpi_set(d->x, s->x); 84 mpi_set(d->y, s->y); 85 mpi_set(d->z, s->z); 86 } 87 88 static void point_resize(MPI_POINT p, struct mpi_ec_ctx *ctx) 89 { 90 size_t nlimbs = ctx->p->nlimbs; 91 92 mpi_resize(p->x, nlimbs); 93 p->x->nlimbs = nlimbs; 94 mpi_resize(p->z, nlimbs); 95 p->z->nlimbs = nlimbs; 96 97 if (ctx->model != MPI_EC_MONTGOMERY) { 98 mpi_resize(p->y, nlimbs); 99 p->y->nlimbs = nlimbs; 100 } 101 } 102 103 static void point_swap_cond(MPI_POINT d, MPI_POINT s, unsigned long swap, 104 struct mpi_ec_ctx *ctx) 105 { 106 mpi_swap_cond(d->x, s->x, swap); 107 if (ctx->model != MPI_EC_MONTGOMERY) 108 mpi_swap_cond(d->y, s->y, swap); 109 mpi_swap_cond(d->z, s->z, swap); 110 } 111 112 113 /* W = W mod P. */ 114 static void ec_mod(MPI w, struct mpi_ec_ctx *ec) 115 { 116 if (ec->t.p_barrett) 117 mpi_mod_barrett(w, w, ec->t.p_barrett); 118 else 119 mpi_mod(w, w, ec->p); 120 } 121 122 static void ec_addm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) 123 { 124 mpi_add(w, u, v); 125 ec_mod(w, ctx); 126 } 127 128 static void ec_subm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ec) 129 { 130 mpi_sub(w, u, v); 131 while (w->sign) 132 mpi_add(w, w, ec->p); 133 /*ec_mod(w, ec);*/ 134 } 135 136 static void ec_mulm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) 137 { 138 mpi_mul(w, u, v); 139 ec_mod(w, ctx); 140 } 141 142 /* W = 2 * U mod P. */ 143 static void ec_mul2(MPI w, MPI u, struct mpi_ec_ctx *ctx) 144 { 145 mpi_lshift(w, u, 1); 146 ec_mod(w, ctx); 147 } 148 149 static void ec_powm(MPI w, const MPI b, const MPI e, 150 struct mpi_ec_ctx *ctx) 151 { 152 mpi_powm(w, b, e, ctx->p); 153 /* mpi_abs(w); */ 154 } 155 156 /* Shortcut for 157 * ec_powm(B, B, mpi_const(MPI_C_TWO), ctx); 158 * for easier optimization. 159 */ 160 static void ec_pow2(MPI w, const MPI b, struct mpi_ec_ctx *ctx) 161 { 162 /* Using mpi_mul is slightly faster (at least on amd64). */ 163 /* mpi_powm(w, b, mpi_const(MPI_C_TWO), ctx->p); */ 164 ec_mulm(w, b, b, ctx); 165 } 166 167 /* Shortcut for 168 * ec_powm(B, B, mpi_const(MPI_C_THREE), ctx); 169 * for easier optimization. 170 */ 171 static void ec_pow3(MPI w, const MPI b, struct mpi_ec_ctx *ctx) 172 { 173 mpi_powm(w, b, mpi_const(MPI_C_THREE), ctx->p); 174 } 175 176 static void ec_invm(MPI x, MPI a, struct mpi_ec_ctx *ctx) 177 { 178 if (!mpi_invm(x, a, ctx->p)) 179 log_error("ec_invm: inverse does not exist:\n"); 180 } 181 182 static void mpih_set_cond(mpi_ptr_t wp, mpi_ptr_t up, 183 mpi_size_t usize, unsigned long set) 184 { 185 mpi_size_t i; 186 mpi_limb_t mask = ((mpi_limb_t)0) - set; 187 mpi_limb_t x; 188 189 for (i = 0; i < usize; i++) { 190 x = mask & (wp[i] ^ up[i]); 191 wp[i] = wp[i] ^ x; 192 } 193 } 194 195 /* Routines for 2^255 - 19. */ 196 197 #define LIMB_SIZE_25519 ((256+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB) 198 199 static void ec_addm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) 200 { 201 mpi_ptr_t wp, up, vp; 202 mpi_size_t wsize = LIMB_SIZE_25519; 203 mpi_limb_t n[LIMB_SIZE_25519]; 204 mpi_limb_t borrow; 205 206 if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) 207 log_bug("addm_25519: different sizes\n"); 208 209 memset(n, 0, sizeof(n)); 210 up = u->d; 211 vp = v->d; 212 wp = w->d; 213 214 mpihelp_add_n(wp, up, vp, wsize); 215 borrow = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); 216 mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); 217 mpihelp_add_n(wp, wp, n, wsize); 218 wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); 219 } 220 221 static void ec_subm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) 222 { 223 mpi_ptr_t wp, up, vp; 224 mpi_size_t wsize = LIMB_SIZE_25519; 225 mpi_limb_t n[LIMB_SIZE_25519]; 226 mpi_limb_t borrow; 227 228 if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) 229 log_bug("subm_25519: different sizes\n"); 230 231 memset(n, 0, sizeof(n)); 232 up = u->d; 233 vp = v->d; 234 wp = w->d; 235 236 borrow = mpihelp_sub_n(wp, up, vp, wsize); 237 mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); 238 mpihelp_add_n(wp, wp, n, wsize); 239 wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); 240 } 241 242 static void ec_mulm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) 243 { 244 mpi_ptr_t wp, up, vp; 245 mpi_size_t wsize = LIMB_SIZE_25519; 246 mpi_limb_t n[LIMB_SIZE_25519*2]; 247 mpi_limb_t m[LIMB_SIZE_25519+1]; 248 mpi_limb_t cy; 249 int msb; 250 251 (void)ctx; 252 if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) 253 log_bug("mulm_25519: different sizes\n"); 254 255 up = u->d; 256 vp = v->d; 257 wp = w->d; 258 259 mpihelp_mul_n(n, up, vp, wsize); 260 memcpy(wp, n, wsize * BYTES_PER_MPI_LIMB); 261 wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); 262 263 memcpy(m, n+LIMB_SIZE_25519-1, (wsize+1) * BYTES_PER_MPI_LIMB); 264 mpihelp_rshift(m, m, LIMB_SIZE_25519+1, (255 % BITS_PER_MPI_LIMB)); 265 266 memcpy(n, m, wsize * BYTES_PER_MPI_LIMB); 267 cy = mpihelp_lshift(m, m, LIMB_SIZE_25519, 4); 268 m[LIMB_SIZE_25519] = cy; 269 cy = mpihelp_add_n(m, m, n, wsize); 270 m[LIMB_SIZE_25519] += cy; 271 cy = mpihelp_add_n(m, m, n, wsize); 272 m[LIMB_SIZE_25519] += cy; 273 cy = mpihelp_add_n(m, m, n, wsize); 274 m[LIMB_SIZE_25519] += cy; 275 276 cy = mpihelp_add_n(wp, wp, m, wsize); 277 m[LIMB_SIZE_25519] += cy; 278 279 memset(m, 0, wsize * BYTES_PER_MPI_LIMB); 280 msb = (wp[LIMB_SIZE_25519-1] >> (255 % BITS_PER_MPI_LIMB)); 281 m[0] = (m[LIMB_SIZE_25519] * 2 + msb) * 19; 282 wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); 283 mpihelp_add_n(wp, wp, m, wsize); 284 285 m[0] = 0; 286 cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); 287 mpih_set_cond(m, ctx->p->d, wsize, (cy != 0UL)); 288 mpihelp_add_n(wp, wp, m, wsize); 289 } 290 291 static void ec_mul2_25519(MPI w, MPI u, struct mpi_ec_ctx *ctx) 292 { 293 ec_addm_25519(w, u, u, ctx); 294 } 295 296 static void ec_pow2_25519(MPI w, const MPI b, struct mpi_ec_ctx *ctx) 297 { 298 ec_mulm_25519(w, b, b, ctx); 299 } 300 301 /* Routines for 2^448 - 2^224 - 1. */ 302 303 #define LIMB_SIZE_448 ((448+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB) 304 #define LIMB_SIZE_HALF_448 ((LIMB_SIZE_448+1)/2) 305 306 static void ec_addm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) 307 { 308 mpi_ptr_t wp, up, vp; 309 mpi_size_t wsize = LIMB_SIZE_448; 310 mpi_limb_t n[LIMB_SIZE_448]; 311 mpi_limb_t cy; 312 313 if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) 314 log_bug("addm_448: different sizes\n"); 315 316 memset(n, 0, sizeof(n)); 317 up = u->d; 318 vp = v->d; 319 wp = w->d; 320 321 cy = mpihelp_add_n(wp, up, vp, wsize); 322 mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL)); 323 mpihelp_sub_n(wp, wp, n, wsize); 324 } 325 326 static void ec_subm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) 327 { 328 mpi_ptr_t wp, up, vp; 329 mpi_size_t wsize = LIMB_SIZE_448; 330 mpi_limb_t n[LIMB_SIZE_448]; 331 mpi_limb_t borrow; 332 333 if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) 334 log_bug("subm_448: different sizes\n"); 335 336 memset(n, 0, sizeof(n)); 337 up = u->d; 338 vp = v->d; 339 wp = w->d; 340 341 borrow = mpihelp_sub_n(wp, up, vp, wsize); 342 mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); 343 mpihelp_add_n(wp, wp, n, wsize); 344 } 345 346 static void ec_mulm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) 347 { 348 mpi_ptr_t wp, up, vp; 349 mpi_size_t wsize = LIMB_SIZE_448; 350 mpi_limb_t n[LIMB_SIZE_448*2]; 351 mpi_limb_t a2[LIMB_SIZE_HALF_448]; 352 mpi_limb_t a3[LIMB_SIZE_HALF_448]; 353 mpi_limb_t b0[LIMB_SIZE_HALF_448]; 354 mpi_limb_t b1[LIMB_SIZE_HALF_448]; 355 mpi_limb_t cy; 356 int i; 357 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) 358 mpi_limb_t b1_rest, a3_rest; 359 #endif 360 361 if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) 362 log_bug("mulm_448: different sizes\n"); 363 364 up = u->d; 365 vp = v->d; 366 wp = w->d; 367 368 mpihelp_mul_n(n, up, vp, wsize); 369 370 for (i = 0; i < (wsize + 1) / 2; i++) { 371 b0[i] = n[i]; 372 b1[i] = n[i+wsize/2]; 373 a2[i] = n[i+wsize]; 374 a3[i] = n[i+wsize+wsize/2]; 375 } 376 377 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) 378 b0[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1; 379 a2[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1; 380 381 b1_rest = 0; 382 a3_rest = 0; 383 384 for (i = (wsize + 1) / 2 - 1; i >= 0; i--) { 385 mpi_limb_t b1v, a3v; 386 b1v = b1[i]; 387 a3v = a3[i]; 388 b1[i] = (b1_rest << 32) | (b1v >> 32); 389 a3[i] = (a3_rest << 32) | (a3v >> 32); 390 b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1); 391 a3_rest = a3v & (((mpi_limb_t)1UL << 32)-1); 392 } 393 #endif 394 395 cy = mpihelp_add_n(b0, b0, a2, LIMB_SIZE_HALF_448); 396 cy += mpihelp_add_n(b0, b0, a3, LIMB_SIZE_HALF_448); 397 for (i = 0; i < (wsize + 1) / 2; i++) 398 wp[i] = b0[i]; 399 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) 400 wp[LIMB_SIZE_HALF_448-1] &= (((mpi_limb_t)1UL << 32)-1); 401 #endif 402 403 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) 404 cy = b0[LIMB_SIZE_HALF_448-1] >> 32; 405 #endif 406 407 cy = mpihelp_add_1(b1, b1, LIMB_SIZE_HALF_448, cy); 408 cy += mpihelp_add_n(b1, b1, a2, LIMB_SIZE_HALF_448); 409 cy += mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448); 410 cy += mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448); 411 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) 412 b1_rest = 0; 413 for (i = (wsize + 1) / 2 - 1; i >= 0; i--) { 414 mpi_limb_t b1v = b1[i]; 415 b1[i] = (b1_rest << 32) | (b1v >> 32); 416 b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1); 417 } 418 wp[LIMB_SIZE_HALF_448-1] |= (b1_rest << 32); 419 #endif 420 for (i = 0; i < wsize / 2; i++) 421 wp[i+(wsize + 1) / 2] = b1[i]; 422 423 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) 424 cy = b1[LIMB_SIZE_HALF_448-1]; 425 #endif 426 427 memset(n, 0, wsize * BYTES_PER_MPI_LIMB); 428 429 #if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) 430 n[LIMB_SIZE_HALF_448-1] = cy << 32; 431 #else 432 n[LIMB_SIZE_HALF_448] = cy; 433 #endif 434 n[0] = cy; 435 mpihelp_add_n(wp, wp, n, wsize); 436 437 memset(n, 0, wsize * BYTES_PER_MPI_LIMB); 438 cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); 439 mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL)); 440 mpihelp_add_n(wp, wp, n, wsize); 441 } 442 443 static void ec_mul2_448(MPI w, MPI u, struct mpi_ec_ctx *ctx) 444 { 445 ec_addm_448(w, u, u, ctx); 446 } 447 448 static void ec_pow2_448(MPI w, const MPI b, struct mpi_ec_ctx *ctx) 449 { 450 ec_mulm_448(w, b, b, ctx); 451 } 452 453 struct field_table { 454 const char *p; 455 456 /* computation routines for the field. */ 457 void (*addm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); 458 void (*subm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); 459 void (*mulm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); 460 void (*mul2)(MPI w, MPI u, struct mpi_ec_ctx *ctx); 461 void (*pow2)(MPI w, const MPI b, struct mpi_ec_ctx *ctx); 462 }; 463 464 static const struct field_table field_table[] = { 465 { 466 "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED", 467 ec_addm_25519, 468 ec_subm_25519, 469 ec_mulm_25519, 470 ec_mul2_25519, 471 ec_pow2_25519 472 }, 473 { 474 "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE" 475 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 476 ec_addm_448, 477 ec_subm_448, 478 ec_mulm_448, 479 ec_mul2_448, 480 ec_pow2_448 481 }, 482 { NULL, NULL, NULL, NULL, NULL, NULL }, 483 }; 484 485 /* Force recomputation of all helper variables. */ 486 static void mpi_ec_get_reset(struct mpi_ec_ctx *ec) 487 { 488 ec->t.valid.a_is_pminus3 = 0; 489 ec->t.valid.two_inv_p = 0; 490 } 491 492 /* Accessor for helper variable. */ 493 static int ec_get_a_is_pminus3(struct mpi_ec_ctx *ec) 494 { 495 MPI tmp; 496 497 if (!ec->t.valid.a_is_pminus3) { 498 ec->t.valid.a_is_pminus3 = 1; 499 tmp = mpi_alloc_like(ec->p); 500 mpi_sub_ui(tmp, ec->p, 3); 501 ec->t.a_is_pminus3 = !mpi_cmp(ec->a, tmp); 502 mpi_free(tmp); 503 } 504 505 return ec->t.a_is_pminus3; 506 } 507 508 /* Accessor for helper variable. */ 509 static MPI ec_get_two_inv_p(struct mpi_ec_ctx *ec) 510 { 511 if (!ec->t.valid.two_inv_p) { 512 ec->t.valid.two_inv_p = 1; 513 if (!ec->t.two_inv_p) 514 ec->t.two_inv_p = mpi_alloc(0); 515 ec_invm(ec->t.two_inv_p, mpi_const(MPI_C_TWO), ec); 516 } 517 return ec->t.two_inv_p; 518 } 519 520 static const char *const curve25519_bad_points[] = { 521 "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed", 522 "0x0000000000000000000000000000000000000000000000000000000000000000", 523 "0x0000000000000000000000000000000000000000000000000000000000000001", 524 "0x00b8495f16056286fdb1329ceb8d09da6ac49ff1fae35616aeb8413b7c7aebe0", 525 "0x57119fd0dd4e22d8868e1c58c45c44045bef839c55b1d0b1248c50a3bc959c5f", 526 "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec", 527 "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffee", 528 NULL 529 }; 530 531 static const char *const curve448_bad_points[] = { 532 "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe" 533 "ffffffffffffffffffffffffffffffffffffffffffffffffffffffff", 534 "0x00000000000000000000000000000000000000000000000000000000" 535 "00000000000000000000000000000000000000000000000000000000", 536 "0x00000000000000000000000000000000000000000000000000000000" 537 "00000000000000000000000000000000000000000000000000000001", 538 "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe" 539 "fffffffffffffffffffffffffffffffffffffffffffffffffffffffe", 540 "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffff" 541 "00000000000000000000000000000000000000000000000000000000", 542 NULL 543 }; 544 545 static const char *const *bad_points_table[] = { 546 curve25519_bad_points, 547 curve448_bad_points, 548 }; 549 550 static void mpi_ec_coefficient_normalize(MPI a, MPI p) 551 { 552 if (a->sign) { 553 mpi_resize(a, p->nlimbs); 554 mpihelp_sub_n(a->d, p->d, a->d, p->nlimbs); 555 a->nlimbs = p->nlimbs; 556 a->sign = 0; 557 } 558 } 559 560 /* This function initialized a context for elliptic curve based on the 561 * field GF(p). P is the prime specifying this field, A is the first 562 * coefficient. CTX is expected to be zeroized. 563 */ 564 void mpi_ec_init(struct mpi_ec_ctx *ctx, enum gcry_mpi_ec_models model, 565 enum ecc_dialects dialect, 566 int flags, MPI p, MPI a, MPI b) 567 { 568 int i; 569 static int use_barrett = -1 /* TODO: 1 or -1 */; 570 571 mpi_ec_coefficient_normalize(a, p); 572 mpi_ec_coefficient_normalize(b, p); 573 574 /* Fixme: Do we want to check some constraints? e.g. a < p */ 575 576 ctx->model = model; 577 ctx->dialect = dialect; 578 ctx->flags = flags; 579 if (dialect == ECC_DIALECT_ED25519) 580 ctx->nbits = 256; 581 else 582 ctx->nbits = mpi_get_nbits(p); 583 ctx->p = mpi_copy(p); 584 ctx->a = mpi_copy(a); 585 ctx->b = mpi_copy(b); 586 587 ctx->t.p_barrett = use_barrett > 0 ? mpi_barrett_init(ctx->p, 0) : NULL; 588 589 mpi_ec_get_reset(ctx); 590 591 if (model == MPI_EC_MONTGOMERY) { 592 for (i = 0; i < DIM(bad_points_table); i++) { 593 MPI p_candidate = mpi_scanval(bad_points_table[i][0]); 594 int match_p = !mpi_cmp(ctx->p, p_candidate); 595 int j; 596 597 mpi_free(p_candidate); 598 if (!match_p) 599 continue; 600 601 for (j = 0; i < DIM(ctx->t.scratch) && bad_points_table[i][j]; j++) 602 ctx->t.scratch[j] = mpi_scanval(bad_points_table[i][j]); 603 } 604 } else { 605 /* Allocate scratch variables. */ 606 for (i = 0; i < DIM(ctx->t.scratch); i++) 607 ctx->t.scratch[i] = mpi_alloc_like(ctx->p); 608 } 609 610 ctx->addm = ec_addm; 611 ctx->subm = ec_subm; 612 ctx->mulm = ec_mulm; 613 ctx->mul2 = ec_mul2; 614 ctx->pow2 = ec_pow2; 615 616 for (i = 0; field_table[i].p; i++) { 617 MPI f_p; 618 619 f_p = mpi_scanval(field_table[i].p); 620 if (!f_p) 621 break; 622 623 if (!mpi_cmp(p, f_p)) { 624 ctx->addm = field_table[i].addm; 625 ctx->subm = field_table[i].subm; 626 ctx->mulm = field_table[i].mulm; 627 ctx->mul2 = field_table[i].mul2; 628 ctx->pow2 = field_table[i].pow2; 629 mpi_free(f_p); 630 631 mpi_resize(ctx->a, ctx->p->nlimbs); 632 ctx->a->nlimbs = ctx->p->nlimbs; 633 634 mpi_resize(ctx->b, ctx->p->nlimbs); 635 ctx->b->nlimbs = ctx->p->nlimbs; 636 637 for (i = 0; i < DIM(ctx->t.scratch) && ctx->t.scratch[i]; i++) 638 ctx->t.scratch[i]->nlimbs = ctx->p->nlimbs; 639 640 break; 641 } 642 643 mpi_free(f_p); 644 } 645 } 646 EXPORT_SYMBOL_GPL(mpi_ec_init); 647 648 void mpi_ec_deinit(struct mpi_ec_ctx *ctx) 649 { 650 int i; 651 652 mpi_barrett_free(ctx->t.p_barrett); 653 654 /* Domain parameter. */ 655 mpi_free(ctx->p); 656 mpi_free(ctx->a); 657 mpi_free(ctx->b); 658 mpi_point_release(ctx->G); 659 mpi_free(ctx->n); 660 661 /* The key. */ 662 mpi_point_release(ctx->Q); 663 mpi_free(ctx->d); 664 665 /* Private data of ec.c. */ 666 mpi_free(ctx->t.two_inv_p); 667 668 for (i = 0; i < DIM(ctx->t.scratch); i++) 669 mpi_free(ctx->t.scratch[i]); 670 } 671 EXPORT_SYMBOL_GPL(mpi_ec_deinit); 672 673 /* Compute the affine coordinates from the projective coordinates in 674 * POINT. Set them into X and Y. If one coordinate is not required, 675 * X or Y may be passed as NULL. CTX is the usual context. Returns: 0 676 * on success or !0 if POINT is at infinity. 677 */ 678 int mpi_ec_get_affine(MPI x, MPI y, MPI_POINT point, struct mpi_ec_ctx *ctx) 679 { 680 if (!mpi_cmp_ui(point->z, 0)) 681 return -1; 682 683 switch (ctx->model) { 684 case MPI_EC_WEIERSTRASS: /* Using Jacobian coordinates. */ 685 { 686 MPI z1, z2, z3; 687 688 z1 = mpi_new(0); 689 z2 = mpi_new(0); 690 ec_invm(z1, point->z, ctx); /* z1 = z^(-1) mod p */ 691 ec_mulm(z2, z1, z1, ctx); /* z2 = z^(-2) mod p */ 692 693 if (x) 694 ec_mulm(x, point->x, z2, ctx); 695 696 if (y) { 697 z3 = mpi_new(0); 698 ec_mulm(z3, z2, z1, ctx); /* z3 = z^(-3) mod p */ 699 ec_mulm(y, point->y, z3, ctx); 700 mpi_free(z3); 701 } 702 703 mpi_free(z2); 704 mpi_free(z1); 705 } 706 return 0; 707 708 case MPI_EC_MONTGOMERY: 709 { 710 if (x) 711 mpi_set(x, point->x); 712 713 if (y) { 714 log_fatal("%s: Getting Y-coordinate on %s is not supported\n", 715 "mpi_ec_get_affine", "Montgomery"); 716 return -1; 717 } 718 } 719 return 0; 720 721 case MPI_EC_EDWARDS: 722 { 723 MPI z; 724 725 z = mpi_new(0); 726 ec_invm(z, point->z, ctx); 727 728 mpi_resize(z, ctx->p->nlimbs); 729 z->nlimbs = ctx->p->nlimbs; 730 731 if (x) { 732 mpi_resize(x, ctx->p->nlimbs); 733 x->nlimbs = ctx->p->nlimbs; 734 ctx->mulm(x, point->x, z, ctx); 735 } 736 if (y) { 737 mpi_resize(y, ctx->p->nlimbs); 738 y->nlimbs = ctx->p->nlimbs; 739 ctx->mulm(y, point->y, z, ctx); 740 } 741 742 mpi_free(z); 743 } 744 return 0; 745 746 default: 747 return -1; 748 } 749 } 750 EXPORT_SYMBOL_GPL(mpi_ec_get_affine); 751 752 /* RESULT = 2 * POINT (Weierstrass version). */ 753 static void dup_point_weierstrass(MPI_POINT result, 754 MPI_POINT point, struct mpi_ec_ctx *ctx) 755 { 756 #define x3 (result->x) 757 #define y3 (result->y) 758 #define z3 (result->z) 759 #define t1 (ctx->t.scratch[0]) 760 #define t2 (ctx->t.scratch[1]) 761 #define t3 (ctx->t.scratch[2]) 762 #define l1 (ctx->t.scratch[3]) 763 #define l2 (ctx->t.scratch[4]) 764 #define l3 (ctx->t.scratch[5]) 765 766 if (!mpi_cmp_ui(point->y, 0) || !mpi_cmp_ui(point->z, 0)) { 767 /* P_y == 0 || P_z == 0 => [1:1:0] */ 768 mpi_set_ui(x3, 1); 769 mpi_set_ui(y3, 1); 770 mpi_set_ui(z3, 0); 771 } else { 772 if (ec_get_a_is_pminus3(ctx)) { 773 /* Use the faster case. */ 774 /* L1 = 3(X - Z^2)(X + Z^2) */ 775 /* T1: used for Z^2. */ 776 /* T2: used for the right term. */ 777 ec_pow2(t1, point->z, ctx); 778 ec_subm(l1, point->x, t1, ctx); 779 ec_mulm(l1, l1, mpi_const(MPI_C_THREE), ctx); 780 ec_addm(t2, point->x, t1, ctx); 781 ec_mulm(l1, l1, t2, ctx); 782 } else { 783 /* Standard case. */ 784 /* L1 = 3X^2 + aZ^4 */ 785 /* T1: used for aZ^4. */ 786 ec_pow2(l1, point->x, ctx); 787 ec_mulm(l1, l1, mpi_const(MPI_C_THREE), ctx); 788 ec_powm(t1, point->z, mpi_const(MPI_C_FOUR), ctx); 789 ec_mulm(t1, t1, ctx->a, ctx); 790 ec_addm(l1, l1, t1, ctx); 791 } 792 /* Z3 = 2YZ */ 793 ec_mulm(z3, point->y, point->z, ctx); 794 ec_mul2(z3, z3, ctx); 795 796 /* L2 = 4XY^2 */ 797 /* T2: used for Y2; required later. */ 798 ec_pow2(t2, point->y, ctx); 799 ec_mulm(l2, t2, point->x, ctx); 800 ec_mulm(l2, l2, mpi_const(MPI_C_FOUR), ctx); 801 802 /* X3 = L1^2 - 2L2 */ 803 /* T1: used for L2^2. */ 804 ec_pow2(x3, l1, ctx); 805 ec_mul2(t1, l2, ctx); 806 ec_subm(x3, x3, t1, ctx); 807 808 /* L3 = 8Y^4 */ 809 /* T2: taken from above. */ 810 ec_pow2(t2, t2, ctx); 811 ec_mulm(l3, t2, mpi_const(MPI_C_EIGHT), ctx); 812 813 /* Y3 = L1(L2 - X3) - L3 */ 814 ec_subm(y3, l2, x3, ctx); 815 ec_mulm(y3, y3, l1, ctx); 816 ec_subm(y3, y3, l3, ctx); 817 } 818 819 #undef x3 820 #undef y3 821 #undef z3 822 #undef t1 823 #undef t2 824 #undef t3 825 #undef l1 826 #undef l2 827 #undef l3 828 } 829 830 /* RESULT = 2 * POINT (Montgomery version). */ 831 static void dup_point_montgomery(MPI_POINT result, 832 MPI_POINT point, struct mpi_ec_ctx *ctx) 833 { 834 (void)result; 835 (void)point; 836 (void)ctx; 837 log_fatal("%s: %s not yet supported\n", 838 "mpi_ec_dup_point", "Montgomery"); 839 } 840 841 /* RESULT = 2 * POINT (Twisted Edwards version). */ 842 static void dup_point_edwards(MPI_POINT result, 843 MPI_POINT point, struct mpi_ec_ctx *ctx) 844 { 845 #define X1 (point->x) 846 #define Y1 (point->y) 847 #define Z1 (point->z) 848 #define X3 (result->x) 849 #define Y3 (result->y) 850 #define Z3 (result->z) 851 #define B (ctx->t.scratch[0]) 852 #define C (ctx->t.scratch[1]) 853 #define D (ctx->t.scratch[2]) 854 #define E (ctx->t.scratch[3]) 855 #define F (ctx->t.scratch[4]) 856 #define H (ctx->t.scratch[5]) 857 #define J (ctx->t.scratch[6]) 858 859 /* Compute: (X_3 : Y_3 : Z_3) = 2( X_1 : Y_1 : Z_1 ) */ 860 861 /* B = (X_1 + Y_1)^2 */ 862 ctx->addm(B, X1, Y1, ctx); 863 ctx->pow2(B, B, ctx); 864 865 /* C = X_1^2 */ 866 /* D = Y_1^2 */ 867 ctx->pow2(C, X1, ctx); 868 ctx->pow2(D, Y1, ctx); 869 870 /* E = aC */ 871 if (ctx->dialect == ECC_DIALECT_ED25519) 872 ctx->subm(E, ctx->p, C, ctx); 873 else 874 ctx->mulm(E, ctx->a, C, ctx); 875 876 /* F = E + D */ 877 ctx->addm(F, E, D, ctx); 878 879 /* H = Z_1^2 */ 880 ctx->pow2(H, Z1, ctx); 881 882 /* J = F - 2H */ 883 ctx->mul2(J, H, ctx); 884 ctx->subm(J, F, J, ctx); 885 886 /* X_3 = (B - C - D) · J */ 887 ctx->subm(X3, B, C, ctx); 888 ctx->subm(X3, X3, D, ctx); 889 ctx->mulm(X3, X3, J, ctx); 890 891 /* Y_3 = F · (E - D) */ 892 ctx->subm(Y3, E, D, ctx); 893 ctx->mulm(Y3, Y3, F, ctx); 894 895 /* Z_3 = F · J */ 896 ctx->mulm(Z3, F, J, ctx); 897 898 #undef X1 899 #undef Y1 900 #undef Z1 901 #undef X3 902 #undef Y3 903 #undef Z3 904 #undef B 905 #undef C 906 #undef D 907 #undef E 908 #undef F 909 #undef H 910 #undef J 911 } 912 913 /* RESULT = 2 * POINT */ 914 static void 915 mpi_ec_dup_point(MPI_POINT result, MPI_POINT point, struct mpi_ec_ctx *ctx) 916 { 917 switch (ctx->model) { 918 case MPI_EC_WEIERSTRASS: 919 dup_point_weierstrass(result, point, ctx); 920 break; 921 case MPI_EC_MONTGOMERY: 922 dup_point_montgomery(result, point, ctx); 923 break; 924 case MPI_EC_EDWARDS: 925 dup_point_edwards(result, point, ctx); 926 break; 927 } 928 } 929 930 /* RESULT = P1 + P2 (Weierstrass version).*/ 931 static void add_points_weierstrass(MPI_POINT result, 932 MPI_POINT p1, MPI_POINT p2, 933 struct mpi_ec_ctx *ctx) 934 { 935 #define x1 (p1->x) 936 #define y1 (p1->y) 937 #define z1 (p1->z) 938 #define x2 (p2->x) 939 #define y2 (p2->y) 940 #define z2 (p2->z) 941 #define x3 (result->x) 942 #define y3 (result->y) 943 #define z3 (result->z) 944 #define l1 (ctx->t.scratch[0]) 945 #define l2 (ctx->t.scratch[1]) 946 #define l3 (ctx->t.scratch[2]) 947 #define l4 (ctx->t.scratch[3]) 948 #define l5 (ctx->t.scratch[4]) 949 #define l6 (ctx->t.scratch[5]) 950 #define l7 (ctx->t.scratch[6]) 951 #define l8 (ctx->t.scratch[7]) 952 #define l9 (ctx->t.scratch[8]) 953 #define t1 (ctx->t.scratch[9]) 954 #define t2 (ctx->t.scratch[10]) 955 956 if ((!mpi_cmp(x1, x2)) && (!mpi_cmp(y1, y2)) && (!mpi_cmp(z1, z2))) { 957 /* Same point; need to call the duplicate function. */ 958 mpi_ec_dup_point(result, p1, ctx); 959 } else if (!mpi_cmp_ui(z1, 0)) { 960 /* P1 is at infinity. */ 961 mpi_set(x3, p2->x); 962 mpi_set(y3, p2->y); 963 mpi_set(z3, p2->z); 964 } else if (!mpi_cmp_ui(z2, 0)) { 965 /* P2 is at infinity. */ 966 mpi_set(x3, p1->x); 967 mpi_set(y3, p1->y); 968 mpi_set(z3, p1->z); 969 } else { 970 int z1_is_one = !mpi_cmp_ui(z1, 1); 971 int z2_is_one = !mpi_cmp_ui(z2, 1); 972 973 /* l1 = x1 z2^2 */ 974 /* l2 = x2 z1^2 */ 975 if (z2_is_one) 976 mpi_set(l1, x1); 977 else { 978 ec_pow2(l1, z2, ctx); 979 ec_mulm(l1, l1, x1, ctx); 980 } 981 if (z1_is_one) 982 mpi_set(l2, x2); 983 else { 984 ec_pow2(l2, z1, ctx); 985 ec_mulm(l2, l2, x2, ctx); 986 } 987 /* l3 = l1 - l2 */ 988 ec_subm(l3, l1, l2, ctx); 989 /* l4 = y1 z2^3 */ 990 ec_powm(l4, z2, mpi_const(MPI_C_THREE), ctx); 991 ec_mulm(l4, l4, y1, ctx); 992 /* l5 = y2 z1^3 */ 993 ec_powm(l5, z1, mpi_const(MPI_C_THREE), ctx); 994 ec_mulm(l5, l5, y2, ctx); 995 /* l6 = l4 - l5 */ 996 ec_subm(l6, l4, l5, ctx); 997 998 if (!mpi_cmp_ui(l3, 0)) { 999 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); 1507