Coverage Report

Created: 2024-11-21 07:03

/src/libgcrypt/mpi/ec.c
Line
Count
Source (jump to first uncovered line)
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
extern void reverse_buffer (unsigned char *buffer, unsigned int length);
34
35
3.76k
#define point_init(a)  _gcry_mpi_point_init ((a))
36
5.49k
#define point_free(a)  _gcry_mpi_point_free_parts ((a))
37
38
39
/* Print a point using the log functions.  If CTX is not NULL affine
40
   coordinates will be printed.  */
41
void
42
_gcry_mpi_point_log (const char *name, mpi_point_t point, mpi_ec_t ctx)
43
0
{
44
0
  gcry_mpi_t x, y;
45
0
  char buf[100];
46
47
0
  if (!point)
48
0
    {
49
0
      snprintf (buf, sizeof buf - 1, "%s.*", name);
50
0
      log_mpidump (buf, NULL);
51
0
      return;
52
0
    }
53
0
  snprintf (buf, sizeof buf - 1, "%s.X", name);
54
55
0
  if (ctx)
56
0
    {
57
0
      x = mpi_new (0);
58
0
      y = mpi_new (0);
59
0
    }
60
0
  if (!ctx || _gcry_mpi_ec_get_affine (x, y, point, ctx))
61
0
    {
62
0
      log_mpidump (buf, point->x);
63
0
      buf[strlen(buf)-1] = 'Y';
64
0
      log_mpidump (buf, point->y);
65
0
      buf[strlen(buf)-1] = 'Z';
66
0
      log_mpidump (buf, point->z);
67
0
    }
68
0
  else
69
0
    {
70
0
      buf[strlen(buf)-1] = 'x';
71
0
      log_mpidump (buf, x);
72
0
      buf[strlen(buf)-1] = 'y';
73
0
      log_mpidump (buf, y);
74
75
0
    }
76
0
  if (ctx)
77
0
    {
78
0
      _gcry_mpi_release (x);
79
0
      _gcry_mpi_release (y);
80
0
    }
81
0
}
82
83
84
/* Create a new point option.  NBITS gives the size in bits of one
85
   coordinate; it is only used to pre-allocate some resources and
86
   might also be passed as 0 to use a default value.  */
87
mpi_point_t
88
_gcry_mpi_point_new (unsigned int nbits)
89
7.33k
{
90
7.33k
  mpi_point_t p;
91
92
7.33k
  (void)nbits;  /* Currently not used.  */
93
94
7.33k
  p = xmalloc (sizeof *p);
95
7.33k
  _gcry_mpi_point_init (p);
96
7.33k
  return p;
97
7.33k
}
98
99
100
/* Release the point object P.  P may be NULL. */
101
void
102
_gcry_mpi_point_release (mpi_point_t p)
103
13.3k
{
104
13.3k
  if (p)
105
7.33k
    {
106
7.33k
      _gcry_mpi_point_free_parts (p);
107
7.33k
      xfree (p);
108
7.33k
    }
109
13.3k
}
110
111
112
/* Initialize the fields of a point object.  gcry_mpi_point_free_parts
113
   may be used to release the fields.  */
114
void
115
_gcry_mpi_point_init (mpi_point_t p)
116
11.7k
{
117
11.7k
  p->x = mpi_new (0);
118
11.7k
  p->y = mpi_new (0);
119
11.7k
  p->z = mpi_new (0);
120
11.7k
}
121
122
123
/* Release the parts of a point object. */
124
void
125
_gcry_mpi_point_free_parts (mpi_point_t p)
126
16.5k
{
127
16.5k
  mpi_free (p->x); p->x = NULL;
128
16.5k
  mpi_free (p->y); p->y = NULL;
129
16.5k
  mpi_free (p->z); p->z = NULL;
130
16.5k
}
131
132
133
/* Set the value from S into D.  */
134
static void
135
point_set (mpi_point_t d, mpi_point_t s)
136
326k
{
137
326k
  mpi_set (d->x, s->x);
138
326k
  mpi_set (d->y, s->y);
139
326k
  mpi_set (d->z, s->z);
140
326k
}
141
142
143
/* Return a copy of POINT. */
144
gcry_mpi_point_t
145
_gcry_mpi_point_copy (gcry_mpi_point_t point)
146
0
{
147
0
  mpi_point_t newpoint;
148
149
0
  newpoint = _gcry_mpi_point_new (0);
150
0
  if (point)
151
0
    point_set (newpoint, point);
152
153
0
  return newpoint;
154
0
}
155
156
157
void
158
_gcry_mpi_ec_point_resize (mpi_point_t p, mpi_ec_t ctx)
159
622
{
160
622
  size_t nlimbs = ctx->p->nlimbs;
161
162
622
  mpi_resize (p->x, nlimbs);
163
622
  p->x->nlimbs = nlimbs;
164
622
  mpi_resize (p->z, nlimbs);
165
622
  p->z->nlimbs = nlimbs;
166
167
622
  if (ctx->model != MPI_EC_MONTGOMERY)
168
622
    {
169
622
      mpi_resize (p->y, nlimbs);
170
622
      p->y->nlimbs = nlimbs;
171
622
    }
172
622
}
173
174
175
static void
176
point_swap_cond (mpi_point_t d, mpi_point_t s, unsigned long swap,
177
                 mpi_ec_t ctx)
178
91.0k
{
179
91.0k
  mpi_swap_cond (d->x, s->x, swap);
180
91.0k
  if (ctx->model != MPI_EC_MONTGOMERY)
181
91.0k
    mpi_swap_cond (d->y, s->y, swap);
182
91.0k
  mpi_swap_cond (d->z, s->z, swap);
183
91.0k
}
184
185
186
/* Set the projective coordinates from POINT into X, Y, and Z.  If a
187
   coordinate is not required, X, Y, or Z may be passed as NULL.  */
188
void
189
_gcry_mpi_point_get (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t z,
190
                     mpi_point_t point)
191
0
{
192
0
  if (x)
193
0
    mpi_set (x, point->x);
194
0
  if (y)
195
0
    mpi_set (y, point->y);
196
0
  if (z)
197
0
    mpi_set (z, point->z);
198
0
}
199
200
201
/* Set the projective coordinates from POINT into X, Y, and Z and
202
   release POINT.  If a coordinate is not required, X, Y, or Z may be
203
   passed as NULL.  */
204
void
205
_gcry_mpi_point_snatch_get (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t z,
206
                            mpi_point_t point)
207
0
{
208
0
  mpi_snatch (x, point->x);
209
0
  mpi_snatch (y, point->y);
210
0
  mpi_snatch (z, point->z);
211
0
  xfree (point);
212
0
}
213
214
215
/* Set the projective coordinates from X, Y, and Z into POINT.  If a
216
   coordinate is given as NULL, the value 0 is stored into point.  If
217
   POINT is given as NULL a new point object is allocated.  Returns
218
   POINT or the newly allocated point object. */
219
mpi_point_t
220
_gcry_mpi_point_set (mpi_point_t point,
221
                     gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t z)
222
1.57k
{
223
1.57k
  if (!point)
224
0
    point = mpi_point_new (0);
225
226
1.57k
  if (x)
227
1.57k
    mpi_set (point->x, x);
228
0
  else
229
0
    mpi_clear (point->x);
230
1.57k
  if (y)
231
1.57k
    mpi_set (point->y, y);
232
0
  else
233
0
    mpi_clear (point->y);
234
1.57k
  if (z)
235
1.57k
    mpi_set (point->z, z);
236
0
  else
237
0
    mpi_clear (point->z);
238
239
1.57k
  return point;
240
1.57k
}
241
242
243
/* Set the projective coordinates from X, Y, and Z into POINT.  If a
244
   coordinate is given as NULL, the value 0 is stored into point.  If
245
   POINT is given as NULL a new point object is allocated.  The
246
   coordinates X, Y, and Z are released.  Returns POINT or the newly
247
   allocated point object. */
248
mpi_point_t
249
_gcry_mpi_point_snatch_set (mpi_point_t point,
250
                            gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t z)
251
2.99k
{
252
2.99k
  if (!point)
253
2.99k
    point = mpi_point_new (0);
254
255
2.99k
  if (x)
256
2.99k
    mpi_snatch (point->x, x);
257
0
  else
258
0
    mpi_clear (point->x);
259
2.99k
  if (y)
260
2.99k
    mpi_snatch (point->y, y);
261
0
  else
262
0
    mpi_clear (point->y);
263
2.99k
  if (z)
264
2.99k
    mpi_snatch (point->z, z);
265
0
  else
266
0
    mpi_clear (point->z);
267
268
2.99k
  return point;
269
2.99k
}
270
271
272
/* W = W mod P.  */
273
static void
274
ec_mod (gcry_mpi_t w, mpi_ec_t ec)
275
3.51M
{
276
3.51M
  if (0 && ec->dialect == ECC_DIALECT_ED25519)
277
0
    _gcry_mpi_ec_ed25519_mod (w);
278
3.51M
  else if (ec->t.p_barrett)
279
0
    _gcry_mpi_mod_barrett (w, w, ec->t.p_barrett);
280
3.51M
  else
281
3.51M
    _gcry_mpi_mod (w, w, ec->p);
282
3.51M
}
283
284
static void
285
ec_addm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
286
1.95M
{
287
1.95M
  mpi_add (w, u, v);
288
1.95M
  ctx->mod (w, ctx);
289
1.95M
}
290
291
static void
292
ec_subm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ec)
293
6.19M
{
294
6.19M
  mpi_sub (w, u, v);
295
9.28M
  while (w->sign)
296
3.09M
    mpi_add (w, w, ec->p);
297
  /*ctx->mod (w, ec);*/
298
6.19M
}
299
300
static void
301
ec_mulm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
302
17.3M
{
303
17.3M
  mpi_mul (w, u, v);
304
17.3M
  ctx->mod (w, ctx);
305
17.3M
}
306
307
/* W = 2 * U mod P.  */
308
static void
309
ec_mul2 (gcry_mpi_t w, gcry_mpi_t u, mpi_ec_t ctx)
310
2.65M
{
311
2.65M
  mpi_lshift (w, u, 1);
312
2.65M
  ctx->mod (w, ctx);
313
2.65M
}
314
315
static void
316
ec_powm (gcry_mpi_t w, const gcry_mpi_t b, const gcry_mpi_t e,
317
         mpi_ec_t ctx)
318
1.61M
{
319
1.61M
  mpi_powm (w, b, e, ctx->p);
320
  /* _gcry_mpi_abs (w); */
321
1.61M
}
322
323
324
/* Shortcut for
325
     ec_powm (B, B, mpi_const (MPI_C_TWO), ctx);
326
   for easier optimization.  */
327
static void
328
ec_pow2 (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx)
329
5.73M
{
330
  /* Using mpi_mul is slightly faster (at least on amd64).  */
331
  /* mpi_powm (w, b, mpi_const (MPI_C_TWO), ctx->p); */
332
5.73M
  ec_mulm (w, b, b, ctx);
333
5.73M
}
334
335
336
/* Shortcut for
337
     ec_powm (B, B, mpi_const (MPI_C_THREE), ctx);
338
   for easier optimization.  */
339
static void
340
ec_pow3 (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx)
341
1.42k
{
342
1.42k
  mpi_powm (w, b, mpi_const (MPI_C_THREE), ctx->p);
343
1.42k
}
344
345
346
static void
347
ec_invm (gcry_mpi_t x, gcry_mpi_t a, mpi_ec_t ctx)
348
4.51k
{
349
4.51k
  if (!mpi_invm (x, a, ctx->p))
350
0
    {
351
0
      log_error ("ec_invm: inverse does not exist:\n");
352
0
      log_mpidump ("  a", a);
353
0
      log_mpidump ("  p", ctx->p);
354
0
    }
355
4.51k
}
356

357
/* Routines for 2^255 - 19.  */
358
359
0
#define LIMB_SIZE_25519 ((256+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB)
360
361
static void
362
ec_addm_25519 (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
363
0
{
364
0
  mpi_ptr_t wp, up, vp;
365
0
  mpi_size_t wsize = LIMB_SIZE_25519;
366
0
  mpi_limb_t n[LIMB_SIZE_25519];
367
0
  mpi_limb_t borrow;
368
369
0
  if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
370
0
    log_bug ("addm_25519: different sizes\n");
371
372
0
  up = u->d;
373
0
  vp = v->d;
374
0
  wp = w->d;
375
376
0
  _gcry_mpih_add_n (wp, up, vp, wsize);
377
0
  borrow = _gcry_mpih_sub_n (n, wp, ctx->p->d, wsize);
378
0
  mpih_set_cond (wp, n, wsize, mpih_limb_is_zero (borrow));
379
0
  wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));
380
0
}
381
382
static void
383
ec_subm_25519 (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
384
0
{
385
0
  mpi_ptr_t wp, up, vp;
386
0
  mpi_size_t wsize = LIMB_SIZE_25519;
387
0
  mpi_limb_t n[LIMB_SIZE_25519];
388
0
  mpi_limb_t borrow;
389
390
0
  if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
391
0
    log_bug ("subm_25519: different sizes\n");
392
393
0
  up = u->d;
394
0
  vp = v->d;
395
0
  wp = w->d;
396
397
0
  borrow = _gcry_mpih_sub_n (wp, up, vp, wsize);
398
0
  _gcry_mpih_add_n (n, wp, ctx->p->d, wsize);
399
0
  mpih_set_cond (wp, n, wsize, mpih_limb_is_not_zero (borrow));
400
0
  wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));
401
0
}
402
403
static void
404
ec_mulm_25519 (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
405
0
{
406
0
  mpi_ptr_t wp, up, vp;
407
0
  mpi_size_t wsize = LIMB_SIZE_25519;
408
0
  mpi_limb_t n[LIMB_SIZE_25519*2];
409
0
  mpi_limb_t cy;
410
0
  int msb;
411
412
0
  (void)ctx;
413
0
  if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
414
0
    log_bug ("mulm_25519: different sizes\n");
415
416
0
  up = u->d;
417
0
  vp = v->d;
418
0
  wp = w->d;
419
420
0
  _gcry_mpih_mul_n (n, up, vp, wsize);
421
0
  memcpy (wp, n, wsize * BYTES_PER_MPI_LIMB);
422
0
  wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));
423
424
0
  _gcry_mpih_rshift (n, n+LIMB_SIZE_25519-1, LIMB_SIZE_25519+1,
425
0
         (255 % BITS_PER_MPI_LIMB));
426
427
0
  cy = _gcry_mpih_addmul_1 (wp, n, wsize, 19);
428
429
0
  memset (n, 0, wsize * BYTES_PER_MPI_LIMB);
430
0
  msb = (wp[LIMB_SIZE_25519-1] >> (255 % BITS_PER_MPI_LIMB));
431
0
  n[0] = (cy * 2 + msb) * 19;
432
0
  wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));
433
0
  _gcry_mpih_add_n (wp, wp, n, wsize);
434
435
0
  cy = _gcry_mpih_sub_n (n, wp, ctx->p->d, wsize);
436
0
  mpih_set_cond (wp, n, wsize, mpih_limb_is_zero (cy));
437
0
}
438
439
static void
440
ec_mul2_25519 (gcry_mpi_t w, gcry_mpi_t u, mpi_ec_t ctx)
441
0
{
442
0
  ec_addm_25519 (w, u, u, ctx);
443
0
}
444
445
static void
446
ec_pow2_25519 (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx)
447
0
{
448
0
  ec_mulm_25519 (w, b, b, ctx);
449
0
}
450

451
/* Routines for 2^448 - 2^224 - 1.  */
452
453
0
#define LIMB_SIZE_448 ((448+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB)
454
0
#define LIMB_SIZE_HALF_448 ((LIMB_SIZE_448+1)/2)
455
456
static void
457
ec_addm_448 (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
458
0
{
459
0
  mpi_ptr_t wp, up, vp;
460
0
  mpi_size_t wsize = LIMB_SIZE_448;
461
0
  mpi_limb_t n[LIMB_SIZE_448];
462
0
  mpi_limb_t cy;
463
464
0
  if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
465
0
    log_bug ("addm_448: different sizes\n");
466
467
0
  up = u->d;
468
0
  vp = v->d;
469
0
  wp = w->d;
470
471
0
  cy = _gcry_mpih_add_n (wp, up, vp, wsize);
472
0
  _gcry_mpih_sub_n (n, wp, ctx->p->d, wsize);
473
0
  mpih_set_cond (wp, n, wsize, mpih_limb_is_not_zero (cy));
474
0
}
475
476
static void
477
ec_subm_448 (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
478
0
{
479
0
  mpi_ptr_t wp, up, vp;
480
0
  mpi_size_t wsize = LIMB_SIZE_448;
481
0
  mpi_limb_t n[LIMB_SIZE_448];
482
0
  mpi_limb_t borrow;
483
484
0
  if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
485
0
    log_bug ("subm_448: different sizes\n");
486
487
0
  up = u->d;
488
0
  vp = v->d;
489
0
  wp = w->d;
490
491
0
  borrow = _gcry_mpih_sub_n (wp, up, vp, wsize);
492
0
  _gcry_mpih_add_n (n, wp, ctx->p->d, wsize);
493
0
  mpih_set_cond (wp, n, wsize, mpih_limb_is_not_zero (borrow));
494
0
}
495
496
static void
497
ec_mulm_448 (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
498
0
{
499
0
  mpi_ptr_t wp, up, vp;
500
0
  mpi_size_t wsize = LIMB_SIZE_448;
501
0
  mpi_limb_t n[LIMB_SIZE_448*2];
502
0
  mpi_limb_t a2[LIMB_SIZE_HALF_448];
503
0
  mpi_limb_t a3[LIMB_SIZE_HALF_448];
504
0
  mpi_limb_t b0[LIMB_SIZE_HALF_448];
505
0
  mpi_limb_t b1[LIMB_SIZE_HALF_448];
506
0
  mpi_limb_t cy;
507
508
0
  if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
509
0
    log_bug ("mulm_448: different sizes\n");
510
511
0
  up = u->d;
512
0
  vp = v->d;
513
0
  wp = w->d;
514
515
0
  _gcry_mpih_mul_n (n, up, vp, wsize);
516
517
0
  memcpy (b0, n, LIMB_SIZE_HALF_448 * BYTES_PER_MPI_LIMB);
518
0
  memcpy (a2, n + wsize, LIMB_SIZE_HALF_448 * BYTES_PER_MPI_LIMB);
519
520
0
#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
521
0
  b0[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL<<32)-1;
522
0
  a2[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL<<32)-1;
523
0
  _gcry_mpih_rshift (b1, n + wsize/2, LIMB_SIZE_HALF_448, 32);
524
0
  _gcry_mpih_rshift (a3, n + wsize + wsize/2, LIMB_SIZE_HALF_448, 32);
525
#else
526
  memcpy (b1, n + wsize/2, LIMB_SIZE_HALF_448 * BYTES_PER_MPI_LIMB);
527
  memcpy (a3, n + wsize + wsize/2, LIMB_SIZE_HALF_448 * BYTES_PER_MPI_LIMB);
528
#endif
529
530
0
  cy = _gcry_mpih_add_n (b0, b0, a2, LIMB_SIZE_HALF_448);
531
0
  cy += _gcry_mpih_add_n (wp, b0, a3, LIMB_SIZE_HALF_448);
532
0
#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
533
0
  cy = wp[LIMB_SIZE_HALF_448-1] >> 32;
534
0
  wp[LIMB_SIZE_HALF_448-1] &= (((mpi_limb_t)1UL <<32)-1);
535
0
#endif
536
0
  memset (b0, 0, LIMB_SIZE_HALF_448 * BYTES_PER_MPI_LIMB);
537
0
  b0[0] = cy;
538
539
0
  cy = _gcry_mpih_add_n (b1, b1, b0, LIMB_SIZE_HALF_448);
540
0
  cy += _gcry_mpih_lshift (a3, a3, LIMB_SIZE_HALF_448, 1);
541
0
  cy += _gcry_mpih_add_n (b1, b1, a2, LIMB_SIZE_HALF_448);
542
0
  cy += _gcry_mpih_add_n (b1, b1, a3, LIMB_SIZE_HALF_448);
543
0
#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
544
0
  cy = _gcry_mpih_rshift (b1, b1, LIMB_SIZE_HALF_448, 32);
545
0
  wp[LIMB_SIZE_HALF_448-1] |= cy;
546
0
#endif
547
0
  memcpy (wp + LIMB_SIZE_HALF_448, b1, (wsize / 2) * BYTES_PER_MPI_LIMB);
548
549
0
#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
550
0
  cy = b1[LIMB_SIZE_HALF_448-1];
551
0
#endif
552
553
0
  memset (n, 0, wsize * BYTES_PER_MPI_LIMB);
554
555
0
#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
556
0
  n[LIMB_SIZE_HALF_448-1] = cy << 32;
557
#else
558
  n[LIMB_SIZE_HALF_448] = cy;
559
#endif
560
0
  n[0] = cy;
561
0
  _gcry_mpih_add_n (wp, wp, n, wsize);
562
563
0
  cy = _gcry_mpih_sub_n (n, wp, ctx->p->d, wsize);
564
0
  mpih_set_cond (wp, n, wsize, mpih_limb_is_zero (cy));
565
0
}
566
567
static void
568
ec_mul2_448 (gcry_mpi_t w, gcry_mpi_t u, mpi_ec_t ctx)
569
0
{
570
0
  ec_addm_448 (w, u, u, ctx);
571
0
}
572
573
static void
574
ec_pow2_448 (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx)
575
0
{
576
0
  ec_mulm_448 (w, b, b, ctx);
577
0
}
578

579
580
/* Fast reduction for secp256k1 */
581
static void
582
ec_secp256k1_mod (gcry_mpi_t w, mpi_ec_t ctx)
583
4.30M
{
584
4.30M
  mpi_limb_t s[(256 + BITS_PER_MPI_LIMB - 1) / BITS_PER_MPI_LIMB + 1];
585
4.30M
  mpi_limb_t n[DIM(s)];
586
4.30M
  const mpi_size_t wsize = DIM(s) - 1;
587
4.30M
  mpi_limb_t cy, borrow;
588
4.30M
  mpi_ptr_t wp;
589
590
4.30M
  MPN_NORMALIZE (w->d, w->nlimbs);
591
4.30M
  if (w->nlimbs > 2 * 256 / BITS_PER_MPI_LIMB)
592
0
    log_bug ("W must be less than m^2\n");
593
594
4.30M
  RESIZE_AND_CLEAR_IF_NEEDED (w, wsize * 2);
595
596
4.30M
  wp = w->d;
597
598
  /* mod P (2^256 - 2^32 - 977) */
599
600
  /* first pass of reduction */
601
4.30M
  memcpy (n, wp + wsize, wsize * BYTES_PER_MPI_LIMB);
602
4.30M
#if BITS_PER_MPI_LIMB == 64
603
4.30M
  s[wsize] = _gcry_mpih_lshift (s, wp + wsize, wsize, 32);
604
#else
605
  s[0] = 0;
606
  memcpy (s + 1, wp + wsize, wsize * BYTES_PER_MPI_LIMB);
607
#endif
608
4.30M
  wp[wsize] = _gcry_mpih_addmul_1 (wp, n, wsize, 977);
609
4.30M
  cy = _gcry_mpih_add_n (wp, wp, s, wsize + 1);
610
611
  /* second pass of reduction */
612
4.30M
#if BITS_PER_MPI_LIMB == 64
613
  /* cy == 0 */
614
4.30M
  memset (n + 1, 0, (wsize - 1) * BYTES_PER_MPI_LIMB);
615
4.30M
  umul_ppmm(n[1], n[0], wp[wsize], ((mpi_limb_t)1 << 32) + 977);
616
#else
617
  memset (n + 2, 0, (wsize - 2) * BYTES_PER_MPI_LIMB);
618
  umul_ppmm(n[1], n[0], wp[wsize], 977);
619
  add_ssaaaa(n[2], n[1], 0, n[1], 0, cy * 977);
620
  add_ssaaaa(n[2], n[1], n[2], n[1], cy, wp[wsize]);
621
#endif
622
4.30M
  cy = _gcry_mpih_add_n (wp, wp, n, wsize);
623
624
4.30M
  borrow = _gcry_mpih_sub_n (s, wp, ctx->p->d, wsize);
625
4.30M
  mpih_set_cond (wp, s, wsize,
626
4.30M
     mpih_limb_is_not_zero (cy) | mpih_limb_is_zero (borrow));
627
628
4.30M
  w->nlimbs = wsize;
629
4.30M
  MPN_NORMALIZE (wp, w->nlimbs);
630
4.30M
}
631
632
633
struct field_table {
634
  const char *p;
635
636
  /* computation routines for the field.  */
637
  void (* addm) (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx);
638
  void (* subm) (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx);
639
  void (* mulm) (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx);
640
  void (* mul2) (gcry_mpi_t w, gcry_mpi_t u, mpi_ec_t ctx);
641
  void (* pow2) (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx);
642
  void (* mod) (gcry_mpi_t w, mpi_ec_t ctx);
643
};
644
645
static const struct field_table field_table[] = {
646
  {
647
    "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED",
648
    ec_addm_25519,
649
    ec_subm_25519,
650
    ec_mulm_25519,
651
    ec_mul2_25519,
652
    ec_pow2_25519,
653
    NULL
654
  },
655
  {
656
   "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE"
657
   "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
658
    ec_addm_448,
659
    ec_subm_448,
660
    ec_mulm_448,
661
    ec_mul2_448,
662
    ec_pow2_448,
663
    NULL
664
  },
665
  {
666
    "0xfffffffffffffffffffffffffffffffeffffffffffffffff",
667
    NULL,
668
    NULL,
669
    NULL,
670
    NULL,
671
    NULL,
672
    _gcry_mpi_ec_nist192_mod
673
  },
674
  {
675
    "0xffffffffffffffffffffffffffffffff000000000000000000000001",
676
    NULL,
677
    NULL,
678
    NULL,
679
    NULL,
680
    NULL,
681
    _gcry_mpi_ec_nist224_mod
682
  },
683
  {
684
    "0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff",
685
    NULL,
686
    NULL,
687
    NULL,
688
    NULL,
689
    NULL,
690
    _gcry_mpi_ec_nist256_mod
691
  },
692
  {
693
    "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
694
    "ffffffff0000000000000000ffffffff",
695
    NULL,
696
    NULL,
697
    NULL,
698
    NULL,
699
    NULL,
700
    _gcry_mpi_ec_nist384_mod
701
  },
702
  {
703
    "0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
704
    "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
705
    NULL,
706
    NULL,
707
    NULL,
708
    NULL,
709
    NULL,
710
    _gcry_mpi_ec_nist521_mod
711
  },
712
  {
713
    "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F",
714
    NULL,
715
    NULL,
716
    NULL,
717
    NULL,
718
    NULL,
719
    ec_secp256k1_mod
720
  },
721
  { NULL, NULL, NULL, NULL, NULL, NULL },
722
};
723
724
static gcry_mpi_t field_table_mpis[DIM(field_table)];
725

726
727
/* Force recomputation of all helper variables.  */
728
void
729
_gcry_mpi_ec_get_reset (mpi_ec_t ec)
730
2.99k
{
731
2.99k
  ec->t.valid.a_is_pminus3 = 0;
732
2.99k
  ec->t.valid.two_inv_p = 0;
733
2.99k
}
734
735
736
/* Accessor for helper variable.  */
737
static int
738
ec_get_a_is_pminus3 (mpi_ec_t ec)
739
1.12M
{
740
1.12M
  gcry_mpi_t tmp;
741
742
1.12M
  if (!ec->t.valid.a_is_pminus3)
743
1.90k
    {
744
1.90k
      ec->t.valid.a_is_pminus3 = 1;
745
1.90k
      tmp = mpi_alloc_like (ec->p);
746
1.90k
      mpi_sub_ui (tmp, ec->p, 3);
747
1.90k
      ec->t.a_is_pminus3 = !mpi_cmp (ec->a, tmp);
748
1.90k
      mpi_free (tmp);
749
1.90k
    }
750
751
1.12M
  return ec->t.a_is_pminus3;
752
1.12M
}
753
754
755
/* Accessor for helper variable.  */
756
static gcry_mpi_t
757
ec_get_two_inv_p (mpi_ec_t ec)
758
415k
{
759
415k
  if (!ec->t.valid.two_inv_p)
760
1.87k
    {
761
1.87k
      ec->t.valid.two_inv_p = 1;
762
1.87k
      if (!ec->t.two_inv_p)
763
1.87k
        ec->t.two_inv_p = mpi_alloc (0);
764
1.87k
      ec_invm (ec->t.two_inv_p, mpi_const (MPI_C_TWO), ec);
765
1.87k
    }
766
415k
  return ec->t.two_inv_p;
767
415k
}
768
769
770
static const char *const curve25519_bad_points[] = {
771
  "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed",
772
  "0x0000000000000000000000000000000000000000000000000000000000000000",
773
  "0x0000000000000000000000000000000000000000000000000000000000000001",
774
  "0x00b8495f16056286fdb1329ceb8d09da6ac49ff1fae35616aeb8413b7c7aebe0",
775
  "0x57119fd0dd4e22d8868e1c58c45c44045bef839c55b1d0b1248c50a3bc959c5f",
776
  "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec",
777
  "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffee",
778
  NULL
779
};
780
781
782
static const char *const curve448_bad_points[] = {
783
  "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
784
  "ffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
785
  "0x00000000000000000000000000000000000000000000000000000000"
786
  "00000000000000000000000000000000000000000000000000000000",
787
  "0x00000000000000000000000000000000000000000000000000000000"
788
  "00000000000000000000000000000000000000000000000000000001",
789
  "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
790
  "fffffffffffffffffffffffffffffffffffffffffffffffffffffffe",
791
  "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
792
  "00000000000000000000000000000000000000000000000000000000",
793
  NULL
794
};
795
796
static const char *const *bad_points_table[] = {
797
  curve25519_bad_points,
798
  curve448_bad_points,
799
};
800
801
static gcry_mpi_t
802
scanval (const char *string)
803
0
{
804
0
  gpg_err_code_t rc;
805
0
  gcry_mpi_t val;
806
807
0
  rc = _gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL);
808
0
  if (rc)
809
0
    log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (rc));
810
0
  return val;
811
0
}
812
813
814
/* This function initialized a context for elliptic curve based on the
815
   field GF(p).  P is the prime specifying this field, A is the first
816
   coefficient.  CTX is expected to be zeroized.  */
817
static void
818
ec_p_init (mpi_ec_t ctx, enum gcry_mpi_ec_models model,
819
           enum ecc_dialects dialect,
820
           int flags,
821
           gcry_mpi_t p, gcry_mpi_t a, gcry_mpi_t b)
822
2.99k
{
823
2.99k
  int i;
824
2.99k
  static int use_barrett;
825
826
2.99k
  if (!use_barrett)
827
5
    {
828
5
      if (getenv ("GCRYPT_BARRETT"))
829
0
        use_barrett = 1;
830
5
      else
831
5
        use_barrett = -1;
832
5
    }
833
834
  /* Fixme: Do we want to check some constraints? e.g.  a < p  */
835
836
2.99k
  ctx->model = model;
837
2.99k
  ctx->dialect = dialect;
838
2.99k
  ctx->flags = flags;
839
2.99k
  ctx->nbits = mpi_get_nbits (p);
840
2.99k
  ctx->p = mpi_copy (p);
841
2.99k
  ctx->a = mpi_copy (a);
842
2.99k
  ctx->b = mpi_copy (b);
843
844
2.99k
  ctx->t.p_barrett = use_barrett > 0? _gcry_mpi_barrett_init (ctx->p, 0):NULL;
845
846
2.99k
  _gcry_mpi_ec_get_reset (ctx);
847
848
2.99k
  if (model == MPI_EC_MONTGOMERY)
849
0
    {
850
0
      for (i=0; i< DIM(bad_points_table); i++)
851
0
        {
852
0
          gcry_mpi_t p_candidate = scanval (bad_points_table[i][0]);
853
0
          int match_p = !mpi_cmp (ctx->p, p_candidate);
854
0
          int j;
855
856
0
          mpi_free (p_candidate);
857
0
          if (!match_p)
858
0
            continue;
859
860
0
          for (j=0; j < DIM(ctx->t.scratch) && bad_points_table[i][j]; j++)
861
0
            ctx->t.scratch[j] = scanval (bad_points_table[i][j]);
862
0
        }
863
0
    }
864
2.99k
  else
865
2.99k
    {
866
      /* Allocate scratch variables.  */
867
35.9k
      for (i=0; i< DIM(ctx->t.scratch); i++)
868
32.9k
        ctx->t.scratch[i] = mpi_alloc_like (ctx->p);
869
2.99k
    }
870
871
2.99k
  ctx->addm = ec_addm;
872
2.99k
  ctx->subm = ec_subm;
873
2.99k
  ctx->mulm = ec_mulm;
874
2.99k
  ctx->mul2 = ec_mul2;
875
2.99k
  ctx->pow2 = ec_pow2;
876
2.99k
  ctx->mod = ec_mod;
877
878
19.5k
  for (i=0; field_table[i].p; i++)
879
19.1k
    {
880
19.1k
      gcry_mpi_t f_p;
881
19.1k
      gpg_err_code_t rc;
882
883
19.1k
      if (field_table_mpis[i] == NULL)
884
40
  {
885
40
    rc = _gcry_mpi_scan (&f_p, GCRYMPI_FMT_HEX, field_table[i].p, 0,
886
40
             NULL);
887
40
    if (rc)
888
0
      log_fatal ("scanning ECC parameter failed: %s\n",
889
0
           gpg_strerror (rc));
890
40
    field_table_mpis[i] = f_p; /* cache */
891
40
  }
892
19.1k
      else
893
19.1k
  {
894
19.1k
    f_p = field_table_mpis[i];
895
19.1k
  }
896
897
19.1k
      if (!mpi_cmp (p, f_p))
898
2.62k
        {
899
2.62k
          ctx->addm = field_table[i].addm ? field_table[i].addm : ctx->addm;
900
2.62k
          ctx->subm = field_table[i].subm ? field_table[i].subm : ctx->subm;
901
2.62k
          ctx->mulm = field_table[i].mulm ? field_table[i].mulm : ctx->mulm;
902
2.62k
          ctx->mul2 = field_table[i].mul2 ? field_table[i].mul2 : ctx->mul2;
903
2.62k
          ctx->pow2 = field_table[i].pow2 ? field_table[i].pow2 : ctx->pow2;
904
2.62k
          ctx->mod = field_table[i].mod ? field_table[i].mod : ctx->mod;
905
906
2.62k
    if (ctx->a)
907
2.62k
      {
908
2.62k
        mpi_resize (ctx->a, ctx->p->nlimbs);
909
2.62k
        ctx->a->nlimbs = ctx->p->nlimbs;
910
2.62k
      }
911
912
2.62k
    if (ctx->b)
913
2.62k
      {
914
2.62k
        mpi_resize (ctx->b, ctx->p->nlimbs);
915
2.62k
        ctx->b->nlimbs = ctx->p->nlimbs;
916
2.62k
      }
917
918
31.5k
          for (i=0; i< DIM(ctx->t.scratch) && ctx->t.scratch[i]; i++)
919
28.9k
            ctx->t.scratch[i]->nlimbs = ctx->p->nlimbs;
920
921
2.62k
          break;
922
2.62k
        }
923
19.1k
    }
924
925
  /* Prepare for fast reduction.  */
926
  /* FIXME: need a test for NIST values.  However it does not gain us
927
     any real advantage, for 384 bits it is actually slower than using
928
     mpi_mulm.  */
929
/*   ctx->nist_nbits = mpi_get_nbits (ctx->p); */
930
/*   if (ctx->nist_nbits == 192) */
931
/*     { */
932
/*       for (i=0; i < 4; i++) */
933
/*         ctx->s[i] = mpi_new (192); */
934
/*       ctx->c    = mpi_new (192*2); */
935
/*     } */
936
/*   else if (ctx->nist_nbits == 384) */
937
/*     { */
938
/*       for (i=0; i < 10; i++) */
939
/*         ctx->s[i] = mpi_new (384); */
940
/*       ctx->c    = mpi_new (384*2); */
941
/*     } */
942
2.99k
}
943
944
945
static void
946
ec_deinit (void *opaque)
947
2.99k
{
948
2.99k
  mpi_ec_t ctx = opaque;
949
2.99k
  int i;
950
951
2.99k
  _gcry_mpi_barrett_free (ctx->t.p_barrett);
952
953
  /* Domain parameter.  */
954
2.99k
  mpi_free (ctx->p);
955
2.99k
  mpi_free (ctx->a);
956
2.99k
  mpi_free (ctx->b);
957
2.99k
  _gcry_mpi_point_release (ctx->G);
958
2.99k
  mpi_free (ctx->n);
959
960
  /* The key.  */
961
2.99k
  _gcry_mpi_point_release (ctx->Q);
962
2.99k
  mpi_free (ctx->d);
963
964
  /* Private data of ec.c.  */
965
2.99k
  mpi_free (ctx->t.two_inv_p);
966
967
35.9k
  for (i=0; i< DIM(ctx->t.scratch); i++)
968
32.9k
    mpi_free (ctx->t.scratch[i]);
969
970
/*   if (ctx->nist_nbits == 192) */
971
/*     { */
972
/*       for (i=0; i < 4; i++) */
973
/*         mpi_free (ctx->s[i]); */
974
/*       mpi_free (ctx->c); */
975
/*     } */
976
/*   else if (ctx->nist_nbits == 384) */
977
/*     { */
978
/*       for (i=0; i < 10; i++) */
979
/*         mpi_free (ctx->s[i]); */
980
/*       mpi_free (ctx->c); */
981
/*     } */
982
2.99k
}
983
984
985
/* This function returns a new context for elliptic curve based on the
986
   field GF(p).  P is the prime specifying this field, A is the first
987
   coefficient, B is the second coefficient, and MODEL is the model
988
   for the curve.  This function is only used within Libgcrypt and not
989
   part of the public API.
990
991
   This context needs to be released using _gcry_mpi_ec_free.  */
992
mpi_ec_t
993
_gcry_mpi_ec_p_internal_new (enum gcry_mpi_ec_models model,
994
                             enum ecc_dialects dialect,
995
                             int flags,
996
                             gcry_mpi_t p, gcry_mpi_t a, gcry_mpi_t b)
997
446
{
998
446
  mpi_ec_t ctx;
999
1000
446
  ctx = xcalloc (1, sizeof *ctx);
1001
446
  ec_p_init (ctx, model, dialect, flags, p, a, b);
1002
1003
446
  return ctx;
1004
446
}
1005
1006
1007
/* This is a variant of _gcry_mpi_ec_p_internal_new which returns an
1008
   public context and does some error checking on the supplied
1009
   arguments.  On success the new context is stored at R_CTX and 0 is
1010
   returned; on error NULL is stored at R_CTX and an error code is
1011
   returned.
1012
1013
   The context needs to be released using gcry_ctx_release.  */
1014
gpg_err_code_t
1015
_gcry_mpi_ec_p_new (gcry_ctx_t *r_ctx,
1016
                    enum gcry_mpi_ec_models model,
1017
                    enum ecc_dialects dialect,
1018
                    int flags,
1019
                    gcry_mpi_t p, gcry_mpi_t a, gcry_mpi_t b)
1020
2.55k
{
1021
2.55k
  gcry_ctx_t ctx;
1022
2.55k
  mpi_ec_t ec;
1023
1024
2.55k
  *r_ctx = NULL;
1025
2.55k
  if (!p || !a)
1026
0
    return GPG_ERR_EINVAL;
1027
1028
2.55k
  ctx = _gcry_ctx_alloc (CONTEXT_TYPE_EC, sizeof *ec, ec_deinit, NULL);
1029
2.55k
  if (!ctx)
1030
0
    return gpg_err_code_from_syserror ();
1031
2.55k
  ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
1032
2.55k
  ec_p_init (ec, model, dialect, flags, p, a, b);
1033
1034
2.55k
  *r_ctx = ctx;
1035
2.55k
  return 0;
1036
2.55k
}
1037
1038
1039
void
1040
_gcry_mpi_ec_free (mpi_ec_t ctx)
1041
446
{
1042
446
  if (ctx)
1043
446
    {
1044
446
      ec_deinit (ctx);
1045
446
      xfree (ctx);
1046
446
    }
1047
446
}
1048
1049
1050
gcry_mpi_t
1051
_gcry_mpi_ec_get_mpi (const char *name, gcry_ctx_t ctx, int copy)
1052
0
{
1053
0
  mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
1054
1055
0
  return _gcry_ecc_get_mpi (name, ec, copy);
1056
0
}
1057
1058
1059
gcry_mpi_point_t
1060
_gcry_mpi_ec_get_point (const char *name, gcry_ctx_t ctx, int copy)
1061
1.11k
{
1062
1.11k
  mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
1063
1064
1.11k
  (void)copy;  /* Not used.  */
1065
1066
1.11k
  return _gcry_ecc_get_point (name, ec);
1067
1.11k
}
1068
1069
1070
gpg_err_code_t
1071
_gcry_mpi_ec_set_mpi (const char *name, gcry_mpi_t newvalue,
1072
                      gcry_ctx_t ctx)
1073
0
{
1074
0
  mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
1075
1076
0
  return _gcry_ecc_set_mpi (name, newvalue, ec);
1077
0
}
1078
1079
1080
gpg_err_code_t
1081
_gcry_mpi_ec_set_point (const char *name, gcry_mpi_point_t newvalue,
1082
                        gcry_ctx_t ctx)
1083
0
{
1084
0
  mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
1085
1086
0
  return _gcry_ecc_set_point (name, newvalue, ec);
1087
0
}
1088
1089
1090
/* Given an encoded point in the MPI VALUE and a context EC, decode
1091
 * the point according to the context and store it in RESULT.  On
1092
 * error an error code is return but RESULT might have been changed.
1093
 * If no context is given the function tries to decode VALUE by
1094
 * assuming a 0x04 prefixed uncompressed encoding.  */
1095
gpg_err_code_t
1096
_gcry_mpi_ec_decode_point (mpi_point_t result, gcry_mpi_t value, mpi_ec_t ec)
1097
126
{
1098
126
  gpg_err_code_t rc;
1099
1100
126
  if (ec
1101
126
      && (ec->dialect == ECC_DIALECT_ED25519
1102
126
          || (ec->model == MPI_EC_EDWARDS
1103
126
              && ec->dialect == ECC_DIALECT_SAFECURVE)))
1104
0
    rc = _gcry_ecc_eddsa_decodepoint (value, ec, result, NULL, NULL);
1105
126
  else if (ec && ec->model == MPI_EC_MONTGOMERY)
1106
0
    rc = _gcry_ecc_mont_decodepoint (value, ec, result);
1107
126
  else
1108
126
    rc = _gcry_ecc_sec_decodepoint (value, ec, result);
1109
1110
126
  return rc;
1111
126
}
1112
1113
1114
/* Compute the affine coordinates from the projective coordinates in
1115
   POINT.  Set them into X and Y.  If one coordinate is not required,
1116
   X or Y may be passed as NULL.  CTX is the usual context. Returns: 0
1117
   on success or !0 if POINT is at infinity.  */
1118
int
1119
_gcry_mpi_ec_get_affine (gcry_mpi_t x, gcry_mpi_t y, mpi_point_t point,
1120
                         mpi_ec_t ctx)
1121
3.38k
{
1122
3.38k
  if (!mpi_cmp_ui (point->z, 0))
1123
22
    return -1;
1124
1125
3.35k
  switch (ctx->model)
1126
3.35k
    {
1127
3.35k
    case MPI_EC_WEIERSTRASS: /* Using Jacobian coordinates.  */
1128
3.35k
      {
1129
3.35k
        gcry_mpi_t z1, z2, z3;
1130
1131
3.35k
  if (!mpi_cmp_ui (point->z, 1))
1132
976
    {
1133
976
      if (x)
1134
976
        mpi_set (x, point->x);
1135
976
      if (y)
1136
976
        mpi_set (y, point->y);
1137
976
      return 0;
1138
976
    }
1139
1140
2.38k
        z1 = mpi_new (0);
1141
2.38k
        z2 = mpi_new (0);
1142
2.38k
        ec_invm (z1, point->z, ctx);  /* z1 = z^(-1) mod p  */
1143
2.38k
        ec_mulm (z2, z1, z1, ctx);    /* z2 = z^(-2) mod p  */
1144
1145
2.38k
        if (x)
1146
2.38k
          ec_mulm (x, point->x, z2, ctx);
1147
1148
2.38k
        if (y)
1149
1.94k
          {
1150
1.94k
            z3 = mpi_new (0);
1151
1.94k
            ec_mulm (z3, z2, z1, ctx);      /* z3 = z^(-3) mod p  */
1152
1.94k
            ec_mulm (y, point->y, z3, ctx);
1153
1.94k
            mpi_free (z3);
1154
1.94k
          }
1155
1156
2.38k
        mpi_free (z2);
1157
2.38k
        mpi_free (z1);
1158
2.38k
      }
1159
0
      return 0;
1160
1161
0
    case MPI_EC_MONTGOMERY:
1162
0
      {
1163
0
        if (x)
1164
0
          mpi_set (x, point->x);
1165
1166
0
        if (y)
1167
0
          {
1168
0
            log_fatal ("%s: Getting Y-coordinate on %s is not supported\n",
1169
0
                       "_gcry_mpi_ec_get_affine", "Montgomery");
1170
0
            return -1;
1171
0
          }
1172
0
      }
1173
0
      return 0;
1174
1175
0
    case MPI_EC_EDWARDS:
1176
0
      {
1177
0
        gcry_mpi_t z;
1178
1179
0
  if (!mpi_cmp_ui (point->z, 1))
1180
0
    {
1181
0
      if (x)
1182
0
        mpi_set (x, point->x);
1183
0
      if (y)
1184
0
        mpi_set (y, point->y);
1185
0
      return 0;
1186
0
    }
1187
1188
0
        z = mpi_new (0);
1189
0
        ec_invm (z, point->z, ctx);
1190
1191
0
        mpi_resize (z, ctx->p->nlimbs);
1192
0
        z->nlimbs = ctx->p->nlimbs;
1193
1194
0
        if (x)
1195
0
          {
1196
0
            mpi_resize (x, ctx->p->nlimbs);
1197
0
            x->nlimbs = ctx->p->nlimbs;
1198
0
            ctx->mulm (x, point->x, z, ctx);
1199
0
          }
1200
0
        if (y)
1201
0
          {
1202
0
            mpi_resize (y, ctx->p->nlimbs);
1203
0
            y->nlimbs = ctx->p->nlimbs;
1204
0
            ctx->mulm (y, point->y, z, ctx);
1205
0
          }
1206
1207
0
        _gcry_mpi_release (z);
1208
0
      }
1209
0
      return 0;
1210
1211
0
    default:
1212
0
      return -1;
1213
3.35k
    }
1214
3.35k
}
1215
1216
1217

1218
/*  RESULT = 2 * POINT  (Weierstrass version). */
1219
static void
1220
dup_point_weierstrass (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
1221
1.12M
{
1222
4.48M
#define x3 (result->x)
1223
5.60M
#define y3 (result->y)
1224
3.36M
#define z3 (result->z)
1225
5.97M
#define t1 (ctx->t.scratch[0])
1226
7.10M
#define t2 (ctx->t.scratch[1])
1227
1.12M
#define t3 (ctx->t.scratch[2])
1228
7.84M
#define l1 (ctx->t.scratch[3])
1229
5.60M
#define l2 (ctx->t.scratch[4])
1230
2.24M
#define l3 (ctx->t.scratch[5])
1231
1232
1.12M
  if (!mpi_cmp_ui (point->y, 0) || !mpi_cmp_ui (point->z, 0))
1233
311
    {
1234
      /* P_y == 0 || P_z == 0 => [1:1:0] */
1235
311
      mpi_set_ui (x3, 1);
1236
311
      mpi_set_ui (y3, 1);
1237
311
      mpi_set_ui (z3, 0);
1238
311
    }
1239
1.12M
  else
1240
1.12M
    {
1241
1.12M
      if (ec_get_a_is_pminus3 (ctx))  /* Use the faster case.  */
1242
750k
        {
1243
          /* L1 = 3(X - Z^2)(X + Z^2) */
1244
          /*                          T1: used for Z^2. */
1245
          /*                          T2: used for the right term.  */
1246
750k
          ec_pow2 (t1, point->z, ctx);
1247
750k
          ec_subm (l1, point->x, t1, ctx);
1248
750k
          ec_mulm (l1, l1, mpi_const (MPI_C_THREE), ctx);
1249
750k
          ec_addm (t2, point->x, t1, ctx);
1250
750k
          ec_mulm (l1, l1, t2, ctx);
1251
750k
        }
1252
369k
      else /* Standard case. */
1253
369k
        {
1254
          /* L1 = 3X^2 + aZ^4 */
1255
          /*                          T1: used for aZ^4. */
1256
369k
          ec_pow2 (l1, point->x, ctx);
1257
369k
          ec_mulm (l1, l1, mpi_const (MPI_C_THREE), ctx);
1258
369k
          ec_powm (t1, point->z, mpi_const (MPI_C_FOUR), ctx);
1259
369k
          ec_mulm (t1, t1, ctx->a, ctx);
1260
369k
          ec_addm (l1, l1, t1, ctx);
1261
369k
        }
1262
      /* Z3 = 2YZ */
1263
1.12M
      ec_mulm (z3, point->y, point->z, ctx);
1264
1.12M
      ec_mul2 (z3, z3, ctx);
1265
1266
      /* L2 = 4XY^2 */
1267
      /*                              T2: used for Y2; required later. */
1268
1.12M
      ec_pow2 (t2, point->y, ctx);
1269
1.12M
      ec_mulm (l2, t2, point->x, ctx);
1270
1.12M
      ec_mulm (l2, l2, mpi_const (MPI_C_FOUR), ctx);
1271
1272
      /* X3 = L1^2 - 2L2 */
1273
      /*                              T1: used for L2^2. */
1274
1.12M
      ec_pow2 (x3, l1, ctx);
1275
1.12M
      ec_mul2 (t1, l2, ctx);
1276
1.12M
      ec_subm (x3, x3, t1, ctx);
1277
1278
      /* L3 = 8Y^4 */
1279
      /*                              T2: taken from above. */
1280
1.12M
      ec_pow2 (t2, t2, ctx);
1281
1.12M
      ec_mulm (l3, t2, mpi_const (MPI_C_EIGHT), ctx);
1282
1283
      /* Y3 = L1(L2 - X3) - L3 */
1284
1.12M
      ec_subm (y3, l2, x3, ctx);
1285
1.12M
      ec_mulm (y3, y3, l1, ctx);
1286
1.12M
      ec_subm (y3, y3, l3, ctx);
1287
1.12M
    }
1288
1289
1.12M
#undef x3
1290
1.12M
#undef y3
1291
1.12M
#undef z3
1292
1.12M
#undef t1
1293
1.12M
#undef t2
1294
1.12M
#undef t3
1295
1.12M
#undef l1
1296
1.12M
#undef l2
1297
1.12M
#undef l3
1298
1.12M
}
1299
1300
1301
/*  RESULT = 2 * POINT  (Montgomery version). */
1302
static void
1303
dup_point_montgomery (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
1304
0
{
1305
0
  (void)result;
1306
0
  (void)point;
1307
0
  (void)ctx;
1308
0
  log_fatal ("%s: %s not yet supported\n",
1309
0
             "_gcry_mpi_ec_dup_point", "Montgomery");
1310
0
}
1311
1312
1313
/*  RESULT = 2 * POINT  (Twisted Edwards version). */
1314
static void
1315
dup_point_edwards (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
1316
0
{
1317
0
#define X1 (point->x)
1318
0
#define Y1 (point->y)
1319
0
#define Z1 (point->z)
1320
0
#define X3 (result->x)
1321
0
#define Y3 (result->y)
1322
0
#define Z3 (result->z)
1323
0
#define B (ctx->t.scratch[0])
1324
0
#define C (ctx->t.scratch[1])
1325
0
#define D (ctx->t.scratch[2])
1326
0
#define E (ctx->t.scratch[3])
1327
0
#define F (ctx->t.scratch[4])
1328
0
#define H (ctx->t.scratch[5])
1329
0
#define J (ctx->t.scratch[6])
1330
1331
  /* Compute: (X_3 : Y_3 : Z_3) = 2( X_1 : Y_1 : Z_1 ) */
1332
1333
  /* B = (X_1 + Y_1)^2  */
1334
0
  ctx->addm (B, X1, Y1, ctx);
1335
0
  ctx->pow2 (B, B, ctx);
1336
1337
  /* C = X_1^2 */
1338
  /* D = Y_1^2 */
1339
0
  ctx->pow2 (C, X1, ctx);
1340
0
  ctx->pow2 (D, Y1, ctx);
1341
1342
  /* E = aC */
1343
0
  if (ctx->dialect == ECC_DIALECT_ED25519)
1344
0
    ctx->subm (E, ctx->p, C, ctx);
1345
0
  else
1346
0
    ctx->mulm (E, ctx->a, C, ctx);
1347
1348
  /* F = E + D */
1349
0
  ctx->addm (F, E, D, ctx);
1350
1351
  /* H = Z_1^2 */
1352
0
  ctx->pow2 (H, Z1, ctx);
1353
1354
  /* J = F - 2H */
1355
0
  ctx->mul2 (J, H, ctx);
1356
0
  ctx->subm (J, F, J, ctx);
1357
1358
  /* X_3 = (B - C - D) · J */
1359
0
  ctx->subm (X3, B, C, ctx);
1360
0
  ctx->subm (X3, X3, D, ctx);
1361
0
  ctx->mulm (X3, X3, J, ctx);
1362
1363
  /* Y_3 = F · (E - D) */
1364
0
  ctx->subm (Y3, E, D, ctx);
1365
0
  ctx->mulm (Y3, Y3, F, ctx);
1366
1367
  /* Z_3 = F · J */
1368
0
  ctx->mulm (Z3, F, J, ctx);
1369
1370
0
#undef X1
1371
0
#undef Y1
1372
0
#undef Z1
1373
0
#undef X3
1374
0
#undef Y3
1375
0
#undef Z3
1376
0
#undef B
1377
0
#undef C
1378
0
#undef D
1379
0
#undef E
1380
0
#undef F
1381
0
#undef H
1382
0
#undef J
1383
0
}
1384
1385
1386
/*  RESULT = 2 * POINT  */
1387
void
1388
_gcry_mpi_ec_dup_point (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
1389
1.12M
{
1390
1.12M
  switch (ctx->model)
1391
1.12M
    {
1392
1.12M
    case MPI_EC_WEIERSTRASS:
1393
1.12M
      dup_point_weierstrass (result, point, ctx);
1394
1.12M
      break;
1395
0
    case MPI_EC_MONTGOMERY:
1396
0
      dup_point_montgomery (result, point, ctx);
1397
0
      break;
1398
0
    case MPI_EC_EDWARDS:
1399
0
      dup_point_edwards (result, point, ctx);
1400
0
      break;
1401
1.12M
    }
1402
1.12M
}
1403
1404
1405
/* RESULT = P1 + P2  (Weierstrass version).*/
1406
static void
1407
add_points_weierstrass (mpi_point_t result,
1408
                        mpi_point_t p1, mpi_point_t p2,
1409
                        mpi_ec_t ctx)
1410
416k
{
1411
416k
#define x1 (p1->x    )
1412
416k
#define y1 (p1->y    )
1413
1.24M
#define z1 (p1->z    )
1414
416k
#define x2 (p2->x    )
1415
416k
#define y2 (p2->y    )
1416
832k
#define z2 (p2->z    )
1417
831k
#define x3 (result->x)
1418
1.24M
#define y3 (result->y)
1419
1.24M
#define z3 (result->z)
1420
832k
#define l1 (ctx->t.scratch[0])
1421
2.07M
#define l2 (ctx->t.scratch[1])
1422
1.66M
#define l3 (ctx->t.scratch[2])
1423
2.07M
#define l4 (ctx->t.scratch[3])
1424
2.07M
#define l5 (ctx->t.scratch[4])
1425
1.24M
#define l6 (ctx->t.scratch[5])
1426
831k
#define l7 (ctx->t.scratch[6])
1427
831k
#define l8 (ctx->t.scratch[7])
1428
1.66M
#define l9 (ctx->t.scratch[8])
1429
3.32M
#define t1 (ctx->t.scratch[9])
1430
2.07M
#define t2 (ctx->t.scratch[10])
1431
1432
416k
  if ( (!mpi_cmp (x1, x2)) && (!mpi_cmp (y1, y2)) && (!mpi_cmp (z1, z2)) )
1433
12
    {
1434
      /* Same point; need to call the duplicate function.  */
1435
12
      _gcry_mpi_ec_dup_point (result, p1, ctx);
1436
12
    }
1437
416k
  else if (!mpi_cmp_ui (z1, 0))
1438
311
    {
1439
      /* P1 is at infinity.  */
1440
311
      mpi_set (x3, p2->x);
1441
311
      mpi_set (y3, p2->y);
1442
311
      mpi_set (z3, p2->z);
1443
311
    }
1444
415k
  else if (!mpi_cmp_ui (z2, 0))
1445
0
    {
1446
      /* P2 is at infinity.  */
1447
0
      mpi_set (x3, p1->x);
1448
0
      mpi_set (y3, p1->y);
1449
0
      mpi_set (z3, p1->z);
1450
0
    }
1451
415k
  else
1452
415k
    {
1453
415k
      int z1_is_one = !mpi_cmp_ui (z1, 1);
1454
415k
      int z2_is_one = !mpi_cmp_ui (z2, 1);
1455
1456
      /* l1 = x1 z2^2  */
1457
      /* l2 = x2 z1^2  */
1458
415k
      if (z2_is_one)
1459
415k
        mpi_set (l1, x1);
1460
138
      else
1461
138
        {
1462
138
          ec_pow2 (l1, z2, ctx);
1463
138
          ec_mulm (l1, l1, x1, ctx);
1464
138
        }
1465
415k
      if (z1_is_one)
1466
20
        mpi_set (l2, x2);
1467
415k
      else
1468
415k
        {
1469
415k
          ec_pow2 (l2, z1, ctx);
1470
415k
          ec_mulm (l2, l2, x2, ctx);
1471
415k
        }
1472
      /* l3 = l1 - l2 */
1473
415k
      ec_subm (l3, l1, l2, ctx);
1474
      /* l4 = y1 z2^3  */
1475
415k
      ec_powm (l4, z2, mpi_const (MPI_C_THREE), ctx);
1476
415k
      ec_mulm (l4, l4, y1, ctx);
1477
      /* l5 = y2 z1^3  */
1478
415k
      ec_powm (l5, z1, mpi_const (MPI_C_THREE), ctx);
1479
415k
      ec_mulm (l5, l5, y2, ctx);
1480
      /* l6 = l4 - l5  */
1481
415k
      ec_subm (l6, l4, l5, ctx);
1482
1483
415k
      if (!mpi_cmp_ui (l3, 0))
1484
12
        {
1485
12
          if (!mpi_cmp_ui (l6, 0))
1486
11
            {
1487
              /* P1 and P2 are the same - use duplicate function.  */
1488
11
              _gcry_mpi_ec_dup_point (result, p1, ctx);
1489
11
            }
1490
1
          else
1491
1
            {
1492
              /* P1 is the inverse of P2.  */
1493
1
              mpi_set_ui (x3, 1);
1494
1
              mpi_set_ui (y3, 1);
1495
1
              mpi_set_ui (z3, 0);
1496
1
            }
1497
12
        }
1498
415k
      else
1499
415k
        {
1500
          /* l7 = l1 + l2  */
1501
415k
          ec_addm (l7, l1, l2, ctx);
1502
          /* l8 = l4 + l5  */
1503
415k
          ec_addm (l8, l4, l5, ctx);
1504
          /* z3 = z1 z2 l3  */
1505
415k
          ec_mulm (z3, z1, z2, ctx);
1506
415k
          ec_mulm (z3, z3, l3, ctx);
1507
          /* x3 = l6^2 - l7 l3^2  */
1508
415k
          ec_pow2 (t1, l6, ctx);
1509
415k
          ec_pow2 (t2, l3, ctx);
1510
415k
          ec_mulm (t2, t2, l7, ctx);
1511
415k
          ec_subm (x3, t1, t2, ctx);
1512
          /* l9 = l7 l3^2 - 2 x3  */
1513
415k
          ec_mul2 (t1, x3, ctx);
1514
415k
          ec_subm (l9, t2, t1, ctx);
1515
          /* y3 = (l9 l6 - l8 l3^3)/2  */
1516
415k
          ec_mulm (l9, l9, l6, ctx);
1517
415k
          ec_powm (t1, l3, mpi_const (MPI_C_THREE), ctx); /* fixme: Use saved value*/
1518
415k
          ec_mulm (t1, t1, l8, ctx);
1519
415k
          ec_subm (y3, l9, t1, ctx);
1520
415k
          ec_mulm (y3, y3, ec_get_two_inv_p (ctx), ctx);
1521
415k
        }
1522
415k
    }
1523
1524
416k
#undef x1
1525
416k
#undef y1
1526
416k
#undef z1
1527
416k
#undef x2
1528
416k
#undef y2
1529
416k
#undef z2
1530
416k
#undef x3
1531
416k
#undef y3
1532
416k
#undef z3
1533
416k
#undef l1
1534
416k
#undef l2
1535
416k
#undef l3
1536
416k
#undef l4
1537
416k
#undef l5
1538
416k
#undef l6
1539
416k
#undef l7
1540
416k
#undef l8
1541
416k
#undef l9
1542
416k
#undef t1
1543
416k
#undef t2
1544
416k
}
1545
1546
1547
/* RESULT = P1 + P2  (Montgomery version).*/
1548
static void
1549
add_points_montgomery (mpi_point_t result,
1550
                       mpi_point_t p1, mpi_point_t p2,
1551
                       mpi_ec_t ctx)
1552
0
{
1553
0
  (void)result;
1554
0
  (void)p1;
1555
0
  (void)p2;
1556
0
  (void)ctx;
1557
0
  log_fatal ("%s: %s not yet supported\n",
1558
0
             "_gcry_mpi_ec_add_points", "Montgomery");
1559
0
}
1560
1561
1562
/* RESULT = P1 + P2  (Twisted Edwards version).*/
1563
static void
1564
add_points_edwards (mpi_point_t result,
1565
                    mpi_point_t p1, mpi_point_t p2,
1566
                    mpi_ec_t ctx)
1567
0
{
1568
0
#define X1 (p1->x)
1569
0
#define Y1 (p1->y)
1570
0
#define Z1 (p1->z)
1571
0
#define X2 (p2->x)
1572
0
#define Y2 (p2->y)
1573
0
#define Z2 (p2->z)
1574
0
#define X3 (result->x)
1575
0
#define Y3 (result->y)
1576
0
#define Z3 (result->z)
1577
0
#define A (ctx->t.scratch[0])
1578
0
#define B (ctx->t.scratch[1])
1579
0
#define C (ctx->t.scratch[2])
1580
0
#define D (ctx->t.scratch[3])
1581
0
#define E (ctx->t.scratch[4])
1582
0
#define F (ctx->t.scratch[5])
1583
0
#define G (ctx->t.scratch[6])
1584
0
#define tmp (ctx->t.scratch[7])
1585
1586
0
  mpi_point_resize (result, ctx);
1587
1588
  /* Compute: (X_3 : Y_3 : Z_3) = (X_1 : Y_1 : Z_1) + (X_2 : Y_2 : Z_3)  */
1589
1590
  /* A = Z1 · Z2 */
1591
0
  ctx->mulm (A, Z1, Z2, ctx);
1592
1593
  /* B = A^2 */
1594
0
  ctx->pow2 (B, A, ctx);
1595
1596
  /* C = X1 · X2 */
1597
0
  ctx->mulm (C, X1, X2, ctx);
1598
1599
  /* D = Y1 · Y2 */
1600
0
  ctx->mulm (D, Y1, Y2, ctx);
1601
1602
  /* E = d · C · D */
1603
0
  ctx->mulm (E, ctx->b, C, ctx);
1604
0
  ctx->mulm (E, E, D, ctx);
1605
1606
  /* F = B - E */
1607
0
  ctx->subm (F, B, E, ctx);
1608
1609
  /* G = B + E */
1610
0
  ctx->addm (G, B, E, ctx);
1611
1612
  /* X_3 = A · F · ((X_1 + Y_1) · (X_2 + Y_2) - C - D) */
1613
0
  ctx->addm (tmp, X1, Y1, ctx);
1614
0
  ctx->addm (X3, X2, Y2, ctx);
1615
0
  ctx->mulm (X3, X3, tmp, ctx);
1616
0
  ctx->subm (X3, X3, C, ctx);
1617
0
  ctx->subm (X3, X3, D, ctx);
1618
0
  ctx->mulm (X3, X3, F, ctx);
1619
0
  ctx->mulm (X3, X3, A, ctx);
1620
1621
  /* Y_3 = A · G · (D - aC) */
1622
0
  if (ctx->dialect == ECC_DIALECT_ED25519)
1623
0
    {
1624
0
      ctx->addm (Y3, D, C, ctx);
1625
0
    }
1626
0
  else
1627
0
    {
1628
0
      ctx->mulm (Y3, ctx->a, C, ctx);
1629
0
      ctx->subm (Y3, D, Y3, ctx);
1630
0
    }
1631
0
  ctx->mulm (Y3, Y3, G, ctx);
1632
0
  ctx->mulm (Y3, Y3, A, ctx);
1633
1634
  /* Z_3 = F · G */
1635
0
  ctx->mulm (Z3, F, G, ctx);
1636
1637
1638
0
#undef X1
1639
0
#undef Y1
1640
0
#undef Z1
1641
0
#undef X2
1642
0
#undef Y2
1643
0
#undef Z2
1644
0
#undef X3
1645
0
#undef Y3
1646
0
#undef Z3
1647
0
#undef A
1648
0
#undef B
1649
0
#undef C
1650
0
#undef D
1651
0
#undef E
1652
0
#undef F
1653
0
#undef G
1654
0
#undef tmp
1655
0
}
1656
1657
1658
/* Compute a step of Montgomery Ladder (only use X and Z in the point).
1659
   Inputs:  P1, P2, and x-coordinate of DIF = P1 - P1.
1660
   Outputs: PRD = 2 * P1 and  SUM = P1 + P2. */
1661
static void
1662
montgomery_ladder (mpi_point_t prd, mpi_point_t sum,
1663
                   mpi_point_t p1, mpi_point_t p2, gcry_mpi_t dif_x,
1664
                   mpi_ec_t ctx)
1665
0
{
1666
0
  ctx->addm (sum->x, p2->x, p2->z, ctx);
1667
0
  ctx->subm (p2->z, p2->x, p2->z, ctx);
1668
0
  ctx->addm (prd->x, p1->x, p1->z, ctx);
1669
0
  ctx->subm (p1->z, p1->x, p1->z, ctx);
1670
0
  ctx->mulm (p2->x, p1->z, sum->x, ctx);
1671
0
  ctx->mulm (p2->z, prd->x, p2->z, ctx);
1672
0
  ctx->pow2 (p1->x, prd->x, ctx);
1673
0
  ctx->pow2 (p1->z, p1->z, ctx);
1674
0
  ctx->addm (sum->x, p2->x, p2->z, ctx);
1675
0
  ctx->subm (p2->z, p2->x, p2->z, ctx);
1676
0
  ctx->mulm (prd->x, p1->x, p1->z, ctx);
1677
0
  ctx->subm (p1->z, p1->x, p1->z, ctx);
1678
0
  ctx->pow2 (sum->x, sum->x, ctx);
1679
0
  ctx->pow2 (sum->z, p2->z, ctx);
1680
0
  ctx->mulm (prd->z, p1->z, ctx->a, ctx); /* CTX->A: (a-2)/4 */
1681
0
  ctx->mulm (sum->z, sum->z, dif_x, ctx);
1682
0
  ctx->addm (prd->z, p1->x, prd->z, ctx);
1683
0
  ctx->mulm (prd->z, prd->z, p1->z, ctx);
1684
0
}
1685
1686
1687
/* RESULT = P1 + P2 */
1688
void
1689
_gcry_mpi_ec_add_points (mpi_point_t result,
1690
                         mpi_point_t p1, mpi_point_t p2,
1691
                         mpi_ec_t ctx)
1692
416k
{
1693
416k
  switch (ctx->model)
1694
416k
    {
1695
416k
    case MPI_EC_WEIERSTRASS:
1696
416k
      add_points_weierstrass (result, p1, p2, ctx);
1697
416k
      break;
1698
0
    case MPI_EC_MONTGOMERY:
1699
0
      add_points_montgomery (result, p1, p2, ctx);
1700
0
      break;
1701
0
    case MPI_EC_EDWARDS:
1702
0
      add_points_edwards (result, p1, p2, ctx);
1703
0
      break;
1704
416k
    }
1705
416k
}
1706
1707
1708
/* RESULT = P1 - P2  (Weierstrass version).*/
1709
static void
1710
sub_points_weierstrass (mpi_point_t result,
1711
                        mpi_point_t p1, mpi_point_t p2,
1712
                        mpi_ec_t ctx)
1713
0
{
1714
0
  (void)result;
1715
0
  (void)p1;
1716
0
  (void)p2;
1717
0
  (void)ctx;
1718
0
  log_fatal ("%s: %s not yet supported\n",
1719
0
             "_gcry_mpi_ec_sub_points", "Weierstrass");
1720
0
}
1721
1722
1723
/* RESULT = P1 - P2  (Montgomery version).*/
1724
static void
1725
sub_points_montgomery (mpi_point_t result,
1726
                       mpi_point_t p1, mpi_point_t p2,
1727
                       mpi_ec_t ctx)
1728
0
{
1729
0
  (void)result;
1730
0
  (void)p1;
1731
0
  (void)p2;
1732
0
  (void)ctx;
1733
0
  log_fatal ("%s: %s not yet supported\n",
1734
0
             "_gcry_mpi_ec_sub_points", "Montgomery");
1735
0
}
1736
1737
1738
/* RESULT = P1 - P2  (Twisted Edwards version).*/
1739
static void
1740
sub_points_edwards (mpi_point_t result,
1741
                    mpi_point_t p1, mpi_point_t p2,
1742
                    mpi_ec_t ctx)
1743
0
{
1744
0
  mpi_point_t p2i = _gcry_mpi_point_new (0);
1745
0
  point_set (p2i, p2);
1746
0
  ctx->subm (p2i->x, ctx->p, p2i->x, ctx);
1747
0
  add_points_edwards (result, p1, p2i, ctx);
1748
0
  _gcry_mpi_point_release (p2i);
1749
0
}
1750
1751
1752
/* RESULT = P1 - P2 */
1753
void
1754
_gcry_mpi_ec_sub_points (mpi_point_t result,
1755
                         mpi_point_t p1, mpi_point_t p2,
1756
                         mpi_ec_t ctx)
1757
0
{
1758
0
  switch (ctx->model)
1759
0
    {
1760
0
    case MPI_EC_WEIERSTRASS:
1761
0
      sub_points_weierstrass (result, p1, p2, ctx);
1762
0
      break;
1763
0
    case MPI_EC_MONTGOMERY:
1764
0
      sub_points_montgomery (result, p1, p2, ctx);
1765
0
      break;
1766
0
    case MPI_EC_EDWARDS:
1767
0
      sub_points_edwards (result, p1, p2, ctx);
1768
0
      break;
1769
0
    }
1770
0
}
1771
1772
1773
/* Scalar point multiplication - the main function for ECC.  It takes
1774
   an integer SCALAR and a POINT as well as the usual context CTX.
1775
   RESULT will be set to the resulting point. */
1776
void
1777
_gcry_mpi_ec_mul_point (mpi_point_t result,
1778
                        gcry_mpi_t scalar, mpi_point_t point,
1779
                        mpi_ec_t ctx)
1780
2.03k
{
1781
2.03k
  gcry_mpi_t x1, y1, z1, k, h, yy;
1782
2.03k
  unsigned int i, loops;
1783
2.03k
  mpi_point_struct p1, p2, p1inv;
1784
1785
  /* First try HW accelerated scalar multiplications.  Error
1786
     is returned if acceleration is not supported or if HW
1787
     does not support acceleration of given input.  */
1788
2.03k
  if (mpi_ec_hw_mul_point (result, scalar, point, ctx) >= 0)
1789
0
    {
1790
0
      return;
1791
0
    }
1792
1793
2.03k
  if (ctx->model == MPI_EC_EDWARDS
1794
2.03k
      || (ctx->model == MPI_EC_WEIERSTRASS
1795
2.03k
          && mpi_is_secure (scalar)))
1796
311
    {
1797
      /* Simple left to right binary method.  Algorithm 3.27 from
1798
       * {author={Hankerson, Darrel and Menezes, Alfred J. and Vanstone, Scott},
1799
       *  title = {Guide to Elliptic Curve Cryptography},
1800
       *  year = {2003}, isbn = {038795273X},
1801
       *  url = {http://www.cacr.math.uwaterloo.ca/ecc/},
1802
       *  publisher = {Springer-Verlag New York, Inc.}} */
1803
311
      unsigned int nbits;
1804
311
      int j;
1805
1806
311
      if (mpi_cmp (scalar, ctx->p) >= 0)
1807
311
        nbits = mpi_get_nbits (scalar);
1808
0
      else
1809
0
        nbits = mpi_get_nbits (ctx->p);
1810
1811
311
      if (ctx->model == MPI_EC_WEIERSTRASS)
1812
311
        {
1813
311
          mpi_set_ui (result->x, 1);
1814
311
          mpi_set_ui (result->y, 1);
1815
311
          mpi_set_ui (result->z, 0);
1816
311
        }
1817
0
      else
1818
0
        {
1819
0
          mpi_set_ui (result->x, 0);
1820
0
          mpi_set_ui (result->y, 1);
1821
0
          mpi_set_ui (result->z, 1);
1822
0
          mpi_point_resize (point, ctx);
1823
0
        }
1824
1825
311
      if (mpi_is_secure (scalar))
1826
311
        {
1827
          /* If SCALAR is in secure memory we assume that it is the
1828
             secret key we use constant time operation.  */
1829
311
          mpi_point_struct tmppnt;
1830
1831
311
          point_init (&tmppnt);
1832
311
          mpi_point_resize (result, ctx);
1833
311
          mpi_point_resize (&tmppnt, ctx);
1834
91.3k
          for (j=nbits-1; j >= 0; j--)
1835
91.0k
            {
1836
91.0k
              _gcry_mpi_ec_dup_point (result, result, ctx);
1837
91.0k
              _gcry_mpi_ec_add_points (&tmppnt, result, point, ctx);
1838
91.0k
              point_swap_cond (result, &tmppnt, mpi_test_bit (scalar, j), ctx);
1839
91.0k
            }
1840
311
          point_free (&tmppnt);
1841
311
        }
1842
0
      else
1843
0
        {
1844
0
          if (ctx->model == MPI_EC_EDWARDS)
1845
0
            {
1846
0
              mpi_point_resize (result, ctx);
1847
0
              mpi_point_resize (point, ctx);
1848
0
            }
1849
1850
0
          for (j=nbits-1; j >= 0; j--)
1851
0
            {
1852
0
              _gcry_mpi_ec_dup_point (result, result, ctx);
1853
0
              if (mpi_test_bit (scalar, j))
1854
0
                _gcry_mpi_ec_add_points (result, result, point, ctx);
1855
0
            }
1856
0
        }
1857
311
      return;
1858
311
    }
1859
1.72k
  else if (ctx->model == MPI_EC_MONTGOMERY)
1860
0
    {
1861
0
      unsigned int nbits;
1862
0
      int j;
1863
0
      mpi_point_struct p1_, p2_;
1864
0
      mpi_point_t q1, q2, prd, sum;
1865
0
      unsigned long sw;
1866
0
      mpi_size_t rsize;
1867
0
      int scalar_copied = 0;
1868
1869
      /* Compute scalar point multiplication with Montgomery Ladder.
1870
         Note that we don't use Y-coordinate in the points at all.
1871
         RESULT->Y will be filled by zero.  */
1872
1873
0
      nbits = mpi_get_nbits (scalar);
1874
0
      point_init (&p1);
1875
0
      point_init (&p2);
1876
0
      point_init (&p1_);
1877
0
      point_init (&p2_);
1878
0
      mpi_set_ui (p1.x, 1);
1879
0
      mpi_free (p2.x);
1880
0
      p2.x  = mpi_copy (point->x);
1881
0
      mpi_set_ui (p2.z, 1);
1882
1883
0
      if (mpi_is_opaque (scalar))
1884
0
        {
1885
0
          const unsigned int pbits = ctx->nbits;
1886
0
          gcry_mpi_t a;
1887
0
          unsigned int n;
1888
0
          unsigned char *raw;
1889
1890
0
          scalar_copied = 1;
1891
1892
0
          raw = _gcry_mpi_get_opaque_copy (scalar, &n);
1893
0
          if ((n+7)/8 != (pbits+7)/8)
1894
0
            log_fatal ("scalar size (%d) != prime size (%d)\n",
1895
0
                       (n+7)/8, (pbits+7)/8);
1896
1897
0
          reverse_buffer (raw, (n+7)/8);
1898
0
          if ((pbits % 8))
1899
0
            raw[0] &= (1 << (pbits % 8)) - 1;
1900
0
          raw[0] |= (1 << ((pbits + 7) % 8));
1901
0
          raw[(pbits+7)/8 - 1] &= (256 - ctx->h);
1902
0
          a = mpi_is_secure (scalar) ? mpi_snew (pbits): mpi_new (pbits);
1903
0
          _gcry_mpi_set_buffer (a, raw, (n+7)/8, 0);
1904
0
          xfree (raw);
1905
1906
0
          scalar = a;
1907
0
        }
1908
1909
0
      mpi_point_resize (&p1, ctx);
1910
0
      mpi_point_resize (&p2, ctx);
1911
0
      mpi_point_resize (&p1_, ctx);
1912
0
      mpi_point_resize (&p2_, ctx);
1913
1914
0
      mpi_resize (point->x, ctx->p->nlimbs);
1915
0
      point->x->nlimbs = ctx->p->nlimbs;
1916
1917
0
      q1 = &p1;
1918
0
      q2 = &p2;
1919
0
      prd = &p1_;
1920
0
      sum = &p2_;
1921
1922
0
      for (j=nbits-1; j >= 0; j--)
1923
0
        {
1924
0
          mpi_point_t t;
1925
1926
0
          sw = mpi_test_bit (scalar, j);
1927
0
          point_swap_cond (q1, q2, sw, ctx);
1928
0
          montgomery_ladder (prd, sum, q1, q2, point->x, ctx);
1929
0
          point_swap_cond (prd, sum, sw, ctx);
1930
0
          t = q1;  q1 = prd;  prd = t;
1931
0
          t = q2;  q2 = sum;  sum = t;
1932
0
        }
1933
1934
0
      mpi_clear (result->y);
1935
0
      sw = (nbits & 1);
1936
0
      point_swap_cond (&p1, &p1_, sw, ctx);
1937
1938
0
      rsize = p1.z->nlimbs;
1939
0
      MPN_NORMALIZE (p1.z->d, rsize);
1940
0
      if (rsize == 0)
1941
0
        {
1942
0
          mpi_set_ui (result->x, 1);
1943
0
          mpi_set_ui (result->z, 0);
1944
0
        }
1945
0
      else
1946
0
        {
1947
0
          z1 = mpi_new (0);
1948
0
          ec_invm (z1, p1.z, ctx);
1949
0
          ec_mulm (result->x, p1.x, z1, ctx);
1950
0
          mpi_set_ui (result->z, 1);
1951
0
          mpi_free (z1);
1952
0
        }
1953
1954
0
      point_free (&p1);
1955
0
      point_free (&p2);
1956
0
      point_free (&p1_);
1957
0
      point_free (&p2_);
1958
0
      if (scalar_copied)
1959
0
        _gcry_mpi_release (scalar);
1960
0
      return;
1961
0
    }
1962
1963
1.72k
  x1 = mpi_alloc_like (ctx->p);
1964
1.72k
  y1 = mpi_alloc_like (ctx->p);
1965
1.72k
  h  = mpi_alloc_like (ctx->p);
1966
1.72k
  k  = mpi_copy (scalar);
1967
1.72k
  yy = mpi_copy (point->y);
1968
1969
1.72k
  if ( mpi_has_sign (k) )
1970
0
    {
1971
0
      k->sign = 0;
1972
0
      ec_invm (yy, yy, ctx);
1973
0
    }
1974
1975
1.72k
  if (!mpi_cmp_ui (point->z, 1))
1976
1.60k
    {
1977
1.60k
      mpi_set (x1, point->x);
1978
1.60k
      mpi_set (y1, yy);
1979
1.60k
    }
1980
128
  else
1981
128
    {
1982
128
      gcry_mpi_t z2, z3;
1983
1984
128
      z2 = mpi_alloc_like (ctx->p);
1985
128
      z3 = mpi_alloc_like (ctx->p);
1986
128
      ec_mulm (z2, point->z, point->z, ctx);
1987
128
      ec_mulm (z3, point->z, z2, ctx);
1988
128
      ec_invm (z2, z2, ctx);
1989
128
      ec_mulm (x1, point->x, z2, ctx);
1990
128
      ec_invm (z3, z3, ctx);
1991
128
      ec_mulm (y1, yy, z3, ctx);
1992
128
      mpi_free (z2);
1993
128
      mpi_free (z3);
1994
128
    }
1995
1.72k
  z1 = mpi_copy (mpi_const (MPI_C_ONE));
1996
1997
1.72k
  mpi_mul (h, k, mpi_const (MPI_C_THREE)); /* h = 3k */
1998
1.72k
  loops = mpi_get_nbits (h);
1999
1.72k
  if (loops < 2)
2000
21
    {
2001
      /* If SCALAR is zero, the above mpi_mul sets H to zero and thus
2002
         LOOPs will be zero.  To avoid an underflow of I in the main
2003
         loop we set LOOP to 2 and the result to (0,0,0).  */
2004
21
      loops = 2;
2005
21
      mpi_clear (result->x);
2006
21
      mpi_clear (result->y);
2007
21
      mpi_clear (result->z);
2008
21
    }
2009
1.70k
  else
2010
1.70k
    {
2011
1.70k
      mpi_set (result->x, point->x);
2012
1.70k
      mpi_set (result->y, yy);
2013
1.70k
      mpi_set (result->z, point->z);
2014
1.70k
    }
2015
1.72k
  mpi_free (yy); yy = NULL;
2016
2017
1.72k
  p1.x = x1; x1 = NULL;
2018
1.72k
  p1.y = y1; y1 = NULL;
2019
1.72k
  p1.z = z1; z1 = NULL;
2020
1.72k
  point_init (&p2);
2021
1.72k
  point_init (&p1inv);
2022
2023
  /* Invert point: y = p - y mod p  */
2024
1.72k
  point_set (&p1inv, &p1);
2025
1.72k
  ec_subm (p1inv.y, ctx->p, p1inv.y, ctx);
2026
2027
1.03M
  for (i=loops-2; i > 0; i--)
2028
1.02M
    {
2029
1.02M
      _gcry_mpi_ec_dup_point (result, result, ctx);
2030
1.02M
      if (mpi_test_bit (h, i) == 1 && mpi_test_bit (k, i) == 0)
2031
161k
        {
2032
161k
          point_set (&p2, result);
2033
161k
          _gcry_mpi_ec_add_points (result, &p2, &p1, ctx);
2034
161k
        }
2035
1.02M
      if (mpi_test_bit (h, i) == 0 && mpi_test_bit (k, i) == 1)
2036
163k
        {
2037
163k
          point_set (&p2, result);
2038
163k
          _gcry_mpi_ec_add_points (result, &p2, &p1inv, ctx);
2039
163k
        }
2040
1.02M
    }
2041
2042
1.72k
  point_free (&p1);
2043
1.72k
  point_free (&p2);
2044
1.72k
  point_free (&p1inv);
2045
1.72k
  mpi_free (h);
2046
1.72k
  mpi_free (k);
2047
1.72k
}
2048
2049
2050
/* Return true if POINT is on the curve described by CTX.  */
2051
int
2052
_gcry_mpi_ec_curve_point (gcry_mpi_point_t point, mpi_ec_t ctx)
2053
1.69k
{
2054
1.69k
  int res = 0;
2055
1.69k
  gcry_mpi_t x, y, w;
2056
2057
1.69k
  x = mpi_new (0);
2058
1.69k
  y = mpi_new (0);
2059
1.69k
  w = mpi_new (0);
2060
2061
  /* Check that the point is in range.  This needs to be done here and
2062
   * not after conversion to affine coordinates.  */
2063
1.69k
  if (mpi_cmpabs (point->x, ctx->p) >= 0)
2064
158
    goto leave;
2065
1.54k
  if (mpi_cmpabs (point->y, ctx->p) >= 0)
2066
119
    goto leave;
2067
1.42k
  if (mpi_cmpabs (point->z, ctx->p) >= 0)
2068
0
    goto leave;
2069
2070
1.42k
  switch (ctx->model)
2071
1.42k
    {
2072
1.42k
    case MPI_EC_WEIERSTRASS:
2073
1.42k
      {
2074
1.42k
        gcry_mpi_t xxx;
2075
2076
1.42k
        if (_gcry_mpi_ec_get_affine (x, y, point, ctx))
2077
0
          goto leave;
2078
2079
1.42k
        xxx = mpi_new (0);
2080
2081
        /* y^2 == x^3 + a·x + b */
2082
1.42k
        ec_pow2 (y, y, ctx);
2083
2084
1.42k
        ec_pow3 (xxx, x, ctx);
2085
1.42k
        ec_mulm (w, ctx->a, x, ctx);
2086
1.42k
        ec_addm (w, w, ctx->b, ctx);
2087
1.42k
        ec_addm (w, w, xxx, ctx);
2088
2089
1.42k
        if (!mpi_cmp (y, w))
2090
715
          res = 1;
2091
2092
1.42k
        _gcry_mpi_release (xxx);
2093
1.42k
      }
2094
0
      break;
2095
0
    case MPI_EC_MONTGOMERY:
2096
0
      {
2097
0
#define xx y
2098
        /* With Montgomery curve, only X-coordinate is valid.  */
2099
0
        if (_gcry_mpi_ec_get_affine (x, NULL, point, ctx))
2100
0
          goto leave;
2101
2102
        /* The equation is: b * y^2 == x^3 + a · x^2 + x */
2103
        /* We check if right hand is quadratic residue or not by
2104
           Euler's criterion.  */
2105
        /* CTX->A has (a-2)/4 and CTX->B has b^-1 */
2106
0
        ec_mulm (w, ctx->a, mpi_const (MPI_C_FOUR), ctx);
2107
0
        ec_addm (w, w, mpi_const (MPI_C_TWO), ctx);
2108
0
        ec_mulm (w, w, x, ctx);
2109
0
        ec_pow2 (xx, x, ctx);
2110
0
        ec_addm (w, w, xx, ctx);
2111
0
        ec_addm (w, w, mpi_const (MPI_C_ONE), ctx);
2112
0
        ec_mulm (w, w, x, ctx);
2113
0
        ec_mulm (w, w, ctx->b, ctx);
2114
0
#undef xx
2115
        /* Compute Euler's criterion: w^(p-1)/2 */
2116
0
#define p_minus1 y
2117
0
        ec_subm (p_minus1, ctx->p, mpi_const (MPI_C_ONE), ctx);
2118
0
        mpi_rshift (p_minus1, p_minus1, 1);
2119
0
        ec_powm (w, w, p_minus1, ctx);
2120
2121
0
        res = !mpi_cmp_ui (w, 1);
2122
0
#undef p_minus1
2123
0
      }
2124
0
      break;
2125
0
    case MPI_EC_EDWARDS:
2126
0
      {
2127
0
        if (_gcry_mpi_ec_get_affine (x, y, point, ctx))
2128
0
          goto leave;
2129
2130
0
        mpi_resize (w, ctx->p->nlimbs);
2131
0
        w->nlimbs = ctx->p->nlimbs;
2132
2133
        /* a · x^2 + y^2 - 1 - b · x^2 · y^2 == 0 */
2134
0
        ctx->pow2 (x, x, ctx);
2135
0
        ctx->pow2 (y, y, ctx);
2136
0
        if (ctx->dialect == ECC_DIALECT_ED25519)
2137
0
          ctx->subm (w, ctx->p, x, ctx);
2138
0
        else
2139
0
          ctx->mulm (w, ctx->a, x, ctx);
2140
0
        ctx->addm (w, w, y, ctx);
2141
0
        ctx->mulm (x, x, y, ctx);
2142
0
        ctx->mulm (x, x, ctx->b, ctx);
2143
0
        ctx->subm (w, w, x, ctx);
2144
0
        if (!mpi_cmp_ui (w, 1))
2145
0
          res = 1;
2146
0
      }
2147
0
      break;
2148
1.42k
    }
2149
2150
1.69k
 leave:
2151
1.69k
  _gcry_mpi_release (w);
2152
1.69k
  _gcry_mpi_release (x);
2153
1.69k
  _gcry_mpi_release (y);
2154
2155
1.69k
  return res;
2156
1.42k
}
2157
2158
2159
int
2160
_gcry_mpi_ec_bad_point (gcry_mpi_point_t point, mpi_ec_t ctx)
2161
0
{
2162
0
  int i;
2163
0
  gcry_mpi_t x_bad;
2164
2165
0
  for (i = 0; (x_bad = ctx->t.scratch[i]); i++)
2166
0
    if (!mpi_cmp (point->x, x_bad))
2167
0
      return 1;
2168
2169
0
  return 0;
2170
0
}