pubkey: Move sexp parsing for gcry_pk_decrypt to the modules.
[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           log_debug ("ecc verify: Not verified\n");
562         }
563       err = GPG_ERR_BAD_SIGNATURE;
564       goto leave;
565     }
566   if (DBG_CIPHER)
567     log_debug ("ecc verify: Accepted\n");
568
569  leave:
570   _gcry_mpi_ec_free (ctx);
571   point_free (&Q2);
572   point_free (&Q1);
573   point_free (&Q);
574   mpi_free (x);
575   mpi_free (h2);
576   mpi_free (h1);
577   mpi_free (h);
578   return err;
579 }
580
581
582 \f
583 static void
584 reverse_buffer (unsigned char *buffer, unsigned int length)
585 {
586   unsigned int tmp, i;
587
588   for (i=0; i < length/2; i++)
589     {
590       tmp = buffer[i];
591       buffer[i] = buffer[length-1-i];
592       buffer[length-1-i] = tmp;
593     }
594 }
595
596
597 /* Encode MPI using the EdDSA scheme.  MINLEN specifies the required
598    length of the buffer in bytes.  On success 0 is returned an a
599    malloced buffer with the encoded point is stored at R_BUFFER; the
600    length of this buffer is stored at R_BUFLEN.  */
601 static gpg_err_code_t
602 eddsa_encodempi (gcry_mpi_t mpi, unsigned int minlen,
603                  unsigned char **r_buffer, unsigned int *r_buflen)
604 {
605   unsigned char *rawmpi;
606   unsigned int rawmpilen;
607
608   rawmpi = _gcry_mpi_get_buffer (mpi, minlen, &rawmpilen, NULL);
609   if (!rawmpi)
610     return gpg_err_code_from_syserror ();
611
612   *r_buffer = rawmpi;
613   *r_buflen = rawmpilen;
614   return 0;
615 }
616
617
618 /* Encode (X,Y) using the EdDSA scheme.  MINLEN is the required length
619    in bytes for the result.  On success 0 is returned and a malloced
620    buffer with the encoded point is stored at R_BUFFER; the length of
621    this buffer is stored at R_BUFLEN.  */
622 static gpg_err_code_t
623 eddsa_encode_x_y (gcry_mpi_t x, gcry_mpi_t y, unsigned int minlen,
624                   unsigned char **r_buffer, unsigned int *r_buflen)
625 {
626   unsigned char *rawmpi;
627   unsigned int rawmpilen;
628
629   rawmpi = _gcry_mpi_get_buffer (y, minlen, &rawmpilen, NULL);
630   if (!rawmpi)
631     return gpg_err_code_from_syserror ();
632   if (mpi_test_bit (x, 0) && rawmpilen)
633     rawmpi[rawmpilen - 1] |= 0x80;  /* Set sign bit.  */
634
635   *r_buffer = rawmpi;
636   *r_buflen = rawmpilen;
637   return 0;
638 }
639
640 /* Encode POINT using the EdDSA scheme.  X and Y are either scratch
641    variables supplied by the caller or NULL.  CTX is the usual
642    context.  On success 0 is returned and a malloced buffer with the
643    encoded point is stored at R_BUFFER; the length of this buffer is
644    stored at R_BUFLEN.  */
645 gpg_err_code_t
646 _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ec,
647                              gcry_mpi_t x_in, gcry_mpi_t y_in,
648                              unsigned char **r_buffer, unsigned int *r_buflen)
649 {
650   gpg_err_code_t rc;
651   gcry_mpi_t x, y;
652
653   x = x_in? x_in : mpi_new (0);
654   y = y_in? y_in : mpi_new (0);
655
656   if (_gcry_mpi_ec_get_affine (x, y, point, ec))
657     {
658       log_error ("eddsa_encodepoint: Failed to get affine coordinates\n");
659       rc = GPG_ERR_INTERNAL;
660     }
661   else
662     rc = eddsa_encode_x_y (x, y, ec->nbits/8, r_buffer, r_buflen);
663
664   if (!x_in)
665     mpi_free (x);
666   if (!y_in)
667     mpi_free (y);
668   return rc;
669 }
670
671
672 /* Decode the EdDSA style encoded PK and set it into RESULT.  CTX is
673    the usual curve context.  If R_ENCPK is not NULL, the encoded PK is
674    stored at that address; this is a new copy to be released by the
675    caller.  In contrast to the supplied PK, this is not an MPI and
676    thus guarnateed to be properly padded.  R_ENCPKLEN received the
677    length of that encoded key.  */
678 gpg_err_code_t
679 _gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result,
680                              unsigned char **r_encpk, unsigned int *r_encpklen)
681 {
682   gpg_err_code_t rc;
683   unsigned char *rawmpi;
684   unsigned int rawmpilen;
685   gcry_mpi_t yy, t, x, p1, p2, p3;
686   int sign;
687
688   if (mpi_is_opaque (pk))
689     {
690       const unsigned char *buf;
691
692       buf = gcry_mpi_get_opaque (pk, &rawmpilen);
693       if (!buf)
694         return GPG_ERR_INV_OBJ;
695       rawmpilen = (rawmpilen + 7)/8;
696
697       /* First check whether the public key has been given in standard
698          uncompressed format.  No need to recover x in this case.
699          Detection is easy: The size of the buffer will be odd and the
700          first byte be 0x04.  */
701       if (rawmpilen > 1 && buf[0] == 0x04 && (rawmpilen%2))
702         {
703           gcry_mpi_t y;
704
705           rc = gcry_mpi_scan (&x, GCRYMPI_FMT_STD,
706                               buf+1, (rawmpilen-1)/2, NULL);
707           if (rc)
708             return rc;
709           rc = gcry_mpi_scan (&y, GCRYMPI_FMT_STD,
710                               buf+1+(rawmpilen-1)/2, (rawmpilen-1)/2, NULL);
711           if (rc)
712             {
713               mpi_free (x);
714               return rc;
715             }
716
717           if (r_encpk)
718             {
719               rc = eddsa_encode_x_y (x, y, ctx->nbits/8, r_encpk, r_encpklen);
720               if (rc)
721                 {
722                   mpi_free (x);
723                   mpi_free (y);
724                   return rc;
725                 }
726             }
727           mpi_snatch (result->x, x);
728           mpi_snatch (result->y, y);
729           mpi_set_ui (result->z, 1);
730           return 0;
731         }
732
733       /* EdDSA compressed point.  */
734       rawmpi = gcry_malloc (rawmpilen? rawmpilen:1);
735       if (!rawmpi)
736         return gpg_err_code_from_syserror ();
737       memcpy (rawmpi, buf, rawmpilen);
738       reverse_buffer (rawmpi, rawmpilen);
739     }
740   else
741     {
742       /* Note: Without using an opaque MPI it is not reliable possible
743          to find out whether the public key has been given in
744          uncompressed format.  Thus we expect EdDSA format here.  */
745       rawmpi = _gcry_mpi_get_buffer (pk, ctx->nbits/8, &rawmpilen, NULL);
746       if (!rawmpi)
747         return gpg_err_code_from_syserror ();
748     }
749
750   if (rawmpilen)
751     {
752       sign = !!(rawmpi[0] & 0x80);
753       rawmpi[0] &= 0x7f;
754     }
755   else
756     sign = 0;
757   _gcry_mpi_set_buffer (result->y, rawmpi, rawmpilen, 0);
758   if (r_encpk)
759     {
760       /* Revert to little endian.  */
761       if (sign && rawmpilen)
762         rawmpi[0] |= 0x80;
763       reverse_buffer (rawmpi, rawmpilen);
764       *r_encpk = rawmpi;
765       if (r_encpklen)
766         *r_encpklen = rawmpilen;
767     }
768   else
769     gcry_free (rawmpi);
770
771   /* Now recover X.  */
772   /* t = (y^2-1) · ((b*y^2+1)^{p-2} mod p) */
773   x = mpi_new (0);
774   yy = mpi_new (0);
775   mpi_mul (yy, result->y, result->y);
776   t = mpi_copy (yy);
777   mpi_mul (t, t, ctx->b);
778   mpi_add_ui (t, t, 1);
779   p2 = mpi_copy (ctx->p);
780   mpi_sub_ui (p2, p2, 2);
781   mpi_powm (t, t, p2, ctx->p);
782
783   mpi_sub_ui (yy, yy, 1);
784   mpi_mul (t, yy, t);
785
786   /* x = t^{(p+3)/8} mod p */
787   p3 = mpi_copy (ctx->p);
788   mpi_add_ui (p3, p3, 3);
789   mpi_fdiv_q (p3, p3, mpi_const (MPI_C_EIGHT));
790   mpi_powm (x, t, p3, ctx->p);
791
792   /* (x^2 - t) % p != 0 ? x = (x*(2^{(p-1)/4} mod p)) % p */
793   mpi_mul (yy, x, x);
794   mpi_subm (yy, yy, t, ctx->p);
795   if (mpi_cmp_ui (yy, 0))
796     {
797       p1 = mpi_copy (ctx->p);
798       mpi_sub_ui (p1, p1, 1);
799       mpi_fdiv_q (p1, p1, mpi_const (MPI_C_FOUR));
800       mpi_powm (yy, mpi_const (MPI_C_TWO), p1, ctx->p);
801       mpi_mulm (x, x, yy, ctx->p);
802     }
803   else
804     p1 = NULL;
805
806   /* is_odd(x) ? x = p-x */
807   if (mpi_test_bit (x, 0))
808     mpi_sub (x, ctx->p, x);
809
810   /* lowbit(x) != highbit(input) ?  x = p-x */
811   if (mpi_test_bit (x, 0) != sign)
812     mpi_sub (x, ctx->p, x);
813
814   mpi_set (result->x, x);
815   mpi_set_ui (result->z, 1);
816
817   gcry_mpi_release (x);
818   gcry_mpi_release (yy);
819   gcry_mpi_release (t);
820   gcry_mpi_release (p3);
821   gcry_mpi_release (p2);
822   gcry_mpi_release (p1);
823
824   return 0;
825 }
826
827
828 /* Ed25519 version of the key generation.  */
829 static gpg_err_code_t
830 eddsa_generate_key (ECC_secret_key *sk, elliptic_curve_t *E, mpi_ec_t ctx,
831                     gcry_random_level_t random_level)
832 {
833   gpg_err_code_t rc;
834   int b = 256/8;             /* The only size we currently support.  */
835   gcry_mpi_t a, x, y;
836   mpi_point_struct Q;
837   char *dbuf;
838   size_t dlen;
839   gcry_buffer_t hvec[1];
840   unsigned char *hash_d = NULL;
841
842   point_init (&Q);
843   memset (hvec, 0, sizeof hvec);
844
845   a = mpi_snew (0);
846   x = mpi_new (0);
847   y = mpi_new (0);
848
849   /* Generate a secret.  */
850   hash_d = gcry_malloc_secure (2*b);
851   if (!hash_d)
852     {
853       rc = gpg_error_from_syserror ();
854       goto leave;
855     }
856   dlen = b;
857   dbuf = gcry_random_bytes_secure (dlen, random_level);
858
859   /* Compute the A value.  */
860   hvec[0].data = dbuf;
861   hvec[0].len = dlen;
862   rc = _gcry_md_hash_buffers (GCRY_MD_SHA512, 0, hash_d, hvec, 1);
863   if (rc)
864     goto leave;
865   sk->d = _gcry_mpi_set_opaque (NULL, dbuf, dlen*8);
866   dbuf = NULL;
867   reverse_buffer (hash_d, 32);  /* Only the first half of the hash.  */
868   hash_d[0] = (hash_d[0] & 0x7f) | 0x40;
869   hash_d[31] &= 0xf8;
870   _gcry_mpi_set_buffer (a, hash_d, 32, 0);
871   gcry_free (hash_d); hash_d = NULL;
872   /* log_printmpi ("ecgen         a", a); */
873
874   /* Compute Q.  */
875   _gcry_mpi_ec_mul_point (&Q, a, &E->G, ctx);
876   if (DBG_CIPHER)
877     log_printpnt ("ecgen      pk", &Q, ctx);
878
879   /* Copy the stuff to the key structures. */
880   sk->E.model = E->model;
881   sk->E.dialect = E->dialect;
882   sk->E.p = mpi_copy (E->p);
883   sk->E.a = mpi_copy (E->a);
884   sk->E.b = mpi_copy (E->b);
885   point_init (&sk->E.G);
886   point_set (&sk->E.G, &E->G);
887   sk->E.n = mpi_copy (E->n);
888   point_init (&sk->Q);
889   point_set (&sk->Q, &Q);
890
891  leave:
892   gcry_mpi_release (a);
893   gcry_mpi_release (x);
894   gcry_mpi_release (y);
895   gcry_free (hash_d);
896   return rc;
897 }
898
899
900 /* Compute an EdDSA signature. See:
901  *   [ed25519] 23pp. (PDF) Daniel J. Bernstein, Niels Duif, Tanja
902  *   Lange, Peter Schwabe, Bo-Yin Yang. High-speed high-security
903  *   signatures.  Journal of Cryptographic Engineering 2 (2012), 77-89.
904  *   Document ID: a1a62a2f76d23f65d622484ddd09caf8.
905  *   URL: http://cr.yp.to/papers.html#ed25519. Date: 2011.09.26.
906  *
907  * Despite that this function requires the specification of a hash
908  * algorithm, we only support what has been specified by the paper.
909  * This may change in the future.  Note that we don't check the used
910  * curve; the user is responsible to use Ed25519.
911  *
912  * Return the signature struct (r,s) from the message hash.  The caller
913  * must have allocated R_R and S.
914  */
915 static gpg_err_code_t
916 sign_eddsa (gcry_mpi_t input, ECC_secret_key *skey,
917             gcry_mpi_t r_r, gcry_mpi_t s, int hashalgo, gcry_mpi_t pk)
918 {
919   int rc;
920   mpi_ec_t ctx = NULL;
921   int b;
922   unsigned int tmp;
923   unsigned char *digest;
924   gcry_buffer_t hvec[3];
925   const void *mbuf;
926   size_t mlen;
927   unsigned char *rawmpi = NULL;
928   unsigned int rawmpilen;
929   unsigned char *encpk = NULL; /* Encoded public key.  */
930   unsigned int encpklen;
931   mpi_point_struct I;          /* Intermediate value.  */
932   mpi_point_struct Q;          /* Public key.  */
933   gcry_mpi_t a, x, y, r;
934
935   memset (hvec, 0, sizeof hvec);
936
937   if (!mpi_is_opaque (input))
938     return GPG_ERR_INV_DATA;
939   if (hashalgo != GCRY_MD_SHA512)
940     return GPG_ERR_DIGEST_ALGO;
941
942   /* Initialize some helpers.  */
943   point_init (&I);
944   point_init (&Q);
945   a = mpi_snew (0);
946   x = mpi_new (0);
947   y = mpi_new (0);
948   r = mpi_new (0);
949   ctx = _gcry_mpi_ec_p_internal_new (skey->E.model, skey->E.dialect,
950                                      skey->E.p, skey->E.a, skey->E.b);
951   b = (ctx->nbits+7)/8;
952   if (b != 256/8)
953     return GPG_ERR_INTERNAL; /* We only support 256 bit. */
954
955   digest = gcry_calloc_secure (2, b);
956   if (!digest)
957     {
958       rc = gpg_err_code_from_syserror ();
959       goto leave;
960     }
961
962   /* Hash the secret key.  We clear DIGEST so we can use it as input
963      to left pad the key with zeroes for hashing.  */
964   rawmpi = _gcry_mpi_get_buffer (skey->d, 0, &rawmpilen, NULL);
965   if (!rawmpi)
966     {
967       rc = gpg_err_code_from_syserror ();
968       goto leave;
969     }
970   hvec[0].data = digest;
971   hvec[0].off = 0;
972   hvec[0].len = b > rawmpilen? b - rawmpilen : 0;
973   hvec[1].data = rawmpi;
974   hvec[1].off = 0;
975   hvec[1].len = rawmpilen;
976   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2);
977   gcry_free (rawmpi); rawmpi = NULL;
978   if (rc)
979     goto leave;
980
981   /* Compute the A value (this modifies DIGEST).  */
982   reverse_buffer (digest, 32);  /* Only the first half of the hash.  */
983   digest[0] = (digest[0] & 0x7f) | 0x40;
984   digest[31] &= 0xf8;
985   _gcry_mpi_set_buffer (a, digest, 32, 0);
986
987   /* Compute the public key if it has not been supplied as optional
988      parameter.  */
989   if (pk)
990     {
991       rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q,  &encpk, &encpklen);
992       if (rc)
993         goto leave;
994       if (DBG_CIPHER)
995         log_printhex ("* e_pk", encpk, encpklen);
996       if (!_gcry_mpi_ec_curve_point (&Q, ctx))
997         {
998           rc = GPG_ERR_BROKEN_PUBKEY;
999           goto leave;
1000         }
1001     }
1002   else
1003     {
1004       _gcry_mpi_ec_mul_point (&Q, a, &skey->E.G, ctx);
1005       rc = _gcry_ecc_eddsa_encodepoint (&Q, ctx, x, y, &encpk, &encpklen);
1006       if (rc)
1007         goto leave;
1008       if (DBG_CIPHER)
1009         log_printhex ("  e_pk", encpk, encpklen);
1010     }
1011
1012   /* Compute R.  */
1013   mbuf = gcry_mpi_get_opaque (input, &tmp);
1014   mlen = (tmp +7)/8;
1015   if (DBG_CIPHER)
1016     log_printhex ("     m", mbuf, mlen);
1017
1018   hvec[0].data = digest;
1019   hvec[0].off  = 32;
1020   hvec[0].len  = 32;
1021   hvec[1].data = (char*)mbuf;
1022   hvec[1].len  = mlen;
1023   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2);
1024   if (rc)
1025     goto leave;
1026   reverse_buffer (digest, 64);
1027   if (DBG_CIPHER)
1028     log_printhex ("     r", digest, 64);
1029   _gcry_mpi_set_buffer (r, digest, 64, 0);
1030   _gcry_mpi_ec_mul_point (&I, r, &skey->E.G, ctx);
1031   if (DBG_CIPHER)
1032     log_printpnt ("   r", &I, ctx);
1033
1034   /* Convert R into affine coordinates and apply encoding.  */
1035   rc = _gcry_ecc_eddsa_encodepoint (&I, ctx, x, y, &rawmpi, &rawmpilen);
1036   if (rc)
1037     goto leave;
1038   if (DBG_CIPHER)
1039     log_printhex ("   e_r", rawmpi, rawmpilen);
1040
1041   /* S = r + a * H(encodepoint(R) + encodepoint(pk) + m) mod n  */
1042   hvec[0].data = rawmpi;  /* (this is R) */
1043   hvec[0].off  = 0;
1044   hvec[0].len  = rawmpilen;
1045   hvec[1].data = encpk;
1046   hvec[1].off  = 0;
1047   hvec[1].len  = encpklen;
1048   hvec[2].data = (char*)mbuf;
1049   hvec[2].off  = 0;
1050   hvec[2].len  = mlen;
1051   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
1052   if (rc)
1053     goto leave;
1054
1055   /* No more need for RAWMPI thus we now transfer it to R_R.  */
1056   gcry_mpi_set_opaque (r_r, rawmpi, rawmpilen*8);
1057   rawmpi = NULL;
1058
1059   reverse_buffer (digest, 64);
1060   if (DBG_CIPHER)
1061     log_printhex (" H(R+)", digest, 64);
1062   _gcry_mpi_set_buffer (s, digest, 64, 0);
1063   mpi_mulm (s, s, a, skey->E.n);
1064   mpi_addm (s, s, r, skey->E.n);
1065   rc = eddsa_encodempi (s, b, &rawmpi, &rawmpilen);
1066   if (rc)
1067     goto leave;
1068   if (DBG_CIPHER)
1069     log_printhex ("   e_s", rawmpi, rawmpilen);
1070   gcry_mpi_set_opaque (s, rawmpi, rawmpilen*8);
1071   rawmpi = NULL;
1072
1073   rc = 0;
1074
1075  leave:
1076   gcry_mpi_release (a);
1077   gcry_mpi_release (x);
1078   gcry_mpi_release (y);
1079   gcry_mpi_release (r);
1080   gcry_free (digest);
1081   _gcry_mpi_ec_free (ctx);
1082   point_free (&I);
1083   point_free (&Q);
1084   gcry_free (encpk);
1085   gcry_free (rawmpi);
1086   return rc;
1087 }
1088
1089
1090 /* Verify an EdDSA signature.  See sign_eddsa for the reference.
1091  * Check if R_IN and S_IN verifies INPUT.  PKEY has the curve
1092  * parameters and PK is the EdDSA style encoded public key.
1093  */
1094 static gpg_err_code_t
1095 verify_eddsa (gcry_mpi_t input, ECC_public_key *pkey,
1096               gcry_mpi_t r_in, gcry_mpi_t s_in, int hashalgo, gcry_mpi_t pk)
1097 {
1098   int rc;
1099   mpi_ec_t ctx = NULL;
1100   int b;
1101   unsigned int tmp;
1102   mpi_point_struct Q;          /* Public key.  */
1103   unsigned char *encpk = NULL; /* Encoded public key.  */
1104   unsigned int encpklen;
1105   const void *mbuf, *rbuf;
1106   unsigned char *tbuf = NULL;
1107   size_t mlen, rlen;
1108   unsigned int tlen;
1109   unsigned char digest[64];
1110   gcry_buffer_t hvec[3];
1111   gcry_mpi_t h, s;
1112   mpi_point_struct Ia, Ib;
1113
1114   if (!mpi_is_opaque (input) || !mpi_is_opaque (r_in) || !mpi_is_opaque (s_in))
1115     return GPG_ERR_INV_DATA;
1116   if (hashalgo != GCRY_MD_SHA512)
1117     return GPG_ERR_DIGEST_ALGO;
1118
1119   point_init (&Q);
1120   point_init (&Ia);
1121   point_init (&Ib);
1122   h = mpi_new (0);
1123   s = mpi_new (0);
1124
1125   ctx = _gcry_mpi_ec_p_internal_new (pkey->E.model, pkey->E.dialect,
1126                                      pkey->E.p, pkey->E.a, pkey->E.b);
1127   b = ctx->nbits/8;
1128   if (b != 256/8)
1129     return GPG_ERR_INTERNAL; /* We only support 256 bit. */
1130
1131   /* Decode and check the public key.  */
1132   rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q, &encpk, &encpklen);
1133   if (rc)
1134     goto leave;
1135   if (!_gcry_mpi_ec_curve_point (&Q, ctx))
1136     {
1137       rc = GPG_ERR_BROKEN_PUBKEY;
1138       goto leave;
1139     }
1140   if (DBG_CIPHER)
1141     log_printhex ("  e_pk", encpk, encpklen);
1142   if (encpklen != b)
1143     {
1144       rc = GPG_ERR_INV_LENGTH;
1145       goto leave;
1146     }
1147
1148   /* Convert the other input parameters.  */
1149   mbuf = gcry_mpi_get_opaque (input, &tmp);
1150   mlen = (tmp +7)/8;
1151   if (DBG_CIPHER)
1152     log_printhex ("     m", mbuf, mlen);
1153   rbuf = gcry_mpi_get_opaque (r_in, &tmp);
1154   rlen = (tmp +7)/8;
1155   if (DBG_CIPHER)
1156     log_printhex ("     r", rbuf, rlen);
1157   if (rlen != b)
1158     {
1159       rc = GPG_ERR_INV_LENGTH;
1160       goto leave;
1161     }
1162
1163   /* h = H(encodepoint(R) + encodepoint(pk) + m)  */
1164   hvec[0].data = (char*)rbuf;
1165   hvec[0].off  = 0;
1166   hvec[0].len  = rlen;
1167   hvec[1].data = encpk;
1168   hvec[1].off  = 0;
1169   hvec[1].len  = encpklen;
1170   hvec[2].data = (char*)mbuf;
1171   hvec[2].off  = 0;
1172   hvec[2].len  = mlen;
1173   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
1174   if (rc)
1175     goto leave;
1176   reverse_buffer (digest, 64);
1177   if (DBG_CIPHER)
1178     log_printhex (" H(R+)", digest, 64);
1179   _gcry_mpi_set_buffer (h, digest, 64, 0);
1180
1181   /* According to the paper the best way for verification is:
1182          encodepoint(sG - h·Q) = encodepoint(r)
1183      because we don't need to decode R. */
1184   {
1185     void *sbuf;
1186     unsigned int slen;
1187
1188     sbuf = _gcry_mpi_get_opaque_copy (s_in, &tmp);
1189     slen = (tmp +7)/8;
1190     reverse_buffer (sbuf, slen);
1191     if (DBG_CIPHER)
1192       log_printhex ("     s", sbuf, slen);
1193     _gcry_mpi_set_buffer (s, sbuf, slen, 0);
1194     gcry_free (sbuf);
1195     if (slen != b)
1196       {
1197         rc = GPG_ERR_INV_LENGTH;
1198         goto leave;
1199       }
1200   }
1201
1202   _gcry_mpi_ec_mul_point (&Ia, s, &pkey->E.G, ctx);
1203   _gcry_mpi_ec_mul_point (&Ib, h, &Q, ctx);
1204   _gcry_mpi_neg (Ib.x, Ib.x);
1205   _gcry_mpi_ec_add_points (&Ia, &Ia, &Ib, ctx);
1206   rc = _gcry_ecc_eddsa_encodepoint (&Ia, ctx, s, h, &tbuf, &tlen);
1207   if (rc)
1208     goto leave;
1209   if (tlen != rlen || memcmp (tbuf, rbuf, tlen))
1210     {
1211       if (DBG_CIPHER)
1212         log_debug ("eddsa verify: Not verified\n");
1213       rc = GPG_ERR_BAD_SIGNATURE;
1214       goto leave;
1215     }
1216
1217   if (DBG_CIPHER)
1218     log_debug ("eddsa verify: Accepted\n");
1219   rc = 0;
1220
1221  leave:
1222   gcry_free (encpk);
1223   gcry_free (tbuf);
1224   _gcry_mpi_ec_free (ctx);
1225   gcry_mpi_release (s);
1226   gcry_mpi_release (h);
1227   point_free (&Ia);
1228   point_free (&Ib);
1229   point_free (&Q);
1230   return rc;
1231 }
1232
1233
1234 \f
1235 /*********************************************
1236  **************  interface  ******************
1237  *********************************************/
1238
1239 static gcry_err_code_t
1240 ecc_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
1241 {
1242   gpg_err_code_t rc;
1243   unsigned int nbits;
1244   elliptic_curve_t E;
1245   ECC_secret_key sk;
1246   gcry_mpi_t x = NULL;
1247   gcry_mpi_t y = NULL;
1248   char *curve_name = NULL;
1249   gcry_sexp_t l1;
1250   int transient_key = 0;
1251   gcry_random_level_t random_level;
1252   mpi_ec_t ctx = NULL;
1253   gcry_sexp_t curve_info = NULL;
1254   gcry_mpi_t base = NULL;
1255   gcry_mpi_t public = NULL;
1256   gcry_mpi_t secret = NULL;
1257
1258   memset (&E, 0, sizeof E);
1259   memset (&sk, 0, sizeof sk);
1260
1261   rc = _gcry_pk_util_get_nbits (genparms, &nbits);
1262   if (rc)
1263     return rc;
1264
1265   /* Parse the optional "curve" parameter. */
1266   l1 = gcry_sexp_find_token (genparms, "curve", 0);
1267   if (l1)
1268     {
1269       curve_name = _gcry_sexp_nth_string (l1, 1);
1270       gcry_sexp_release (l1);
1271       if (!curve_name)
1272         return GPG_ERR_INV_OBJ; /* No curve name or value too large. */
1273     }
1274
1275   /* Parse the optional transient-key flag.  */
1276   l1 = gcry_sexp_find_token (genparms, "transient-key", 0);
1277   if (l1)
1278     {
1279       transient_key = 1;
1280       gcry_sexp_release (l1);
1281     }
1282
1283   /* NBITS is required if no curve name has been given.  */
1284   if (!nbits && !curve_name)
1285     return GPG_ERR_NO_OBJ; /* No NBITS parameter. */
1286
1287   rc = _gcry_ecc_fill_in_curve (nbits, curve_name, &E, &nbits);
1288   gcry_free (curve_name); curve_name = NULL;
1289   if (rc)
1290     goto leave;
1291
1292   if (DBG_CIPHER)
1293     {
1294       log_debug ("ecgen curve info: %s/%s\n",
1295                  _gcry_ecc_model2str (E.model),
1296                  _gcry_ecc_dialect2str (E.dialect));
1297       if (E.name)
1298         log_debug ("ecgen curve used: %s\n", E.name);
1299       log_printmpi ("ecgen curve   p", E.p);
1300       log_printmpi ("ecgen curve   a", E.a);
1301       log_printmpi ("ecgen curve   b", E.b);
1302       log_printmpi ("ecgen curve   n", E.n);
1303       log_printpnt ("ecgen curve G", &E.G, NULL);
1304     }
1305
1306   random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
1307   ctx = _gcry_mpi_ec_p_internal_new (E.model, E.dialect, E.p, E.a, E.b);
1308   x = mpi_new (0);
1309   y = mpi_new (0);
1310
1311   switch (E.dialect)
1312     {
1313     case ECC_DIALECT_STANDARD:
1314       rc = nist_generate_key (&sk, &E, ctx, random_level, nbits);
1315       break;
1316     case ECC_DIALECT_ED25519:
1317       rc = eddsa_generate_key (&sk, &E, ctx, random_level);
1318       break;
1319     default:
1320       rc = GPG_ERR_INTERNAL;
1321       break;
1322     }
1323   if (rc)
1324     goto leave;
1325
1326   /* Copy data to the result.  */
1327   if (_gcry_mpi_ec_get_affine (x, y, &sk.E.G, ctx))
1328     log_fatal ("ecgen: Failed to get affine coordinates for %s\n", "G");
1329   base = _gcry_ecc_ec2os (x, y, sk.E.p);
1330   if (sk.E.dialect == ECC_DIALECT_ED25519)
1331     {
1332       unsigned char *encpk;
1333       unsigned int encpklen;
1334
1335       rc = _gcry_ecc_eddsa_encodepoint (&sk.Q, ctx, x, y, &encpk, &encpklen);
1336       if (rc)
1337         return rc;
1338       public = mpi_new (0);
1339       gcry_mpi_set_opaque (public, encpk, encpklen*8);
1340       encpk = NULL;
1341     }
1342   else
1343     {
1344       if (_gcry_mpi_ec_get_affine (x, y, &sk.Q, ctx))
1345         log_fatal ("ecgen: Failed to get affine coordinates for %s\n", "Q");
1346       public = _gcry_ecc_ec2os (x, y, sk.E.p);
1347     }
1348   secret = sk.d; sk.d = NULL;
1349   if (E.name)
1350     {
1351       rc = gcry_sexp_build (&curve_info, NULL, "(curve %s)", E.name);
1352       if (rc)
1353         goto leave;
1354     }
1355
1356   rc = gcry_sexp_build (r_skey, NULL,
1357                         "(key-data"
1358                         " (public-key"
1359                         "  (ecc%S(p%m)(a%m)(b%m)(g%m)(n%m)(q%m)))"
1360                         " (private-key"
1361                         "  (ecc%S(p%m)(a%m)(b%m)(g%m)(n%m)(q%m)(d%m)))"
1362                         " )",
1363                         curve_info,
1364                         sk.E.p, sk.E.a, sk.E.b, base, sk.E.n, public,
1365                         curve_info,
1366                         sk.E.p, sk.E.a, sk.E.b, base, sk.E.n, public, secret);
1367   if (rc)
1368     goto leave;
1369
1370   if (DBG_CIPHER)
1371     {
1372       log_printmpi ("ecgen result  p", sk.E.p);
1373       log_printmpi ("ecgen result  a", sk.E.a);
1374       log_printmpi ("ecgen result  b", sk.E.b);
1375       log_printmpi ("ecgen result  G", base);
1376       log_printmpi ("ecgen result  n", sk.E.n);
1377       log_printmpi ("ecgen result  Q", public);
1378       log_printmpi ("ecgen result  d", secret);
1379     }
1380
1381  leave:
1382   mpi_free (secret);
1383   mpi_free (public);
1384   mpi_free (base);
1385   {
1386     _gcry_ecc_curve_free (&sk.E);
1387     point_free (&sk.Q);
1388     mpi_free (sk.d);
1389   }
1390   _gcry_ecc_curve_free (&E);
1391   mpi_free (x);
1392   mpi_free (y);
1393   _gcry_mpi_ec_free (ctx);
1394   gcry_sexp_release (curve_info);
1395   return rc;
1396 }
1397
1398
1399 static gcry_err_code_t
1400 ecc_check_secret_key (int algo, gcry_mpi_t *skey)
1401 {
1402   gpg_err_code_t err;
1403   ECC_secret_key sk;
1404
1405   (void)algo;
1406
1407   /* FIXME:  This check looks a bit fishy:  Now long is the array?  */
1408   if (!skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] || !skey[5]
1409       || !skey[6])
1410     return GPG_ERR_BAD_MPI;
1411
1412   sk.E.model = MPI_EC_WEIERSTRASS;
1413   sk.E.p = skey[0];
1414   sk.E.a = skey[1];
1415   sk.E.b = skey[2];
1416   point_init (&sk.E.G);
1417   err = _gcry_ecc_os2ec (&sk.E.G, skey[3]);
1418   if (err)
1419     {
1420       point_free (&sk.E.G);
1421       return err;
1422     }
1423   sk.E.n = skey[4];
1424   point_init (&sk.Q);
1425   err = _gcry_ecc_os2ec (&sk.Q, skey[5]);
1426   if (err)
1427     {
1428       point_free (&sk.E.G);
1429       point_free (&sk.Q);
1430       return err;
1431     }
1432
1433   {
1434     const unsigned char *buf;
1435     unsigned int n;
1436
1437     gcry_assert (mpi_is_opaque (skey[6]));
1438
1439     buf = gcry_mpi_get_opaque (skey[6], &n);
1440     if (!buf)
1441       err = GPG_ERR_INV_OBJ;
1442     else
1443       {
1444         n = (n + 7)/8;
1445         sk.d = NULL;
1446         err = gcry_mpi_scan (&sk.d, GCRYMPI_FMT_USG, buf, n, NULL);
1447         if (!err)
1448           {
1449             if (check_secret_key (&sk))
1450               err = GPG_ERR_BAD_SECKEY;
1451             gcry_mpi_release (sk.d);
1452             sk.d = NULL;
1453           }
1454       }
1455   }
1456
1457   point_free (&sk.E.G);
1458   point_free (&sk.Q);
1459   return err;
1460 }
1461
1462
1463 static gcry_err_code_t
1464 ecc_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1465 {
1466   gcry_err_code_t rc;
1467   struct pk_encoding_ctx ctx;
1468   gcry_mpi_t data = NULL;
1469   gcry_sexp_t l1 = NULL;
1470   char *curvename = NULL;
1471   gcry_mpi_t mpi_g = NULL;
1472   gcry_mpi_t mpi_q = NULL;
1473   ECC_secret_key sk;
1474   gcry_mpi_t sig_r = NULL;
1475   gcry_mpi_t sig_s = NULL;
1476
1477   memset (&sk, 0, sizeof sk);
1478
1479   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_SIGN, 0);
1480
1481   /* Extract the data.  */
1482   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1483   if (rc)
1484     goto leave;
1485   if (DBG_CIPHER)
1486     log_mpidump ("ecc_sign   data", data);
1487
1488   /*
1489    * Extract the key.
1490    */
1491   rc = _gcry_pk_util_extract_mpis (keyparms, "-p?a?b?g?n?/q?+d",
1492                                    &sk.E.p, &sk.E.a, &sk.E.b, &mpi_g, &sk.E.n,
1493                                    &mpi_q, &sk.d, NULL);
1494   if (rc)
1495     goto leave;
1496   if (mpi_g)
1497     {
1498       point_init (&sk.E.G);
1499       rc = _gcry_ecc_os2ec (&sk.E.G, mpi_g);
1500       if (rc)
1501         goto leave;
1502     }
1503   /* Add missing parameters using the optional curve parameter.  */
1504   gcry_sexp_release (l1);
1505   l1 = gcry_sexp_find_token (keyparms, "curve", 5);
1506   if (l1)
1507     {
1508       curvename = gcry_sexp_nth_string (l1, 1);
1509       if (curvename)
1510         {
1511           rc = _gcry_ecc_fill_in_curve (0, curvename, &sk.E, NULL);
1512           if (rc)
1513             return rc;
1514         }
1515     }
1516   /* Guess required fields if a curve parameter has not been given.
1517      FIXME: This is a crude hacks.  We need to fix that.  */
1518   if (!curvename)
1519     {
1520       sk.E.model = ((ctx.flags & PUBKEY_FLAG_EDDSA)
1521                     ? MPI_EC_TWISTEDEDWARDS
1522                     : MPI_EC_WEIERSTRASS);
1523       sk.E.dialect = ((ctx.flags & PUBKEY_FLAG_EDDSA)
1524                       ? ECC_DIALECT_ED25519
1525                       : ECC_DIALECT_STANDARD);
1526     }
1527   if (DBG_CIPHER)
1528     {
1529       log_debug ("ecc_sign   info: %s/%s\n",
1530                  _gcry_ecc_model2str (sk.E.model),
1531                  _gcry_ecc_dialect2str (sk.E.dialect));
1532       if (sk.E.name)
1533         log_debug  ("ecc_sign   name: %s\n", sk.E.name);
1534       log_printmpi ("ecc_sign      p", sk.E.p);
1535       log_printmpi ("ecc_sign      a", sk.E.a);
1536       log_printmpi ("ecc_sign      b", sk.E.b);
1537       log_printpnt ("ecc_sign    g",   &sk.E.G, NULL);
1538       log_printmpi ("ecc_sign      n", sk.E.n);
1539       log_printmpi ("ecc_sign      q", mpi_q);
1540       if (!fips_mode ())
1541         log_printmpi ("ecc_sign      d", sk.d);
1542     }
1543   if (!sk.E.p || !sk.E.a || !sk.E.b || !sk.E.G.x || !sk.E.n || !sk.d)
1544     {
1545       rc = GPG_ERR_NO_OBJ;
1546       goto leave;
1547     }
1548
1549
1550   sig_r = gcry_mpi_new (0);
1551   sig_s = gcry_mpi_new (0);
1552   if ((ctx.flags & PUBKEY_FLAG_EDDSA))
1553     {
1554       /* EdDSA requires the public key.  */
1555       rc = sign_eddsa (data, &sk, sig_r, sig_s, ctx.hash_algo, mpi_q);
1556       if (!rc)
1557         rc = gcry_sexp_build (r_sig, NULL,
1558                               "(sig-val(eddsa(r%M)(s%M)))", sig_r, sig_s);
1559     }
1560   else
1561     {
1562       rc = sign_ecdsa (data, &sk, sig_r, sig_s, ctx.flags, ctx.hash_algo);
1563       if (!rc)
1564         rc = gcry_sexp_build (r_sig, NULL,
1565                               "(sig-val(ecdsa(r%M)(s%M)))", sig_r, sig_s);
1566     }
1567
1568
1569  leave:
1570   gcry_mpi_release (sk.E.p);
1571   gcry_mpi_release (sk.E.a);
1572   gcry_mpi_release (sk.E.b);
1573   gcry_mpi_release (mpi_g);
1574   point_free (&sk.E.G);
1575   gcry_mpi_release (sk.E.n);
1576   gcry_mpi_release (mpi_q);
1577   point_free (&sk.Q);
1578   gcry_mpi_release (sk.d);
1579   gcry_mpi_release (sig_r);
1580   gcry_mpi_release (sig_s);
1581   gcry_free (curvename);
1582   gcry_mpi_release (data);
1583   gcry_sexp_release (l1);
1584   _gcry_pk_util_free_encoding_ctx (&ctx);
1585   if (DBG_CIPHER)
1586     log_debug ("ecc_sign      => %s\n", gpg_strerror (rc));
1587   return rc;
1588 }
1589
1590
1591 static gcry_err_code_t
1592 ecc_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t s_keyparms)
1593 {
1594   gcry_err_code_t rc;
1595   struct pk_encoding_ctx ctx;
1596   gcry_sexp_t l1 = NULL;
1597   char *curvename = NULL;
1598   gcry_mpi_t mpi_g = NULL;
1599   gcry_mpi_t mpi_q = NULL;
1600   gcry_mpi_t sig_r = NULL;
1601   gcry_mpi_t sig_s = NULL;
1602   gcry_mpi_t data = NULL;
1603   ECC_public_key pk;
1604   int sigflags;
1605
1606   memset (&pk, 0, sizeof pk);
1607   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY,
1608                                    ecc_get_nbits (s_keyparms));
1609
1610   /* Extract the data.  */
1611   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1612   if (rc)
1613     goto leave;
1614   if (DBG_CIPHER)
1615     log_mpidump ("ecc_verify data", data);
1616
1617   /*
1618    * Extract the signature value.
1619    */
1620   rc = _gcry_pk_util_preparse_sigval (s_sig, ecc_names, &l1, &sigflags);
1621   if (rc)
1622     goto leave;
1623   rc = _gcry_pk_util_extract_mpis (l1,
1624                                    (sigflags & PUBKEY_FLAG_EDDSA)? "/rs":"rs",
1625                                    &sig_r, &sig_s, NULL);
1626   if (rc)
1627     goto leave;
1628   if (DBG_CIPHER)
1629     {
1630       log_mpidump ("ecc_verify  s_r", sig_r);
1631       log_mpidump ("ecc_verify  s_s", sig_s);
1632     }
1633   if ((ctx.flags & PUBKEY_FLAG_EDDSA) ^ (sigflags & PUBKEY_FLAG_EDDSA))
1634     {
1635       rc = GPG_ERR_CONFLICT; /* Inconsistent use of flag/algoname.  */
1636       goto leave;
1637     }
1638
1639
1640   /*
1641    * Extract the key.
1642    */
1643   rc = _gcry_pk_util_extract_mpis (s_keyparms, "-p?a?b?g?n?/q?",
1644                                    &pk.E.p, &pk.E.a, &pk.E.b, &mpi_g, &pk.E.n,
1645                                    &mpi_q, NULL);
1646   if (rc)
1647     goto leave;
1648   if (mpi_g)
1649     {
1650       point_init (&pk.E.G);
1651       rc = _gcry_ecc_os2ec (&pk.E.G, mpi_g);
1652       if (rc)
1653         goto leave;
1654     }
1655   /* Add missing parameters using the optional curve parameter.  */
1656   gcry_sexp_release (l1);
1657   l1 = gcry_sexp_find_token (s_keyparms, "curve", 5);
1658   if (l1)
1659     {
1660       curvename = gcry_sexp_nth_string (l1, 1);
1661       if (curvename)
1662         {
1663           rc = _gcry_ecc_fill_in_curve (0, curvename, &pk.E, NULL);
1664           if (rc)
1665             return rc;
1666         }
1667     }
1668   /* Guess required fields if a curve parameter has not been given.
1669      FIXME: This is a crude hacks.  We need to fix that.  */
1670   if (!curvename)
1671     {
1672       pk.E.model = ((sigflags & PUBKEY_FLAG_EDDSA)
1673                     ? MPI_EC_TWISTEDEDWARDS
1674                     : MPI_EC_WEIERSTRASS);
1675       pk.E.dialect = ((sigflags & PUBKEY_FLAG_EDDSA)
1676                       ? ECC_DIALECT_ED25519
1677                       : ECC_DIALECT_STANDARD);
1678     }
1679
1680   if (DBG_CIPHER)
1681     {
1682       log_debug ("ecc_verify info: %s/%s\n",
1683                  _gcry_ecc_model2str (pk.E.model),
1684                  _gcry_ecc_dialect2str (pk.E.dialect));
1685       if (pk.E.name)
1686         log_debug  ("ecc_verify name: %s\n", pk.E.name);
1687       log_printmpi ("ecc_verify    p", pk.E.p);
1688       log_printmpi ("ecc_verify    a", pk.E.a);
1689       log_printmpi ("ecc_verify    b", pk.E.b);
1690       log_printpnt ("ecc_verify  g",   &pk.E.G, NULL);
1691       log_printmpi ("ecc_verify    n", pk.E.n);
1692       log_printmpi ("ecc_verify    q", mpi_q);
1693     }
1694   if (!pk.E.p || !pk.E.a || !pk.E.b || !pk.E.G.x || !pk.E.n || !mpi_q)
1695     {
1696       rc = GPG_ERR_NO_OBJ;
1697       goto leave;
1698     }
1699
1700
1701   /*
1702    * Verify the signature.
1703    */
1704   if ((sigflags & PUBKEY_FLAG_EDDSA))
1705     {
1706       rc = verify_eddsa (data, &pk, sig_r, sig_s, ctx.hash_algo, mpi_q);
1707     }
1708   else
1709     {
1710       point_init (&pk.Q);
1711       rc = _gcry_ecc_os2ec (&pk.Q, mpi_q);
1712       if (rc)
1713         goto leave;
1714
1715       if (mpi_is_opaque (data))
1716         {
1717           const void *abuf;
1718           unsigned int abits, qbits;
1719           gcry_mpi_t a;
1720
1721           qbits = mpi_get_nbits (pk.E.n);
1722
1723           abuf = gcry_mpi_get_opaque (data, &abits);
1724           rc = gpg_err_code (gcry_mpi_scan (&a, GCRYMPI_FMT_USG,
1725                                             abuf, (abits+7)/8, NULL));
1726           if (!rc)
1727             {
1728               if (abits > qbits)
1729                 gcry_mpi_rshift (a, a, abits - qbits);
1730
1731               rc = verify_ecdsa (a, &pk, sig_r, sig_s);
1732               gcry_mpi_release (a);
1733             }
1734         }
1735       else
1736         rc = verify_ecdsa (data, &pk, sig_r, sig_s);
1737     }
1738
1739  leave:
1740   gcry_mpi_release (pk.E.p);
1741   gcry_mpi_release (pk.E.a);
1742   gcry_mpi_release (pk.E.b);
1743   gcry_mpi_release (mpi_g);
1744   point_free (&pk.E.G);
1745   gcry_mpi_release (pk.E.n);
1746   gcry_mpi_release (mpi_q);
1747   point_free (&pk.Q);
1748   gcry_mpi_release (data);
1749   gcry_mpi_release (sig_r);
1750   gcry_mpi_release (sig_s);
1751   gcry_free (curvename);
1752   gcry_sexp_release (l1);
1753   _gcry_pk_util_free_encoding_ctx (&ctx);
1754   if (DBG_CIPHER)
1755     log_debug ("ecc_verify    => %s\n", rc?gpg_strerror (rc):"Good");
1756   return rc;
1757 }
1758
1759
1760 /* ecdh raw is classic 2-round DH protocol published in 1976.
1761  *
1762  * Overview of ecc_encrypt_raw and ecc_decrypt_raw.
1763  *
1764  * As with any PK operation, encrypt version uses a public key and
1765  * decrypt -- private.
1766  *
1767  * Symbols used below:
1768  *     G - field generator point
1769  *     d - private long-term scalar
1770  *    dG - public long-term key
1771  *     k - ephemeral scalar
1772  *    kG - ephemeral public key
1773  *   dkG - shared secret
1774  *
1775  * ecc_encrypt_raw description:
1776  *   input:
1777  *     data[0] : private scalar (k)
1778  *   output: A new S-expression with the parameters:
1779  *     s : shared point (kdG)
1780  *     e : generated ephemeral public key (kG)
1781  *
1782  * ecc_decrypt_raw description:
1783  *   input:
1784  *     data[0] : a point kG (ephemeral public key)
1785  *   output:
1786  *     result[0] : shared point (kdG)
1787  */
1788 static gcry_err_code_t
1789 ecc_encrypt_raw (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1790 {
1791   gcry_err_code_t rc;
1792   struct pk_encoding_ctx ctx;
1793   gcry_sexp_t l1 = NULL;
1794   char *curvename = NULL;
1795   gcry_mpi_t mpi_g = NULL;
1796   gcry_mpi_t mpi_q = NULL;
1797   gcry_mpi_t mpi_s = NULL;
1798   gcry_mpi_t mpi_e = NULL;
1799   gcry_mpi_t data = NULL;
1800   ECC_public_key pk;
1801   mpi_ec_t ec = NULL;
1802
1803   memset (&pk, 0, sizeof pk);
1804   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_ENCRYPT,
1805                                    ecc_get_nbits (keyparms));
1806
1807   /*
1808    * Extract the data.
1809    */
1810   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1811   if (rc)
1812     goto leave;
1813   if (DBG_CIPHER)
1814     log_mpidump ("ecc_encrypt data", data);
1815   if (mpi_is_opaque (data))
1816     {
1817       rc = GPG_ERR_INV_DATA;
1818       goto leave;
1819     }
1820
1821
1822   /*
1823    * Extract the key.
1824    */
1825   rc = _gcry_pk_util_extract_mpis (keyparms, "-p?a?b?g?n?+q",
1826                                    &pk.E.p, &pk.E.a, &pk.E.b, &mpi_g, &pk.E.n,
1827                                    &mpi_q, NULL);
1828   if (rc)
1829     goto leave;
1830   if (mpi_g)
1831     {
1832       point_init (&pk.E.G);
1833       rc = _gcry_ecc_os2ec (&pk.E.G, mpi_g);
1834       if (rc)
1835         goto leave;
1836     }
1837   /* Add missing parameters using the optional curve parameter.  */
1838   gcry_sexp_release (l1);
1839   l1 = gcry_sexp_find_token (keyparms, "curve", 5);
1840   if (l1)
1841     {
1842       curvename = gcry_sexp_nth_string (l1, 1);
1843       if (curvename)
1844         {
1845           rc = _gcry_ecc_fill_in_curve (0, curvename, &pk.E, NULL);
1846           if (rc)
1847             return rc;
1848         }
1849     }
1850   /* Guess required fields if a curve parameter has not been given.  */
1851   if (!curvename)
1852     {
1853       pk.E.model = MPI_EC_WEIERSTRASS;
1854       pk.E.dialect = ECC_DIALECT_STANDARD;
1855     }
1856
1857   if (DBG_CIPHER)
1858     {
1859       log_debug ("ecc_encrypt info: %s/%s\n",
1860                  _gcry_ecc_model2str (pk.E.model),
1861                  _gcry_ecc_dialect2str (pk.E.dialect));
1862       if (pk.E.name)
1863         log_debug  ("ecc_encrypt name: %s\n", pk.E.name);
1864       log_printmpi ("ecc_encrypt    p", pk.E.p);
1865       log_printmpi ("ecc_encrypt    a", pk.E.a);
1866       log_printmpi ("ecc_encrypt    b", pk.E.b);
1867       log_printpnt ("ecc_encrypt  g",   &pk.E.G, NULL);
1868       log_printmpi ("ecc_encrypt    n", pk.E.n);
1869       log_printmpi ("ecc_encrypt    q", mpi_q);
1870     }
1871   if (!pk.E.p || !pk.E.a || !pk.E.b || !pk.E.G.x || !pk.E.n || !mpi_q)
1872     {
1873       rc = GPG_ERR_NO_OBJ;
1874       goto leave;
1875     }
1876
1877   /* Convert the public key.  */
1878   if (mpi_q)
1879     {
1880       point_init (&pk.Q);
1881       rc = _gcry_ecc_os2ec (&pk.Q, mpi_q);
1882       if (rc)
1883         goto leave;
1884     }
1885
1886   /* Compute the encrypted value.  */
1887   ec = _gcry_mpi_ec_p_internal_new (pk.E.model, pk.E.dialect,
1888                                     pk.E.p, pk.E.a, pk.E.b);
1889
1890   /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so */
1891   {
1892     mpi_point_struct R;  /* Result that we return.  */
1893     gcry_mpi_t x, y;
1894
1895     x = mpi_new (0);
1896     y = mpi_new (0);
1897
1898     point_init (&R);
1899
1900     /* R = kQ  <=>  R = kdG  */
1901     _gcry_mpi_ec_mul_point (&R, data, &pk.Q, ec);
1902
1903     if (_gcry_mpi_ec_get_affine (x, y, &R, ec))
1904       log_fatal ("ecdh: Failed to get affine coordinates for kdG\n");
1905     mpi_s = _gcry_ecc_ec2os (x, y, pk.E.p);
1906
1907     /* R = kG */
1908     _gcry_mpi_ec_mul_point (&R, data, &pk.E.G, ec);
1909
1910     if (_gcry_mpi_ec_get_affine (x, y, &R, ec))
1911       log_fatal ("ecdh: Failed to get affine coordinates for kG\n");
1912     mpi_e = _gcry_ecc_ec2os (x, y, pk.E.p);
1913
1914     mpi_free (x);
1915     mpi_free (y);
1916
1917     point_free (&R);
1918   }
1919
1920   rc = gcry_sexp_build (r_ciph, NULL, "(enc-val(ecdh(s%m)(e%m)))",
1921                         mpi_s, mpi_e);
1922
1923  leave:
1924   gcry_mpi_release (pk.E.p);
1925   gcry_mpi_release (pk.E.a);
1926   gcry_mpi_release (pk.E.b);
1927   gcry_mpi_release (mpi_g);
1928   point_free (&pk.E.G);
1929   gcry_mpi_release (pk.E.n);
1930   gcry_mpi_release (mpi_q);
1931   point_free (&pk.Q);
1932   gcry_mpi_release (data);
1933   gcry_mpi_release (mpi_s);
1934   gcry_mpi_release (mpi_e);
1935   gcry_free (curvename);
1936   _gcry_mpi_ec_free (ec);
1937   _gcry_pk_util_free_encoding_ctx (&ctx);
1938   if (DBG_CIPHER)
1939     log_debug ("ecc_encrypt    => %s\n", gpg_strerror (rc));
1940   return rc;
1941 }
1942
1943
1944 /*  input:
1945  *     data[0] : a point kG (ephemeral public key)
1946  *   output:
1947  *     resaddr[0] : shared point kdG
1948  *
1949  *  see ecc_encrypt_raw for details.
1950  */
1951 static gcry_err_code_t
1952 ecc_decrypt_raw (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1953 {
1954   gpg_err_code_t rc;
1955   struct pk_encoding_ctx ctx;
1956   gcry_sexp_t l1 = NULL;
1957   gcry_mpi_t data_e = NULL;
1958   ECC_secret_key sk;
1959   gcry_mpi_t mpi_g = NULL;
1960   char *curvename = NULL;
1961   mpi_ec_t ec = NULL;
1962   mpi_point_struct kG;
1963   mpi_point_struct R;
1964   gcry_mpi_t r = NULL;
1965
1966   memset (&sk, 0, sizeof sk);
1967   point_init (&kG);
1968   point_init (&R);
1969
1970   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_DECRYPT,
1971                                    ecc_get_nbits (keyparms));
1972
1973   /*
1974    * Extract the data.
1975    */
1976   rc = _gcry_pk_util_preparse_encval (s_data, ecc_names, &l1, &ctx);
1977   if (rc)
1978     goto leave;
1979   rc = _gcry_pk_util_extract_mpis (l1, "e", &data_e, NULL);
1980   if (rc)
1981     goto leave;
1982   if (DBG_CIPHER)
1983     log_printmpi ("ecc_decrypt  d_e", data_e);
1984   if (mpi_is_opaque (data_e))
1985     {
1986       rc = GPG_ERR_INV_DATA;
1987       goto leave;
1988     }
1989
1990   /*
1991    * Extract the key.
1992    */
1993   rc = _gcry_pk_util_extract_mpis (keyparms, "-p?a?b?g?n?+d",
1994                                    &sk.E.p, &sk.E.a, &sk.E.b, &mpi_g, &sk.E.n,
1995                                    &sk.d, NULL);
1996   if (rc)
1997     goto leave;
1998   if (mpi_g)
1999     {
2000       point_init (&sk.E.G);
2001       rc = _gcry_ecc_os2ec (&sk.E.G, mpi_g);
2002       if (rc)
2003         goto leave;
2004     }
2005   /* Add missing parameters using the optional curve parameter.  */
2006   gcry_sexp_release (l1);
2007   l1 = gcry_sexp_find_token (keyparms, "curve", 5);
2008   if (l1)
2009     {
2010       curvename = gcry_sexp_nth_string (l1, 1);
2011       if (curvename)
2012         {
2013           rc = _gcry_ecc_fill_in_curve (0, curvename, &sk.E, NULL);
2014           if (rc)
2015             return rc;
2016         }
2017     }
2018   /* Guess required fields if a curve parameter has not been given.  */
2019   if (!curvename)
2020     {
2021       sk.E.model = MPI_EC_WEIERSTRASS;
2022       sk.E.dialect = ECC_DIALECT_STANDARD;
2023     }
2024   if (DBG_CIPHER)
2025     {
2026       log_debug ("ecc_decrypt info: %s/%s\n",
2027                  _gcry_ecc_model2str (sk.E.model),
2028                  _gcry_ecc_dialect2str (sk.E.dialect));
2029       if (sk.E.name)
2030         log_debug  ("ecc_decrypt name: %s\n", sk.E.name);
2031       log_printmpi ("ecc_decrypt    p", sk.E.p);
2032       log_printmpi ("ecc_decrypt    a", sk.E.a);
2033       log_printmpi ("ecc_decrypt    b", sk.E.b);
2034       log_printpnt ("ecc_decrypt  g",   &sk.E.G, NULL);
2035       log_printmpi ("ecc_decrypt    n", sk.E.n);
2036       if (!fips_mode ())
2037         log_printmpi ("ecc_decrypt    d", sk.d);
2038     }
2039   if (!sk.E.p || !sk.E.a || !sk.E.b || !sk.E.G.x || !sk.E.n || !sk.d)
2040     {
2041       rc = GPG_ERR_NO_OBJ;
2042       goto leave;
2043     }
2044
2045
2046   /*
2047    * Compute the plaintext.
2048    */
2049   rc = _gcry_ecc_os2ec (&kG, data_e);
2050   if (rc)
2051     {
2052       point_free (&kG);
2053       return rc;
2054     }
2055
2056   ec = _gcry_mpi_ec_p_internal_new (sk.E.model, sk.E.dialect,
2057                                     sk.E.p, sk.E.a, sk.E.b);
2058
2059   /* R = dkG */
2060   _gcry_mpi_ec_mul_point (&R, sk.d, &kG, ec);
2061
2062   /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so:  */
2063   {
2064     gcry_mpi_t x, y;
2065
2066     x = mpi_new (0);
2067     y = mpi_new (0);
2068
2069     if (_gcry_mpi_ec_get_affine (x, y, &R, ec))
2070       log_fatal ("ecdh: Failed to get affine coordinates\n");
2071
2072     r = _gcry_ecc_ec2os (x, y, sk.E.p);
2073     if (!r)
2074       rc = gpg_err_code_from_syserror ();
2075     else
2076       rc = 0;
2077     mpi_free (x);
2078     mpi_free (y);
2079   }
2080   if (DBG_CIPHER)
2081     log_printmpi ("ecc_decrypt  res", r);
2082
2083   if (!rc)
2084     rc = gcry_sexp_build (r_plain, NULL, "(value %m)", r);
2085
2086  leave:
2087   point_free (&R);
2088   point_free (&kG);
2089   gcry_mpi_release (r);
2090   gcry_mpi_release (sk.E.p);
2091   gcry_mpi_release (sk.E.a);
2092   gcry_mpi_release (sk.E.b);
2093   gcry_mpi_release (mpi_g);
2094   point_free (&sk.E.G);
2095   gcry_mpi_release (sk.E.n);
2096   gcry_mpi_release (sk.d);
2097   gcry_mpi_release (data_e);
2098   gcry_free (curvename);
2099   gcry_sexp_release (l1);
2100   _gcry_mpi_ec_free (ec);
2101   _gcry_pk_util_free_encoding_ctx (&ctx);
2102   if (DBG_CIPHER)
2103     log_debug ("ecc_decrypt    => %s\n", gpg_strerror (rc));
2104   return rc;
2105 }
2106
2107
2108 /* Return the number of bits for the key described by PARMS.  On error
2109  * 0 is returned.  The format of PARMS starts with the algorithm name;
2110  * for example:
2111  *
2112  *   (ecc
2113  *     (p <mpi>)
2114  *     (a <mpi>)
2115  *     (b <mpi>)
2116  *     (g <mpi>)
2117  *     (n <mpi>)
2118  *     (q <mpi>))
2119  *
2120  * More parameters may be given currently P is needed.  FIXME: We
2121  * need allow for a "curve" parameter.
2122  */
2123 static unsigned int
2124 ecc_get_nbits (gcry_sexp_t parms)
2125 {
2126   gcry_sexp_t l1;
2127   gcry_mpi_t p;
2128   unsigned int nbits = 0;
2129   char *curve;
2130
2131   l1 = gcry_sexp_find_token (parms, "p", 1);
2132   if (!l1)
2133     { /* Parameter P not found - check whether we have "curve".  */
2134       l1 = gcry_sexp_find_token (parms, "curve", 5);
2135       if (!l1)
2136         return 0; /* Neither P nor CURVE found.  */
2137
2138       curve = _gcry_sexp_nth_string (l1, 1);
2139       gcry_sexp_release (l1);
2140       if (!curve)
2141         return 0;  /* No curve name given (or out of core). */
2142
2143       if (_gcry_ecc_fill_in_curve (0, curve, NULL, &nbits))
2144         nbits = 0;
2145       gcry_free (curve);
2146     }
2147   else
2148     {
2149       p = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
2150       gcry_sexp_release (l1);
2151       if (p)
2152         {
2153           nbits = mpi_get_nbits (p);
2154           gcry_mpi_release (p);
2155         }
2156     }
2157   return nbits;
2158 }
2159
2160
2161 /* See rsa.c for a description of this function.  */
2162 static gpg_err_code_t
2163 compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
2164 {
2165 #define N_COMPONENTS 6
2166   static const char names[N_COMPONENTS+1] = "pabgnq";
2167   gpg_err_code_t ec = 0;
2168   gcry_sexp_t l1;
2169   gcry_mpi_t values[N_COMPONENTS];
2170   int idx;
2171
2172   /* Clear the values for easier error cleanup.  */
2173   for (idx=0; idx < N_COMPONENTS; idx++)
2174     values[idx] = NULL;
2175
2176   /* Fill values with all provided parameters.  */
2177   for (idx=0; idx < N_COMPONENTS; idx++)
2178     {
2179       l1 = gcry_sexp_find_token (keyparam, names+idx, 1);
2180       if (l1)
2181         {
2182           values[idx] = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
2183           gcry_sexp_release (l1);
2184           if (!values[idx])
2185             {
2186               ec = GPG_ERR_INV_OBJ;
2187               goto leave;
2188             }
2189         }
2190     }
2191
2192   /* Check whether a curve parameter is available and use that to fill
2193      in missing values.  */
2194   l1 = gcry_sexp_find_token (keyparam, "curve", 5);
2195   if (l1)
2196     {
2197       char *curve;
2198       gcry_mpi_t tmpvalues[N_COMPONENTS];
2199
2200       for (idx = 0; idx < N_COMPONENTS; idx++)
2201         tmpvalues[idx] = NULL;
2202
2203       curve = _gcry_sexp_nth_string (l1, 1);
2204       gcry_sexp_release (l1);
2205       if (!curve)
2206         {
2207           ec = GPG_ERR_INV_OBJ; /* Name missing or out of core. */
2208           goto leave;
2209         }
2210       ec = _gcry_ecc_get_param (curve, tmpvalues);
2211       gcry_free (curve);
2212       if (ec)
2213         goto leave;
2214
2215       for (idx = 0; idx < N_COMPONENTS; idx++)
2216         {
2217           if (!values[idx])
2218             values[idx] = tmpvalues[idx];
2219           else
2220             mpi_free (tmpvalues[idx]);
2221         }
2222     }
2223
2224   /* Check that all parameters are known and normalize all MPIs (that
2225      should not be required but we use an internal function later and
2226      thus we better make 100% sure that they are normalized). */
2227   for (idx = 0; idx < N_COMPONENTS; idx++)
2228     if (!values[idx])
2229       {
2230         ec = GPG_ERR_NO_OBJ;
2231         goto leave;
2232       }
2233     else
2234       _gcry_mpi_normalize (values[idx]);
2235
2236   /* Hash them all.  */
2237   for (idx = 0; idx < N_COMPONENTS; idx++)
2238     {
2239       char buf[30];
2240       unsigned char *rawmpi;
2241       unsigned int rawmpilen;
2242
2243       rawmpi = _gcry_mpi_get_buffer (values[idx], 0, &rawmpilen, NULL);
2244       if (!rawmpi)
2245         {
2246           ec = gpg_err_code_from_syserror ();
2247           goto leave;
2248         }
2249       snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], rawmpilen);
2250       gcry_md_write (md, buf, strlen (buf));
2251       gcry_md_write (md, rawmpi, rawmpilen);
2252       gcry_md_write (md, ")", 1);
2253       gcry_free (rawmpi);
2254     }
2255
2256  leave:
2257   for (idx = 0; idx < N_COMPONENTS; idx++)
2258     _gcry_mpi_release (values[idx]);
2259
2260   return ec;
2261 #undef N_COMPONENTS
2262 }
2263
2264
2265 \f
2266 /*
2267    Low-level API helper functions.
2268  */
2269
2270 /* This is the worker function for gcry_pubkey_get_sexp for ECC
2271    algorithms.  Note that the caller has already stored NULL at
2272    R_SEXP.  */
2273 gpg_err_code_t
2274 _gcry_pk_ecc_get_sexp (gcry_sexp_t *r_sexp, int mode, mpi_ec_t ec)
2275 {
2276   gpg_err_code_t rc;
2277   gcry_mpi_t mpi_G = NULL;
2278   gcry_mpi_t mpi_Q = NULL;
2279
2280   if (!ec->p || !ec->a || !ec->b || !ec->G || !ec->n)
2281     return GPG_ERR_BAD_CRYPT_CTX;
2282
2283   if (mode == GCRY_PK_GET_SECKEY && !ec->d)
2284     return GPG_ERR_NO_SECKEY;
2285
2286   /* Compute the public point if it is missing.  */
2287   if (!ec->Q && ec->d)
2288     ec->Q = _gcry_ecc_compute_public (NULL, ec);
2289
2290   /* Encode G and Q.  */
2291   mpi_G = _gcry_mpi_ec_ec2os (ec->G, ec);
2292   if (!mpi_G)
2293     {
2294       rc = GPG_ERR_BROKEN_PUBKEY;
2295       goto leave;
2296     }
2297   if (!ec->Q)
2298     {
2299       rc = GPG_ERR_BAD_CRYPT_CTX;
2300       goto leave;
2301     }
2302
2303   if (ec->dialect == ECC_DIALECT_ED25519)
2304     {
2305       unsigned char *encpk;
2306       unsigned int encpklen;
2307
2308       rc = _gcry_ecc_eddsa_encodepoint (ec->Q, ec, NULL, NULL,
2309                                         &encpk, &encpklen);
2310       if (rc)
2311         goto leave;
2312       mpi_Q = gcry_mpi_set_opaque (NULL, encpk, encpklen*8);
2313       encpk = NULL;
2314     }
2315   else
2316     {
2317       mpi_Q = _gcry_mpi_ec_ec2os (ec->Q, ec);
2318     }
2319   if (!mpi_Q)
2320     {
2321       rc = GPG_ERR_BROKEN_PUBKEY;
2322       goto leave;
2323     }
2324
2325   /* Fixme: We should return a curve name instead of the parameters if
2326      if know that they match a curve.  */
2327
2328   if (ec->d && (!mode || mode == GCRY_PK_GET_SECKEY))
2329     {
2330       /* Let's return a private key. */
2331       rc = gcry_sexp_build
2332         (r_sexp, NULL,
2333          "(private-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)(q%m)(d%m)))",
2334          ec->p, ec->a, ec->b, mpi_G, ec->n, mpi_Q, ec->d);
2335     }
2336   else if (ec->Q)
2337     {
2338       /* Let's return a public key.  */
2339       rc = gcry_sexp_build
2340         (r_sexp, NULL,
2341          "(public-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)(q%m)))",
2342          ec->p, ec->a, ec->b, mpi_G, ec->n, mpi_Q);
2343     }
2344   else
2345     rc = GPG_ERR_BAD_CRYPT_CTX;
2346
2347  leave:
2348   mpi_free (mpi_Q);
2349   mpi_free (mpi_G);
2350   return rc;
2351 }
2352
2353
2354 \f
2355 /*
2356      Self-test section.
2357  */
2358
2359
2360 static gpg_err_code_t
2361 selftests_ecdsa (selftest_report_func_t report)
2362 {
2363   const char *what;
2364   const char *errtxt;
2365
2366   what = "low-level";
2367   errtxt = NULL; /*selftest ();*/
2368   if (errtxt)
2369     goto failed;
2370
2371   /* FIXME:  need more tests.  */
2372
2373   return 0; /* Succeeded. */
2374
2375  failed:
2376   if (report)
2377     report ("pubkey", GCRY_PK_ECC, what, errtxt);
2378   return GPG_ERR_SELFTEST_FAILED;
2379 }
2380
2381
2382 /* Run a full self-test for ALGO and return 0 on success.  */
2383 static gpg_err_code_t
2384 run_selftests (int algo, int extended, selftest_report_func_t report)
2385 {
2386   (void)extended;
2387
2388   if (algo != GCRY_PK_ECC)
2389     return GPG_ERR_PUBKEY_ALGO;
2390
2391   return selftests_ecdsa (report);
2392 }
2393
2394
2395
2396 \f
2397 gcry_pk_spec_t _gcry_pubkey_spec_ecc =
2398   {
2399     GCRY_PK_ECC, { 0, 0 },
2400     (GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR),
2401     "ECC", ecc_names,
2402     "pabgnq", "pabgnqd", "sw", "rs", "pabgnq",
2403     ecc_generate,
2404     ecc_check_secret_key,
2405     ecc_encrypt_raw,
2406     ecc_decrypt_raw,
2407     ecc_sign,
2408     ecc_verify,
2409     ecc_get_nbits,
2410     run_selftests,
2411     compute_keygrip,
2412     _gcry_ecc_get_param,
2413     _gcry_ecc_get_curve,
2414     _gcry_ecc_get_param_sexp
2415   };