ecc: Implement Curve Ed25519 signing and verification.
[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            gcry_mpi_t p, gcry_mpi_t a, gcry_mpi_t b)
435 {
436   int i;
437
438   /* Fixme: Do we want to check some constraints? e.g.  a < p  */
439
440   ctx->model = model;
441   ctx->p = mpi_copy (p);
442   ctx->a = mpi_copy (a);
443   if (b && model == MPI_EC_TWISTEDEDWARDS)
444     ctx->b = mpi_copy (b);
445
446   ec_get_reset (ctx);
447
448   /* Allocate scratch variables.  */
449   for (i=0; i< DIM(ctx->t.scratch); i++)
450     ctx->t.scratch[i] = mpi_alloc_like (ctx->p);
451
452   /* Prepare for fast reduction.  */
453   /* FIXME: need a test for NIST values.  However it does not gain us
454      any real advantage, for 384 bits it is actually slower than using
455      mpi_mulm.  */
456 /*   ctx->nist_nbits = mpi_get_nbits (ctx->p); */
457 /*   if (ctx->nist_nbits == 192) */
458 /*     { */
459 /*       for (i=0; i < 4; i++) */
460 /*         ctx->s[i] = mpi_new (192); */
461 /*       ctx->c    = mpi_new (192*2); */
462 /*     } */
463 /*   else if (ctx->nist_nbits == 384) */
464 /*     { */
465 /*       for (i=0; i < 10; i++) */
466 /*         ctx->s[i] = mpi_new (384); */
467 /*       ctx->c    = mpi_new (384*2); */
468 /*     } */
469 }
470
471
472 static void
473 ec_deinit (void *opaque)
474 {
475   mpi_ec_t ctx = opaque;
476   int i;
477
478   /* Domain parameter.  */
479   mpi_free (ctx->p);
480   mpi_free (ctx->a);
481   mpi_free (ctx->b);
482   gcry_mpi_point_release (ctx->G);
483   mpi_free (ctx->n);
484
485   /* The key.  */
486   gcry_mpi_point_release (ctx->Q);
487   mpi_free (ctx->d);
488
489   /* Private data of ec.c.  */
490   mpi_free (ctx->t.two_inv_p);
491
492   for (i=0; i< DIM(ctx->t.scratch); i++)
493     mpi_free (ctx->t.scratch[i]);
494
495 /*   if (ctx->nist_nbits == 192) */
496 /*     { */
497 /*       for (i=0; i < 4; i++) */
498 /*         mpi_free (ctx->s[i]); */
499 /*       mpi_free (ctx->c); */
500 /*     } */
501 /*   else if (ctx->nist_nbits == 384) */
502 /*     { */
503 /*       for (i=0; i < 10; i++) */
504 /*         mpi_free (ctx->s[i]); */
505 /*       mpi_free (ctx->c); */
506 /*     } */
507 }
508
509
510 /* This function returns a new context for elliptic curve based on the
511    field GF(p).  P is the prime specifying this field, A is the first
512    coefficient, B is the second coefficient, and MODEL is the model
513    for the curve.  This function is only used within Libgcrypt and not
514    part of the public API.
515
516    This context needs to be released using _gcry_mpi_ec_free.  */
517 mpi_ec_t
518 _gcry_mpi_ec_p_internal_new (enum gcry_mpi_ec_models model,
519                              gcry_mpi_t p, gcry_mpi_t a, gcry_mpi_t b)
520 {
521   mpi_ec_t ctx;
522
523   ctx = gcry_xcalloc (1, sizeof *ctx);
524   ec_p_init (ctx, model, p, a, b);
525
526   return ctx;
527 }
528
529
530 /* This is a variant of _gcry_mpi_ec_p_internal_new which returns an
531    public contect and does some error checking on the supplied
532    arguments.  On success the new context is stored at R_CTX and 0 is
533    returned; on error NULL is stored at R_CTX and an error code is
534    returned.
535
536    The context needs to be released using gcry_ctx_release.  */
537 gpg_err_code_t
538 _gcry_mpi_ec_p_new (gcry_ctx_t *r_ctx,
539                     enum gcry_mpi_ec_models model,
540                     gcry_mpi_t p, gcry_mpi_t a, gcry_mpi_t b)
541 {
542   gcry_ctx_t ctx;
543   mpi_ec_t ec;
544
545   *r_ctx = NULL;
546   if (!p || !a || !mpi_cmp_ui (a, 0))
547     return GPG_ERR_EINVAL;
548
549   ctx = _gcry_ctx_alloc (CONTEXT_TYPE_EC, sizeof *ec, ec_deinit);
550   if (!ctx)
551     return gpg_err_code_from_syserror ();
552   ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
553   ec_p_init (ec, model, p, a, b);
554
555   *r_ctx = ctx;
556   return 0;
557 }
558
559
560 void
561 _gcry_mpi_ec_free (mpi_ec_t ctx)
562 {
563   if (ctx)
564     {
565       ec_deinit (ctx);
566       gcry_free (ctx);
567     }
568 }
569
570
571 gcry_mpi_t
572 _gcry_mpi_ec_get_mpi (const char *name, gcry_ctx_t ctx, int copy)
573 {
574   mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
575
576   if (!strcmp (name, "p") && ec->p)
577     return mpi_is_const (ec->p) && !copy? ec->p : mpi_copy (ec->p);
578   if (!strcmp (name, "a") && ec->a)
579     return mpi_is_const (ec->a) && !copy? ec->a : mpi_copy (ec->a);
580   if (!strcmp (name, "b") && ec->b)
581     return mpi_is_const (ec->b) && !copy? ec->b : mpi_copy (ec->b);
582   if (!strcmp (name, "n") && ec->n)
583     return mpi_is_const (ec->n) && !copy? ec->n : mpi_copy (ec->n);
584   if (!strcmp (name, "d") && ec->d)
585     return mpi_is_const (ec->d) && !copy? ec->d : mpi_copy (ec->d);
586
587   /* Return a requested point coordinate.  */
588   if (!strcmp (name, "g.x") && ec->G && ec->G->x)
589     return mpi_is_const (ec->G->x) && !copy? ec->G->x : mpi_copy (ec->G->x);
590   if (!strcmp (name, "g.y") && ec->G && ec->G->y)
591     return mpi_is_const (ec->G->y) && !copy? ec->G->y : mpi_copy (ec->G->y);
592   if (!strcmp (name, "q.x") && ec->Q && ec->Q->x)
593     return mpi_is_const (ec->Q->x) && !copy? ec->Q->x : mpi_copy (ec->Q->x);
594   if (!strcmp (name, "q.y") && ec->Q && ec->Q->y)
595     return mpi_is_const (ec->G->y) && !copy? ec->Q->y : mpi_copy (ec->Q->y);
596
597   /* If a point has been requested, return it in standard encoding.  */
598   if (!strcmp (name, "g") && ec->G)
599     return _gcry_mpi_ec_ec2os (ec->G, ec);
600   if (!strcmp (name, "q"))
601     {
602       /* If only the private key is given, compute the public key.  */
603       if (!ec->Q && ec->d && ec->G && ec->p && ec->a)
604         {
605           ec->Q = gcry_mpi_point_new (0);
606           _gcry_mpi_ec_mul_point (ec->Q, ec->d, ec->G, ec);
607         }
608
609       if (ec->Q)
610         return _gcry_mpi_ec_ec2os (ec->Q, ec);
611     }
612
613   return NULL;
614 }
615
616
617 gcry_mpi_point_t
618 _gcry_mpi_ec_get_point (const char *name, gcry_ctx_t ctx, int copy)
619 {
620   mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
621
622   (void)copy;  /* Not used.  */
623
624   if (!strcmp (name, "g") && ec->G)
625     return point_copy (ec->G);
626   if (!strcmp (name, "q"))
627     {
628       /* If only the private key is given, compute the public key.  */
629       if (!ec->Q && ec->d && ec->G && ec->p && ec->a)
630         {
631           ec->Q = gcry_mpi_point_new (0);
632           _gcry_mpi_ec_mul_point (ec->Q, ec->d, ec->G, ec);
633         }
634
635       if (ec->Q)
636         return point_copy (ec->Q);
637     }
638
639   return NULL;
640 }
641
642
643 gpg_err_code_t
644 _gcry_mpi_ec_set_mpi (const char *name, gcry_mpi_t newvalue,
645                       gcry_ctx_t ctx)
646 {
647   mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
648
649   if (!strcmp (name, "p"))
650     {
651       mpi_free (ec->p);
652       ec->p = mpi_copy (newvalue);
653       ec_get_reset (ec);
654     }
655   else if (!strcmp (name, "a"))
656     {
657       mpi_free (ec->a);
658       ec->a = mpi_copy (newvalue);
659       ec_get_reset (ec);
660     }
661   else if (!strcmp (name, "b"))
662     {
663       mpi_free (ec->b);
664       ec->b = mpi_copy (newvalue);
665     }
666   else if (!strcmp (name, "n"))
667     {
668       mpi_free (ec->n);
669       ec->n = mpi_copy (newvalue);
670     }
671   else if (!strcmp (name, "d"))
672     {
673       mpi_free (ec->d);
674       ec->d = mpi_copy (newvalue);
675     }
676   else
677     return GPG_ERR_UNKNOWN_NAME;
678
679   return 0;
680 }
681
682
683 gpg_err_code_t
684 _gcry_mpi_ec_set_point (const char *name, gcry_mpi_point_t newvalue,
685                         gcry_ctx_t ctx)
686 {
687   mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
688
689   if (!strcmp (name, "g"))
690     {
691       gcry_mpi_point_release (ec->G);
692       ec->G = point_copy (newvalue);
693     }
694   else if (!strcmp (name, "q"))
695     {
696       gcry_mpi_point_release (ec->Q);
697       ec->Q = point_copy (newvalue);
698     }
699   else
700     return GPG_ERR_UNKNOWN_NAME;
701
702   return 0;
703 }
704
705
706 /* Compute the affine coordinates from the projective coordinates in
707    POINT.  Set them into X and Y.  If one coordinate is not required,
708    X or Y may be passed as NULL.  CTX is the usual context. Returns: 0
709    on success or !0 if POINT is at infinity.  */
710 int
711 _gcry_mpi_ec_get_affine (gcry_mpi_t x, gcry_mpi_t y, mpi_point_t point,
712                          mpi_ec_t ctx)
713 {
714   if (!mpi_cmp_ui (point->z, 0))
715     return -1;
716
717   switch (ctx->model)
718     {
719     case MPI_EC_WEIERSTRASS: /* Using Jacobian coordinates.  */
720       {
721         gcry_mpi_t z1, z2, z3;
722
723         z1 = mpi_new (0);
724         z2 = mpi_new (0);
725         ec_invm (z1, point->z, ctx);  /* z1 = z^(-1) mod p  */
726         ec_mulm (z2, z1, z1, ctx);    /* z2 = z^(-2) mod p  */
727
728         if (x)
729           ec_mulm (x, point->x, z2, ctx);
730
731         if (y)
732           {
733             z3 = mpi_new (0);
734             ec_mulm (z3, z2, z1, ctx);      /* z3 = z^(-3) mod p  */
735             ec_mulm (y, point->y, z3, ctx);
736             mpi_free (z3);
737           }
738
739         mpi_free (z2);
740         mpi_free (z1);
741       }
742       return 0;
743
744     case MPI_EC_MONTGOMERY:
745       {
746         log_fatal ("%s: %s not yet supported\n",
747                    "_gcry_mpi_ec_get_affine", "Montgomery");
748       }
749       return -1;
750
751     case MPI_EC_TWISTEDEDWARDS:
752       {
753         gcry_mpi_t z;
754
755         z = mpi_new (0);
756         ec_invm (z, point->z, ctx);
757
758         if (x)
759           ec_mulm (x, point->x, z, ctx);
760         if (y)
761           ec_mulm (y, point->y, z, ctx);
762
763         gcry_mpi_release (z);
764       }
765       return 0;
766
767     default:
768       return -1;
769     }
770 }
771
772
773 \f
774 /*  RESULT = 2 * POINT  (Weierstrass version). */
775 static void
776 dup_point_weierstrass (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
777 {
778 #define x3 (result->x)
779 #define y3 (result->y)
780 #define z3 (result->z)
781 #define t1 (ctx->t.scratch[0])
782 #define t2 (ctx->t.scratch[1])
783 #define t3 (ctx->t.scratch[2])
784 #define l1 (ctx->t.scratch[3])
785 #define l2 (ctx->t.scratch[4])
786 #define l3 (ctx->t.scratch[5])
787
788   if (!mpi_cmp_ui (point->y, 0) || !mpi_cmp_ui (point->z, 0))
789     {
790       /* P_y == 0 || P_z == 0 => [1:1:0] */
791       mpi_set_ui (x3, 1);
792       mpi_set_ui (y3, 1);
793       mpi_set_ui (z3, 0);
794     }
795   else
796     {
797       if (ec_get_a_is_pminus3 (ctx))  /* Use the faster case.  */
798         {
799           /* L1 = 3(X - Z^2)(X + Z^2) */
800           /*                          T1: used for Z^2. */
801           /*                          T2: used for the right term.  */
802           ec_powm (t1, point->z, mpi_const (MPI_C_TWO), ctx);
803           ec_subm (l1, point->x, t1, ctx);
804           ec_mulm (l1, l1, mpi_const (MPI_C_THREE), ctx);
805           ec_addm (t2, point->x, t1, ctx);
806           ec_mulm (l1, l1, t2, ctx);
807         }
808       else /* Standard case. */
809         {
810           /* L1 = 3X^2 + aZ^4 */
811           /*                          T1: used for aZ^4. */
812           ec_powm (l1, point->x, mpi_const (MPI_C_TWO), ctx);
813           ec_mulm (l1, l1, mpi_const (MPI_C_THREE), ctx);
814           ec_powm (t1, point->z, mpi_const (MPI_C_FOUR), ctx);
815           ec_mulm (t1, t1, ctx->a, ctx);
816           ec_addm (l1, l1, t1, ctx);
817         }
818       /* Z3 = 2YZ */
819       ec_mulm (z3, point->y, point->z, ctx);
820       ec_mulm (z3, z3, mpi_const (MPI_C_TWO), ctx);
821
822       /* L2 = 4XY^2 */
823       /*                              T2: used for Y2; required later. */
824       ec_powm (t2, point->y, mpi_const (MPI_C_TWO), ctx);
825       ec_mulm (l2, t2, point->x, ctx);
826       ec_mulm (l2, l2, mpi_const (MPI_C_FOUR), ctx);
827
828       /* X3 = L1^2 - 2L2 */
829       /*                              T1: used for L2^2. */
830       ec_powm (x3, l1, mpi_const (MPI_C_TWO), ctx);
831       ec_mulm (t1, l2, mpi_const (MPI_C_TWO), ctx);
832       ec_subm (x3, x3, t1, ctx);
833
834       /* L3 = 8Y^4 */
835       /*                              T2: taken from above. */
836       ec_powm (t2, t2, mpi_const (MPI_C_TWO), ctx);
837       ec_mulm (l3, t2, mpi_const (MPI_C_EIGHT), ctx);
838
839       /* Y3 = L1(L2 - X3) - L3 */
840       ec_subm (y3, l2, x3, ctx);
841       ec_mulm (y3, y3, l1, ctx);
842       ec_subm (y3, y3, l3, ctx);
843     }
844
845 #undef x3
846 #undef y3
847 #undef z3
848 #undef t1
849 #undef t2
850 #undef t3
851 #undef l1
852 #undef l2
853 #undef l3
854 }
855
856
857 /*  RESULT = 2 * POINT  (Montgomery version). */
858 static void
859 dup_point_montgomery (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
860 {
861   (void)result;
862   (void)point;
863   (void)ctx;
864   log_fatal ("%s: %s not yet supported\n",
865              "_gcry_mpi_ec_dup_point", "Montgomery");
866 }
867
868
869 /*  RESULT = 2 * POINT  (Twisted Edwards version). */
870 static void
871 dup_point_twistededwards (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
872 {
873 #define X1 (point->x)
874 #define Y1 (point->y)
875 #define Z1 (point->z)
876 #define X3 (result->x)
877 #define Y3 (result->y)
878 #define Z3 (result->z)
879 #define B (ctx->t.scratch[0])
880 #define C (ctx->t.scratch[1])
881 #define D (ctx->t.scratch[2])
882 #define E (ctx->t.scratch[3])
883 #define F (ctx->t.scratch[4])
884 #define H (ctx->t.scratch[5])
885 #define J (ctx->t.scratch[6])
886
887   /* Compute: (X_3 : Y_3 : Z_3) = 2( X_1 : Y_1 : Z_1 ) */
888
889   /* B = (X_1 + Y_1)^2  */
890   ec_addm (B, X1, Y1, ctx);
891   ec_powm (B, B, mpi_const (MPI_C_TWO), ctx);
892
893   /* C = X_1^2 */
894   /* D = Y_1^2 */
895   ec_powm (C, X1, mpi_const (MPI_C_TWO), ctx);
896   ec_powm (D, Y1, mpi_const (MPI_C_TWO), ctx);
897
898   /* E = aC */
899   ec_mulm (E, ctx->a, C, ctx);
900
901   /* F = E + D */
902   ec_addm (F, E, D, ctx);
903
904   /* H = Z_1^2 */
905   ec_powm (H, Z1, mpi_const (MPI_C_TWO), ctx);
906
907   /* J = F - 2H */
908   ec_mulm (J, H, mpi_const (MPI_C_TWO), ctx);
909   ec_subm (J, F, J, ctx);
910
911   /* X_3 = (B - C - D) · J */
912   ec_subm (X3, B, C, ctx);
913   ec_subm (X3, X3, D, ctx);
914   ec_mulm (X3, X3, J, ctx);
915
916   /* Y_3 = F · (E - D) */
917   ec_subm (Y3, E, D, ctx);
918   ec_mulm (Y3, Y3, F, ctx);
919
920   /* Z_3 = F · J */
921   ec_mulm (Z3, F, J, ctx);
922
923 #undef X1
924 #undef Y1
925 #undef Z1
926 #undef X3
927 #undef Y3
928 #undef Z3
929 #undef B
930 #undef C
931 #undef D
932 #undef E
933 #undef F
934 #undef H
935 #undef J
936 }
937
938
939 /*  RESULT = 2 * POINT  */
940 void
941 _gcry_mpi_ec_dup_point (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
942 {
943   switch (ctx->model)
944     {
945     case MPI_EC_WEIERSTRASS:
946       dup_point_weierstrass (result, point, ctx);
947       break;
948     case MPI_EC_MONTGOMERY:
949       dup_point_montgomery (result, point, ctx);
950       break;
951     case MPI_EC_TWISTEDEDWARDS:
952       dup_point_twistededwards (result, point, ctx);
953       break;
954     }
955 }
956
957
958 /* RESULT = P1 + P2  (Weierstrass version).*/
959 static void
960 add_points_weierstrass (mpi_point_t result,
961                         mpi_point_t p1, mpi_point_t p2,
962                         mpi_ec_t ctx)
963 {
964 #define x1 (p1->x    )
965 #define y1 (p1->y    )
966 #define z1 (p1->z    )
967 #define x2 (p2->x    )
968 #define y2 (p2->y    )
969 #define z2 (p2->z    )
970 #define x3 (result->x)
971 #define y3 (result->y)
972 #define z3 (result->z)
973 #define l1 (ctx->t.scratch[0])
974 #define l2 (ctx->t.scratch[1])
975 #define l3 (ctx->t.scratch[2])
976 #define l4 (ctx->t.scratch[3])
977 #define l5 (ctx->t.scratch[4])
978 #define l6 (ctx->t.scratch[5])
979 #define l7 (ctx->t.scratch[6])
980 #define l8 (ctx->t.scratch[7])
981 #define l9 (ctx->t.scratch[8])
982 #define t1 (ctx->t.scratch[9])
983 #define t2 (ctx->t.scratch[10])
984
985   if ( (!mpi_cmp (x1, x2)) && (!mpi_cmp (y1, y2)) && (!mpi_cmp (z1, z2)) )
986     {
987       /* Same point; need to call the duplicate function.  */
988       _gcry_mpi_ec_dup_point (result, p1, ctx);
989     }
990   else if (!mpi_cmp_ui (z1, 0))
991     {
992       /* P1 is at infinity.  */
993       mpi_set (x3, p2->x);
994       mpi_set (y3, p2->y);
995       mpi_set (z3, p2->z);
996     }
997   else if (!mpi_cmp_ui (z2, 0))
998     {
999       /* P2 is at infinity.  */
1000       mpi_set (x3, p1->x);
1001       mpi_set (y3, p1->y);
1002       mpi_set (z3, p1->z);
1003     }
1004   else
1005     {
1006       int z1_is_one = !mpi_cmp_ui (z1, 1);
1007       int z2_is_one = !mpi_cmp_ui (z2, 1);
1008
1009       /* l1 = x1 z2^2  */
1010       /* l2 = x2 z1^2  */
1011       if (z2_is_one)
1012         mpi_set (l1, x1);
1013       else
1014         {
1015           ec_powm (l1, z2, mpi_const (MPI_C_TWO), ctx);
1016           ec_mulm (l1, l1, x1, ctx);
1017         }
1018       if (z1_is_one)
1019         mpi_set (l2, x2);
1020       else
1021         {
1022           ec_powm (l2, z1, mpi_const (MPI_C_TWO), ctx);
1023           ec_mulm (l2, l2, x2, ctx);
1024         }
1025       /* l3 = l1 - l2 */
1026       ec_subm (l3, l1, l2, ctx);
1027       /* l4 = y1 z2^3  */
1028       ec_powm (l4, z2, mpi_const (MPI_C_THREE), ctx);
1029       ec_mulm (l4, l4, y1, ctx);
1030       /* l5 = y2 z1^3  */
1031       ec_powm (l5, z1, mpi_const (MPI_C_THREE), ctx);
1032       ec_mulm (l5, l5, y2, ctx);
1033       /* l6 = l4 - l5  */
1034       ec_subm (l6, l4, l5, ctx);
1035
1036       if (!mpi_cmp_ui (l3, 0))
1037         {
1038           if (!mpi_cmp_ui (l6, 0))
1039             {
1040               /* P1 and P2 are the same - use duplicate function.  */
1041               _gcry_mpi_ec_dup_point (result, p1, ctx);
1042             }
1043           else
1044             {
1045               /* P1 is the inverse of P2.  */
1046               mpi_set_ui (x3, 1);
1047               mpi_set_ui (y3, 1);
1048               mpi_set_ui (z3, 0);
1049             }
1050         }
1051       else
1052         {
1053           /* l7 = l1 + l2  */
1054           ec_addm (l7, l1, l2, ctx);
1055           /* l8 = l4 + l5  */
1056           ec_addm (l8, l4, l5, ctx);
1057           /* z3 = z1 z2 l3  */
1058           ec_mulm (z3, z1, z2, ctx);
1059           ec_mulm (z3, z3, l3, ctx);
1060           /* x3 = l6^2 - l7 l3^2  */
1061           ec_powm (t1, l6, mpi_const (MPI_C_TWO), ctx);
1062           ec_powm (t2, l3, mpi_const (MPI_C_TWO), ctx);
1063           ec_mulm (t2, t2, l7, ctx);
1064           ec_subm (x3, t1, t2, ctx);
1065           /* l9 = l7 l3^2 - 2 x3  */
1066           ec_mulm (t1, x3, mpi_const (MPI_C_TWO), ctx);
1067           ec_subm (l9, t2, t1, ctx);
1068           /* y3 = (l9 l6 - l8 l3^3)/2  */
1069           ec_mulm (l9, l9, l6, ctx);
1070           ec_powm (t1, l3, mpi_const (MPI_C_THREE), ctx); /* fixme: Use saved value*/
1071           ec_mulm (t1, t1, l8, ctx);
1072           ec_subm (y3, l9, t1, ctx);
1073           ec_mulm (y3, y3, ec_get_two_inv_p (ctx), ctx);
1074         }
1075     }
1076
1077 #undef x1
1078 #undef y1
1079 #undef z1
1080 #undef x2
1081 #undef y2
1082 #undef z2
1083 #undef x3
1084 #undef y3
1085 #undef z3
1086 #undef l1
1087 #undef l2
1088 #undef l3
1089 #undef l4
1090 #undef l5
1091 #undef l6
1092 #undef l7
1093 #undef l8
1094 #undef l9
1095 #undef t1
1096 #undef t2
1097 }
1098
1099
1100 /* RESULT = P1 + P2  (Montgomery version).*/
1101 static void
1102 add_points_montgomery (mpi_point_t result,
1103                        mpi_point_t p1, mpi_point_t p2,
1104                        mpi_ec_t ctx)
1105 {
1106   (void)result;
1107   (void)p1;
1108   (void)p2;
1109   (void)ctx;
1110   log_fatal ("%s: %s not yet supported\n",
1111              "_gcry_mpi_ec_add_points", "Montgomery");
1112 }
1113
1114
1115 /* RESULT = P1 + P2  (Twisted Edwards version).*/
1116 static void
1117 add_points_twistededwards (mpi_point_t result,
1118                            mpi_point_t p1, mpi_point_t p2,
1119                            mpi_ec_t ctx)
1120 {
1121 #define X1 (p1->x)
1122 #define Y1 (p1->y)
1123 #define Z1 (p1->z)
1124 #define X2 (p2->x)
1125 #define Y2 (p2->y)
1126 #define Z2 (p2->z)
1127 #define X3 (result->x)
1128 #define Y3 (result->y)
1129 #define Z3 (result->z)
1130 #define A (ctx->t.scratch[0])
1131 #define B (ctx->t.scratch[1])
1132 #define C (ctx->t.scratch[2])
1133 #define D (ctx->t.scratch[3])
1134 #define E (ctx->t.scratch[4])
1135 #define F (ctx->t.scratch[5])
1136 #define G (ctx->t.scratch[6])
1137 #define tmp (ctx->t.scratch[7])
1138
1139   /* Compute: (X_3 : Y_3 : Z_3) = (X_1 : Y_1 : Z_1) + (X_2 : Y_2 : Z_3)  */
1140
1141   /* A = Z1 · Z2 */
1142   ec_mulm (A, Z1, Z2, ctx);
1143
1144   /* B = A^2 */
1145   ec_powm (B, A, mpi_const (MPI_C_TWO), ctx);
1146
1147   /* C = X1 · X2 */
1148   ec_mulm (C, X1, X2, ctx);
1149
1150   /* D = Y1 · Y2 */
1151   ec_mulm (D, Y1, Y2, ctx);
1152
1153   /* E = d · C · D */
1154   ec_mulm (E, ctx->b, C, ctx);
1155   ec_mulm (E, E, D, ctx);
1156
1157   /* F = B - E */
1158   ec_subm (F, B, E, ctx);
1159
1160   /* G = B + E */
1161   ec_addm (G, B, E, ctx);
1162
1163   /* X_3 = A · F · ((X_1 + Y_1) · (X_2 + Y_2) - C - D) */
1164   ec_addm (tmp, X1, Y1, ctx);
1165   ec_addm (X3, X2, Y2, ctx);
1166   ec_mulm (X3, X3, tmp, ctx);
1167   ec_subm (X3, X3, C, ctx);
1168   ec_subm (X3, X3, D, ctx);
1169   ec_mulm (X3, X3, F, ctx);
1170   ec_mulm (X3, X3, A, ctx);
1171
1172   /* Y_3 = A · G · (D - aC) */
1173   ec_mulm (Y3, ctx->a, C, ctx);
1174   ec_subm (Y3, D, Y3, ctx);
1175   ec_mulm (Y3, Y3, G, ctx);
1176   ec_mulm (Y3, Y3, A, ctx);
1177
1178   /* Z_3 = F · G */
1179   ec_mulm (Z3, F, G, ctx);
1180
1181
1182 #undef X1
1183 #undef Y1
1184 #undef Z1
1185 #undef X2
1186 #undef Y2
1187 #undef Z2
1188 #undef X3
1189 #undef Y3
1190 #undef Z3
1191 #undef A
1192 #undef B
1193 #undef C
1194 #undef D
1195 #undef E
1196 #undef F
1197 #undef G
1198 #undef tmp
1199 }
1200
1201
1202 /* RESULT = P1 + P2 */
1203 void
1204 _gcry_mpi_ec_add_points (mpi_point_t result,
1205                          mpi_point_t p1, mpi_point_t p2,
1206                          mpi_ec_t ctx)
1207 {
1208   switch (ctx->model)
1209     {
1210     case MPI_EC_WEIERSTRASS:
1211       add_points_weierstrass (result, p1, p2, ctx);
1212       break;
1213     case MPI_EC_MONTGOMERY:
1214       add_points_montgomery (result, p1, p2, ctx);
1215       break;
1216     case MPI_EC_TWISTEDEDWARDS:
1217       add_points_twistededwards (result, p1, p2, ctx);
1218       break;
1219     }
1220 }
1221
1222
1223 /* Scalar point multiplication - the main function for ECC.  If takes
1224    an integer SCALAR and a POINT as well as the usual context CTX.
1225    RESULT will be set to the resulting point. */
1226 void
1227 _gcry_mpi_ec_mul_point (mpi_point_t result,
1228                         gcry_mpi_t scalar, mpi_point_t point,
1229                         mpi_ec_t ctx)
1230 {
1231   gcry_mpi_t x1, y1, z1, k, h, yy;
1232   unsigned int i, loops;
1233   mpi_point_struct p1, p2, p1inv;
1234
1235   if (ctx->model == MPI_EC_TWISTEDEDWARDS)
1236     {
1237       /* Simple left to right binary method.  GECC Algorithm 3.27 */
1238       unsigned int nbits;
1239       int j;
1240
1241       nbits = mpi_get_nbits (scalar);
1242       mpi_set_ui (result->x, 0);
1243       mpi_set_ui (result->y, 1);
1244       mpi_set_ui (result->z, 1);
1245
1246       for (j=nbits-1; j >= 0; j--)
1247         {
1248           _gcry_mpi_ec_dup_point (result, result, ctx);
1249           if (mpi_test_bit (scalar, j) == 1)
1250             _gcry_mpi_ec_add_points (result, result, point, ctx);
1251         }
1252       return;
1253     }
1254
1255   x1 = mpi_alloc_like (ctx->p);
1256   y1 = mpi_alloc_like (ctx->p);
1257   h  = mpi_alloc_like (ctx->p);
1258   k  = mpi_copy (scalar);
1259   yy = mpi_copy (point->y);
1260
1261   if ( mpi_has_sign (k) )
1262     {
1263       k->sign = 0;
1264       ec_invm (yy, yy, ctx);
1265     }
1266
1267   if (!mpi_cmp_ui (point->z, 1))
1268     {
1269       mpi_set (x1, point->x);
1270       mpi_set (y1, yy);
1271     }
1272   else
1273     {
1274       gcry_mpi_t z2, z3;
1275
1276       z2 = mpi_alloc_like (ctx->p);
1277       z3 = mpi_alloc_like (ctx->p);
1278       ec_mulm (z2, point->z, point->z, ctx);
1279       ec_mulm (z3, point->z, z2, ctx);
1280       ec_invm (z2, z2, ctx);
1281       ec_mulm (x1, point->x, z2, ctx);
1282       ec_invm (z3, z3, ctx);
1283       ec_mulm (y1, yy, z3, ctx);
1284       mpi_free (z2);
1285       mpi_free (z3);
1286     }
1287   z1 = mpi_copy (mpi_const (MPI_C_ONE));
1288
1289   mpi_mul (h, k, mpi_const (MPI_C_THREE)); /* h = 3k */
1290   loops = mpi_get_nbits (h);
1291   if (loops < 2)
1292     {
1293       /* If SCALAR is zero, the above mpi_mul sets H to zero and thus
1294          LOOPs will be zero.  To avoid an underflow of I in the main
1295          loop we set LOOP to 2 and the result to (0,0,0).  */
1296       loops = 2;
1297       mpi_clear (result->x);
1298       mpi_clear (result->y);
1299       mpi_clear (result->z);
1300     }
1301   else
1302     {
1303       mpi_set (result->x, point->x);
1304       mpi_set (result->y, yy);
1305       mpi_set (result->z, point->z);
1306     }
1307   mpi_free (yy); yy = NULL;
1308
1309   p1.x = x1; x1 = NULL;
1310   p1.y = y1; y1 = NULL;
1311   p1.z = z1; z1 = NULL;
1312   point_init (&p2);
1313   point_init (&p1inv);
1314
1315   for (i=loops-2; i > 0; i--)
1316     {
1317       _gcry_mpi_ec_dup_point (result, result, ctx);
1318       if (mpi_test_bit (h, i) == 1 && mpi_test_bit (k, i) == 0)
1319         {
1320           point_set (&p2, result);
1321           _gcry_mpi_ec_add_points (result, &p2, &p1, ctx);
1322         }
1323       if (mpi_test_bit (h, i) == 0 && mpi_test_bit (k, i) == 1)
1324         {
1325           point_set (&p2, result);
1326           /* Invert point: y = p - y mod p  */
1327           point_set (&p1inv, &p1);
1328           ec_subm (p1inv.y, ctx->p, p1inv.y, ctx);
1329           _gcry_mpi_ec_add_points (result, &p2, &p1inv, ctx);
1330         }
1331     }
1332
1333   point_free (&p1);
1334   point_free (&p2);
1335   point_free (&p1inv);
1336   mpi_free (h);
1337   mpi_free (k);
1338 }
1339
1340
1341 /* Return true if POINT is on the curve described by CTX.  */
1342 int
1343 _gcry_mpi_ec_curve_point (gcry_mpi_point_t point, mpi_ec_t ctx)
1344 {
1345   int res = 0;
1346   gcry_mpi_t x, y, w;
1347
1348   x = mpi_new (0);
1349   y = mpi_new (0);
1350   w = mpi_new (0);
1351
1352   if (_gcry_mpi_ec_get_affine (x, y, point, ctx))
1353     return 0;
1354
1355   switch (ctx->model)
1356     {
1357     case MPI_EC_WEIERSTRASS:
1358       log_fatal ("%s: %s not yet supported\n",
1359                  "_gcry_mpi_ec_curve_point", "Weierstrass");
1360       break;
1361     case MPI_EC_MONTGOMERY:
1362       log_fatal ("%s: %s not yet supported\n",
1363                  "_gcry_mpi_ec_curve_point", "Montgomery");
1364       break;
1365     case MPI_EC_TWISTEDEDWARDS:
1366       {
1367         /* a · x^2 + y^2 - 1 - b · x^2 · y^2 == 0 */
1368         ec_powm (x, x, mpi_const (MPI_C_TWO), ctx);
1369         ec_powm (y, y, mpi_const (MPI_C_TWO), ctx);
1370         ec_mulm (w, ctx->a, x, ctx);
1371         ec_addm (w, w, y, ctx);
1372         ec_subm (w, w, mpi_const (MPI_C_ONE), ctx);
1373         ec_mulm (x, x, y, ctx);
1374         ec_mulm (x, x, ctx->b, ctx);
1375         ec_subm (w, w, x, ctx);
1376         if (!mpi_cmp_ui (w, 0))
1377           res = 1;
1378       }
1379       break;
1380     }
1381
1382   gcry_mpi_release (w);
1383   gcry_mpi_release (x);
1384   gcry_mpi_release (y);
1385
1386   return res;
1387 }