ecc: Improve Montgomery curve implementation.
[libgcrypt.git] / cipher / ecc.c
1 /* ecc.c  -  Elliptic Curve Cryptography
2  * Copyright (C) 2007, 2008, 2010, 2011 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 /* This code is originally based on the Patch 0.1.6 for the gnupg
22    1.4.x branch as retrieved on 2007-03-21 from
23    http://www.calcurco.cat/eccGnuPG/src/gnupg-1.4.6-ecc0.2.0beta1.diff.bz2
24    The original authors are:
25      Written by
26       Sergi Blanch i Torne <d4372211 at alumnes.eup.udl.es>,
27       Ramiro Moreno Chiral <ramiro at eup.udl.es>
28      Maintainers
29       Sergi Blanch i Torne
30       Ramiro Moreno Chiral
31       Mikael Mylnikov (mmr)
32   For use in Libgcrypt the code has been heavily modified and cleaned
33   up. In fact there is not much left of the orginally code except for
34   some variable names and the text book implementaion of the sign and
35   verification algorithms.  The arithmetic functions have entirely
36   been rewritten and moved to mpi/ec.c.
37
38   ECDH encrypt and decrypt code written by Andrey Jivsov.
39 */
40
41
42 /* TODO:
43
44   - In mpi/ec.c we use mpi_powm for x^2 mod p: Either implement a
45     special case in mpi_powm or check whether mpi_mulm is faster.
46
47 */
48
49
50 #include <config.h>
51 #include <stdio.h>
52 #include <stdlib.h>
53 #include <string.h>
54 #include <errno.h>
55
56 #include "g10lib.h"
57 #include "mpi.h"
58 #include "cipher.h"
59 #include "context.h"
60 #include "ec-context.h"
61 #include "pubkey-internal.h"
62 #include "ecc-common.h"
63
64
65 static const char *ecc_names[] =
66   {
67     "ecc",
68     "ecdsa",
69     "ecdh",
70     "eddsa",
71     "gost",
72     NULL,
73   };
74
75
76 /* Registered progress function and its callback value. */
77 static void (*progress_cb) (void *, const char*, int, int, int);
78 static void *progress_cb_data;
79
80
81 \f
82 /* Local prototypes. */
83 static void test_keys (ECC_secret_key * sk, unsigned int nbits);
84 static void test_ecdh_only_keys (ECC_secret_key * sk, unsigned int nbits);
85 static unsigned int ecc_get_nbits (gcry_sexp_t parms);
86
87
88
89 \f
90 void
91 _gcry_register_pk_ecc_progress (void (*cb) (void *, const char *,
92                                             int, int, int),
93                                 void *cb_data)
94 {
95   progress_cb = cb;
96   progress_cb_data = cb_data;
97 }
98
99 /* static void */
100 /* progress (int c) */
101 /* { */
102 /*   if (progress_cb) */
103 /*     progress_cb (progress_cb_data, "pk_ecc", c, 0, 0); */
104 /* } */
105
106
107 \f
108 /* Standard version of the key generation.  */
109 static gpg_err_code_t
110 nist_generate_key (ECC_secret_key *sk, elliptic_curve_t *E, mpi_ec_t ctx,
111                    gcry_random_level_t random_level, unsigned int nbits)
112 {
113   mpi_point_struct Q;
114
115   point_init (&Q);
116
117   /* Generate a secret.  */
118   if (ctx->dialect == ECC_DIALECT_ED25519)
119     {
120       char *rndbuf;
121
122       sk->d = mpi_snew (256);
123       rndbuf = _gcry_random_bytes_secure (32, random_level);
124       rndbuf[0] &= 0x7f;  /* Clear bit 255. */
125       rndbuf[0] |= 0x40;  /* Set bit 254.   */
126       rndbuf[31] &= 0xf8; /* Clear bits 2..0 so that d mod 8 == 0  */
127       _gcry_mpi_set_buffer (sk->d, rndbuf, 32, 0);
128       xfree (rndbuf);
129     }
130   else
131     sk->d = _gcry_dsa_gen_k (E->n, random_level);
132
133
134   /* Compute Q.  */
135   _gcry_mpi_ec_mul_point (&Q, sk->d, &E->G, ctx);
136
137   /* Copy the stuff to the key structures. */
138   sk->E.model = E->model;
139   sk->E.dialect = E->dialect;
140   sk->E.p = mpi_copy (E->p);
141   sk->E.a = mpi_copy (E->a);
142   sk->E.b = mpi_copy (E->b);
143   point_init (&sk->E.G);
144   point_set (&sk->E.G, &E->G);
145   sk->E.n = mpi_copy (E->n);
146   sk->E.h = mpi_copy (E->h);
147   point_init (&sk->Q);
148
149   /* We want the Q=(x,y) be a "compliant key" in terms of the
150    * http://tools.ietf.org/html/draft-jivsov-ecc-compact, which simply
151    * means that we choose either Q=(x,y) or -Q=(x,p-y) such that we
152    * end up with the min(y,p-y) as the y coordinate.  Such a public
153    * key allows the most efficient compression: y can simply be
154    * dropped because we know that it's a minimum of the two
155    * possibilities without any loss of security.  Note that we don't
156    * do that for Ed25519 so that we do not violate the special
157    * construction of the secret key.  */
158   if (E->dialect == ECC_DIALECT_ED25519)
159     point_set (&sk->Q, &Q);
160   else
161     {
162       gcry_mpi_t x, y, negative;
163       const unsigned int pbits = mpi_get_nbits (E->p);
164
165       x = mpi_new (pbits);
166       y = mpi_new (pbits);
167       negative = mpi_new (pbits);
168
169       if (_gcry_mpi_ec_get_affine (x, y, &Q, ctx))
170         log_fatal ("ecgen: Failed to get affine coordinates for %s\n", "Q");
171
172       if (E->model == MPI_EC_WEIERSTRASS)
173         mpi_sub (negative, E->p, y);      /* negative = p - y */
174       else
175         mpi_sub (negative, E->p, x);      /* negative = p - x */
176
177       if (mpi_cmp (negative, y) < 0)   /* p - y < p */
178         {
179           /* We need to end up with -Q; this assures that new Q's y is
180              the smallest one */
181           mpi_sub (sk->d, E->n, sk->d);   /* d = order - d */
182           if (E->model == MPI_EC_WEIERSTRASS)
183             mpi_point_snatch_set (&sk->Q, x, negative,
184                                        mpi_alloc_set_ui (1));
185           else
186             mpi_point_snatch_set (&sk->Q, negative, y, mpi_alloc_set_ui (1));
187
188           if (DBG_CIPHER)
189             log_debug ("ecgen converted Q to a compliant point\n");
190         }
191       else /* p - y >= p */
192         {
193           /* No change is needed exactly 50% of the time: just copy. */
194           point_set (&sk->Q, &Q);
195           if (DBG_CIPHER)
196             log_debug ("ecgen didn't need to convert Q to a compliant point\n");
197
198           mpi_free (negative);
199           if (E->model == MPI_EC_WEIERSTRASS)
200             mpi_free (x);
201           else
202             mpi_free (y);
203         }
204
205       if (E->model == MPI_EC_WEIERSTRASS)
206         mpi_free (y);
207       else
208         mpi_free (x);
209     }
210
211   point_free (&Q);
212   /* Now we can test our keys (this should never fail!).  */
213   if (sk->E.model != MPI_EC_MONTGOMERY)
214     test_keys (sk, nbits - 64);
215   else
216     test_ecdh_only_keys (sk, nbits - 64);
217
218   return 0;
219 }
220
221
222 /*
223  * To verify correct skey it use a random information.
224  * First, encrypt and decrypt this dummy value,
225  * test if the information is recuperated.
226  * Second, test with the sign and verify functions.
227  */
228 static void
229 test_keys (ECC_secret_key *sk, unsigned int nbits)
230 {
231   ECC_public_key pk;
232   gcry_mpi_t test = mpi_new (nbits);
233   mpi_point_struct R_;
234   gcry_mpi_t c = mpi_new (nbits);
235   gcry_mpi_t out = mpi_new (nbits);
236   gcry_mpi_t r = mpi_new (nbits);
237   gcry_mpi_t s = mpi_new (nbits);
238
239   if (DBG_CIPHER)
240     log_debug ("Testing key.\n");
241
242   point_init (&R_);
243
244   pk.E = _gcry_ecc_curve_copy (sk->E);
245   point_init (&pk.Q);
246   point_set (&pk.Q, &sk->Q);
247
248   _gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM);
249
250   if (_gcry_ecc_ecdsa_sign (test, sk, r, s, 0, 0) )
251     log_fatal ("ECDSA operation: sign failed\n");
252
253   if (_gcry_ecc_ecdsa_verify (test, &pk, r, s))
254     {
255       log_fatal ("ECDSA operation: sign, verify failed\n");
256     }
257
258   if (DBG_CIPHER)
259     log_debug ("ECDSA operation: sign, verify ok.\n");
260
261   point_free (&pk.Q);
262   _gcry_ecc_curve_free (&pk.E);
263
264   point_free (&R_);
265   mpi_free (s);
266   mpi_free (r);
267   mpi_free (out);
268   mpi_free (c);
269   mpi_free (test);
270 }
271
272
273 static void
274 test_ecdh_only_keys (ECC_secret_key *sk, unsigned int nbits)
275 {
276   ECC_public_key pk;
277   gcry_mpi_t test;
278   mpi_point_struct R_;
279   gcry_mpi_t x0, x1;
280   mpi_ec_t ec;
281
282   if (DBG_CIPHER)
283     log_debug ("Testing key.\n");
284
285   point_init (&R_);
286
287   pk.E = _gcry_ecc_curve_copy (sk->E);
288   point_init (&pk.Q);
289   point_set (&pk.Q, &sk->Q);
290
291   if (sk->E.dialect == ECC_DIALECT_ED25519)
292     {
293       char *rndbuf;
294
295       test = mpi_new (256);
296       rndbuf = _gcry_random_bytes (32, GCRY_WEAK_RANDOM);
297       rndbuf[0] &= 0x7f;  /* Clear bit 255. */
298       rndbuf[0] |= 0x40;  /* Set bit 254.   */
299       rndbuf[31] &= 0xf8; /* Clear bits 2..0 so that d mod 8 == 0  */
300       _gcry_mpi_set_buffer (test, rndbuf, 32, 0);
301       xfree (rndbuf);
302     }
303   else
304     {
305       test = mpi_new (nbits);
306       _gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM);
307     }
308
309   ec = _gcry_mpi_ec_p_internal_new (pk.E.model, pk.E.dialect, 0,
310                                     pk.E.p, pk.E.a, pk.E.b);
311   x0 = mpi_new (0);
312   x1 = mpi_new (0);
313
314   /* R_ = hkQ  <=>  R_ = hkdG  */
315   _gcry_mpi_ec_mul_point (&R_, test, &pk.Q, ec);
316   if (sk->E.dialect != ECC_DIALECT_ED25519)
317     _gcry_mpi_ec_mul_point (&R_, ec->h, &R_, ec);
318   if (_gcry_mpi_ec_get_affine (x0, NULL, &R_, ec))
319     log_fatal ("ecdh: Failed to get affine coordinates for hkQ\n");
320
321   _gcry_mpi_ec_mul_point (&R_, test, &pk.E.G, ec);
322   _gcry_mpi_ec_mul_point (&R_, sk->d, &R_, ec);
323   /* R_ = hdkG */
324   if (sk->E.dialect != ECC_DIALECT_ED25519)
325     _gcry_mpi_ec_mul_point (&R_, ec->h, &R_, ec);
326
327   if (_gcry_mpi_ec_get_affine (x1, NULL, &R_, ec))
328     log_fatal ("ecdh: Failed to get affine coordinates for hdkG\n");
329
330   if (mpi_cmp (x0, x1))
331     {
332       log_fatal ("ECDH test failed.\n");
333     }
334
335   mpi_free (x0);
336   mpi_free (x1);
337   _gcry_mpi_ec_free (ec);
338
339   point_free (&pk.Q);
340   _gcry_ecc_curve_free (&pk.E);
341
342   point_free (&R_);
343   mpi_free (test);
344 }
345
346
347 /*
348  * To check the validity of the value, recalculate the correspondence
349  * between the public value and the secret one.
350  */
351 static int
352 check_secret_key (ECC_secret_key *sk, mpi_ec_t ec, int flags)
353 {
354   int rc = 1;
355   mpi_point_struct Q;
356   gcry_mpi_t x1, y1;
357   gcry_mpi_t x2 = NULL;
358   gcry_mpi_t y2 = NULL;
359
360   point_init (&Q);
361   x1 = mpi_new (0);
362   if (ec->model == MPI_EC_MONTGOMERY)
363     y1 = NULL;
364   else
365     y1 = mpi_new (0);
366
367   /* G in E(F_p) */
368   if (!_gcry_mpi_ec_curve_point (&sk->E.G, ec))
369     {
370       if (DBG_CIPHER)
371         log_debug ("Bad check: Point 'G' does not belong to curve 'E'!\n");
372       goto leave;
373     }
374
375   /* G != PaI */
376   if (!mpi_cmp_ui (sk->E.G.z, 0))
377     {
378       if (DBG_CIPHER)
379         log_debug ("Bad check: 'G' cannot be Point at Infinity!\n");
380       goto leave;
381     }
382
383   /* Check order of curve.  */
384   if (sk->E.dialect != ECC_DIALECT_ED25519)
385     {
386       _gcry_mpi_ec_mul_point (&Q, sk->E.n, &sk->E.G, ec);
387       if (mpi_cmp_ui (Q.z, 0))
388         {
389           if (DBG_CIPHER)
390             log_debug ("check_secret_key: E is not a curve of order n\n");
391           goto leave;
392         }
393     }
394
395   /* Pubkey cannot be PaI */
396   if (!mpi_cmp_ui (sk->Q.z, 0))
397     {
398       if (DBG_CIPHER)
399         log_debug ("Bad check: Q can not be a Point at Infinity!\n");
400       goto leave;
401     }
402
403   /* pubkey = [d]G over E */
404   if (!_gcry_ecc_compute_public (&Q, ec, &sk->E.G, sk->d))
405     {
406       if (DBG_CIPHER)
407         log_debug ("Bad check: computation of dG failed\n");
408       goto leave;
409     }
410   if (_gcry_mpi_ec_get_affine (x1, y1, &Q, ec))
411     {
412       if (DBG_CIPHER)
413         log_debug ("Bad check: Q can not be a Point at Infinity!\n");
414       goto leave;
415     }
416
417   if ((flags & PUBKEY_FLAG_EDDSA))
418     ; /* Fixme: EdDSA is special.  */
419   else if (!mpi_cmp_ui (sk->Q.z, 1))
420     {
421       /* Fast path if Q is already in affine coordinates.  */
422       if (mpi_cmp (x1, sk->Q.x) || (!y1 && mpi_cmp (y1, sk->Q.y)))
423         {
424           if (DBG_CIPHER)
425             log_debug
426               ("Bad check: There is NO correspondence between 'd' and 'Q'!\n");
427           goto leave;
428         }
429     }
430   else
431     {
432       x2 = mpi_new (0);
433       y2 = mpi_new (0);
434       if (_gcry_mpi_ec_get_affine (x2, y2, &sk->Q, ec))
435         {
436           if (DBG_CIPHER)
437             log_debug ("Bad check: Q can not be a Point at Infinity!\n");
438           goto leave;
439         }
440
441       if (mpi_cmp (x1, x2) || mpi_cmp (y1, y2))
442         {
443           if (DBG_CIPHER)
444             log_debug
445               ("Bad check: There is NO correspondence between 'd' and 'Q'!\n");
446           goto leave;
447         }
448     }
449   rc = 0; /* Okay.  */
450
451  leave:
452   mpi_free (x2);
453   mpi_free (x1);
454   mpi_free (y1);
455   mpi_free (y2);
456   point_free (&Q);
457   return rc;
458 }
459
460
461 \f
462 /*********************************************
463  **************  interface  ******************
464  *********************************************/
465
466 static gcry_err_code_t
467 ecc_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
468 {
469   gpg_err_code_t rc;
470   unsigned int nbits;
471   elliptic_curve_t E;
472   ECC_secret_key sk;
473   gcry_mpi_t x = NULL;
474   gcry_mpi_t y = NULL;
475   char *curve_name = NULL;
476   gcry_sexp_t l1;
477   gcry_random_level_t random_level;
478   mpi_ec_t ctx = NULL;
479   gcry_sexp_t curve_info = NULL;
480   gcry_sexp_t curve_flags = NULL;
481   gcry_mpi_t base = NULL;
482   gcry_mpi_t public = NULL;
483   gcry_mpi_t secret = NULL;
484   int flags = 0;
485
486   memset (&E, 0, sizeof E);
487   memset (&sk, 0, sizeof sk);
488
489   rc = _gcry_pk_util_get_nbits (genparms, &nbits);
490   if (rc)
491     return rc;
492
493   /* Parse the optional "curve" parameter. */
494   l1 = sexp_find_token (genparms, "curve", 0);
495   if (l1)
496     {
497       curve_name = _gcry_sexp_nth_string (l1, 1);
498       sexp_release (l1);
499       if (!curve_name)
500         return GPG_ERR_INV_OBJ; /* No curve name or value too large. */
501     }
502
503   /* Parse the optional flags list.  */
504   l1 = sexp_find_token (genparms, "flags", 0);
505   if (l1)
506     {
507       rc = _gcry_pk_util_parse_flaglist (l1, &flags, NULL);
508       sexp_release (l1);
509       if (rc)
510         goto leave;
511     }
512
513   /* Parse the deprecated optional transient-key flag.  */
514   l1 = sexp_find_token (genparms, "transient-key", 0);
515   if (l1)
516     {
517       flags |= PUBKEY_FLAG_TRANSIENT_KEY;
518       sexp_release (l1);
519     }
520
521   /* NBITS is required if no curve name has been given.  */
522   if (!nbits && !curve_name)
523     return GPG_ERR_NO_OBJ; /* No NBITS parameter. */
524
525   rc = _gcry_ecc_fill_in_curve (nbits, curve_name, &E, &nbits);
526   xfree (curve_name); curve_name = NULL;
527   if (rc)
528     goto leave;
529
530   if (DBG_CIPHER)
531     {
532       log_debug ("ecgen curve info: %s/%s\n",
533                  _gcry_ecc_model2str (E.model),
534                  _gcry_ecc_dialect2str (E.dialect));
535       if (E.name)
536         log_debug ("ecgen curve used: %s\n", E.name);
537       log_printmpi ("ecgen curve   p", E.p);
538       log_printmpi ("ecgen curve   a", E.a);
539       log_printmpi ("ecgen curve   b", E.b);
540       log_printmpi ("ecgen curve   n", E.n);
541       log_printmpi ("ecgen curve   h", E.h);
542       log_printpnt ("ecgen curve G", &E.G, NULL);
543     }
544
545   if ((flags & PUBKEY_FLAG_TRANSIENT_KEY))
546     random_level = GCRY_STRONG_RANDOM;
547   else
548     random_level = GCRY_VERY_STRONG_RANDOM;
549
550   ctx = _gcry_mpi_ec_p_internal_new (E.model, E.dialect, 0, E.p, E.a, E.b);
551   x = mpi_new (0);
552   y = mpi_new (0);
553
554   if ((flags & PUBKEY_FLAG_EDDSA))
555     rc = _gcry_ecc_eddsa_genkey (&sk, &E, ctx, random_level);
556   else
557     rc = nist_generate_key (&sk, &E, ctx, random_level, nbits);
558   if (rc)
559     goto leave;
560
561   /* Copy data to the result.  */
562   if (_gcry_mpi_ec_get_affine (x, y, &sk.E.G, ctx))
563     log_fatal ("ecgen: Failed to get affine coordinates for %s\n", "G");
564   base = _gcry_ecc_ec2os (x, y, sk.E.p);
565   if (sk.E.dialect == ECC_DIALECT_ED25519 && !(flags & PUBKEY_FLAG_NOCOMP))
566     {
567       unsigned char *encpk;
568       unsigned int encpklen;
569
570       rc = _gcry_ecc_eddsa_encodepoint (&sk.Q, ctx, x, y,
571                                         !!(flags & PUBKEY_FLAG_COMP),
572                                         &encpk, &encpklen);
573       if (rc)
574         return rc;
575       public = mpi_new (0);
576       mpi_set_opaque (public, encpk, encpklen*8);
577       encpk = NULL;
578     }
579   else
580     {
581       if (_gcry_mpi_ec_get_affine (x, y, &sk.Q, ctx))
582         log_fatal ("ecgen: Failed to get affine coordinates for %s\n", "Q");
583       public = _gcry_ecc_ec2os (x, y, sk.E.p);
584     }
585   secret = sk.d; sk.d = NULL;
586   if (E.name)
587     {
588       rc = sexp_build (&curve_info, NULL, "(curve %s)", E.name);
589       if (rc)
590         goto leave;
591     }
592
593   if ((flags & PUBKEY_FLAG_PARAM) || (flags & PUBKEY_FLAG_EDDSA))
594     {
595       rc = sexp_build
596         (&curve_flags, NULL,
597          ((flags & PUBKEY_FLAG_PARAM) && (flags & PUBKEY_FLAG_EDDSA))?
598          "(flags param eddsa)" :
599          ((flags & PUBKEY_FLAG_PARAM))?
600          "(flags param)" :
601          "(flags eddsa)");
602       if (rc)
603         goto leave;
604     }
605
606   if ((flags & PUBKEY_FLAG_PARAM) && E.name)
607     rc = sexp_build (r_skey, NULL,
608                      "(key-data"
609                      " (public-key"
610                      "  (ecc%S%S(p%m)(a%m)(b%m)(g%m)(n%m)(h%m)(q%m)))"
611                      " (private-key"
612                      "  (ecc%S%S(p%m)(a%m)(b%m)(g%m)(n%m)(h%m)(q%m)(d%m)))"
613                      " )",
614                      curve_info, curve_flags,
615                      sk.E.p, sk.E.a, sk.E.b, base, sk.E.n, sk.E.h, public,
616                      curve_info, curve_flags,
617                      sk.E.p, sk.E.a, sk.E.b, base, sk.E.n, sk.E.h, public, secret);
618   else
619     rc = sexp_build (r_skey, NULL,
620                      "(key-data"
621                      " (public-key"
622                      "  (ecc%S%S(q%m)))"
623                      " (private-key"
624                      "  (ecc%S%S(q%m)(d%m)))"
625                      " )",
626                      curve_info, curve_flags,
627                      public,
628                      curve_info, curve_flags,
629                      public, secret);
630   if (rc)
631     goto leave;
632
633   if (DBG_CIPHER)
634     {
635       log_printmpi ("ecgen result  p", sk.E.p);
636       log_printmpi ("ecgen result  a", sk.E.a);
637       log_printmpi ("ecgen result  b", sk.E.b);
638       log_printmpi ("ecgen result  G", base);
639       log_printmpi ("ecgen result  n", sk.E.n);
640       log_printmpi ("ecgen result  h", sk.E.h);
641       log_printmpi ("ecgen result  Q", public);
642       log_printmpi ("ecgen result  d", secret);
643       if ((flags & PUBKEY_FLAG_EDDSA))
644         log_debug ("ecgen result  using Ed25519+EdDSA\n");
645     }
646
647  leave:
648   mpi_free (secret);
649   mpi_free (public);
650   mpi_free (base);
651   {
652     _gcry_ecc_curve_free (&sk.E);
653     point_free (&sk.Q);
654     mpi_free (sk.d);
655   }
656   _gcry_ecc_curve_free (&E);
657   mpi_free (x);
658   mpi_free (y);
659   _gcry_mpi_ec_free (ctx);
660   sexp_release (curve_flags);
661   sexp_release (curve_info);
662   return rc;
663 }
664
665
666 static gcry_err_code_t
667 ecc_check_secret_key (gcry_sexp_t keyparms)
668 {
669   gcry_err_code_t rc;
670   gcry_sexp_t l1 = NULL;
671   int flags = 0;
672   char *curvename = NULL;
673   gcry_mpi_t mpi_g = NULL;
674   gcry_mpi_t mpi_q = NULL;
675   ECC_secret_key sk;
676   mpi_ec_t ec = NULL;
677
678   memset (&sk, 0, sizeof sk);
679
680   /* Look for flags. */
681   l1 = sexp_find_token (keyparms, "flags", 0);
682   if (l1)
683     {
684       rc = _gcry_pk_util_parse_flaglist (l1, &flags, NULL);
685       if (rc)
686         goto leave;
687     }
688
689   /* Extract the parameters.  */
690   if ((flags & PUBKEY_FLAG_PARAM))
691     rc = sexp_extract_param (keyparms, NULL, "-p?a?b?g?n?h?/q?+d",
692                              &sk.E.p, &sk.E.a, &sk.E.b, &mpi_g, &sk.E.n,
693                              &sk.E.h, &mpi_q, &sk.d, NULL);
694   else
695     rc = sexp_extract_param (keyparms, NULL, "/q?+d",
696                              &mpi_q, &sk.d, NULL);
697   if (rc)
698     goto leave;
699
700   /* Add missing parameters using the optional curve parameter.  */
701   sexp_release (l1);
702   l1 = sexp_find_token (keyparms, "curve", 5);
703   if (l1)
704     {
705       curvename = sexp_nth_string (l1, 1);
706       if (curvename)
707         {
708           rc = _gcry_ecc_update_curve_param (curvename,
709                                              &sk.E.model, &sk.E.dialect,
710                                              &sk.E.p, &sk.E.a, &sk.E.b,
711                                              &mpi_g, &sk.E.n, &sk.E.h);
712           if (rc)
713             return rc;
714         }
715     }
716   if (mpi_g)
717     {
718       point_init (&sk.E.G);
719       rc = _gcry_ecc_os2ec (&sk.E.G, mpi_g);
720       if (rc)
721         goto leave;
722     }
723
724   /* Guess required fields if a curve parameter has not been given.
725      FIXME: This is a crude hacks.  We need to fix that.  */
726   if (!curvename)
727     {
728       sk.E.model = ((flags & PUBKEY_FLAG_EDDSA)
729                ? MPI_EC_EDWARDS
730                : MPI_EC_WEIERSTRASS);
731       sk.E.dialect = ((flags & PUBKEY_FLAG_EDDSA)
732                       ? ECC_DIALECT_ED25519
733                       : ECC_DIALECT_STANDARD);
734     }
735   if (DBG_CIPHER)
736     {
737       log_debug ("ecc_testkey inf: %s/%s\n",
738                  _gcry_ecc_model2str (sk.E.model),
739                  _gcry_ecc_dialect2str (sk.E.dialect));
740       if (sk.E.name)
741         log_debug  ("ecc_testkey nam: %s\n", sk.E.name);
742       log_printmpi ("ecc_testkey   p", sk.E.p);
743       log_printmpi ("ecc_testkey   a", sk.E.a);
744       log_printmpi ("ecc_testkey   b", sk.E.b);
745       log_printpnt ("ecc_testkey g",   &sk.E.G, NULL);
746       log_printmpi ("ecc_testkey   n", sk.E.n);
747       log_printmpi ("ecc_testkey   h", sk.E.h);
748       log_printmpi ("ecc_testkey   q", mpi_q);
749       if (!fips_mode ())
750         log_printmpi ("ecc_testkey   d", sk.d);
751     }
752   if (!sk.E.p || !sk.E.a || !sk.E.b || !sk.E.G.x || !sk.E.n || !sk.E.h || !sk.d)
753     {
754       rc = GPG_ERR_NO_OBJ;
755       goto leave;
756     }
757
758   ec = _gcry_mpi_ec_p_internal_new (sk.E.model, sk.E.dialect, 0,
759                                     sk.E.p, sk.E.a, sk.E.b);
760
761   if (mpi_q)
762     {
763       point_init (&sk.Q);
764       if (ec->dialect == ECC_DIALECT_ED25519)
765         rc = _gcry_ecc_eddsa_decodepoint (mpi_q, ec, &sk.Q, NULL, NULL);
766       else
767         rc = _gcry_ecc_os2ec (&sk.Q, mpi_q);
768       if (rc)
769         goto leave;
770     }
771   else
772     {
773       /* The secret key test requires Q.  */
774       rc = GPG_ERR_NO_OBJ;
775       goto leave;
776     }
777
778   if (check_secret_key (&sk, ec, flags))
779     rc = GPG_ERR_BAD_SECKEY;
780
781  leave:
782   _gcry_mpi_ec_free (ec);
783   _gcry_mpi_release (sk.E.p);
784   _gcry_mpi_release (sk.E.a);
785   _gcry_mpi_release (sk.E.b);
786   _gcry_mpi_release (mpi_g);
787   point_free (&sk.E.G);
788   _gcry_mpi_release (sk.E.n);
789   _gcry_mpi_release (sk.E.h);
790   _gcry_mpi_release (mpi_q);
791   point_free (&sk.Q);
792   _gcry_mpi_release (sk.d);
793   xfree (curvename);
794   sexp_release (l1);
795   if (DBG_CIPHER)
796     log_debug ("ecc_testkey   => %s\n", gpg_strerror (rc));
797   return rc;
798 }
799
800
801 static gcry_err_code_t
802 ecc_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
803 {
804   gcry_err_code_t rc;
805   struct pk_encoding_ctx ctx;
806   gcry_mpi_t data = NULL;
807   gcry_sexp_t l1 = NULL;
808   char *curvename = NULL;
809   gcry_mpi_t mpi_g = NULL;
810   gcry_mpi_t mpi_q = NULL;
811   ECC_secret_key sk;
812   gcry_mpi_t sig_r = NULL;
813   gcry_mpi_t sig_s = NULL;
814
815   memset (&sk, 0, sizeof sk);
816
817   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_SIGN, 0);
818
819   /* Extract the data.  */
820   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
821   if (rc)
822     goto leave;
823   if (DBG_CIPHER)
824     log_mpidump ("ecc_sign   data", data);
825
826   /*
827    * Extract the key.
828    */
829   if ((ctx.flags & PUBKEY_FLAG_PARAM))
830     rc = sexp_extract_param (keyparms, NULL, "-p?a?b?g?n?h?/q?+d",
831                              &sk.E.p, &sk.E.a, &sk.E.b, &mpi_g, &sk.E.n,
832                              &sk.E.h, &mpi_q, &sk.d, NULL);
833   else
834     rc = sexp_extract_param (keyparms, NULL, "/q?+d",
835                              &mpi_q, &sk.d, NULL);
836   if (rc)
837     goto leave;
838   if (mpi_g)
839     {
840       point_init (&sk.E.G);
841       rc = _gcry_ecc_os2ec (&sk.E.G, mpi_g);
842       if (rc)
843         goto leave;
844     }
845   /* Add missing parameters using the optional curve parameter.  */
846   sexp_release (l1);
847   l1 = sexp_find_token (keyparms, "curve", 5);
848   if (l1)
849     {
850       curvename = sexp_nth_string (l1, 1);
851       if (curvename)
852         {
853           rc = _gcry_ecc_fill_in_curve (0, curvename, &sk.E, NULL);
854           if (rc)
855             return rc;
856         }
857     }
858   /* Guess required fields if a curve parameter has not been given.
859      FIXME: This is a crude hacks.  We need to fix that.  */
860   if (!curvename)
861     {
862       sk.E.model = ((ctx.flags & PUBKEY_FLAG_EDDSA)
863                     ? MPI_EC_EDWARDS
864                     : MPI_EC_WEIERSTRASS);
865       sk.E.dialect = ((ctx.flags & PUBKEY_FLAG_EDDSA)
866                       ? ECC_DIALECT_ED25519
867                       : ECC_DIALECT_STANDARD);
868     }
869   if (DBG_CIPHER)
870     {
871       log_debug ("ecc_sign   info: %s/%s%s\n",
872                  _gcry_ecc_model2str (sk.E.model),
873                  _gcry_ecc_dialect2str (sk.E.dialect),
874                  (ctx.flags & PUBKEY_FLAG_EDDSA)? "+EdDSA":"");
875       if (sk.E.name)
876         log_debug  ("ecc_sign   name: %s\n", sk.E.name);
877       log_printmpi ("ecc_sign      p", sk.E.p);
878       log_printmpi ("ecc_sign      a", sk.E.a);
879       log_printmpi ("ecc_sign      b", sk.E.b);
880       log_printpnt ("ecc_sign    g",   &sk.E.G, NULL);
881       log_printmpi ("ecc_sign      n", sk.E.n);
882       log_printmpi ("ecc_sign      h", sk.E.h);
883       log_printmpi ("ecc_sign      q", mpi_q);
884       if (!fips_mode ())
885         log_printmpi ("ecc_sign      d", sk.d);
886     }
887   if (!sk.E.p || !sk.E.a || !sk.E.b || !sk.E.G.x || !sk.E.n || !sk.E.h || !sk.d)
888     {
889       rc = GPG_ERR_NO_OBJ;
890       goto leave;
891     }
892
893
894   sig_r = mpi_new (0);
895   sig_s = mpi_new (0);
896   if ((ctx.flags & PUBKEY_FLAG_EDDSA))
897     {
898       /* EdDSA requires the public key.  */
899       rc = _gcry_ecc_eddsa_sign (data, &sk, sig_r, sig_s, ctx.hash_algo, mpi_q);
900       if (!rc)
901         rc = sexp_build (r_sig, NULL,
902                          "(sig-val(eddsa(r%M)(s%M)))", sig_r, sig_s);
903     }
904   else if ((ctx.flags & PUBKEY_FLAG_GOST))
905     {
906       rc = _gcry_ecc_gost_sign (data, &sk, sig_r, sig_s);
907       if (!rc)
908         rc = sexp_build (r_sig, NULL,
909                          "(sig-val(gost(r%M)(s%M)))", sig_r, sig_s);
910     }
911   else
912     {
913       rc = _gcry_ecc_ecdsa_sign (data, &sk, sig_r, sig_s,
914                                  ctx.flags, ctx.hash_algo);
915       if (!rc)
916         rc = sexp_build (r_sig, NULL,
917                          "(sig-val(ecdsa(r%M)(s%M)))", sig_r, sig_s);
918     }
919
920
921  leave:
922   _gcry_mpi_release (sk.E.p);
923   _gcry_mpi_release (sk.E.a);
924   _gcry_mpi_release (sk.E.b);
925   _gcry_mpi_release (mpi_g);
926   point_free (&sk.E.G);
927   _gcry_mpi_release (sk.E.n);
928   _gcry_mpi_release (sk.E.h);
929   _gcry_mpi_release (mpi_q);
930   point_free (&sk.Q);
931   _gcry_mpi_release (sk.d);
932   _gcry_mpi_release (sig_r);
933   _gcry_mpi_release (sig_s);
934   xfree (curvename);
935   _gcry_mpi_release (data);
936   sexp_release (l1);
937   _gcry_pk_util_free_encoding_ctx (&ctx);
938   if (DBG_CIPHER)
939     log_debug ("ecc_sign      => %s\n", gpg_strerror (rc));
940   return rc;
941 }
942
943
944 static gcry_err_code_t
945 ecc_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t s_keyparms)
946 {
947   gcry_err_code_t rc;
948   struct pk_encoding_ctx ctx;
949   gcry_sexp_t l1 = NULL;
950   char *curvename = NULL;
951   gcry_mpi_t mpi_g = NULL;
952   gcry_mpi_t mpi_q = NULL;
953   gcry_mpi_t sig_r = NULL;
954   gcry_mpi_t sig_s = NULL;
955   gcry_mpi_t data = NULL;
956   ECC_public_key pk;
957   int sigflags;
958
959   memset (&pk, 0, sizeof pk);
960   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY,
961                                    ecc_get_nbits (s_keyparms));
962
963   /* Extract the data.  */
964   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
965   if (rc)
966     goto leave;
967   if (DBG_CIPHER)
968     log_mpidump ("ecc_verify data", data);
969
970   /*
971    * Extract the signature value.
972    */
973   rc = _gcry_pk_util_preparse_sigval (s_sig, ecc_names, &l1, &sigflags);
974   if (rc)
975     goto leave;
976   rc = sexp_extract_param (l1, NULL, (sigflags & PUBKEY_FLAG_EDDSA)? "/rs":"rs",
977                            &sig_r, &sig_s, NULL);
978   if (rc)
979     goto leave;
980   if (DBG_CIPHER)
981     {
982       log_mpidump ("ecc_verify  s_r", sig_r);
983       log_mpidump ("ecc_verify  s_s", sig_s);
984     }
985   if ((ctx.flags & PUBKEY_FLAG_EDDSA) ^ (sigflags & PUBKEY_FLAG_EDDSA))
986     {
987       rc = GPG_ERR_CONFLICT; /* Inconsistent use of flag/algoname.  */
988       goto leave;
989     }
990
991
992   /*
993    * Extract the key.
994    */
995   if ((ctx.flags & PUBKEY_FLAG_PARAM))
996     rc = sexp_extract_param (s_keyparms, NULL, "-p?a?b?g?n?h?/q",
997                              &pk.E.p, &pk.E.a, &pk.E.b, &mpi_g, &pk.E.n,
998                              &pk.E.n, &mpi_q, NULL);
999   else
1000     rc = sexp_extract_param (s_keyparms, NULL, "/q",
1001                              &mpi_q, NULL);
1002   if (rc)
1003     goto leave;
1004   if (mpi_g)
1005     {
1006       point_init (&pk.E.G);
1007       rc = _gcry_ecc_os2ec (&pk.E.G, mpi_g);
1008       if (rc)
1009         goto leave;
1010     }
1011   /* Add missing parameters using the optional curve parameter.  */
1012   sexp_release (l1);
1013   l1 = sexp_find_token (s_keyparms, "curve", 5);
1014   if (l1)
1015     {
1016       curvename = sexp_nth_string (l1, 1);
1017       if (curvename)
1018         {
1019           rc = _gcry_ecc_fill_in_curve (0, curvename, &pk.E, NULL);
1020           if (rc)
1021             return rc;
1022         }
1023     }
1024   /* Guess required fields if a curve parameter has not been given.
1025      FIXME: This is a crude hacks.  We need to fix that.  */
1026   if (!curvename)
1027     {
1028       pk.E.model = ((sigflags & PUBKEY_FLAG_EDDSA)
1029                     ? MPI_EC_EDWARDS
1030                     : MPI_EC_WEIERSTRASS);
1031       pk.E.dialect = ((sigflags & PUBKEY_FLAG_EDDSA)
1032                       ? ECC_DIALECT_ED25519
1033                       : ECC_DIALECT_STANDARD);
1034     }
1035
1036   if (DBG_CIPHER)
1037     {
1038       log_debug ("ecc_verify info: %s/%s%s\n",
1039                  _gcry_ecc_model2str (pk.E.model),
1040                  _gcry_ecc_dialect2str (pk.E.dialect),
1041                  (sigflags & PUBKEY_FLAG_EDDSA)? "+EdDSA":"");
1042       if (pk.E.name)
1043         log_debug  ("ecc_verify name: %s\n", pk.E.name);
1044       log_printmpi ("ecc_verify    p", pk.E.p);
1045       log_printmpi ("ecc_verify    a", pk.E.a);
1046       log_printmpi ("ecc_verify    b", pk.E.b);
1047       log_printpnt ("ecc_verify  g",   &pk.E.G, NULL);
1048       log_printmpi ("ecc_verify    n", pk.E.n);
1049       log_printmpi ("ecc_verify    h", pk.E.h);
1050       log_printmpi ("ecc_verify    q", mpi_q);
1051     }
1052   if (!pk.E.p || !pk.E.a || !pk.E.b || !pk.E.G.x || !pk.E.n || !pk.E.h || !mpi_q)
1053     {
1054       rc = GPG_ERR_NO_OBJ;
1055       goto leave;
1056     }
1057
1058
1059   /*
1060    * Verify the signature.
1061    */
1062   if ((sigflags & PUBKEY_FLAG_EDDSA))
1063     {
1064       rc = _gcry_ecc_eddsa_verify (data, &pk, sig_r, sig_s,
1065                                    ctx.hash_algo, mpi_q);
1066     }
1067   else if ((sigflags & PUBKEY_FLAG_GOST))
1068     {
1069       point_init (&pk.Q);
1070       rc = _gcry_ecc_os2ec (&pk.Q, mpi_q);
1071       if (rc)
1072         goto leave;
1073
1074       rc = _gcry_ecc_gost_verify (data, &pk, sig_r, sig_s);
1075     }
1076   else
1077     {
1078       point_init (&pk.Q);
1079       if (pk.E.dialect == ECC_DIALECT_ED25519)
1080         {
1081           mpi_ec_t ec;
1082
1083           /* Fixme: Factor the curve context setup out of eddsa_verify
1084              and ecdsa_verify. So that we don't do it twice.  */
1085           ec = _gcry_mpi_ec_p_internal_new (pk.E.model, pk.E.dialect, 0,
1086                                             pk.E.p, pk.E.a, pk.E.b);
1087
1088           rc = _gcry_ecc_eddsa_decodepoint (mpi_q, ec, &pk.Q, NULL, NULL);
1089           _gcry_mpi_ec_free (ec);
1090         }
1091       else
1092         {
1093           rc = _gcry_ecc_os2ec (&pk.Q, mpi_q);
1094         }
1095       if (rc)
1096         goto leave;
1097
1098       if (mpi_is_opaque (data))
1099         {
1100           const void *abuf;
1101           unsigned int abits, qbits;
1102           gcry_mpi_t a;
1103
1104           qbits = mpi_get_nbits (pk.E.n);
1105
1106           abuf = mpi_get_opaque (data, &abits);
1107           rc = _gcry_mpi_scan (&a, GCRYMPI_FMT_USG, abuf, (abits+7)/8, NULL);
1108           if (!rc)
1109             {
1110               if (abits > qbits)
1111                 mpi_rshift (a, a, abits - qbits);
1112
1113               rc = _gcry_ecc_ecdsa_verify (a, &pk, sig_r, sig_s);
1114               _gcry_mpi_release (a);
1115             }
1116         }
1117       else
1118         rc = _gcry_ecc_ecdsa_verify (data, &pk, sig_r, sig_s);
1119     }
1120
1121  leave:
1122   _gcry_mpi_release (pk.E.p);
1123   _gcry_mpi_release (pk.E.a);
1124   _gcry_mpi_release (pk.E.b);
1125   _gcry_mpi_release (mpi_g);
1126   point_free (&pk.E.G);
1127   _gcry_mpi_release (pk.E.n);
1128   _gcry_mpi_release (pk.E.h);
1129   _gcry_mpi_release (mpi_q);
1130   point_free (&pk.Q);
1131   _gcry_mpi_release (data);
1132   _gcry_mpi_release (sig_r);
1133   _gcry_mpi_release (sig_s);
1134   xfree (curvename);
1135   sexp_release (l1);
1136   _gcry_pk_util_free_encoding_ctx (&ctx);
1137   if (DBG_CIPHER)
1138     log_debug ("ecc_verify    => %s\n", rc?gpg_strerror (rc):"Good");
1139   return rc;
1140 }
1141
1142
1143 /* ecdh raw is classic 2-round DH protocol published in 1976.
1144  *
1145  * Overview of ecc_encrypt_raw and ecc_decrypt_raw.
1146  *
1147  * As with any PK operation, encrypt version uses a public key and
1148  * decrypt -- private.
1149  *
1150  * Symbols used below:
1151  *     G - field generator point
1152  *     d - private long-term scalar
1153  *    dG - public long-term key
1154  *     k - ephemeral scalar
1155  *    kG - ephemeral public key
1156  *   dkG - shared secret
1157  *
1158  * ecc_encrypt_raw description:
1159  *   input:
1160  *     data[0] : private scalar (k)
1161  *   output: A new S-expression with the parameters:
1162  *     s : shared point (kdG)
1163  *     e : generated ephemeral public key (kG)
1164  *
1165  * ecc_decrypt_raw description:
1166  *   input:
1167  *     data[0] : a point kG (ephemeral public key)
1168  *   output:
1169  *     result[0] : shared point (kdG)
1170  */
1171 static gcry_err_code_t
1172 ecc_encrypt_raw (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1173 {
1174   gcry_err_code_t rc;
1175   struct pk_encoding_ctx ctx;
1176   gcry_sexp_t l1 = NULL;
1177   char *curvename = NULL;
1178   gcry_mpi_t mpi_g = NULL;
1179   gcry_mpi_t mpi_q = NULL;
1180   gcry_mpi_t mpi_s = NULL;
1181   gcry_mpi_t mpi_e = NULL;
1182   gcry_mpi_t data = NULL;
1183   ECC_public_key pk;
1184   mpi_ec_t ec = NULL;
1185
1186   memset (&pk, 0, sizeof pk);
1187   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_ENCRYPT,
1188                                    ecc_get_nbits (keyparms));
1189
1190   /*
1191    * Extract the data.
1192    */
1193   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1194   if (rc)
1195     goto leave;
1196   if (DBG_CIPHER)
1197     log_mpidump ("ecc_encrypt data", data);
1198   if (mpi_is_opaque (data))
1199     {
1200       rc = GPG_ERR_INV_DATA;
1201       goto leave;
1202     }
1203
1204
1205   /*
1206    * Extract the key.
1207    */
1208   rc = sexp_extract_param (keyparms, NULL, "-p?a?b?g?n?h?+q",
1209                            &pk.E.p, &pk.E.a, &pk.E.b, &mpi_g, &pk.E.n, &pk.E.h,
1210                            &mpi_q, NULL);
1211   if (rc)
1212     goto leave;
1213   if (mpi_g)
1214     {
1215       point_init (&pk.E.G);
1216       rc = _gcry_ecc_os2ec (&pk.E.G, mpi_g);
1217       if (rc)
1218         goto leave;
1219     }
1220   /* Add missing parameters using the optional curve parameter.  */
1221   sexp_release (l1);
1222   l1 = sexp_find_token (keyparms, "curve", 5);
1223   if (l1)
1224     {
1225       curvename = sexp_nth_string (l1, 1);
1226       if (curvename)
1227         {
1228           rc = _gcry_ecc_fill_in_curve (0, curvename, &pk.E, NULL);
1229           if (rc)
1230             return rc;
1231         }
1232     }
1233   /* Guess required fields if a curve parameter has not been given.  */
1234   if (!curvename)
1235     {
1236       pk.E.model = MPI_EC_WEIERSTRASS;
1237       pk.E.dialect = ECC_DIALECT_STANDARD;
1238     }
1239
1240   if (DBG_CIPHER)
1241     {
1242       log_debug ("ecc_encrypt info: %s/%s\n",
1243                  _gcry_ecc_model2str (pk.E.model),
1244                  _gcry_ecc_dialect2str (pk.E.dialect));
1245       if (pk.E.name)
1246         log_debug  ("ecc_encrypt name: %s\n", pk.E.name);
1247       log_printmpi ("ecc_encrypt    p", pk.E.p);
1248       log_printmpi ("ecc_encrypt    a", pk.E.a);
1249       log_printmpi ("ecc_encrypt    b", pk.E.b);
1250       log_printpnt ("ecc_encrypt  g",   &pk.E.G, NULL);
1251       log_printmpi ("ecc_encrypt    n", pk.E.n);
1252       log_printmpi ("ecc_encrypt    h", pk.E.h);
1253       log_printmpi ("ecc_encrypt    q", mpi_q);
1254     }
1255   if (!pk.E.p || !pk.E.a || !pk.E.b || !pk.E.G.x || !pk.E.n || !pk.E.h || !mpi_q)
1256     {
1257       rc = GPG_ERR_NO_OBJ;
1258       goto leave;
1259     }
1260
1261   /* Convert the public key.  */
1262   if (mpi_q)
1263     {
1264       point_init (&pk.Q);
1265       rc = _gcry_ecc_os2ec (&pk.Q, mpi_q);
1266       if (rc)
1267         goto leave;
1268     }
1269
1270   /* Compute the encrypted value.  */
1271   ec = _gcry_mpi_ec_p_internal_new (pk.E.model, pk.E.dialect, 0,
1272                                     pk.E.p, pk.E.a, pk.E.b);
1273
1274   /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so */
1275   {
1276     mpi_point_struct R;  /* Result that we return.  */
1277     gcry_mpi_t x, y;
1278
1279     x = mpi_new (0);
1280     y = mpi_new (0);
1281
1282     point_init (&R);
1283
1284     /* R = kQ  <=>  R = kdG  */
1285     _gcry_mpi_ec_mul_point (&R, data, &pk.Q, ec);
1286
1287     if (_gcry_mpi_ec_get_affine (x, y, &R, ec))
1288       log_fatal ("ecdh: Failed to get affine coordinates for kdG\n");
1289     mpi_s = _gcry_ecc_ec2os (x, y, pk.E.p);
1290
1291     /* R = kG */
1292     _gcry_mpi_ec_mul_point (&R, data, &pk.E.G, ec);
1293
1294     if (_gcry_mpi_ec_get_affine (x, y, &R, ec))
1295       log_fatal ("ecdh: Failed to get affine coordinates for kG\n");
1296     mpi_e = _gcry_ecc_ec2os (x, y, pk.E.p);
1297
1298     mpi_free (x);
1299     mpi_free (y);
1300
1301     point_free (&R);
1302   }
1303
1304   rc = sexp_build (r_ciph, NULL, "(enc-val(ecdh(s%m)(e%m)))", mpi_s, mpi_e);
1305
1306  leave:
1307   _gcry_mpi_release (pk.E.p);
1308   _gcry_mpi_release (pk.E.a);
1309   _gcry_mpi_release (pk.E.b);
1310   _gcry_mpi_release (mpi_g);
1311   point_free (&pk.E.G);
1312   _gcry_mpi_release (pk.E.n);
1313   _gcry_mpi_release (pk.E.h);
1314   _gcry_mpi_release (mpi_q);
1315   point_free (&pk.Q);
1316   _gcry_mpi_release (data);
1317   _gcry_mpi_release (mpi_s);
1318   _gcry_mpi_release (mpi_e);
1319   xfree (curvename);
1320   _gcry_mpi_ec_free (ec);
1321   _gcry_pk_util_free_encoding_ctx (&ctx);
1322   if (DBG_CIPHER)
1323     log_debug ("ecc_encrypt    => %s\n", gpg_strerror (rc));
1324   return rc;
1325 }
1326
1327
1328 /*  input:
1329  *     data[0] : a point kG (ephemeral public key)
1330  *   output:
1331  *     resaddr[0] : shared point kdG
1332  *
1333  *  see ecc_encrypt_raw for details.
1334  */
1335 static gcry_err_code_t
1336 ecc_decrypt_raw (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1337 {
1338   gpg_err_code_t rc;
1339   struct pk_encoding_ctx ctx;
1340   gcry_sexp_t l1 = NULL;
1341   gcry_mpi_t data_e = NULL;
1342   ECC_secret_key sk;
1343   gcry_mpi_t mpi_g = NULL;
1344   char *curvename = NULL;
1345   mpi_ec_t ec = NULL;
1346   mpi_point_struct kG;
1347   mpi_point_struct R;
1348   gcry_mpi_t r = NULL;
1349
1350   memset (&sk, 0, sizeof sk);
1351   point_init (&kG);
1352   point_init (&R);
1353
1354   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_DECRYPT,
1355                                    ecc_get_nbits (keyparms));
1356
1357   /*
1358    * Extract the data.
1359    */
1360   rc = _gcry_pk_util_preparse_encval (s_data, ecc_names, &l1, &ctx);
1361   if (rc)
1362     goto leave;
1363   rc = sexp_extract_param (l1, NULL, "e", &data_e, NULL);
1364   if (rc)
1365     goto leave;
1366   if (DBG_CIPHER)
1367     log_printmpi ("ecc_decrypt  d_e", data_e);
1368   if (mpi_is_opaque (data_e))
1369     {
1370       rc = GPG_ERR_INV_DATA;
1371       goto leave;
1372     }
1373
1374   /*
1375    * Extract the key.
1376    */
1377   rc = sexp_extract_param (keyparms, NULL, "-p?a?b?g?n?h?+d",
1378                            &sk.E.p, &sk.E.a, &sk.E.b, &mpi_g, &sk.E.n,
1379                            &sk.E.h, &sk.d, NULL);
1380   if (rc)
1381     goto leave;
1382   if (mpi_g)
1383     {
1384       point_init (&sk.E.G);
1385       rc = _gcry_ecc_os2ec (&sk.E.G, mpi_g);
1386       if (rc)
1387         goto leave;
1388     }
1389   /* Add missing parameters using the optional curve parameter.  */
1390   sexp_release (l1);
1391   l1 = sexp_find_token (keyparms, "curve", 5);
1392   if (l1)
1393     {
1394       curvename = sexp_nth_string (l1, 1);
1395       if (curvename)
1396         {
1397           rc = _gcry_ecc_fill_in_curve (0, curvename, &sk.E, NULL);
1398           if (rc)
1399             return rc;
1400         }
1401     }
1402   /* Guess required fields if a curve parameter has not been given.  */
1403   if (!curvename)
1404     {
1405       sk.E.model = MPI_EC_WEIERSTRASS;
1406       sk.E.dialect = ECC_DIALECT_STANDARD;
1407     }
1408   if (DBG_CIPHER)
1409     {
1410       log_debug ("ecc_decrypt info: %s/%s\n",
1411                  _gcry_ecc_model2str (sk.E.model),
1412                  _gcry_ecc_dialect2str (sk.E.dialect));
1413       if (sk.E.name)
1414         log_debug  ("ecc_decrypt name: %s\n", sk.E.name);
1415       log_printmpi ("ecc_decrypt    p", sk.E.p);
1416       log_printmpi ("ecc_decrypt    a", sk.E.a);
1417       log_printmpi ("ecc_decrypt    b", sk.E.b);
1418       log_printpnt ("ecc_decrypt  g",   &sk.E.G, NULL);
1419       log_printmpi ("ecc_decrypt    n", sk.E.n);
1420       log_printmpi ("ecc_decrypt    h", sk.E.h);
1421       if (!fips_mode ())
1422         log_printmpi ("ecc_decrypt    d", sk.d);
1423     }
1424   if (!sk.E.p || !sk.E.a || !sk.E.b || !sk.E.G.x || !sk.E.n || !sk.E.h || !sk.d)
1425     {
1426       rc = GPG_ERR_NO_OBJ;
1427       goto leave;
1428     }
1429
1430
1431   /*
1432    * Compute the plaintext.
1433    */
1434   rc = _gcry_ecc_os2ec (&kG, data_e);
1435   if (rc)
1436     {
1437       point_free (&kG);
1438       return rc;
1439     }
1440
1441   ec = _gcry_mpi_ec_p_internal_new (sk.E.model, sk.E.dialect, 0,
1442                                     sk.E.p, sk.E.a, sk.E.b);
1443
1444   /* R = dkG */
1445   _gcry_mpi_ec_mul_point (&R, sk.d, &kG, ec);
1446
1447   /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so:  */
1448   {
1449     gcry_mpi_t x, y;
1450
1451     x = mpi_new (0);
1452     y = mpi_new (0);
1453
1454     if (_gcry_mpi_ec_get_affine (x, y, &R, ec))
1455       log_fatal ("ecdh: Failed to get affine coordinates\n");
1456
1457     r = _gcry_ecc_ec2os (x, y, sk.E.p);
1458     if (!r)
1459       rc = gpg_err_code_from_syserror ();
1460     else
1461       rc = 0;
1462     mpi_free (x);
1463     mpi_free (y);
1464   }
1465   if (DBG_CIPHER)
1466     log_printmpi ("ecc_decrypt  res", r);
1467
1468   if (!rc)
1469     rc = sexp_build (r_plain, NULL, "(value %m)", r);
1470
1471  leave:
1472   point_free (&R);
1473   point_free (&kG);
1474   _gcry_mpi_release (r);
1475   _gcry_mpi_release (sk.E.p);
1476   _gcry_mpi_release (sk.E.a);
1477   _gcry_mpi_release (sk.E.b);
1478   _gcry_mpi_release (mpi_g);
1479   point_free (&sk.E.G);
1480   _gcry_mpi_release (sk.E.n);
1481   _gcry_mpi_release (sk.E.h);
1482   _gcry_mpi_release (sk.d);
1483   _gcry_mpi_release (data_e);
1484   xfree (curvename);
1485   sexp_release (l1);
1486   _gcry_mpi_ec_free (ec);
1487   _gcry_pk_util_free_encoding_ctx (&ctx);
1488   if (DBG_CIPHER)
1489     log_debug ("ecc_decrypt    => %s\n", gpg_strerror (rc));
1490   return rc;
1491 }
1492
1493
1494 /* Return the number of bits for the key described by PARMS.  On error
1495  * 0 is returned.  The format of PARMS starts with the algorithm name;
1496  * for example:
1497  *
1498  *   (ecc
1499  *     (p <mpi>)
1500  *     (a <mpi>)
1501  *     (b <mpi>)
1502  *     (g <mpi>)
1503  *     (n <mpi>)
1504  *     (q <mpi>))
1505  *
1506  * More parameters may be given currently P is needed.  FIXME: We
1507  * need allow for a "curve" parameter.
1508  */
1509 static unsigned int
1510 ecc_get_nbits (gcry_sexp_t parms)
1511 {
1512   gcry_sexp_t l1;
1513   gcry_mpi_t p;
1514   unsigned int nbits = 0;
1515   char *curve;
1516
1517   l1 = sexp_find_token (parms, "p", 1);
1518   if (!l1)
1519     { /* Parameter P not found - check whether we have "curve".  */
1520       l1 = sexp_find_token (parms, "curve", 5);
1521       if (!l1)
1522         return 0; /* Neither P nor CURVE found.  */
1523
1524       curve = sexp_nth_string (l1, 1);
1525       sexp_release (l1);
1526       if (!curve)
1527         return 0;  /* No curve name given (or out of core). */
1528
1529       if (_gcry_ecc_fill_in_curve (0, curve, NULL, &nbits))
1530         nbits = 0;
1531       xfree (curve);
1532     }
1533   else
1534     {
1535       p = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1536       sexp_release (l1);
1537       if (p)
1538         {
1539           nbits = mpi_get_nbits (p);
1540           _gcry_mpi_release (p);
1541         }
1542     }
1543   return nbits;
1544 }
1545
1546
1547 /* See rsa.c for a description of this function.  */
1548 static gpg_err_code_t
1549 compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparms)
1550 {
1551 #define N_COMPONENTS 7
1552   static const char names[N_COMPONENTS] = "pabgnhq";
1553   gpg_err_code_t rc;
1554   gcry_sexp_t l1;
1555   gcry_mpi_t values[N_COMPONENTS];
1556   int idx;
1557   char *curvename = NULL;
1558   int flags = 0;
1559   enum gcry_mpi_ec_models model = 0;
1560   enum ecc_dialects dialect = 0;
1561
1562   /* Clear the values first.  */
1563   for (idx=0; idx < N_COMPONENTS; idx++)
1564     values[idx] = NULL;
1565
1566
1567   /* Look for flags. */
1568   l1 = sexp_find_token (keyparms, "flags", 0);
1569   if (l1)
1570     {
1571       rc = _gcry_pk_util_parse_flaglist (l1, &flags, NULL);
1572       if (rc)
1573         goto leave;
1574     }
1575
1576   /* Extract the parameters.  */
1577   if ((flags & PUBKEY_FLAG_PARAM))
1578     {
1579       if ((flags & PUBKEY_FLAG_EDDSA))
1580         rc = sexp_extract_param (keyparms, NULL, "p?a?b?g?n?h?/q",
1581                                  &values[0], &values[1], &values[2],
1582                                  &values[3], &values[4], &values[5],
1583                                  &values[6], NULL);
1584       else
1585         rc = sexp_extract_param (keyparms, NULL, "p?a?b?g?n?h?q",
1586                                  &values[0], &values[1], &values[2],
1587                                  &values[3], &values[4], &values[5],
1588                                  &values[6], NULL);
1589     }
1590   else
1591     {
1592       if ((flags & PUBKEY_FLAG_EDDSA))
1593         rc = sexp_extract_param (keyparms, NULL, "/q",
1594                                  &values[6], NULL);
1595       else
1596         rc = sexp_extract_param (keyparms, NULL, "q",
1597                                  &values[6], NULL);
1598     }
1599   if (rc)
1600     goto leave;
1601
1602   /* Check whether a curve parameter is available and use that to fill
1603      in missing values.  */
1604   sexp_release (l1);
1605   l1 = sexp_find_token (keyparms, "curve", 5);
1606   if (l1)
1607     {
1608       curvename = sexp_nth_string (l1, 1);
1609       if (curvename)
1610         {
1611           rc = _gcry_ecc_update_curve_param (curvename,
1612                                              &model, &dialect,
1613                                              &values[0], &values[1], &values[2],
1614                                              &values[3], &values[4], &values[5]);
1615           if (rc)
1616             goto leave;
1617         }
1618     }
1619
1620   /* Guess required fields if a curve parameter has not been given.
1621      FIXME: This is a crude hacks.  We need to fix that.  */
1622   if (!curvename)
1623     {
1624       model = ((flags & PUBKEY_FLAG_EDDSA)
1625                ? MPI_EC_EDWARDS
1626                : MPI_EC_WEIERSTRASS);
1627       dialect = ((flags & PUBKEY_FLAG_EDDSA)
1628                  ? ECC_DIALECT_ED25519
1629                  : ECC_DIALECT_STANDARD);
1630     }
1631
1632   /* Check that all parameters are known and normalize all MPIs (that
1633      should not be required but we use an internal function later and
1634      thus we better make 100% sure that they are normalized). */
1635   for (idx = 0; idx < N_COMPONENTS; idx++)
1636     if (!values[idx])
1637       {
1638         rc = GPG_ERR_NO_OBJ;
1639         goto leave;
1640       }
1641     else
1642       _gcry_mpi_normalize (values[idx]);
1643
1644   /* Uncompress the public key with the exception of EdDSA where
1645      compression is the default and we thus compute the keygrip using
1646      the compressed version.  Because we don't support any non-eddsa
1647      compression, the only thing we need to do is to compress
1648      EdDSA.  */
1649   if ((flags & PUBKEY_FLAG_EDDSA))
1650     {
1651       if (dialect == ECC_DIALECT_ED25519)
1652         rc = _gcry_ecc_eddsa_ensure_compact (values[6], 256);
1653       else
1654         rc = GPG_ERR_NOT_IMPLEMENTED;
1655       if (rc)
1656         goto leave;
1657     }
1658
1659   /* Hash them all.  */
1660   for (idx = 0; idx < N_COMPONENTS; idx++)
1661     {
1662       char buf[30];
1663
1664       if (idx == 5)
1665         continue;               /* Skip cofactor. */
1666
1667       if (mpi_is_opaque (values[idx]))
1668         {
1669           const unsigned char *raw;
1670           unsigned int n;
1671
1672           raw = mpi_get_opaque (values[idx], &n);
1673           n = (n + 7)/8;
1674           snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], n);
1675           _gcry_md_write (md, buf, strlen (buf));
1676           _gcry_md_write (md, raw, n);
1677           _gcry_md_write (md, ")", 1);
1678         }
1679       else
1680         {
1681           unsigned char *rawmpi;
1682           unsigned int rawmpilen;
1683
1684           rawmpi = _gcry_mpi_get_buffer (values[idx], 0, &rawmpilen, NULL);
1685           if (!rawmpi)
1686             {
1687               rc = gpg_err_code_from_syserror ();
1688               goto leave;
1689             }
1690           snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], rawmpilen);
1691           _gcry_md_write (md, buf, strlen (buf));
1692           _gcry_md_write (md, rawmpi, rawmpilen);
1693           _gcry_md_write (md, ")", 1);
1694           xfree (rawmpi);
1695         }
1696     }
1697
1698  leave:
1699   xfree (curvename);
1700   sexp_release (l1);
1701   for (idx = 0; idx < N_COMPONENTS; idx++)
1702     _gcry_mpi_release (values[idx]);
1703
1704   return rc;
1705 #undef N_COMPONENTS
1706 }
1707
1708
1709 \f
1710 /*
1711    Low-level API helper functions.
1712  */
1713
1714 /* This is the worker function for gcry_pubkey_get_sexp for ECC
1715    algorithms.  Note that the caller has already stored NULL at
1716    R_SEXP.  */
1717 gpg_err_code_t
1718 _gcry_pk_ecc_get_sexp (gcry_sexp_t *r_sexp, int mode, mpi_ec_t ec)
1719 {
1720   gpg_err_code_t rc;
1721   gcry_mpi_t mpi_G = NULL;
1722   gcry_mpi_t mpi_Q = NULL;
1723
1724   if (!ec->p || !ec->a || !ec->b || !ec->G || !ec->n || !ec->h)
1725     return GPG_ERR_BAD_CRYPT_CTX;
1726
1727   if (mode == GCRY_PK_GET_SECKEY && !ec->d)
1728     return GPG_ERR_NO_SECKEY;
1729
1730   /* Compute the public point if it is missing.  */
1731   if (!ec->Q && ec->d)
1732     ec->Q = _gcry_ecc_compute_public (NULL, ec, NULL, NULL);
1733
1734   /* Encode G and Q.  */
1735   mpi_G = _gcry_mpi_ec_ec2os (ec->G, ec);
1736   if (!mpi_G)
1737     {
1738       rc = GPG_ERR_BROKEN_PUBKEY;
1739       goto leave;
1740     }
1741   if (!ec->Q)
1742     {
1743       rc = GPG_ERR_BAD_CRYPT_CTX;
1744       goto leave;
1745     }
1746
1747   if (ec->dialect == ECC_DIALECT_ED25519)
1748     {
1749       unsigned char *encpk;
1750       unsigned int encpklen;
1751
1752       rc = _gcry_ecc_eddsa_encodepoint (ec->Q, ec, NULL, NULL, 0,
1753                                         &encpk, &encpklen);
1754       if (rc)
1755         goto leave;
1756       mpi_Q = mpi_set_opaque (NULL, encpk, encpklen*8);
1757       encpk = NULL;
1758     }
1759   else
1760     {
1761       mpi_Q = _gcry_mpi_ec_ec2os (ec->Q, ec);
1762     }
1763   if (!mpi_Q)
1764     {
1765       rc = GPG_ERR_BROKEN_PUBKEY;
1766       goto leave;
1767     }
1768
1769   /* Fixme: We should return a curve name instead of the parameters if
1770      if know that they match a curve.  */
1771
1772   if (ec->d && (!mode || mode == GCRY_PK_GET_SECKEY))
1773     {
1774       /* Let's return a private key. */
1775       rc = sexp_build (r_sexp, NULL,
1776                        "(private-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)(h%m)(q%m)(d%m)))",
1777                        ec->p, ec->a, ec->b, mpi_G, ec->n, ec->h, mpi_Q, ec->d);
1778     }
1779   else if (ec->Q)
1780     {
1781       /* Let's return a public key.  */
1782       rc = sexp_build (r_sexp, NULL,
1783                        "(public-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)(h%m)(q%m)))",
1784                        ec->p, ec->a, ec->b, mpi_G, ec->n, ec->h, mpi_Q);
1785     }
1786   else
1787     rc = GPG_ERR_BAD_CRYPT_CTX;
1788
1789  leave:
1790   mpi_free (mpi_Q);
1791   mpi_free (mpi_G);
1792   return rc;
1793 }
1794
1795
1796 \f
1797 /*
1798      Self-test section.
1799  */
1800
1801
1802 static gpg_err_code_t
1803 selftests_ecdsa (selftest_report_func_t report)
1804 {
1805   const char *what;
1806   const char *errtxt;
1807
1808   what = "low-level";
1809   errtxt = NULL; /*selftest ();*/
1810   if (errtxt)
1811     goto failed;
1812
1813   /* FIXME:  need more tests.  */
1814
1815   return 0; /* Succeeded. */
1816
1817  failed:
1818   if (report)
1819     report ("pubkey", GCRY_PK_ECC, what, errtxt);
1820   return GPG_ERR_SELFTEST_FAILED;
1821 }
1822
1823
1824 /* Run a full self-test for ALGO and return 0 on success.  */
1825 static gpg_err_code_t
1826 run_selftests (int algo, int extended, selftest_report_func_t report)
1827 {
1828   (void)extended;
1829
1830   if (algo != GCRY_PK_ECC)
1831     return GPG_ERR_PUBKEY_ALGO;
1832
1833   return selftests_ecdsa (report);
1834 }
1835
1836
1837
1838 \f
1839 gcry_pk_spec_t _gcry_pubkey_spec_ecc =
1840   {
1841     GCRY_PK_ECC, { 0, 0 },
1842     (GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR),
1843     "ECC", ecc_names,
1844     "pabgnhq", "pabgnhqd", "sw", "rs", "pabgnhq",
1845     ecc_generate,
1846     ecc_check_secret_key,
1847     ecc_encrypt_raw,
1848     ecc_decrypt_raw,
1849     ecc_sign,
1850     ecc_verify,
1851     ecc_get_nbits,
1852     run_selftests,
1853     compute_keygrip,
1854     _gcry_ecc_get_curve,
1855     _gcry_ecc_get_param_sexp
1856   };