7d468ee54af8df3d6618eca82869f7448626bf40
[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 /* Registered progress function and its callback value. */
69 static void (*progress_cb) (void *, const char*, int, int, int);
70 static void *progress_cb_data;
71
72
73 #define point_init(a)  _gcry_mpi_point_init ((a))
74 #define point_free(a)  _gcry_mpi_point_free_parts ((a))
75
76 \f
77 /* Local prototypes. */
78 static void test_keys (ECC_secret_key * sk, unsigned int nbits);
79 static int check_secret_key (ECC_secret_key * sk);
80 static gpg_err_code_t sign_ecdsa (gcry_mpi_t input, ECC_secret_key *skey,
81                                   gcry_mpi_t r, gcry_mpi_t s,
82                                   int flags, int hashalgo);
83 static gpg_err_code_t verify_ecdsa (gcry_mpi_t input, ECC_public_key *pkey,
84                                     gcry_mpi_t r, gcry_mpi_t s);
85
86 static gcry_mpi_t gen_y_2 (gcry_mpi_t x, elliptic_curve_t * base);
87
88
89
90 \f
91 void
92 _gcry_register_pk_ecc_progress (void (*cb) (void *, const char *,
93                                             int, int, int),
94                                 void *cb_data)
95 {
96   progress_cb = cb;
97   progress_cb_data = cb_data;
98 }
99
100 /* static void */
101 /* progress (int c) */
102 /* { */
103 /*   if (progress_cb) */
104 /*     progress_cb (progress_cb_data, "pk_ecc", c, 0, 0); */
105 /* } */
106
107
108 \f
109
110 /*
111  * Solve the right side of the Weierstrass equation.
112  */
113 static gcry_mpi_t
114 gen_y_2 (gcry_mpi_t x, elliptic_curve_t *base)
115 {
116   gcry_mpi_t three, x_3, axb, y;
117
118   three = mpi_alloc_set_ui (3);
119   x_3 = mpi_new (0);
120   axb = mpi_new (0);
121   y   = mpi_new (0);
122
123   mpi_powm (x_3, x, three, base->p);
124   mpi_mulm (axb, base->a, x, base->p);
125   mpi_addm (axb, axb, base->b, base->p);
126   mpi_addm (y, x_3, axb, base->p);
127
128   mpi_free (x_3);
129   mpi_free (axb);
130   mpi_free (three);
131   return y; /* The quadratic value of the coordinate if it exist. */
132 }
133
134
135 /*
136  * First obtain the setup.  Over the finite field randomize an scalar
137  * secret value, and calculate the public point.
138  */
139 static gpg_err_code_t
140 generate_key (ECC_secret_key *sk, unsigned int nbits, const char *name,
141               int transient_key,
142               gcry_mpi_t g_x, gcry_mpi_t g_y,
143               gcry_mpi_t q_x, gcry_mpi_t q_y,
144               const char **r_usedcurve)
145 {
146   gpg_err_code_t err;
147   elliptic_curve_t E;
148   mpi_point_struct Q;
149   mpi_ec_t ctx;
150   gcry_random_level_t random_level;
151
152   *r_usedcurve = NULL;
153
154   err = _gcry_ecc_fill_in_curve (nbits, name, &E, &nbits);
155   if (err)
156     return err;
157
158   if (DBG_CIPHER)
159     {
160       log_debug ("ecgen curve model: %s\n", _gcry_ecc_model2str (E.model));
161       log_mpidump ("ecgen curve  p", E.p);
162       log_mpidump ("ecgen curve  a", E.a);
163       log_mpidump ("ecgen curve  b", E.b);
164       log_mpidump ("ecgen curve  n", E.n);
165       log_mpidump ("ecgen curve Gx", E.G.x);
166       log_mpidump ("ecgen curve Gy", E.G.y);
167       log_mpidump ("ecgen curve Gz", E.G.z);
168       if (E.name)
169         log_debug ("ecgen curve used: %s\n", E.name);
170     }
171
172   random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
173   sk->d = _gcry_dsa_gen_k (E.n, random_level);
174
175   /* Compute Q.  */
176   point_init (&Q);
177   ctx = _gcry_mpi_ec_p_internal_new (E.model, E.p, E.a, E.b);
178   _gcry_mpi_ec_mul_point (&Q, sk->d, &E.G, ctx);
179
180   /* Copy the stuff to the key structures. */
181   sk->E.model = E.model;
182   sk->E.p = mpi_copy (E.p);
183   sk->E.a = mpi_copy (E.a);
184   sk->E.b = mpi_copy (E.b);
185   point_init (&sk->E.G);
186   point_set (&sk->E.G, &E.G);
187   sk->E.n = mpi_copy (E.n);
188   point_init (&sk->Q);
189
190   /* We want the Q=(x,y) be a "compliant key" in terms of the
191    * http://tools.ietf.org/html/draft-jivsov-ecc-compact, which simply
192    * means that we choose either Q=(x,y) or -Q=(x,p-y) such that we
193    * end up with the min(y,p-y) as the y coordinate.  Such a public
194    * key allows the most efficient compression: y can simply be
195    * dropped because we know that it's a minimum of the two
196    * possibilities without any loss of security.  */
197   {
198     gcry_mpi_t x, y, p_y;
199     const unsigned int pbits = mpi_get_nbits (E.p);
200
201     x = mpi_new (pbits);
202     y = mpi_new (pbits);
203     p_y = mpi_new (pbits);
204
205     if (_gcry_mpi_ec_get_affine (x, y, &Q, ctx))
206       log_fatal ("ecgen: Failed to get affine coordinates for %s\n", "Q");
207
208     mpi_sub (p_y, E.p, y);      /* p_y = p - y */
209
210     if (mpi_cmp (p_y, y) < 0)   /* p - y < p */
211       {
212         /* We need to end up with -Q; this assures that new Q's y is
213            the smallest one */
214         mpi_sub (sk->d, E.n, sk->d);   /* d = order - d */
215         gcry_mpi_point_snatch_set (&sk->Q, x, p_y, mpi_alloc_set_ui (1));
216
217         if (DBG_CIPHER)
218           log_debug ("ecgen converted Q to a compliant point\n");
219       }
220     else /* p - y >= p */
221       {
222         /* No change is needed exactly 50% of the time: just copy. */
223         point_set (&sk->Q, &Q);
224         if (DBG_CIPHER)
225           log_debug ("ecgen didn't need to convert Q to a compliant point\n");
226
227         mpi_free (p_y);
228         mpi_free (x);
229       }
230     mpi_free (y);
231   }
232
233   /* We also return copies of G and Q in affine coordinates if
234      requested.  */
235   if (g_x && g_y)
236     {
237       if (_gcry_mpi_ec_get_affine (g_x, g_y, &sk->E.G, ctx))
238         log_fatal ("ecgen: Failed to get affine coordinates for %s\n", "G");
239     }
240   if (q_x && q_y)
241     {
242       if (_gcry_mpi_ec_get_affine (q_x, q_y, &sk->Q, ctx))
243         log_fatal ("ecgen: Failed to get affine coordinates for %s\n", "Q");
244     }
245   _gcry_mpi_ec_free (ctx);
246
247   point_free (&Q);
248
249   *r_usedcurve = E.name;
250   _gcry_ecc_curve_free (&E);
251
252   /* Now we can test our keys (this should never fail!).  */
253   test_keys (sk, nbits - 64);
254
255   return 0;
256 }
257
258
259 /*
260  * To verify correct skey it use a random information.
261  * First, encrypt and decrypt this dummy value,
262  * test if the information is recuperated.
263  * Second, test with the sign and verify functions.
264  */
265 static void
266 test_keys (ECC_secret_key *sk, unsigned int nbits)
267 {
268   ECC_public_key pk;
269   gcry_mpi_t test = mpi_new (nbits);
270   mpi_point_struct R_;
271   gcry_mpi_t c = mpi_new (nbits);
272   gcry_mpi_t out = mpi_new (nbits);
273   gcry_mpi_t r = mpi_new (nbits);
274   gcry_mpi_t s = mpi_new (nbits);
275
276   if (DBG_CIPHER)
277     log_debug ("Testing key.\n");
278
279   point_init (&R_);
280
281   pk.E = _gcry_ecc_curve_copy (sk->E);
282   point_init (&pk.Q);
283   point_set (&pk.Q, &sk->Q);
284
285   gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM);
286
287   if (sign_ecdsa (test, sk, r, s, 0, 0) )
288     log_fatal ("ECDSA operation: sign failed\n");
289
290   if (verify_ecdsa (test, &pk, r, s))
291     {
292       log_fatal ("ECDSA operation: sign, verify failed\n");
293     }
294
295   if (DBG_CIPHER)
296     log_debug ("ECDSA operation: sign, verify ok.\n");
297
298   point_free (&pk.Q);
299   _gcry_ecc_curve_free (&pk.E);
300
301   point_free (&R_);
302   mpi_free (s);
303   mpi_free (r);
304   mpi_free (out);
305   mpi_free (c);
306   mpi_free (test);
307 }
308
309
310 /*
311  * To check the validity of the value, recalculate the correspondence
312  * between the public value and the secret one.
313  */
314 static int
315 check_secret_key (ECC_secret_key * sk)
316 {
317   int rc = 1;
318   mpi_point_struct Q;
319   gcry_mpi_t y_2, y2;
320   gcry_mpi_t x1, x2;
321   mpi_ec_t ctx = NULL;
322
323   point_init (&Q);
324
325   /* ?primarity test of 'p' */
326   /*  (...) //!! */
327   /* G in E(F_p) */
328   y_2 = gen_y_2 (sk->E.G.x, &sk->E);   /*  y^2=x^3+a*x+b */
329   y2 = mpi_alloc (0);
330   x1 = mpi_alloc (0);
331   x2 = mpi_alloc (0);
332   mpi_mulm (y2, sk->E.G.y, sk->E.G.y, sk->E.p);      /*  y^2=y*y */
333   if (mpi_cmp (y_2, y2))
334     {
335       if (DBG_CIPHER)
336         log_debug ("Bad check: Point 'G' does not belong to curve 'E'!\n");
337       goto leave;
338     }
339   /* G != PaI */
340   if (!mpi_cmp_ui (sk->E.G.z, 0))
341     {
342       if (DBG_CIPHER)
343         log_debug ("Bad check: 'G' cannot be Point at Infinity!\n");
344       goto leave;
345     }
346
347   ctx = _gcry_mpi_ec_p_internal_new (sk->E.model, sk->E.p, sk->E.a, sk->E.b);
348
349   _gcry_mpi_ec_mul_point (&Q, sk->E.n, &sk->E.G, ctx);
350   if (mpi_cmp_ui (Q.z, 0))
351     {
352       if (DBG_CIPHER)
353         log_debug ("check_secret_key: E is not a curve of order n\n");
354       goto leave;
355     }
356   /* pubkey cannot be PaI */
357   if (!mpi_cmp_ui (sk->Q.z, 0))
358     {
359       if (DBG_CIPHER)
360         log_debug ("Bad check: Q can not be a Point at Infinity!\n");
361       goto leave;
362     }
363   /* pubkey = [d]G over E */
364   _gcry_mpi_ec_mul_point (&Q, sk->d, &sk->E.G, ctx);
365
366   if (_gcry_mpi_ec_get_affine (x1, y_2, &Q, ctx))
367     {
368       if (DBG_CIPHER)
369         log_debug ("Bad check: Q can not be a Point at Infinity!\n");
370       goto leave;
371     }
372
373   /* Fast path for loaded secret keys - Q is already in affine coordinates */
374   if (!mpi_cmp_ui (sk->Q.z, 1))
375     {
376       if (mpi_cmp (x1, sk->Q.x) || mpi_cmp (y_2, sk->Q.y))
377         {
378           if (DBG_CIPHER)
379             log_debug
380               ("Bad check: There is NO correspondence between 'd' and 'Q'!\n");
381           goto leave;
382         }
383     }
384   else
385     {
386       if (_gcry_mpi_ec_get_affine (x2, y2, &sk->Q, ctx))
387         {
388           if (DBG_CIPHER)
389             log_debug ("Bad check: Q can not be a Point at Infinity!\n");
390           goto leave;
391         }
392
393       if (mpi_cmp (x1, x2) || mpi_cmp (y_2, y2))
394         {
395           if (DBG_CIPHER)
396             log_debug
397               ("Bad check: There is NO correspondence between 'd' and 'Q'!\n");
398           goto leave;
399         }
400     }
401   rc = 0; /* Okay.  */
402
403  leave:
404   _gcry_mpi_ec_free (ctx);
405   mpi_free (x2);
406   mpi_free (x1);
407   mpi_free (y2);
408   mpi_free (y_2);
409   point_free (&Q);
410   return rc;
411 }
412
413
414 /* Compute an ECDSA signature.
415  * Return the signature struct (r,s) from the message hash.  The caller
416  * must have allocated R and S.
417  */
418 static gpg_err_code_t
419 sign_ecdsa (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s,
420             int flags, int hashalgo)
421 {
422   gpg_err_code_t err = 0;
423   int extraloops = 0;
424   gcry_mpi_t k, dr, sum, k_1, x;
425   mpi_point_struct I;
426   gcry_mpi_t hash;
427   const void *abuf;
428   unsigned int abits, qbits;
429   mpi_ec_t ctx;
430
431   if (DBG_CIPHER)
432     log_mpidump ("ecdsa sign hash  ", input );
433
434   qbits = mpi_get_nbits (skey->E.n);
435
436   /* Convert the INPUT into an MPI if needed.  */
437   if (mpi_is_opaque (input))
438     {
439       abuf = gcry_mpi_get_opaque (input, &abits);
440       err = gpg_err_code (gcry_mpi_scan (&hash, GCRYMPI_FMT_USG,
441                                          abuf, (abits+7)/8, NULL));
442       if (err)
443         return err;
444       if (abits > qbits)
445         gcry_mpi_rshift (hash, hash, abits - qbits);
446     }
447   else
448     hash = input;
449
450
451   k = NULL;
452   dr = mpi_alloc (0);
453   sum = mpi_alloc (0);
454   k_1 = mpi_alloc (0);
455   x = mpi_alloc (0);
456   point_init (&I);
457
458   mpi_set_ui (s, 0);
459   mpi_set_ui (r, 0);
460
461   ctx = _gcry_mpi_ec_p_internal_new (skey->E.model,
462                                      skey->E.p, skey->E.a, skey->E.b);
463
464   while (!mpi_cmp_ui (s, 0)) /* s == 0 */
465     {
466       while (!mpi_cmp_ui (r, 0)) /* r == 0 */
467         {
468           /* Note, that we are guaranteed to enter this loop at least
469              once because r has been intialized to 0.  We can't use a
470              do_while because we want to keep the value of R even if S
471              has to be recomputed.  */
472
473           mpi_free (k);
474           k = NULL;
475           if ((flags & PUBKEY_FLAG_RFC6979) && hashalgo)
476             {
477               /* Use Pornin's method for deterministic DSA.  If this
478                  flag is set, it is expected that HASH is an opaque
479                  MPI with the to be signed hash.  That hash is also
480                  used as h1 from 3.2.a.  */
481               if (!mpi_is_opaque (input))
482                 {
483                   err = GPG_ERR_CONFLICT;
484                   goto leave;
485                 }
486
487               abuf = gcry_mpi_get_opaque (input, &abits);
488               err = _gcry_dsa_gen_rfc6979_k (&k, skey->E.n, skey->d,
489                                              abuf, (abits+7)/8,
490                                              hashalgo, extraloops);
491               if (err)
492                 goto leave;
493               extraloops++;
494             }
495           else
496             k = _gcry_dsa_gen_k (skey->E.n, GCRY_STRONG_RANDOM);
497
498           _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx);
499           if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx))
500             {
501               if (DBG_CIPHER)
502                 log_debug ("ecc sign: Failed to get affine coordinates\n");
503               err = GPG_ERR_BAD_SIGNATURE;
504               goto leave;
505             }
506           mpi_mod (r, x, skey->E.n);  /* r = x mod n */
507         }
508       mpi_mulm (dr, skey->d, r, skey->E.n); /* dr = d*r mod n  */
509       mpi_addm (sum, hash, dr, skey->E.n);  /* sum = hash + (d*r) mod n  */
510       mpi_invm (k_1, k, skey->E.n);         /* k_1 = k^(-1) mod n  */
511       mpi_mulm (s, k_1, sum, skey->E.n);    /* s = k^(-1)*(hash+(d*r)) mod n */
512     }
513
514   if (DBG_CIPHER)
515     {
516       log_mpidump ("ecdsa sign result r ", r);
517       log_mpidump ("ecdsa sign result s ", s);
518     }
519
520  leave:
521   _gcry_mpi_ec_free (ctx);
522   point_free (&I);
523   mpi_free (x);
524   mpi_free (k_1);
525   mpi_free (sum);
526   mpi_free (dr);
527   mpi_free (k);
528
529   if (hash != input)
530     mpi_free (hash);
531
532   return err;
533 }
534
535
536 /* Verify an ECDSA signature.
537  * Check if R and S verifies INPUT.
538  */
539 static gpg_err_code_t
540 verify_ecdsa (gcry_mpi_t input, ECC_public_key *pkey,
541               gcry_mpi_t r, gcry_mpi_t s)
542 {
543   gpg_err_code_t err = 0;
544   gcry_mpi_t h, h1, h2, x;
545   mpi_point_struct Q, Q1, Q2;
546   mpi_ec_t ctx;
547
548   if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) )
549     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < r < n  failed.  */
550   if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) )
551     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < s < n  failed.  */
552
553   h  = mpi_alloc (0);
554   h1 = mpi_alloc (0);
555   h2 = mpi_alloc (0);
556   x = mpi_alloc (0);
557   point_init (&Q);
558   point_init (&Q1);
559   point_init (&Q2);
560
561   ctx = _gcry_mpi_ec_p_internal_new (pkey->E.model,
562                                      pkey->E.p, pkey->E.a, pkey->E.b);
563
564   /* h  = s^(-1) (mod n) */
565   mpi_invm (h, s, pkey->E.n);
566   /* h1 = hash * s^(-1) (mod n) */
567   mpi_mulm (h1, input, h, pkey->E.n);
568   /* Q1 = [ hash * s^(-1) ]G  */
569   _gcry_mpi_ec_mul_point (&Q1, h1, &pkey->E.G, ctx);
570   /* h2 = r * s^(-1) (mod n) */
571   mpi_mulm (h2, r, h, pkey->E.n);
572   /* Q2 = [ r * s^(-1) ]Q */
573   _gcry_mpi_ec_mul_point (&Q2, h2, &pkey->Q, ctx);
574   /* Q  = ([hash * s^(-1)]G) + ([r * s^(-1)]Q) */
575   _gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ctx);
576
577   if (!mpi_cmp_ui (Q.z, 0))
578     {
579       if (DBG_CIPHER)
580           log_debug ("ecc verify: Rejected\n");
581       err = GPG_ERR_BAD_SIGNATURE;
582       goto leave;
583     }
584   if (_gcry_mpi_ec_get_affine (x, NULL, &Q, ctx))
585     {
586       if (DBG_CIPHER)
587         log_debug ("ecc verify: Failed to get affine coordinates\n");
588       err = GPG_ERR_BAD_SIGNATURE;
589       goto leave;
590     }
591   mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */
592   if (mpi_cmp (x, r))   /* x != r */
593     {
594       if (DBG_CIPHER)
595         {
596           log_mpidump ("     x", x);
597           log_mpidump ("     r", r);
598           log_mpidump ("     s", s);
599           log_debug ("ecc verify: Not verified\n");
600         }
601       err = GPG_ERR_BAD_SIGNATURE;
602       goto leave;
603     }
604   if (DBG_CIPHER)
605     log_debug ("ecc verify: Accepted\n");
606
607  leave:
608   _gcry_mpi_ec_free (ctx);
609   point_free (&Q2);
610   point_free (&Q1);
611   point_free (&Q);
612   mpi_free (x);
613   mpi_free (h2);
614   mpi_free (h1);
615   mpi_free (h);
616   return err;
617 }
618
619
620 \f
621 static void
622 reverse_buffer (unsigned char *buffer, unsigned int length)
623 {
624   unsigned int tmp, i;
625
626   for (i=0; i < length/2; i++)
627     {
628       tmp = buffer[i];
629       buffer[i] = buffer[length-1-i];
630       buffer[length-1-i] = tmp;
631     }
632 }
633
634
635 /* Encode MPI using the EdDSA scheme.  MINLEN specifies the required
636    length of the buffer in bytes.  On success 0 is returned an a
637    malloced buffer with the encoded point is stored at R_BUFFER; the
638    length of this buffer is stored at R_BUFLEN.  */
639 static gpg_err_code_t
640 eddsa_encodempi (gcry_mpi_t mpi, unsigned int minlen,
641                  unsigned char **r_buffer, unsigned int *r_buflen)
642 {
643   unsigned char *rawmpi;
644   unsigned int rawmpilen;
645
646   rawmpi = _gcry_mpi_get_buffer (mpi, minlen, &rawmpilen, NULL);
647   if (!rawmpi)
648     return gpg_err_code_from_syserror ();
649
650   *r_buffer = rawmpi;
651   *r_buflen = rawmpilen;
652   return 0;
653 }
654
655
656 /* Encode POINT using the EdDSA scheme.  X and Y are scratch variables
657    supplied by the caller and CTX is the usual context.  MINLEN is the
658    required length in bytes for the result. On success 0 is returned
659    an a malloced buffer with the encoded point is stored at R_BUFFER;
660    the length of this buffer is stored at R_BUFLEN.  */
661 static gpg_err_code_t
662 eddsa_encodepoint (mpi_point_t point, unsigned int minlen, mpi_ec_t ctx,
663                    gcry_mpi_t x, gcry_mpi_t y,
664                    unsigned char **r_buffer, unsigned int *r_buflen)
665 {
666   unsigned char *rawmpi;
667   unsigned int rawmpilen;
668
669   if (_gcry_mpi_ec_get_affine (x, y, point, ctx))
670     {
671       log_error ("eddsa_encodepoint: Failed to get affine coordinates\n");
672       return GPG_ERR_INTERNAL;
673     }
674   rawmpi = _gcry_mpi_get_buffer (y, minlen, &rawmpilen, NULL);
675   if (!rawmpi)
676     return gpg_err_code_from_syserror ();
677   if (mpi_test_bit (x, 0) && rawmpilen)
678     rawmpi[rawmpilen - 1] |= 0x80;  /* Set sign bit.  */
679
680   *r_buffer = rawmpi;
681   *r_buflen = rawmpilen;
682   return 0;
683 }
684
685
686 /* Decode the EdDSA style encoded PK and set it into RESULT.  LEN is
687    the expected length in bytes of the encoded key and CTX the usual
688    curve context.  If R_ENCPK is not NULL, the encoded PK is stored at
689    that address; this is a new copy to be release by the caller.  In
690    contrast to the supplied PK, this is not an MPI and thus guarnteed
691    to be properly padded.  R_ENCPKLEN received the length of that
692    encoded key.  */
693 static gpg_err_code_t
694 eddsa_decodepoint (gcry_mpi_t pk, unsigned int len, mpi_ec_t ctx,
695                    mpi_point_t result,
696                    unsigned char **r_encpk, unsigned int *r_encpklen)
697 {
698   unsigned char *rawmpi;
699   unsigned int rawmpilen;
700   gcry_mpi_t yy, t, x, p1, p2, p3;
701   int sign;
702
703   rawmpi = _gcry_mpi_get_buffer (pk, len, &rawmpilen, NULL);
704   if (!rawmpi)
705     return gpg_err_code_from_syserror ();
706   if (rawmpilen)
707     {
708       sign = !!(rawmpi[0] & 0x80);
709       rawmpi[0] &= 0x7f;
710     }
711   else
712     sign = 0;
713   _gcry_mpi_set_buffer (result->y, rawmpi, rawmpilen, 0);
714   if (r_encpk)
715     {
716       /* Revert to little endian.  */
717       if (sign && rawmpilen)
718         rawmpi[0] |= 0x80;
719       reverse_buffer (rawmpi, rawmpilen);
720       *r_encpk = rawmpi;
721       if (r_encpklen)
722         *r_encpklen = rawmpilen;
723     }
724   else
725     gcry_free (rawmpi);
726
727   /* Now recover X.  */
728   /* t = (y^2-1) · ((b*y^2+1)^{p-2} mod p) */
729   x = mpi_new (0);
730   yy = mpi_new (0);
731   mpi_mul (yy, result->y, result->y);
732   t = mpi_copy (yy);
733   mpi_mul (t, t, ctx->b);
734   mpi_add_ui (t, t, 1);
735   p2 = mpi_copy (ctx->p);
736   mpi_sub_ui (p2, p2, 2);
737   mpi_powm (t, t, p2, ctx->p);
738
739   mpi_sub_ui (yy, yy, 1);
740   mpi_mul (t, yy, t);
741
742   /* x = t^{(p+3)/8} mod p */
743   p3 = mpi_copy (ctx->p);
744   mpi_add_ui (p3, p3, 3);
745   mpi_fdiv_q (p3, p3, mpi_const (MPI_C_EIGHT));
746   mpi_powm (x, t, p3, ctx->p);
747
748   /* (x^2 - t) % p != 0 ? x = (x*(2^{(p-1)/4} mod p)) % p */
749   mpi_mul (yy, x, x);
750   mpi_subm (yy, yy, t, ctx->p);
751   if (mpi_cmp_ui (yy, 0))
752     {
753       p1 = mpi_copy (ctx->p);
754       mpi_sub_ui (p1, p1, 1);
755       mpi_fdiv_q (p1, p1, mpi_const (MPI_C_FOUR));
756       mpi_powm (yy, mpi_const (MPI_C_TWO), p1, ctx->p);
757       mpi_mulm (x, x, yy, ctx->p);
758     }
759   else
760     p1 = NULL;
761
762   /* is_odd(x) ? x = p-x */
763   if (mpi_test_bit (x, 0))
764     mpi_sub (x, ctx->p, x);
765
766   /* lowbit(x) != highbit(input) ?  x = p-x */
767   if (mpi_test_bit (x, 0) != sign)
768     mpi_sub (x, ctx->p, x);
769
770   mpi_set (result->x, x);
771   mpi_set_ui (result->z, 1);
772
773   gcry_mpi_release (x);
774   gcry_mpi_release (yy);
775   gcry_mpi_release (t);
776   gcry_mpi_release (p3);
777   gcry_mpi_release (p2);
778   gcry_mpi_release (p1);
779
780   return 0;
781 }
782
783
784 /* Compute an EdDSA signature. See:
785  *   [ed25519] 23pp. (PDF) Daniel J. Bernstein, Niels Duif, Tanja
786  *   Lange, Peter Schwabe, Bo-Yin Yang. High-speed high-security
787  *   signatures.  Journal of Cryptographic Engineering 2 (2012), 77-89.
788  *   Document ID: a1a62a2f76d23f65d622484ddd09caf8.
789  *   URL: http://cr.yp.to/papers.html#ed25519. Date: 2011.09.26.
790  *
791  * Despite that this function requires the specification of a hash
792  * algorithm, we only support what has been specified by the paper.
793  * This may change in the future.  Note that we don't check the used
794  * curve; the user is responsible to use Ed25519.
795  *
796  * Return the signature struct (r,s) from the message hash.  The caller
797  * must have allocated R_R and S.
798  */
799 static gpg_err_code_t
800 sign_eddsa (gcry_mpi_t input, ECC_secret_key *skey,
801             gcry_mpi_t r_r, gcry_mpi_t s, int hashalgo, gcry_mpi_t pk)
802 {
803   int rc;
804   mpi_ec_t ctx = NULL;
805   int b = 256/8;             /* The only size we currently support.  */
806   unsigned int tmp;
807   unsigned char hash_d[64];  /* Fixme: malloc in secure memory */
808   unsigned char digest[64];
809   gcry_buffer_t hvec[3];
810   const void *mbuf;
811   size_t mlen;
812   unsigned char *rawmpi = NULL;
813   unsigned int rawmpilen;
814   unsigned char *encpk = NULL; /* Encoded public key.  */
815   unsigned int encpklen;
816   mpi_point_struct I;          /* Intermediate value.  */
817   mpi_point_struct Q;          /* Public key.  */
818   gcry_mpi_t a, x, y, r;
819
820   memset (hvec, 0, sizeof hvec);
821
822   if (!mpi_is_opaque (input))
823     return GPG_ERR_INV_DATA;
824   if (hashalgo != GCRY_MD_SHA512)
825     return GPG_ERR_DIGEST_ALGO;
826
827   /* Initialize some helpers.  */
828   point_init (&I);
829   point_init (&Q);
830   a = mpi_snew (0);
831   x = mpi_new (0);
832   y = mpi_new (0);
833   r = mpi_new (0);
834   ctx = _gcry_mpi_ec_p_internal_new (skey->E.model,
835                                      skey->E.p, skey->E.a, skey->E.b);
836
837   /* Hash the secret key.  We clear DIGEST so we can use it to left
838      pad the key with zeroes for hashing.  */
839   rawmpi = _gcry_mpi_get_buffer (skey->d, 0, &rawmpilen, NULL);
840   if (!rawmpi)
841     {
842       rc = gpg_err_code_from_syserror ();
843       goto leave;
844     }
845   memset (digest, 0, b);
846   hvec[0].data = digest;
847   hvec[0].off = 0;
848   hvec[0].len = b > rawmpilen? b - rawmpilen : 0;
849   hvec[1].data = rawmpi;
850   hvec[1].off = 0;
851   hvec[1].len = rawmpilen;
852   rc = _gcry_md_hash_buffers (hashalgo, 0, hash_d, hvec, 2);
853   gcry_free (rawmpi); rawmpi = NULL;
854   if (rc)
855     goto leave;
856
857   /* Compute the A value (this modifies hash_d).  */
858   reverse_buffer (hash_d, 32);  /* Only the first half of the hash.  */
859   hash_d[0] = (hash_d[0] & 0x7f) | 0x40;
860   hash_d[31] &= 0xf8;
861   _gcry_mpi_set_buffer (a, hash_d, 32, 0);
862   /* log_printmpi ("     a", a); */
863
864   /* Compute the public key if it has not been supplied as optional
865      parameter.  */
866   if (pk)
867     {
868       rc = eddsa_decodepoint (pk, b, ctx, &Q,  &encpk, &encpklen);
869       if (rc)
870         goto leave;
871       if (DBG_CIPHER)
872         log_printhex ("* e_pk", encpk, encpklen);
873       if (!_gcry_mpi_ec_curve_point (&Q, ctx))
874         {
875           rc = GPG_ERR_BROKEN_PUBKEY;
876           goto leave;
877         }
878     }
879   else
880     {
881       _gcry_mpi_ec_mul_point (&Q, a, &skey->E.G, ctx);
882       rc = eddsa_encodepoint (&Q, b, ctx, x, y, &encpk, &encpklen);
883       if (rc)
884         goto leave;
885       if (DBG_CIPHER)
886         log_printhex ("  e_pk", encpk, encpklen);
887     }
888
889   /* Compute R.  */
890   mbuf = gcry_mpi_get_opaque (input, &tmp);
891   mlen = (tmp +7)/8;
892   if (DBG_CIPHER)
893     log_printhex ("     m", mbuf, mlen);
894
895   hvec[0].data = hash_d;
896   hvec[0].off  = 32;
897   hvec[0].len  = 32;
898   hvec[1].data = (char*)mbuf;
899   hvec[1].len  = mlen;
900   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2);
901   if (rc)
902     goto leave;
903   reverse_buffer (digest, 64);
904   if (DBG_CIPHER)
905     log_printhex ("     r", digest, 64);
906   _gcry_mpi_set_buffer (r, digest, 64, 0);
907   _gcry_mpi_ec_mul_point (&I, r, &skey->E.G, ctx);
908   if (DBG_CIPHER)
909     log_printpnt ("   r", &I, ctx);
910
911   /* Convert R into affine coordinates and apply encoding.  */
912   rc = eddsa_encodepoint (&I, b, ctx, x, y, &rawmpi, &rawmpilen);
913   if (rc)
914     goto leave;
915   if (DBG_CIPHER)
916     log_printhex ("   e_r", rawmpi, rawmpilen);
917
918   /* S = r + a * H(encodepoint(R) + encodepoint(pk) + m) mod n  */
919   hvec[0].data = rawmpi;  /* (this is R) */
920   hvec[0].off  = 0;
921   hvec[0].len  = rawmpilen;
922   hvec[1].data = encpk;
923   hvec[1].off  = 0;
924   hvec[1].len  = encpklen;
925   hvec[2].data = (char*)mbuf;
926   hvec[2].off  = 0;
927   hvec[2].len  = mlen;
928   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
929   if (rc)
930     goto leave;
931
932   /* No more need for RAWMPI thus we now transfer it to R_R.  */
933   gcry_mpi_set_opaque (r_r, rawmpi, rawmpilen*8);
934   rawmpi = NULL;
935
936   reverse_buffer (digest, 64);
937   if (DBG_CIPHER)
938     log_printhex (" H(R+)", digest, 64);
939   _gcry_mpi_set_buffer (s, digest, 64, 0);
940   mpi_mulm (s, s, a, skey->E.n);
941   mpi_addm (s, s, r, skey->E.n);
942   rc = eddsa_encodempi (s, b, &rawmpi, &rawmpilen);
943   if (rc)
944     goto leave;
945   if (DBG_CIPHER)
946     log_printhex ("   e_s", rawmpi, rawmpilen);
947   gcry_mpi_set_opaque (s, rawmpi, rawmpilen*8);
948   rawmpi = NULL;
949
950   rc = 0;
951
952  leave:
953   gcry_mpi_release (a);
954   gcry_mpi_release (x);
955   gcry_mpi_release (y);
956   gcry_mpi_release (r);
957   _gcry_mpi_ec_free (ctx);
958   point_free (&I);
959   point_free (&Q);
960   gcry_free (encpk);
961   gcry_free (rawmpi);
962   return rc;
963 }
964
965
966 /* Verify an EdDSA signature.  See sign_eddsa for the reference.
967  * Check if R_IN and S_IN verifies INPUT.  PKEY has the curve
968  * parameters and PK is the EdDSA style encoded public key.
969  */
970 static gpg_err_code_t
971 verify_eddsa (gcry_mpi_t input, ECC_public_key *pkey,
972               gcry_mpi_t r_in, gcry_mpi_t s_in, int hashalgo, gcry_mpi_t pk)
973 {
974   int rc;
975   mpi_ec_t ctx = NULL;
976   int b = 256/8;               /* The only size we currently support.  */
977   unsigned int tmp;
978   mpi_point_struct Q;          /* Public key.  */
979   unsigned char *encpk = NULL; /* Encoded public key.  */
980   unsigned int encpklen;
981   const void *mbuf, *rbuf;
982   unsigned char *tbuf = NULL;
983   size_t mlen, rlen;
984   unsigned int tlen;
985   unsigned char digest[64];
986   gcry_buffer_t hvec[3];
987   gcry_mpi_t h, s;
988   mpi_point_struct Ia, Ib;
989
990   if (!mpi_is_opaque (input) || !mpi_is_opaque (r_in) || !mpi_is_opaque (s_in))
991     return GPG_ERR_INV_DATA;
992   if (hashalgo != GCRY_MD_SHA512)
993     return GPG_ERR_DIGEST_ALGO;
994
995   point_init (&Q);
996   point_init (&Ia);
997   point_init (&Ib);
998   h = mpi_new (0);
999   s = mpi_new (0);
1000
1001   ctx = _gcry_mpi_ec_p_internal_new (pkey->E.model,
1002                                      pkey->E.p, pkey->E.a, pkey->E.b);
1003
1004   /* Decode and check the public key.  */
1005   rc = eddsa_decodepoint (pk, b, ctx, &Q, &encpk, &encpklen);
1006   if (rc)
1007     goto leave;
1008   if (!_gcry_mpi_ec_curve_point (&Q, ctx))
1009     {
1010       rc = GPG_ERR_BROKEN_PUBKEY;
1011       goto leave;
1012     }
1013   if (DBG_CIPHER)
1014     log_printhex ("  e_pk", encpk, encpklen);
1015   if (encpklen != b)
1016     {
1017       rc = GPG_ERR_INV_LENGTH;
1018       goto leave;
1019     }
1020
1021   /* Convert the other input parameters.  */
1022   mbuf = gcry_mpi_get_opaque (input, &tmp);
1023   mlen = (tmp +7)/8;
1024   if (DBG_CIPHER)
1025     log_printhex ("     m", mbuf, mlen);
1026   rbuf = gcry_mpi_get_opaque (r_in, &tmp);
1027   rlen = (tmp +7)/8;
1028   if (DBG_CIPHER)
1029     log_printhex ("     r", rbuf, rlen);
1030   if (rlen != b)
1031     {
1032       rc = GPG_ERR_INV_LENGTH;
1033       goto leave;
1034     }
1035
1036   /* h = H(encodepoint(R) + encodepoint(pk) + m)  */
1037   hvec[0].data = (char*)rbuf;
1038   hvec[0].off  = 0;
1039   hvec[0].len  = rlen;
1040   hvec[1].data = encpk;
1041   hvec[1].off  = 0;
1042   hvec[1].len  = encpklen;
1043   hvec[2].data = (char*)mbuf;
1044   hvec[2].off  = 0;
1045   hvec[2].len  = mlen;
1046   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
1047   if (rc)
1048     goto leave;
1049   reverse_buffer (digest, 64);
1050   if (DBG_CIPHER)
1051     log_printhex (" H(R+)", digest, 64);
1052   _gcry_mpi_set_buffer (h, digest, 64, 0);
1053
1054   /* According to the paper the best way for verification is:
1055          encodepoint(sG - h·Q) = encodepoint(r)
1056      because we don't need to decode R. */
1057   {
1058     void *sbuf;
1059     unsigned int slen;
1060
1061     sbuf = _gcry_mpi_get_opaque_copy (s_in, &tmp);
1062     slen = (tmp +7)/8;
1063     reverse_buffer (sbuf, slen);
1064     if (DBG_CIPHER)
1065       log_printhex ("     s", sbuf, slen);
1066     _gcry_mpi_set_buffer (s, sbuf, slen, 0);
1067     gcry_free (sbuf);
1068     if (slen != b)
1069       {
1070         rc = GPG_ERR_INV_LENGTH;
1071         goto leave;
1072       }
1073   }
1074
1075   _gcry_mpi_ec_mul_point (&Ia, s, &pkey->E.G, ctx);
1076   _gcry_mpi_ec_mul_point (&Ib, h, &Q, ctx);
1077   _gcry_mpi_neg (Ib.x, Ib.x);
1078   _gcry_mpi_ec_add_points (&Ia, &Ia, &Ib, ctx);
1079   rc = eddsa_encodepoint (&Ia, b, ctx, s, h, &tbuf, &tlen);
1080   if (rc)
1081     goto leave;
1082   if (tlen != rlen || memcmp (tbuf, rbuf, tlen))
1083     {
1084       if (DBG_CIPHER)
1085         log_debug ("eddsa verify: Not verified\n");
1086       rc = GPG_ERR_BAD_SIGNATURE;
1087       goto leave;
1088     }
1089
1090   if (DBG_CIPHER)
1091     log_debug ("eddsa verify: Accepted\n");
1092   rc = 0;
1093
1094  leave:
1095   gcry_free (encpk);
1096   gcry_free (tbuf);
1097   _gcry_mpi_ec_free (ctx);
1098   gcry_mpi_release (s);
1099   gcry_mpi_release (h);
1100   point_free (&Ia);
1101   point_free (&Ib);
1102   point_free (&Q);
1103   return rc;
1104 }
1105
1106
1107 \f
1108 /*********************************************
1109  **************  interface  ******************
1110  *********************************************/
1111
1112 /* Extended version of ecc_generate.  */
1113 static gcry_err_code_t
1114 ecc_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
1115                   const gcry_sexp_t genparms,
1116                   gcry_mpi_t *skey, gcry_mpi_t **retfactors,
1117                   gcry_sexp_t *r_extrainfo)
1118 {
1119   gpg_err_code_t ec;
1120   ECC_secret_key sk;
1121   gcry_mpi_t g_x, g_y, q_x, q_y;
1122   char *curve_name = NULL;
1123   gcry_sexp_t l1;
1124   int transient_key = 0;
1125   const char *usedcurve = NULL;
1126
1127   (void)algo;
1128   (void)evalue;
1129
1130   if (genparms)
1131     {
1132       /* Parse the optional "curve" parameter. */
1133       l1 = gcry_sexp_find_token (genparms, "curve", 0);
1134       if (l1)
1135         {
1136           curve_name = _gcry_sexp_nth_string (l1, 1);
1137           gcry_sexp_release (l1);
1138           if (!curve_name)
1139             return GPG_ERR_INV_OBJ; /* No curve name or value too large. */
1140         }
1141
1142       /* Parse the optional transient-key flag.  */
1143       l1 = gcry_sexp_find_token (genparms, "transient-key", 0);
1144       if (l1)
1145         {
1146           transient_key = 1;
1147           gcry_sexp_release (l1);
1148         }
1149     }
1150
1151   /* NBITS is required if no curve name has been given.  */
1152   if (!nbits && !curve_name)
1153     return GPG_ERR_NO_OBJ; /* No NBITS parameter. */
1154
1155   g_x = mpi_new (0);
1156   g_y = mpi_new (0);
1157   q_x = mpi_new (0);
1158   q_y = mpi_new (0);
1159   ec = generate_key (&sk, nbits, curve_name, transient_key, g_x, g_y, q_x, q_y,
1160                      &usedcurve);
1161   gcry_free (curve_name);
1162   if (ec)
1163     return ec;
1164   if (usedcurve)  /* Fixme: No error return checking.  */
1165     gcry_sexp_build (r_extrainfo, NULL, "(curve %s)", usedcurve);
1166
1167   skey[0] = sk.E.p;
1168   skey[1] = sk.E.a;
1169   skey[2] = sk.E.b;
1170   skey[3] = _gcry_ecc_ec2os (g_x, g_y, sk.E.p);
1171   skey[4] = sk.E.n;
1172   skey[5] = _gcry_ecc_ec2os (q_x, q_y, sk.E.p);
1173   skey[6] = sk.d;
1174
1175   mpi_free (g_x);
1176   mpi_free (g_y);
1177   mpi_free (q_x);
1178   mpi_free (q_y);
1179
1180   point_free (&sk.E.G);
1181   point_free (&sk.Q);
1182
1183   /* Make an empty list of factors.  */
1184   *retfactors = gcry_calloc ( 1, sizeof **retfactors );
1185   if (!*retfactors)
1186     return gpg_err_code_from_syserror ();  /* Fixme: relase mem?  */
1187
1188   if (DBG_CIPHER)
1189     {
1190       log_debug ("ecgen result model: %s\n", _gcry_ecc_model2str (sk.E.model));
1191       log_mpidump ("ecgen result p", skey[0]);
1192       log_mpidump ("ecgen result a", skey[1]);
1193       log_mpidump ("ecgen result b", skey[2]);
1194       log_mpidump ("ecgen result G", skey[3]);
1195       log_mpidump ("ecgen result n", skey[4]);
1196       log_mpidump ("ecgen result Q", skey[5]);
1197       log_mpidump ("ecgen result d", skey[6]);
1198     }
1199
1200   return 0;
1201 }
1202
1203
1204 static gcry_err_code_t
1205 ecc_generate (int algo, unsigned int nbits, unsigned long evalue,
1206               gcry_mpi_t *skey, gcry_mpi_t **retfactors)
1207 {
1208   (void)evalue;
1209   return ecc_generate_ext (algo, nbits, 0, NULL, skey, retfactors, NULL);
1210 }
1211
1212
1213 static gcry_err_code_t
1214 ecc_check_secret_key (int algo, gcry_mpi_t *skey)
1215 {
1216   gpg_err_code_t err;
1217   ECC_secret_key sk;
1218
1219   (void)algo;
1220
1221   /* FIXME:  This check looks a bit fishy:  Now long is the array?  */
1222   if (!skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] || !skey[5]
1223       || !skey[6])
1224     return GPG_ERR_BAD_MPI;
1225
1226   sk.E.model = MPI_EC_WEIERSTRASS;
1227   sk.E.p = skey[0];
1228   sk.E.a = skey[1];
1229   sk.E.b = skey[2];
1230   point_init (&sk.E.G);
1231   err = _gcry_ecc_os2ec (&sk.E.G, skey[3]);
1232   if (err)
1233     {
1234       point_free (&sk.E.G);
1235       return err;
1236     }
1237   sk.E.n = skey[4];
1238   point_init (&sk.Q);
1239   err = _gcry_ecc_os2ec (&sk.Q, skey[5]);
1240   if (err)
1241     {
1242       point_free (&sk.E.G);
1243       point_free (&sk.Q);
1244       return err;
1245     }
1246
1247   sk.d = skey[6];
1248
1249   if (check_secret_key (&sk))
1250     {
1251       point_free (&sk.E.G);
1252       point_free (&sk.Q);
1253       return GPG_ERR_BAD_SECKEY;
1254     }
1255   point_free (&sk.E.G);
1256   point_free (&sk.Q);
1257   return 0;
1258 }
1259
1260
1261 static gcry_err_code_t
1262 ecc_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey,
1263           int flags, int hashalgo)
1264 {
1265   gpg_err_code_t err;
1266   ECC_secret_key sk;
1267
1268   (void)algo;
1269
1270   if (!data || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4]
1271       || !skey[6] )
1272     return GPG_ERR_BAD_MPI;
1273
1274   sk.E.model = ((flags & PUBKEY_FLAG_EDDSA)
1275                 ? MPI_EC_TWISTEDEDWARDS
1276                 : MPI_EC_WEIERSTRASS);
1277   sk.E.p = skey[0];
1278   sk.E.a = skey[1];
1279   sk.E.b = skey[2];
1280   point_init (&sk.E.G);
1281   sk.Q.x = NULL;
1282   sk.Q.y = NULL;
1283   sk.Q.z = NULL;
1284   err = _gcry_ecc_os2ec (&sk.E.G, skey[3]);
1285   if (err)
1286     {
1287       point_free (&sk.E.G);
1288       return err;
1289     }
1290   sk.E.n = skey[4];
1291   sk.d = skey[6];
1292
1293   resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.E.p));
1294   resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.E.p));
1295   if ((flags & PUBKEY_FLAG_EDDSA))
1296     err = sign_eddsa (data, &sk, resarr[0], resarr[1], hashalgo, skey[5]);
1297   else
1298     err = sign_ecdsa (data, &sk, resarr[0], resarr[1], flags, hashalgo);
1299   if (err)
1300     {
1301       mpi_free (resarr[0]);
1302       mpi_free (resarr[1]);
1303       resarr[0] = NULL; /* Mark array as released.  */
1304     }
1305   point_free (&sk.E.G);
1306   if (sk.Q.x)
1307     point_free (&sk.Q);
1308   return err;
1309 }
1310
1311
1312 static gcry_err_code_t
1313 ecc_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
1314             int (*cmp)(void *, gcry_mpi_t), void *opaquev,
1315             int flags, int hashalgo)
1316 {
1317   gpg_err_code_t err;
1318   ECC_public_key pk;
1319
1320   (void)algo;
1321   (void)cmp;
1322   (void)opaquev;
1323
1324   if (!data[0] || !data[1] || !hash || !pkey[0] || !pkey[1] || !pkey[2]
1325       || !pkey[3] || !pkey[4] || !pkey[5] )
1326     return GPG_ERR_BAD_MPI;
1327
1328   pk.E.model = ((flags & PUBKEY_FLAG_EDDSA)
1329                 ? MPI_EC_TWISTEDEDWARDS
1330                 : MPI_EC_WEIERSTRASS);
1331   pk.E.p = pkey[0];
1332   pk.E.a = pkey[1];
1333   pk.E.b = pkey[2];
1334   point_init (&pk.E.G);
1335   err = _gcry_ecc_os2ec (&pk.E.G, pkey[3]);
1336   if (err)
1337     {
1338       point_free (&pk.E.G);
1339       return err;
1340     }
1341   pk.E.n = pkey[4];
1342
1343   if ((flags & PUBKEY_FLAG_EDDSA))
1344     {
1345       pk.Q.x = NULL;
1346       pk.Q.y = NULL;
1347       pk.Q.z = NULL;
1348
1349       err = verify_eddsa (hash, &pk, data[0], data[1], hashalgo, pkey[5]);
1350     }
1351   else
1352     {
1353       point_init (&pk.Q);
1354       err = _gcry_ecc_os2ec (&pk.Q, pkey[5]);
1355       if (err)
1356         {
1357           point_free (&pk.E.G);
1358           point_free (&pk.Q);
1359           return err;
1360         }
1361
1362       if (mpi_is_opaque (hash))
1363         {
1364           const void *abuf;
1365           unsigned int abits, qbits;
1366           gcry_mpi_t a;
1367
1368           qbits = mpi_get_nbits (pk.E.n);
1369
1370           abuf = gcry_mpi_get_opaque (hash, &abits);
1371           err = gcry_mpi_scan (&a, GCRYMPI_FMT_USG, abuf, (abits+7)/8, NULL);
1372           if (!err)
1373             {
1374               if (abits > qbits)
1375                 gcry_mpi_rshift (a, a, abits - qbits);
1376
1377               err = verify_ecdsa (a, &pk, data[0], data[1]);
1378               gcry_mpi_release (a);
1379             }
1380         }
1381       else
1382         err = verify_ecdsa (hash, &pk, data[0], data[1]);
1383     }
1384
1385   point_free (&pk.E.G);
1386   point_free (&pk.Q);
1387   return err;
1388 }
1389
1390
1391 /* ecdh raw is classic 2-round DH protocol published in 1976.
1392  *
1393  * Overview of ecc_encrypt_raw and ecc_decrypt_raw.
1394  *
1395  * As with any PK operation, encrypt version uses a public key and
1396  * decrypt -- private.
1397  *
1398  * Symbols used below:
1399  *     G - field generator point
1400  *     d - private long-term scalar
1401  *    dG - public long-term key
1402  *     k - ephemeral scalar
1403  *    kG - ephemeral public key
1404  *   dkG - shared secret
1405  *
1406  * ecc_encrypt_raw description:
1407  *   input:
1408  *     data[0] : private scalar (k)
1409  *   output:
1410  *     result[0] : shared point (kdG)
1411  *     result[1] : generated ephemeral public key (kG)
1412  *
1413  * ecc_decrypt_raw description:
1414  *   input:
1415  *     data[0] : a point kG (ephemeral public key)
1416  *   output:
1417  *     result[0] : shared point (kdG)
1418  */
1419 static gcry_err_code_t
1420 ecc_encrypt_raw (int algo, gcry_mpi_t *resarr, gcry_mpi_t k,
1421                  gcry_mpi_t *pkey, int flags)
1422 {
1423   ECC_public_key pk;
1424   mpi_ec_t ctx;
1425   gcry_mpi_t result[2];
1426   int err;
1427
1428   (void)algo;
1429   (void)flags;
1430
1431   if (!k
1432       || !pkey[0] || !pkey[1] || !pkey[2] || !pkey[3] || !pkey[4] || !pkey[5])
1433     return GPG_ERR_BAD_MPI;
1434
1435   pk.E.model = MPI_EC_WEIERSTRASS;
1436   pk.E.p = pkey[0];
1437   pk.E.a = pkey[1];
1438   pk.E.b = pkey[2];
1439   point_init (&pk.E.G);
1440   err = _gcry_ecc_os2ec (&pk.E.G, pkey[3]);
1441   if (err)
1442     {
1443       point_free (&pk.E.G);
1444       return err;
1445     }
1446   pk.E.n = pkey[4];
1447   point_init (&pk.Q);
1448   err = _gcry_ecc_os2ec (&pk.Q, pkey[5]);
1449   if (err)
1450     {
1451       point_free (&pk.E.G);
1452       point_free (&pk.Q);
1453       return err;
1454     }
1455
1456   ctx = _gcry_mpi_ec_p_internal_new (pk.E.model, pk.E.p, pk.E.a, pk.E.b);
1457
1458   /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so */
1459   {
1460     mpi_point_struct R;  /* Result that we return.  */
1461     gcry_mpi_t x, y;
1462
1463     x = mpi_new (0);
1464     y = mpi_new (0);
1465
1466     point_init (&R);
1467
1468     /* R = kQ  <=>  R = kdG  */
1469     _gcry_mpi_ec_mul_point (&R, k, &pk.Q, ctx);
1470
1471     if (_gcry_mpi_ec_get_affine (x, y, &R, ctx))
1472       log_fatal ("ecdh: Failed to get affine coordinates for kdG\n");
1473
1474     result[0] = _gcry_ecc_ec2os (x, y, pk.E.p);
1475
1476     /* R = kG */
1477     _gcry_mpi_ec_mul_point (&R, k, &pk.E.G, ctx);
1478
1479     if (_gcry_mpi_ec_get_affine (x, y, &R, ctx))
1480       log_fatal ("ecdh: Failed to get affine coordinates for kG\n");
1481
1482     result[1] = _gcry_ecc_ec2os (x, y, pk.E.p);
1483
1484     mpi_free (x);
1485     mpi_free (y);
1486
1487     point_free (&R);
1488   }
1489
1490   _gcry_mpi_ec_free (ctx);
1491   point_free (&pk.E.G);
1492   point_free (&pk.Q);
1493
1494   if (!result[0] || !result[1])
1495     {
1496       mpi_free (result[0]);
1497       mpi_free (result[1]);
1498       return GPG_ERR_ENOMEM;
1499     }
1500
1501   /* Success.  */
1502   resarr[0] = result[0];
1503   resarr[1] = result[1];
1504
1505   return 0;
1506 }
1507
1508 /*  input:
1509  *     data[0] : a point kG (ephemeral public key)
1510  *   output:
1511  *     resaddr[0] : shared point kdG
1512  *
1513  *  see ecc_encrypt_raw for details.
1514  */
1515 static gcry_err_code_t
1516 ecc_decrypt_raw (int algo, gcry_mpi_t *result, gcry_mpi_t *data,
1517                  gcry_mpi_t *skey, int flags)
1518 {
1519   ECC_secret_key sk;
1520   mpi_point_struct R;   /* Result that we return.  */
1521   mpi_point_struct kG;
1522   mpi_ec_t ctx;
1523   gcry_mpi_t r;
1524   int err;
1525
1526   (void)algo;
1527   (void)flags;
1528
1529   *result = NULL;
1530
1531   if (!data || !data[0]
1532       || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4]
1533       || !skey[5] || !skey[6] )
1534     return GPG_ERR_BAD_MPI;
1535
1536   point_init (&kG);
1537   err = _gcry_ecc_os2ec (&kG, data[0]);
1538   if (err)
1539     {
1540       point_free (&kG);
1541       return err;
1542     }
1543
1544   sk.E.model = MPI_EC_WEIERSTRASS;
1545   sk.E.p = skey[0];
1546   sk.E.a = skey[1];
1547   sk.E.b = skey[2];
1548   point_init (&sk.E.G);
1549   err = _gcry_ecc_os2ec (&sk.E.G, skey[3]);
1550   if (err)
1551     {
1552       point_free (&kG);
1553       point_free (&sk.E.G);
1554       return err;
1555     }
1556   sk.E.n = skey[4];
1557   point_init (&sk.Q);
1558   err = _gcry_ecc_os2ec (&sk.Q, skey[5]);
1559   if (err)
1560     {
1561       point_free (&kG);
1562       point_free (&sk.E.G);
1563       point_free (&sk.Q);
1564       return err;
1565     }
1566   sk.d = skey[6];
1567
1568   ctx = _gcry_mpi_ec_p_internal_new (sk.E.model, sk.E.p, sk.E.a, sk.E.b);
1569
1570   /* R = dkG */
1571   point_init (&R);
1572   _gcry_mpi_ec_mul_point (&R, sk.d, &kG, ctx);
1573
1574   point_free (&kG);
1575
1576   /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so:  */
1577   {
1578     gcry_mpi_t x, y;
1579
1580     x = mpi_new (0);
1581     y = mpi_new (0);
1582
1583     if (_gcry_mpi_ec_get_affine (x, y, &R, ctx))
1584       log_fatal ("ecdh: Failed to get affine coordinates\n");
1585
1586     r = _gcry_ecc_ec2os (x, y, sk.E.p);
1587     mpi_free (x);
1588     mpi_free (y);
1589   }
1590
1591   point_free (&R);
1592   _gcry_mpi_ec_free (ctx);
1593   point_free (&kG);
1594   point_free (&sk.E.G);
1595   point_free (&sk.Q);
1596
1597   if (!r)
1598     return GPG_ERR_ENOMEM;
1599
1600   /* Success.  */
1601
1602   *result = r;
1603
1604   return 0;
1605 }
1606
1607
1608 static unsigned int
1609 ecc_get_nbits (int algo, gcry_mpi_t *pkey)
1610 {
1611   (void)algo;
1612
1613   return mpi_get_nbits (pkey[0]);
1614 }
1615
1616
1617 /* See rsa.c for a description of this function.  */
1618 static gpg_err_code_t
1619 compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
1620 {
1621 #define N_COMPONENTS 6
1622   static const char names[N_COMPONENTS+1] = "pabgnq";
1623   gpg_err_code_t ec = 0;
1624   gcry_sexp_t l1;
1625   gcry_mpi_t values[N_COMPONENTS];
1626   int idx;
1627
1628   /* Clear the values for easier error cleanup.  */
1629   for (idx=0; idx < N_COMPONENTS; idx++)
1630     values[idx] = NULL;
1631
1632   /* Fill values with all provided parameters.  */
1633   for (idx=0; idx < N_COMPONENTS; idx++)
1634     {
1635       l1 = gcry_sexp_find_token (keyparam, names+idx, 1);
1636       if (l1)
1637         {
1638           values[idx] = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1639           gcry_sexp_release (l1);
1640           if (!values[idx])
1641             {
1642               ec = GPG_ERR_INV_OBJ;
1643               goto leave;
1644             }
1645         }
1646     }
1647
1648   /* Check whether a curve parameter is available and use that to fill
1649      in missing values.  */
1650   l1 = gcry_sexp_find_token (keyparam, "curve", 5);
1651   if (l1)
1652     {
1653       char *curve;
1654       gcry_mpi_t tmpvalues[N_COMPONENTS];
1655
1656       for (idx = 0; idx < N_COMPONENTS; idx++)
1657         tmpvalues[idx] = NULL;
1658
1659       curve = _gcry_sexp_nth_string (l1, 1);
1660       gcry_sexp_release (l1);
1661       if (!curve)
1662         {
1663           ec = GPG_ERR_INV_OBJ; /* Name missing or out of core. */
1664           goto leave;
1665         }
1666       ec = _gcry_ecc_get_param (curve, tmpvalues);
1667       gcry_free (curve);
1668       if (ec)
1669         goto leave;
1670
1671       for (idx = 0; idx < N_COMPONENTS; idx++)
1672         {
1673           if (!values[idx])
1674             values[idx] = tmpvalues[idx];
1675           else
1676             mpi_free (tmpvalues[idx]);
1677         }
1678     }
1679
1680   /* Check that all parameters are known and normalize all MPIs (that
1681      should not be required but we use an internal function later and
1682      thus we better make 100% sure that they are normalized). */
1683   for (idx = 0; idx < N_COMPONENTS; idx++)
1684     if (!values[idx])
1685       {
1686         ec = GPG_ERR_NO_OBJ;
1687         goto leave;
1688       }
1689     else
1690       _gcry_mpi_normalize (values[idx]);
1691
1692   /* Hash them all.  */
1693   for (idx = 0; idx < N_COMPONENTS; idx++)
1694     {
1695       char buf[30];
1696       unsigned char *rawmpi;
1697       unsigned int rawmpilen;
1698
1699       rawmpi = _gcry_mpi_get_buffer (values[idx], 0, &rawmpilen, NULL);
1700       if (!rawmpi)
1701         {
1702           ec = gpg_err_code_from_syserror ();
1703           goto leave;
1704         }
1705       snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], rawmpilen);
1706       gcry_md_write (md, buf, strlen (buf));
1707       gcry_md_write (md, rawmpi, rawmpilen);
1708       gcry_md_write (md, ")", 1);
1709       gcry_free (rawmpi);
1710     }
1711
1712  leave:
1713   for (idx = 0; idx < N_COMPONENTS; idx++)
1714     _gcry_mpi_release (values[idx]);
1715
1716   return ec;
1717 #undef N_COMPONENTS
1718 }
1719
1720
1721 \f
1722 /*
1723    Low-level API helper functions.
1724  */
1725
1726 /* This is the wroker function for gcry_pubkey_get_sexp for ECC
1727    algorithms.  Note that the caller has already stored NULL at
1728    R_SEXP.  */
1729 gpg_err_code_t
1730 _gcry_pk_ecc_get_sexp (gcry_sexp_t *r_sexp, int mode, mpi_ec_t ec)
1731 {
1732   gpg_err_code_t rc;
1733   gcry_mpi_t mpi_G = NULL;
1734   gcry_mpi_t mpi_Q = NULL;
1735
1736   if (!ec->p || !ec->a || !ec->b || !ec->G || !ec->n)
1737     return GPG_ERR_BAD_CRYPT_CTX;
1738
1739   if (mode == GCRY_PK_GET_SECKEY && !ec->d)
1740     return GPG_ERR_NO_SECKEY;
1741
1742   /* Compute the public point if it is missing.  */
1743   if (!ec->Q && ec->d)
1744     {
1745       ec->Q = gcry_mpi_point_new (0);
1746       _gcry_mpi_ec_mul_point (ec->Q, ec->d, ec->G, ec);
1747     }
1748
1749   /* Encode G and Q.  */
1750   mpi_G = _gcry_mpi_ec_ec2os (ec->G, ec);
1751   if (!mpi_G)
1752     {
1753       rc = GPG_ERR_BROKEN_PUBKEY;
1754       goto leave;
1755     }
1756   if (!ec->Q)
1757     {
1758       rc = GPG_ERR_BAD_CRYPT_CTX;
1759       goto leave;
1760     }
1761   mpi_Q = _gcry_mpi_ec_ec2os (ec->Q, ec);
1762   if (!mpi_Q)
1763     {
1764       rc = GPG_ERR_BROKEN_PUBKEY;
1765       goto leave;
1766     }
1767
1768   /* Fixme: We should return a curve name instead of the parameters if
1769      if know that they match a curve.  */
1770
1771   if (ec->d && (!mode || mode == GCRY_PK_GET_SECKEY))
1772     {
1773       /* Let's return a private key. */
1774       rc = gpg_err_code
1775         (gcry_sexp_build
1776          (r_sexp, NULL,
1777           "(private-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)(q%m)(d%m)))",
1778           ec->p, ec->a, ec->b, mpi_G, ec->n, mpi_Q, ec->d));
1779     }
1780   else if (ec->Q)
1781     {
1782       /* Let's return a public key.  */
1783       rc = gpg_err_code
1784         (gcry_sexp_build
1785          (r_sexp, NULL,
1786           "(public-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)(q%m)))",
1787           ec->p, ec->a, ec->b, mpi_G, ec->n, mpi_Q));
1788     }
1789   else
1790     rc = GPG_ERR_BAD_CRYPT_CTX;
1791
1792  leave:
1793   mpi_free (mpi_Q);
1794   mpi_free (mpi_G);
1795   return rc;
1796 }
1797
1798
1799 \f
1800 /*
1801      Self-test section.
1802  */
1803
1804
1805 static gpg_err_code_t
1806 selftests_ecdsa (selftest_report_func_t report)
1807 {
1808   const char *what;
1809   const char *errtxt;
1810
1811   what = "low-level";
1812   errtxt = NULL; /*selftest ();*/
1813   if (errtxt)
1814     goto failed;
1815
1816   /* FIXME:  need more tests.  */
1817
1818   return 0; /* Succeeded. */
1819
1820  failed:
1821   if (report)
1822     report ("pubkey", GCRY_PK_ECDSA, what, errtxt);
1823   return GPG_ERR_SELFTEST_FAILED;
1824 }
1825
1826
1827 /* Run a full self-test for ALGO and return 0 on success.  */
1828 static gpg_err_code_t
1829 run_selftests (int algo, int extended, selftest_report_func_t report)
1830 {
1831   gpg_err_code_t ec;
1832
1833   (void)extended;
1834
1835   switch (algo)
1836     {
1837     case GCRY_PK_ECDSA:
1838       ec = selftests_ecdsa (report);
1839       break;
1840     default:
1841       ec = GPG_ERR_PUBKEY_ALGO;
1842       break;
1843
1844     }
1845   return ec;
1846 }
1847
1848
1849
1850 \f
1851 static const char *ecdsa_names[] =
1852   {
1853     "ecdsa",
1854     "ecc",
1855     NULL,
1856   };
1857 static const char *ecdh_names[] =
1858   {
1859     "ecdh",
1860     "ecc",
1861     NULL,
1862   };
1863
1864 gcry_pk_spec_t _gcry_pubkey_spec_ecdsa =
1865   {
1866     "ECDSA", ecdsa_names,
1867     "pabgnq", "pabgnqd", "", "rs", "pabgnq",
1868     GCRY_PK_USAGE_SIGN,
1869     ecc_generate,
1870     ecc_check_secret_key,
1871     NULL,
1872     NULL,
1873     ecc_sign,
1874     ecc_verify,
1875     ecc_get_nbits
1876   };
1877
1878 gcry_pk_spec_t _gcry_pubkey_spec_ecdh =
1879   {
1880     "ECDH", ecdh_names,
1881     "pabgnq", "pabgnqd", "se", "", "pabgnq",
1882     GCRY_PK_USAGE_ENCR,
1883     ecc_generate,
1884     ecc_check_secret_key,
1885     ecc_encrypt_raw,
1886     ecc_decrypt_raw,
1887     NULL,
1888     NULL,
1889     ecc_get_nbits
1890   };
1891
1892
1893 pk_extra_spec_t _gcry_pubkey_extraspec_ecdsa =
1894   {
1895     run_selftests,
1896     ecc_generate_ext,
1897     compute_keygrip,
1898     _gcry_ecc_get_param,
1899     _gcry_ecc_get_curve,
1900     _gcry_ecc_get_param_sexp
1901   };