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 */
aff_pt_montgomery_check_initialized(aff_pt_montgomery_src_t in)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 */
aff_pt_montgomery_init(aff_pt_montgomery_t in,ec_montgomery_crv_src_t curve)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 */
aff_pt_montgomery_init_from_coords(aff_pt_montgomery_t in,ec_montgomery_crv_src_t curve,fp_src_t ucoord,fp_src_t vcoord)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 */
aff_pt_montgomery_uninit(aff_pt_montgomery_t in)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 */
is_on_montgomery_curve(fp_src_t u,fp_src_t v,ec_montgomery_crv_src_t curve,int * on_curve)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 */
aff_pt_montgomery_is_on_curve(aff_pt_montgomery_src_t pt,int * on_curve)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 */
ec_montgomery_aff_copy(aff_pt_montgomery_t out,aff_pt_montgomery_src_t in)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 */
ec_montgomery_aff_cmp(aff_pt_montgomery_src_t in1,aff_pt_montgomery_src_t in2,int * cmp)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 */
aff_pt_montgomery_import_from_buf(aff_pt_montgomery_t pt,const u8 * pt_buf,u16 pt_buf_len,ec_montgomery_crv_src_t crv)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 */
aff_pt_montgomery_export_to_buf(aff_pt_montgomery_src_t pt,u8 * pt_buf,u32 pt_buf_len)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 */
curve_montgomery_to_shortw(ec_montgomery_crv_src_t montgomery_crv,ec_shortw_crv_t shortw_crv)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 */
curve_montgomery_shortw_check(ec_montgomery_crv_src_t montgomery_crv,ec_shortw_crv_src_t shortw_crv)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 */
curve_shortw_to_montgomery(ec_shortw_crv_src_t shortw_crv,ec_montgomery_crv_t montgomery_crv,fp_src_t alpha,fp_src_t gamma)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 */
aff_pt_montgomery_to_shortw(aff_pt_montgomery_src_t in_montgomery,ec_shortw_crv_src_t shortw_crv,aff_pt_t out_shortw)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 */
aff_pt_shortw_to_montgomery(aff_pt_src_t in_shortw,ec_montgomery_crv_src_t montgomery_crv,aff_pt_montgomery_t out_montgomery)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 */
aff_pt_montgomery_v_from_u(fp_t v1,fp_t v2,fp_src_t u,ec_montgomery_crv_src_t crv)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 }
580