LCOV - code coverage report
Current view: top level - mpi - ec.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 518 617 84.0 %
Date: 2016-12-01 18:32:04 Functions: 42 50 84.0 %

          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       41737 : point_set (mpi_point_t d, mpi_point_t s)
     135             : {
     136       41737 :   mpi_set (d->x, s->x);
     137       41737 :   mpi_set (d->y, s->y);
     138       41737 :   mpi_set (d->z, s->z);
     139       41737 : }
     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      831546 : point_swap_cond (mpi_point_t d, mpi_point_t s, unsigned long swap,
     161             :                  mpi_ec_t ctx)
     162             : {
     163      831546 :   mpi_swap_cond (d->x, s->x, swap);
     164      831546 :   if (ctx->model != MPI_EC_MONTGOMERY)
     165      300617 :     mpi_swap_cond (d->y, s->y, swap);
     166      831546 :   mpi_swap_cond (d->z, s->z, swap);
     167      831546 : }
     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        1012 : _gcry_mpi_point_set (mpi_point_t point,
     205             :                      gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t z)
     206             : {
     207        1012 :   if (!point)
     208           2 :     point = mpi_point_new (0);
     209             : 
     210        1012 :   if (x)
     211        1012 :     mpi_set (point->x, x);
     212             :   else
     213           0 :     mpi_clear (point->x);
     214        1012 :   if (y)
     215           9 :     mpi_set (point->y, y);
     216             :   else
     217        1003 :     mpi_clear (point->y);
     218        1012 :   if (z)
     219        1012 :     mpi_set (point->z, z);
     220             :   else
     221           0 :     mpi_clear (point->z);
     222             : 
     223        1012 :   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    37921162 : 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    37921162 :   else if (ec->t.p_barrett)
     263           0 :     _gcry_mpi_mod_barrett (w, w, ec->t.p_barrett);
     264             :   else
     265    37921162 :     _gcry_mpi_mod (w, w, ec->p);
     266    37921162 : }
     267             : 
     268             : static void
     269     8273156 : ec_addm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
     270             : {
     271     8273156 :   mpi_add (w, u, v);
     272     8273156 :   ec_mod (w, ctx);
     273     8273156 : }
     274             : 
     275             : static void
     276    11212392 : ec_subm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ec)
     277             : {
     278    11212392 :   mpi_sub (w, u, v);
     279    28004125 :   while (w->sign)
     280     5579341 :     mpi_add (w, w, ec->p);
     281             :   /*ec_mod (w, ec);*/
     282    11212392 : }
     283             : 
     284             : static void
     285    27655432 : ec_mulm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
     286             : {
     287    27655432 :   mpi_mul (w, u, v);
     288    27655432 :   ec_mod (w, ctx);
     289    27655432 : }
     290             : 
     291             : /* W = 2 * U mod P.  */
     292             : static void
     293     1992574 : ec_mul2 (gcry_mpi_t w, gcry_mpi_t u, mpi_ec_t ctx)
     294             : {
     295     1992574 :   mpi_lshift (w, u, 1);
     296     1992574 :   ec_mod (w, ctx);
     297     1992574 : }
     298             : 
     299             : static void
     300      265478 : ec_powm (gcry_mpi_t w, const gcry_mpi_t b, const gcry_mpi_t e,
     301             :          mpi_ec_t ctx)
     302             : {
     303      265478 :   mpi_powm (w, b, e, ctx->p);
     304             :   /* _gcry_mpi_abs (w); */
     305      265478 : }
     306             : 
     307             : 
     308             : /* Shortcut for
     309             :      ec_powm (B, B, mpi_const (MPI_C_TWO), ctx);
     310             :    for easier optimization.  */
     311             : static void
     312     9233712 : 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     9233712 :   ec_mulm (w, b, b, ctx);
     317     9233712 : }
     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        5955 : ec_invm (gcry_mpi_t x, gcry_mpi_t a, mpi_ec_t ctx)
     332             : {
     333        5955 :   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        5955 : }
     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      162503 : ec_get_a_is_pminus3 (mpi_ec_t ec)
     354             : {
     355             :   gcry_mpi_t tmp;
     356             : 
     357      162503 :   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      162503 :   return ec->t.a_is_pminus3;
     367             : }
     368             : 
     369             : 
     370             : /* Accessor for helper variable.  */
     371             : static gcry_mpi_t
     372       77313 : ec_get_two_inv_p (mpi_ec_t ec)
     373             : {
     374       77313 :   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       77313 :   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      162614 : 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      162614 :   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      162503 :       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      128986 :           ec_pow2 (t1, point->z, ctx);
     718      128986 :           ec_subm (l1, point->x, t1, ctx);
     719      128986 :           ec_mulm (l1, l1, mpi_const (MPI_C_THREE), ctx);
     720      128986 :           ec_addm (t2, point->x, t1, ctx);
     721      128986 :           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       33517 :           ec_pow2 (l1, point->x, ctx);
     728       33517 :           ec_mulm (l1, l1, mpi_const (MPI_C_THREE), ctx);
     729       33517 :           ec_powm (t1, point->z, mpi_const (MPI_C_FOUR), ctx);
     730       33517 :           ec_mulm (t1, t1, ctx->a, ctx);
     731       33517 :           ec_addm (l1, l1, t1, ctx);
     732             :         }
     733             :       /* Z3 = 2YZ */
     734      162503 :       ec_mulm (z3, point->y, point->z, ctx);
     735      162503 :       ec_mul2 (z3, z3, ctx);
     736             : 
     737             :       /* L2 = 4XY^2 */
     738             :       /*                              T2: used for Y2; required later. */
     739      162503 :       ec_pow2 (t2, point->y, ctx);
     740      162503 :       ec_mulm (l2, t2, point->x, ctx);
     741      162503 :       ec_mulm (l2, l2, mpi_const (MPI_C_FOUR), ctx);
     742             : 
     743             :       /* X3 = L1^2 - 2L2 */
     744             :       /*                              T1: used for L2^2. */
     745      162503 :       ec_pow2 (x3, l1, ctx);
     746      162503 :       ec_mul2 (t1, l2, ctx);
     747      162503 :       ec_subm (x3, x3, t1, ctx);
     748             : 
     749             :       /* L3 = 8Y^4 */
     750             :       /*                              T2: taken from above. */
     751      162503 :       ec_pow2 (t2, t2, ctx);
     752      162503 :       ec_mulm (l3, t2, mpi_const (MPI_C_EIGHT), ctx);
     753             : 
     754             :       /* Y3 = L1(L2 - X3) - L3 */
     755      162503 :       ec_subm (y3, l2, x3, ctx);
     756      162503 :       ec_mulm (y3, y3, l1, ctx);
     757      162503 :       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      162614 : }
     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     1590255 : 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     1590255 :   ec_addm (B, X1, Y1, ctx);
     806     1590255 :   ec_pow2 (B, B, ctx);
     807             : 
     808             :   /* C = X_1^2 */
     809             :   /* D = Y_1^2 */
     810     1590255 :   ec_pow2 (C, X1, ctx);
     811     1590255 :   ec_pow2 (D, Y1, ctx);
     812             : 
     813             :   /* E = aC */
     814     1590255 :   if (ctx->dialect == ECC_DIALECT_ED25519)
     815     1590255 :     mpi_sub (E, ctx->p, C);
     816             :   else
     817           0 :     ec_mulm (E, ctx->a, C, ctx);
     818             : 
     819             :   /* F = E + D */
     820     1590255 :   ec_addm (F, E, D, ctx);
     821             : 
     822             :   /* H = Z_1^2 */
     823     1590255 :   ec_pow2 (H, Z1, ctx);
     824             : 
     825             :   /* J = F - 2H */
     826     1590255 :   ec_mul2 (J, H, ctx);
     827     1590255 :   ec_subm (J, F, J, ctx);
     828             : 
     829             :   /* X_3 = (B - C - D) · J */
     830     1590255 :   ec_subm (X3, B, C, ctx);
     831     1590255 :   ec_subm (X3, X3, D, ctx);
     832     1590255 :   ec_mulm (X3, X3, J, ctx);
     833             : 
     834             :   /* Y_3 = F · (E - D) */
     835     1590255 :   ec_subm (Y3, E, D, ctx);
     836     1590255 :   ec_mulm (Y3, Y3, F, ctx);
     837             : 
     838             :   /* Z_3 = F · J */
     839     1590255 :   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     1590255 : }
     855             : 
     856             : 
     857             : /*  RESULT = 2 * POINT  */
     858             : void
     859     1752869 : _gcry_mpi_ec_dup_point (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
     860             : {
     861     1752869 :   switch (ctx->model)
     862             :     {
     863             :     case MPI_EC_WEIERSTRASS:
     864      162614 :       dup_point_weierstrass (result, point, ctx);
     865      162614 :       break;
     866             :     case MPI_EC_MONTGOMERY:
     867           0 :       dup_point_montgomery (result, point, ctx);
     868           0 :       break;
     869             :     case MPI_EC_EDWARDS:
     870     1590255 :       dup_point_edwards (result, point, ctx);
     871     1590255 :       break;
     872             :     }
     873     1752869 : }
     874             : 
     875             : 
     876             : /* RESULT = P1 + P2  (Weierstrass version).*/
     877             : static void
     878       77435 : 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       77435 :   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       77435 :   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       77324 :   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       77324 :       int z1_is_one = !mpi_cmp_ui (z1, 1);
     925       77324 :       int z2_is_one = !mpi_cmp_ui (z2, 1);
     926             : 
     927             :       /* l1 = x1 z2^2  */
     928             :       /* l2 = x2 z1^2  */
     929       77324 :       if (z2_is_one)
     930       77160 :         mpi_set (l1, x1);
     931             :       else
     932             :         {
     933         164 :           ec_pow2 (l1, z2, ctx);
     934         164 :           ec_mulm (l1, l1, x1, ctx);
     935             :         }
     936       77324 :       if (z1_is_one)
     937           0 :         mpi_set (l2, x2);
     938             :       else
     939             :         {
     940       77324 :           ec_pow2 (l2, z1, ctx);
     941       77324 :           ec_mulm (l2, l2, x2, ctx);
     942             :         }
     943             :       /* l3 = l1 - l2 */
     944       77324 :       ec_subm (l3, l1, l2, ctx);
     945             :       /* l4 = y1 z2^3  */
     946       77324 :       ec_powm (l4, z2, mpi_const (MPI_C_THREE), ctx);
     947       77324 :       ec_mulm (l4, l4, y1, ctx);
     948             :       /* l5 = y2 z1^3  */
     949       77324 :       ec_powm (l5, z1, mpi_const (MPI_C_THREE), ctx);
     950       77324 :       ec_mulm (l5, l5, y2, ctx);
     951             :       /* l6 = l4 - l5  */
     952       77324 :       ec_subm (l6, l4, l5, ctx);
     953             : 
     954       77324 :       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       77313 :           ec_addm (l7, l1, l2, ctx);
     973             :           /* l8 = l4 + l5  */
     974       77313 :           ec_addm (l8, l4, l5, ctx);
     975             :           /* z3 = z1 z2 l3  */
     976       77313 :           ec_mulm (z3, z1, z2, ctx);
     977       77313 :           ec_mulm (z3, z3, l3, ctx);
     978             :           /* x3 = l6^2 - l7 l3^2  */
     979       77313 :           ec_pow2 (t1, l6, ctx);
     980       77313 :           ec_pow2 (t2, l3, ctx);
     981       77313 :           ec_mulm (t2, t2, l7, ctx);
     982       77313 :           ec_subm (x3, t1, t2, ctx);
     983             :           /* l9 = l7 l3^2 - 2 x3  */
     984       77313 :           ec_mul2 (t1, x3, ctx);
     985       77313 :           ec_subm (l9, t2, t1, ctx);
     986             :           /* y3 = (l9 l6 - l8 l3^3)/2  */
     987       77313 :           ec_mulm (l9, l9, l6, ctx);
     988       77313 :           ec_powm (t1, l3, mpi_const (MPI_C_THREE), ctx); /* fixme: Use saved value*/
     989       77313 :           ec_mulm (t1, t1, l8, ctx);
     990       77313 :           ec_subm (y3, l9, t1, ctx);
     991       77313 :           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       77435 : }
    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      928665 : 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      928665 :   ec_mulm (A, Z1, Z2, ctx);
    1061             : 
    1062             :   /* B = A^2 */
    1063      928665 :   ec_pow2 (B, A, ctx);
    1064             : 
    1065             :   /* C = X1 · X2 */
    1066      928665 :   ec_mulm (C, X1, X2, ctx);
    1067             : 
    1068             :   /* D = Y1 · Y2 */
    1069      928665 :   ec_mulm (D, Y1, Y2, ctx);
    1070             : 
    1071             :   /* E = d · C · D */
    1072      928665 :   ec_mulm (E, ctx->b, C, ctx);
    1073      928665 :   ec_mulm (E, E, D, ctx);
    1074             : 
    1075             :   /* F = B - E */
    1076      928665 :   ec_subm (F, B, E, ctx);
    1077             : 
    1078             :   /* G = B + E */
    1079      928665 :   ec_addm (G, B, E, ctx);
    1080             : 
    1081             :   /* X_3 = A · F · ((X_1 + Y_1) · (X_2 + Y_2) - C - D) */
    1082      928665 :   ec_addm (tmp, X1, Y1, ctx);
    1083      928665 :   ec_addm (X3, X2, Y2, ctx);
    1084      928665 :   ec_mulm (X3, X3, tmp, ctx);
    1085      928665 :   ec_subm (X3, X3, C, ctx);
    1086      928665 :   ec_subm (X3, X3, D, ctx);
    1087      928665 :   ec_mulm (X3, X3, F, ctx);
    1088      928665 :   ec_mulm (X3, X3, A, ctx);
    1089             : 
    1090             :   /* Y_3 = A · G · (D - aC) */
    1091      928665 :   if (ctx->dialect == ECC_DIALECT_ED25519)
    1092             :     {
    1093      928665 :       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      928665 :   ec_mulm (Y3, Y3, G, ctx);
    1101      928665 :   ec_mulm (Y3, Y3, A, ctx);
    1102             : 
    1103             :   /* Z_3 = F · G */
    1104      928665 :   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      928665 : }
    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     1006100 : _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     1006100 :   switch (ctx->model)
    1163             :     {
    1164             :     case MPI_EC_WEIERSTRASS:
    1165       77435 :       add_points_weierstrass (result, p1, p2, ctx);
    1166       77435 :       break;
    1167             :     case MPI_EC_MONTGOMERY:
    1168           0 :       add_points_montgomery (result, p1, p2, ctx);
    1169           0 :       break;
    1170             :     case MPI_EC_EDWARDS:
    1171      928665 :       add_points_edwards (result, p1, p2, ctx);
    1172      928665 :       break;
    1173             :     }
    1174     1006100 : }
    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      301766 :           for (j=nbits-1; j >= 0; j--)
    1286             :             {
    1287      300617 :               _gcry_mpi_ec_dup_point (result, result, ctx);
    1288      300617 :               _gcry_mpi_ec_add_points (&tmppnt, result, point, ctx);
    1289      300617 :               point_swap_cond (result, &tmppnt, mpi_test_bit (scalar, j), ctx);
    1290             :             }
    1291        1149 :           point_free (&tmppnt);
    1292             :         }
    1293             :       else
    1294             :         {
    1295     1328710 :           for (j=nbits-1; j >= 0; j--)
    1296             :             {
    1297     1325577 :               _gcry_mpi_ec_dup_point (result, result, ctx);
    1298     1325577 :               if (mpi_test_bit (scalar, j))
    1299      662944 :                 _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         401 :       mpi_set (x1, point->x);
    1388         401 :       mpi_set (y1, yy);
    1389             :     }
    1390             :   else
    1391             :     {
    1392             :       gcry_mpi_t z2, z3;
    1393             : 
    1394           4 :       z2 = mpi_alloc_like (ctx->p);
    1395           4 :       z3 = mpi_alloc_like (ctx->p);
    1396           4 :       ec_mulm (z2, point->z, point->z, ctx);
    1397           4 :       ec_mulm (z3, point->z, z2, ctx);
    1398           4 :       ec_invm (z2, z2, ctx);
    1399           4 :       ec_mulm (x1, point->x, z2, ctx);
    1400           4 :       ec_invm (z3, z3, ctx);
    1401           4 :       ec_mulm (y1, yy, z3, ctx);
    1402           4 :       mpi_free (z2);
    1403           4 :       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      127080 :   for (i=loops-2; i > 0; i--)
    1438             :     {
    1439      126675 :       _gcry_mpi_ec_dup_point (result, result, ctx);
    1440      126675 :       if (mpi_test_bit (h, i) == 1 && mpi_test_bit (k, i) == 0)
    1441             :         {
    1442       20563 :           point_set (&p2, result);
    1443       20563 :           _gcry_mpi_ec_add_points (result, &p2, &p1, ctx);
    1444             :         }
    1445      126675 :       if (mpi_test_bit (h, i) == 0 && mpi_test_bit (k, i) == 1)
    1446             :         {
    1447       20769 :           point_set (&p2, result);
    1448       20769 :           _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             : }

Generated by: LCOV version 1.11