sexp: Add function gcry_sexp_extract_param.
[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   - If we support point compression we need to uncompress before
45     computing the keygrip
46
47   - In mpi/ec.c we use mpi_powm for x^2 mod p: Either implement a
48     special case in mpi_powm or check whether mpi_mulm is faster.
49
50 */
51
52
53 #include <config.h>
54 #include <stdio.h>
55 #include <stdlib.h>
56 #include <string.h>
57 #include <errno.h>
58
59 #include "g10lib.h"
60 #include "mpi.h"
61 #include "cipher.h"
62 #include "context.h"
63 #include "ec-context.h"
64 #include "pubkey-internal.h"
65 #include "ecc-common.h"
66
67
68 static const char *ecc_names[] =
69   {
70     "ecc",
71     "ecdsa",
72     "ecdh",
73     "eddsa",
74     NULL,
75   };
76
77
78 /* Registered progress function and its callback value. */
79 static void (*progress_cb) (void *, const char*, int, int, int);
80 static void *progress_cb_data;
81
82
83 #define point_init(a)  _gcry_mpi_point_init ((a))
84 #define point_free(a)  _gcry_mpi_point_free_parts ((a))
85
86 \f
87 /* Local prototypes. */
88 static void test_keys (ECC_secret_key * sk, unsigned int nbits);
89 static int check_secret_key (ECC_secret_key * sk);
90 static gpg_err_code_t sign_ecdsa (gcry_mpi_t input, ECC_secret_key *skey,
91                                   gcry_mpi_t r, gcry_mpi_t s,
92                                   int flags, int hashalgo);
93 static gpg_err_code_t verify_ecdsa (gcry_mpi_t input, ECC_public_key *pkey,
94                                     gcry_mpi_t r, gcry_mpi_t s);
95
96 static gcry_mpi_t gen_y_2 (gcry_mpi_t x, elliptic_curve_t * base);
97 static unsigned int ecc_get_nbits (gcry_sexp_t parms);
98
99
100
101 \f
102 void
103 _gcry_register_pk_ecc_progress (void (*cb) (void *, const char *,
104                                             int, int, int),
105                                 void *cb_data)
106 {
107   progress_cb = cb;
108   progress_cb_data = cb_data;
109 }
110
111 /* static void */
112 /* progress (int c) */
113 /* { */
114 /*   if (progress_cb) */
115 /*     progress_cb (progress_cb_data, "pk_ecc", c, 0, 0); */
116 /* } */
117
118
119 \f
120
121 /*
122  * Solve the right side of the Weierstrass equation.
123  */
124 static gcry_mpi_t
125 gen_y_2 (gcry_mpi_t x, elliptic_curve_t *base)
126 {
127   gcry_mpi_t three, x_3, axb, y;
128
129   three = mpi_alloc_set_ui (3);
130   x_3 = mpi_new (0);
131   axb = mpi_new (0);
132   y   = mpi_new (0);
133
134   mpi_powm (x_3, x, three, base->p);
135   mpi_mulm (axb, base->a, x, base->p);
136   mpi_addm (axb, axb, base->b, base->p);
137   mpi_addm (y, x_3, axb, base->p);
138
139   mpi_free (x_3);
140   mpi_free (axb);
141   mpi_free (three);
142   return y; /* The quadratic value of the coordinate if it exist. */
143 }
144
145
146 /* Standard version of the key generation.  */
147 static gpg_err_code_t
148 nist_generate_key (ECC_secret_key *sk, elliptic_curve_t *E, mpi_ec_t ctx,
149                    gcry_random_level_t random_level, unsigned int nbits)
150 {
151   mpi_point_struct Q;
152
153   point_init (&Q);
154
155   /* Generate a secret.  */
156   sk->d = _gcry_dsa_gen_k (E->n, random_level);
157
158   /* Compute Q.  */
159   _gcry_mpi_ec_mul_point (&Q, sk->d, &E->G, ctx);
160
161   /* Copy the stuff to the key structures. */
162   sk->E.model = E->model;
163   sk->E.dialect = E->dialect;
164   sk->E.p = mpi_copy (E->p);
165   sk->E.a = mpi_copy (E->a);
166   sk->E.b = mpi_copy (E->b);
167   point_init (&sk->E.G);
168   point_set (&sk->E.G, &E->G);
169   sk->E.n = mpi_copy (E->n);
170   point_init (&sk->Q);
171
172   /* We want the Q=(x,y) be a "compliant key" in terms of the
173    * http://tools.ietf.org/html/draft-jivsov-ecc-compact, which simply
174    * means that we choose either Q=(x,y) or -Q=(x,p-y) such that we
175    * end up with the min(y,p-y) as the y coordinate.  Such a public
176    * key allows the most efficient compression: y can simply be
177    * dropped because we know that it's a minimum of the two
178    * possibilities without any loss of security.  */
179   {
180     gcry_mpi_t x, y, p_y;
181     const unsigned int pbits = mpi_get_nbits (E->p);
182
183     x = mpi_new (pbits);
184     y = mpi_new (pbits);
185     p_y = mpi_new (pbits);
186
187     if (_gcry_mpi_ec_get_affine (x, y, &Q, ctx))
188       log_fatal ("ecgen: Failed to get affine coordinates for %s\n", "Q");
189
190     mpi_sub (p_y, E->p, y);     /* p_y = p - y */
191
192     if (mpi_cmp (p_y, y) < 0)   /* p - y < p */
193       {
194         /* We need to end up with -Q; this assures that new Q's y is
195            the smallest one */
196         mpi_sub (sk->d, E->n, sk->d);   /* d = order - d */
197         gcry_mpi_point_snatch_set (&sk->Q, x, p_y, mpi_alloc_set_ui (1));
198
199       if (DBG_CIPHER)
200         log_debug ("ecgen converted Q to a compliant point\n");
201       }
202     else /* p - y >= p */
203       {
204         /* No change is needed exactly 50% of the time: just copy. */
205         point_set (&sk->Q, &Q);
206         if (DBG_CIPHER)
207           log_debug ("ecgen didn't need to convert Q to a compliant point\n");
208
209         mpi_free (p_y);
210         mpi_free (x);
211       }
212     mpi_free (y);
213   }
214
215   /* Now we can test our keys (this should never fail!).  */
216   test_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 (sign_ecdsa (test, sk, r, s, 0, 0) )
251     log_fatal ("ECDSA operation: sign failed\n");
252
253   if (verify_ecdsa (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 /*
274  * To check the validity of the value, recalculate the correspondence
275  * between the public value and the secret one.
276  */
277 static int
278 check_secret_key (ECC_secret_key * sk)
279 {
280   int rc = 1;
281   mpi_point_struct Q;
282   gcry_mpi_t y_2, y2;
283   gcry_mpi_t x1, x2;
284   mpi_ec_t ctx = NULL;
285
286   point_init (&Q);
287
288   /* ?primarity test of 'p' */
289   /*  (...) //!! */
290   /* G in E(F_p) */
291   y_2 = gen_y_2 (sk->E.G.x, &sk->E);   /*  y^2=x^3+a*x+b */
292   y2 = mpi_alloc (0);
293   x1 = mpi_alloc (0);
294   x2 = mpi_alloc (0);
295   mpi_mulm (y2, sk->E.G.y, sk->E.G.y, sk->E.p);      /*  y^2=y*y */
296   if (mpi_cmp (y_2, y2))
297     {
298       if (DBG_CIPHER)
299         log_debug ("Bad check: Point 'G' does not belong to curve 'E'!\n");
300       goto leave;
301     }
302   /* G != PaI */
303   if (!mpi_cmp_ui (sk->E.G.z, 0))
304     {
305       if (DBG_CIPHER)
306         log_debug ("Bad check: 'G' cannot be Point at Infinity!\n");
307       goto leave;
308     }
309
310   ctx = _gcry_mpi_ec_p_internal_new (sk->E.model, sk->E.dialect,
311                                      sk->E.p, sk->E.a, sk->E.b);
312
313   _gcry_mpi_ec_mul_point (&Q, sk->E.n, &sk->E.G, ctx);
314   if (mpi_cmp_ui (Q.z, 0))
315     {
316       if (DBG_CIPHER)
317         log_debug ("check_secret_key: E is not a curve of order n\n");
318       goto leave;
319     }
320   /* pubkey cannot be PaI */
321   if (!mpi_cmp_ui (sk->Q.z, 0))
322     {
323       if (DBG_CIPHER)
324         log_debug ("Bad check: Q can not be a Point at Infinity!\n");
325       goto leave;
326     }
327   /* pubkey = [d]G over E */
328   _gcry_mpi_ec_mul_point (&Q, sk->d, &sk->E.G, ctx);
329
330   if (_gcry_mpi_ec_get_affine (x1, y_2, &Q, ctx))
331     {
332       if (DBG_CIPHER)
333         log_debug ("Bad check: Q can not be a Point at Infinity!\n");
334       goto leave;
335     }
336
337   /* Fast path for loaded secret keys - Q is already in affine coordinates */
338   if (!mpi_cmp_ui (sk->Q.z, 1))
339     {
340       if (mpi_cmp (x1, sk->Q.x) || mpi_cmp (y_2, sk->Q.y))
341         {
342           if (DBG_CIPHER)
343             log_debug
344               ("Bad check: There is NO correspondence between 'd' and 'Q'!\n");
345           goto leave;
346         }
347     }
348   else
349     {
350       if (_gcry_mpi_ec_get_affine (x2, y2, &sk->Q, ctx))
351         {
352           if (DBG_CIPHER)
353             log_debug ("Bad check: Q can not be a Point at Infinity!\n");
354           goto leave;
355         }
356
357       if (mpi_cmp (x1, x2) || mpi_cmp (y_2, y2))
358         {
359           if (DBG_CIPHER)
360             log_debug
361               ("Bad check: There is NO correspondence between 'd' and 'Q'!\n");
362           goto leave;
363         }
364     }
365   rc = 0; /* Okay.  */
366
367  leave:
368   _gcry_mpi_ec_free (ctx);
369   mpi_free (x2);
370   mpi_free (x1);
371   mpi_free (y2);
372   mpi_free (y_2);
373   point_free (&Q);
374   return rc;
375 }
376
377
378 /* Compute an ECDSA signature.
379  * Return the signature struct (r,s) from the message hash.  The caller
380  * must have allocated R and S.
381  */
382 static gpg_err_code_t
383 sign_ecdsa (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s,
384             int flags, int hashalgo)
385 {
386   gpg_err_code_t err = 0;
387   int extraloops = 0;
388   gcry_mpi_t k, dr, sum, k_1, x;
389   mpi_point_struct I;
390   gcry_mpi_t hash;
391   const void *abuf;
392   unsigned int abits, qbits;
393   mpi_ec_t ctx;
394
395   if (DBG_CIPHER)
396     log_mpidump ("ecdsa sign hash  ", input );
397
398   qbits = mpi_get_nbits (skey->E.n);
399
400   /* Convert the INPUT into an MPI if needed.  */
401   if (mpi_is_opaque (input))
402     {
403       abuf = gcry_mpi_get_opaque (input, &abits);
404       err = gpg_err_code (gcry_mpi_scan (&hash, GCRYMPI_FMT_USG,
405                                          abuf, (abits+7)/8, NULL));
406       if (err)
407         return err;
408       if (abits > qbits)
409         gcry_mpi_rshift (hash, hash, abits - qbits);
410     }
411   else
412     hash = input;
413
414
415   k = NULL;
416   dr = mpi_alloc (0);
417   sum = mpi_alloc (0);
418   k_1 = mpi_alloc (0);
419   x = mpi_alloc (0);
420   point_init (&I);
421
422   ctx = _gcry_mpi_ec_p_internal_new (skey->E.model, skey->E.dialect,
423                                      skey->E.p, skey->E.a, skey->E.b);
424
425   /* Two loops to avoid R or S are zero.  This is more of a joke than
426      a real demand because the probability of them being zero is less
427      than any hardware failure.  Some specs however require it.  */
428   do
429     {
430       do
431         {
432           mpi_free (k);
433           k = NULL;
434           if ((flags & PUBKEY_FLAG_RFC6979) && hashalgo)
435             {
436               /* Use Pornin's method for deterministic DSA.  If this
437                  flag is set, it is expected that HASH is an opaque
438                  MPI with the to be signed hash.  That hash is also
439                  used as h1 from 3.2.a.  */
440               if (!mpi_is_opaque (input))
441                 {
442                   err = GPG_ERR_CONFLICT;
443                   goto leave;
444                 }
445
446               abuf = gcry_mpi_get_opaque (input, &abits);
447               err = _gcry_dsa_gen_rfc6979_k (&k, skey->E.n, skey->d,
448                                              abuf, (abits+7)/8,
449                                              hashalgo, extraloops);
450               if (err)
451                 goto leave;
452               extraloops++;
453             }
454           else
455             k = _gcry_dsa_gen_k (skey->E.n, GCRY_STRONG_RANDOM);
456
457           _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx);
458           if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx))
459             {
460               if (DBG_CIPHER)
461                 log_debug ("ecc sign: Failed to get affine coordinates\n");
462               err = GPG_ERR_BAD_SIGNATURE;
463               goto leave;
464             }
465           mpi_mod (r, x, skey->E.n);  /* r = x mod n */
466         }
467       while (!mpi_cmp_ui (r, 0));
468
469       mpi_mulm (dr, skey->d, r, skey->E.n); /* dr = d*r mod n  */
470       mpi_addm (sum, hash, dr, skey->E.n);  /* sum = hash + (d*r) mod n  */
471       mpi_invm (k_1, k, skey->E.n);         /* k_1 = k^(-1) mod n  */
472       mpi_mulm (s, k_1, sum, skey->E.n);    /* s = k^(-1)*(hash+(d*r)) mod n */
473     }
474   while (!mpi_cmp_ui (s, 0));
475
476   if (DBG_CIPHER)
477     {
478       log_mpidump ("ecdsa sign result r ", r);
479       log_mpidump ("ecdsa sign result s ", s);
480     }
481
482  leave:
483   _gcry_mpi_ec_free (ctx);
484   point_free (&I);
485   mpi_free (x);
486   mpi_free (k_1);
487   mpi_free (sum);
488   mpi_free (dr);
489   mpi_free (k);
490
491   if (hash != input)
492     mpi_free (hash);
493
494   return err;
495 }
496
497
498 /* Verify an ECDSA signature.
499  * Check if R and S verifies INPUT.
500  */
501 static gpg_err_code_t
502 verify_ecdsa (gcry_mpi_t input, ECC_public_key *pkey,
503               gcry_mpi_t r, gcry_mpi_t s)
504 {
505   gpg_err_code_t err = 0;
506   gcry_mpi_t h, h1, h2, x;
507   mpi_point_struct Q, Q1, Q2;
508   mpi_ec_t ctx;
509
510   if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) )
511     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < r < n  failed.  */
512   if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) )
513     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < s < n  failed.  */
514
515   h  = mpi_alloc (0);
516   h1 = mpi_alloc (0);
517   h2 = mpi_alloc (0);
518   x = mpi_alloc (0);
519   point_init (&Q);
520   point_init (&Q1);
521   point_init (&Q2);
522
523   ctx = _gcry_mpi_ec_p_internal_new (pkey->E.model, pkey->E.dialect,
524                                      pkey->E.p, pkey->E.a, pkey->E.b);
525
526   /* h  = s^(-1) (mod n) */
527   mpi_invm (h, s, pkey->E.n);
528   /* h1 = hash * s^(-1) (mod n) */
529   mpi_mulm (h1, input, h, pkey->E.n);
530   /* Q1 = [ hash * s^(-1) ]G  */
531   _gcry_mpi_ec_mul_point (&Q1, h1, &pkey->E.G, ctx);
532   /* h2 = r * s^(-1) (mod n) */
533   mpi_mulm (h2, r, h, pkey->E.n);
534   /* Q2 = [ r * s^(-1) ]Q */
535   _gcry_mpi_ec_mul_point (&Q2, h2, &pkey->Q, ctx);
536   /* Q  = ([hash * s^(-1)]G) + ([r * s^(-1)]Q) */
537   _gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ctx);
538
539   if (!mpi_cmp_ui (Q.z, 0))
540     {
541       if (DBG_CIPHER)
542           log_debug ("ecc verify: Rejected\n");
543       err = GPG_ERR_BAD_SIGNATURE;
544       goto leave;
545     }
546   if (_gcry_mpi_ec_get_affine (x, NULL, &Q, ctx))
547     {
548       if (DBG_CIPHER)
549         log_debug ("ecc verify: Failed to get affine coordinates\n");
550       err = GPG_ERR_BAD_SIGNATURE;
551       goto leave;
552     }
553   mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */
554   if (mpi_cmp (x, r))   /* x != r */
555     {
556       if (DBG_CIPHER)
557         {
558           log_mpidump ("     x", x);
559           log_mpidump ("     r", r);
560           log_mpidump ("     s", s);
561         }
562       err = GPG_ERR_BAD_SIGNATURE;
563       goto leave;
564     }
565
566  leave:
567   _gcry_mpi_ec_free (ctx);
568   point_free (&Q2);
569   point_free (&Q1);
570   point_free (&Q);
571   mpi_free (x);
572   mpi_free (h2);
573   mpi_free (h1);
574   mpi_free (h);
575   return err;
576 }
577
578
579 \f
580 static void
581 reverse_buffer (unsigned char *buffer, unsigned int length)
582 {
583   unsigned int tmp, i;
584
585   for (i=0; i < length/2; i++)
586     {
587       tmp = buffer[i];
588       buffer[i] = buffer[length-1-i];
589       buffer[length-1-i] = tmp;
590     }
591 }
592
593
594 /* Encode MPI using the EdDSA scheme.  MINLEN specifies the required
595    length of the buffer in bytes.  On success 0 is returned an a
596    malloced buffer with the encoded point is stored at R_BUFFER; the
597    length of this buffer is stored at R_BUFLEN.  */
598 static gpg_err_code_t
599 eddsa_encodempi (gcry_mpi_t mpi, unsigned int minlen,
600                  unsigned char **r_buffer, unsigned int *r_buflen)
601 {
602   unsigned char *rawmpi;
603   unsigned int rawmpilen;
604
605   rawmpi = _gcry_mpi_get_buffer (mpi, minlen, &rawmpilen, NULL);
606   if (!rawmpi)
607     return gpg_err_code_from_syserror ();
608
609   *r_buffer = rawmpi;
610   *r_buflen = rawmpilen;
611   return 0;
612 }
613
614
615 /* Encode (X,Y) using the EdDSA scheme.  MINLEN is the required length
616    in bytes for the result.  On success 0 is returned and a malloced
617    buffer with the encoded point is stored at R_BUFFER; the length of
618    this buffer is stored at R_BUFLEN.  */
619 static gpg_err_code_t
620 eddsa_encode_x_y (gcry_mpi_t x, gcry_mpi_t y, unsigned int minlen,
621                   unsigned char **r_buffer, unsigned int *r_buflen)
622 {
623   unsigned char *rawmpi;
624   unsigned int rawmpilen;
625
626   rawmpi = _gcry_mpi_get_buffer (y, minlen, &rawmpilen, NULL);
627   if (!rawmpi)
628     return gpg_err_code_from_syserror ();
629   if (mpi_test_bit (x, 0) && rawmpilen)
630     rawmpi[rawmpilen - 1] |= 0x80;  /* Set sign bit.  */
631
632   *r_buffer = rawmpi;
633   *r_buflen = rawmpilen;
634   return 0;
635 }
636
637 /* Encode POINT using the EdDSA scheme.  X and Y are either scratch
638    variables supplied by the caller or NULL.  CTX is the usual
639    context.  On success 0 is returned and a malloced buffer with the
640    encoded point is stored at R_BUFFER; the length of this buffer is
641    stored at R_BUFLEN.  */
642 gpg_err_code_t
643 _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ec,
644                              gcry_mpi_t x_in, gcry_mpi_t y_in,
645                              unsigned char **r_buffer, unsigned int *r_buflen)
646 {
647   gpg_err_code_t rc;
648   gcry_mpi_t x, y;
649
650   x = x_in? x_in : mpi_new (0);
651   y = y_in? y_in : mpi_new (0);
652
653   if (_gcry_mpi_ec_get_affine (x, y, point, ec))
654     {
655       log_error ("eddsa_encodepoint: Failed to get affine coordinates\n");
656       rc = GPG_ERR_INTERNAL;
657     }
658   else
659     rc = eddsa_encode_x_y (x, y, ec->nbits/8, r_buffer, r_buflen);
660
661   if (!x_in)
662     mpi_free (x);
663   if (!y_in)
664     mpi_free (y);
665   return rc;
666 }
667
668
669 /* Decode the EdDSA style encoded PK and set it into RESULT.  CTX is
670    the usual curve context.  If R_ENCPK is not NULL, the encoded PK is
671    stored at that address; this is a new copy to be released by the
672    caller.  In contrast to the supplied PK, this is not an MPI and
673    thus guarnateed to be properly padded.  R_ENCPKLEN received the
674    length of that encoded key.  */
675 gpg_err_code_t
676 _gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result,
677                              unsigned char **r_encpk, unsigned int *r_encpklen)
678 {
679   gpg_err_code_t rc;
680   unsigned char *rawmpi;
681   unsigned int rawmpilen;
682   gcry_mpi_t yy, t, x, p1, p2, p3;
683   int sign;
684
685   if (mpi_is_opaque (pk))
686     {
687       const unsigned char *buf;
688
689       buf = gcry_mpi_get_opaque (pk, &rawmpilen);
690       if (!buf)
691         return GPG_ERR_INV_OBJ;
692       rawmpilen = (rawmpilen + 7)/8;
693
694       /* First check whether the public key has been given in standard
695          uncompressed format.  No need to recover x in this case.
696          Detection is easy: The size of the buffer will be odd and the
697          first byte be 0x04.  */
698       if (rawmpilen > 1 && buf[0] == 0x04 && (rawmpilen%2))
699         {
700           gcry_mpi_t y;
701
702           rc = gcry_mpi_scan (&x, GCRYMPI_FMT_STD,
703                               buf+1, (rawmpilen-1)/2, NULL);
704           if (rc)
705             return rc;
706           rc = gcry_mpi_scan (&y, GCRYMPI_FMT_STD,
707                               buf+1+(rawmpilen-1)/2, (rawmpilen-1)/2, NULL);
708           if (rc)
709             {
710               mpi_free (x);
711               return rc;
712             }
713
714           if (r_encpk)
715             {
716               rc = eddsa_encode_x_y (x, y, ctx->nbits/8, r_encpk, r_encpklen);
717               if (rc)
718                 {
719                   mpi_free (x);
720                   mpi_free (y);
721                   return rc;
722                 }
723             }
724           mpi_snatch (result->x, x);
725           mpi_snatch (result->y, y);
726           mpi_set_ui (result->z, 1);
727           return 0;
728         }
729
730       /* EdDSA compressed point.  */
731       rawmpi = gcry_malloc (rawmpilen? rawmpilen:1);
732       if (!rawmpi)
733         return gpg_err_code_from_syserror ();
734       memcpy (rawmpi, buf, rawmpilen);
735       reverse_buffer (rawmpi, rawmpilen);
736     }
737   else
738     {
739       /* Note: Without using an opaque MPI it is not reliable possible
740          to find out whether the public key has been given in
741          uncompressed format.  Thus we expect EdDSA format here.  */
742       rawmpi = _gcry_mpi_get_buffer (pk, ctx->nbits/8, &rawmpilen, NULL);
743       if (!rawmpi)
744         return gpg_err_code_from_syserror ();
745     }
746
747   if (rawmpilen)
748     {
749       sign = !!(rawmpi[0] & 0x80);
750       rawmpi[0] &= 0x7f;
751     }
752   else
753     sign = 0;
754   _gcry_mpi_set_buffer (result->y, rawmpi, rawmpilen, 0);
755   if (r_encpk)
756     {
757       /* Revert to little endian.  */
758       if (sign && rawmpilen)
759         rawmpi[0] |= 0x80;
760       reverse_buffer (rawmpi, rawmpilen);
761       *r_encpk = rawmpi;
762       if (r_encpklen)
763         *r_encpklen = rawmpilen;
764     }
765   else
766     gcry_free (rawmpi);
767
768   /* Now recover X.  */
769   /* t = (y^2-1) · ((b*y^2+1)^{p-2} mod p) */
770   x = mpi_new (0);
771   yy = mpi_new (0);
772   mpi_mul (yy, result->y, result->y);
773   t = mpi_copy (yy);
774   mpi_mul (t, t, ctx->b);
775   mpi_add_ui (t, t, 1);
776   p2 = mpi_copy (ctx->p);
777   mpi_sub_ui (p2, p2, 2);
778   mpi_powm (t, t, p2, ctx->p);
779
780   mpi_sub_ui (yy, yy, 1);
781   mpi_mul (t, yy, t);
782
783   /* x = t^{(p+3)/8} mod p */
784   p3 = mpi_copy (ctx->p);
785   mpi_add_ui (p3, p3, 3);
786   mpi_fdiv_q (p3, p3, mpi_const (MPI_C_EIGHT));
787   mpi_powm (x, t, p3, ctx->p);
788
789   /* (x^2 - t) % p != 0 ? x = (x*(2^{(p-1)/4} mod p)) % p */
790   mpi_mul (yy, x, x);
791   mpi_subm (yy, yy, t, ctx->p);
792   if (mpi_cmp_ui (yy, 0))
793     {
794       p1 = mpi_copy (ctx->p);
795       mpi_sub_ui (p1, p1, 1);
796       mpi_fdiv_q (p1, p1, mpi_const (MPI_C_FOUR));
797       mpi_powm (yy, mpi_const (MPI_C_TWO), p1, ctx->p);
798       mpi_mulm (x, x, yy, ctx->p);
799     }
800   else
801     p1 = NULL;
802
803   /* is_odd(x) ? x = p-x */
804   if (mpi_test_bit (x, 0))
805     mpi_sub (x, ctx->p, x);
806
807   /* lowbit(x) != highbit(input) ?  x = p-x */
808   if (mpi_test_bit (x, 0) != sign)
809     mpi_sub (x, ctx->p, x);
810
811   mpi_set (result->x, x);
812   mpi_set_ui (result->z, 1);
813
814   gcry_mpi_release (x);
815   gcry_mpi_release (yy);
816   gcry_mpi_release (t);
817   gcry_mpi_release (p3);
818   gcry_mpi_release (p2);
819   gcry_mpi_release (p1);
820
821   return 0;
822 }
823
824
825 /* Ed25519 version of the key generation.  */
826 static gpg_err_code_t
827 eddsa_generate_key (ECC_secret_key *sk, elliptic_curve_t *E, mpi_ec_t ctx,
828                     gcry_random_level_t random_level)
829 {
830   gpg_err_code_t rc;
831   int b = 256/8;             /* The only size we currently support.  */
832   gcry_mpi_t a, x, y;
833   mpi_point_struct Q;
834   char *dbuf;
835   size_t dlen;
836   gcry_buffer_t hvec[1];
837   unsigned char *hash_d = NULL;
838
839   point_init (&Q);
840   memset (hvec, 0, sizeof hvec);
841
842   a = mpi_snew (0);
843   x = mpi_new (0);
844   y = mpi_new (0);
845
846   /* Generate a secret.  */
847   hash_d = gcry_malloc_secure (2*b);
848   if (!hash_d)
849     {
850       rc = gpg_error_from_syserror ();
851       goto leave;
852     }
853   dlen = b;
854   dbuf = gcry_random_bytes_secure (dlen, random_level);
855
856   /* Compute the A value.  */
857   hvec[0].data = dbuf;
858   hvec[0].len = dlen;
859   rc = _gcry_md_hash_buffers (GCRY_MD_SHA512, 0, hash_d, hvec, 1);
860   if (rc)
861     goto leave;
862   sk->d = _gcry_mpi_set_opaque (NULL, dbuf, dlen*8);
863   dbuf = NULL;
864   reverse_buffer (hash_d, 32);  /* Only the first half of the hash.  */
865   hash_d[0] = (hash_d[0] & 0x7f) | 0x40;
866   hash_d[31] &= 0xf8;
867   _gcry_mpi_set_buffer (a, hash_d, 32, 0);
868   gcry_free (hash_d); hash_d = NULL;
869   /* log_printmpi ("ecgen         a", a); */
870
871   /* Compute Q.  */
872   _gcry_mpi_ec_mul_point (&Q, a, &E->G, ctx);
873   if (DBG_CIPHER)
874     log_printpnt ("ecgen      pk", &Q, ctx);
875
876   /* Copy the stuff to the key structures. */
877   sk->E.model = E->model;
878   sk->E.dialect = E->dialect;
879   sk->E.p = mpi_copy (E->p);
880   sk->E.a = mpi_copy (E->a);
881   sk->E.b = mpi_copy (E->b);
882   point_init (&sk->E.G);
883   point_set (&sk->E.G, &E->G);
884   sk->E.n = mpi_copy (E->n);
885   point_init (&sk->Q);
886   point_set (&sk->Q, &Q);
887
888  leave:
889   gcry_mpi_release (a);
890   gcry_mpi_release (x);
891   gcry_mpi_release (y);
892   gcry_free (hash_d);
893   return rc;
894 }
895
896
897 /* Compute an EdDSA signature. See:
898  *   [ed25519] 23pp. (PDF) Daniel J. Bernstein, Niels Duif, Tanja
899  *   Lange, Peter Schwabe, Bo-Yin Yang. High-speed high-security
900  *   signatures.  Journal of Cryptographic Engineering 2 (2012), 77-89.
901  *   Document ID: a1a62a2f76d23f65d622484ddd09caf8.
902  *   URL: http://cr.yp.to/papers.html#ed25519. Date: 2011.09.26.
903  *
904  * Despite that this function requires the specification of a hash
905  * algorithm, we only support what has been specified by the paper.
906  * This may change in the future.  Note that we don't check the used
907  * curve; the user is responsible to use Ed25519.
908  *
909  * Return the signature struct (r,s) from the message hash.  The caller
910  * must have allocated R_R and S.
911  */
912 static gpg_err_code_t
913 sign_eddsa (gcry_mpi_t input, ECC_secret_key *skey,
914             gcry_mpi_t r_r, gcry_mpi_t s, int hashalgo, gcry_mpi_t pk)
915 {
916   int rc;
917   mpi_ec_t ctx = NULL;
918   int b;
919   unsigned int tmp;
920   unsigned char *digest;
921   gcry_buffer_t hvec[3];
922   const void *mbuf;
923   size_t mlen;
924   unsigned char *rawmpi = NULL;
925   unsigned int rawmpilen;
926   unsigned char *encpk = NULL; /* Encoded public key.  */
927   unsigned int encpklen;
928   mpi_point_struct I;          /* Intermediate value.  */
929   mpi_point_struct Q;          /* Public key.  */
930   gcry_mpi_t a, x, y, r;
931
932   memset (hvec, 0, sizeof hvec);
933
934   if (!mpi_is_opaque (input))
935     return GPG_ERR_INV_DATA;
936   if (hashalgo != GCRY_MD_SHA512)
937     return GPG_ERR_DIGEST_ALGO;
938
939   /* Initialize some helpers.  */
940   point_init (&I);
941   point_init (&Q);
942   a = mpi_snew (0);
943   x = mpi_new (0);
944   y = mpi_new (0);
945   r = mpi_new (0);
946   ctx = _gcry_mpi_ec_p_internal_new (skey->E.model, skey->E.dialect,
947                                      skey->E.p, skey->E.a, skey->E.b);
948   b = (ctx->nbits+7)/8;
949   if (b != 256/8)
950     return GPG_ERR_INTERNAL; /* We only support 256 bit. */
951
952   digest = gcry_calloc_secure (2, b);
953   if (!digest)
954     {
955       rc = gpg_err_code_from_syserror ();
956       goto leave;
957     }
958
959   /* Hash the secret key.  We clear DIGEST so we can use it as input
960      to left pad the key with zeroes for hashing.  */
961   rawmpi = _gcry_mpi_get_buffer (skey->d, 0, &rawmpilen, NULL);
962   if (!rawmpi)
963     {
964       rc = gpg_err_code_from_syserror ();
965       goto leave;
966     }
967   hvec[0].data = digest;
968   hvec[0].off = 0;
969   hvec[0].len = b > rawmpilen? b - rawmpilen : 0;
970   hvec[1].data = rawmpi;
971   hvec[1].off = 0;
972   hvec[1].len = rawmpilen;
973   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2);
974   gcry_free (rawmpi); rawmpi = NULL;
975   if (rc)
976     goto leave;
977
978   /* Compute the A value (this modifies DIGEST).  */
979   reverse_buffer (digest, 32);  /* Only the first half of the hash.  */
980   digest[0] = (digest[0] & 0x7f) | 0x40;
981   digest[31] &= 0xf8;
982   _gcry_mpi_set_buffer (a, digest, 32, 0);
983
984   /* Compute the public key if it has not been supplied as optional
985      parameter.  */
986   if (pk)
987     {
988       rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q,  &encpk, &encpklen);
989       if (rc)
990         goto leave;
991       if (DBG_CIPHER)
992         log_printhex ("* e_pk", encpk, encpklen);
993       if (!_gcry_mpi_ec_curve_point (&Q, ctx))
994         {
995           rc = GPG_ERR_BROKEN_PUBKEY;
996           goto leave;
997         }
998     }
999   else
1000     {
1001       _gcry_mpi_ec_mul_point (&Q, a, &skey->E.G, ctx);
1002       rc = _gcry_ecc_eddsa_encodepoint (&Q, ctx, x, y, &encpk, &encpklen);
1003       if (rc)
1004         goto leave;
1005       if (DBG_CIPHER)
1006         log_printhex ("  e_pk", encpk, encpklen);
1007     }
1008
1009   /* Compute R.  */
1010   mbuf = gcry_mpi_get_opaque (input, &tmp);
1011   mlen = (tmp +7)/8;
1012   if (DBG_CIPHER)
1013     log_printhex ("     m", mbuf, mlen);
1014
1015   hvec[0].data = digest;
1016   hvec[0].off  = 32;
1017   hvec[0].len  = 32;
1018   hvec[1].data = (char*)mbuf;
1019   hvec[1].len  = mlen;
1020   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2);
1021   if (rc)
1022     goto leave;
1023   reverse_buffer (digest, 64);
1024   if (DBG_CIPHER)
1025     log_printhex ("     r", digest, 64);
1026   _gcry_mpi_set_buffer (r, digest, 64, 0);
1027   _gcry_mpi_ec_mul_point (&I, r, &skey->E.G, ctx);
1028   if (DBG_CIPHER)
1029     log_printpnt ("   r", &I, ctx);
1030
1031   /* Convert R into affine coordinates and apply encoding.  */
1032   rc = _gcry_ecc_eddsa_encodepoint (&I, ctx, x, y, &rawmpi, &rawmpilen);
1033   if (rc)
1034     goto leave;
1035   if (DBG_CIPHER)
1036     log_printhex ("   e_r", rawmpi, rawmpilen);
1037
1038   /* S = r + a * H(encodepoint(R) + encodepoint(pk) + m) mod n  */
1039   hvec[0].data = rawmpi;  /* (this is R) */
1040   hvec[0].off  = 0;
1041   hvec[0].len  = rawmpilen;
1042   hvec[1].data = encpk;
1043   hvec[1].off  = 0;
1044   hvec[1].len  = encpklen;
1045   hvec[2].data = (char*)mbuf;
1046   hvec[2].off  = 0;
1047   hvec[2].len  = mlen;
1048   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
1049   if (rc)
1050     goto leave;
1051
1052   /* No more need for RAWMPI thus we now transfer it to R_R.  */
1053   gcry_mpi_set_opaque (r_r, rawmpi, rawmpilen*8);
1054   rawmpi = NULL;
1055
1056   reverse_buffer (digest, 64);
1057   if (DBG_CIPHER)
1058     log_printhex (" H(R+)", digest, 64);
1059   _gcry_mpi_set_buffer (s, digest, 64, 0);
1060   mpi_mulm (s, s, a, skey->E.n);
1061   mpi_addm (s, s, r, skey->E.n);
1062   rc = eddsa_encodempi (s, b, &rawmpi, &rawmpilen);
1063   if (rc)
1064     goto leave;
1065   if (DBG_CIPHER)
1066     log_printhex ("   e_s", rawmpi, rawmpilen);
1067   gcry_mpi_set_opaque (s, rawmpi, rawmpilen*8);
1068   rawmpi = NULL;
1069
1070   rc = 0;
1071
1072  leave:
1073   gcry_mpi_release (a);
1074   gcry_mpi_release (x);
1075   gcry_mpi_release (y);
1076   gcry_mpi_release (r);
1077   gcry_free (digest);
1078   _gcry_mpi_ec_free (ctx);
1079   point_free (&I);
1080   point_free (&Q);
1081   gcry_free (encpk);
1082   gcry_free (rawmpi);
1083   return rc;
1084 }
1085
1086
1087 /* Verify an EdDSA signature.  See sign_eddsa for the reference.
1088  * Check if R_IN and S_IN verifies INPUT.  PKEY has the curve
1089  * parameters and PK is the EdDSA style encoded public key.
1090  */
1091 static gpg_err_code_t
1092 verify_eddsa (gcry_mpi_t input, ECC_public_key *pkey,
1093               gcry_mpi_t r_in, gcry_mpi_t s_in, int hashalgo, gcry_mpi_t pk)
1094 {
1095   int rc;
1096   mpi_ec_t ctx = NULL;
1097   int b;
1098   unsigned int tmp;
1099   mpi_point_struct Q;          /* Public key.  */
1100   unsigned char *encpk = NULL; /* Encoded public key.  */
1101   unsigned int encpklen;
1102   const void *mbuf, *rbuf;
1103   unsigned char *tbuf = NULL;
1104   size_t mlen, rlen;
1105   unsigned int tlen;
1106   unsigned char digest[64];
1107   gcry_buffer_t hvec[3];
1108   gcry_mpi_t h, s;
1109   mpi_point_struct Ia, Ib;
1110
1111   if (!mpi_is_opaque (input) || !mpi_is_opaque (r_in) || !mpi_is_opaque (s_in))
1112     return GPG_ERR_INV_DATA;
1113   if (hashalgo != GCRY_MD_SHA512)
1114     return GPG_ERR_DIGEST_ALGO;
1115
1116   point_init (&Q);
1117   point_init (&Ia);
1118   point_init (&Ib);
1119   h = mpi_new (0);
1120   s = mpi_new (0);
1121
1122   ctx = _gcry_mpi_ec_p_internal_new (pkey->E.model, pkey->E.dialect,
1123                                      pkey->E.p, pkey->E.a, pkey->E.b);
1124   b = ctx->nbits/8;
1125   if (b != 256/8)
1126     return GPG_ERR_INTERNAL; /* We only support 256 bit. */
1127
1128   /* Decode and check the public key.  */
1129   rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q, &encpk, &encpklen);
1130   if (rc)
1131     goto leave;
1132   if (!_gcry_mpi_ec_curve_point (&Q, ctx))
1133     {
1134       rc = GPG_ERR_BROKEN_PUBKEY;
1135       goto leave;
1136     }
1137   if (DBG_CIPHER)
1138     log_printhex ("  e_pk", encpk, encpklen);
1139   if (encpklen != b)
1140     {
1141       rc = GPG_ERR_INV_LENGTH;
1142       goto leave;
1143     }
1144
1145   /* Convert the other input parameters.  */
1146   mbuf = gcry_mpi_get_opaque (input, &tmp);
1147   mlen = (tmp +7)/8;
1148   if (DBG_CIPHER)
1149     log_printhex ("     m", mbuf, mlen);
1150   rbuf = gcry_mpi_get_opaque (r_in, &tmp);
1151   rlen = (tmp +7)/8;
1152   if (DBG_CIPHER)
1153     log_printhex ("     r", rbuf, rlen);
1154   if (rlen != b)
1155     {
1156       rc = GPG_ERR_INV_LENGTH;
1157       goto leave;
1158     }
1159
1160   /* h = H(encodepoint(R) + encodepoint(pk) + m)  */
1161   hvec[0].data = (char*)rbuf;
1162   hvec[0].off  = 0;
1163   hvec[0].len  = rlen;
1164   hvec[1].data = encpk;
1165   hvec[1].off  = 0;
1166   hvec[1].len  = encpklen;
1167   hvec[2].data = (char*)mbuf;
1168   hvec[2].off  = 0;
1169   hvec[2].len  = mlen;
1170   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
1171   if (rc)
1172     goto leave;
1173   reverse_buffer (digest, 64);
1174   if (DBG_CIPHER)
1175     log_printhex (" H(R+)", digest, 64);
1176   _gcry_mpi_set_buffer (h, digest, 64, 0);
1177
1178   /* According to the paper the best way for verification is:
1179          encodepoint(sG - h·Q) = encodepoint(r)
1180      because we don't need to decode R. */
1181   {
1182     void *sbuf;
1183     unsigned int slen;
1184
1185     sbuf = _gcry_mpi_get_opaque_copy (s_in, &tmp);
1186     slen = (tmp +7)/8;
1187     reverse_buffer (sbuf, slen);
1188     if (DBG_CIPHER)
1189       log_printhex ("     s", sbuf, slen);
1190     _gcry_mpi_set_buffer (s, sbuf, slen, 0);
1191     gcry_free (sbuf);
1192     if (slen != b)
1193       {
1194         rc = GPG_ERR_INV_LENGTH;
1195         goto leave;
1196       }
1197   }
1198
1199   _gcry_mpi_ec_mul_point (&Ia, s, &pkey->E.G, ctx);
1200   _gcry_mpi_ec_mul_point (&Ib, h, &Q, ctx);
1201   _gcry_mpi_neg (Ib.x, Ib.x);
1202   _gcry_mpi_ec_add_points (&Ia, &Ia, &Ib, ctx);
1203   rc = _gcry_ecc_eddsa_encodepoint (&Ia, ctx, s, h, &tbuf, &tlen);
1204   if (rc)
1205     goto leave;
1206   if (tlen != rlen || memcmp (tbuf, rbuf, tlen))
1207     {
1208       rc = GPG_ERR_BAD_SIGNATURE;
1209       goto leave;
1210     }
1211
1212   rc = 0;
1213
1214  leave:
1215   gcry_free (encpk);
1216   gcry_free (tbuf);
1217   _gcry_mpi_ec_free (ctx);
1218   gcry_mpi_release (s);
1219   gcry_mpi_release (h);
1220   point_free (&Ia);
1221   point_free (&Ib);
1222   point_free (&Q);
1223   return rc;
1224 }
1225
1226
1227 \f
1228 /*********************************************
1229  **************  interface  ******************
1230  *********************************************/
1231
1232 static gcry_err_code_t
1233 ecc_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
1234 {
1235   gpg_err_code_t rc;
1236   unsigned int nbits;
1237   elliptic_curve_t E;
1238   ECC_secret_key sk;
1239   gcry_mpi_t x = NULL;
1240   gcry_mpi_t y = NULL;
1241   char *curve_name = NULL;
1242   gcry_sexp_t l1;
1243   gcry_random_level_t random_level;
1244   mpi_ec_t ctx = NULL;
1245   gcry_sexp_t curve_info = NULL;
1246   gcry_sexp_t curve_flags = NULL;
1247   gcry_mpi_t base = NULL;
1248   gcry_mpi_t public = NULL;
1249   gcry_mpi_t secret = NULL;
1250   int flags = 0;
1251   int ed25519_with_ecdsa = 0;
1252
1253   memset (&E, 0, sizeof E);
1254   memset (&sk, 0, sizeof sk);
1255
1256   rc = _gcry_pk_util_get_nbits (genparms, &nbits);
1257   if (rc)
1258     return rc;
1259
1260   /* Parse the optional "curve" parameter. */
1261   l1 = gcry_sexp_find_token (genparms, "curve", 0);
1262   if (l1)
1263     {
1264       curve_name = _gcry_sexp_nth_string (l1, 1);
1265       gcry_sexp_release (l1);
1266       if (!curve_name)
1267         return GPG_ERR_INV_OBJ; /* No curve name or value too large. */
1268     }
1269
1270   /* Parse the optional transient-key flag.  */
1271   l1 = gcry_sexp_find_token (genparms, "transient-key", 0);
1272   if (l1)
1273     {
1274       flags |= PUBKEY_FLAG_TRANSIENT_KEY;
1275       gcry_sexp_release (l1);
1276     }
1277
1278   /* Parse the optional flags list.  */
1279   l1 = gcry_sexp_find_token (genparms, "flags", 0);
1280   if (l1)
1281     {
1282       rc = _gcry_pk_util_parse_flaglist (l1, &flags, NULL);
1283       gcry_sexp_release (l1);
1284       if (rc)
1285         goto leave;
1286     }
1287
1288   /* NBITS is required if no curve name has been given.  */
1289   if (!nbits && !curve_name)
1290     return GPG_ERR_NO_OBJ; /* No NBITS parameter. */
1291
1292   rc = _gcry_ecc_fill_in_curve (nbits, curve_name, &E, &nbits);
1293   gcry_free (curve_name); curve_name = NULL;
1294   if (rc)
1295     goto leave;
1296
1297   if (DBG_CIPHER)
1298     {
1299       log_debug ("ecgen curve info: %s/%s\n",
1300                  _gcry_ecc_model2str (E.model),
1301                  _gcry_ecc_dialect2str (E.dialect));
1302       if (E.name)
1303         log_debug ("ecgen curve used: %s\n", E.name);
1304       log_printmpi ("ecgen curve   p", E.p);
1305       log_printmpi ("ecgen curve   a", E.a);
1306       log_printmpi ("ecgen curve   b", E.b);
1307       log_printmpi ("ecgen curve   n", E.n);
1308       log_printpnt ("ecgen curve G", &E.G, NULL);
1309     }
1310
1311   if ((flags & PUBKEY_FLAG_TRANSIENT_KEY))
1312     random_level = GCRY_STRONG_RANDOM;
1313   else
1314     random_level = GCRY_VERY_STRONG_RANDOM;
1315
1316   ctx = _gcry_mpi_ec_p_internal_new (E.model, E.dialect, E.p, E.a, E.b);
1317   x = mpi_new (0);
1318   y = mpi_new (0);
1319
1320   switch (E.dialect)
1321     {
1322     case ECC_DIALECT_STANDARD:
1323       rc = nist_generate_key (&sk, &E, ctx, random_level, nbits);
1324       break;
1325     case ECC_DIALECT_ED25519:
1326       if ((flags & PUBKEY_FLAG_ECDSA))
1327         {
1328           ed25519_with_ecdsa = 1;
1329           rc = nist_generate_key (&sk, &E, ctx, random_level, nbits);
1330         }
1331       else
1332         rc = eddsa_generate_key (&sk, &E, ctx, random_level);
1333       break;
1334     default:
1335       rc = GPG_ERR_INTERNAL;
1336       break;
1337     }
1338   if (rc)
1339     goto leave;
1340
1341   /* Copy data to the result.  */
1342   if (_gcry_mpi_ec_get_affine (x, y, &sk.E.G, ctx))
1343     log_fatal ("ecgen: Failed to get affine coordinates for %s\n", "G");
1344   base = _gcry_ecc_ec2os (x, y, sk.E.p);
1345   if (sk.E.dialect == ECC_DIALECT_ED25519 && !ed25519_with_ecdsa)
1346     {
1347       unsigned char *encpk;
1348       unsigned int encpklen;
1349
1350       rc = _gcry_ecc_eddsa_encodepoint (&sk.Q, ctx, x, y, &encpk, &encpklen);
1351       if (rc)
1352         return rc;
1353       public = mpi_new (0);
1354       gcry_mpi_set_opaque (public, encpk, encpklen*8);
1355       encpk = NULL;
1356     }
1357   else
1358     {
1359       if (_gcry_mpi_ec_get_affine (x, y, &sk.Q, ctx))
1360         log_fatal ("ecgen: Failed to get affine coordinates for %s\n", "Q");
1361       public = _gcry_ecc_ec2os (x, y, sk.E.p);
1362     }
1363   secret = sk.d; sk.d = NULL;
1364   if (E.name)
1365     {
1366       rc = gcry_sexp_build (&curve_info, NULL, "(curve %s)", E.name);
1367       if (rc)
1368         goto leave;
1369     }
1370
1371   if (ed25519_with_ecdsa)
1372     {
1373       rc = gcry_sexp_build (&curve_info, NULL, "(flags ecdsa)");
1374       if (rc)
1375         goto leave;
1376     }
1377
1378   rc = gcry_sexp_build (r_skey, NULL,
1379                         "(key-data"
1380                         " (public-key"
1381                         "  (ecc%S%S(p%m)(a%m)(b%m)(g%m)(n%m)(q%m)))"
1382                         " (private-key"
1383                         "  (ecc%S%S(p%m)(a%m)(b%m)(g%m)(n%m)(q%m)(d%m)))"
1384                         " )",
1385                         curve_info, curve_flags,
1386                         sk.E.p, sk.E.a, sk.E.b, base, sk.E.n, public,
1387                         curve_info, curve_flags,
1388                         sk.E.p, sk.E.a, sk.E.b, base, sk.E.n, public, secret);
1389   if (rc)
1390     goto leave;
1391
1392   if (DBG_CIPHER)
1393     {
1394       log_printmpi ("ecgen result  p", sk.E.p);
1395       log_printmpi ("ecgen result  a", sk.E.a);
1396       log_printmpi ("ecgen result  b", sk.E.b);
1397       log_printmpi ("ecgen result  G", base);
1398       log_printmpi ("ecgen result  n", sk.E.n);
1399       log_printmpi ("ecgen result  Q", public);
1400       log_printmpi ("ecgen result  d", secret);
1401       if (ed25519_with_ecdsa)
1402         log_debug ("ecgen result  using Ed25519/ECDSA\n");
1403     }
1404
1405  leave:
1406   mpi_free (secret);
1407   mpi_free (public);
1408   mpi_free (base);
1409   {
1410     _gcry_ecc_curve_free (&sk.E);
1411     point_free (&sk.Q);
1412     mpi_free (sk.d);
1413   }
1414   _gcry_ecc_curve_free (&E);
1415   mpi_free (x);
1416   mpi_free (y);
1417   _gcry_mpi_ec_free (ctx);
1418   gcry_sexp_release (curve_info);
1419   return rc;
1420 }
1421
1422
1423 static gcry_err_code_t
1424 ecc_check_secret_key (gcry_sexp_t keyparms)
1425 {
1426   gcry_err_code_t rc;
1427   gcry_sexp_t l1 = NULL;
1428   char *curvename = NULL;
1429   gcry_mpi_t mpi_g = NULL;
1430   gcry_mpi_t mpi_q = NULL;
1431   ECC_secret_key sk;
1432
1433   memset (&sk, 0, sizeof sk);
1434
1435   /*
1436    * Extract the key.
1437    */
1438   rc = _gcry_sexp_extract_param (keyparms, NULL, "-p?a?b?g?n?/q?+d",
1439                                  &sk.E.p, &sk.E.a, &sk.E.b, &mpi_g, &sk.E.n,
1440                                  &mpi_q, &sk.d, NULL);
1441   if (rc)
1442     goto leave;
1443   if (mpi_g)
1444     {
1445       point_init (&sk.E.G);
1446       rc = _gcry_ecc_os2ec (&sk.E.G, mpi_g);
1447       if (rc)
1448         goto leave;
1449     }
1450   /* Add missing parameters using the optional curve parameter.  */
1451   gcry_sexp_release (l1);
1452   l1 = gcry_sexp_find_token (keyparms, "curve", 5);
1453   if (l1)
1454     {
1455       curvename = gcry_sexp_nth_string (l1, 1);
1456       if (curvename)
1457         {
1458           rc = _gcry_ecc_fill_in_curve (0, curvename, &sk.E, NULL);
1459           if (rc)
1460             return rc;
1461         }
1462     }
1463   /* Guess required fields if a curve parameter has not been given.
1464      FIXME: This is a crude hacks.  We need to fix that.  */
1465   if (!curvename)
1466     {
1467       sk.E.model = MPI_EC_WEIERSTRASS;
1468       sk.E.dialect = ECC_DIALECT_STANDARD;
1469     }
1470   if (DBG_CIPHER)
1471     {
1472       log_debug ("ecc_testkey inf: %s/%s\n",
1473                  _gcry_ecc_model2str (sk.E.model),
1474                  _gcry_ecc_dialect2str (sk.E.dialect));
1475       if (sk.E.name)
1476         log_debug  ("ecc_testkey nam: %s\n", sk.E.name);
1477       log_printmpi ("ecc_testkey   p", sk.E.p);
1478       log_printmpi ("ecc_testkey   a", sk.E.a);
1479       log_printmpi ("ecc_testkey   b", sk.E.b);
1480       log_printpnt ("ecc_testkey g",   &sk.E.G, NULL);
1481       log_printmpi ("ecc_testkey   n", sk.E.n);
1482       log_printmpi ("ecc_testkey   q", mpi_q);
1483       if (!fips_mode ())
1484         log_printmpi ("ecc_testkey   d", sk.d);
1485     }
1486   if (!sk.E.p || !sk.E.a || !sk.E.b || !sk.E.G.x || !sk.E.n || !sk.d)
1487     {
1488       rc = GPG_ERR_NO_OBJ;
1489       goto leave;
1490     }
1491
1492   if (mpi_q)
1493     {
1494       point_init (&sk.Q);
1495       rc = _gcry_ecc_os2ec (&sk.Q, mpi_q);
1496       if (rc)
1497         goto leave;
1498     }
1499   else
1500     {
1501       /* The current test requires Q.  */
1502       rc = GPG_ERR_NO_OBJ;
1503       goto leave;
1504     }
1505
1506   if (check_secret_key (&sk))
1507     rc = GPG_ERR_BAD_SECKEY;
1508
1509  leave:
1510   gcry_mpi_release (sk.E.p);
1511   gcry_mpi_release (sk.E.a);
1512   gcry_mpi_release (sk.E.b);
1513   gcry_mpi_release (mpi_g);
1514   point_free (&sk.E.G);
1515   gcry_mpi_release (sk.E.n);
1516   gcry_mpi_release (mpi_q);
1517   point_free (&sk.Q);
1518   gcry_mpi_release (sk.d);
1519   gcry_free (curvename);
1520   gcry_sexp_release (l1);
1521   if (DBG_CIPHER)
1522     log_debug ("ecc_testkey   => %s\n", gpg_strerror (rc));
1523   return rc;
1524 }
1525
1526
1527 static gcry_err_code_t
1528 ecc_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1529 {
1530   gcry_err_code_t rc;
1531   struct pk_encoding_ctx ctx;
1532   gcry_mpi_t data = NULL;
1533   gcry_sexp_t l1 = NULL;
1534   char *curvename = NULL;
1535   gcry_mpi_t mpi_g = NULL;
1536   gcry_mpi_t mpi_q = NULL;
1537   ECC_secret_key sk;
1538   gcry_mpi_t sig_r = NULL;
1539   gcry_mpi_t sig_s = NULL;
1540
1541   memset (&sk, 0, sizeof sk);
1542
1543   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_SIGN, 0);
1544
1545   /* Extract the data.  */
1546   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1547   if (rc)
1548     goto leave;
1549   if (DBG_CIPHER)
1550     log_mpidump ("ecc_sign   data", data);
1551
1552   /*
1553    * Extract the key.
1554    */
1555   rc = _gcry_sexp_extract_param (keyparms, NULL, "-p?a?b?g?n?/q?+d",
1556                                  &sk.E.p, &sk.E.a, &sk.E.b, &mpi_g, &sk.E.n,
1557                                  &mpi_q, &sk.d, NULL);
1558   if (rc)
1559     goto leave;
1560   if (mpi_g)
1561     {
1562       point_init (&sk.E.G);
1563       rc = _gcry_ecc_os2ec (&sk.E.G, mpi_g);
1564       if (rc)
1565         goto leave;
1566     }
1567   /* Add missing parameters using the optional curve parameter.  */
1568   gcry_sexp_release (l1);
1569   l1 = gcry_sexp_find_token (keyparms, "curve", 5);
1570   if (l1)
1571     {
1572       curvename = gcry_sexp_nth_string (l1, 1);
1573       if (curvename)
1574         {
1575           rc = _gcry_ecc_fill_in_curve (0, curvename, &sk.E, NULL);
1576           if (rc)
1577             return rc;
1578         }
1579     }
1580   /* Guess required fields if a curve parameter has not been given.
1581      FIXME: This is a crude hacks.  We need to fix that.  */
1582   if (!curvename)
1583     {
1584       sk.E.model = ((ctx.flags & PUBKEY_FLAG_EDDSA)
1585                     ? MPI_EC_TWISTEDEDWARDS
1586                     : MPI_EC_WEIERSTRASS);
1587       sk.E.dialect = ((ctx.flags & PUBKEY_FLAG_EDDSA)
1588                       ? ECC_DIALECT_ED25519
1589                       : ECC_DIALECT_STANDARD);
1590     }
1591   if (DBG_CIPHER)
1592     {
1593       log_debug ("ecc_sign   info: %s/%s%s\n",
1594                  _gcry_ecc_model2str (sk.E.model),
1595                  _gcry_ecc_dialect2str (sk.E.dialect),
1596                  (sk.E.dialect == ECC_DIALECT_ED25519
1597                   && (ctx.flags & PUBKEY_FLAG_ECDSA))? "ECDSA":"");
1598       if (sk.E.name)
1599         log_debug  ("ecc_sign   name: %s\n", sk.E.name);
1600       log_printmpi ("ecc_sign      p", sk.E.p);
1601       log_printmpi ("ecc_sign      a", sk.E.a);
1602       log_printmpi ("ecc_sign      b", sk.E.b);
1603       log_printpnt ("ecc_sign    g",   &sk.E.G, NULL);
1604       log_printmpi ("ecc_sign      n", sk.E.n);
1605       log_printmpi ("ecc_sign      q", mpi_q);
1606       if (!fips_mode ())
1607         log_printmpi ("ecc_sign      d", sk.d);
1608     }
1609   if (!sk.E.p || !sk.E.a || !sk.E.b || !sk.E.G.x || !sk.E.n || !sk.d)
1610     {
1611       rc = GPG_ERR_NO_OBJ;
1612       goto leave;
1613     }
1614
1615
1616   sig_r = gcry_mpi_new (0);
1617   sig_s = gcry_mpi_new (0);
1618   if ((ctx.flags & PUBKEY_FLAG_EDDSA))
1619     {
1620       /* EdDSA requires the public key.  */
1621       rc = sign_eddsa (data, &sk, sig_r, sig_s, ctx.hash_algo, mpi_q);
1622       if (!rc)
1623         rc = gcry_sexp_build (r_sig, NULL,
1624                               "(sig-val(eddsa(r%M)(s%M)))", sig_r, sig_s);
1625     }
1626   else
1627     {
1628       rc = sign_ecdsa (data, &sk, sig_r, sig_s, ctx.flags, ctx.hash_algo);
1629       if (!rc)
1630         rc = gcry_sexp_build (r_sig, NULL,
1631                               "(sig-val(ecdsa(r%M)(s%M)))", sig_r, sig_s);
1632     }
1633
1634
1635  leave:
1636   gcry_mpi_release (sk.E.p);
1637   gcry_mpi_release (sk.E.a);
1638   gcry_mpi_release (sk.E.b);
1639   gcry_mpi_release (mpi_g);
1640   point_free (&sk.E.G);
1641   gcry_mpi_release (sk.E.n);
1642   gcry_mpi_release (mpi_q);
1643   point_free (&sk.Q);
1644   gcry_mpi_release (sk.d);
1645   gcry_mpi_release (sig_r);
1646   gcry_mpi_release (sig_s);
1647   gcry_free (curvename);
1648   gcry_mpi_release (data);
1649   gcry_sexp_release (l1);
1650   _gcry_pk_util_free_encoding_ctx (&ctx);
1651   if (DBG_CIPHER)
1652     log_debug ("ecc_sign      => %s\n", gpg_strerror (rc));
1653   return rc;
1654 }
1655
1656
1657 static gcry_err_code_t
1658 ecc_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t s_keyparms)
1659 {
1660   gcry_err_code_t rc;
1661   struct pk_encoding_ctx ctx;
1662   gcry_sexp_t l1 = NULL;
1663   char *curvename = NULL;
1664   gcry_mpi_t mpi_g = NULL;
1665   gcry_mpi_t mpi_q = NULL;
1666   gcry_mpi_t sig_r = NULL;
1667   gcry_mpi_t sig_s = NULL;
1668   gcry_mpi_t data = NULL;
1669   ECC_public_key pk;
1670   int sigflags;
1671
1672   memset (&pk, 0, sizeof pk);
1673   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY,
1674                                    ecc_get_nbits (s_keyparms));
1675
1676   /* Extract the data.  */
1677   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1678   if (rc)
1679     goto leave;
1680   if (DBG_CIPHER)
1681     log_mpidump ("ecc_verify data", data);
1682
1683   /*
1684    * Extract the signature value.
1685    */
1686   rc = _gcry_pk_util_preparse_sigval (s_sig, ecc_names, &l1, &sigflags);
1687   if (rc)
1688     goto leave;
1689   rc = _gcry_sexp_extract_param (l1, NULL,
1690                                  (sigflags & PUBKEY_FLAG_EDDSA)? "/rs":"rs",
1691                                  &sig_r, &sig_s, NULL);
1692   if (rc)
1693     goto leave;
1694   if (DBG_CIPHER)
1695     {
1696       log_mpidump ("ecc_verify  s_r", sig_r);
1697       log_mpidump ("ecc_verify  s_s", sig_s);
1698     }
1699   if ((ctx.flags & PUBKEY_FLAG_EDDSA) ^ (sigflags & PUBKEY_FLAG_EDDSA))
1700     {
1701       rc = GPG_ERR_CONFLICT; /* Inconsistent use of flag/algoname.  */
1702       goto leave;
1703     }
1704
1705
1706   /*
1707    * Extract the key.
1708    */
1709   rc = _gcry_sexp_extract_param (s_keyparms, NULL, "-p?a?b?g?n?/q?",
1710                                  &pk.E.p, &pk.E.a, &pk.E.b, &mpi_g, &pk.E.n,
1711                                  &mpi_q, NULL);
1712   if (rc)
1713     goto leave;
1714   if (mpi_g)
1715     {
1716       point_init (&pk.E.G);
1717       rc = _gcry_ecc_os2ec (&pk.E.G, mpi_g);
1718       if (rc)
1719         goto leave;
1720     }
1721   /* Add missing parameters using the optional curve parameter.  */
1722   gcry_sexp_release (l1);
1723   l1 = gcry_sexp_find_token (s_keyparms, "curve", 5);
1724   if (l1)
1725     {
1726       curvename = gcry_sexp_nth_string (l1, 1);
1727       if (curvename)
1728         {
1729           rc = _gcry_ecc_fill_in_curve (0, curvename, &pk.E, NULL);
1730           if (rc)
1731             return rc;
1732         }
1733     }
1734   /* Guess required fields if a curve parameter has not been given.
1735      FIXME: This is a crude hacks.  We need to fix that.  */
1736   if (!curvename)
1737     {
1738       pk.E.model = ((sigflags & PUBKEY_FLAG_EDDSA)
1739                     ? MPI_EC_TWISTEDEDWARDS
1740                     : MPI_EC_WEIERSTRASS);
1741       pk.E.dialect = ((sigflags & PUBKEY_FLAG_EDDSA)
1742                       ? ECC_DIALECT_ED25519
1743                       : ECC_DIALECT_STANDARD);
1744     }
1745
1746   if (DBG_CIPHER)
1747     {
1748       log_debug ("ecc_verify info: %s/%s%s\n",
1749                  _gcry_ecc_model2str (pk.E.model),
1750                  _gcry_ecc_dialect2str (pk.E.dialect),
1751                  (pk.E.dialect == ECC_DIALECT_ED25519
1752                   && !(sigflags & PUBKEY_FLAG_EDDSA))? "/ECDSA":"");
1753       if (pk.E.name)
1754         log_debug  ("ecc_verify name: %s\n", pk.E.name);
1755       log_printmpi ("ecc_verify    p", pk.E.p);
1756       log_printmpi ("ecc_verify    a", pk.E.a);
1757       log_printmpi ("ecc_verify    b", pk.E.b);
1758       log_printpnt ("ecc_verify  g",   &pk.E.G, NULL);
1759       log_printmpi ("ecc_verify    n", pk.E.n);
1760       log_printmpi ("ecc_verify    q", mpi_q);
1761     }
1762   if (!pk.E.p || !pk.E.a || !pk.E.b || !pk.E.G.x || !pk.E.n || !mpi_q)
1763     {
1764       rc = GPG_ERR_NO_OBJ;
1765       goto leave;
1766     }
1767
1768
1769   /*
1770    * Verify the signature.
1771    */
1772   if ((sigflags & PUBKEY_FLAG_EDDSA))
1773     {
1774       rc = verify_eddsa (data, &pk, sig_r, sig_s, ctx.hash_algo, mpi_q);
1775     }
1776   else
1777     {
1778       point_init (&pk.Q);
1779       rc = _gcry_ecc_os2ec (&pk.Q, mpi_q);
1780       if (rc)
1781         goto leave;
1782
1783       if (mpi_is_opaque (data))
1784         {
1785           const void *abuf;
1786           unsigned int abits, qbits;
1787           gcry_mpi_t a;
1788
1789           qbits = mpi_get_nbits (pk.E.n);
1790
1791           abuf = gcry_mpi_get_opaque (data, &abits);
1792           rc = gpg_err_code (gcry_mpi_scan (&a, GCRYMPI_FMT_USG,
1793                                             abuf, (abits+7)/8, NULL));
1794           if (!rc)
1795             {
1796               if (abits > qbits)
1797                 gcry_mpi_rshift (a, a, abits - qbits);
1798
1799               rc = verify_ecdsa (a, &pk, sig_r, sig_s);
1800               gcry_mpi_release (a);
1801             }
1802         }
1803       else
1804         rc = verify_ecdsa (data, &pk, sig_r, sig_s);
1805     }
1806
1807  leave:
1808   gcry_mpi_release (pk.E.p);
1809   gcry_mpi_release (pk.E.a);
1810   gcry_mpi_release (pk.E.b);
1811   gcry_mpi_release (mpi_g);
1812   point_free (&pk.E.G);
1813   gcry_mpi_release (pk.E.n);
1814   gcry_mpi_release (mpi_q);
1815   point_free (&pk.Q);
1816   gcry_mpi_release (data);
1817   gcry_mpi_release (sig_r);
1818   gcry_mpi_release (sig_s);
1819   gcry_free (curvename);
1820   gcry_sexp_release (l1);
1821   _gcry_pk_util_free_encoding_ctx (&ctx);
1822   if (DBG_CIPHER)
1823     log_debug ("ecc_verify    => %s\n", rc?gpg_strerror (rc):"Good");
1824   return rc;
1825 }
1826
1827
1828 /* ecdh raw is classic 2-round DH protocol published in 1976.
1829  *
1830  * Overview of ecc_encrypt_raw and ecc_decrypt_raw.
1831  *
1832  * As with any PK operation, encrypt version uses a public key and
1833  * decrypt -- private.
1834  *
1835  * Symbols used below:
1836  *     G - field generator point
1837  *     d - private long-term scalar
1838  *    dG - public long-term key
1839  *     k - ephemeral scalar
1840  *    kG - ephemeral public key
1841  *   dkG - shared secret
1842  *
1843  * ecc_encrypt_raw description:
1844  *   input:
1845  *     data[0] : private scalar (k)
1846  *   output: A new S-expression with the parameters:
1847  *     s : shared point (kdG)
1848  *     e : generated ephemeral public key (kG)
1849  *
1850  * ecc_decrypt_raw description:
1851  *   input:
1852  *     data[0] : a point kG (ephemeral public key)
1853  *   output:
1854  *     result[0] : shared point (kdG)
1855  */
1856 static gcry_err_code_t
1857 ecc_encrypt_raw (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1858 {
1859   gcry_err_code_t rc;
1860   struct pk_encoding_ctx ctx;
1861   gcry_sexp_t l1 = NULL;
1862   char *curvename = NULL;
1863   gcry_mpi_t mpi_g = NULL;
1864   gcry_mpi_t mpi_q = NULL;
1865   gcry_mpi_t mpi_s = NULL;
1866   gcry_mpi_t mpi_e = NULL;
1867   gcry_mpi_t data = NULL;
1868   ECC_public_key pk;
1869   mpi_ec_t ec = NULL;
1870
1871   memset (&pk, 0, sizeof pk);
1872   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_ENCRYPT,
1873                                    ecc_get_nbits (keyparms));
1874
1875   /*
1876    * Extract the data.
1877    */
1878   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1879   if (rc)
1880     goto leave;
1881   if (DBG_CIPHER)
1882     log_mpidump ("ecc_encrypt data", data);
1883   if (mpi_is_opaque (data))
1884     {
1885       rc = GPG_ERR_INV_DATA;
1886       goto leave;
1887     }
1888
1889
1890   /*
1891    * Extract the key.
1892    */
1893   rc = _gcry_sexp_extract_param (keyparms, NULL, "-p?a?b?g?n?+q",
1894                                  &pk.E.p, &pk.E.a, &pk.E.b, &mpi_g, &pk.E.n,
1895                                  &mpi_q, NULL);
1896   if (rc)
1897     goto leave;
1898   if (mpi_g)
1899     {
1900       point_init (&pk.E.G);
1901       rc = _gcry_ecc_os2ec (&pk.E.G, mpi_g);
1902       if (rc)
1903         goto leave;
1904     }
1905   /* Add missing parameters using the optional curve parameter.  */
1906   gcry_sexp_release (l1);
1907   l1 = gcry_sexp_find_token (keyparms, "curve", 5);
1908   if (l1)
1909     {
1910       curvename = gcry_sexp_nth_string (l1, 1);
1911       if (curvename)
1912         {
1913           rc = _gcry_ecc_fill_in_curve (0, curvename, &pk.E, NULL);
1914           if (rc)
1915             return rc;
1916         }
1917     }
1918   /* Guess required fields if a curve parameter has not been given.  */
1919   if (!curvename)
1920     {
1921       pk.E.model = MPI_EC_WEIERSTRASS;
1922       pk.E.dialect = ECC_DIALECT_STANDARD;
1923     }
1924
1925   if (DBG_CIPHER)
1926     {
1927       log_debug ("ecc_encrypt info: %s/%s\n",
1928                  _gcry_ecc_model2str (pk.E.model),
1929                  _gcry_ecc_dialect2str (pk.E.dialect));
1930       if (pk.E.name)
1931         log_debug  ("ecc_encrypt name: %s\n", pk.E.name);
1932       log_printmpi ("ecc_encrypt    p", pk.E.p);
1933       log_printmpi ("ecc_encrypt    a", pk.E.a);
1934       log_printmpi ("ecc_encrypt    b", pk.E.b);
1935       log_printpnt ("ecc_encrypt  g",   &pk.E.G, NULL);
1936       log_printmpi ("ecc_encrypt    n", pk.E.n);
1937       log_printmpi ("ecc_encrypt    q", mpi_q);
1938     }
1939   if (!pk.E.p || !pk.E.a || !pk.E.b || !pk.E.G.x || !pk.E.n || !mpi_q)
1940     {
1941       rc = GPG_ERR_NO_OBJ;
1942       goto leave;
1943     }
1944
1945   /* Convert the public key.  */
1946   if (mpi_q)
1947     {
1948       point_init (&pk.Q);
1949       rc = _gcry_ecc_os2ec (&pk.Q, mpi_q);
1950       if (rc)
1951         goto leave;
1952     }
1953
1954   /* Compute the encrypted value.  */
1955   ec = _gcry_mpi_ec_p_internal_new (pk.E.model, pk.E.dialect,
1956                                     pk.E.p, pk.E.a, pk.E.b);
1957
1958   /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so */
1959   {
1960     mpi_point_struct R;  /* Result that we return.  */
1961     gcry_mpi_t x, y;
1962
1963     x = mpi_new (0);
1964     y = mpi_new (0);
1965
1966     point_init (&R);
1967
1968     /* R = kQ  <=>  R = kdG  */
1969     _gcry_mpi_ec_mul_point (&R, data, &pk.Q, ec);
1970
1971     if (_gcry_mpi_ec_get_affine (x, y, &R, ec))
1972       log_fatal ("ecdh: Failed to get affine coordinates for kdG\n");
1973     mpi_s = _gcry_ecc_ec2os (x, y, pk.E.p);
1974
1975     /* R = kG */
1976     _gcry_mpi_ec_mul_point (&R, data, &pk.E.G, ec);
1977
1978     if (_gcry_mpi_ec_get_affine (x, y, &R, ec))
1979       log_fatal ("ecdh: Failed to get affine coordinates for kG\n");
1980     mpi_e = _gcry_ecc_ec2os (x, y, pk.E.p);
1981
1982     mpi_free (x);
1983     mpi_free (y);
1984
1985     point_free (&R);
1986   }
1987
1988   rc = gcry_sexp_build (r_ciph, NULL, "(enc-val(ecdh(s%m)(e%m)))",
1989                         mpi_s, mpi_e);
1990
1991  leave:
1992   gcry_mpi_release (pk.E.p);
1993   gcry_mpi_release (pk.E.a);
1994   gcry_mpi_release (pk.E.b);
1995   gcry_mpi_release (mpi_g);
1996   point_free (&pk.E.G);
1997   gcry_mpi_release (pk.E.n);
1998   gcry_mpi_release (mpi_q);
1999   point_free (&pk.Q);
2000   gcry_mpi_release (data);
2001   gcry_mpi_release (mpi_s);
2002   gcry_mpi_release (mpi_e);
2003   gcry_free (curvename);
2004   _gcry_mpi_ec_free (ec);
2005   _gcry_pk_util_free_encoding_ctx (&ctx);
2006   if (DBG_CIPHER)
2007     log_debug ("ecc_encrypt    => %s\n", gpg_strerror (rc));
2008   return rc;
2009 }
2010
2011
2012 /*  input:
2013  *     data[0] : a point kG (ephemeral public key)
2014  *   output:
2015  *     resaddr[0] : shared point kdG
2016  *
2017  *  see ecc_encrypt_raw for details.
2018  */
2019 static gcry_err_code_t
2020 ecc_decrypt_raw (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms)
2021 {
2022   gpg_err_code_t rc;
2023   struct pk_encoding_ctx ctx;
2024   gcry_sexp_t l1 = NULL;
2025   gcry_mpi_t data_e = NULL;
2026   ECC_secret_key sk;
2027   gcry_mpi_t mpi_g = NULL;
2028   char *curvename = NULL;
2029   mpi_ec_t ec = NULL;
2030   mpi_point_struct kG;
2031   mpi_point_struct R;
2032   gcry_mpi_t r = NULL;
2033
2034   memset (&sk, 0, sizeof sk);
2035   point_init (&kG);
2036   point_init (&R);
2037
2038   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_DECRYPT,
2039                                    ecc_get_nbits (keyparms));
2040
2041   /*
2042    * Extract the data.
2043    */
2044   rc = _gcry_pk_util_preparse_encval (s_data, ecc_names, &l1, &ctx);
2045   if (rc)
2046     goto leave;
2047   rc = _gcry_sexp_extract_param (l1, NULL, "e", &data_e, NULL);
2048   if (rc)
2049     goto leave;
2050   if (DBG_CIPHER)
2051     log_printmpi ("ecc_decrypt  d_e", data_e);
2052   if (mpi_is_opaque (data_e))
2053     {
2054       rc = GPG_ERR_INV_DATA;
2055       goto leave;
2056     }
2057
2058   /*
2059    * Extract the key.
2060    */
2061   rc = _gcry_sexp_extract_param (keyparms, NULL, "-p?a?b?g?n?+d",
2062                                  &sk.E.p, &sk.E.a, &sk.E.b, &mpi_g, &sk.E.n,
2063                                  &sk.d, NULL);
2064   if (rc)
2065     goto leave;
2066   if (mpi_g)
2067     {
2068       point_init (&sk.E.G);
2069       rc = _gcry_ecc_os2ec (&sk.E.G, mpi_g);
2070       if (rc)
2071         goto leave;
2072     }
2073   /* Add missing parameters using the optional curve parameter.  */
2074   gcry_sexp_release (l1);
2075   l1 = gcry_sexp_find_token (keyparms, "curve", 5);
2076   if (l1)
2077     {
2078       curvename = gcry_sexp_nth_string (l1, 1);
2079       if (curvename)
2080         {
2081           rc = _gcry_ecc_fill_in_curve (0, curvename, &sk.E, NULL);
2082           if (rc)
2083             return rc;
2084         }
2085     }
2086   /* Guess required fields if a curve parameter has not been given.  */
2087   if (!curvename)
2088     {
2089       sk.E.model = MPI_EC_WEIERSTRASS;
2090       sk.E.dialect = ECC_DIALECT_STANDARD;
2091     }
2092   if (DBG_CIPHER)
2093     {
2094       log_debug ("ecc_decrypt info: %s/%s\n",
2095                  _gcry_ecc_model2str (sk.E.model),
2096                  _gcry_ecc_dialect2str (sk.E.dialect));
2097       if (sk.E.name)
2098         log_debug  ("ecc_decrypt name: %s\n", sk.E.name);
2099       log_printmpi ("ecc_decrypt    p", sk.E.p);
2100       log_printmpi ("ecc_decrypt    a", sk.E.a);
2101       log_printmpi ("ecc_decrypt    b", sk.E.b);
2102       log_printpnt ("ecc_decrypt  g",   &sk.E.G, NULL);
2103       log_printmpi ("ecc_decrypt    n", sk.E.n);
2104       if (!fips_mode ())
2105         log_printmpi ("ecc_decrypt    d", sk.d);
2106     }
2107   if (!sk.E.p || !sk.E.a || !sk.E.b || !sk.E.G.x || !sk.E.n || !sk.d)
2108     {
2109       rc = GPG_ERR_NO_OBJ;
2110       goto leave;
2111     }
2112
2113
2114   /*
2115    * Compute the plaintext.
2116    */
2117   rc = _gcry_ecc_os2ec (&kG, data_e);
2118   if (rc)
2119     {
2120       point_free (&kG);
2121       return rc;
2122     }
2123
2124   ec = _gcry_mpi_ec_p_internal_new (sk.E.model, sk.E.dialect,
2125                                     sk.E.p, sk.E.a, sk.E.b);
2126
2127   /* R = dkG */
2128   _gcry_mpi_ec_mul_point (&R, sk.d, &kG, ec);
2129
2130   /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so:  */
2131   {
2132     gcry_mpi_t x, y;
2133
2134     x = mpi_new (0);
2135     y = mpi_new (0);
2136
2137     if (_gcry_mpi_ec_get_affine (x, y, &R, ec))
2138       log_fatal ("ecdh: Failed to get affine coordinates\n");
2139
2140     r = _gcry_ecc_ec2os (x, y, sk.E.p);
2141     if (!r)
2142       rc = gpg_err_code_from_syserror ();
2143     else
2144       rc = 0;
2145     mpi_free (x);
2146     mpi_free (y);
2147   }
2148   if (DBG_CIPHER)
2149     log_printmpi ("ecc_decrypt  res", r);
2150
2151   if (!rc)
2152     rc = gcry_sexp_build (r_plain, NULL, "(value %m)", r);
2153
2154  leave:
2155   point_free (&R);
2156   point_free (&kG);
2157   gcry_mpi_release (r);
2158   gcry_mpi_release (sk.E.p);
2159   gcry_mpi_release (sk.E.a);
2160   gcry_mpi_release (sk.E.b);
2161   gcry_mpi_release (mpi_g);
2162   point_free (&sk.E.G);
2163   gcry_mpi_release (sk.E.n);
2164   gcry_mpi_release (sk.d);
2165   gcry_mpi_release (data_e);
2166   gcry_free (curvename);
2167   gcry_sexp_release (l1);
2168   _gcry_mpi_ec_free (ec);
2169   _gcry_pk_util_free_encoding_ctx (&ctx);
2170   if (DBG_CIPHER)
2171     log_debug ("ecc_decrypt    => %s\n", gpg_strerror (rc));
2172   return rc;
2173 }
2174
2175
2176 /* Return the number of bits for the key described by PARMS.  On error
2177  * 0 is returned.  The format of PARMS starts with the algorithm name;
2178  * for example:
2179  *
2180  *   (ecc
2181  *     (p <mpi>)
2182  *     (a <mpi>)
2183  *     (b <mpi>)
2184  *     (g <mpi>)
2185  *     (n <mpi>)
2186  *     (q <mpi>))
2187  *
2188  * More parameters may be given currently P is needed.  FIXME: We
2189  * need allow for a "curve" parameter.
2190  */
2191 static unsigned int
2192 ecc_get_nbits (gcry_sexp_t parms)
2193 {
2194   gcry_sexp_t l1;
2195   gcry_mpi_t p;
2196   unsigned int nbits = 0;
2197   char *curve;
2198
2199   l1 = gcry_sexp_find_token (parms, "p", 1);
2200   if (!l1)
2201     { /* Parameter P not found - check whether we have "curve".  */
2202       l1 = gcry_sexp_find_token (parms, "curve", 5);
2203       if (!l1)
2204         return 0; /* Neither P nor CURVE found.  */
2205
2206       curve = _gcry_sexp_nth_string (l1, 1);
2207       gcry_sexp_release (l1);
2208       if (!curve)
2209         return 0;  /* No curve name given (or out of core). */
2210
2211       if (_gcry_ecc_fill_in_curve (0, curve, NULL, &nbits))
2212         nbits = 0;
2213       gcry_free (curve);
2214     }
2215   else
2216     {
2217       p = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
2218       gcry_sexp_release (l1);
2219       if (p)
2220         {
2221           nbits = mpi_get_nbits (p);
2222           gcry_mpi_release (p);
2223         }
2224     }
2225   return nbits;
2226 }
2227
2228
2229 /* See rsa.c for a description of this function.  */
2230 static gpg_err_code_t
2231 compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
2232 {
2233 #define N_COMPONENTS 6
2234   static const char names[N_COMPONENTS+1] = "pabgnq";
2235   gpg_err_code_t ec = 0;
2236   gcry_sexp_t l1;
2237   gcry_mpi_t values[N_COMPONENTS];
2238   int idx;
2239
2240   /* Clear the values for easier error cleanup.  */
2241   for (idx=0; idx < N_COMPONENTS; idx++)
2242     values[idx] = NULL;
2243
2244   /* Fill values with all provided parameters.  */
2245   for (idx=0; idx < N_COMPONENTS; idx++)
2246     {
2247       l1 = gcry_sexp_find_token (keyparam, names+idx, 1);
2248       if (l1)
2249         {
2250           values[idx] = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
2251           gcry_sexp_release (l1);
2252           if (!values[idx])
2253             {
2254               ec = GPG_ERR_INV_OBJ;
2255               goto leave;
2256             }
2257         }
2258     }
2259
2260   /* Check whether a curve parameter is available and use that to fill
2261      in missing values.  */
2262   l1 = gcry_sexp_find_token (keyparam, "curve", 5);
2263   if (l1)
2264     {
2265       char *curve;
2266       gcry_mpi_t tmpvalues[N_COMPONENTS];
2267
2268       for (idx = 0; idx < N_COMPONENTS; idx++)
2269         tmpvalues[idx] = NULL;
2270
2271       curve = _gcry_sexp_nth_string (l1, 1);
2272       gcry_sexp_release (l1);
2273       if (!curve)
2274         {
2275           ec = GPG_ERR_INV_OBJ; /* Name missing or out of core. */
2276           goto leave;
2277         }
2278       ec = _gcry_ecc_get_param (curve, tmpvalues);
2279       gcry_free (curve);
2280       if (ec)
2281         goto leave;
2282
2283       for (idx = 0; idx < N_COMPONENTS; idx++)
2284         {
2285           if (!values[idx])
2286             values[idx] = tmpvalues[idx];
2287           else
2288             mpi_free (tmpvalues[idx]);
2289         }
2290     }
2291
2292   /* Check that all parameters are known and normalize all MPIs (that
2293      should not be required but we use an internal function later and
2294      thus we better make 100% sure that they are normalized). */
2295   for (idx = 0; idx < N_COMPONENTS; idx++)
2296     if (!values[idx])
2297       {
2298         ec = GPG_ERR_NO_OBJ;
2299         goto leave;
2300       }
2301     else
2302       _gcry_mpi_normalize (values[idx]);
2303
2304   /* Hash them all.  */
2305   for (idx = 0; idx < N_COMPONENTS; idx++)
2306     {
2307       char buf[30];
2308       unsigned char *rawmpi;
2309       unsigned int rawmpilen;
2310
2311       rawmpi = _gcry_mpi_get_buffer (values[idx], 0, &rawmpilen, NULL);
2312       if (!rawmpi)
2313         {
2314           ec = gpg_err_code_from_syserror ();
2315           goto leave;
2316         }
2317       snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], rawmpilen);
2318       gcry_md_write (md, buf, strlen (buf));
2319       gcry_md_write (md, rawmpi, rawmpilen);
2320       gcry_md_write (md, ")", 1);
2321       gcry_free (rawmpi);
2322     }
2323
2324  leave:
2325   for (idx = 0; idx < N_COMPONENTS; idx++)
2326     _gcry_mpi_release (values[idx]);
2327
2328   return ec;
2329 #undef N_COMPONENTS
2330 }
2331
2332
2333 \f
2334 /*
2335    Low-level API helper functions.
2336  */
2337
2338 /* This is the worker function for gcry_pubkey_get_sexp for ECC
2339    algorithms.  Note that the caller has already stored NULL at
2340    R_SEXP.  */
2341 gpg_err_code_t
2342 _gcry_pk_ecc_get_sexp (gcry_sexp_t *r_sexp, int mode, mpi_ec_t ec)
2343 {
2344   gpg_err_code_t rc;
2345   gcry_mpi_t mpi_G = NULL;
2346   gcry_mpi_t mpi_Q = NULL;
2347
2348   if (!ec->p || !ec->a || !ec->b || !ec->G || !ec->n)
2349     return GPG_ERR_BAD_CRYPT_CTX;
2350
2351   if (mode == GCRY_PK_GET_SECKEY && !ec->d)
2352     return GPG_ERR_NO_SECKEY;
2353
2354   /* Compute the public point if it is missing.  */
2355   if (!ec->Q && ec->d)
2356     ec->Q = _gcry_ecc_compute_public (NULL, ec);
2357
2358   /* Encode G and Q.  */
2359   mpi_G = _gcry_mpi_ec_ec2os (ec->G, ec);
2360   if (!mpi_G)
2361     {
2362       rc = GPG_ERR_BROKEN_PUBKEY;
2363       goto leave;
2364     }
2365   if (!ec->Q)
2366     {
2367       rc = GPG_ERR_BAD_CRYPT_CTX;
2368       goto leave;
2369     }
2370
2371   if (ec->dialect == ECC_DIALECT_ED25519)
2372     {
2373       unsigned char *encpk;
2374       unsigned int encpklen;
2375
2376       rc = _gcry_ecc_eddsa_encodepoint (ec->Q, ec, NULL, NULL,
2377                                         &encpk, &encpklen);
2378       if (rc)
2379         goto leave;
2380       mpi_Q = gcry_mpi_set_opaque (NULL, encpk, encpklen*8);
2381       encpk = NULL;
2382     }
2383   else
2384     {
2385       mpi_Q = _gcry_mpi_ec_ec2os (ec->Q, ec);
2386     }
2387   if (!mpi_Q)
2388     {
2389       rc = GPG_ERR_BROKEN_PUBKEY;
2390       goto leave;
2391     }
2392
2393   /* Fixme: We should return a curve name instead of the parameters if
2394      if know that they match a curve.  */
2395
2396   if (ec->d && (!mode || mode == GCRY_PK_GET_SECKEY))
2397     {
2398       /* Let's return a private key. */
2399       rc = gcry_sexp_build
2400         (r_sexp, NULL,
2401          "(private-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)(q%m)(d%m)))",
2402          ec->p, ec->a, ec->b, mpi_G, ec->n, mpi_Q, ec->d);
2403     }
2404   else if (ec->Q)
2405     {
2406       /* Let's return a public key.  */
2407       rc = gcry_sexp_build
2408         (r_sexp, NULL,
2409          "(public-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)(q%m)))",
2410          ec->p, ec->a, ec->b, mpi_G, ec->n, mpi_Q);
2411     }
2412   else
2413     rc = GPG_ERR_BAD_CRYPT_CTX;
2414
2415  leave:
2416   mpi_free (mpi_Q);
2417   mpi_free (mpi_G);
2418   return rc;
2419 }
2420
2421
2422 \f
2423 /*
2424      Self-test section.
2425  */
2426
2427
2428 static gpg_err_code_t
2429 selftests_ecdsa (selftest_report_func_t report)
2430 {
2431   const char *what;
2432   const char *errtxt;
2433
2434   what = "low-level";
2435   errtxt = NULL; /*selftest ();*/
2436   if (errtxt)
2437     goto failed;
2438
2439   /* FIXME:  need more tests.  */
2440
2441   return 0; /* Succeeded. */
2442
2443  failed:
2444   if (report)
2445     report ("pubkey", GCRY_PK_ECC, what, errtxt);
2446   return GPG_ERR_SELFTEST_FAILED;
2447 }
2448
2449
2450 /* Run a full self-test for ALGO and return 0 on success.  */
2451 static gpg_err_code_t
2452 run_selftests (int algo, int extended, selftest_report_func_t report)
2453 {
2454   (void)extended;
2455
2456   if (algo != GCRY_PK_ECC)
2457     return GPG_ERR_PUBKEY_ALGO;
2458
2459   return selftests_ecdsa (report);
2460 }
2461
2462
2463
2464 \f
2465 gcry_pk_spec_t _gcry_pubkey_spec_ecc =
2466   {
2467     GCRY_PK_ECC, { 0, 0 },
2468     (GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR),
2469     "ECC", ecc_names,
2470     "pabgnq", "pabgnqd", "sw", "rs", "pabgnq",
2471     ecc_generate,
2472     ecc_check_secret_key,
2473     ecc_encrypt_raw,
2474     ecc_decrypt_raw,
2475     ecc_sign,
2476     ecc_verify,
2477     ecc_get_nbits,
2478     run_selftests,
2479     compute_keygrip,
2480     _gcry_ecc_get_param,
2481     _gcry_ecc_get_curve,
2482     _gcry_ecc_get_param_sexp
2483   };