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 /* NOTE: Edwards here implies Twisted Edwards curves
14 * (these in fact include/extend basic form Edwards curves).
15 */
16
17 #define AFF_PT_EDWARDS_MAGIC ((word_t)(0x8390a9bc43d9ffabULL))
18
19 /* Verify that an affine point has already been initialized
20 *
21 * Returns 0 on success, -1 on error.
22 */
aff_pt_edwards_check_initialized(aff_pt_edwards_src_t in)23 int aff_pt_edwards_check_initialized(aff_pt_edwards_src_t in)
24 {
25 int ret;
26
27 MUST_HAVE(((in != NULL) && (in->magic == AFF_PT_EDWARDS_MAGIC)), ret, err);
28 ret = ec_edwards_crv_check_initialized(in->crv);
29
30 err:
31 return ret;
32 }
33
34 /*
35 * Initialize pointed aff_pt_edwards structure to make it usable by library
36 * function on given curve.
37 *
38 * Returns 0 on success, -1 on error.
39 */
aff_pt_edwards_init(aff_pt_edwards_t in,ec_edwards_crv_src_t curve)40 int aff_pt_edwards_init(aff_pt_edwards_t in, ec_edwards_crv_src_t curve)
41 {
42 int ret;
43
44 MUST_HAVE((in != NULL), ret, err);
45 ret = ec_edwards_crv_check_initialized(curve); EG(ret, err);
46
47 ret = fp_init(&(in->x), curve->a.ctx); EG(ret, err);
48 ret = fp_init(&(in->y), curve->a.ctx); EG(ret, err);
49
50 in->crv = curve;
51 in->magic = AFF_PT_EDWARDS_MAGIC;
52
53 err:
54 return ret;
55 }
56
57 /*
58 * Initialize pointed aff_pt_edwards structure to make it usable by library
59 * function on given curve with explicit coordinates.
60 *
61 * Returns 0 on success, -1 on error.
62 */
aff_pt_edwards_init_from_coords(aff_pt_edwards_t in,ec_edwards_crv_src_t curve,fp_src_t xcoord,fp_src_t ycoord)63 int aff_pt_edwards_init_from_coords(aff_pt_edwards_t in,
64 ec_edwards_crv_src_t curve,
65 fp_src_t xcoord, fp_src_t ycoord)
66 {
67 int ret;
68
69 ret = aff_pt_edwards_init(in, curve); EG(ret, err);
70 ret = fp_copy(&(in->x), xcoord); EG(ret, err);
71 ret = fp_copy(&(in->y), ycoord);
72
73 err:
74 return ret;
75 }
76
77 /*
78 * Uninitialize pointed affine point to prevent further use (magic field
79 * in the structure is zeroized) and zeroize associated storage space.
80 * Note that the curve context pointed to by the point element (passed
81 * during init) is left untouched.
82 *
83 */
aff_pt_edwards_uninit(aff_pt_edwards_t in)84 void aff_pt_edwards_uninit(aff_pt_edwards_t in)
85 {
86 if ((in != NULL) && (in->magic == AFF_PT_EDWARDS_MAGIC) && (in->crv != NULL)) {
87 fp_uninit(&(in->x));
88 fp_uninit(&(in->y));
89
90 in->crv = NULL;
91 in->magic = WORD(0);
92 }
93
94 return;
95 }
96
97 /*
98 * 'on_curve' set to 1 if the point of coordinates (u,v) is on the curve, i.e. if it
99 * verifies curve equation a*x^2 + y^2 = 1 + d*x^2*y^2. It is set to 0 otherwise.
100 * 'on_curve' is not meaningful on error.
101 *
102 * Returns 0 on success, -1 on error.
103 */
is_on_edwards_curve(fp_src_t x,fp_src_t y,ec_edwards_crv_src_t curve,int * on_curve)104 int is_on_edwards_curve(fp_src_t x, fp_src_t y,
105 ec_edwards_crv_src_t curve,
106 int *on_curve)
107 {
108 fp x2, y2, tmp1, tmp2;
109 int ret, cmp;
110 x2.magic = y2.magic = tmp1.magic = tmp2.magic = WORD(0);
111
112 MUST_HAVE((on_curve != NULL), ret, err);
113 ret = ec_edwards_crv_check_initialized(curve); EG(ret, err);
114
115 ret = fp_check_initialized(x); EG(ret, err);
116 ret = fp_check_initialized(y); EG(ret, err);
117
118 MUST_HAVE((x->ctx == y->ctx), ret, err);
119 MUST_HAVE((x->ctx == curve->a.ctx), ret, err);
120
121 ret = fp_init(&x2, x->ctx); EG(ret, err);
122 ret = fp_sqr(&x2, x); EG(ret, err);
123 ret = fp_init(&y2, x->ctx); EG(ret, err);
124 ret = fp_sqr(&y2, y); EG(ret, err);
125
126 ret = fp_init(&tmp1, x->ctx); EG(ret, err);
127 ret = fp_init(&tmp2, x->ctx); EG(ret, err);
128
129 ret = fp_mul(&tmp1, &x2, &y2); EG(ret, err);
130 ret = fp_mul(&tmp1, &tmp1, &(curve->d)); EG(ret, err);
131 ret = fp_inc(&tmp1, &tmp1); EG(ret, err);
132
133 ret = fp_mul(&tmp2, &x2, &(curve->a)); EG(ret, err);
134 ret = fp_add(&tmp2, &tmp2, &y2); EG(ret, err);
135
136 ret = fp_cmp(&tmp1, &tmp2, &cmp);
137
138 if (!ret) {
139 (*on_curve) = (!cmp);
140 }
141
142 err:
143 fp_uninit(&x2);
144 fp_uninit(&y2);
145 fp_uninit(&tmp1);
146 fp_uninit(&tmp2);
147
148 return ret;
149 }
150
151 /*
152 * Checks if affine coordinates point is on an Edwards curve. 'on_curve' is set
153 * to 1 if yes, 0 if no. 'on_curve' is not meaningful in case of error.
154 *
155 * Returns 0 on success, -1 on error.
156 */
aff_pt_edwards_is_on_curve(aff_pt_edwards_src_t pt,int * on_curve)157 int aff_pt_edwards_is_on_curve(aff_pt_edwards_src_t pt, int *on_curve)
158 {
159 int ret;
160
161 ret = aff_pt_edwards_check_initialized(pt); EG(ret, err);
162
163 ret = is_on_edwards_curve(&(pt->x), &(pt->y), pt->crv, on_curve);
164
165 err:
166 return ret;
167 }
168
169 /*
170 * Copy an Edwards affine point in an output. The output is initialized properly.
171 *
172 * Returns 0 on success, -1 on error.
173 */
ec_edwards_aff_copy(aff_pt_edwards_t out,aff_pt_edwards_src_t in)174 int ec_edwards_aff_copy(aff_pt_edwards_t out, aff_pt_edwards_src_t in)
175 {
176 int ret;
177
178 ret = aff_pt_edwards_check_initialized(in); EG(ret, err);
179 ret = aff_pt_edwards_init(out, in->crv); EG(ret, err);
180
181 ret = fp_copy(&(out->x), &(in->x)); EG(ret, err);
182 ret = fp_copy(&(out->y), &(in->y));
183
184 err:
185 return ret;
186 }
187
188 /*
189 * Compares two given affine points on an Edwards curve, it returns 0 in input
190 * 'cmp' if they correspond or not 0 if not. 'cmp' is not meaningful on error.
191 *
192 * Returns 0 on success, -1 on error.
193 */
ec_edwards_aff_cmp(aff_pt_edwards_src_t in1,aff_pt_edwards_src_t in2,int * cmp)194 int ec_edwards_aff_cmp(aff_pt_edwards_src_t in1, aff_pt_edwards_src_t in2,
195 int *cmp)
196 {
197 int ret, cmp1, cmp2;
198
199 MUST_HAVE((cmp != NULL), ret, err);
200 ret = aff_pt_edwards_check_initialized(in1); EG(ret, err);
201 ret = aff_pt_edwards_check_initialized(in2); EG(ret, err);
202
203 MUST_HAVE((in1->crv == in2->crv), ret, err);
204
205 ret = fp_cmp(&(in1->x), &(in2->x), &cmp1); EG(ret, err);
206 ret = fp_cmp(&(in1->y), &(in2->y), &cmp2);
207
208 if (!ret) {
209 (*cmp) = (cmp1 | cmp2);
210 }
211
212 err:
213 return ret;
214 }
215
216 /*
217 * Import an Edwards affine point from a buffer with the following layout; the 2
218 * coordinates (elements of Fp) are each encoded on p_len bytes, where p_len
219 * is the size of p in bytes (e.g. 66 for a prime p of 521 bits). Each
220 * coordinate is encoded in big endian. Size of buffer must exactly match
221 * 2 * p_len.
222 *
223 * Returns 0 on success, -1 on error.
224 */
aff_pt_edwards_import_from_buf(aff_pt_edwards_t pt,const u8 * pt_buf,u16 pt_buf_len,ec_edwards_crv_src_t crv)225 int aff_pt_edwards_import_from_buf(aff_pt_edwards_t pt,
226 const u8 *pt_buf,
227 u16 pt_buf_len, ec_edwards_crv_src_t crv)
228 {
229 fp_ctx_src_t ctx;
230 u16 coord_len;
231 int ret, on_curve;
232
233 ret = ec_edwards_crv_check_initialized(crv); EG(ret, err);
234 MUST_HAVE(((pt_buf != NULL) && (pt != NULL)), ret, err);
235
236 ctx = crv->a.ctx;
237 coord_len = (u16)BYTECEIL(ctx->p_bitlen);
238
239 MUST_HAVE((pt_buf_len == (2 * coord_len)), ret, err);
240
241 ret = fp_init_from_buf(&(pt->x), ctx, pt_buf, coord_len); EG(ret, err);
242 ret = fp_init_from_buf(&(pt->y), ctx, pt_buf + coord_len, coord_len); EG(ret, err);
243
244 /* Set the curve */
245 pt->crv = crv;
246
247 /* Mark the point as initialized */
248 pt->magic = AFF_PT_EDWARDS_MAGIC;
249
250 /* Check that the point is indeed on the provided curve, uninitialize it
251 * if this is not the case.
252 */
253 ret = aff_pt_edwards_is_on_curve(pt, &on_curve); EG(ret, err);
254 if (!on_curve) {
255 aff_pt_edwards_uninit(pt);
256 ret = -1;
257 }
258
259 err:
260 return ret;
261 }
262
263
264 /* Export an Edwards affine point to a buffer with the following layout; the 2
265 * coordinates (elements of Fp) are each encoded on p_len bytes, where p_len
266 * is the size of p in bytes (e.g. 66 for a prime p of 521 bits). Each
267 * coordinate is encoded in big endian. Size of buffer must exactly match
268 * 2 * p_len.
269 *
270 * Returns 0 on success, -1 on error.
271 */
aff_pt_edwards_export_to_buf(aff_pt_edwards_src_t pt,u8 * pt_buf,u32 pt_buf_len)272 int aff_pt_edwards_export_to_buf(aff_pt_edwards_src_t pt,
273 u8 *pt_buf, u32 pt_buf_len)
274 {
275 fp_ctx_src_t ctx;
276 u16 coord_len;
277 int ret, on_curve;
278
279 ret = aff_pt_edwards_check_initialized(pt); EG(ret, err);
280 MUST_HAVE((pt_buf != NULL), ret, err);
281
282 /* The point to be exported must be on the curve */
283 ret = aff_pt_edwards_is_on_curve(pt, &on_curve); EG(ret, err);
284 MUST_HAVE(on_curve, ret, err);
285
286 ctx = pt->crv->a.ctx;
287 coord_len = (u16)BYTECEIL(ctx->p_bitlen);
288
289 MUST_HAVE((pt_buf_len == (2 * coord_len)), ret, err);
290
291 /* Export the three coordinates */
292 ret = fp_export_to_buf(pt_buf, coord_len, &(pt->x)); EG(ret, err);
293 ret = fp_export_to_buf(pt_buf + coord_len, coord_len, &(pt->y));
294
295 err:
296 return ret;
297 }
298
299 /*
300 * Mapping curves from twisted Edwards to Montgomery.
301 *
302 * E{a, d} is mapped to M{A, B} using the formula:
303 * A = 2(a+d)/(a-d)
304 * B = 4/((a-d) * alpha^2)
305 *
306 * Returns 0 on success, -1 on error.
307 */
curve_edwards_to_montgomery(ec_edwards_crv_src_t edwards_crv,ec_montgomery_crv_t montgomery_crv,fp_src_t alpha_edwards)308 int curve_edwards_to_montgomery(ec_edwards_crv_src_t edwards_crv,
309 ec_montgomery_crv_t montgomery_crv,
310 fp_src_t alpha_edwards)
311 {
312 fp tmp1, tmp2, A, B;
313 int ret;
314 tmp1.magic = tmp2.magic = A.magic = B.magic = WORD(0);
315
316 ret = ec_edwards_crv_check_initialized(edwards_crv); EG(ret, err);
317 ret = fp_check_initialized(alpha_edwards); EG(ret, err);
318 MUST_HAVE((edwards_crv->a.ctx == alpha_edwards->ctx), ret, err);
319
320 ret = fp_init(&tmp1, edwards_crv->a.ctx); EG(ret, err);
321 ret = fp_init(&tmp2, edwards_crv->a.ctx); EG(ret, err);
322 ret = fp_init(&A, edwards_crv->a.ctx); EG(ret, err);
323 ret = fp_init(&B, edwards_crv->a.ctx); EG(ret, err);
324
325
326 /* Compute Z = (alpha ^ 2) et T = 2 / ((a-d) * Z)
327 * and then:
328 * A = 2(a+d)/(a-d) = Z * (a + d) * T
329 * B = 4/((a-d) * alpha^2) = 2 * T
330 */
331 ret = fp_sqr(&tmp1, alpha_edwards); EG(ret, err);
332 ret = fp_sub(&tmp2, &(edwards_crv->a), &(edwards_crv->d)); EG(ret, err);
333 ret = fp_mul(&tmp2, &tmp2, &tmp1); EG(ret, err);
334 ret = fp_inv(&tmp2, &tmp2); EG(ret, err);
335 ret = fp_set_word_value(&B, WORD(2)); EG(ret, err);
336 ret = fp_mul(&tmp2, &tmp2, &B); EG(ret, err);
337
338 ret = fp_add(&A, &(edwards_crv->a), &(edwards_crv->d)); EG(ret, err);
339 ret = fp_mul(&A, &A, &tmp1); EG(ret, err);
340 ret = fp_mul(&A, &A, &tmp2); EG(ret, err);
341 ret = fp_mul(&B, &B, &tmp2); EG(ret, err);
342
343 /* Initialize our Montgomery curve */
344 ret = ec_montgomery_crv_init(montgomery_crv, &A, &B, &(edwards_crv->order));
345
346 err:
347 fp_uninit(&tmp1);
348 fp_uninit(&tmp2);
349 fp_uninit(&A);
350 fp_uninit(&B);
351
352 return ret;
353 }
354
355 /*
356 * Checks that an Edwards curve and Montgomery curve are compatible.
357 *
358 * Returns 0 on success, -1 on error.
359 */
curve_edwards_montgomery_check(ec_edwards_crv_src_t e_crv,ec_montgomery_crv_src_t m_crv,fp_src_t alpha_edwards)360 int curve_edwards_montgomery_check(ec_edwards_crv_src_t e_crv,
361 ec_montgomery_crv_src_t m_crv,
362 fp_src_t alpha_edwards)
363 {
364 int ret, cmp;
365 ec_montgomery_crv check;
366 check.magic = WORD(0);
367
368 ret = ec_montgomery_crv_check_initialized(m_crv); EG(ret, err);
369 ret = curve_edwards_to_montgomery(e_crv, &check, alpha_edwards); EG(ret, err);
370
371 /* Check elements */
372 MUST_HAVE((!fp_cmp(&(check.A), &(m_crv->A), &cmp)) && (!cmp), ret, err);
373 MUST_HAVE((!fp_cmp(&(check.B), &(m_crv->B), &cmp)) && (!cmp), ret, err);
374 MUST_HAVE((!nn_cmp(&(check.order), &(m_crv->order), &cmp)) && (!cmp), ret, err);
375
376 err:
377 ec_montgomery_crv_uninit(&check);
378
379 return ret;
380 }
381
382 /*
383 * Mapping curves from Montgomery to twisted Edwards.
384 *
385 * M{A, B} is mapped to E{a, d} using the formula:
386 * a = (A+2)/(B * alpha^2)
387 * d = (A-2)/(B * alpha^2)
388 *
389 * Or the inverse (switch a and d roles).
390 *
391 * Returns 0 on success, -1 on error.
392 */
curve_montgomery_to_edwards(ec_montgomery_crv_src_t m_crv,ec_edwards_crv_t e_crv,fp_src_t alpha_edwards)393 int curve_montgomery_to_edwards(ec_montgomery_crv_src_t m_crv,
394 ec_edwards_crv_t e_crv,
395 fp_src_t alpha_edwards)
396 {
397 int ret, cmp;
398 fp tmp, tmp2, a, d;
399 tmp.magic = tmp2.magic = a.magic = d.magic = WORD(0);
400
401 ret = ec_montgomery_crv_check_initialized(m_crv); EG(ret, err);
402 ret = fp_check_initialized(alpha_edwards); EG(ret, err);
403 MUST_HAVE((m_crv->A.ctx == alpha_edwards->ctx), ret, err);
404
405 ret = fp_init(&tmp, m_crv->A.ctx); EG(ret, err);
406 ret = fp_init(&tmp2, m_crv->A.ctx); EG(ret, err);
407 ret = fp_init(&a, m_crv->A.ctx); EG(ret, err);
408 ret = fp_init(&d, m_crv->A.ctx); EG(ret, err);
409
410 ret = fp_set_word_value(&tmp, WORD(2)); EG(ret, err);
411 ret = fp_mul(&tmp2, &(m_crv->B), alpha_edwards); EG(ret, err);
412 ret = fp_mul(&tmp2, &tmp2, alpha_edwards); EG(ret, err);
413 ret = fp_inv(&tmp2, &tmp2); EG(ret, err);
414
415 /* a = (A+2)/(B * alpha^2) */
416 ret = fp_add(&a, &(m_crv->A), &tmp); EG(ret, err);
417 ret = fp_mul(&a, &a, &tmp2); EG(ret, err);
418
419 /* d = (A-2)/(B * alpha^2) */
420 ret = fp_sub(&d, &(m_crv->A), &tmp); EG(ret, err);
421 ret = fp_mul(&d, &d, &tmp2); EG(ret, err);
422
423 /* Initialize our Edwards curve */
424 /* Check if we have to inverse a and d */
425 ret = fp_one(&tmp); EG(ret, err);
426 ret = fp_cmp(&d, &tmp, &cmp); EG(ret, err);
427 if (cmp == 0) {
428 ret = ec_edwards_crv_init(e_crv, &d, &a, &(m_crv->order));
429 } else {
430 ret = ec_edwards_crv_init(e_crv, &a, &d, &(m_crv->order));
431 }
432
433 err:
434 fp_uninit(&tmp);
435 fp_uninit(&tmp2);
436 fp_uninit(&a);
437 fp_uninit(&d);
438
439 return ret;
440 }
441
442 /*
443 * Mapping curve from Edwards to short Weierstrass.
444 *
445 * Returns 0 on success, -1 on error.
446 */
curve_edwards_to_shortw(ec_edwards_crv_src_t edwards_crv,ec_shortw_crv_t shortw_crv,fp_src_t alpha_edwards)447 int curve_edwards_to_shortw(ec_edwards_crv_src_t edwards_crv,
448 ec_shortw_crv_t shortw_crv,
449 fp_src_t alpha_edwards)
450 {
451 int ret;
452 ec_montgomery_crv montgomery_crv;
453 montgomery_crv.magic = WORD(0);
454
455 ret = curve_edwards_to_montgomery(edwards_crv, &montgomery_crv, alpha_edwards); EG(ret, err);
456 ret = curve_montgomery_to_shortw(&montgomery_crv, shortw_crv);
457
458 err:
459 ec_montgomery_crv_uninit(&montgomery_crv);
460
461 return ret;
462 }
463
464 /* Checking if an Edwards curve and short Weierstrass curve are compliant (through Montgomery mapping).
465 *
466 * Returns 0 on success, -1 on error.
467 */
curve_edwards_shortw_check(ec_edwards_crv_src_t edwards_crv,ec_shortw_crv_src_t shortw_crv,fp_src_t alpha_edwards)468 int curve_edwards_shortw_check(ec_edwards_crv_src_t edwards_crv,
469 ec_shortw_crv_src_t shortw_crv,
470 fp_src_t alpha_edwards)
471 {
472 int ret;
473 ec_montgomery_crv montgomery_crv;
474 montgomery_crv.magic = WORD(0);
475
476 ret = curve_edwards_to_montgomery(edwards_crv, &montgomery_crv, alpha_edwards); EG(ret, err);
477
478 ret = curve_montgomery_shortw_check(&montgomery_crv, shortw_crv);
479
480 err:
481 ec_montgomery_crv_uninit(&montgomery_crv);
482
483 return ret;
484 }
485
486 /*
487 * Mapping curve from short Weierstrass to Edwards.
488 *
489 * Returns 0 on success, -1 on error.
490 */
curve_shortw_to_edwards(ec_shortw_crv_src_t shortw_crv,ec_edwards_crv_t edwards_crv,fp_src_t alpha_montgomery,fp_src_t gamma_montgomery,fp_src_t alpha_edwards)491 int curve_shortw_to_edwards(ec_shortw_crv_src_t shortw_crv,
492 ec_edwards_crv_t edwards_crv,
493 fp_src_t alpha_montgomery,
494 fp_src_t gamma_montgomery,
495 fp_src_t alpha_edwards)
496 {
497 int ret;
498 ec_montgomery_crv montgomery_crv;
499 montgomery_crv.magic = WORD(0);
500
501 ret = curve_shortw_to_montgomery(shortw_crv, &montgomery_crv, alpha_montgomery, gamma_montgomery); EG(ret, err);
502
503 ret = curve_montgomery_to_edwards(&montgomery_crv, edwards_crv, alpha_edwards);
504
505 err:
506 ec_montgomery_crv_uninit(&montgomery_crv);
507
508 return ret;
509 }
510
511 /*
512 * Mapping points from twisted Edwards to Montgomery.
513 * Point E(x, y) is mapped to M(u, v) with the formula:
514 * - (0, 1) mapped to the point at infinity (not possible in our affine coordinates)
515 * - (0, -1) mapped to (0, 0)
516 * - (u, v) mapped to ((1+y)/(1-y), alpha * (1+y)/((1-y)x))
517 *
518 * Returns 0 on success, -1 on error.
519 */
aff_pt_edwards_to_montgomery(aff_pt_edwards_src_t in_edwards,ec_montgomery_crv_src_t montgomery_crv,aff_pt_montgomery_t out_montgomery,fp_src_t alpha_edwards)520 int aff_pt_edwards_to_montgomery(aff_pt_edwards_src_t in_edwards,
521 ec_montgomery_crv_src_t montgomery_crv,
522 aff_pt_montgomery_t out_montgomery,
523 fp_src_t alpha_edwards)
524 {
525 /* NOTE: we attempt to perform the (0, -1) -> (0, 0) mapping in constant time.
526 * Hence the weird table selection.
527 */
528 int ret, iszero, on_curve, cmp;
529 fp tmp, tmp2, x, y;
530 fp tab_x[2];
531 fp_src_t tab_x_t[2] = { &tab_x[0], &tab_x[1] };
532 fp tab_y[2];
533 fp_src_t tab_y_t[2] = { &tab_y[0], &tab_y[1] };
534 u8 idx = 0;
535 tmp.magic = tmp2.magic = x.magic = y.magic = WORD(0);
536 tab_x[0].magic = tab_x[1].magic = WORD(0);
537 tab_y[0].magic = tab_y[1].magic = WORD(0);
538
539 ret = ec_montgomery_crv_check_initialized(montgomery_crv); EG(ret, err);
540
541 /* Check input point is on its curve */
542 ret = aff_pt_edwards_is_on_curve(in_edwards, &on_curve); EG(ret, err);
543 MUST_HAVE(on_curve, ret, err);
544
545 ret = curve_edwards_montgomery_check(in_edwards->crv, montgomery_crv, alpha_edwards); EG(ret, err);
546
547 ret = fp_init(&tmp, in_edwards->crv->a.ctx); EG(ret, err);
548 ret = fp_init(&tmp2, in_edwards->crv->a.ctx); EG(ret, err);
549 ret = fp_init(&x, in_edwards->crv->a.ctx); EG(ret, err);
550 ret = fp_init(&y, in_edwards->crv->a.ctx); EG(ret, err);
551 ret = fp_init(&tab_x[0], in_edwards->crv->a.ctx); EG(ret, err);
552 ret = fp_init(&tab_x[1], in_edwards->crv->a.ctx); EG(ret, err);
553 ret = fp_init(&tab_y[0], in_edwards->crv->a.ctx); EG(ret, err);
554 ret = fp_init(&tab_y[1], in_edwards->crv->a.ctx); EG(ret, err);
555
556 ret = fp_one(&tmp); EG(ret, err);
557 /* We do not handle point at infinity in affine coordinates */
558 ret = fp_iszero(&(in_edwards->x), &iszero); EG(ret, err);
559 ret = fp_cmp(&(in_edwards->y), &tmp, &cmp); EG(ret, err);
560 MUST_HAVE(!(iszero && (cmp == 0)), ret, err);
561 /* Map (0, -1) to (0, 0) */
562 ret = fp_zero(&tmp2); EG(ret, err);
563 ret = fp_sub(&tmp2, &tmp2, &tmp); EG(ret, err);
564 /* Copy 1 as x as dummy value */
565 ret = fp_one(&tab_x[0]); EG(ret, err);
566 ret = fp_copy(&tab_x[1], &(in_edwards->x)); EG(ret, err);
567 /* Copy -1 as y to produce (0, 0) */
568 ret = fp_copy(&tab_y[0], &tmp2); EG(ret, err);
569 ret = fp_copy(&tab_y[1], &(in_edwards->y)); EG(ret, err);
570
571 ret = fp_iszero(&(in_edwards->x), &iszero); EG(ret, err);
572 ret = fp_cmp(&(in_edwards->y), &tmp2, &cmp); EG(ret, err);
573 idx = !(iszero && cmp);
574 ret = fp_tabselect(&x, idx, tab_x_t, 2); EG(ret, err);
575 ret = fp_tabselect(&y, idx, tab_y_t, 2); EG(ret, err);
576
577 ret = aff_pt_montgomery_init(out_montgomery, montgomery_crv); EG(ret, err);
578 /* Compute general case */
579 ret = fp_copy(&tmp2, &tmp); EG(ret, err);
580 /* Put 1/(1-y) in tmp */
581 ret = fp_sub(&tmp, &tmp, &y); EG(ret, err);
582 ret = fp_inv(&tmp, &tmp); EG(ret, err);
583 /* Put (1+y) in tmp2 */
584 ret = fp_add(&tmp2, &tmp2, &y); EG(ret, err);
585 /* u = (1+y) / (1-y) */
586 ret = fp_mul(&(out_montgomery->u), &tmp, &tmp2); EG(ret, err);
587 /* v = alpha_edwards * (1+y)/((1-y)x) */
588 ret = fp_inv(&(out_montgomery->v), &x); EG(ret, err);
589 ret = fp_mul(&(out_montgomery->v), &(out_montgomery->v), alpha_edwards); EG(ret, err);
590 ret = fp_mul(&(out_montgomery->v), &(out_montgomery->u), &(out_montgomery->v)); EG(ret, err);
591
592 /* Final check that the point is on the curve */
593 ret = aff_pt_montgomery_is_on_curve(out_montgomery, &on_curve); EG(ret, err);
594 if (!on_curve) {
595 ret = -1;
596 }
597
598 err:
599 fp_uninit(&tmp);
600 fp_uninit(&tmp2);
601 fp_uninit(&x);
602 fp_uninit(&y);
603 fp_uninit(&tab_x[0]);
604 fp_uninit(&tab_x[1]);
605 fp_uninit(&tab_y[0]);
606 fp_uninit(&tab_y[1]);
607
608 return ret;
609 }
610
611 /*
612 * Mapping points from Montgomery to twisted Edwards.
613 * Point M(u, v) is mapped to E(x, y) with the formula:
614 * - Point at infinity mapped to (0, 1) (not possible in our affine coordinates)
615 * - (0, 0) mapped to (0, -1)
616 * - (x, y) mapped to (alpha * (u/v), (u-1)/(u+1))
617 *
618 * Returns 0 on success, -1 on error.
619 */
aff_pt_montgomery_to_edwards(aff_pt_montgomery_src_t in_montgomery,ec_edwards_crv_src_t edwards_crv,aff_pt_edwards_t out_edwards,fp_src_t alpha)620 int aff_pt_montgomery_to_edwards(aff_pt_montgomery_src_t in_montgomery,
621 ec_edwards_crv_src_t edwards_crv,
622 aff_pt_edwards_t out_edwards,
623 fp_src_t alpha)
624 {
625 /* NOTE: we attempt to perform the (0, 0) -> (0, -1) mapping in constant time.
626 * Hence the weird table selection.
627 */
628 int ret, iszero1, iszero2, on_curve;
629 fp tmp, u, v;
630 fp tab_u[2];
631 fp_src_t tab_u_t[2] = { &tab_u[0], &tab_u[1] };
632 fp tab_v[2];
633 fp_src_t tab_v_t[2] = { &tab_v[0], &tab_v[1] };
634 u8 idx = 0;
635 tmp.magic = u.magic = v.magic = 0;
636 tab_u[0].magic = tab_u[1].magic = WORD(0);
637 tab_v[0].magic = tab_v[1].magic = WORD(0);
638
639 ret = ec_edwards_crv_check_initialized(edwards_crv); EG(ret, err);
640
641 /* Check input point is on its curve */
642 ret = aff_pt_montgomery_is_on_curve(in_montgomery, &on_curve); EG(ret, err);
643 MUST_HAVE(on_curve, ret, err);
644
645 ret = curve_edwards_montgomery_check(edwards_crv, in_montgomery->crv, alpha); EG(ret, err);
646
647 ret = fp_init(&tmp, in_montgomery->crv->A.ctx); EG(ret, err);
648 ret = fp_init(&u, in_montgomery->crv->A.ctx); EG(ret, err);
649 ret = fp_init(&v, in_montgomery->crv->A.ctx); EG(ret, err);
650 ret = fp_init(&tab_u[0], in_montgomery->crv->A.ctx); EG(ret, err);
651 ret = fp_init(&tab_u[1], in_montgomery->crv->A.ctx); EG(ret, err);
652 ret = fp_init(&tab_v[0], in_montgomery->crv->A.ctx); EG(ret, err);
653 ret = fp_init(&tab_v[1], in_montgomery->crv->A.ctx); EG(ret, err);
654
655 ret = fp_one(&tmp); EG(ret, err);
656 /* Map (0, 0) to (0, -1) */
657 /* Copy 0 as u as dummy value */
658 ret = fp_zero(&tab_u[0]); EG(ret, err);
659 ret = fp_copy(&tab_u[1], &(in_montgomery->u)); EG(ret, err);
660 /* Copy 1 as v dummy value to produce (0, -1) */
661 ret = fp_copy(&tab_v[0], &tmp); EG(ret, err);
662 ret = fp_copy(&tab_v[1], &(in_montgomery->v)); EG(ret, err);
663
664 ret = fp_iszero(&(in_montgomery->u), &iszero1); EG(ret, err);
665 ret = fp_iszero(&(in_montgomery->v), &iszero2); EG(ret, err);
666 idx = (iszero1 && iszero2) ? 0 : 1;
667 ret = fp_tabselect(&u, idx, tab_u_t, 2); EG(ret, err);
668 ret = fp_tabselect(&v, idx, tab_v_t, 2); EG(ret, err);
669
670 ret = aff_pt_edwards_init(out_edwards, edwards_crv); EG(ret, err);
671 /* x = alpha * (u / v) */
672 ret = fp_inv(&(out_edwards->x), &v); EG(ret, err);
673 ret = fp_mul(&(out_edwards->x), &(out_edwards->x), alpha); EG(ret, err);
674 ret = fp_mul(&(out_edwards->x), &(out_edwards->x), &u); EG(ret, err);
675 /* y = (u-1)/(u+1) */
676 ret = fp_add(&(out_edwards->y), &u, &tmp); EG(ret, err);
677 ret = fp_inv(&(out_edwards->y), &(out_edwards->y)); EG(ret, err);
678 ret = fp_sub(&tmp, &u, &tmp); EG(ret, err);
679 ret = fp_mul(&(out_edwards->y), &(out_edwards->y), &tmp); EG(ret, err);
680
681 /* Final check that the point is on the curve */
682 ret = aff_pt_edwards_is_on_curve(out_edwards, &on_curve); EG(ret, err);
683 if (!on_curve) {
684 ret = -1;
685 }
686
687 err:
688 fp_uninit(&tmp);
689 fp_uninit(&u);
690 fp_uninit(&v);
691 fp_uninit(&tab_u[0]);
692 fp_uninit(&tab_u[1]);
693 fp_uninit(&tab_v[0]);
694 fp_uninit(&tab_v[1]);
695
696 return ret;
697 }
698
699
700 /*
701 * Map points from Edwards to short Weierstrass through Montgomery (composition mapping).
702 *
703 * Returns 0 on success, -1 on error.
704 */
aff_pt_edwards_to_shortw(aff_pt_edwards_src_t in_edwards,ec_shortw_crv_src_t shortw_crv,aff_pt_t out_shortw,fp_src_t alpha_edwards)705 int aff_pt_edwards_to_shortw(aff_pt_edwards_src_t in_edwards,
706 ec_shortw_crv_src_t shortw_crv,
707 aff_pt_t out_shortw, fp_src_t alpha_edwards)
708 {
709 int ret;
710 aff_pt_montgomery inter_montgomery;
711 ec_montgomery_crv inter_montgomery_crv;
712 inter_montgomery.magic = inter_montgomery_crv.magic = WORD(0);
713
714 /* First, map from Edwards to Montgomery */
715 ret = aff_pt_edwards_check_initialized(in_edwards); EG(ret, err);
716 ret = curve_edwards_to_montgomery(in_edwards->crv, &inter_montgomery_crv, alpha_edwards); EG(ret, err);
717 ret = aff_pt_edwards_to_montgomery(in_edwards, &inter_montgomery_crv, &inter_montgomery, alpha_edwards); EG(ret, err);
718
719 /* Then map from Montgomery to short Weierstrass */
720 ret = aff_pt_montgomery_to_shortw(&inter_montgomery, shortw_crv, out_shortw);
721
722 err:
723 aff_pt_montgomery_uninit(&inter_montgomery);
724 ec_montgomery_crv_uninit(&inter_montgomery_crv);
725
726 return ret;
727 }
728
729 /*
730 * Map points from projective short Weierstrass to Edwards through Montgomery (composition mapping).
731 *
732 * Returns 0 on success, -1 on error.
733 */
aff_pt_shortw_to_edwards(aff_pt_src_t in_shortw,ec_edwards_crv_src_t edwards_crv,aff_pt_edwards_t out_edwards,fp_src_t alpha_edwards)734 int aff_pt_shortw_to_edwards(aff_pt_src_t in_shortw,
735 ec_edwards_crv_src_t edwards_crv,
736 aff_pt_edwards_t out_edwards,
737 fp_src_t alpha_edwards)
738 {
739 int ret;
740 aff_pt_montgomery inter_montgomery;
741 ec_montgomery_crv inter_montgomery_crv;
742 inter_montgomery.magic = inter_montgomery_crv.magic = WORD(0);
743
744 /* First, map from short Weierstrass to Montgomery */
745 ret = curve_edwards_to_montgomery(edwards_crv, &inter_montgomery_crv, alpha_edwards); EG(ret, err);
746 ret = aff_pt_shortw_to_montgomery(in_shortw, &inter_montgomery_crv, &inter_montgomery); EG(ret, err);
747
748 /* Then map from Montgomery to Edwards */
749 ret = aff_pt_montgomery_to_edwards(&inter_montgomery, edwards_crv, out_edwards, alpha_edwards);
750
751 err:
752 aff_pt_montgomery_uninit(&inter_montgomery);
753 ec_montgomery_crv_uninit(&inter_montgomery_crv);
754
755 return ret;
756 }
757
758 /*
759 * Recover the two possible y coordinates from one x on a given
760 * curve.
761 * The two outputs y1 and y2 are initialized in the function.
762 *
763 * The function returns -1 on error, 0 on success.
764 *
765 */
aff_pt_edwards_y_from_x(fp_t y1,fp_t y2,fp_src_t x,ec_edwards_crv_src_t crv)766 int aff_pt_edwards_y_from_x(fp_t y1, fp_t y2, fp_src_t x, ec_edwards_crv_src_t crv)
767 {
768 int ret;
769 fp tmp;
770 tmp.magic = WORD(0);
771
772 /* Sanity checks */
773 ret = fp_check_initialized(x); EG(ret, err);
774 ret = ec_edwards_crv_check_initialized(crv); EG(ret, err);
775 MUST_HAVE((x->ctx == crv->a.ctx) && (x->ctx == crv->d.ctx), ret, err);
776 MUST_HAVE((y1 != NULL) && (y2 != NULL), ret, err);
777 /* Aliasing is not supported */
778 MUST_HAVE((y1 != y2) && (y1 != x), ret, err);
779
780 ret = fp_init(y1, x->ctx); EG(ret, err);
781 ret = fp_init(y2, x->ctx); EG(ret, err);
782 ret = fp_init(&tmp, x->ctx); EG(ret, err);
783
784 /* In order to find our two possible y, we have to find the square
785 * roots of (1 - a x**2) / (1 - d * x**2).
786 */
787 ret = fp_one(&tmp); EG(ret, err);
788 /* (1 - a x**2) */
789 ret = fp_mul(y1, x, &(crv->a)); EG(ret, err);
790 ret = fp_mul(y1, y1, x); EG(ret, err);
791 ret = fp_sub(y1, &tmp, y1); EG(ret, err);
792 /* 1 / (1 - d * x**2) */
793 ret = fp_mul(y2, x, &(crv->d)); EG(ret, err);
794 ret = fp_mul(y2, y2, x); EG(ret, err);
795 ret = fp_sub(y2, &tmp, y2); EG(ret, err);
796 ret = fp_inv(y2, y2); EG(ret, err);
797
798 ret = fp_mul(&tmp, y1, y2); EG(ret, err);
799
800 ret = fp_sqrt(y1, y2, &tmp);
801
802 err:
803 fp_uninit(&tmp);
804
805 return ret;
806 }
807
808 /*
809 * Recover the two possible x coordinates from one y on a given
810 * curve.
811 * The two outputs x1 and x2 are initialized in the function.
812 *
813 * The function returns -1 on error, 0 on success.
814 *
815 */
aff_pt_edwards_x_from_y(fp_t x1,fp_t x2,fp_src_t y,ec_edwards_crv_src_t crv)816 int aff_pt_edwards_x_from_y(fp_t x1, fp_t x2, fp_src_t y, ec_edwards_crv_src_t crv)
817 {
818 int ret;
819 fp tmp;
820 tmp.magic = WORD(0);
821
822 /* Sanity checks */
823 ret = fp_check_initialized(y); EG(ret, err);
824 ret = ec_edwards_crv_check_initialized(crv); EG(ret, err);
825 MUST_HAVE((y->ctx == crv->a.ctx) && (y->ctx == crv->d.ctx), ret, err);
826 MUST_HAVE((x1 != NULL) && (x2 != NULL), ret, err);
827 /* Aliasing is not supported */
828 MUST_HAVE((x1 != x2) && (x1 != y), ret, err);
829
830 ret = fp_init(x1, y->ctx); EG(ret, err);
831 ret = fp_init(x2, y->ctx); EG(ret, err);
832 ret = fp_init(&tmp, y->ctx); EG(ret, err);
833
834 /* In order to find our two possible y, we have to find the square
835 * roots of (1 - y**2) / (a - d * y**2).
836 */
837 ret = fp_one(&tmp); EG(ret, err);
838 /* (1 - y**2) */
839 ret = fp_mul(x1, y, y); EG(ret, err);
840 ret = fp_sub(x1, &tmp, x1); EG(ret, err);
841 /* 1 / (a - d * x**2) */
842 ret = fp_mul(x2, y, &(crv->d)); EG(ret, err);
843 ret = fp_mul(x2, x2, y); EG(ret, err);
844 ret = fp_sub(x2, &(crv->a), x2); EG(ret, err);
845 ret = fp_inv(x2, x2); EG(ret, err);
846
847 ret = fp_mul(&tmp, x1, x2); EG(ret, err);
848
849 ret = fp_sqrt(x1, x2, &tmp);
850
851 err:
852 fp_uninit(&tmp);
853
854 return ret;
855 }
856