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