pubkey: Move sexp parsing of remaining fucntions 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 (gcry_sexp_t keyparms)
1401 {
1402   gcry_err_code_t rc;
1403   gcry_sexp_t l1 = NULL;
1404   char *curvename = NULL;
1405   gcry_mpi_t mpi_g = NULL;
1406   gcry_mpi_t mpi_q = NULL;
1407   ECC_secret_key sk;
1408
1409   memset (&sk, 0, sizeof sk);
1410
1411   /*
1412    * Extract the key.
1413    */
1414   rc = _gcry_pk_util_extract_mpis (keyparms, "-p?a?b?g?n?/q?+d",
1415                                    &sk.E.p, &sk.E.a, &sk.E.b, &mpi_g, &sk.E.n,
1416                                    &mpi_q, &sk.d, NULL);
1417   if (rc)
1418     goto leave;
1419   if (mpi_g)
1420     {
1421       point_init (&sk.E.G);
1422       rc = _gcry_ecc_os2ec (&sk.E.G, mpi_g);
1423       if (rc)
1424         goto leave;
1425     }
1426   /* Add missing parameters using the optional curve parameter.  */
1427   gcry_sexp_release (l1);
1428   l1 = gcry_sexp_find_token (keyparms, "curve", 5);
1429   if (l1)
1430     {
1431       curvename = gcry_sexp_nth_string (l1, 1);
1432       if (curvename)
1433         {
1434           rc = _gcry_ecc_fill_in_curve (0, curvename, &sk.E, NULL);
1435           if (rc)
1436             return rc;
1437         }
1438     }
1439   /* Guess required fields if a curve parameter has not been given.
1440      FIXME: This is a crude hacks.  We need to fix that.  */
1441   if (!curvename)
1442     {
1443       sk.E.model = MPI_EC_WEIERSTRASS;
1444       sk.E.dialect = ECC_DIALECT_STANDARD;
1445     }
1446   if (DBG_CIPHER)
1447     {
1448       log_debug ("ecc_testkey inf: %s/%s\n",
1449                  _gcry_ecc_model2str (sk.E.model),
1450                  _gcry_ecc_dialect2str (sk.E.dialect));
1451       if (sk.E.name)
1452         log_debug  ("ecc_testkey nam: %s\n", sk.E.name);
1453       log_printmpi ("ecc_testkey   p", sk.E.p);
1454       log_printmpi ("ecc_testkey   a", sk.E.a);
1455       log_printmpi ("ecc_testkey   b", sk.E.b);
1456       log_printpnt ("ecc_testkey g",   &sk.E.G, NULL);
1457       log_printmpi ("ecc_testkey   n", sk.E.n);
1458       log_printmpi ("ecc_testkey   q", mpi_q);
1459       if (!fips_mode ())
1460         log_printmpi ("ecc_testkey   d", sk.d);
1461     }
1462   if (!sk.E.p || !sk.E.a || !sk.E.b || !sk.E.G.x || !sk.E.n || !sk.d)
1463     {
1464       rc = GPG_ERR_NO_OBJ;
1465       goto leave;
1466     }
1467
1468   if (mpi_q)
1469     {
1470       point_init (&sk.Q);
1471       rc = _gcry_ecc_os2ec (&sk.Q, mpi_q);
1472       if (rc)
1473         goto leave;
1474     }
1475   else
1476     {
1477       /* The current test requires Q.  */
1478       rc = GPG_ERR_NO_OBJ;
1479       goto leave;
1480     }
1481
1482   if (check_secret_key (&sk))
1483     rc = GPG_ERR_BAD_SECKEY;
1484
1485  leave:
1486   gcry_mpi_release (sk.E.p);
1487   gcry_mpi_release (sk.E.a);
1488   gcry_mpi_release (sk.E.b);
1489   gcry_mpi_release (mpi_g);
1490   point_free (&sk.E.G);
1491   gcry_mpi_release (sk.E.n);
1492   gcry_mpi_release (mpi_q);
1493   point_free (&sk.Q);
1494   gcry_mpi_release (sk.d);
1495   gcry_free (curvename);
1496   gcry_sexp_release (l1);
1497   if (DBG_CIPHER)
1498     log_debug ("ecc_testkey   => %s\n", gpg_strerror (rc));
1499   return rc;
1500 }
1501
1502
1503 static gcry_err_code_t
1504 ecc_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1505 {
1506   gcry_err_code_t rc;
1507   struct pk_encoding_ctx ctx;
1508   gcry_mpi_t data = NULL;
1509   gcry_sexp_t l1 = NULL;
1510   char *curvename = NULL;
1511   gcry_mpi_t mpi_g = NULL;
1512   gcry_mpi_t mpi_q = NULL;
1513   ECC_secret_key sk;
1514   gcry_mpi_t sig_r = NULL;
1515   gcry_mpi_t sig_s = NULL;
1516
1517   memset (&sk, 0, sizeof sk);
1518
1519   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_SIGN, 0);
1520
1521   /* Extract the data.  */
1522   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1523   if (rc)
1524     goto leave;
1525   if (DBG_CIPHER)
1526     log_mpidump ("ecc_sign   data", data);
1527
1528   /*
1529    * Extract the key.
1530    */
1531   rc = _gcry_pk_util_extract_mpis (keyparms, "-p?a?b?g?n?/q?+d",
1532                                    &sk.E.p, &sk.E.a, &sk.E.b, &mpi_g, &sk.E.n,
1533                                    &mpi_q, &sk.d, NULL);
1534   if (rc)
1535     goto leave;
1536   if (mpi_g)
1537     {
1538       point_init (&sk.E.G);
1539       rc = _gcry_ecc_os2ec (&sk.E.G, mpi_g);
1540       if (rc)
1541         goto leave;
1542     }
1543   /* Add missing parameters using the optional curve parameter.  */
1544   gcry_sexp_release (l1);
1545   l1 = gcry_sexp_find_token (keyparms, "curve", 5);
1546   if (l1)
1547     {
1548       curvename = gcry_sexp_nth_string (l1, 1);
1549       if (curvename)
1550         {
1551           rc = _gcry_ecc_fill_in_curve (0, curvename, &sk.E, NULL);
1552           if (rc)
1553             return rc;
1554         }
1555     }
1556   /* Guess required fields if a curve parameter has not been given.
1557      FIXME: This is a crude hacks.  We need to fix that.  */
1558   if (!curvename)
1559     {
1560       sk.E.model = ((ctx.flags & PUBKEY_FLAG_EDDSA)
1561                     ? MPI_EC_TWISTEDEDWARDS
1562                     : MPI_EC_WEIERSTRASS);
1563       sk.E.dialect = ((ctx.flags & PUBKEY_FLAG_EDDSA)
1564                       ? ECC_DIALECT_ED25519
1565                       : ECC_DIALECT_STANDARD);
1566     }
1567   if (DBG_CIPHER)
1568     {
1569       log_debug ("ecc_sign   info: %s/%s\n",
1570                  _gcry_ecc_model2str (sk.E.model),
1571                  _gcry_ecc_dialect2str (sk.E.dialect));
1572       if (sk.E.name)
1573         log_debug  ("ecc_sign   name: %s\n", sk.E.name);
1574       log_printmpi ("ecc_sign      p", sk.E.p);
1575       log_printmpi ("ecc_sign      a", sk.E.a);
1576       log_printmpi ("ecc_sign      b", sk.E.b);
1577       log_printpnt ("ecc_sign    g",   &sk.E.G, NULL);
1578       log_printmpi ("ecc_sign      n", sk.E.n);
1579       log_printmpi ("ecc_sign      q", mpi_q);
1580       if (!fips_mode ())
1581         log_printmpi ("ecc_sign      d", sk.d);
1582     }
1583   if (!sk.E.p || !sk.E.a || !sk.E.b || !sk.E.G.x || !sk.E.n || !sk.d)
1584     {
1585       rc = GPG_ERR_NO_OBJ;
1586       goto leave;
1587     }
1588
1589
1590   sig_r = gcry_mpi_new (0);
1591   sig_s = gcry_mpi_new (0);
1592   if ((ctx.flags & PUBKEY_FLAG_EDDSA))
1593     {
1594       /* EdDSA requires the public key.  */
1595       rc = sign_eddsa (data, &sk, sig_r, sig_s, ctx.hash_algo, mpi_q);
1596       if (!rc)
1597         rc = gcry_sexp_build (r_sig, NULL,
1598                               "(sig-val(eddsa(r%M)(s%M)))", sig_r, sig_s);
1599     }
1600   else
1601     {
1602       rc = sign_ecdsa (data, &sk, sig_r, sig_s, ctx.flags, ctx.hash_algo);
1603       if (!rc)
1604         rc = gcry_sexp_build (r_sig, NULL,
1605                               "(sig-val(ecdsa(r%M)(s%M)))", sig_r, sig_s);
1606     }
1607
1608
1609  leave:
1610   gcry_mpi_release (sk.E.p);
1611   gcry_mpi_release (sk.E.a);
1612   gcry_mpi_release (sk.E.b);
1613   gcry_mpi_release (mpi_g);
1614   point_free (&sk.E.G);
1615   gcry_mpi_release (sk.E.n);
1616   gcry_mpi_release (mpi_q);
1617   point_free (&sk.Q);
1618   gcry_mpi_release (sk.d);
1619   gcry_mpi_release (sig_r);
1620   gcry_mpi_release (sig_s);
1621   gcry_free (curvename);
1622   gcry_mpi_release (data);
1623   gcry_sexp_release (l1);
1624   _gcry_pk_util_free_encoding_ctx (&ctx);
1625   if (DBG_CIPHER)
1626     log_debug ("ecc_sign      => %s\n", gpg_strerror (rc));
1627   return rc;
1628 }
1629
1630
1631 static gcry_err_code_t
1632 ecc_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t s_keyparms)
1633 {
1634   gcry_err_code_t rc;
1635   struct pk_encoding_ctx ctx;
1636   gcry_sexp_t l1 = NULL;
1637   char *curvename = NULL;
1638   gcry_mpi_t mpi_g = NULL;
1639   gcry_mpi_t mpi_q = NULL;
1640   gcry_mpi_t sig_r = NULL;
1641   gcry_mpi_t sig_s = NULL;
1642   gcry_mpi_t data = NULL;
1643   ECC_public_key pk;
1644   int sigflags;
1645
1646   memset (&pk, 0, sizeof pk);
1647   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY,
1648                                    ecc_get_nbits (s_keyparms));
1649
1650   /* Extract the data.  */
1651   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1652   if (rc)
1653     goto leave;
1654   if (DBG_CIPHER)
1655     log_mpidump ("ecc_verify data", data);
1656
1657   /*
1658    * Extract the signature value.
1659    */
1660   rc = _gcry_pk_util_preparse_sigval (s_sig, ecc_names, &l1, &sigflags);
1661   if (rc)
1662     goto leave;
1663   rc = _gcry_pk_util_extract_mpis (l1,
1664                                    (sigflags & PUBKEY_FLAG_EDDSA)? "/rs":"rs",
1665                                    &sig_r, &sig_s, NULL);
1666   if (rc)
1667     goto leave;
1668   if (DBG_CIPHER)
1669     {
1670       log_mpidump ("ecc_verify  s_r", sig_r);
1671       log_mpidump ("ecc_verify  s_s", sig_s);
1672     }
1673   if ((ctx.flags & PUBKEY_FLAG_EDDSA) ^ (sigflags & PUBKEY_FLAG_EDDSA))
1674     {
1675       rc = GPG_ERR_CONFLICT; /* Inconsistent use of flag/algoname.  */
1676       goto leave;
1677     }
1678
1679
1680   /*
1681    * Extract the key.
1682    */
1683   rc = _gcry_pk_util_extract_mpis (s_keyparms, "-p?a?b?g?n?/q?",
1684                                    &pk.E.p, &pk.E.a, &pk.E.b, &mpi_g, &pk.E.n,
1685                                    &mpi_q, NULL);
1686   if (rc)
1687     goto leave;
1688   if (mpi_g)
1689     {
1690       point_init (&pk.E.G);
1691       rc = _gcry_ecc_os2ec (&pk.E.G, mpi_g);
1692       if (rc)
1693         goto leave;
1694     }
1695   /* Add missing parameters using the optional curve parameter.  */
1696   gcry_sexp_release (l1);
1697   l1 = gcry_sexp_find_token (s_keyparms, "curve", 5);
1698   if (l1)
1699     {
1700       curvename = gcry_sexp_nth_string (l1, 1);
1701       if (curvename)
1702         {
1703           rc = _gcry_ecc_fill_in_curve (0, curvename, &pk.E, NULL);
1704           if (rc)
1705             return rc;
1706         }
1707     }
1708   /* Guess required fields if a curve parameter has not been given.
1709      FIXME: This is a crude hacks.  We need to fix that.  */
1710   if (!curvename)
1711     {
1712       pk.E.model = ((sigflags & PUBKEY_FLAG_EDDSA)
1713                     ? MPI_EC_TWISTEDEDWARDS
1714                     : MPI_EC_WEIERSTRASS);
1715       pk.E.dialect = ((sigflags & PUBKEY_FLAG_EDDSA)
1716                       ? ECC_DIALECT_ED25519
1717                       : ECC_DIALECT_STANDARD);
1718     }
1719
1720   if (DBG_CIPHER)
1721     {
1722       log_debug ("ecc_verify info: %s/%s\n",
1723                  _gcry_ecc_model2str (pk.E.model),
1724                  _gcry_ecc_dialect2str (pk.E.dialect));
1725       if (pk.E.name)
1726         log_debug  ("ecc_verify name: %s\n", pk.E.name);
1727       log_printmpi ("ecc_verify    p", pk.E.p);
1728       log_printmpi ("ecc_verify    a", pk.E.a);
1729       log_printmpi ("ecc_verify    b", pk.E.b);
1730       log_printpnt ("ecc_verify  g",   &pk.E.G, NULL);
1731       log_printmpi ("ecc_verify    n", pk.E.n);
1732       log_printmpi ("ecc_verify    q", mpi_q);
1733     }
1734   if (!pk.E.p || !pk.E.a || !pk.E.b || !pk.E.G.x || !pk.E.n || !mpi_q)
1735     {
1736       rc = GPG_ERR_NO_OBJ;
1737       goto leave;
1738     }
1739
1740
1741   /*
1742    * Verify the signature.
1743    */
1744   if ((sigflags & PUBKEY_FLAG_EDDSA))
1745     {
1746       rc = verify_eddsa (data, &pk, sig_r, sig_s, ctx.hash_algo, mpi_q);
1747     }
1748   else
1749     {
1750       point_init (&pk.Q);
1751       rc = _gcry_ecc_os2ec (&pk.Q, mpi_q);
1752       if (rc)
1753         goto leave;
1754
1755       if (mpi_is_opaque (data))
1756         {
1757           const void *abuf;
1758           unsigned int abits, qbits;
1759           gcry_mpi_t a;
1760
1761           qbits = mpi_get_nbits (pk.E.n);
1762
1763           abuf = gcry_mpi_get_opaque (data, &abits);
1764           rc = gpg_err_code (gcry_mpi_scan (&a, GCRYMPI_FMT_USG,
1765                                             abuf, (abits+7)/8, NULL));
1766           if (!rc)
1767             {
1768               if (abits > qbits)
1769                 gcry_mpi_rshift (a, a, abits - qbits);
1770
1771               rc = verify_ecdsa (a, &pk, sig_r, sig_s);
1772               gcry_mpi_release (a);
1773             }
1774         }
1775       else
1776         rc = verify_ecdsa (data, &pk, sig_r, sig_s);
1777     }
1778
1779  leave:
1780   gcry_mpi_release (pk.E.p);
1781   gcry_mpi_release (pk.E.a);
1782   gcry_mpi_release (pk.E.b);
1783   gcry_mpi_release (mpi_g);
1784   point_free (&pk.E.G);
1785   gcry_mpi_release (pk.E.n);
1786   gcry_mpi_release (mpi_q);
1787   point_free (&pk.Q);
1788   gcry_mpi_release (data);
1789   gcry_mpi_release (sig_r);
1790   gcry_mpi_release (sig_s);
1791   gcry_free (curvename);
1792   gcry_sexp_release (l1);
1793   _gcry_pk_util_free_encoding_ctx (&ctx);
1794   if (DBG_CIPHER)
1795     log_debug ("ecc_verify    => %s\n", rc?gpg_strerror (rc):"Good");
1796   return rc;
1797 }
1798
1799
1800 /* ecdh raw is classic 2-round DH protocol published in 1976.
1801  *
1802  * Overview of ecc_encrypt_raw and ecc_decrypt_raw.
1803  *
1804  * As with any PK operation, encrypt version uses a public key and
1805  * decrypt -- private.
1806  *
1807  * Symbols used below:
1808  *     G - field generator point
1809  *     d - private long-term scalar
1810  *    dG - public long-term key
1811  *     k - ephemeral scalar
1812  *    kG - ephemeral public key
1813  *   dkG - shared secret
1814  *
1815  * ecc_encrypt_raw description:
1816  *   input:
1817  *     data[0] : private scalar (k)
1818  *   output: A new S-expression with the parameters:
1819  *     s : shared point (kdG)
1820  *     e : generated ephemeral public key (kG)
1821  *
1822  * ecc_decrypt_raw description:
1823  *   input:
1824  *     data[0] : a point kG (ephemeral public key)
1825  *   output:
1826  *     result[0] : shared point (kdG)
1827  */
1828 static gcry_err_code_t
1829 ecc_encrypt_raw (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1830 {
1831   gcry_err_code_t rc;
1832   struct pk_encoding_ctx ctx;
1833   gcry_sexp_t l1 = NULL;
1834   char *curvename = NULL;
1835   gcry_mpi_t mpi_g = NULL;
1836   gcry_mpi_t mpi_q = NULL;
1837   gcry_mpi_t mpi_s = NULL;
1838   gcry_mpi_t mpi_e = NULL;
1839   gcry_mpi_t data = NULL;
1840   ECC_public_key pk;
1841   mpi_ec_t ec = NULL;
1842
1843   memset (&pk, 0, sizeof pk);
1844   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_ENCRYPT,
1845                                    ecc_get_nbits (keyparms));
1846
1847   /*
1848    * Extract the data.
1849    */
1850   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1851   if (rc)
1852     goto leave;
1853   if (DBG_CIPHER)
1854     log_mpidump ("ecc_encrypt data", data);
1855   if (mpi_is_opaque (data))
1856     {
1857       rc = GPG_ERR_INV_DATA;
1858       goto leave;
1859     }
1860
1861
1862   /*
1863    * Extract the key.
1864    */
1865   rc = _gcry_pk_util_extract_mpis (keyparms, "-p?a?b?g?n?+q",
1866                                    &pk.E.p, &pk.E.a, &pk.E.b, &mpi_g, &pk.E.n,
1867                                    &mpi_q, NULL);
1868   if (rc)
1869     goto leave;
1870   if (mpi_g)
1871     {
1872       point_init (&pk.E.G);
1873       rc = _gcry_ecc_os2ec (&pk.E.G, mpi_g);
1874       if (rc)
1875         goto leave;
1876     }
1877   /* Add missing parameters using the optional curve parameter.  */
1878   gcry_sexp_release (l1);
1879   l1 = gcry_sexp_find_token (keyparms, "curve", 5);
1880   if (l1)
1881     {
1882       curvename = gcry_sexp_nth_string (l1, 1);
1883       if (curvename)
1884         {
1885           rc = _gcry_ecc_fill_in_curve (0, curvename, &pk.E, NULL);
1886           if (rc)
1887             return rc;
1888         }
1889     }
1890   /* Guess required fields if a curve parameter has not been given.  */
1891   if (!curvename)
1892     {
1893       pk.E.model = MPI_EC_WEIERSTRASS;
1894       pk.E.dialect = ECC_DIALECT_STANDARD;
1895     }
1896
1897   if (DBG_CIPHER)
1898     {
1899       log_debug ("ecc_encrypt info: %s/%s\n",
1900                  _gcry_ecc_model2str (pk.E.model),
1901                  _gcry_ecc_dialect2str (pk.E.dialect));
1902       if (pk.E.name)
1903         log_debug  ("ecc_encrypt name: %s\n", pk.E.name);
1904       log_printmpi ("ecc_encrypt    p", pk.E.p);
1905       log_printmpi ("ecc_encrypt    a", pk.E.a);
1906       log_printmpi ("ecc_encrypt    b", pk.E.b);
1907       log_printpnt ("ecc_encrypt  g",   &pk.E.G, NULL);
1908       log_printmpi ("ecc_encrypt    n", pk.E.n);
1909       log_printmpi ("ecc_encrypt    q", mpi_q);
1910     }
1911   if (!pk.E.p || !pk.E.a || !pk.E.b || !pk.E.G.x || !pk.E.n || !mpi_q)
1912     {
1913       rc = GPG_ERR_NO_OBJ;
1914       goto leave;
1915     }
1916
1917   /* Convert the public key.  */
1918   if (mpi_q)
1919     {
1920       point_init (&pk.Q);
1921       rc = _gcry_ecc_os2ec (&pk.Q, mpi_q);
1922       if (rc)
1923         goto leave;
1924     }
1925
1926   /* Compute the encrypted value.  */
1927   ec = _gcry_mpi_ec_p_internal_new (pk.E.model, pk.E.dialect,
1928                                     pk.E.p, pk.E.a, pk.E.b);
1929
1930   /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so */
1931   {
1932     mpi_point_struct R;  /* Result that we return.  */
1933     gcry_mpi_t x, y;
1934
1935     x = mpi_new (0);
1936     y = mpi_new (0);
1937
1938     point_init (&R);
1939
1940     /* R = kQ  <=>  R = kdG  */
1941     _gcry_mpi_ec_mul_point (&R, data, &pk.Q, ec);
1942
1943     if (_gcry_mpi_ec_get_affine (x, y, &R, ec))
1944       log_fatal ("ecdh: Failed to get affine coordinates for kdG\n");
1945     mpi_s = _gcry_ecc_ec2os (x, y, pk.E.p);
1946
1947     /* R = kG */
1948     _gcry_mpi_ec_mul_point (&R, data, &pk.E.G, ec);
1949
1950     if (_gcry_mpi_ec_get_affine (x, y, &R, ec))
1951       log_fatal ("ecdh: Failed to get affine coordinates for kG\n");
1952     mpi_e = _gcry_ecc_ec2os (x, y, pk.E.p);
1953
1954     mpi_free (x);
1955     mpi_free (y);
1956
1957     point_free (&R);
1958   }
1959
1960   rc = gcry_sexp_build (r_ciph, NULL, "(enc-val(ecdh(s%m)(e%m)))",
1961                         mpi_s, mpi_e);
1962
1963  leave:
1964   gcry_mpi_release (pk.E.p);
1965   gcry_mpi_release (pk.E.a);
1966   gcry_mpi_release (pk.E.b);
1967   gcry_mpi_release (mpi_g);
1968   point_free (&pk.E.G);
1969   gcry_mpi_release (pk.E.n);
1970   gcry_mpi_release (mpi_q);
1971   point_free (&pk.Q);
1972   gcry_mpi_release (data);
1973   gcry_mpi_release (mpi_s);
1974   gcry_mpi_release (mpi_e);
1975   gcry_free (curvename);
1976   _gcry_mpi_ec_free (ec);
1977   _gcry_pk_util_free_encoding_ctx (&ctx);
1978   if (DBG_CIPHER)
1979     log_debug ("ecc_encrypt    => %s\n", gpg_strerror (rc));
1980   return rc;
1981 }
1982
1983
1984 /*  input:
1985  *     data[0] : a point kG (ephemeral public key)
1986  *   output:
1987  *     resaddr[0] : shared point kdG
1988  *
1989  *  see ecc_encrypt_raw for details.
1990  */
1991 static gcry_err_code_t
1992 ecc_decrypt_raw (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1993 {
1994   gpg_err_code_t rc;
1995   struct pk_encoding_ctx ctx;
1996   gcry_sexp_t l1 = NULL;
1997   gcry_mpi_t data_e = NULL;
1998   ECC_secret_key sk;
1999   gcry_mpi_t mpi_g = NULL;
2000   char *curvename = NULL;
2001   mpi_ec_t ec = NULL;
2002   mpi_point_struct kG;
2003   mpi_point_struct R;
2004   gcry_mpi_t r = NULL;
2005
2006   memset (&sk, 0, sizeof sk);
2007   point_init (&kG);
2008   point_init (&R);
2009
2010   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_DECRYPT,
2011                                    ecc_get_nbits (keyparms));
2012
2013   /*
2014    * Extract the data.
2015    */
2016   rc = _gcry_pk_util_preparse_encval (s_data, ecc_names, &l1, &ctx);
2017   if (rc)
2018     goto leave;
2019   rc = _gcry_pk_util_extract_mpis (l1, "e", &data_e, NULL);
2020   if (rc)
2021     goto leave;
2022   if (DBG_CIPHER)
2023     log_printmpi ("ecc_decrypt  d_e", data_e);
2024   if (mpi_is_opaque (data_e))
2025     {
2026       rc = GPG_ERR_INV_DATA;
2027       goto leave;
2028     }
2029
2030   /*
2031    * Extract the key.
2032    */
2033   rc = _gcry_pk_util_extract_mpis (keyparms, "-p?a?b?g?n?+d",
2034                                    &sk.E.p, &sk.E.a, &sk.E.b, &mpi_g, &sk.E.n,
2035                                    &sk.d, NULL);
2036   if (rc)
2037     goto leave;
2038   if (mpi_g)
2039     {
2040       point_init (&sk.E.G);
2041       rc = _gcry_ecc_os2ec (&sk.E.G, mpi_g);
2042       if (rc)
2043         goto leave;
2044     }
2045   /* Add missing parameters using the optional curve parameter.  */
2046   gcry_sexp_release (l1);
2047   l1 = gcry_sexp_find_token (keyparms, "curve", 5);
2048   if (l1)
2049     {
2050       curvename = gcry_sexp_nth_string (l1, 1);
2051       if (curvename)
2052         {
2053           rc = _gcry_ecc_fill_in_curve (0, curvename, &sk.E, NULL);
2054           if (rc)
2055             return rc;
2056         }
2057     }
2058   /* Guess required fields if a curve parameter has not been given.  */
2059   if (!curvename)
2060     {
2061       sk.E.model = MPI_EC_WEIERSTRASS;
2062       sk.E.dialect = ECC_DIALECT_STANDARD;
2063     }
2064   if (DBG_CIPHER)
2065     {
2066       log_debug ("ecc_decrypt info: %s/%s\n",
2067                  _gcry_ecc_model2str (sk.E.model),
2068                  _gcry_ecc_dialect2str (sk.E.dialect));
2069       if (sk.E.name)
2070         log_debug  ("ecc_decrypt name: %s\n", sk.E.name);
2071       log_printmpi ("ecc_decrypt    p", sk.E.p);
2072       log_printmpi ("ecc_decrypt    a", sk.E.a);
2073       log_printmpi ("ecc_decrypt    b", sk.E.b);
2074       log_printpnt ("ecc_decrypt  g",   &sk.E.G, NULL);
2075       log_printmpi ("ecc_decrypt    n", sk.E.n);
2076       if (!fips_mode ())
2077         log_printmpi ("ecc_decrypt    d", sk.d);
2078     }
2079   if (!sk.E.p || !sk.E.a || !sk.E.b || !sk.E.G.x || !sk.E.n || !sk.d)
2080     {
2081       rc = GPG_ERR_NO_OBJ;
2082       goto leave;
2083     }
2084
2085
2086   /*
2087    * Compute the plaintext.
2088    */
2089   rc = _gcry_ecc_os2ec (&kG, data_e);
2090   if (rc)
2091     {
2092       point_free (&kG);
2093       return rc;
2094     }
2095
2096   ec = _gcry_mpi_ec_p_internal_new (sk.E.model, sk.E.dialect,
2097                                     sk.E.p, sk.E.a, sk.E.b);
2098
2099   /* R = dkG */
2100   _gcry_mpi_ec_mul_point (&R, sk.d, &kG, ec);
2101
2102   /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so:  */
2103   {
2104     gcry_mpi_t x, y;
2105
2106     x = mpi_new (0);
2107     y = mpi_new (0);
2108
2109     if (_gcry_mpi_ec_get_affine (x, y, &R, ec))
2110       log_fatal ("ecdh: Failed to get affine coordinates\n");
2111
2112     r = _gcry_ecc_ec2os (x, y, sk.E.p);
2113     if (!r)
2114       rc = gpg_err_code_from_syserror ();
2115     else
2116       rc = 0;
2117     mpi_free (x);
2118     mpi_free (y);
2119   }
2120   if (DBG_CIPHER)
2121     log_printmpi ("ecc_decrypt  res", r);
2122
2123   if (!rc)
2124     rc = gcry_sexp_build (r_plain, NULL, "(value %m)", r);
2125
2126  leave:
2127   point_free (&R);
2128   point_free (&kG);
2129   gcry_mpi_release (r);
2130   gcry_mpi_release (sk.E.p);
2131   gcry_mpi_release (sk.E.a);
2132   gcry_mpi_release (sk.E.b);
2133   gcry_mpi_release (mpi_g);
2134   point_free (&sk.E.G);
2135   gcry_mpi_release (sk.E.n);
2136   gcry_mpi_release (sk.d);
2137   gcry_mpi_release (data_e);
2138   gcry_free (curvename);
2139   gcry_sexp_release (l1);
2140   _gcry_mpi_ec_free (ec);
2141   _gcry_pk_util_free_encoding_ctx (&ctx);
2142   if (DBG_CIPHER)
2143     log_debug ("ecc_decrypt    => %s\n", gpg_strerror (rc));
2144   return rc;
2145 }
2146
2147
2148 /* Return the number of bits for the key described by PARMS.  On error
2149  * 0 is returned.  The format of PARMS starts with the algorithm name;
2150  * for example:
2151  *
2152  *   (ecc
2153  *     (p <mpi>)
2154  *     (a <mpi>)
2155  *     (b <mpi>)
2156  *     (g <mpi>)
2157  *     (n <mpi>)
2158  *     (q <mpi>))
2159  *
2160  * More parameters may be given currently P is needed.  FIXME: We
2161  * need allow for a "curve" parameter.
2162  */
2163 static unsigned int
2164 ecc_get_nbits (gcry_sexp_t parms)
2165 {
2166   gcry_sexp_t l1;
2167   gcry_mpi_t p;
2168   unsigned int nbits = 0;
2169   char *curve;
2170
2171   l1 = gcry_sexp_find_token (parms, "p", 1);
2172   if (!l1)
2173     { /* Parameter P not found - check whether we have "curve".  */
2174       l1 = gcry_sexp_find_token (parms, "curve", 5);
2175       if (!l1)
2176         return 0; /* Neither P nor CURVE found.  */
2177
2178       curve = _gcry_sexp_nth_string (l1, 1);
2179       gcry_sexp_release (l1);
2180       if (!curve)
2181         return 0;  /* No curve name given (or out of core). */
2182
2183       if (_gcry_ecc_fill_in_curve (0, curve, NULL, &nbits))
2184         nbits = 0;
2185       gcry_free (curve);
2186     }
2187   else
2188     {
2189       p = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
2190       gcry_sexp_release (l1);
2191       if (p)
2192         {
2193           nbits = mpi_get_nbits (p);
2194           gcry_mpi_release (p);
2195         }
2196     }
2197   return nbits;
2198 }
2199
2200
2201 /* See rsa.c for a description of this function.  */
2202 static gpg_err_code_t
2203 compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
2204 {
2205 #define N_COMPONENTS 6
2206   static const char names[N_COMPONENTS+1] = "pabgnq";
2207   gpg_err_code_t ec = 0;
2208   gcry_sexp_t l1;
2209   gcry_mpi_t values[N_COMPONENTS];
2210   int idx;
2211
2212   /* Clear the values for easier error cleanup.  */
2213   for (idx=0; idx < N_COMPONENTS; idx++)
2214     values[idx] = NULL;
2215
2216   /* Fill values with all provided parameters.  */
2217   for (idx=0; idx < N_COMPONENTS; idx++)
2218     {
2219       l1 = gcry_sexp_find_token (keyparam, names+idx, 1);
2220       if (l1)
2221         {
2222           values[idx] = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
2223           gcry_sexp_release (l1);
2224           if (!values[idx])
2225             {
2226               ec = GPG_ERR_INV_OBJ;
2227               goto leave;
2228             }
2229         }
2230     }
2231
2232   /* Check whether a curve parameter is available and use that to fill
2233      in missing values.  */
2234   l1 = gcry_sexp_find_token (keyparam, "curve", 5);
2235   if (l1)
2236     {
2237       char *curve;
2238       gcry_mpi_t tmpvalues[N_COMPONENTS];
2239
2240       for (idx = 0; idx < N_COMPONENTS; idx++)
2241         tmpvalues[idx] = NULL;
2242
2243       curve = _gcry_sexp_nth_string (l1, 1);
2244       gcry_sexp_release (l1);
2245       if (!curve)
2246         {
2247           ec = GPG_ERR_INV_OBJ; /* Name missing or out of core. */
2248           goto leave;
2249         }
2250       ec = _gcry_ecc_get_param (curve, tmpvalues);
2251       gcry_free (curve);
2252       if (ec)
2253         goto leave;
2254
2255       for (idx = 0; idx < N_COMPONENTS; idx++)
2256         {
2257           if (!values[idx])
2258             values[idx] = tmpvalues[idx];
2259           else
2260             mpi_free (tmpvalues[idx]);
2261         }
2262     }
2263
2264   /* Check that all parameters are known and normalize all MPIs (that
2265      should not be required but we use an internal function later and
2266      thus we better make 100% sure that they are normalized). */
2267   for (idx = 0; idx < N_COMPONENTS; idx++)
2268     if (!values[idx])
2269       {
2270         ec = GPG_ERR_NO_OBJ;
2271         goto leave;
2272       }
2273     else
2274       _gcry_mpi_normalize (values[idx]);
2275
2276   /* Hash them all.  */
2277   for (idx = 0; idx < N_COMPONENTS; idx++)
2278     {
2279       char buf[30];
2280       unsigned char *rawmpi;
2281       unsigned int rawmpilen;
2282
2283       rawmpi = _gcry_mpi_get_buffer (values[idx], 0, &rawmpilen, NULL);
2284       if (!rawmpi)
2285         {
2286           ec = gpg_err_code_from_syserror ();
2287           goto leave;
2288         }
2289       snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], rawmpilen);
2290       gcry_md_write (md, buf, strlen (buf));
2291       gcry_md_write (md, rawmpi, rawmpilen);
2292       gcry_md_write (md, ")", 1);
2293       gcry_free (rawmpi);
2294     }
2295
2296  leave:
2297   for (idx = 0; idx < N_COMPONENTS; idx++)
2298     _gcry_mpi_release (values[idx]);
2299
2300   return ec;
2301 #undef N_COMPONENTS
2302 }
2303
2304
2305 \f
2306 /*
2307    Low-level API helper functions.
2308  */
2309
2310 /* This is the worker function for gcry_pubkey_get_sexp for ECC
2311    algorithms.  Note that the caller has already stored NULL at
2312    R_SEXP.  */
2313 gpg_err_code_t
2314 _gcry_pk_ecc_get_sexp (gcry_sexp_t *r_sexp, int mode, mpi_ec_t ec)
2315 {
2316   gpg_err_code_t rc;
2317   gcry_mpi_t mpi_G = NULL;
2318   gcry_mpi_t mpi_Q = NULL;
2319
2320   if (!ec->p || !ec->a || !ec->b || !ec->G || !ec->n)
2321     return GPG_ERR_BAD_CRYPT_CTX;
2322
2323   if (mode == GCRY_PK_GET_SECKEY && !ec->d)
2324     return GPG_ERR_NO_SECKEY;
2325
2326   /* Compute the public point if it is missing.  */
2327   if (!ec->Q && ec->d)
2328     ec->Q = _gcry_ecc_compute_public (NULL, ec);
2329
2330   /* Encode G and Q.  */
2331   mpi_G = _gcry_mpi_ec_ec2os (ec->G, ec);
2332   if (!mpi_G)
2333     {
2334       rc = GPG_ERR_BROKEN_PUBKEY;
2335       goto leave;
2336     }
2337   if (!ec->Q)
2338     {
2339       rc = GPG_ERR_BAD_CRYPT_CTX;
2340       goto leave;
2341     }
2342
2343   if (ec->dialect == ECC_DIALECT_ED25519)
2344     {
2345       unsigned char *encpk;
2346       unsigned int encpklen;
2347
2348       rc = _gcry_ecc_eddsa_encodepoint (ec->Q, ec, NULL, NULL,
2349                                         &encpk, &encpklen);
2350       if (rc)
2351         goto leave;
2352       mpi_Q = gcry_mpi_set_opaque (NULL, encpk, encpklen*8);
2353       encpk = NULL;
2354     }
2355   else
2356     {
2357       mpi_Q = _gcry_mpi_ec_ec2os (ec->Q, ec);
2358     }
2359   if (!mpi_Q)
2360     {
2361       rc = GPG_ERR_BROKEN_PUBKEY;
2362       goto leave;
2363     }
2364
2365   /* Fixme: We should return a curve name instead of the parameters if
2366      if know that they match a curve.  */
2367
2368   if (ec->d && (!mode || mode == GCRY_PK_GET_SECKEY))
2369     {
2370       /* Let's return a private key. */
2371       rc = gcry_sexp_build
2372         (r_sexp, NULL,
2373          "(private-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)(q%m)(d%m)))",
2374          ec->p, ec->a, ec->b, mpi_G, ec->n, mpi_Q, ec->d);
2375     }
2376   else if (ec->Q)
2377     {
2378       /* Let's return a public key.  */
2379       rc = gcry_sexp_build
2380         (r_sexp, NULL,
2381          "(public-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)(q%m)))",
2382          ec->p, ec->a, ec->b, mpi_G, ec->n, mpi_Q);
2383     }
2384   else
2385     rc = GPG_ERR_BAD_CRYPT_CTX;
2386
2387  leave:
2388   mpi_free (mpi_Q);
2389   mpi_free (mpi_G);
2390   return rc;
2391 }
2392
2393
2394 \f
2395 /*
2396      Self-test section.
2397  */
2398
2399
2400 static gpg_err_code_t
2401 selftests_ecdsa (selftest_report_func_t report)
2402 {
2403   const char *what;
2404   const char *errtxt;
2405
2406   what = "low-level";
2407   errtxt = NULL; /*selftest ();*/
2408   if (errtxt)
2409     goto failed;
2410
2411   /* FIXME:  need more tests.  */
2412
2413   return 0; /* Succeeded. */
2414
2415  failed:
2416   if (report)
2417     report ("pubkey", GCRY_PK_ECC, what, errtxt);
2418   return GPG_ERR_SELFTEST_FAILED;
2419 }
2420
2421
2422 /* Run a full self-test for ALGO and return 0 on success.  */
2423 static gpg_err_code_t
2424 run_selftests (int algo, int extended, selftest_report_func_t report)
2425 {
2426   (void)extended;
2427
2428   if (algo != GCRY_PK_ECC)
2429     return GPG_ERR_PUBKEY_ALGO;
2430
2431   return selftests_ecdsa (report);
2432 }
2433
2434
2435
2436 \f
2437 gcry_pk_spec_t _gcry_pubkey_spec_ecc =
2438   {
2439     GCRY_PK_ECC, { 0, 0 },
2440     (GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR),
2441     "ECC", ecc_names,
2442     "pabgnq", "pabgnqd", "sw", "rs", "pabgnq",
2443     ecc_generate,
2444     ecc_check_secret_key,
2445     ecc_encrypt_raw,
2446     ecc_decrypt_raw,
2447     ecc_sign,
2448     ecc_verify,
2449     ecc_get_nbits,
2450     run_selftests,
2451     compute_keygrip,
2452     _gcry_ecc_get_param,
2453     _gcry_ecc_get_curve,
2454     _gcry_ecc_get_param_sexp
2455   };