pubkey: Move sexp parsing for gcry_pk_verify 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 (int algo, gcry_sexp_t *r_result, gcry_mpi_t data, gcry_mpi_t *skey,
1465           int flags, int hashalgo)
1466 {
1467   gpg_err_code_t rc;
1468   ECC_secret_key sk;
1469   gcry_mpi_t r, s;
1470
1471   (void)algo;
1472
1473   if (!data || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4]
1474       || !skey[6] )
1475     return GPG_ERR_BAD_MPI;
1476
1477   /* FIXME: The setting of model and dialect are crude hacks.  We will
1478      fix that by moving the s-expression parsing from pubkey.c to
1479      here.  */
1480   sk.E.model = ((flags & PUBKEY_FLAG_EDDSA)
1481                 ? MPI_EC_TWISTEDEDWARDS
1482                 : MPI_EC_WEIERSTRASS);
1483   sk.E.dialect = ((flags & PUBKEY_FLAG_EDDSA)
1484                   ? ECC_DIALECT_ED25519
1485                   : ECC_DIALECT_STANDARD);
1486   sk.E.p = skey[0];
1487   sk.E.a = skey[1];
1488   sk.E.b = skey[2];
1489   point_init (&sk.E.G);
1490   sk.Q.x = NULL;
1491   sk.Q.y = NULL;
1492   sk.Q.z = NULL;
1493   rc = _gcry_ecc_os2ec (&sk.E.G, skey[3]);
1494   if (rc)
1495     {
1496       point_free (&sk.E.G);
1497       return rc;
1498     }
1499   sk.E.n = skey[4];
1500
1501   r = mpi_alloc (mpi_get_nlimbs (sk.E.p));
1502   s = mpi_alloc (mpi_get_nlimbs (sk.E.p));
1503
1504   {
1505     const unsigned char *buf;
1506     unsigned int n;
1507
1508     gcry_assert (mpi_is_opaque (skey[6]));
1509
1510     buf = gcry_mpi_get_opaque (skey[6], &n);
1511     if (!buf)
1512       rc = GPG_ERR_INV_OBJ;
1513     else
1514       {
1515         n = (n + 7)/8;
1516         sk.d = NULL;
1517         rc = gcry_mpi_scan (&sk.d, GCRYMPI_FMT_USG, buf, n, NULL);
1518         if (!rc)
1519           {
1520             if ((flags & PUBKEY_FLAG_EDDSA))
1521               {
1522                 rc = sign_eddsa (data, &sk, r, s, hashalgo, skey[5]);
1523                 if (!rc)
1524                   rc = gcry_sexp_build (r_result, NULL,
1525                                         "(sig-val(eddsa(r%M)(s%M)))", r, s);
1526               }
1527             else
1528               {
1529                 rc = sign_ecdsa (data, &sk, r, s, flags, hashalgo);
1530                 if (!rc)
1531                   rc = gcry_sexp_build (r_result, NULL,
1532                                         "(sig-val(ecdsa(r%M)(s%M)))", r, s);
1533               }
1534             gcry_mpi_release (sk.d);
1535             sk.d = NULL;
1536           }
1537       }
1538   }
1539
1540   mpi_free (r);
1541   mpi_free (s);
1542   point_free (&sk.E.G);
1543   if (sk.Q.x)
1544     point_free (&sk.Q);
1545   return rc;
1546 }
1547
1548
1549 static gcry_err_code_t
1550 ecc_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t s_keyparms)
1551 {
1552   gcry_err_code_t rc;
1553   struct pk_encoding_ctx ctx;
1554   gcry_sexp_t l1 = NULL;
1555   char *curvename = NULL;
1556   gcry_mpi_t mpi_g = NULL;
1557   gcry_mpi_t mpi_q = NULL;
1558   gcry_mpi_t sig_r = NULL;
1559   gcry_mpi_t sig_s = NULL;
1560   gcry_mpi_t data = NULL;
1561   ECC_public_key pk;
1562   int sigflags;
1563
1564   memset (&pk, 0, sizeof pk);
1565   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY,
1566                                    ecc_get_nbits (s_keyparms));
1567
1568   /* Extract the data.  */
1569   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1570   if (rc)
1571     goto leave;
1572   if (DBG_CIPHER)
1573     log_mpidump ("ecc_verify data", data);
1574
1575   /*
1576    * Extract the signature value.
1577    */
1578   rc = _gcry_pk_util_preparse_sigval (s_sig, ecc_names, &l1, &sigflags);
1579   if (rc)
1580     goto leave;
1581   rc = _gcry_pk_util_extract_mpis (l1,
1582                                    (sigflags & PUBKEY_FLAG_EDDSA)? "/rs":"rs",
1583                                    &sig_r, &sig_s, NULL);
1584   if (rc)
1585     goto leave;
1586   if (DBG_CIPHER)
1587     {
1588       log_mpidump ("ecc_verify  s_r", sig_r);
1589       log_mpidump ("ecc_verify  s_s", sig_s);
1590     }
1591   if ((ctx.flags & PUBKEY_FLAG_EDDSA) ^ (sigflags & PUBKEY_FLAG_EDDSA))
1592     {
1593       rc = GPG_ERR_CONFLICT; /* Inconsistent use of flag/algoname.  */
1594       goto leave;
1595     }
1596
1597
1598   /*
1599    * Extract the key.
1600    */
1601   rc = _gcry_pk_util_extract_mpis (s_keyparms, "-p?a?b?g?n?/q?",
1602                                    &pk.E.p, &pk.E.a, &pk.E.b, &mpi_g, &pk.E.n,
1603                                    &mpi_q, NULL);
1604   if (rc)
1605     goto leave;
1606   if (mpi_g)
1607     {
1608       point_init (&pk.E.G);
1609       rc = _gcry_ecc_os2ec (&pk.E.G, mpi_g);
1610       if (rc)
1611         goto leave;
1612     }
1613   /* Add missing parameters using the optional curve parameter.  */
1614   gcry_sexp_release (l1);
1615   l1 = gcry_sexp_find_token (s_keyparms, "curve", 5);
1616   if (l1)
1617     {
1618       curvename = gcry_sexp_nth_string (l1, 1);
1619       if (curvename)
1620         {
1621           rc = _gcry_ecc_fill_in_curve (0, curvename, &pk.E, NULL);
1622           if (rc)
1623             return rc;
1624         }
1625     }
1626   /* Guess required fields if a curve parameter has not been given.
1627      FIXME: This is a crude hacks.  We need to fix that.  */
1628   if (!curvename)
1629     {
1630       pk.E.model = ((sigflags & PUBKEY_FLAG_EDDSA)
1631                     ? MPI_EC_TWISTEDEDWARDS
1632                     : MPI_EC_WEIERSTRASS);
1633       pk.E.dialect = ((sigflags & PUBKEY_FLAG_EDDSA)
1634                       ? ECC_DIALECT_ED25519
1635                       : ECC_DIALECT_STANDARD);
1636     }
1637
1638   if (DBG_CIPHER)
1639     {
1640       log_debug ("ecc_verify info: %s/%s\n",
1641                  _gcry_ecc_model2str (pk.E.model),
1642                  _gcry_ecc_dialect2str (pk.E.dialect));
1643       if (pk.E.name)
1644         log_debug  ("ecc_verify name: %s\n", pk.E.name);
1645       log_printmpi ("ecc_verify    p", pk.E.p);
1646       log_printmpi ("ecc_verify    a", pk.E.a);
1647       log_printmpi ("ecc_verify    b", pk.E.b);
1648       log_printpnt ("ecc_verify  g",   &pk.E.G, NULL);
1649       log_printmpi ("ecc_verify    n", pk.E.n);
1650       log_printmpi ("ecc_verify    q", mpi_q);
1651     }
1652
1653
1654   /*
1655    * Verify the signature.
1656    */
1657   if ((sigflags & PUBKEY_FLAG_EDDSA))
1658     {
1659       rc = verify_eddsa (data, &pk, sig_r, sig_s, ctx.hash_algo, mpi_q);
1660     }
1661   else
1662     {
1663       point_init (&pk.Q);
1664       rc = _gcry_ecc_os2ec (&pk.Q, mpi_q);
1665       if (rc)
1666         goto leave;
1667
1668       if (mpi_is_opaque (data))
1669         {
1670           const void *abuf;
1671           unsigned int abits, qbits;
1672           gcry_mpi_t a;
1673
1674           qbits = mpi_get_nbits (pk.E.n);
1675
1676           abuf = gcry_mpi_get_opaque (data, &abits);
1677           rc = gpg_err_code (gcry_mpi_scan (&a, GCRYMPI_FMT_USG,
1678                                             abuf, (abits+7)/8, NULL));
1679           if (!rc)
1680             {
1681               if (abits > qbits)
1682                 gcry_mpi_rshift (a, a, abits - qbits);
1683
1684               rc = verify_ecdsa (a, &pk, sig_r, sig_s);
1685               gcry_mpi_release (a);
1686             }
1687         }
1688       else
1689         rc = verify_ecdsa (data, &pk, sig_r, sig_s);
1690     }
1691
1692  leave:
1693   gcry_mpi_release (pk.E.p);
1694   gcry_mpi_release (pk.E.a);
1695   gcry_mpi_release (pk.E.b);
1696   point_free (&pk.E.G);
1697   gcry_mpi_release (pk.E.n);
1698   point_free (&pk.Q);
1699   gcry_mpi_release (mpi_g);
1700   gcry_mpi_release (data);
1701   gcry_mpi_release (sig_r);
1702   gcry_mpi_release (sig_s);
1703   gcry_free (curvename);
1704   gcry_sexp_release (l1);
1705   _gcry_pk_util_free_encoding_ctx (&ctx);
1706   if (DBG_CIPHER)
1707     log_debug ("ecc_verify    => %s\n", rc?gpg_strerror (rc):"good");
1708   return rc;
1709 }
1710
1711
1712 /* ecdh raw is classic 2-round DH protocol published in 1976.
1713  *
1714  * Overview of ecc_encrypt_raw and ecc_decrypt_raw.
1715  *
1716  * As with any PK operation, encrypt version uses a public key and
1717  * decrypt -- private.
1718  *
1719  * Symbols used below:
1720  *     G - field generator point
1721  *     d - private long-term scalar
1722  *    dG - public long-term key
1723  *     k - ephemeral scalar
1724  *    kG - ephemeral public key
1725  *   dkG - shared secret
1726  *
1727  * ecc_encrypt_raw description:
1728  *   input:
1729  *     data[0] : private scalar (k)
1730  *   output: A new S-expression with the parameters:
1731  *     s : shared point (kdG)
1732  *     e : generated ephemeral public key (kG)
1733  *
1734  * ecc_decrypt_raw description:
1735  *   input:
1736  *     data[0] : a point kG (ephemeral public key)
1737  *   output:
1738  *     result[0] : shared point (kdG)
1739  */
1740 static gcry_err_code_t
1741 ecc_encrypt_raw (int algo, gcry_sexp_t *r_result, gcry_mpi_t k,
1742                  gcry_mpi_t *pkey, int flags)
1743 {
1744   gpg_err_code_t rc;
1745   ECC_public_key pk;
1746   mpi_ec_t ctx;
1747   gcry_mpi_t s, e;
1748
1749   (void)algo;
1750   (void)flags;
1751
1752   if (!k
1753       || !pkey[0] || !pkey[1] || !pkey[2] || !pkey[3] || !pkey[4] || !pkey[5])
1754     return GPG_ERR_BAD_MPI;
1755
1756   pk.E.model = MPI_EC_WEIERSTRASS;
1757   pk.E.p = pkey[0];
1758   pk.E.a = pkey[1];
1759   pk.E.b = pkey[2];
1760   point_init (&pk.E.G);
1761   rc = _gcry_ecc_os2ec (&pk.E.G, pkey[3]);
1762   if (rc)
1763     {
1764       point_free (&pk.E.G);
1765       return rc;
1766     }
1767   pk.E.n = pkey[4];
1768   point_init (&pk.Q);
1769   rc = _gcry_ecc_os2ec (&pk.Q, pkey[5]);
1770   if (rc)
1771     {
1772       point_free (&pk.E.G);
1773       point_free (&pk.Q);
1774       return rc;
1775     }
1776
1777   ctx = _gcry_mpi_ec_p_internal_new (pk.E.model, pk.E.dialect,
1778                                      pk.E.p, pk.E.a, pk.E.b);
1779   s = mpi_alloc (mpi_get_nlimbs (pk.E.p));
1780   e = mpi_alloc (mpi_get_nlimbs (pk.E.p));
1781
1782   /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so */
1783   {
1784     mpi_point_struct R;  /* Result that we return.  */
1785     gcry_mpi_t x, y;
1786
1787     x = mpi_new (0);
1788     y = mpi_new (0);
1789
1790     point_init (&R);
1791
1792     /* R = kQ  <=>  R = kdG  */
1793     _gcry_mpi_ec_mul_point (&R, k, &pk.Q, ctx);
1794
1795     if (_gcry_mpi_ec_get_affine (x, y, &R, ctx))
1796       log_fatal ("ecdh: Failed to get affine coordinates for kdG\n");
1797     s = _gcry_ecc_ec2os (x, y, pk.E.p);
1798
1799     /* R = kG */
1800     _gcry_mpi_ec_mul_point (&R, k, &pk.E.G, ctx);
1801
1802     if (_gcry_mpi_ec_get_affine (x, y, &R, ctx))
1803       log_fatal ("ecdh: Failed to get affine coordinates for kG\n");
1804     e = _gcry_ecc_ec2os (x, y, pk.E.p);
1805
1806     mpi_free (x);
1807     mpi_free (y);
1808
1809     point_free (&R);
1810   }
1811
1812   _gcry_mpi_ec_free (ctx);
1813   point_free (&pk.E.G);
1814   point_free (&pk.Q);
1815
1816   rc = gcry_sexp_build (r_result, NULL, "(enc-val(ecdh(s%m)(e%m)))", s, e);
1817   mpi_free (s);
1818   mpi_free (e);
1819
1820   return rc;
1821 }
1822
1823 /*  input:
1824  *     data[0] : a point kG (ephemeral public key)
1825  *   output:
1826  *     resaddr[0] : shared point kdG
1827  *
1828  *  see ecc_encrypt_raw for details.
1829  */
1830 static gcry_err_code_t
1831 ecc_decrypt_raw (int algo, gcry_sexp_t *r_plain, gcry_mpi_t *data,
1832                  gcry_mpi_t *skey, int flags,
1833                  enum pk_encoding encoding, int hash_algo,
1834                  unsigned char *label, size_t labellen)
1835 {
1836   gpg_err_code_t rc;
1837   ECC_secret_key sk;
1838   mpi_point_struct R;   /* Result that we return.  */
1839   mpi_point_struct kG;
1840   mpi_ec_t ctx;
1841   gcry_mpi_t r;
1842
1843   (void)algo;
1844   (void)flags;
1845   (void)encoding;
1846   (void)hash_algo;
1847   (void)label;
1848   (void)labellen;
1849
1850   if (!data || !data[0]
1851       || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4]
1852       || !skey[5] || !skey[6] )
1853     return GPG_ERR_BAD_MPI;
1854
1855   point_init (&kG);
1856   rc = _gcry_ecc_os2ec (&kG, data[0]);
1857   if (rc)
1858     {
1859       point_free (&kG);
1860       return rc;
1861     }
1862
1863   sk.E.model = MPI_EC_WEIERSTRASS;
1864   sk.E.p = skey[0];
1865   sk.E.a = skey[1];
1866   sk.E.b = skey[2];
1867   point_init (&sk.E.G);
1868   rc = _gcry_ecc_os2ec (&sk.E.G, skey[3]);
1869   if (rc)
1870     {
1871       point_free (&kG);
1872       point_free (&sk.E.G);
1873       return rc;
1874     }
1875   sk.E.n = skey[4];
1876   point_init (&sk.Q);
1877   rc = _gcry_ecc_os2ec (&sk.Q, skey[5]);
1878   if (rc)
1879     {
1880       point_free (&kG);
1881       point_free (&sk.E.G);
1882       point_free (&sk.Q);
1883       return rc;
1884     }
1885   sk.d = skey[6];
1886
1887   ctx = _gcry_mpi_ec_p_internal_new (sk.E.model, sk.E.dialect,
1888                                      sk.E.p, sk.E.a, sk.E.b);
1889
1890   /* R = dkG */
1891   point_init (&R);
1892   _gcry_mpi_ec_mul_point (&R, sk.d, &kG, ctx);
1893
1894   point_free (&kG);
1895
1896   /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so:  */
1897   {
1898     gcry_mpi_t x, y;
1899
1900     x = mpi_new (0);
1901     y = mpi_new (0);
1902
1903     if (_gcry_mpi_ec_get_affine (x, y, &R, ctx))
1904       log_fatal ("ecdh: Failed to get affine coordinates\n");
1905
1906     r = _gcry_ecc_ec2os (x, y, sk.E.p);
1907     if (!r)
1908       rc = gpg_err_code_from_syserror ();
1909     else
1910       rc = 0;
1911     mpi_free (x);
1912     mpi_free (y);
1913   }
1914
1915   point_free (&R);
1916   _gcry_mpi_ec_free (ctx);
1917   point_free (&kG);
1918   point_free (&sk.E.G);
1919   point_free (&sk.Q);
1920
1921   if (!rc)
1922     rc = gcry_sexp_build (r_plain, NULL, "(value %m)", r);
1923   mpi_free (r);
1924   return rc;
1925 }
1926
1927
1928 /* Return the number of bits for the key described by PARMS.  On error
1929  * 0 is returned.  The format of PARMS starts with the algorithm name;
1930  * for example:
1931  *
1932  *   (ecc
1933  *     (p <mpi>)
1934  *     (a <mpi>)
1935  *     (b <mpi>)
1936  *     (g <mpi>)
1937  *     (n <mpi>)
1938  *     (q <mpi>))
1939  *
1940  * More parameters may be given currently P is needed.  FIXME: We
1941  * need allow for a "curve" parameter.
1942  */
1943 static unsigned int
1944 ecc_get_nbits (gcry_sexp_t parms)
1945 {
1946   gcry_sexp_t l1;
1947   gcry_mpi_t p;
1948   unsigned int nbits = 0;
1949   char *curve;
1950
1951   l1 = gcry_sexp_find_token (parms, "p", 1);
1952   if (!l1)
1953     { /* Parameter P not found - check whether we have "curve".  */
1954       l1 = gcry_sexp_find_token (parms, "curve", 5);
1955       if (!l1)
1956         return 0; /* Neither P nor CURVE found.  */
1957
1958       curve = _gcry_sexp_nth_string (l1, 1);
1959       gcry_sexp_release (l1);
1960       if (!curve)
1961         return 0;  /* No curve name given (or out of core). */
1962
1963       if (_gcry_ecc_fill_in_curve (0, curve, NULL, &nbits))
1964         nbits = 0;
1965       gcry_free (curve);
1966     }
1967   else
1968     {
1969       p = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1970       gcry_sexp_release (l1);
1971       if (p)
1972         {
1973           nbits = mpi_get_nbits (p);
1974           gcry_mpi_release (p);
1975         }
1976     }
1977   return nbits;
1978 }
1979
1980
1981 /* See rsa.c for a description of this function.  */
1982 static gpg_err_code_t
1983 compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
1984 {
1985 #define N_COMPONENTS 6
1986   static const char names[N_COMPONENTS+1] = "pabgnq";
1987   gpg_err_code_t ec = 0;
1988   gcry_sexp_t l1;
1989   gcry_mpi_t values[N_COMPONENTS];
1990   int idx;
1991
1992   /* Clear the values for easier error cleanup.  */
1993   for (idx=0; idx < N_COMPONENTS; idx++)
1994     values[idx] = NULL;
1995
1996   /* Fill values with all provided parameters.  */
1997   for (idx=0; idx < N_COMPONENTS; idx++)
1998     {
1999       l1 = gcry_sexp_find_token (keyparam, names+idx, 1);
2000       if (l1)
2001         {
2002           values[idx] = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
2003           gcry_sexp_release (l1);
2004           if (!values[idx])
2005             {
2006               ec = GPG_ERR_INV_OBJ;
2007               goto leave;
2008             }
2009         }
2010     }
2011
2012   /* Check whether a curve parameter is available and use that to fill
2013      in missing values.  */
2014   l1 = gcry_sexp_find_token (keyparam, "curve", 5);
2015   if (l1)
2016     {
2017       char *curve;
2018       gcry_mpi_t tmpvalues[N_COMPONENTS];
2019
2020       for (idx = 0; idx < N_COMPONENTS; idx++)
2021         tmpvalues[idx] = NULL;
2022
2023       curve = _gcry_sexp_nth_string (l1, 1);
2024       gcry_sexp_release (l1);
2025       if (!curve)
2026         {
2027           ec = GPG_ERR_INV_OBJ; /* Name missing or out of core. */
2028           goto leave;
2029         }
2030       ec = _gcry_ecc_get_param (curve, tmpvalues);
2031       gcry_free (curve);
2032       if (ec)
2033         goto leave;
2034
2035       for (idx = 0; idx < N_COMPONENTS; idx++)
2036         {
2037           if (!values[idx])
2038             values[idx] = tmpvalues[idx];
2039           else
2040             mpi_free (tmpvalues[idx]);
2041         }
2042     }
2043
2044   /* Check that all parameters are known and normalize all MPIs (that
2045      should not be required but we use an internal function later and
2046      thus we better make 100% sure that they are normalized). */
2047   for (idx = 0; idx < N_COMPONENTS; idx++)
2048     if (!values[idx])
2049       {
2050         ec = GPG_ERR_NO_OBJ;
2051         goto leave;
2052       }
2053     else
2054       _gcry_mpi_normalize (values[idx]);
2055
2056   /* Hash them all.  */
2057   for (idx = 0; idx < N_COMPONENTS; idx++)
2058     {
2059       char buf[30];
2060       unsigned char *rawmpi;
2061       unsigned int rawmpilen;
2062
2063       rawmpi = _gcry_mpi_get_buffer (values[idx], 0, &rawmpilen, NULL);
2064       if (!rawmpi)
2065         {
2066           ec = gpg_err_code_from_syserror ();
2067           goto leave;
2068         }
2069       snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], rawmpilen);
2070       gcry_md_write (md, buf, strlen (buf));
2071       gcry_md_write (md, rawmpi, rawmpilen);
2072       gcry_md_write (md, ")", 1);
2073       gcry_free (rawmpi);
2074     }
2075
2076  leave:
2077   for (idx = 0; idx < N_COMPONENTS; idx++)
2078     _gcry_mpi_release (values[idx]);
2079
2080   return ec;
2081 #undef N_COMPONENTS
2082 }
2083
2084
2085 \f
2086 /*
2087    Low-level API helper functions.
2088  */
2089
2090 /* This is the worker function for gcry_pubkey_get_sexp for ECC
2091    algorithms.  Note that the caller has already stored NULL at
2092    R_SEXP.  */
2093 gpg_err_code_t
2094 _gcry_pk_ecc_get_sexp (gcry_sexp_t *r_sexp, int mode, mpi_ec_t ec)
2095 {
2096   gpg_err_code_t rc;
2097   gcry_mpi_t mpi_G = NULL;
2098   gcry_mpi_t mpi_Q = NULL;
2099
2100   if (!ec->p || !ec->a || !ec->b || !ec->G || !ec->n)
2101     return GPG_ERR_BAD_CRYPT_CTX;
2102
2103   if (mode == GCRY_PK_GET_SECKEY && !ec->d)
2104     return GPG_ERR_NO_SECKEY;
2105
2106   /* Compute the public point if it is missing.  */
2107   if (!ec->Q && ec->d)
2108     ec->Q = _gcry_ecc_compute_public (NULL, ec);
2109
2110   /* Encode G and Q.  */
2111   mpi_G = _gcry_mpi_ec_ec2os (ec->G, ec);
2112   if (!mpi_G)
2113     {
2114       rc = GPG_ERR_BROKEN_PUBKEY;
2115       goto leave;
2116     }
2117   if (!ec->Q)
2118     {
2119       rc = GPG_ERR_BAD_CRYPT_CTX;
2120       goto leave;
2121     }
2122
2123   if (ec->dialect == ECC_DIALECT_ED25519)
2124     {
2125       unsigned char *encpk;
2126       unsigned int encpklen;
2127
2128       rc = _gcry_ecc_eddsa_encodepoint (ec->Q, ec, NULL, NULL,
2129                                         &encpk, &encpklen);
2130       if (rc)
2131         goto leave;
2132       mpi_Q = gcry_mpi_set_opaque (NULL, encpk, encpklen*8);
2133       encpk = NULL;
2134     }
2135   else
2136     {
2137       mpi_Q = _gcry_mpi_ec_ec2os (ec->Q, ec);
2138     }
2139   if (!mpi_Q)
2140     {
2141       rc = GPG_ERR_BROKEN_PUBKEY;
2142       goto leave;
2143     }
2144
2145   /* Fixme: We should return a curve name instead of the parameters if
2146      if know that they match a curve.  */
2147
2148   if (ec->d && (!mode || mode == GCRY_PK_GET_SECKEY))
2149     {
2150       /* Let's return a private key. */
2151       rc = gcry_sexp_build
2152         (r_sexp, NULL,
2153          "(private-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)(q%m)(d%m)))",
2154          ec->p, ec->a, ec->b, mpi_G, ec->n, mpi_Q, ec->d);
2155     }
2156   else if (ec->Q)
2157     {
2158       /* Let's return a public key.  */
2159       rc = gcry_sexp_build
2160         (r_sexp, NULL,
2161          "(public-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)(q%m)))",
2162          ec->p, ec->a, ec->b, mpi_G, ec->n, mpi_Q);
2163     }
2164   else
2165     rc = GPG_ERR_BAD_CRYPT_CTX;
2166
2167  leave:
2168   mpi_free (mpi_Q);
2169   mpi_free (mpi_G);
2170   return rc;
2171 }
2172
2173
2174 \f
2175 /*
2176      Self-test section.
2177  */
2178
2179
2180 static gpg_err_code_t
2181 selftests_ecdsa (selftest_report_func_t report)
2182 {
2183   const char *what;
2184   const char *errtxt;
2185
2186   what = "low-level";
2187   errtxt = NULL; /*selftest ();*/
2188   if (errtxt)
2189     goto failed;
2190
2191   /* FIXME:  need more tests.  */
2192
2193   return 0; /* Succeeded. */
2194
2195  failed:
2196   if (report)
2197     report ("pubkey", GCRY_PK_ECC, what, errtxt);
2198   return GPG_ERR_SELFTEST_FAILED;
2199 }
2200
2201
2202 /* Run a full self-test for ALGO and return 0 on success.  */
2203 static gpg_err_code_t
2204 run_selftests (int algo, int extended, selftest_report_func_t report)
2205 {
2206   (void)extended;
2207
2208   if (algo != GCRY_PK_ECC)
2209     return GPG_ERR_PUBKEY_ALGO;
2210
2211   return selftests_ecdsa (report);
2212 }
2213
2214
2215
2216 \f
2217 gcry_pk_spec_t _gcry_pubkey_spec_ecc =
2218   {
2219     GCRY_PK_ECC, { 0, 0 },
2220     (GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR),
2221     "ECC", ecc_names,
2222     "pabgnq", "pabgnqd", "sw", "rs", "pabgnq",
2223     ecc_generate,
2224     ecc_check_secret_key,
2225     ecc_encrypt_raw,
2226     ecc_decrypt_raw,
2227     ecc_sign,
2228     ecc_verify,
2229     ecc_get_nbits,
2230     run_selftests,
2231     compute_keygrip,
2232     _gcry_ecc_get_param,
2233     _gcry_ecc_get_curve,
2234     _gcry_ecc_get_param_sexp
2235   };