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