aff_pt_montgomery.c
1 /* 2 * Copyright (C) 2021 - This file is part of libecc project 3 * 4 * Authors: 5 * Ryad BENADJILA <ryadbenadjila@gmail.com> 6 * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr> 7 * 8 * This software is licensed under a dual BSD and GPL v2 license. 9 * See LICENSE file at the root folder of the project. 10 */ 11 #include <libecc/curves/aff_pt.h> 12 13 #define AFF_PT_MONTGOMERY_MAGIC ((word_t)(0x7390a9bc43d94598ULL)) 14 15 /* Verify that an affine point has already been initialized. 16 * 17 * Returns 0 on success, -1 on error. 18 */ 19 int aff_pt_montgomery_check_initialized(aff_pt_montgomery_src_t in) 20 { 21 int ret; 22 23 MUST_HAVE(((in != NULL) && (in->magic == AFF_PT_MONTGOMERY_MAGIC)), ret, err); 24 ret = ec_montgomery_crv_check_initialized(in->crv); 25 26 err: 27 return ret; 28 } 29 30 /* 31 * Initialize pointed aff_pt_montgomery structure to make it usable by library 32 * function on given curve. 33 * 34 * Returns 0 on success, -1 on error. 35 */ 36 int aff_pt_montgomery_init(aff_pt_montgomery_t in, ec_montgomery_crv_src_t curve) 37 { 38 int ret; 39 40 MUST_HAVE((in != NULL), ret, err); 41 ret = ec_montgomery_crv_check_initialized(curve); EG(ret, err); 42 43 ret = fp_init(&(in->u), curve->A.ctx); EG(ret, err); 44 ret = fp_init(&(in->v), curve->A.ctx); EG(ret, err); 45 46 in->crv = curve; 47 in->magic = AFF_PT_MONTGOMERY_MAGIC; 48 49 err: 50 return ret; 51 } 52 53 /* 54 * Initialize pointed aff_pt_montgomery structure to make it usable by library 55 * function on given curve with explicit coordinates. 56 * 57 * Returns 0 on success, -1 on error. 58 */ 59 int aff_pt_montgomery_init_from_coords(aff_pt_montgomery_t in, 60 ec_montgomery_crv_src_t curve, 61 fp_src_t ucoord, fp_src_t vcoord) 62 { 63 int ret; 64 65 ret = aff_pt_montgomery_init(in, curve); EG(ret, err); 66 ret = fp_copy(&(in->u), ucoord); EG(ret, err); 67 ret = fp_copy(&(in->v), vcoord); 68 69 err: 70 return ret; 71 } 72 73 /* 74 * Uninitialize pointed affine point to prevent further use (magic field 75 * in the structure is zeroized) and zeroize associated storage space. 76 * Note that the curve context pointed to by the point element (passed 77 * during init) is left untouched. 78 * 79 */ 80 void aff_pt_montgomery_uninit(aff_pt_montgomery_t in) 81 { 82 if ((in != NULL) && (in->magic == AFF_PT_MONTGOMERY_MAGIC) && (in->crv != NULL)) { 83 fp_uninit(&(in->u)); 84 fp_uninit(&(in->v)); 85 86 in->crv = NULL; 87 in->magic = WORD(0); 88 } 89 90 return; 91 } 92 93 /* 94 * 'on_curve' set to 1 if the point of coordinates (u,v) is on the curve, i.e. if it 95 * verifies curve equation B*v^2 = u^3 + A*u^2 + u. It is set to 0 otherwise. 96 * 'on_curve' is not meaningful on error. 97 * 98 * Returns 0 on success, -1 on error. 99 */ 100 int is_on_montgomery_curve(fp_src_t u, fp_src_t v, ec_montgomery_crv_src_t curve, int *on_curve) 101 { 102 fp Bv2, u3, Au2, tmp; 103 int ret, cmp; 104 Bv2.magic = u3.magic = Au2.magic = tmp.magic = WORD(0); 105 106 MUST_HAVE((on_curve != NULL), ret, err); 107 ret = ec_montgomery_crv_check_initialized(curve); EG(ret, err); 108 109 ret = fp_check_initialized(u); EG(ret, err); 110 ret = fp_check_initialized(v); EG(ret, err); 111 112 MUST_HAVE((u->ctx == v->ctx), ret, err); 113 MUST_HAVE((u->ctx == curve->A.ctx), ret, err); 114 115 ret = fp_init(&Bv2, v->ctx); EG(ret, err); 116 ret = fp_sqr(&Bv2, v); EG(ret, err); 117 ret = fp_mul(&Bv2, &(curve->B), &Bv2); EG(ret, err); 118 119 ret = fp_init(&Au2, u->ctx); EG(ret, err); 120 ret = fp_sqr(&Au2, u); EG(ret, err); 121 ret = fp_copy(&u3, &Au2); EG(ret, err); 122 ret = fp_mul(&Au2, &(curve->A), &Au2); EG(ret, err); 123 124 ret = fp_mul(&u3, &u3, u); EG(ret, err); 125 126 ret = fp_init(&tmp, u->ctx); EG(ret, err); 127 ret = fp_add(&tmp, &u3, &Au2); EG(ret, err); 128 ret = fp_add(&tmp, &tmp, u); EG(ret, err); 129 130 ret = fp_cmp(&tmp, &Bv2, &cmp); EG(ret, err); 131 132 (*on_curve) = (!cmp); 133 134 err: 135 fp_uninit(&Bv2); 136 fp_uninit(&u3); 137 fp_uninit(&Au2); 138 fp_uninit(&tmp); 139 140 return ret; 141 } 142 143 /* Checks if affine coordinates point is on a Montgomery curve. 'on_curve' is set to 1 if yes, 144 * 0 if no. 'on_curve' is not meaningful in case of error. 145 * 146 * Returns 0 on success, -1 on error. 147 */ 148 int aff_pt_montgomery_is_on_curve(aff_pt_montgomery_src_t pt, int *on_curve) 149 { 150 int ret; 151 152 ret = aff_pt_montgomery_check_initialized(pt); EG(ret, err); 153 154 ret = is_on_montgomery_curve(&(pt->u), &(pt->v), pt->crv, on_curve); 155 156 err: 157 return ret; 158 } 159 160 /* Copy a Montgomery affine point in an output. The output is initialized properly. 161 * 162 * Returns 0 on success, -1 on error. 163 */ 164 int ec_montgomery_aff_copy(aff_pt_montgomery_t out, aff_pt_montgomery_src_t in) 165 { 166 int ret; 167 168 ret = aff_pt_montgomery_check_initialized(in); EG(ret, err); 169 170 ret = aff_pt_montgomery_init(out, in->crv); EG(ret, err); 171 ret = fp_copy(&(out->u), &(in->u)); EG(ret, err); 172 ret = fp_copy(&(out->v), &(in->v)); 173 174 err: 175 return ret; 176 } 177 178 /* 179 * Compares two given affine points on a Montgomery curve, it returns 0 in input 'cmp' if 180 * they correspond or not 0 if not. 'cmp' is not meaningful on error. 181 * 182 * Returns 0 on success, -1 on error. 183 */ 184 int ec_montgomery_aff_cmp(aff_pt_montgomery_src_t in1, aff_pt_montgomery_src_t in2, int *cmp) 185 { 186 int ret, cmp1, cmp2; 187 188 MUST_HAVE((cmp != NULL), ret, err); 189 ret = aff_pt_montgomery_check_initialized(in1); EG(ret, err); 190 ret = aff_pt_montgomery_check_initialized(in2); EG(ret, err); 191 MUST_HAVE((in1->crv == in2->crv), ret, err); 192 193 ret = fp_cmp(&(in1->u), &(in2->u), &cmp1); EG(ret, err); 194 ret = fp_cmp(&(in1->v), &(in2->v), &cmp2); EG(ret, err); 195 196 (*cmp) = (cmp1 | cmp2); 197 198 err: 199 return ret; 200 } 201 202 /* 203 * Import an Montgomery affine point from a buffer with the following layout; the 2 204 * coordinates (elements of Fp) are each encoded on p_len bytes, where p_len 205 * is the size of p in bytes (e.g. 66 for a prime p of 521 bits). Each 206 * coordinate is encoded in big endian. Size of buffer must exactly match 207 * 2 * p_len. 208 * 209 * Returns 0 on success, -1 on error. 210 */ 211 int aff_pt_montgomery_import_from_buf(aff_pt_montgomery_t pt, 212 const u8 *pt_buf, 213 u16 pt_buf_len, ec_montgomery_crv_src_t crv) 214 { 215 fp_ctx_src_t ctx; 216 u16 coord_len; 217 int ret, on_curve; 218 219 ret = ec_montgomery_crv_check_initialized(crv); EG(ret, err); 220 MUST_HAVE((pt_buf != NULL) && (pt != NULL), ret, err); 221 222 ctx = crv->A.ctx; 223 coord_len = (u16)BYTECEIL(ctx->p_bitlen); 224 225 MUST_HAVE((pt_buf_len == (2 * coord_len)), ret, err); 226 227 ret = fp_init_from_buf(&(pt->u), ctx, pt_buf, coord_len); EG(ret, err); 228 ret = fp_init_from_buf(&(pt->v), ctx, pt_buf + coord_len, coord_len); EG(ret, err); 229 230 /* Set the curve */ 231 pt->crv = crv; 232 233 /* Mark the point as initialized */ 234 pt->magic = AFF_PT_MONTGOMERY_MAGIC; 235 236 /* Check that the point is indeed on the provided curve, uninitialize it 237 * if this is not the case. 238 */ 239 ret = aff_pt_montgomery_is_on_curve(pt, &on_curve); EG(ret, err); 240 if (!on_curve) { 241 aff_pt_montgomery_uninit(pt); 242 ret = -1; 243 } 244 245 err: 246 return ret; 247 } 248 249 250 /* Export an Montgomery affine point to a buffer with the following layout; the 2 251 * coordinates (elements of Fp) are each encoded on p_len bytes, where p_len 252 * is the size of p in bytes (e.g. 66 for a prime p of 521 bits). Each 253 * coordinate is encoded in big endian. Size of buffer must exactly match 254 * 2 * p_len. 255 * 256 * Returns 0 on success, -1 on error. 257 */ 258 int aff_pt_montgomery_export_to_buf(aff_pt_montgomery_src_t pt, u8 *pt_buf, u32 pt_buf_len) 259 { 260 fp_ctx_src_t ctx; 261 u16 coord_len; 262 int ret, on_curve; 263 264 ret = aff_pt_montgomery_check_initialized(pt); EG(ret, err); 265 MUST_HAVE((pt_buf != NULL), ret, err); 266 267 /* The point to be exported must be on the curve */ 268 ret = aff_pt_montgomery_is_on_curve(pt, &on_curve); EG(ret, err); 269 MUST_HAVE(on_curve, ret, err); 270 271 ctx = pt->crv->A.ctx; 272 coord_len = (u16)BYTECEIL(ctx->p_bitlen); 273 274 MUST_HAVE((pt_buf_len == (2 * coord_len)), ret, err); 275 276 /* Export the three coordinates */ 277 ret = fp_export_to_buf(pt_buf, coord_len, &(pt->u)); EG(ret, err); 278 ret = fp_export_to_buf(pt_buf + coord_len, coord_len, &(pt->v)); 279 280 err: 281 return ret; 282 } 283 284 /**** Mappings between curves *************/ 285 /* 286 * Mapping curves from Montgomery to short Weiertstrass. 287 * 288 * M{A, B} is mapped to W{a, b} using the formula: 289 * a = (3-A^2)/(3*B^2) 290 * b = (2*A^3-9*A)/(27*B^3) 291 * 292 * Returns 0 on success, -1 on error. 293 */ 294 int curve_montgomery_to_shortw(ec_montgomery_crv_src_t montgomery_crv, ec_shortw_crv_t shortw_crv) 295 { 296 fp tmp, tmp2, a, b; 297 int ret; 298 tmp.magic = tmp2.magic = a.magic = b.magic = WORD(0); 299 300 ret = ec_montgomery_crv_check_initialized(montgomery_crv); EG(ret, err); 301 302 ret = fp_init(&tmp, montgomery_crv->A.ctx); EG(ret, err); 303 ret = fp_init(&tmp2, montgomery_crv->A.ctx); EG(ret, err); 304 ret = fp_init(&a, montgomery_crv->A.ctx); EG(ret, err); 305 ret = fp_init(&b, montgomery_crv->A.ctx); EG(ret, err); 306 307 /* Compute a */ 308 ret = fp_sqr(&tmp, &(montgomery_crv->B)); EG(ret, err); 309 ret = fp_set_word_value(&tmp2, WORD(3)); EG(ret, err); 310 /* 3*B^2 */ 311 ret = fp_mul(&tmp, &tmp, &tmp2); EG(ret, err); 312 /* (3*B^2)^-1 */ 313 ret = fp_inv(&tmp, &tmp); EG(ret, err); 314 315 /* (3-A^2) */ 316 ret = fp_sqr(&tmp2, &(montgomery_crv->A)); EG(ret, err); 317 ret = fp_set_word_value(&a, WORD(3)); EG(ret, err); 318 ret = fp_sub(&tmp2, &a, &tmp2); EG(ret, err); 319 320 ret = fp_mul(&a, &tmp2, &tmp); EG(ret, err); 321 322 /* Compute b */ 323 ret = fp_sqr(&tmp, &(montgomery_crv->B)); EG(ret, err); 324 ret = fp_mul(&tmp, &tmp, &(montgomery_crv->B)); EG(ret, err); 325 ret = fp_set_word_value(&tmp2, WORD(27)); EG(ret, err); 326 /* (27*B^3) */ 327 ret = fp_mul(&tmp, &tmp, &tmp2); EG(ret, err); 328 /* (27*B^3)^-1 */ 329 ret = fp_inv(&tmp, &tmp); EG(ret, err); 330 331 /* (2*A^3-9*A) */ 332 ret = fp_set_word_value(&tmp2, WORD(2)); EG(ret, err); 333 ret = fp_mul(&tmp2, &tmp2, &(montgomery_crv->A)); EG(ret, err); 334 ret = fp_mul(&tmp2, &tmp2, &(montgomery_crv->A)); EG(ret, err); 335 ret = fp_mul(&tmp2, &tmp2, &(montgomery_crv->A)); EG(ret, err); 336 337 ret = fp_set_word_value(&b, WORD(9)); EG(ret, err); 338 ret = fp_mul(&b, &b, &(montgomery_crv->A)); EG(ret, err); 339 ret = fp_sub(&b, &tmp2, &b); EG(ret, err); 340 341 ret = fp_mul(&b, &b, &tmp); EG(ret, err); 342 343 /* Initialize our short Weiertstrass curve */ 344 ret = ec_shortw_crv_init(shortw_crv, &a, &b, &(montgomery_crv->order)); 345 346 err: 347 fp_uninit(&a); 348 fp_uninit(&b); 349 fp_uninit(&tmp); 350 fp_uninit(&tmp2); 351 352 return ret; 353 } 354 355 /* 356 * Checks that a short Weiertstrass curve and Montgomery curve are compatible. 357 * 358 * Returns 0 on success, -1 on error. 359 */ 360 int curve_montgomery_shortw_check(ec_montgomery_crv_src_t montgomery_crv, 361 ec_shortw_crv_src_t shortw_crv) 362 { 363 int ret, cmp; 364 ec_shortw_crv check; 365 check.magic = WORD(0); 366 367 ret = ec_shortw_crv_check_initialized(shortw_crv); EG(ret, err); 368 ret = curve_montgomery_to_shortw(montgomery_crv, &check); EG(ret, err); 369 370 /* Check elements */ 371 MUST_HAVE((!fp_cmp(&(check.a), &(shortw_crv->a), &cmp)) && (!cmp), ret, err); 372 MUST_HAVE((!fp_cmp(&(check.b), &(shortw_crv->b), &cmp)) && (!cmp), ret, err); 373 MUST_HAVE((!nn_cmp(&(check.order), &(shortw_crv->order), &cmp)) && (!cmp), ret, err); 374 375 err: 376 ec_shortw_crv_uninit(&check); 377 378 return ret; 379 } 380 381 /* 382 * Mapping curves from short Weiertstrass to Montgomery 383 * 384 * W{a, b} is mapped to M{A, B} using the formula: 385 * A = 3 * alpha / gamma 386 * B = 1 / gamma 387 * with gamma square root of c = a + 3 * alpha**2 388 * 389 * Returns 0 on success, -1 on error. 390 */ 391 int curve_shortw_to_montgomery(ec_shortw_crv_src_t shortw_crv, 392 ec_montgomery_crv_t montgomery_crv, 393 fp_src_t alpha, fp_src_t gamma) 394 { 395 int ret, cmp; 396 fp c, gamma_inv, A, tmp; 397 c.magic = gamma_inv.magic = A.magic = tmp.magic = WORD(0); 398 399 ret = ec_shortw_crv_check_initialized(shortw_crv); EG(ret, err); 400 ret = fp_check_initialized(alpha); EG(ret, err); 401 ret = fp_check_initialized(gamma); EG(ret, err); 402 MUST_HAVE((alpha->ctx == shortw_crv->a.ctx) && (gamma->ctx == shortw_crv->a.ctx), ret, err); 403 404 ret = fp_init(&A, shortw_crv->a.ctx); EG(ret, err); 405 ret = fp_init(&gamma_inv, shortw_crv->a.ctx); EG(ret, err); 406 ret = fp_init(&c, shortw_crv->a.ctx); EG(ret, err); 407 ret = fp_init(&tmp, shortw_crv->a.ctx); EG(ret, err); 408 409 /* Compute 1 / gamma */ 410 ret = fp_inv(&gamma_inv, gamma); EG(ret, err); 411 412 /* Compute A */ 413 ret = fp_set_word_value(&A, WORD(3)); EG(ret, err); 414 ret = fp_mul(&A, &A, alpha); EG(ret, err); 415 ret = fp_mul(&A, &A, &gamma_inv); EG(ret, err); 416 417 /* Sanity check on c */ 418 ret = fp_set_word_value(&c, WORD(3)); EG(ret, err); 419 ret = fp_mul(&c, &c, alpha); EG(ret, err); 420 ret = fp_mul(&c, &c, alpha); EG(ret, err); 421 ret = fp_add(&c, &c, &(shortw_crv->a)); EG(ret, err); 422 ret = fp_sqr(&tmp, gamma); EG(ret, err); 423 /* gamma ** 2 must be equal to c */ 424 MUST_HAVE((!fp_cmp(&c, &tmp, &cmp)) && (!cmp), ret, err); 425 426 /* B is simply the inverse of gamma */ 427 ret = ec_montgomery_crv_init(montgomery_crv, &A, &gamma_inv, &(shortw_crv->order)); 428 429 err: 430 fp_uninit(&A); 431 fp_uninit(&gamma_inv); 432 fp_uninit(&c); 433 fp_uninit(&tmp); 434 435 return ret; 436 } 437 438 /* 439 * Mapping points from Montgomery to short Weierstrass. 440 * Point M(u, v) is mapped to W(x, y) with the formula: 441 * - (x, y) = ((u/B)+(A/3B), v/B) 442 * 443 * Returns 0 on success, -1 on error. 444 */ 445 int aff_pt_montgomery_to_shortw(aff_pt_montgomery_src_t in_montgomery, 446 ec_shortw_crv_src_t shortw_crv, aff_pt_t out_shortw) 447 { 448 int ret, on_curve; 449 fp tmp, tmp2; 450 tmp.magic = tmp2.magic = WORD(0); 451 452 ret = ec_shortw_crv_check_initialized(shortw_crv); EG(ret, err); 453 454 /* Check that our input point is on its curve */ 455 MUST_HAVE((!aff_pt_montgomery_is_on_curve(in_montgomery, &on_curve)) && on_curve, ret, err); 456 457 ret = fp_init(&tmp, in_montgomery->crv->A.ctx); EG(ret, err); 458 ret = fp_init(&tmp2, in_montgomery->crv->A.ctx); EG(ret, err); 459 460 ret = aff_pt_montgomery_check_initialized(in_montgomery); EG(ret, err); 461 ret = curve_montgomery_shortw_check(in_montgomery->crv, shortw_crv); EG(ret, err); 462 463 ret = aff_pt_init(out_shortw, shortw_crv); EG(ret, err); 464 465 ret = fp_inv(&tmp, &(in_montgomery->crv->B)); EG(ret, err); 466 ret = fp_mul(&tmp, &tmp, &(in_montgomery->u)); EG(ret, err); 467 468 ret = fp_set_word_value(&tmp2, WORD(3)); EG(ret, err); 469 ret = fp_mul(&tmp2, &tmp2, &(in_montgomery->crv->B)); EG(ret, err); 470 ret = fp_inv(&tmp2, &tmp2); EG(ret, err); 471 ret = fp_mul(&tmp2, &tmp2, &(in_montgomery->crv->A)); EG(ret, err); 472 473 ret = fp_add(&(out_shortw->x), &tmp, &tmp2); EG(ret, err); 474 475 ret = fp_inv(&tmp, &(in_montgomery->crv->B)); EG(ret, err); 476 ret = fp_mul(&(out_shortw->y), &tmp, &(in_montgomery->v)); EG(ret, err); 477 478 /* Final check that the point is on the curve */ 479 MUST_HAVE((!aff_pt_is_on_curve(out_shortw, &on_curve)) && on_curve, ret, err); 480 481 err: 482 fp_uninit(&tmp); 483 fp_uninit(&tmp2); 484 485 return ret; 486 } 487 488 /* 489 * Mapping from short Weierstrass to Montgomery. 490 * Point W(x, y) is mapped to M(u, v) with the formula: 491 * - (u, v) = (((Bx)−(A/3), By) 492 * 493 * Returns 0 on success, -1 on error. 494 */ 495 int aff_pt_shortw_to_montgomery(aff_pt_src_t in_shortw, 496 ec_montgomery_crv_src_t montgomery_crv, 497 aff_pt_montgomery_t out_montgomery) 498 { 499 int ret, on_curve; 500 fp tmp, tmp2; 501 tmp.magic = tmp2.magic = WORD(0); 502 503 ret = ec_montgomery_crv_check_initialized(montgomery_crv); EG(ret, err); 504 505 /* Check that our input point is on its curve */ 506 MUST_HAVE((!aff_pt_is_on_curve(in_shortw, &on_curve)) && on_curve, ret, err); 507 508 ret = fp_init(&tmp, in_shortw->crv->a.ctx); EG(ret, err); 509 ret = fp_init(&tmp2, in_shortw->crv->a.ctx); EG(ret, err); 510 511 ret = curve_montgomery_shortw_check(montgomery_crv, in_shortw->crv); EG(ret, err); 512 513 ret = aff_pt_montgomery_init(out_montgomery, montgomery_crv); EG(ret, err); 514 515 /* A/3 */ 516 ret = fp_inv_word(&tmp, WORD(3)); EG(ret, err); 517 ret = fp_mul(&tmp, &tmp, &(montgomery_crv->A)); EG(ret, err); 518 519 /* Bx */ 520 ret = fp_mul(&tmp2, &(montgomery_crv->B), &(in_shortw->x)); EG(ret, err); 521 522 /* u = (Bx) - (A/3) */ 523 ret = fp_sub(&(out_montgomery->u), &tmp2, &tmp); EG(ret, err); 524 525 /* v = By */ 526 ret = fp_mul(&(out_montgomery->v), &(montgomery_crv->B), &(in_shortw->y)); EG(ret, err); 527 528 /* Final check that the point is on the curve */ 529 MUST_HAVE((!aff_pt_montgomery_is_on_curve(out_montgomery, &on_curve)) && on_curve, ret, err); 530 531 err: 532 fp_uninit(&tmp); 533 fp_uninit(&tmp2); 534 535 return ret; 536 } 537 538 539 /* 540 * Recover the two possible v coordinates from one u on a given 541 * curve. 542 * The two outputs v1 and v2 are initialized in the function. 543 * 544 * The function returns -1 on error, 0 on success. 545 * 546 */ 547 int aff_pt_montgomery_v_from_u(fp_t v1, fp_t v2, fp_src_t u, ec_montgomery_crv_src_t crv) 548 { 549 int ret; 550 551 /* Sanity checks */ 552 ret = fp_check_initialized(u); EG(ret, err); 553 ret = ec_montgomery_crv_check_initialized(crv); EG(ret, err); 554 MUST_HAVE((u->ctx == crv->A.ctx) && (u->ctx == crv->B.ctx), ret, err); 555 MUST_HAVE((v1 != NULL) && (v2 != NULL), ret, err); 556 /* Aliasing is not supported */ 557 MUST_HAVE((v1 != v2) && (v1 != u), ret, err); 558 559 /* Initialize v1 and v2 with context */ 560 ret = fp_init(v1, u->ctx); EG(ret, err); 561 ret = fp_init(v2, u->ctx); EG(ret, err); 562 563 /* v must satisfy the equation B v^2 = u^3 + A u^2 + u, 564 * so we compute square root for B^-1 * (u^3 + A u^2 + u) 565 */ 566 ret = fp_sqr(v2, u); EG(ret, err); 567 ret = fp_mul(v1, v2, u); EG(ret, err); 568 ret = fp_mul(v2, v2, &(crv->A)); EG(ret, err); 569 ret = fp_add(v1, v1, v2); EG(ret, err); 570 ret = fp_add(v1, v1, u); EG(ret, err); 571 ret = fp_inv(v2, &(crv->B)); EG(ret, err); 572 ret = fp_mul(v1, v1, v2); EG(ret, err); 573 574 /* Choose any of the two square roots as the solution */ 575 ret = fp_sqrt(v1, v2, v1); 576 577 err: 578 return ret; 579 }