pubkey: Move sexp parsing for gcry_pk_encrypt 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 (int algo, gcry_sexp_t *r_plain, gcry_mpi_t *data,
1953                  gcry_mpi_t *skey, int flags,
1954                  enum pk_encoding encoding, int hash_algo,
1955                  unsigned char *label, size_t labellen)
1956 {
1957   gpg_err_code_t rc;
1958   ECC_secret_key sk;
1959   mpi_point_struct R;   /* Result that we return.  */
1960   mpi_point_struct kG;
1961   mpi_ec_t ctx;
1962   gcry_mpi_t r;
1963
1964   (void)algo;
1965   (void)flags;
1966   (void)encoding;
1967   (void)hash_algo;
1968   (void)label;
1969   (void)labellen;
1970
1971   if (!data || !data[0]
1972       || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4]
1973       || !skey[5] || !skey[6] )
1974     return GPG_ERR_BAD_MPI;
1975
1976   point_init (&kG);
1977   rc = _gcry_ecc_os2ec (&kG, data[0]);
1978   if (rc)
1979     {
1980       point_free (&kG);
1981       return rc;
1982     }
1983
1984   sk.E.model = MPI_EC_WEIERSTRASS;
1985   sk.E.p = skey[0];
1986   sk.E.a = skey[1];
1987   sk.E.b = skey[2];
1988   point_init (&sk.E.G);
1989   rc = _gcry_ecc_os2ec (&sk.E.G, skey[3]);
1990   if (rc)
1991     {
1992       point_free (&kG);
1993       point_free (&sk.E.G);
1994       return rc;
1995     }
1996   sk.E.n = skey[4];
1997   point_init (&sk.Q);
1998   rc = _gcry_ecc_os2ec (&sk.Q, skey[5]);
1999   if (rc)
2000     {
2001       point_free (&kG);
2002       point_free (&sk.E.G);
2003       point_free (&sk.Q);
2004       return rc;
2005     }
2006   sk.d = skey[6];
2007
2008   ctx = _gcry_mpi_ec_p_internal_new (sk.E.model, sk.E.dialect,
2009                                      sk.E.p, sk.E.a, sk.E.b);
2010
2011   /* R = dkG */
2012   point_init (&R);
2013   _gcry_mpi_ec_mul_point (&R, sk.d, &kG, ctx);
2014
2015   point_free (&kG);
2016
2017   /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so:  */
2018   {
2019     gcry_mpi_t x, y;
2020
2021     x = mpi_new (0);
2022     y = mpi_new (0);
2023
2024     if (_gcry_mpi_ec_get_affine (x, y, &R, ctx))
2025       log_fatal ("ecdh: Failed to get affine coordinates\n");
2026
2027     r = _gcry_ecc_ec2os (x, y, sk.E.p);
2028     if (!r)
2029       rc = gpg_err_code_from_syserror ();
2030     else
2031       rc = 0;
2032     mpi_free (x);
2033     mpi_free (y);
2034   }
2035
2036   point_free (&R);
2037   _gcry_mpi_ec_free (ctx);
2038   point_free (&kG);
2039   point_free (&sk.E.G);
2040   point_free (&sk.Q);
2041
2042   if (!rc)
2043     rc = gcry_sexp_build (r_plain, NULL, "(value %m)", r);
2044   mpi_free (r);
2045   return rc;
2046 }
2047
2048
2049 /* Return the number of bits for the key described by PARMS.  On error
2050  * 0 is returned.  The format of PARMS starts with the algorithm name;
2051  * for example:
2052  *
2053  *   (ecc
2054  *     (p <mpi>)
2055  *     (a <mpi>)
2056  *     (b <mpi>)
2057  *     (g <mpi>)
2058  *     (n <mpi>)
2059  *     (q <mpi>))
2060  *
2061  * More parameters may be given currently P is needed.  FIXME: We
2062  * need allow for a "curve" parameter.
2063  */
2064 static unsigned int
2065 ecc_get_nbits (gcry_sexp_t parms)
2066 {
2067   gcry_sexp_t l1;
2068   gcry_mpi_t p;
2069   unsigned int nbits = 0;
2070   char *curve;
2071
2072   l1 = gcry_sexp_find_token (parms, "p", 1);
2073   if (!l1)
2074     { /* Parameter P not found - check whether we have "curve".  */
2075       l1 = gcry_sexp_find_token (parms, "curve", 5);
2076       if (!l1)
2077         return 0; /* Neither P nor CURVE found.  */
2078
2079       curve = _gcry_sexp_nth_string (l1, 1);
2080       gcry_sexp_release (l1);
2081       if (!curve)
2082         return 0;  /* No curve name given (or out of core). */
2083
2084       if (_gcry_ecc_fill_in_curve (0, curve, NULL, &nbits))
2085         nbits = 0;
2086       gcry_free (curve);
2087     }
2088   else
2089     {
2090       p = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
2091       gcry_sexp_release (l1);
2092       if (p)
2093         {
2094           nbits = mpi_get_nbits (p);
2095           gcry_mpi_release (p);
2096         }
2097     }
2098   return nbits;
2099 }
2100
2101
2102 /* See rsa.c for a description of this function.  */
2103 static gpg_err_code_t
2104 compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
2105 {
2106 #define N_COMPONENTS 6
2107   static const char names[N_COMPONENTS+1] = "pabgnq";
2108   gpg_err_code_t ec = 0;
2109   gcry_sexp_t l1;
2110   gcry_mpi_t values[N_COMPONENTS];
2111   int idx;
2112
2113   /* Clear the values for easier error cleanup.  */
2114   for (idx=0; idx < N_COMPONENTS; idx++)
2115     values[idx] = NULL;
2116
2117   /* Fill values with all provided parameters.  */
2118   for (idx=0; idx < N_COMPONENTS; idx++)
2119     {
2120       l1 = gcry_sexp_find_token (keyparam, names+idx, 1);
2121       if (l1)
2122         {
2123           values[idx] = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
2124           gcry_sexp_release (l1);
2125           if (!values[idx])
2126             {
2127               ec = GPG_ERR_INV_OBJ;
2128               goto leave;
2129             }
2130         }
2131     }
2132
2133   /* Check whether a curve parameter is available and use that to fill
2134      in missing values.  */
2135   l1 = gcry_sexp_find_token (keyparam, "curve", 5);
2136   if (l1)
2137     {
2138       char *curve;
2139       gcry_mpi_t tmpvalues[N_COMPONENTS];
2140
2141       for (idx = 0; idx < N_COMPONENTS; idx++)
2142         tmpvalues[idx] = NULL;
2143
2144       curve = _gcry_sexp_nth_string (l1, 1);
2145       gcry_sexp_release (l1);
2146       if (!curve)
2147         {
2148           ec = GPG_ERR_INV_OBJ; /* Name missing or out of core. */
2149           goto leave;
2150         }
2151       ec = _gcry_ecc_get_param (curve, tmpvalues);
2152       gcry_free (curve);
2153       if (ec)
2154         goto leave;
2155
2156       for (idx = 0; idx < N_COMPONENTS; idx++)
2157         {
2158           if (!values[idx])
2159             values[idx] = tmpvalues[idx];
2160           else
2161             mpi_free (tmpvalues[idx]);
2162         }
2163     }
2164
2165   /* Check that all parameters are known and normalize all MPIs (that
2166      should not be required but we use an internal function later and
2167      thus we better make 100% sure that they are normalized). */
2168   for (idx = 0; idx < N_COMPONENTS; idx++)
2169     if (!values[idx])
2170       {
2171         ec = GPG_ERR_NO_OBJ;
2172         goto leave;
2173       }
2174     else
2175       _gcry_mpi_normalize (values[idx]);
2176
2177   /* Hash them all.  */
2178   for (idx = 0; idx < N_COMPONENTS; idx++)
2179     {
2180       char buf[30];
2181       unsigned char *rawmpi;
2182       unsigned int rawmpilen;
2183
2184       rawmpi = _gcry_mpi_get_buffer (values[idx], 0, &rawmpilen, NULL);
2185       if (!rawmpi)
2186         {
2187           ec = gpg_err_code_from_syserror ();
2188           goto leave;
2189         }
2190       snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], rawmpilen);
2191       gcry_md_write (md, buf, strlen (buf));
2192       gcry_md_write (md, rawmpi, rawmpilen);
2193       gcry_md_write (md, ")", 1);
2194       gcry_free (rawmpi);
2195     }
2196
2197  leave:
2198   for (idx = 0; idx < N_COMPONENTS; idx++)
2199     _gcry_mpi_release (values[idx]);
2200
2201   return ec;
2202 #undef N_COMPONENTS
2203 }
2204
2205
2206 \f
2207 /*
2208    Low-level API helper functions.
2209  */
2210
2211 /* This is the worker function for gcry_pubkey_get_sexp for ECC
2212    algorithms.  Note that the caller has already stored NULL at
2213    R_SEXP.  */
2214 gpg_err_code_t
2215 _gcry_pk_ecc_get_sexp (gcry_sexp_t *r_sexp, int mode, mpi_ec_t ec)
2216 {
2217   gpg_err_code_t rc;
2218   gcry_mpi_t mpi_G = NULL;
2219   gcry_mpi_t mpi_Q = NULL;
2220
2221   if (!ec->p || !ec->a || !ec->b || !ec->G || !ec->n)
2222     return GPG_ERR_BAD_CRYPT_CTX;
2223
2224   if (mode == GCRY_PK_GET_SECKEY && !ec->d)
2225     return GPG_ERR_NO_SECKEY;
2226
2227   /* Compute the public point if it is missing.  */
2228   if (!ec->Q && ec->d)
2229     ec->Q = _gcry_ecc_compute_public (NULL, ec);
2230
2231   /* Encode G and Q.  */
2232   mpi_G = _gcry_mpi_ec_ec2os (ec->G, ec);
2233   if (!mpi_G)
2234     {
2235       rc = GPG_ERR_BROKEN_PUBKEY;
2236       goto leave;
2237     }
2238   if (!ec->Q)
2239     {
2240       rc = GPG_ERR_BAD_CRYPT_CTX;
2241       goto leave;
2242     }
2243
2244   if (ec->dialect == ECC_DIALECT_ED25519)
2245     {
2246       unsigned char *encpk;
2247       unsigned int encpklen;
2248
2249       rc = _gcry_ecc_eddsa_encodepoint (ec->Q, ec, NULL, NULL,
2250                                         &encpk, &encpklen);
2251       if (rc)
2252         goto leave;
2253       mpi_Q = gcry_mpi_set_opaque (NULL, encpk, encpklen*8);
2254       encpk = NULL;
2255     }
2256   else
2257     {
2258       mpi_Q = _gcry_mpi_ec_ec2os (ec->Q, ec);
2259     }
2260   if (!mpi_Q)
2261     {
2262       rc = GPG_ERR_BROKEN_PUBKEY;
2263       goto leave;
2264     }
2265
2266   /* Fixme: We should return a curve name instead of the parameters if
2267      if know that they match a curve.  */
2268
2269   if (ec->d && (!mode || mode == GCRY_PK_GET_SECKEY))
2270     {
2271       /* Let's return a private key. */
2272       rc = gcry_sexp_build
2273         (r_sexp, NULL,
2274          "(private-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)(q%m)(d%m)))",
2275          ec->p, ec->a, ec->b, mpi_G, ec->n, mpi_Q, ec->d);
2276     }
2277   else if (ec->Q)
2278     {
2279       /* Let's return a public key.  */
2280       rc = gcry_sexp_build
2281         (r_sexp, NULL,
2282          "(public-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)(q%m)))",
2283          ec->p, ec->a, ec->b, mpi_G, ec->n, mpi_Q);
2284     }
2285   else
2286     rc = GPG_ERR_BAD_CRYPT_CTX;
2287
2288  leave:
2289   mpi_free (mpi_Q);
2290   mpi_free (mpi_G);
2291   return rc;
2292 }
2293
2294
2295 \f
2296 /*
2297      Self-test section.
2298  */
2299
2300
2301 static gpg_err_code_t
2302 selftests_ecdsa (selftest_report_func_t report)
2303 {
2304   const char *what;
2305   const char *errtxt;
2306
2307   what = "low-level";
2308   errtxt = NULL; /*selftest ();*/
2309   if (errtxt)
2310     goto failed;
2311
2312   /* FIXME:  need more tests.  */
2313
2314   return 0; /* Succeeded. */
2315
2316  failed:
2317   if (report)
2318     report ("pubkey", GCRY_PK_ECC, what, errtxt);
2319   return GPG_ERR_SELFTEST_FAILED;
2320 }
2321
2322
2323 /* Run a full self-test for ALGO and return 0 on success.  */
2324 static gpg_err_code_t
2325 run_selftests (int algo, int extended, selftest_report_func_t report)
2326 {
2327   (void)extended;
2328
2329   if (algo != GCRY_PK_ECC)
2330     return GPG_ERR_PUBKEY_ALGO;
2331
2332   return selftests_ecdsa (report);
2333 }
2334
2335
2336
2337 \f
2338 gcry_pk_spec_t _gcry_pubkey_spec_ecc =
2339   {
2340     GCRY_PK_ECC, { 0, 0 },
2341     (GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR),
2342     "ECC", ecc_names,
2343     "pabgnq", "pabgnqd", "sw", "rs", "pabgnq",
2344     ecc_generate,
2345     ecc_check_secret_key,
2346     ecc_encrypt_raw,
2347     ecc_decrypt_raw,
2348     ecc_sign,
2349     ecc_verify,
2350     ecc_get_nbits,
2351     run_selftests,
2352     compute_keygrip,
2353     _gcry_ecc_get_param,
2354     _gcry_ecc_get_curve,
2355     _gcry_ecc_get_param_sexp
2356   };