Line data Source code
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 <config.h>
22 : #include <stdio.h>
23 : #include <stdlib.h>
24 : #include <errno.h>
25 :
26 : #include "mpi-internal.h"
27 : #include "longlong.h"
28 : #include "g10lib.h"
29 : #include "context.h"
30 : #include "ec-context.h"
31 : #include "ec-internal.h"
32 :
33 :
34 : #define point_init(a) _gcry_mpi_point_init ((a))
35 : #define point_free(a) _gcry_mpi_point_free_parts ((a))
36 :
37 :
38 : /* Print a point using the log fucntions. If CTX is not NULL affine
39 : coordinates will be printed. */
40 : void
41 0 : _gcry_mpi_point_log (const char *name, mpi_point_t point, mpi_ec_t ctx)
42 : {
43 : gcry_mpi_t x, y;
44 : char buf[100];
45 :
46 0 : if (!point)
47 : {
48 0 : snprintf (buf, sizeof buf - 1, "%s.*", name);
49 0 : log_mpidump (buf, NULL);
50 0 : return;
51 : }
52 0 : snprintf (buf, sizeof buf - 1, "%s.X", name);
53 :
54 0 : if (ctx)
55 : {
56 0 : x = mpi_new (0);
57 0 : y = mpi_new (0);
58 : }
59 0 : if (!ctx || _gcry_mpi_ec_get_affine (x, y, point, ctx))
60 : {
61 0 : log_mpidump (buf, point->x);
62 0 : buf[strlen(buf)-1] = 'Y';
63 0 : log_mpidump (buf, point->y);
64 0 : buf[strlen(buf)-1] = 'Z';
65 0 : log_mpidump (buf, point->z);
66 : }
67 : else
68 : {
69 0 : buf[strlen(buf)-1] = 'x';
70 0 : log_mpidump (buf, x);
71 0 : buf[strlen(buf)-1] = 'y';
72 0 : log_mpidump (buf, y);
73 :
74 : }
75 0 : if (ctx)
76 : {
77 0 : _gcry_mpi_release (x);
78 0 : _gcry_mpi_release (y);
79 : }
80 : }
81 :
82 :
83 : /* Create a new point option. NBITS gives the size in bits of one
84 : coordinate; it is only used to pre-allocate some resources and
85 : might also be passed as 0 to use a default value. */
86 : mpi_point_t
87 39 : _gcry_mpi_point_new (unsigned int nbits)
88 : {
89 : mpi_point_t p;
90 :
91 : (void)nbits; /* Currently not used. */
92 :
93 39 : p = xmalloc (sizeof *p);
94 39 : _gcry_mpi_point_init (p);
95 39 : return p;
96 : }
97 :
98 :
99 : /* Release the point object P. P may be NULL. */
100 : void
101 4997 : _gcry_mpi_point_release (mpi_point_t p)
102 : {
103 4997 : if (p)
104 : {
105 30 : _gcry_mpi_point_free_parts (p);
106 30 : xfree (p);
107 : }
108 4997 : }
109 :
110 :
111 : /* Initialize the fields of a point object. gcry_mpi_point_free_parts
112 : may be used to release the fields. */
113 : void
114 12337 : _gcry_mpi_point_init (mpi_point_t p)
115 : {
116 12337 : p->x = mpi_new (0);
117 12337 : p->y = mpi_new (0);
118 12337 : p->z = mpi_new (0);
119 12337 : }
120 :
121 :
122 : /* Release the parts of a point object. */
123 : void
124 17383 : _gcry_mpi_point_free_parts (mpi_point_t p)
125 : {
126 17383 : mpi_free (p->x); p->x = NULL;
127 17383 : mpi_free (p->y); p->y = NULL;
128 17383 : mpi_free (p->z); p->z = NULL;
129 17383 : }
130 :
131 :
132 : /* Set the value from S into D. */
133 : static void
134 41870 : point_set (mpi_point_t d, mpi_point_t s)
135 : {
136 41870 : mpi_set (d->x, s->x);
137 41870 : mpi_set (d->y, s->y);
138 41870 : mpi_set (d->z, s->z);
139 41870 : }
140 :
141 :
142 : static void
143 6454 : point_resize (mpi_point_t p, mpi_ec_t ctx)
144 : {
145 : /*
146 : * For now, we allocate enough limbs for our EC computation of ec_*.
147 : * Once we will improve ec_* to be constant size (and constant
148 : * time), NLIMBS can be ctx->p->nlimbs.
149 : */
150 6454 : size_t nlimbs = 2*ctx->p->nlimbs+1;
151 :
152 6454 : mpi_resize (p->x, nlimbs);
153 6454 : if (ctx->model != MPI_EC_MONTGOMERY)
154 2298 : mpi_resize (p->y, nlimbs);
155 6454 : mpi_resize (p->z, nlimbs);
156 6454 : }
157 :
158 :
159 : static void
160 831586 : point_swap_cond (mpi_point_t d, mpi_point_t s, unsigned long swap,
161 : mpi_ec_t ctx)
162 : {
163 831586 : mpi_swap_cond (d->x, s->x, swap);
164 831586 : if (ctx->model != MPI_EC_MONTGOMERY)
165 300657 : mpi_swap_cond (d->y, s->y, swap);
166 831586 : mpi_swap_cond (d->z, s->z, swap);
167 831586 : }
168 :
169 :
170 : /* Set the projective coordinates from POINT into X, Y, and Z. If a
171 : coordinate is not required, X, Y, or Z may be passed as NULL. */
172 : void
173 6 : _gcry_mpi_point_get (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t z,
174 : mpi_point_t point)
175 : {
176 6 : if (x)
177 6 : mpi_set (x, point->x);
178 6 : if (y)
179 6 : mpi_set (y, point->y);
180 6 : if (z)
181 6 : mpi_set (z, point->z);
182 6 : }
183 :
184 :
185 : /* Set the projective coordinates from POINT into X, Y, and Z and
186 : release POINT. If a coordinate is not required, X, Y, or Z may be
187 : passed as NULL. */
188 : void
189 9 : _gcry_mpi_point_snatch_get (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t z,
190 : mpi_point_t point)
191 : {
192 9 : mpi_snatch (x, point->x);
193 9 : mpi_snatch (y, point->y);
194 9 : mpi_snatch (z, point->z);
195 9 : xfree (point);
196 9 : }
197 :
198 :
199 : /* Set the projective coordinates from X, Y, and Z into POINT. If a
200 : coordinate is given as NULL, the value 0 is stored into point. If
201 : POINT is given as NULL a new point object is allocated. Returns
202 : POINT or the newly allocated point object. */
203 : mpi_point_t
204 1009 : _gcry_mpi_point_set (mpi_point_t point,
205 : gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t z)
206 : {
207 1009 : if (!point)
208 2 : point = mpi_point_new (0);
209 :
210 1009 : if (x)
211 1009 : mpi_set (point->x, x);
212 : else
213 0 : mpi_clear (point->x);
214 1009 : if (y)
215 6 : mpi_set (point->y, y);
216 : else
217 1003 : mpi_clear (point->y);
218 1009 : if (z)
219 1009 : mpi_set (point->z, z);
220 : else
221 0 : mpi_clear (point->z);
222 :
223 1009 : return point;
224 : }
225 :
226 :
227 : /* Set the projective coordinates from X, Y, and Z into POINT. If a
228 : coordinate is given as NULL, the value 0 is stored into point. If
229 : POINT is given as NULL a new point object is allocated. The
230 : coordinates X, Y, and Z are released. Returns POINT or the newly
231 : allocated point object. */
232 : mpi_point_t
233 14 : _gcry_mpi_point_snatch_set (mpi_point_t point,
234 : gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t z)
235 : {
236 14 : if (!point)
237 12 : point = mpi_point_new (0);
238 :
239 14 : if (x)
240 14 : mpi_snatch (point->x, x);
241 : else
242 0 : mpi_clear (point->x);
243 14 : if (y)
244 14 : mpi_snatch (point->y, y);
245 : else
246 0 : mpi_clear (point->y);
247 14 : if (z)
248 14 : mpi_snatch (point->z, z);
249 : else
250 0 : mpi_clear (point->z);
251 :
252 14 : return point;
253 : }
254 :
255 :
256 : /* W = W mod P. */
257 : static void
258 37926174 : ec_mod (gcry_mpi_t w, mpi_ec_t ec)
259 : {
260 : if (0 && ec->dialect == ECC_DIALECT_ED25519)
261 : _gcry_mpi_ec_ed25519_mod (w);
262 37926174 : else if (ec->t.p_barrett)
263 0 : _gcry_mpi_mod_barrett (w, w, ec->t.p_barrett);
264 : else
265 37926174 : _gcry_mpi_mod (w, w, ec->p);
266 37926174 : }
267 :
268 : static void
269 8274119 : ec_addm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
270 : {
271 8274119 : mpi_add (w, u, v);
272 8274119 : ec_mod (w, ctx);
273 8274119 : }
274 :
275 : static void
276 11213607 : ec_subm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ec)
277 : {
278 11213607 : mpi_sub (w, u, v);
279 28009532 : while (w->sign)
280 5582318 : mpi_add (w, w, ec->p);
281 : /*ec_mod (w, ec);*/
282 11213607 : }
283 :
284 : static void
285 27659338 : ec_mulm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
286 : {
287 27659338 : mpi_mul (w, u, v);
288 27659338 : ec_mod (w, ctx);
289 27659338 : }
290 :
291 : /* W = 2 * U mod P. */
292 : static void
293 1992717 : ec_mul2 (gcry_mpi_t w, gcry_mpi_t u, mpi_ec_t ctx)
294 : {
295 1992717 : mpi_lshift (w, u, 1);
296 1992717 : ec_mod (w, ctx);
297 1992717 : }
298 :
299 : static void
300 266052 : ec_powm (gcry_mpi_t w, const gcry_mpi_t b, const gcry_mpi_t e,
301 : mpi_ec_t ctx)
302 : {
303 266052 : mpi_powm (w, b, e, ctx->p);
304 : /* _gcry_mpi_abs (w); */
305 266052 : }
306 :
307 :
308 : /* Shortcut for
309 : ec_powm (B, B, mpi_const (MPI_C_TWO), ctx);
310 : for easier optimization. */
311 : static void
312 9234287 : ec_pow2 (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx)
313 : {
314 : /* Using mpi_mul is slightly faster (at least on amd64). */
315 : /* mpi_powm (w, b, mpi_const (MPI_C_TWO), ctx->p); */
316 9234287 : ec_mulm (w, b, b, ctx);
317 9234287 : }
318 :
319 :
320 : /* Shortcut for
321 : ec_powm (B, B, mpi_const (MPI_C_THREE), ctx);
322 : for easier optimization. */
323 : static void
324 11 : ec_pow3 (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx)
325 : {
326 11 : mpi_powm (w, b, mpi_const (MPI_C_THREE), ctx->p);
327 11 : }
328 :
329 :
330 : static void
331 5961 : ec_invm (gcry_mpi_t x, gcry_mpi_t a, mpi_ec_t ctx)
332 : {
333 5961 : if (!mpi_invm (x, a, ctx->p))
334 : {
335 0 : log_error ("ec_invm: inverse does not exist:\n");
336 0 : log_mpidump (" a", a);
337 0 : log_mpidump (" p", ctx->p);
338 : }
339 5961 : }
340 :
341 :
342 : /* Force recomputation of all helper variables. */
343 : void
344 2474 : _gcry_mpi_ec_get_reset (mpi_ec_t ec)
345 : {
346 2474 : ec->t.valid.a_is_pminus3 = 0;
347 2474 : ec->t.valid.two_inv_p = 0;
348 2474 : }
349 :
350 :
351 : /* Accessor for helper variable. */
352 : static int
353 162500 : ec_get_a_is_pminus3 (mpi_ec_t ec)
354 : {
355 : gcry_mpi_t tmp;
356 :
357 162500 : if (!ec->t.valid.a_is_pminus3)
358 : {
359 339 : ec->t.valid.a_is_pminus3 = 1;
360 339 : tmp = mpi_alloc_like (ec->p);
361 339 : mpi_sub_ui (tmp, ec->p, 3);
362 339 : ec->t.a_is_pminus3 = !mpi_cmp (ec->a, tmp);
363 339 : mpi_free (tmp);
364 : }
365 :
366 162500 : return ec->t.a_is_pminus3;
367 : }
368 :
369 :
370 : /* Accessor for helper variable. */
371 : static gcry_mpi_t
372 77489 : ec_get_two_inv_p (mpi_ec_t ec)
373 : {
374 77489 : if (!ec->t.valid.two_inv_p)
375 : {
376 339 : ec->t.valid.two_inv_p = 1;
377 339 : if (!ec->t.two_inv_p)
378 339 : ec->t.two_inv_p = mpi_alloc (0);
379 339 : ec_invm (ec->t.two_inv_p, mpi_const (MPI_C_TWO), ec);
380 : }
381 77489 : return ec->t.two_inv_p;
382 : }
383 :
384 :
385 :
386 : /* This function initialized a context for elliptic curve based on the
387 : field GF(p). P is the prime specifying this field, A is the first
388 : coefficient. CTX is expected to be zeroized. */
389 : static void
390 2474 : ec_p_init (mpi_ec_t ctx, enum gcry_mpi_ec_models model,
391 : enum ecc_dialects dialect,
392 : int flags,
393 : gcry_mpi_t p, gcry_mpi_t a, gcry_mpi_t b)
394 : {
395 : int i;
396 : static int use_barrett;
397 :
398 2474 : if (!use_barrett)
399 : {
400 9 : if (getenv ("GCRYPT_BARRETT"))
401 0 : use_barrett = 1;
402 : else
403 9 : use_barrett = -1;
404 : }
405 :
406 : /* Fixme: Do we want to check some constraints? e.g. a < p */
407 :
408 2474 : ctx->model = model;
409 2474 : ctx->dialect = dialect;
410 2474 : ctx->flags = flags;
411 2474 : if (dialect == ECC_DIALECT_ED25519)
412 2105 : ctx->nbits = 256;
413 : else
414 369 : ctx->nbits = mpi_get_nbits (p);
415 2474 : ctx->p = mpi_copy (p);
416 2474 : ctx->a = mpi_copy (a);
417 2474 : ctx->b = mpi_copy (b);
418 :
419 2474 : ctx->t.p_barrett = use_barrett > 0? _gcry_mpi_barrett_init (ctx->p, 0):NULL;
420 :
421 2474 : _gcry_mpi_ec_get_reset (ctx);
422 :
423 : /* Allocate scratch variables. */
424 29688 : for (i=0; i< DIM(ctx->t.scratch); i++)
425 27214 : ctx->t.scratch[i] = mpi_alloc_like (ctx->p);
426 :
427 : /* Prepare for fast reduction. */
428 : /* FIXME: need a test for NIST values. However it does not gain us
429 : any real advantage, for 384 bits it is actually slower than using
430 : mpi_mulm. */
431 : /* ctx->nist_nbits = mpi_get_nbits (ctx->p); */
432 : /* if (ctx->nist_nbits == 192) */
433 : /* { */
434 : /* for (i=0; i < 4; i++) */
435 : /* ctx->s[i] = mpi_new (192); */
436 : /* ctx->c = mpi_new (192*2); */
437 : /* } */
438 : /* else if (ctx->nist_nbits == 384) */
439 : /* { */
440 : /* for (i=0; i < 10; i++) */
441 : /* ctx->s[i] = mpi_new (384); */
442 : /* ctx->c = mpi_new (384*2); */
443 : /* } */
444 2474 : }
445 :
446 :
447 : static void
448 2474 : ec_deinit (void *opaque)
449 : {
450 2474 : mpi_ec_t ctx = opaque;
451 : int i;
452 :
453 2474 : _gcry_mpi_barrett_free (ctx->t.p_barrett);
454 :
455 : /* Domain parameter. */
456 2474 : mpi_free (ctx->p);
457 2474 : mpi_free (ctx->a);
458 2474 : mpi_free (ctx->b);
459 2474 : _gcry_mpi_point_release (ctx->G);
460 2474 : mpi_free (ctx->n);
461 2474 : mpi_free (ctx->h);
462 :
463 : /* The key. */
464 2474 : _gcry_mpi_point_release (ctx->Q);
465 2474 : mpi_free (ctx->d);
466 :
467 : /* Private data of ec.c. */
468 2474 : mpi_free (ctx->t.two_inv_p);
469 :
470 29688 : for (i=0; i< DIM(ctx->t.scratch); i++)
471 27214 : mpi_free (ctx->t.scratch[i]);
472 :
473 : /* if (ctx->nist_nbits == 192) */
474 : /* { */
475 : /* for (i=0; i < 4; i++) */
476 : /* mpi_free (ctx->s[i]); */
477 : /* mpi_free (ctx->c); */
478 : /* } */
479 : /* else if (ctx->nist_nbits == 384) */
480 : /* { */
481 : /* for (i=0; i < 10; i++) */
482 : /* mpi_free (ctx->s[i]); */
483 : /* mpi_free (ctx->c); */
484 : /* } */
485 2474 : }
486 :
487 :
488 : /* This function returns a new context for elliptic curve based on the
489 : field GF(p). P is the prime specifying this field, A is the first
490 : coefficient, B is the second coefficient, and MODEL is the model
491 : for the curve. This function is only used within Libgcrypt and not
492 : part of the public API.
493 :
494 : This context needs to be released using _gcry_mpi_ec_free. */
495 : mpi_ec_t
496 2460 : _gcry_mpi_ec_p_internal_new (enum gcry_mpi_ec_models model,
497 : enum ecc_dialects dialect,
498 : int flags,
499 : gcry_mpi_t p, gcry_mpi_t a, gcry_mpi_t b)
500 : {
501 : mpi_ec_t ctx;
502 :
503 2460 : ctx = xcalloc (1, sizeof *ctx);
504 2460 : ec_p_init (ctx, model, dialect, flags, p, a, b);
505 :
506 2460 : return ctx;
507 : }
508 :
509 :
510 : /* This is a variant of _gcry_mpi_ec_p_internal_new which returns an
511 : public context and does some error checking on the supplied
512 : arguments. On success the new context is stored at R_CTX and 0 is
513 : returned; on error NULL is stored at R_CTX and an error code is
514 : returned.
515 :
516 : The context needs to be released using gcry_ctx_release. */
517 : gpg_err_code_t
518 16 : _gcry_mpi_ec_p_new (gcry_ctx_t *r_ctx,
519 : enum gcry_mpi_ec_models model,
520 : enum ecc_dialects dialect,
521 : int flags,
522 : gcry_mpi_t p, gcry_mpi_t a, gcry_mpi_t b)
523 : {
524 : gcry_ctx_t ctx;
525 : mpi_ec_t ec;
526 :
527 16 : *r_ctx = NULL;
528 16 : if (!p || !a)
529 2 : return GPG_ERR_EINVAL;
530 :
531 14 : ctx = _gcry_ctx_alloc (CONTEXT_TYPE_EC, sizeof *ec, ec_deinit);
532 14 : if (!ctx)
533 0 : return gpg_err_code_from_syserror ();
534 14 : ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
535 14 : ec_p_init (ec, model, dialect, flags, p, a, b);
536 :
537 14 : *r_ctx = ctx;
538 14 : return 0;
539 : }
540 :
541 :
542 : void
543 2460 : _gcry_mpi_ec_free (mpi_ec_t ctx)
544 : {
545 2460 : if (ctx)
546 : {
547 2460 : ec_deinit (ctx);
548 2460 : xfree (ctx);
549 : }
550 2460 : }
551 :
552 :
553 : gcry_mpi_t
554 53 : _gcry_mpi_ec_get_mpi (const char *name, gcry_ctx_t ctx, int copy)
555 : {
556 53 : mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
557 :
558 53 : return _gcry_ecc_get_mpi (name, ec, copy);
559 : }
560 :
561 :
562 : gcry_mpi_point_t
563 10 : _gcry_mpi_ec_get_point (const char *name, gcry_ctx_t ctx, int copy)
564 : {
565 10 : mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
566 :
567 : (void)copy; /* Not used. */
568 :
569 10 : return _gcry_ecc_get_point (name, ec);
570 : }
571 :
572 :
573 : gpg_err_code_t
574 8 : _gcry_mpi_ec_set_mpi (const char *name, gcry_mpi_t newvalue,
575 : gcry_ctx_t ctx)
576 : {
577 8 : mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
578 :
579 8 : return _gcry_ecc_set_mpi (name, newvalue, ec);
580 : }
581 :
582 :
583 : gpg_err_code_t
584 2 : _gcry_mpi_ec_set_point (const char *name, gcry_mpi_point_t newvalue,
585 : gcry_ctx_t ctx)
586 : {
587 2 : mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
588 :
589 2 : return _gcry_ecc_set_point (name, newvalue, ec);
590 : }
591 :
592 :
593 : /* Given an encoded point in the MPI VALUE and a context EC, decode
594 : * the point according to the context and store it in RESULT. On
595 : * error an error code is return but RESULT might have been changed.
596 : * If no context is given the function tries to decode VALUE by
597 : * assuming a 0x04 prefixed uncompressed encoding. */
598 : gpg_err_code_t
599 0 : _gcry_mpi_ec_decode_point (mpi_point_t result, gcry_mpi_t value, mpi_ec_t ec)
600 : {
601 : gcry_err_code_t rc;
602 :
603 0 : if (ec && ec->dialect == ECC_DIALECT_ED25519)
604 0 : rc = _gcry_ecc_eddsa_decodepoint (value, ec, result, NULL, NULL);
605 0 : else if (ec && ec->model == MPI_EC_MONTGOMERY)
606 0 : rc = _gcry_ecc_mont_decodepoint (value, ec, result);
607 : else
608 0 : rc = _gcry_ecc_os2ec (result, value);
609 :
610 0 : return rc;
611 : }
612 :
613 :
614 : /* Compute the affine coordinates from the projective coordinates in
615 : POINT. Set them into X and Y. If one coordinate is not required,
616 : X or Y may be passed as NULL. CTX is the usual context. Returns: 0
617 : on success or !0 if POINT is at infinity. */
618 : int
619 5615 : _gcry_mpi_ec_get_affine (gcry_mpi_t x, gcry_mpi_t y, mpi_point_t point,
620 : mpi_ec_t ctx)
621 : {
622 5615 : if (!mpi_cmp_ui (point->z, 0))
623 7 : return -1;
624 :
625 5608 : switch (ctx->model)
626 : {
627 : case MPI_EC_WEIERSTRASS: /* Using Jacobian coordinates. */
628 : {
629 : gcry_mpi_t z1, z2, z3;
630 :
631 377 : z1 = mpi_new (0);
632 377 : z2 = mpi_new (0);
633 377 : ec_invm (z1, point->z, ctx); /* z1 = z^(-1) mod p */
634 377 : ec_mulm (z2, z1, z1, ctx); /* z2 = z^(-2) mod p */
635 :
636 377 : if (x)
637 377 : ec_mulm (x, point->x, z2, ctx);
638 :
639 377 : if (y)
640 : {
641 63 : z3 = mpi_new (0);
642 63 : ec_mulm (z3, z2, z1, ctx); /* z3 = z^(-3) mod p */
643 63 : ec_mulm (y, point->y, z3, ctx);
644 63 : mpi_free (z3);
645 : }
646 :
647 377 : mpi_free (z2);
648 377 : mpi_free (z1);
649 : }
650 377 : return 0;
651 :
652 : case MPI_EC_MONTGOMERY:
653 : {
654 1032 : if (x)
655 1032 : mpi_set (x, point->x);
656 :
657 1032 : if (y)
658 : {
659 0 : log_fatal ("%s: Getting Y-coordinate on %s is not supported\n",
660 : "_gcry_mpi_ec_get_affine", "Montgomery");
661 : return -1;
662 : }
663 : }
664 1032 : return 0;
665 :
666 : case MPI_EC_EDWARDS:
667 : {
668 : gcry_mpi_t z;
669 :
670 4199 : z = mpi_new (0);
671 4199 : ec_invm (z, point->z, ctx);
672 :
673 4199 : if (x)
674 4199 : ec_mulm (x, point->x, z, ctx);
675 4199 : if (y)
676 4187 : ec_mulm (y, point->y, z, ctx);
677 :
678 4199 : _gcry_mpi_release (z);
679 : }
680 4199 : return 0;
681 :
682 : default:
683 0 : return -1;
684 : }
685 : }
686 :
687 :
688 :
689 : /* RESULT = 2 * POINT (Weierstrass version). */
690 : static void
691 162611 : dup_point_weierstrass (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
692 : {
693 : #define x3 (result->x)
694 : #define y3 (result->y)
695 : #define z3 (result->z)
696 : #define t1 (ctx->t.scratch[0])
697 : #define t2 (ctx->t.scratch[1])
698 : #define t3 (ctx->t.scratch[2])
699 : #define l1 (ctx->t.scratch[3])
700 : #define l2 (ctx->t.scratch[4])
701 : #define l3 (ctx->t.scratch[5])
702 :
703 162611 : if (!mpi_cmp_ui (point->y, 0) || !mpi_cmp_ui (point->z, 0))
704 : {
705 : /* P_y == 0 || P_z == 0 => [1:1:0] */
706 111 : mpi_set_ui (x3, 1);
707 111 : mpi_set_ui (y3, 1);
708 111 : mpi_set_ui (z3, 0);
709 : }
710 : else
711 : {
712 162500 : if (ec_get_a_is_pminus3 (ctx)) /* Use the faster case. */
713 : {
714 : /* L1 = 3(X - Z^2)(X + Z^2) */
715 : /* T1: used for Z^2. */
716 : /* T2: used for the right term. */
717 128937 : ec_pow2 (t1, point->z, ctx);
718 128937 : ec_subm (l1, point->x, t1, ctx);
719 128937 : ec_mulm (l1, l1, mpi_const (MPI_C_THREE), ctx);
720 128937 : ec_addm (t2, point->x, t1, ctx);
721 128937 : ec_mulm (l1, l1, t2, ctx);
722 : }
723 : else /* Standard case. */
724 : {
725 : /* L1 = 3X^2 + aZ^4 */
726 : /* T1: used for aZ^4. */
727 33563 : ec_pow2 (l1, point->x, ctx);
728 33563 : ec_mulm (l1, l1, mpi_const (MPI_C_THREE), ctx);
729 33563 : ec_powm (t1, point->z, mpi_const (MPI_C_FOUR), ctx);
730 33563 : ec_mulm (t1, t1, ctx->a, ctx);
731 33563 : ec_addm (l1, l1, t1, ctx);
732 : }
733 : /* Z3 = 2YZ */
734 162500 : ec_mulm (z3, point->y, point->z, ctx);
735 162500 : ec_mul2 (z3, z3, ctx);
736 :
737 : /* L2 = 4XY^2 */
738 : /* T2: used for Y2; required later. */
739 162500 : ec_pow2 (t2, point->y, ctx);
740 162500 : ec_mulm (l2, t2, point->x, ctx);
741 162500 : ec_mulm (l2, l2, mpi_const (MPI_C_FOUR), ctx);
742 :
743 : /* X3 = L1^2 - 2L2 */
744 : /* T1: used for L2^2. */
745 162500 : ec_pow2 (x3, l1, ctx);
746 162500 : ec_mul2 (t1, l2, ctx);
747 162500 : ec_subm (x3, x3, t1, ctx);
748 :
749 : /* L3 = 8Y^4 */
750 : /* T2: taken from above. */
751 162500 : ec_pow2 (t2, t2, ctx);
752 162500 : ec_mulm (l3, t2, mpi_const (MPI_C_EIGHT), ctx);
753 :
754 : /* Y3 = L1(L2 - X3) - L3 */
755 162500 : ec_subm (y3, l2, x3, ctx);
756 162500 : ec_mulm (y3, y3, l1, ctx);
757 162500 : ec_subm (y3, y3, l3, ctx);
758 : }
759 :
760 : #undef x3
761 : #undef y3
762 : #undef z3
763 : #undef t1
764 : #undef t2
765 : #undef t3
766 : #undef l1
767 : #undef l2
768 : #undef l3
769 162611 : }
770 :
771 :
772 : /* RESULT = 2 * POINT (Montgomery version). */
773 : static void
774 0 : dup_point_montgomery (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
775 : {
776 : (void)result;
777 : (void)point;
778 : (void)ctx;
779 0 : log_fatal ("%s: %s not yet supported\n",
780 : "_gcry_mpi_ec_dup_point", "Montgomery");
781 : }
782 :
783 :
784 : /* RESULT = 2 * POINT (Twisted Edwards version). */
785 : static void
786 1590228 : dup_point_edwards (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
787 : {
788 : #define X1 (point->x)
789 : #define Y1 (point->y)
790 : #define Z1 (point->z)
791 : #define X3 (result->x)
792 : #define Y3 (result->y)
793 : #define Z3 (result->z)
794 : #define B (ctx->t.scratch[0])
795 : #define C (ctx->t.scratch[1])
796 : #define D (ctx->t.scratch[2])
797 : #define E (ctx->t.scratch[3])
798 : #define F (ctx->t.scratch[4])
799 : #define H (ctx->t.scratch[5])
800 : #define J (ctx->t.scratch[6])
801 :
802 : /* Compute: (X_3 : Y_3 : Z_3) = 2( X_1 : Y_1 : Z_1 ) */
803 :
804 : /* B = (X_1 + Y_1)^2 */
805 1590228 : ec_addm (B, X1, Y1, ctx);
806 1590228 : ec_pow2 (B, B, ctx);
807 :
808 : /* C = X_1^2 */
809 : /* D = Y_1^2 */
810 1590228 : ec_pow2 (C, X1, ctx);
811 1590228 : ec_pow2 (D, Y1, ctx);
812 :
813 : /* E = aC */
814 1590228 : if (ctx->dialect == ECC_DIALECT_ED25519)
815 1590228 : mpi_sub (E, ctx->p, C);
816 : else
817 0 : ec_mulm (E, ctx->a, C, ctx);
818 :
819 : /* F = E + D */
820 1590228 : ec_addm (F, E, D, ctx);
821 :
822 : /* H = Z_1^2 */
823 1590228 : ec_pow2 (H, Z1, ctx);
824 :
825 : /* J = F - 2H */
826 1590228 : ec_mul2 (J, H, ctx);
827 1590228 : ec_subm (J, F, J, ctx);
828 :
829 : /* X_3 = (B - C - D) · J */
830 1590228 : ec_subm (X3, B, C, ctx);
831 1590228 : ec_subm (X3, X3, D, ctx);
832 1590228 : ec_mulm (X3, X3, J, ctx);
833 :
834 : /* Y_3 = F · (E - D) */
835 1590228 : ec_subm (Y3, E, D, ctx);
836 1590228 : ec_mulm (Y3, Y3, F, ctx);
837 :
838 : /* Z_3 = F · J */
839 1590228 : ec_mulm (Z3, F, J, ctx);
840 :
841 : #undef X1
842 : #undef Y1
843 : #undef Z1
844 : #undef X3
845 : #undef Y3
846 : #undef Z3
847 : #undef B
848 : #undef C
849 : #undef D
850 : #undef E
851 : #undef F
852 : #undef H
853 : #undef J
854 1590228 : }
855 :
856 :
857 : /* RESULT = 2 * POINT */
858 : void
859 1752839 : _gcry_mpi_ec_dup_point (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
860 : {
861 1752839 : switch (ctx->model)
862 : {
863 : case MPI_EC_WEIERSTRASS:
864 162611 : dup_point_weierstrass (result, point, ctx);
865 162611 : break;
866 : case MPI_EC_MONTGOMERY:
867 0 : dup_point_montgomery (result, point, ctx);
868 0 : break;
869 : case MPI_EC_EDWARDS:
870 1590228 : dup_point_edwards (result, point, ctx);
871 1590228 : break;
872 : }
873 1752839 : }
874 :
875 :
876 : /* RESULT = P1 + P2 (Weierstrass version).*/
877 : static void
878 77611 : add_points_weierstrass (mpi_point_t result,
879 : mpi_point_t p1, mpi_point_t p2,
880 : mpi_ec_t ctx)
881 : {
882 : #define x1 (p1->x )
883 : #define y1 (p1->y )
884 : #define z1 (p1->z )
885 : #define x2 (p2->x )
886 : #define y2 (p2->y )
887 : #define z2 (p2->z )
888 : #define x3 (result->x)
889 : #define y3 (result->y)
890 : #define z3 (result->z)
891 : #define l1 (ctx->t.scratch[0])
892 : #define l2 (ctx->t.scratch[1])
893 : #define l3 (ctx->t.scratch[2])
894 : #define l4 (ctx->t.scratch[3])
895 : #define l5 (ctx->t.scratch[4])
896 : #define l6 (ctx->t.scratch[5])
897 : #define l7 (ctx->t.scratch[6])
898 : #define l8 (ctx->t.scratch[7])
899 : #define l9 (ctx->t.scratch[8])
900 : #define t1 (ctx->t.scratch[9])
901 : #define t2 (ctx->t.scratch[10])
902 :
903 77611 : if ( (!mpi_cmp (x1, x2)) && (!mpi_cmp (y1, y2)) && (!mpi_cmp (z1, z2)) )
904 : {
905 : /* Same point; need to call the duplicate function. */
906 0 : _gcry_mpi_ec_dup_point (result, p1, ctx);
907 : }
908 77611 : else if (!mpi_cmp_ui (z1, 0))
909 : {
910 : /* P1 is at infinity. */
911 111 : mpi_set (x3, p2->x);
912 111 : mpi_set (y3, p2->y);
913 111 : mpi_set (z3, p2->z);
914 : }
915 77500 : else if (!mpi_cmp_ui (z2, 0))
916 : {
917 : /* P2 is at infinity. */
918 0 : mpi_set (x3, p1->x);
919 0 : mpi_set (y3, p1->y);
920 0 : mpi_set (z3, p1->z);
921 : }
922 : else
923 : {
924 77500 : int z1_is_one = !mpi_cmp_ui (z1, 1);
925 77500 : int z2_is_one = !mpi_cmp_ui (z2, 1);
926 :
927 : /* l1 = x1 z2^2 */
928 : /* l2 = x2 z1^2 */
929 77500 : if (z2_is_one)
930 77336 : mpi_set (l1, x1);
931 : else
932 : {
933 164 : ec_pow2 (l1, z2, ctx);
934 164 : ec_mulm (l1, l1, x1, ctx);
935 : }
936 77500 : if (z1_is_one)
937 0 : mpi_set (l2, x2);
938 : else
939 : {
940 77500 : ec_pow2 (l2, z1, ctx);
941 77500 : ec_mulm (l2, l2, x2, ctx);
942 : }
943 : /* l3 = l1 - l2 */
944 77500 : ec_subm (l3, l1, l2, ctx);
945 : /* l4 = y1 z2^3 */
946 77500 : ec_powm (l4, z2, mpi_const (MPI_C_THREE), ctx);
947 77500 : ec_mulm (l4, l4, y1, ctx);
948 : /* l5 = y2 z1^3 */
949 77500 : ec_powm (l5, z1, mpi_const (MPI_C_THREE), ctx);
950 77500 : ec_mulm (l5, l5, y2, ctx);
951 : /* l6 = l4 - l5 */
952 77500 : ec_subm (l6, l4, l5, ctx);
953 :
954 77500 : if (!mpi_cmp_ui (l3, 0))
955 : {
956 11 : if (!mpi_cmp_ui (l6, 0))
957 : {
958 : /* P1 and P2 are the same - use duplicate function. */
959 0 : _gcry_mpi_ec_dup_point (result, p1, ctx);
960 : }
961 : else
962 : {
963 : /* P1 is the inverse of P2. */
964 11 : mpi_set_ui (x3, 1);
965 11 : mpi_set_ui (y3, 1);
966 11 : mpi_set_ui (z3, 0);
967 : }
968 : }
969 : else
970 : {
971 : /* l7 = l1 + l2 */
972 77489 : ec_addm (l7, l1, l2, ctx);
973 : /* l8 = l4 + l5 */
974 77489 : ec_addm (l8, l4, l5, ctx);
975 : /* z3 = z1 z2 l3 */
976 77489 : ec_mulm (z3, z1, z2, ctx);
977 77489 : ec_mulm (z3, z3, l3, ctx);
978 : /* x3 = l6^2 - l7 l3^2 */
979 77489 : ec_pow2 (t1, l6, ctx);
980 77489 : ec_pow2 (t2, l3, ctx);
981 77489 : ec_mulm (t2, t2, l7, ctx);
982 77489 : ec_subm (x3, t1, t2, ctx);
983 : /* l9 = l7 l3^2 - 2 x3 */
984 77489 : ec_mul2 (t1, x3, ctx);
985 77489 : ec_subm (l9, t2, t1, ctx);
986 : /* y3 = (l9 l6 - l8 l3^3)/2 */
987 77489 : ec_mulm (l9, l9, l6, ctx);
988 77489 : ec_powm (t1, l3, mpi_const (MPI_C_THREE), ctx); /* fixme: Use saved value*/
989 77489 : ec_mulm (t1, t1, l8, ctx);
990 77489 : ec_subm (y3, l9, t1, ctx);
991 77489 : ec_mulm (y3, y3, ec_get_two_inv_p (ctx), ctx);
992 : }
993 : }
994 :
995 : #undef x1
996 : #undef y1
997 : #undef z1
998 : #undef x2
999 : #undef y2
1000 : #undef z2
1001 : #undef x3
1002 : #undef y3
1003 : #undef z3
1004 : #undef l1
1005 : #undef l2
1006 : #undef l3
1007 : #undef l4
1008 : #undef l5
1009 : #undef l6
1010 : #undef l7
1011 : #undef l8
1012 : #undef l9
1013 : #undef t1
1014 : #undef t2
1015 77611 : }
1016 :
1017 :
1018 : /* RESULT = P1 + P2 (Montgomery version).*/
1019 : static void
1020 0 : add_points_montgomery (mpi_point_t result,
1021 : mpi_point_t p1, mpi_point_t p2,
1022 : mpi_ec_t ctx)
1023 : {
1024 : (void)result;
1025 : (void)p1;
1026 : (void)p2;
1027 : (void)ctx;
1028 0 : log_fatal ("%s: %s not yet supported\n",
1029 : "_gcry_mpi_ec_add_points", "Montgomery");
1030 : }
1031 :
1032 :
1033 : /* RESULT = P1 + P2 (Twisted Edwards version).*/
1034 : static void
1035 928832 : add_points_edwards (mpi_point_t result,
1036 : mpi_point_t p1, mpi_point_t p2,
1037 : mpi_ec_t ctx)
1038 : {
1039 : #define X1 (p1->x)
1040 : #define Y1 (p1->y)
1041 : #define Z1 (p1->z)
1042 : #define X2 (p2->x)
1043 : #define Y2 (p2->y)
1044 : #define Z2 (p2->z)
1045 : #define X3 (result->x)
1046 : #define Y3 (result->y)
1047 : #define Z3 (result->z)
1048 : #define A (ctx->t.scratch[0])
1049 : #define B (ctx->t.scratch[1])
1050 : #define C (ctx->t.scratch[2])
1051 : #define D (ctx->t.scratch[3])
1052 : #define E (ctx->t.scratch[4])
1053 : #define F (ctx->t.scratch[5])
1054 : #define G (ctx->t.scratch[6])
1055 : #define tmp (ctx->t.scratch[7])
1056 :
1057 : /* Compute: (X_3 : Y_3 : Z_3) = (X_1 : Y_1 : Z_1) + (X_2 : Y_2 : Z_3) */
1058 :
1059 : /* A = Z1 · Z2 */
1060 928832 : ec_mulm (A, Z1, Z2, ctx);
1061 :
1062 : /* B = A^2 */
1063 928832 : ec_pow2 (B, A, ctx);
1064 :
1065 : /* C = X1 · X2 */
1066 928832 : ec_mulm (C, X1, X2, ctx);
1067 :
1068 : /* D = Y1 · Y2 */
1069 928832 : ec_mulm (D, Y1, Y2, ctx);
1070 :
1071 : /* E = d · C · D */
1072 928832 : ec_mulm (E, ctx->b, C, ctx);
1073 928832 : ec_mulm (E, E, D, ctx);
1074 :
1075 : /* F = B - E */
1076 928832 : ec_subm (F, B, E, ctx);
1077 :
1078 : /* G = B + E */
1079 928832 : ec_addm (G, B, E, ctx);
1080 :
1081 : /* X_3 = A · F · ((X_1 + Y_1) · (X_2 + Y_2) - C - D) */
1082 928832 : ec_addm (tmp, X1, Y1, ctx);
1083 928832 : ec_addm (X3, X2, Y2, ctx);
1084 928832 : ec_mulm (X3, X3, tmp, ctx);
1085 928832 : ec_subm (X3, X3, C, ctx);
1086 928832 : ec_subm (X3, X3, D, ctx);
1087 928832 : ec_mulm (X3, X3, F, ctx);
1088 928832 : ec_mulm (X3, X3, A, ctx);
1089 :
1090 : /* Y_3 = A · G · (D - aC) */
1091 928832 : if (ctx->dialect == ECC_DIALECT_ED25519)
1092 : {
1093 928832 : ec_addm (Y3, D, C, ctx);
1094 : }
1095 : else
1096 : {
1097 0 : ec_mulm (Y3, ctx->a, C, ctx);
1098 0 : ec_subm (Y3, D, Y3, ctx);
1099 : }
1100 928832 : ec_mulm (Y3, Y3, G, ctx);
1101 928832 : ec_mulm (Y3, Y3, A, ctx);
1102 :
1103 : /* Z_3 = F · G */
1104 928832 : ec_mulm (Z3, F, G, ctx);
1105 :
1106 :
1107 : #undef X1
1108 : #undef Y1
1109 : #undef Z1
1110 : #undef X2
1111 : #undef Y2
1112 : #undef Z2
1113 : #undef X3
1114 : #undef Y3
1115 : #undef Z3
1116 : #undef A
1117 : #undef B
1118 : #undef C
1119 : #undef D
1120 : #undef E
1121 : #undef F
1122 : #undef G
1123 : #undef tmp
1124 928832 : }
1125 :
1126 :
1127 : /* Compute a step of Montgomery Ladder (only use X and Z in the point).
1128 : Inputs: P1, P2, and x-coordinate of DIF = P1 - P1.
1129 : Outputs: PRD = 2 * P1 and SUM = P1 + P2. */
1130 : static void
1131 264945 : montgomery_ladder (mpi_point_t prd, mpi_point_t sum,
1132 : mpi_point_t p1, mpi_point_t p2, gcry_mpi_t dif_x,
1133 : mpi_ec_t ctx)
1134 : {
1135 264945 : ec_addm (sum->x, p2->x, p2->z, ctx);
1136 264945 : ec_subm (p2->z, p2->x, p2->z, ctx);
1137 264945 : ec_addm (prd->x, p1->x, p1->z, ctx);
1138 264945 : ec_subm (p1->z, p1->x, p1->z, ctx);
1139 264945 : ec_mulm (p2->x, p1->z, sum->x, ctx);
1140 264945 : ec_mulm (p2->z, prd->x, p2->z, ctx);
1141 264945 : ec_pow2 (p1->x, prd->x, ctx);
1142 264945 : ec_pow2 (p1->z, p1->z, ctx);
1143 264945 : ec_addm (sum->x, p2->x, p2->z, ctx);
1144 264945 : ec_subm (p2->z, p2->x, p2->z, ctx);
1145 264945 : ec_mulm (prd->x, p1->x, p1->z, ctx);
1146 264945 : ec_subm (p1->z, p1->x, p1->z, ctx);
1147 264945 : ec_pow2 (sum->x, sum->x, ctx);
1148 264945 : ec_pow2 (sum->z, p2->z, ctx);
1149 264945 : ec_mulm (prd->z, p1->z, ctx->a, ctx); /* CTX->A: (a-2)/4 */
1150 264945 : ec_mulm (sum->z, sum->z, dif_x, ctx);
1151 264945 : ec_addm (prd->z, p1->x, prd->z, ctx);
1152 264945 : ec_mulm (prd->z, prd->z, p1->z, ctx);
1153 264945 : }
1154 :
1155 :
1156 : /* RESULT = P1 + P2 */
1157 : void
1158 1006443 : _gcry_mpi_ec_add_points (mpi_point_t result,
1159 : mpi_point_t p1, mpi_point_t p2,
1160 : mpi_ec_t ctx)
1161 : {
1162 1006443 : switch (ctx->model)
1163 : {
1164 : case MPI_EC_WEIERSTRASS:
1165 77611 : add_points_weierstrass (result, p1, p2, ctx);
1166 77611 : break;
1167 : case MPI_EC_MONTGOMERY:
1168 0 : add_points_montgomery (result, p1, p2, ctx);
1169 0 : break;
1170 : case MPI_EC_EDWARDS:
1171 928832 : add_points_edwards (result, p1, p2, ctx);
1172 928832 : break;
1173 : }
1174 1006443 : }
1175 :
1176 :
1177 : /* RESULT = P1 - P2 (Weierstrass version).*/
1178 : static void
1179 0 : sub_points_weierstrass (mpi_point_t result,
1180 : mpi_point_t p1, mpi_point_t p2,
1181 : mpi_ec_t ctx)
1182 : {
1183 : (void)result;
1184 : (void)p1;
1185 : (void)p2;
1186 : (void)ctx;
1187 0 : log_fatal ("%s: %s not yet supported\n",
1188 : "_gcry_mpi_ec_sub_points", "Weierstrass");
1189 : }
1190 :
1191 :
1192 : /* RESULT = P1 - P2 (Montgomery version).*/
1193 : static void
1194 0 : sub_points_montgomery (mpi_point_t result,
1195 : mpi_point_t p1, mpi_point_t p2,
1196 : mpi_ec_t ctx)
1197 : {
1198 : (void)result;
1199 : (void)p1;
1200 : (void)p2;
1201 : (void)ctx;
1202 0 : log_fatal ("%s: %s not yet supported\n",
1203 : "_gcry_mpi_ec_sub_points", "Montgomery");
1204 : }
1205 :
1206 :
1207 : /* RESULT = P1 - P2 (Twisted Edwards version).*/
1208 : static void
1209 0 : sub_points_edwards (mpi_point_t result,
1210 : mpi_point_t p1, mpi_point_t p2,
1211 : mpi_ec_t ctx)
1212 : {
1213 0 : mpi_point_t p2i = _gcry_mpi_point_new (0);
1214 0 : point_set (p2i, p2);
1215 0 : mpi_sub (p2i->x, ctx->p, p2i->x);
1216 0 : add_points_edwards (result, p1, p2i, ctx);
1217 0 : _gcry_mpi_point_release (p2i);
1218 0 : }
1219 :
1220 :
1221 : /* RESULT = P1 - P2 */
1222 : void
1223 0 : _gcry_mpi_ec_sub_points (mpi_point_t result,
1224 : mpi_point_t p1, mpi_point_t p2,
1225 : mpi_ec_t ctx)
1226 : {
1227 0 : switch (ctx->model)
1228 : {
1229 : case MPI_EC_WEIERSTRASS:
1230 0 : sub_points_weierstrass (result, p1, p2, ctx);
1231 0 : break;
1232 : case MPI_EC_MONTGOMERY:
1233 0 : sub_points_montgomery (result, p1, p2, ctx);
1234 0 : break;
1235 : case MPI_EC_EDWARDS:
1236 0 : sub_points_edwards (result, p1, p2, ctx);
1237 0 : break;
1238 : }
1239 0 : }
1240 :
1241 :
1242 : /* Scalar point multiplication - the main function for ECC. If takes
1243 : an integer SCALAR and a POINT as well as the usual context CTX.
1244 : RESULT will be set to the resulting point. */
1245 : void
1246 5726 : _gcry_mpi_ec_mul_point (mpi_point_t result,
1247 : gcry_mpi_t scalar, mpi_point_t point,
1248 : mpi_ec_t ctx)
1249 : {
1250 : gcry_mpi_t x1, y1, z1, k, h, yy;
1251 : unsigned int i, loops;
1252 : mpi_point_struct p1, p2, p1inv;
1253 :
1254 5726 : if (ctx->model == MPI_EC_EDWARDS
1255 1555 : || (ctx->model == MPI_EC_WEIERSTRASS
1256 516 : && mpi_is_secure (scalar)))
1257 : {
1258 : /* Simple left to right binary method. GECC Algorithm 3.27 */
1259 : unsigned int nbits;
1260 : int j;
1261 :
1262 4282 : nbits = mpi_get_nbits (scalar);
1263 4282 : if (ctx->model == MPI_EC_WEIERSTRASS)
1264 : {
1265 111 : mpi_set_ui (result->x, 1);
1266 111 : mpi_set_ui (result->y, 1);
1267 111 : mpi_set_ui (result->z, 0);
1268 : }
1269 : else
1270 : {
1271 4171 : mpi_set_ui (result->x, 0);
1272 4171 : mpi_set_ui (result->y, 1);
1273 4171 : mpi_set_ui (result->z, 1);
1274 : }
1275 :
1276 4282 : if (mpi_is_secure (scalar))
1277 1149 : {
1278 : /* If SCALAR is in secure memory we assume that it is the
1279 : secret key we use constant time operation. */
1280 : mpi_point_struct tmppnt;
1281 :
1282 1149 : point_init (&tmppnt);
1283 1149 : point_resize (result, ctx);
1284 1149 : point_resize (&tmppnt, ctx);
1285 301806 : for (j=nbits-1; j >= 0; j--)
1286 : {
1287 300657 : _gcry_mpi_ec_dup_point (result, result, ctx);
1288 300657 : _gcry_mpi_ec_add_points (&tmppnt, result, point, ctx);
1289 300657 : point_swap_cond (result, &tmppnt, mpi_test_bit (scalar, j), ctx);
1290 : }
1291 1149 : point_free (&tmppnt);
1292 : }
1293 : else
1294 : {
1295 1328686 : for (j=nbits-1; j >= 0; j--)
1296 : {
1297 1325553 : _gcry_mpi_ec_dup_point (result, result, ctx);
1298 1325553 : if (mpi_test_bit (scalar, j))
1299 663114 : _gcry_mpi_ec_add_points (result, result, point, ctx);
1300 : }
1301 : }
1302 9603 : return;
1303 : }
1304 1444 : else if (ctx->model == MPI_EC_MONTGOMERY)
1305 : {
1306 : unsigned int nbits;
1307 : int j;
1308 : mpi_point_struct p1_, p2_;
1309 : mpi_point_t q1, q2, prd, sum;
1310 : unsigned long sw;
1311 :
1312 : /* Compute scalar point multiplication with Montgomery Ladder.
1313 : Note that we don't use Y-coordinate in the points at all.
1314 : RESULT->Y will be filled by zero. */
1315 :
1316 1039 : nbits = mpi_get_nbits (scalar);
1317 1039 : point_init (&p1);
1318 1039 : point_init (&p2);
1319 1039 : point_init (&p1_);
1320 1039 : point_init (&p2_);
1321 1039 : mpi_set_ui (p1.x, 1);
1322 1039 : mpi_free (p2.x);
1323 1039 : p2.x = mpi_copy (point->x);
1324 1039 : mpi_set_ui (p2.z, 1);
1325 :
1326 1039 : point_resize (&p1, ctx);
1327 1039 : point_resize (&p2, ctx);
1328 1039 : point_resize (&p1_, ctx);
1329 1039 : point_resize (&p2_, ctx);
1330 :
1331 1039 : q1 = &p1;
1332 1039 : q2 = &p2;
1333 1039 : prd = &p1_;
1334 1039 : sum = &p2_;
1335 :
1336 265984 : for (j=nbits-1; j >= 0; j--)
1337 : {
1338 : mpi_point_t t;
1339 :
1340 264945 : sw = mpi_test_bit (scalar, j);
1341 264945 : point_swap_cond (q1, q2, sw, ctx);
1342 264945 : montgomery_ladder (prd, sum, q1, q2, point->x, ctx);
1343 264945 : point_swap_cond (prd, sum, sw, ctx);
1344 264945 : t = q1; q1 = prd; prd = t;
1345 264945 : t = q2; q2 = sum; sum = t;
1346 : }
1347 :
1348 1039 : mpi_clear (result->y);
1349 1039 : sw = (nbits & 1);
1350 1039 : point_swap_cond (&p1, &p1_, sw, ctx);
1351 :
1352 1039 : if (p1.z->nlimbs == 0)
1353 : {
1354 7 : mpi_set_ui (result->x, 1);
1355 7 : mpi_set_ui (result->z, 0);
1356 : }
1357 : else
1358 : {
1359 1032 : z1 = mpi_new (0);
1360 1032 : ec_invm (z1, p1.z, ctx);
1361 1032 : ec_mulm (result->x, p1.x, z1, ctx);
1362 1032 : mpi_set_ui (result->z, 1);
1363 1032 : mpi_free (z1);
1364 : }
1365 :
1366 1039 : point_free (&p1);
1367 1039 : point_free (&p2);
1368 1039 : point_free (&p1_);
1369 1039 : point_free (&p2_);
1370 1039 : return;
1371 : }
1372 :
1373 405 : x1 = mpi_alloc_like (ctx->p);
1374 405 : y1 = mpi_alloc_like (ctx->p);
1375 405 : h = mpi_alloc_like (ctx->p);
1376 405 : k = mpi_copy (scalar);
1377 405 : yy = mpi_copy (point->y);
1378 :
1379 405 : if ( mpi_has_sign (k) )
1380 : {
1381 0 : k->sign = 0;
1382 0 : ec_invm (yy, yy, ctx);
1383 : }
1384 :
1385 405 : if (!mpi_cmp_ui (point->z, 1))
1386 : {
1387 398 : mpi_set (x1, point->x);
1388 398 : mpi_set (y1, yy);
1389 : }
1390 : else
1391 : {
1392 : gcry_mpi_t z2, z3;
1393 :
1394 7 : z2 = mpi_alloc_like (ctx->p);
1395 7 : z3 = mpi_alloc_like (ctx->p);
1396 7 : ec_mulm (z2, point->z, point->z, ctx);
1397 7 : ec_mulm (z3, point->z, z2, ctx);
1398 7 : ec_invm (z2, z2, ctx);
1399 7 : ec_mulm (x1, point->x, z2, ctx);
1400 7 : ec_invm (z3, z3, ctx);
1401 7 : ec_mulm (y1, yy, z3, ctx);
1402 7 : mpi_free (z2);
1403 7 : mpi_free (z3);
1404 : }
1405 405 : z1 = mpi_copy (mpi_const (MPI_C_ONE));
1406 :
1407 405 : mpi_mul (h, k, mpi_const (MPI_C_THREE)); /* h = 3k */
1408 405 : loops = mpi_get_nbits (h);
1409 405 : if (loops < 2)
1410 : {
1411 : /* If SCALAR is zero, the above mpi_mul sets H to zero and thus
1412 : LOOPs will be zero. To avoid an underflow of I in the main
1413 : loop we set LOOP to 2 and the result to (0,0,0). */
1414 1 : loops = 2;
1415 1 : mpi_clear (result->x);
1416 1 : mpi_clear (result->y);
1417 1 : mpi_clear (result->z);
1418 : }
1419 : else
1420 : {
1421 404 : mpi_set (result->x, point->x);
1422 404 : mpi_set (result->y, yy);
1423 404 : mpi_set (result->z, point->z);
1424 : }
1425 405 : mpi_free (yy); yy = NULL;
1426 :
1427 405 : p1.x = x1; x1 = NULL;
1428 405 : p1.y = y1; y1 = NULL;
1429 405 : p1.z = z1; z1 = NULL;
1430 405 : point_init (&p2);
1431 405 : point_init (&p1inv);
1432 :
1433 : /* Invert point: y = p - y mod p */
1434 405 : point_set (&p1inv, &p1);
1435 405 : ec_subm (p1inv.y, ctx->p, p1inv.y, ctx);
1436 :
1437 127034 : for (i=loops-2; i > 0; i--)
1438 : {
1439 126629 : _gcry_mpi_ec_dup_point (result, result, ctx);
1440 126629 : if (mpi_test_bit (h, i) == 1 && mpi_test_bit (k, i) == 0)
1441 : {
1442 20320 : point_set (&p2, result);
1443 20320 : _gcry_mpi_ec_add_points (result, &p2, &p1, ctx);
1444 : }
1445 126629 : if (mpi_test_bit (h, i) == 0 && mpi_test_bit (k, i) == 1)
1446 : {
1447 21145 : point_set (&p2, result);
1448 21145 : _gcry_mpi_ec_add_points (result, &p2, &p1inv, ctx);
1449 : }
1450 : }
1451 :
1452 405 : point_free (&p1);
1453 405 : point_free (&p2);
1454 405 : point_free (&p1inv);
1455 405 : mpi_free (h);
1456 405 : mpi_free (k);
1457 : }
1458 :
1459 :
1460 : /* Return true if POINT is on the curve described by CTX. */
1461 : int
1462 1066 : _gcry_mpi_ec_curve_point (gcry_mpi_point_t point, mpi_ec_t ctx)
1463 : {
1464 1066 : int res = 0;
1465 : gcry_mpi_t x, y, w;
1466 :
1467 1066 : x = mpi_new (0);
1468 1066 : y = mpi_new (0);
1469 1066 : w = mpi_new (0);
1470 :
1471 1066 : switch (ctx->model)
1472 : {
1473 : case MPI_EC_WEIERSTRASS:
1474 : {
1475 : gcry_mpi_t xxx;
1476 :
1477 11 : if (_gcry_mpi_ec_get_affine (x, y, point, ctx))
1478 0 : goto leave;
1479 :
1480 11 : xxx = mpi_new (0);
1481 :
1482 : /* y^2 == x^3 + a·x + b */
1483 11 : ec_pow2 (y, y, ctx);
1484 :
1485 11 : ec_pow3 (xxx, x, ctx);
1486 11 : ec_mulm (w, ctx->a, x, ctx);
1487 11 : ec_addm (w, w, ctx->b, ctx);
1488 11 : ec_addm (w, w, xxx, ctx);
1489 :
1490 11 : if (!mpi_cmp (y, w))
1491 11 : res = 1;
1492 :
1493 11 : _gcry_mpi_release (xxx);
1494 : }
1495 11 : break;
1496 : case MPI_EC_MONTGOMERY:
1497 : {
1498 : #define xx y
1499 : /* With Montgomery curve, only X-coordinate is valid. */
1500 0 : if (_gcry_mpi_ec_get_affine (x, NULL, point, ctx))
1501 0 : goto leave;
1502 :
1503 : /* The equation is: b * y^2 == x^3 + a · x^2 + x */
1504 : /* We check if right hand is quadratic residue or not by
1505 : Euler's criterion. */
1506 : /* CTX->A has (a-2)/4 and CTX->B has b^-1 */
1507 0 : ec_mulm (w, ctx->a, mpi_const (MPI_C_FOUR), ctx);
1508 0 : ec_addm (w, w, mpi_const (MPI_C_TWO), ctx);
1509 0 : ec_mulm (w, w, x, ctx);
1510 0 : ec_pow2 (xx, x, ctx);
1511 0 : ec_addm (w, w, xx, ctx);
1512 0 : ec_addm (w, w, mpi_const (MPI_C_ONE), ctx);
1513 0 : ec_mulm (w, w, x, ctx);
1514 0 : ec_mulm (w, w, ctx->b, ctx);
1515 : #undef xx
1516 : /* Compute Euler's criterion: w^(p-1)/2 */
1517 : #define p_minus1 y
1518 0 : ec_subm (p_minus1, ctx->p, mpi_const (MPI_C_ONE), ctx);
1519 0 : mpi_rshift (p_minus1, p_minus1, 1);
1520 0 : ec_powm (w, w, p_minus1, ctx);
1521 :
1522 0 : res = !mpi_cmp_ui (w, 1);
1523 : #undef p_minus1
1524 : }
1525 0 : break;
1526 : case MPI_EC_EDWARDS:
1527 : {
1528 1055 : if (_gcry_mpi_ec_get_affine (x, y, point, ctx))
1529 0 : goto leave;
1530 :
1531 : /* a · x^2 + y^2 - 1 - b · x^2 · y^2 == 0 */
1532 1055 : ec_pow2 (x, x, ctx);
1533 1055 : ec_pow2 (y, y, ctx);
1534 1055 : if (ctx->dialect == ECC_DIALECT_ED25519)
1535 1055 : mpi_sub (w, ctx->p, x);
1536 : else
1537 0 : ec_mulm (w, ctx->a, x, ctx);
1538 1055 : ec_addm (w, w, y, ctx);
1539 1055 : ec_subm (w, w, mpi_const (MPI_C_ONE), ctx);
1540 1055 : ec_mulm (x, x, y, ctx);
1541 1055 : ec_mulm (x, x, ctx->b, ctx);
1542 1055 : ec_subm (w, w, x, ctx);
1543 1055 : if (!mpi_cmp_ui (w, 0))
1544 1055 : res = 1;
1545 : }
1546 1055 : break;
1547 : }
1548 :
1549 : leave:
1550 1066 : _gcry_mpi_release (w);
1551 1066 : _gcry_mpi_release (x);
1552 1066 : _gcry_mpi_release (y);
1553 :
1554 1066 : return res;
1555 : }
|
