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