Add curve aliases from RFC-5656.
[libgcrypt.git] / cipher / ecc.c
1 /* ecc.c  -  Elliptic Curve Cryptography
2    Copyright (C) 2007, 2008, 2010, 2011 Free Software Foundation, Inc.
3
4    This file is part of Libgcrypt.
5
6    Libgcrypt is free software; you can redistribute it and/or modify
7    it under the terms of the GNU Lesser General Public License as
8    published by the Free Software Foundation; either version 2.1 of
9    the License, or (at your option) any later version.
10
11    Libgcrypt is distributed in the hope that it will be useful,
12    but WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14    GNU Lesser General Public License for more details.
15
16    You should have received a copy of the GNU Lesser General Public
17    License along with this program; if not, write to the Free Software
18    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
19    USA.  */
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   - Decide whether we should hide the mpi_point_t definition.
51 */
52
53
54 #include <config.h>
55 #include <stdio.h>
56 #include <stdlib.h>
57 #include <string.h>
58
59 #include "g10lib.h"
60 #include "mpi.h"
61 #include "cipher.h"
62
63 /* Definition of a curve.  */
64 typedef struct
65 {
66   gcry_mpi_t p;   /* Prime specifying the field GF(p).  */
67   gcry_mpi_t a;   /* First coefficient of the Weierstrass equation.  */
68   gcry_mpi_t b;   /* Second coefficient of the Weierstrass equation.  */
69   mpi_point_t G;  /* Base point (generator).  */
70   gcry_mpi_t n;   /* Order of G.  */
71   const char *name;  /* Name of curve or NULL.  */
72 } elliptic_curve_t;
73
74
75 typedef struct
76 {
77   elliptic_curve_t E;
78   mpi_point_t Q;  /* Q = [d]G  */
79 } ECC_public_key;
80
81 typedef struct
82 {
83   elliptic_curve_t E;
84   mpi_point_t Q;
85   gcry_mpi_t d;
86 } ECC_secret_key;
87
88
89 /* This tables defines aliases for curve names.  */
90 static const struct
91 {
92   const char *name;  /* Our name.  */
93   const char *other; /* Other name. */
94 } curve_aliases[] =
95   {
96     { "NIST P-192", "1.2.840.10045.3.1.1" }, /* X9.62 OID  */
97     { "NIST P-192", "prime192v1" },          /* X9.62 name.  */
98     { "NIST P-192", "secp192r1"  },          /* SECP name.  */
99     { "NIST P-192", "nistp192"   },          /* rfc5656.  */
100
101     { "NIST P-224", "secp224r1" },
102     { "NIST P-224", "1.3.132.0.33" },        /* SECP OID.  */
103     { "NIST P-224", "nistp224"   },          /* rfc5656.  */
104
105     { "NIST P-256", "1.2.840.10045.3.1.7" }, /* From NIST SP 800-78-1.  */
106     { "NIST P-256", "prime256v1" },
107     { "NIST P-256", "secp256r1"  },
108     { "NIST P-256", "nistp256"   },          /* rfc5656.  */
109
110     { "NIST P-384", "secp384r1" },
111     { "NIST P-384", "1.3.132.0.34" },
112     { "NIST P-384", "nistp384"   },          /* rfc5656.  */
113
114     { "NIST P-521", "secp521r1" },
115     { "NIST P-521", "1.3.132.0.35" },
116     { "NIST P-521", "nistp521"   },          /* rfc5656.  */
117
118     { "brainpoolP160r1", "1.3.36.3.3.2.8.1.1.1" },
119     { "brainpoolP192r1", "1.3.36.3.3.2.8.1.1.3" },
120     { "brainpoolP224r1", "1.3.36.3.3.2.8.1.1.5" },
121     { "brainpoolP256r1", "1.3.36.3.3.2.8.1.1.7" },
122     { "brainpoolP320r1", "1.3.36.3.3.2.8.1.1.9" },
123     { "brainpoolP384r1", "1.3.36.3.3.2.8.1.1.11"},
124     { "brainpoolP512r1", "1.3.36.3.3.2.8.1.1.13"},
125
126     { NULL, NULL}
127   };
128
129 typedef struct   {
130   const char *desc;           /* Description of the curve.  */
131   unsigned int nbits;         /* Number of bits.  */
132   unsigned int fips:1;        /* True if this is a FIPS140-2 approved curve. */
133   const char  *p;             /* Order of the prime field.  */
134   const char *a, *b;          /* The coefficients. */
135   const char *n;              /* The order of the base point.  */
136   const char *g_x, *g_y;      /* Base point.  */
137 } ecc_domain_parms_t;
138
139 /* This static table defines all available curves.  */
140 static const ecc_domain_parms_t domain_parms[] =
141   {
142     {
143       "NIST P-192", 192, 1,
144       "0xfffffffffffffffffffffffffffffffeffffffffffffffff",
145       "0xfffffffffffffffffffffffffffffffefffffffffffffffc",
146       "0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1",
147       "0xffffffffffffffffffffffff99def836146bc9b1b4d22831",
148
149       "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012",
150       "0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
151     },
152     {
153       "NIST P-224", 224, 1,
154       "0xffffffffffffffffffffffffffffffff000000000000000000000001",
155       "0xfffffffffffffffffffffffffffffffefffffffffffffffffffffffe",
156       "0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4",
157       "0xffffffffffffffffffffffffffff16a2e0b8f03e13dd29455c5c2a3d" ,
158
159       "0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21",
160       "0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34"
161     },
162     {
163       "NIST P-256", 256, 1,
164       "0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff",
165       "0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc",
166       "0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b",
167       "0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551",
168
169       "0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296",
170       "0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5"
171     },
172     {
173       "NIST P-384", 384, 1,
174       "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
175       "ffffffff0000000000000000ffffffff",
176       "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
177       "ffffffff0000000000000000fffffffc",
178       "0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875a"
179       "c656398d8a2ed19d2a85c8edd3ec2aef",
180       "0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf"
181       "581a0db248b0a77aecec196accc52973",
182
183       "0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a38"
184       "5502f25dbf55296c3a545e3872760ab7",
185       "0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c0"
186       "0a60b1ce1d7e819d7a431d7c90ea0e5f"
187     },
188     {
189       "NIST P-521", 521, 1,
190       "0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
191       "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
192       "0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
193       "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc",
194       "0x051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef10"
195       "9e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00",
196       "0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
197       "ffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409",
198
199       "0xc6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3d"
200       "baa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66",
201       "0x11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e6"
202       "62c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650"
203     },
204
205     { "brainpoolP160r1", 160, 0,
206       "0xe95e4a5f737059dc60dfc7ad95b3d8139515620f",
207       "0x340e7be2a280eb74e2be61bada745d97e8f7c300",
208       "0x1e589a8595423412134faa2dbdec95c8d8675e58",
209       "0xe95e4a5f737059dc60df5991d45029409e60fc09",
210       "0xbed5af16ea3f6a4f62938c4631eb5af7bdbcdbc3",
211       "0x1667cb477a1a8ec338f94741669c976316da6321"
212     },
213
214     { "brainpoolP192r1", 192, 0,
215       "0xc302f41d932a36cda7a3463093d18db78fce476de1a86297",
216       "0x6a91174076b1e0e19c39c031fe8685c1cae040e5c69a28ef",
217       "0x469a28ef7c28cca3dc721d044f4496bcca7ef4146fbf25c9",
218       "0xc302f41d932a36cda7a3462f9e9e916b5be8f1029ac4acc1",
219       "0xc0a0647eaab6a48753b033c56cb0f0900a2f5c4853375fd6",
220       "0x14b690866abd5bb88b5f4828c1490002e6773fa2fa299b8f"
221     },
222
223     { "brainpoolP224r1", 224, 0,
224       "0xd7c134aa264366862a18302575d1d787b09f075797da89f57ec8c0ff",
225       "0x68a5e62ca9ce6c1c299803a6c1530b514e182ad8b0042a59cad29f43",
226       "0x2580f63ccfe44138870713b1a92369e33e2135d266dbb372386c400b",
227       "0xd7c134aa264366862a18302575d0fb98d116bc4b6ddebca3a5a7939f",
228       "0x0d9029ad2c7e5cf4340823b2a87dc68c9e4ce3174c1e6efdee12c07d",
229       "0x58aa56f772c0726f24c6b89e4ecdac24354b9e99caa3f6d3761402cd"
230     },
231
232     { "brainpoolP256r1", 256, 0,
233       "0xa9fb57dba1eea9bc3e660a909d838d726e3bf623d52620282013481d1f6e5377",
234       "0x7d5a0975fc2c3057eef67530417affe7fb8055c126dc5c6ce94a4b44f330b5d9",
235       "0x26dc5c6ce94a4b44f330b5d9bbd77cbf958416295cf7e1ce6bccdc18ff8c07b6",
236       "0xa9fb57dba1eea9bc3e660a909d838d718c397aa3b561a6f7901e0e82974856a7",
237       "0x8bd2aeb9cb7e57cb2c4b482ffc81b7afb9de27e1e3bd23c23a4453bd9ace3262",
238       "0x547ef835c3dac4fd97f8461a14611dc9c27745132ded8e545c1d54c72f046997"
239     },
240
241     { "brainpoolP320r1", 320, 0,
242       "0xd35e472036bc4fb7e13c785ed201e065f98fcfa6f6f40def4f92b9ec7893ec28"
243       "fcd412b1f1b32e27",
244       "0x3ee30b568fbab0f883ccebd46d3f3bb8a2a73513f5eb79da66190eb085ffa9f4"
245       "92f375a97d860eb4",
246       "0x520883949dfdbc42d3ad198640688a6fe13f41349554b49acc31dccd88453981"
247       "6f5eb4ac8fb1f1a6",
248       "0xd35e472036bc4fb7e13c785ed201e065f98fcfa5b68f12a32d482ec7ee8658e9"
249       "8691555b44c59311",
250       "0x43bd7e9afb53d8b85289bcc48ee5bfe6f20137d10a087eb6e7871e2a10a599c7"
251       "10af8d0d39e20611",
252       "0x14fdd05545ec1cc8ab4093247f77275e0743ffed117182eaa9c77877aaac6ac7"
253       "d35245d1692e8ee1"
254     },
255
256     { "brainpoolP384r1", 384, 0,
257       "0x8cb91e82a3386d280f5d6f7e50e641df152f7109ed5456b412b1da197fb71123"
258       "acd3a729901d1a71874700133107ec53",
259       "0x7bc382c63d8c150c3c72080ace05afa0c2bea28e4fb22787139165efba91f90f"
260       "8aa5814a503ad4eb04a8c7dd22ce2826",
261       "0x04a8c7dd22ce28268b39b55416f0447c2fb77de107dcd2a62e880ea53eeb62d5"
262       "7cb4390295dbc9943ab78696fa504c11",
263       "0x8cb91e82a3386d280f5d6f7e50e641df152f7109ed5456b31f166e6cac0425a7"
264       "cf3ab6af6b7fc3103b883202e9046565",
265       "0x1d1c64f068cf45ffa2a63a81b7c13f6b8847a3e77ef14fe3db7fcafe0cbd10e8"
266       "e826e03436d646aaef87b2e247d4af1e",
267       "0x8abe1d7520f9c2a45cb1eb8e95cfd55262b70b29feec5864e19c054ff9912928"
268       "0e4646217791811142820341263c5315"
269     },
270
271     { "brainpoolP512r1", 512, 0,
272       "0xaadd9db8dbe9c48b3fd4e6ae33c9fc07cb308db3b3c9d20ed6639cca70330871"
273       "7d4d9b009bc66842aecda12ae6a380e62881ff2f2d82c68528aa6056583a48f3",
274       "0x7830a3318b603b89e2327145ac234cc594cbdd8d3df91610a83441caea9863bc"
275       "2ded5d5aa8253aa10a2ef1c98b9ac8b57f1117a72bf2c7b9e7c1ac4d77fc94ca",
276       "0x3df91610a83441caea9863bc2ded5d5aa8253aa10a2ef1c98b9ac8b57f1117a7"
277       "2bf2c7b9e7c1ac4d77fc94cadc083e67984050b75ebae5dd2809bd638016f723",
278       "0xaadd9db8dbe9c48b3fd4e6ae33c9fc07cb308db3b3c9d20ed6639cca70330870"
279       "553e5c414ca92619418661197fac10471db1d381085ddaddb58796829ca90069",
280       "0x81aee4bdd82ed9645a21322e9c4c6a9385ed9f70b5d916c1b43b62eef4d0098e"
281       "ff3b1f78e2d0d48d50d1687b93b97d5f7c6d5047406a5e688b352209bcb9f822",
282       "0x7dde385d566332ecc0eabfa9cf7822fdf209f70024a57b1aa000c55b881f8111"
283       "b2dcde494a5f485e5bca4bd88a2763aed1ca2b2fa8f0540678cd1e0f3ad80892"
284     },
285
286     { NULL, 0, 0, NULL, NULL, NULL, NULL }
287   };
288
289
290 /* Registered progress function and its callback value. */
291 static void (*progress_cb) (void *, const char*, int, int, int);
292 static void *progress_cb_data;
293
294
295 #define point_init(a)  _gcry_mpi_ec_point_init ((a))
296 #define point_free(a)  _gcry_mpi_ec_point_free ((a))
297
298
299 \f
300 /* Local prototypes. */
301 static gcry_mpi_t gen_k (gcry_mpi_t p, int security_level);
302 static void test_keys (ECC_secret_key * sk, unsigned int nbits);
303 static int check_secret_key (ECC_secret_key * sk);
304 static gpg_err_code_t sign (gcry_mpi_t input, ECC_secret_key *skey,
305                             gcry_mpi_t r, gcry_mpi_t s);
306 static gpg_err_code_t verify (gcry_mpi_t input, ECC_public_key *pkey,
307                               gcry_mpi_t r, gcry_mpi_t s);
308
309
310 static gcry_mpi_t gen_y_2 (gcry_mpi_t x, elliptic_curve_t * base);
311
312
313
314 \f
315 void
316 _gcry_register_pk_ecc_progress (void (*cb) (void *, const char *,
317                                             int, int, int),
318                                 void *cb_data)
319 {
320   progress_cb = cb;
321   progress_cb_data = cb_data;
322 }
323
324 /* static void */
325 /* progress (int c) */
326 /* { */
327 /*   if (progress_cb) */
328 /*     progress_cb (progress_cb_data, "pk_ecc", c, 0, 0); */
329 /* } */
330
331
332 \f
333
334 /* Set the value from S into D.  */
335 static void
336 point_set (mpi_point_t *d, mpi_point_t *s)
337 {
338   mpi_set (d->x, s->x);
339   mpi_set (d->y, s->y);
340   mpi_set (d->z, s->z);
341 }
342
343
344 /*
345  * Release a curve object.
346  */
347 static void
348 curve_free (elliptic_curve_t *E)
349 {
350   mpi_free (E->p); E->p = NULL;
351   mpi_free (E->a); E->a = NULL;
352   mpi_free (E->b);  E->b = NULL;
353   point_free (&E->G);
354   mpi_free (E->n);  E->n = NULL;
355 }
356
357
358 /*
359  * Return a copy of a curve object.
360  */
361 static elliptic_curve_t
362 curve_copy (elliptic_curve_t E)
363 {
364   elliptic_curve_t R;
365
366   R.p = mpi_copy (E.p);
367   R.a = mpi_copy (E.a);
368   R.b = mpi_copy (E.b);
369   point_init (&R.G);
370   point_set (&R.G, &E.G);
371   R.n = mpi_copy (E.n);
372
373   return R;
374 }
375
376
377 /* Helper to scan a hex string. */
378 static gcry_mpi_t
379 scanval (const char *string)
380 {
381   gpg_error_t err;
382   gcry_mpi_t val;
383
384   err = gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL);
385   if (err)
386     log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (err));
387   return val;
388 }
389
390
391
392 \f
393
394 /****************
395  * Solve the right side of the equation that defines a curve.
396  */
397 static gcry_mpi_t
398 gen_y_2 (gcry_mpi_t x, elliptic_curve_t *base)
399 {
400   gcry_mpi_t three, x_3, axb, y;
401
402   three = mpi_alloc_set_ui (3);
403   x_3 = mpi_new (0);
404   axb = mpi_new (0);
405   y   = mpi_new (0);
406
407   mpi_powm (x_3, x, three, base->p);
408   mpi_mulm (axb, base->a, x, base->p);
409   mpi_addm (axb, axb, base->b, base->p);
410   mpi_addm (y, x_3, axb, base->p);
411
412   mpi_free (x_3);
413   mpi_free (axb);
414   mpi_free (three);
415   return y; /* The quadratic value of the coordinate if it exist. */
416 }
417
418
419 /* Generate a random secret scalar k with an order of p
420
421    At the beginning this was identical to the code is in elgamal.c.
422    Later imporved by mmr.   Further simplified by wk.  */
423 static gcry_mpi_t
424 gen_k (gcry_mpi_t p, int security_level)
425 {
426   gcry_mpi_t k;
427   unsigned int nbits;
428
429   nbits = mpi_get_nbits (p);
430   k = mpi_snew (nbits);
431   if (DBG_CIPHER)
432     log_debug ("choosing a random k of %u bits at seclevel %d\n",
433                nbits, security_level);
434
435   gcry_mpi_randomize (k, nbits, security_level);
436
437   mpi_mod (k, k, p);  /*  k = k mod p  */
438
439   return k;
440 }
441
442
443 /* Generate the crypto system setup.  This function takes the NAME of
444    a curve or the desired number of bits and stores at R_CURVE the
445    parameters of the named curve or those of a suitable curve.  The
446    chosen number of bits is stored on R_NBITS.  */
447 static gpg_err_code_t
448 fill_in_curve (unsigned int nbits, const char *name,
449                elliptic_curve_t *curve, unsigned int *r_nbits)
450 {
451   int idx, aliasno;
452   const char *resname = NULL; /* Set to a found curve name.  */
453
454   if (name)
455     {
456       /* First check our native curves.  */
457       for (idx = 0; domain_parms[idx].desc; idx++)
458         if (!strcmp (name, domain_parms[idx].desc))
459           {
460             resname = domain_parms[idx].desc;
461             break;
462           }
463       /* If not found consult the alias table.  */
464       if (!domain_parms[idx].desc)
465         {
466           for (aliasno = 0; curve_aliases[aliasno].name; aliasno++)
467             if (!strcmp (name, curve_aliases[aliasno].other))
468               break;
469           if (curve_aliases[aliasno].name)
470             {
471               for (idx = 0; domain_parms[idx].desc; idx++)
472                 if (!strcmp (curve_aliases[aliasno].name,
473                              domain_parms[idx].desc))
474                   {
475                     resname = domain_parms[idx].desc;
476                     break;
477                   }
478             }
479         }
480     }
481   else
482     {
483       for (idx = 0; domain_parms[idx].desc; idx++)
484         if (nbits == domain_parms[idx].nbits)
485           break;
486     }
487   if (!domain_parms[idx].desc)
488     return GPG_ERR_INV_VALUE;
489
490   /* In fips mode we only support NIST curves.  Note that it is
491      possible to bypass this check by specifying the curve parameters
492      directly.  */
493   if (fips_mode () && !domain_parms[idx].fips )
494     return GPG_ERR_NOT_SUPPORTED;
495
496   *r_nbits = domain_parms[idx].nbits;
497   curve->p = scanval (domain_parms[idx].p);
498   curve->a = scanval (domain_parms[idx].a);
499   curve->b = scanval (domain_parms[idx].b);
500   curve->n = scanval (domain_parms[idx].n);
501   curve->G.x = scanval (domain_parms[idx].g_x);
502   curve->G.y = scanval (domain_parms[idx].g_y);
503   curve->G.z = mpi_alloc_set_ui (1);
504   curve->name = resname;
505
506   return 0;
507 }
508
509
510 /*
511  * First obtain the setup.  Over the finite field randomize an scalar
512  * secret value, and calculate the public point.
513  */
514 static gpg_err_code_t
515 generate_key (ECC_secret_key *sk, unsigned int nbits, const char *name,
516               int transient_key,
517               gcry_mpi_t g_x, gcry_mpi_t g_y,
518               gcry_mpi_t q_x, gcry_mpi_t q_y,
519               const char **r_usedcurve)
520 {
521   gpg_err_code_t err;
522   elliptic_curve_t E;
523   gcry_mpi_t d;
524   mpi_point_t Q;
525   mpi_ec_t ctx;
526   gcry_random_level_t random_level;
527
528   *r_usedcurve = NULL;
529
530   err = fill_in_curve (nbits, name, &E, &nbits);
531   if (err)
532     return err;
533
534   if (DBG_CIPHER)
535     {
536       log_mpidump ("ecgen curve  p", E.p);
537       log_mpidump ("ecgen curve  a", E.a);
538       log_mpidump ("ecgen curve  b", E.b);
539       log_mpidump ("ecgen curve  n", E.n);
540       log_mpidump ("ecgen curve Gx", E.G.x);
541       log_mpidump ("ecgen curve Gy", E.G.y);
542       log_mpidump ("ecgen curve Gz", E.G.z);
543       if (E.name)
544         log_debug   ("ecgen curve used: %s\n", E.name);
545     }
546
547   random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
548   d = gen_k (E.n, random_level);
549
550   /* Compute Q.  */
551   point_init (&Q);
552   ctx = _gcry_mpi_ec_init (E.p, E.a);
553   _gcry_mpi_ec_mul_point (&Q, d, &E.G, ctx);
554
555   /* Copy the stuff to the key structures. */
556   sk->E.p = mpi_copy (E.p);
557   sk->E.a = mpi_copy (E.a);
558   sk->E.b = mpi_copy (E.b);
559   point_init (&sk->E.G);
560   point_set (&sk->E.G, &E.G);
561   sk->E.n = mpi_copy (E.n);
562   point_init (&sk->Q);
563   point_set (&sk->Q, &Q);
564   sk->d    = mpi_copy (d);
565   /* We also return copies of G and Q in affine coordinates if
566      requested.  */
567   if (g_x && g_y)
568     {
569       if (_gcry_mpi_ec_get_affine (g_x, g_y, &sk->E.G, ctx))
570         log_fatal ("ecgen: Failed to get affine coordinates\n");
571     }
572   if (q_x && q_y)
573     {
574       if (_gcry_mpi_ec_get_affine (q_x, q_y, &sk->Q, ctx))
575         log_fatal ("ecgen: Failed to get affine coordinates\n");
576     }
577   _gcry_mpi_ec_free (ctx);
578
579   point_free (&Q);
580   mpi_free (d);
581
582   *r_usedcurve = E.name;
583   curve_free (&E);
584
585   /* Now we can test our keys (this should never fail!).  */
586   test_keys (sk, nbits - 64);
587
588   return 0;
589 }
590
591
592 /*
593  * To verify correct skey it use a random information.
594  * First, encrypt and decrypt this dummy value,
595  * test if the information is recuperated.
596  * Second, test with the sign and verify functions.
597  */
598 static void
599 test_keys (ECC_secret_key *sk, unsigned int nbits)
600 {
601   ECC_public_key pk;
602   gcry_mpi_t test = mpi_new (nbits);
603   mpi_point_t R_;
604   gcry_mpi_t c = mpi_new (nbits);
605   gcry_mpi_t out = mpi_new (nbits);
606   gcry_mpi_t r = mpi_new (nbits);
607   gcry_mpi_t s = mpi_new (nbits);
608
609   if (DBG_CIPHER)
610     log_debug ("Testing key.\n");
611
612   point_init (&R_);
613
614   pk.E = curve_copy (sk->E);
615   point_init (&pk.Q);
616   point_set (&pk.Q, &sk->Q);
617
618   gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM);
619
620   if (sign (test, sk, r, s) )
621     log_fatal ("ECDSA operation: sign failed\n");
622
623   if (verify (test, &pk, r, s))
624     {
625       log_fatal ("ECDSA operation: sign, verify failed\n");
626     }
627
628   if (DBG_CIPHER)
629     log_debug ("ECDSA operation: sign, verify ok.\n");
630
631   point_free (&pk.Q);
632   curve_free (&pk.E);
633
634   point_free (&R_);
635   mpi_free (s);
636   mpi_free (r);
637   mpi_free (out);
638   mpi_free (c);
639   mpi_free (test);
640 }
641
642
643 /*
644  * To check the validity of the value, recalculate the correspondence
645  * between the public value and the secret one.
646  */
647 static int
648 check_secret_key (ECC_secret_key * sk)
649 {
650   mpi_point_t Q;
651   gcry_mpi_t y_2, y2 = mpi_alloc (0);
652   mpi_ec_t ctx;
653
654   /* ?primarity test of 'p' */
655   /*  (...) //!! */
656   /* G in E(F_p) */
657   y_2 = gen_y_2 (sk->E.G.x, &sk->E);   /*  y^2=x^3+a*x+b */
658   mpi_mulm (y2, sk->E.G.y, sk->E.G.y, sk->E.p);      /*  y^2=y*y */
659   if (mpi_cmp (y_2, y2))
660     {
661       if (DBG_CIPHER)
662         log_debug ("Bad check: Point 'G' does not belong to curve 'E'!\n");
663       return (1);
664     }
665   /* G != PaI */
666   if (!mpi_cmp_ui (sk->E.G.z, 0))
667     {
668       if (DBG_CIPHER)
669         log_debug ("Bad check: 'G' cannot be Point at Infinity!\n");
670       return (1);
671     }
672
673   point_init (&Q);
674   ctx = _gcry_mpi_ec_init (sk->E.p, sk->E.a);
675   _gcry_mpi_ec_mul_point (&Q, sk->E.n, &sk->E.G, ctx);
676   if (mpi_cmp_ui (Q.z, 0))
677     {
678       if (DBG_CIPHER)
679         log_debug ("check_secret_key: E is not a curve of order n\n");
680       point_free (&Q);
681       _gcry_mpi_ec_free (ctx);
682       return 1;
683     }
684   /* pubkey cannot be PaI */
685   if (!mpi_cmp_ui (sk->Q.z, 0))
686     {
687       if (DBG_CIPHER)
688         log_debug ("Bad check: Q can not be a Point at Infinity!\n");
689       _gcry_mpi_ec_free (ctx);
690       return (1);
691     }
692   /* pubkey = [d]G over E */
693   _gcry_mpi_ec_mul_point (&Q, sk->d, &sk->E.G, ctx);
694   if ((Q.x == sk->Q.x) && (Q.y == sk->Q.y) && (Q.z == sk->Q.z))
695     {
696       if (DBG_CIPHER)
697         log_debug
698           ("Bad check: There is NO correspondence between 'd' and 'Q'!\n");
699       _gcry_mpi_ec_free (ctx);
700       return (1);
701     }
702   _gcry_mpi_ec_free (ctx);
703   point_free (&Q);
704   return 0;
705 }
706
707
708 /*
709  * Return the signature struct (r,s) from the message hash.  The caller
710  * must have allocated R and S.
711  */
712 static gpg_err_code_t
713 sign (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s)
714 {
715   gpg_err_code_t err = 0;
716   gcry_mpi_t k, dr, sum, k_1, x;
717   mpi_point_t I;
718   mpi_ec_t ctx;
719
720   if (DBG_CIPHER)
721     log_mpidump ("ecdsa sign hash  ", input );
722
723   k = NULL;
724   dr = mpi_alloc (0);
725   sum = mpi_alloc (0);
726   k_1 = mpi_alloc (0);
727   x = mpi_alloc (0);
728   point_init (&I);
729
730   mpi_set_ui (s, 0);
731   mpi_set_ui (r, 0);
732
733   ctx = _gcry_mpi_ec_init (skey->E.p, skey->E.a);
734
735   while (!mpi_cmp_ui (s, 0)) /* s == 0 */
736     {
737       while (!mpi_cmp_ui (r, 0)) /* r == 0 */
738         {
739           /* Note, that we are guaranteed to enter this loop at least
740              once because r has been intialized to 0.  We can't use a
741              do_while because we want to keep the value of R even if S
742              has to be recomputed.  */
743           mpi_free (k);
744           k = gen_k (skey->E.n, GCRY_STRONG_RANDOM);
745           _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx);
746           if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx))
747             {
748               if (DBG_CIPHER)
749                 log_debug ("ecc sign: Failed to get affine coordinates\n");
750               err = GPG_ERR_BAD_SIGNATURE;
751               goto leave;
752             }
753           mpi_mod (r, x, skey->E.n);  /* r = x mod n */
754         }
755       mpi_mulm (dr, skey->d, r, skey->E.n); /* dr = d*r mod n  */
756       mpi_addm (sum, input, dr, skey->E.n); /* sum = hash + (d*r) mod n  */
757       mpi_invm (k_1, k, skey->E.n);         /* k_1 = k^(-1) mod n  */
758       mpi_mulm (s, k_1, sum, skey->E.n);    /* s = k^(-1)*(hash+(d*r)) mod n */
759     }
760
761   if (DBG_CIPHER)
762     {
763       log_mpidump ("ecdsa sign result r ", r);
764       log_mpidump ("ecdsa sign result s ", s);
765     }
766
767  leave:
768   _gcry_mpi_ec_free (ctx);
769   point_free (&I);
770   mpi_free (x);
771   mpi_free (k_1);
772   mpi_free (sum);
773   mpi_free (dr);
774   mpi_free (k);
775
776   return err;
777 }
778
779
780 /*
781  * Check if R and S verifies INPUT.
782  */
783 static gpg_err_code_t
784 verify (gcry_mpi_t input, ECC_public_key *pkey, gcry_mpi_t r, gcry_mpi_t s)
785 {
786   gpg_err_code_t err = 0;
787   gcry_mpi_t h, h1, h2, x, y;
788   mpi_point_t Q, Q1, Q2;
789   mpi_ec_t ctx;
790
791   if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) )
792     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < r < n  failed.  */
793   if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) )
794     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < s < n  failed.  */
795
796   h  = mpi_alloc (0);
797   h1 = mpi_alloc (0);
798   h2 = mpi_alloc (0);
799   x = mpi_alloc (0);
800   y = mpi_alloc (0);
801   point_init (&Q);
802   point_init (&Q1);
803   point_init (&Q2);
804
805   ctx = _gcry_mpi_ec_init (pkey->E.p, pkey->E.a);
806
807   /* h  = s^(-1) (mod n) */
808   mpi_invm (h, s, pkey->E.n);
809 /*   log_mpidump ("   h", h); */
810   /* h1 = hash * s^(-1) (mod n) */
811   mpi_mulm (h1, input, h, pkey->E.n);
812 /*   log_mpidump ("  h1", h1); */
813   /* Q1 = [ hash * s^(-1) ]G  */
814   _gcry_mpi_ec_mul_point (&Q1, h1, &pkey->E.G, ctx);
815 /*   log_mpidump ("Q1.x", Q1.x); */
816 /*   log_mpidump ("Q1.y", Q1.y); */
817 /*   log_mpidump ("Q1.z", Q1.z); */
818   /* h2 = r * s^(-1) (mod n) */
819   mpi_mulm (h2, r, h, pkey->E.n);
820 /*   log_mpidump ("  h2", h2); */
821   /* Q2 = [ r * s^(-1) ]Q */
822   _gcry_mpi_ec_mul_point (&Q2, h2, &pkey->Q, ctx);
823 /*   log_mpidump ("Q2.x", Q2.x); */
824 /*   log_mpidump ("Q2.y", Q2.y); */
825 /*   log_mpidump ("Q2.z", Q2.z); */
826   /* Q  = ([hash * s^(-1)]G) + ([r * s^(-1)]Q) */
827   _gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ctx);
828 /*   log_mpidump (" Q.x", Q.x); */
829 /*   log_mpidump (" Q.y", Q.y); */
830 /*   log_mpidump (" Q.z", Q.z); */
831
832   if (!mpi_cmp_ui (Q.z, 0))
833     {
834       if (DBG_CIPHER)
835           log_debug ("ecc verify: Rejected\n");
836       err = GPG_ERR_BAD_SIGNATURE;
837       goto leave;
838     }
839   if (_gcry_mpi_ec_get_affine (x, y, &Q, ctx))
840     {
841       if (DBG_CIPHER)
842         log_debug ("ecc verify: Failed to get affine coordinates\n");
843       err = GPG_ERR_BAD_SIGNATURE;
844       goto leave;
845     }
846   mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */
847   if (mpi_cmp (x, r))   /* x != r */
848     {
849       if (DBG_CIPHER)
850         {
851           log_mpidump ("     x", x);
852           log_mpidump ("     y", y);
853           log_mpidump ("     r", r);
854           log_mpidump ("     s", s);
855           log_debug ("ecc verify: Not verified\n");
856         }
857       err = GPG_ERR_BAD_SIGNATURE;
858       goto leave;
859     }
860   if (DBG_CIPHER)
861     log_debug ("ecc verify: Accepted\n");
862
863  leave:
864   _gcry_mpi_ec_free (ctx);
865   point_free (&Q2);
866   point_free (&Q1);
867   point_free (&Q);
868   mpi_free (y);
869   mpi_free (x);
870   mpi_free (h2);
871   mpi_free (h1);
872   mpi_free (h);
873   return err;
874 }
875
876
877 \f
878 /*********************************************
879  **************  interface  ******************
880  *********************************************/
881 static gcry_mpi_t
882 ec2os (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t p)
883 {
884   gpg_error_t err;
885   int pbytes = (mpi_get_nbits (p)+7)/8;
886   size_t n;
887   unsigned char *buf, *ptr;
888   gcry_mpi_t result;
889
890   buf = gcry_xmalloc ( 1 + 2*pbytes );
891   *buf = 04; /* Uncompressed point.  */
892   ptr = buf+1;
893   err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, x);
894   if (err)
895     log_fatal ("mpi_print failed: %s\n", gpg_strerror (err));
896   if (n < pbytes)
897     {
898       memmove (ptr+(pbytes-n), ptr, n);
899       memset (ptr, 0, (pbytes-n));
900     }
901   ptr += pbytes;
902   err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, y);
903   if (err)
904     log_fatal ("mpi_print failed: %s\n", gpg_strerror (err));
905   if (n < pbytes)
906     {
907       memmove (ptr+(pbytes-n), ptr, n);
908       memset (ptr, 0, (pbytes-n));
909     }
910
911   err = gcry_mpi_scan (&result, GCRYMPI_FMT_USG, buf, 1+2*pbytes, NULL);
912   if (err)
913     log_fatal ("mpi_scan failed: %s\n", gpg_strerror (err));
914   gcry_free (buf);
915
916   return result;
917 }
918
919
920 /* RESULT must have been initialized and is set on success to the
921    point given by VALUE.  */
922 static gcry_error_t
923 os2ec (mpi_point_t *result, gcry_mpi_t value)
924 {
925   gcry_error_t err;
926   size_t n;
927   unsigned char *buf;
928   gcry_mpi_t x, y;
929
930   n = (mpi_get_nbits (value)+7)/8;
931   buf = gcry_xmalloc (n);
932   err = gcry_mpi_print (GCRYMPI_FMT_USG, buf, n, &n, value);
933   if (err)
934     {
935       gcry_free (buf);
936       return err;
937     }
938   if (n < 1)
939     {
940       gcry_free (buf);
941       return GPG_ERR_INV_OBJ;
942     }
943   if (*buf != 4)
944     {
945       gcry_free (buf);
946       return GPG_ERR_NOT_IMPLEMENTED; /* No support for point compression.  */
947     }
948   if ( ((n-1)%2) )
949     {
950       gcry_free (buf);
951       return GPG_ERR_INV_OBJ;
952     }
953   n = (n-1)/2;
954   err = gcry_mpi_scan (&x, GCRYMPI_FMT_USG, buf+1, n, NULL);
955   if (err)
956     {
957       gcry_free (buf);
958       return err;
959     }
960   err = gcry_mpi_scan (&y, GCRYMPI_FMT_USG, buf+1+n, n, NULL);
961   gcry_free (buf);
962   if (err)
963     {
964       mpi_free (x);
965       return err;
966     }
967
968   mpi_set (result->x, x);
969   mpi_set (result->y, y);
970   mpi_set_ui (result->z, 1);
971
972   mpi_free (x);
973   mpi_free (y);
974
975   return 0;
976 }
977
978
979 /* Extended version of ecc_generate.  */
980 static gcry_err_code_t
981 ecc_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
982                   const gcry_sexp_t genparms,
983                   gcry_mpi_t *skey, gcry_mpi_t **retfactors,
984                   gcry_sexp_t *r_extrainfo)
985 {
986   gpg_err_code_t ec;
987   ECC_secret_key sk;
988   gcry_mpi_t g_x, g_y, q_x, q_y;
989   char *curve_name = NULL;
990   gcry_sexp_t l1;
991   int transient_key = 0;
992   const char *usedcurve = NULL;
993
994   (void)algo;
995   (void)evalue;
996
997   if (genparms)
998     {
999       /* Parse the optional "curve" parameter. */
1000       l1 = gcry_sexp_find_token (genparms, "curve", 0);
1001       if (l1)
1002         {
1003           curve_name = _gcry_sexp_nth_string (l1, 1);
1004           gcry_sexp_release (l1);
1005           if (!curve_name)
1006             return GPG_ERR_INV_OBJ; /* No curve name or value too large. */
1007         }
1008
1009       /* Parse the optional transient-key flag.  */
1010       l1 = gcry_sexp_find_token (genparms, "transient-key", 0);
1011       if (l1)
1012         {
1013           transient_key = 1;
1014           gcry_sexp_release (l1);
1015         }
1016     }
1017
1018   /* NBITS is required if no curve name has been given.  */
1019   if (!nbits && !curve_name)
1020     return GPG_ERR_NO_OBJ; /* No NBITS parameter. */
1021
1022   g_x = mpi_new (0);
1023   g_y = mpi_new (0);
1024   q_x = mpi_new (0);
1025   q_y = mpi_new (0);
1026   ec = generate_key (&sk, nbits, curve_name, transient_key, g_x, g_y, q_x, q_y,
1027                      &usedcurve);
1028   gcry_free (curve_name);
1029   if (ec)
1030     return ec;
1031   if (usedcurve)  /* Fixme: No error return checking.  */
1032     gcry_sexp_build (r_extrainfo, NULL, "(curve %s)", usedcurve);
1033
1034   skey[0] = sk.E.p;
1035   skey[1] = sk.E.a;
1036   skey[2] = sk.E.b;
1037   skey[3] = ec2os (g_x, g_y, sk.E.p);
1038   skey[4] = sk.E.n;
1039   skey[5] = ec2os (q_x, q_y, sk.E.p);
1040   skey[6] = sk.d;
1041
1042   mpi_free (g_x);
1043   mpi_free (g_y);
1044   mpi_free (q_x);
1045   mpi_free (q_y);
1046
1047   point_free (&sk.E.G);
1048   point_free (&sk.Q);
1049
1050   /* Make an empty list of factors.  */
1051   *retfactors = gcry_calloc ( 1, sizeof **retfactors );
1052   if (!*retfactors)
1053     return gpg_err_code_from_syserror ();  /* Fixme: relase mem?  */
1054
1055   if (DBG_CIPHER)
1056     {
1057       log_mpidump ("ecgen result p", skey[0]);
1058       log_mpidump ("ecgen result a", skey[1]);
1059       log_mpidump ("ecgen result b", skey[2]);
1060       log_mpidump ("ecgen result G", skey[3]);
1061       log_mpidump ("ecgen result n", skey[4]);
1062       log_mpidump ("ecgen result Q", skey[5]);
1063       log_mpidump ("ecgen result d", skey[6]);
1064     }
1065
1066   return 0;
1067 }
1068
1069
1070 static gcry_err_code_t
1071 ecc_generate (int algo, unsigned int nbits, unsigned long evalue,
1072               gcry_mpi_t *skey, gcry_mpi_t **retfactors)
1073 {
1074   (void)evalue;
1075   return ecc_generate_ext (algo, nbits, 0, NULL, skey, retfactors, NULL);
1076 }
1077
1078
1079 /* Return the parameters of the curve NAME in an MPI array.  */
1080 static gcry_err_code_t
1081 ecc_get_param (const char *name, gcry_mpi_t *pkey)
1082 {
1083   gpg_err_code_t err;
1084   unsigned int nbits;
1085   elliptic_curve_t E;
1086   mpi_ec_t ctx;
1087   gcry_mpi_t g_x, g_y;
1088
1089   err = fill_in_curve (0, name, &E, &nbits);
1090   if (err)
1091     return err;
1092
1093   g_x = mpi_new (0);
1094   g_y = mpi_new (0);
1095   ctx = _gcry_mpi_ec_init (E.p, E.a);
1096   if (_gcry_mpi_ec_get_affine (g_x, g_y, &E.G, ctx))
1097     log_fatal ("ecc get param: Failed to get affine coordinates\n");
1098   _gcry_mpi_ec_free (ctx);
1099   point_free (&E.G);
1100
1101   pkey[0] = E.p;
1102   pkey[1] = E.a;
1103   pkey[2] = E.b;
1104   pkey[3] = ec2os (g_x, g_y, E.p);
1105   pkey[4] = E.n;
1106   pkey[5] = NULL;
1107
1108   mpi_free (g_x);
1109   mpi_free (g_y);
1110
1111   return 0;
1112 }
1113
1114
1115 /* Return the parameters of the curve NAME as an S-expression.  */
1116 static gcry_sexp_t
1117 ecc_get_param_sexp (const char *name)
1118 {
1119   gcry_mpi_t pkey[6];
1120   gcry_sexp_t result;
1121   int i;
1122
1123   if (ecc_get_param (name, pkey))
1124     return NULL;
1125
1126   if (gcry_sexp_build (&result, NULL,
1127                        "(public-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)))",
1128                        pkey[0], pkey[1], pkey[2], pkey[3], pkey[4]))
1129     result = NULL;
1130
1131   for (i=0; pkey[i]; i++)
1132     gcry_mpi_release (pkey[i]);
1133
1134   return result;
1135 }
1136
1137
1138 /* Return the name matching the parameters in PKEY.  */
1139 static const char *
1140 ecc_get_curve (gcry_mpi_t *pkey, int iterator, unsigned int *r_nbits)
1141 {
1142   gpg_err_code_t err;
1143   elliptic_curve_t E;
1144   int idx;
1145   gcry_mpi_t tmp;
1146   const char *result = NULL;
1147
1148   if (r_nbits)
1149     *r_nbits = 0;
1150
1151   if (!pkey)
1152     {
1153       idx = iterator;
1154       if (idx >= 0 && idx < DIM (domain_parms))
1155         {
1156           result = domain_parms[idx].desc;
1157           if (r_nbits)
1158             *r_nbits = domain_parms[idx].nbits;
1159         }
1160       return result;
1161     }
1162
1163   if (!pkey[0] || !pkey[1] || !pkey[2] || !pkey[3] || !pkey[4])
1164     return NULL;
1165
1166   E.p = pkey[0];
1167   E.a = pkey[1];
1168   E.b = pkey[2];
1169   point_init (&E.G);
1170   err = os2ec (&E.G, pkey[3]);
1171   if (err)
1172     {
1173       point_free (&E.G);
1174       return NULL;
1175     }
1176   E.n = pkey[4];
1177
1178   for (idx = 0; domain_parms[idx].desc; idx++)
1179     {
1180       tmp = scanval (domain_parms[idx].p);
1181       if (!mpi_cmp (tmp, E.p))
1182         {
1183           mpi_free (tmp);
1184           tmp = scanval (domain_parms[idx].a);
1185           if (!mpi_cmp (tmp, E.a))
1186             {
1187               mpi_free (tmp);
1188               tmp = scanval (domain_parms[idx].b);
1189               if (!mpi_cmp (tmp, E.b))
1190                 {
1191                   mpi_free (tmp);
1192                   tmp = scanval (domain_parms[idx].n);
1193                   if (!mpi_cmp (tmp, E.n))
1194                     {
1195                       mpi_free (tmp);
1196                       tmp = scanval (domain_parms[idx].g_x);
1197                       if (!mpi_cmp (tmp, E.G.x))
1198                         {
1199                           mpi_free (tmp);
1200                           tmp = scanval (domain_parms[idx].g_y);
1201                           if (!mpi_cmp (tmp, E.G.y))
1202                             {
1203                               result = domain_parms[idx].desc;
1204                               if (r_nbits)
1205                                 *r_nbits = domain_parms[idx].nbits;
1206                               break;
1207                             }
1208                         }
1209                     }
1210                 }
1211             }
1212         }
1213       mpi_free (tmp);
1214     }
1215
1216   point_free (&E.G);
1217
1218   return result;
1219 }
1220
1221
1222 static gcry_err_code_t
1223 ecc_check_secret_key (int algo, gcry_mpi_t *skey)
1224 {
1225   gpg_err_code_t err;
1226   ECC_secret_key sk;
1227
1228   (void)algo;
1229
1230   /* FIXME:  This check looks a bit fishy:  Now long is the array?  */
1231   if (!skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] || !skey[5]
1232       || !skey[6])
1233     return GPG_ERR_BAD_MPI;
1234
1235   sk.E.p = skey[0];
1236   sk.E.a = skey[1];
1237   sk.E.b = skey[2];
1238   point_init (&sk.E.G);
1239   err = os2ec (&sk.E.G, skey[3]);
1240   if (err)
1241     {
1242       point_free (&sk.E.G);
1243       return err;
1244     }
1245   sk.E.n = skey[4];
1246   point_init (&sk.Q);
1247   err = os2ec (&sk.Q, skey[5]);
1248   if (err)
1249     {
1250       point_free (&sk.E.G);
1251       point_free (&sk.Q);
1252       return err;
1253     }
1254
1255   sk.d = skey[6];
1256
1257   if (check_secret_key (&sk))
1258     {
1259       point_free (&sk.E.G);
1260       point_free (&sk.Q);
1261       return GPG_ERR_BAD_SECKEY;
1262     }
1263   point_free (&sk.E.G);
1264   point_free (&sk.Q);
1265   return 0;
1266 }
1267
1268
1269 static gcry_err_code_t
1270 ecc_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
1271 {
1272   gpg_err_code_t err;
1273   ECC_secret_key sk;
1274
1275   (void)algo;
1276
1277   if (!data || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4]
1278       || !skey[5] || !skey[6] )
1279     return GPG_ERR_BAD_MPI;
1280
1281   sk.E.p = skey[0];
1282   sk.E.a = skey[1];
1283   sk.E.b = skey[2];
1284   point_init (&sk.E.G);
1285   err = os2ec (&sk.E.G, skey[3]);
1286   if (err)
1287     {
1288       point_free (&sk.E.G);
1289       return err;
1290     }
1291   sk.E.n = skey[4];
1292   point_init (&sk.Q);
1293   err = os2ec (&sk.Q, skey[5]);
1294   if (err)
1295     {
1296       point_free (&sk.E.G);
1297       point_free (&sk.Q);
1298       return err;
1299     }
1300   sk.d = skey[6];
1301
1302   resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.E.p));
1303   resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.E.p));
1304   err = sign (data, &sk, resarr[0], resarr[1]);
1305   if (err)
1306     {
1307       mpi_free (resarr[0]);
1308       mpi_free (resarr[1]);
1309       resarr[0] = NULL; /* Mark array as released.  */
1310     }
1311   point_free (&sk.E.G);
1312   point_free (&sk.Q);
1313   return err;
1314 }
1315
1316
1317 static gcry_err_code_t
1318 ecc_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
1319             int (*cmp)(void *, gcry_mpi_t), void *opaquev)
1320 {
1321   gpg_err_code_t err;
1322   ECC_public_key pk;
1323
1324   (void)algo;
1325   (void)cmp;
1326   (void)opaquev;
1327
1328   if (!data[0] || !data[1] || !hash || !pkey[0] || !pkey[1] || !pkey[2]
1329       || !pkey[3] || !pkey[4] || !pkey[5] )
1330     return GPG_ERR_BAD_MPI;
1331
1332   pk.E.p = pkey[0];
1333   pk.E.a = pkey[1];
1334   pk.E.b = pkey[2];
1335   point_init (&pk.E.G);
1336   err = os2ec (&pk.E.G, pkey[3]);
1337   if (err)
1338     {
1339       point_free (&pk.E.G);
1340       return err;
1341     }
1342   pk.E.n = pkey[4];
1343   point_init (&pk.Q);
1344   err = os2ec (&pk.Q, pkey[5]);
1345   if (err)
1346     {
1347       point_free (&pk.E.G);
1348       point_free (&pk.Q);
1349       return err;
1350     }
1351
1352   err = verify (hash, &pk, data[0], data[1]);
1353
1354   point_free (&pk.E.G);
1355   point_free (&pk.Q);
1356   return err;
1357 }
1358
1359
1360 /* ecdh raw is classic 2-round DH protocol published in 1976.
1361  *
1362  * Overview of ecc_encrypt_raw and ecc_decrypt_raw.
1363  *
1364  * As with any PK operation, encrypt version uses a public key and
1365  * decrypt -- private.
1366  *
1367  * Symbols used below:
1368  *     G - field generator point
1369  *     d - private long-term scalar
1370  *    dG - public long-term key
1371  *     k - ephemeral scalar
1372  *    kG - ephemeral public key
1373  *   dkG - shared secret
1374  *
1375  * ecc_encrypt_raw description:
1376  *   input:
1377  *     data[0] : private scalar (k)
1378  *   output:
1379  *     result[0] : shared point (kdG)
1380  *     result[1] : generated ephemeral public key (kG)
1381  *
1382  * ecc_decrypt_raw description:
1383  *   input:
1384  *     data[0] : a point kG (ephemeral public key)
1385  *   output:
1386  *     result[0] : shared point (kdG)
1387  */
1388 static gcry_err_code_t
1389 ecc_encrypt_raw (int algo, gcry_mpi_t *resarr, gcry_mpi_t k,
1390                  gcry_mpi_t *pkey, int flags)
1391 {
1392   ECC_public_key pk;
1393   mpi_ec_t ctx;
1394   gcry_mpi_t result[2];
1395   int err;
1396
1397   (void)algo;
1398   (void)flags;
1399
1400   if (!k
1401       || !pkey[0] || !pkey[1] || !pkey[2] || !pkey[3] || !pkey[4] || !pkey[5])
1402     return GPG_ERR_BAD_MPI;
1403
1404   pk.E.p = pkey[0];
1405   pk.E.a = pkey[1];
1406   pk.E.b = pkey[2];
1407   point_init (&pk.E.G);
1408   err = os2ec (&pk.E.G, pkey[3]);
1409   if (err)
1410     {
1411       point_free (&pk.E.G);
1412       return err;
1413     }
1414   pk.E.n = pkey[4];
1415   point_init (&pk.Q);
1416   err = os2ec (&pk.Q, pkey[5]);
1417   if (err)
1418     {
1419       point_free (&pk.E.G);
1420       point_free (&pk.Q);
1421       return err;
1422     }
1423
1424   ctx = _gcry_mpi_ec_init (pk.E.p, pk.E.a);
1425
1426   /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so */
1427   {
1428     mpi_point_t R;      /* Result that we return.  */
1429     gcry_mpi_t x, y;
1430
1431     x = mpi_new (0);
1432     y = mpi_new (0);
1433
1434     point_init (&R);
1435
1436     /* R = kQ  <=>  R = kdG  */
1437     _gcry_mpi_ec_mul_point (&R, k, &pk.Q, ctx);
1438
1439     if (_gcry_mpi_ec_get_affine (x, y, &R, ctx))
1440       log_fatal ("ecdh: Failed to get affine coordinates for kdG\n");
1441
1442     result[0] = ec2os (x, y, pk.E.p);
1443
1444     /* R = kG */
1445     _gcry_mpi_ec_mul_point (&R, k, &pk.E.G, ctx);
1446
1447     if (_gcry_mpi_ec_get_affine (x, y, &R, ctx))
1448       log_fatal ("ecdh: Failed to get affine coordinates for kG\n");
1449
1450     result[1] = ec2os (x, y, pk.E.p);
1451
1452     mpi_free (x);
1453     mpi_free (y);
1454
1455     point_free (&R);
1456   }
1457
1458   _gcry_mpi_ec_free (ctx);
1459   point_free (&pk.E.G);
1460   point_free (&pk.Q);
1461
1462   if (!result[0] || !result[1])
1463     {
1464       mpi_free (result[0]);
1465       mpi_free (result[1]);
1466       return GPG_ERR_ENOMEM;
1467     }
1468
1469   /* Success.  */
1470   resarr[0] = result[0];
1471   resarr[1] = result[1];
1472
1473   return 0;
1474 }
1475
1476 /*  input:
1477  *     data[0] : a point kG (ephemeral public key)
1478  *   output:
1479  *     resaddr[0] : shared point kdG
1480  *
1481  *  see ecc_encrypt_raw for details.
1482  */
1483 static gcry_err_code_t
1484 ecc_decrypt_raw (int algo, gcry_mpi_t *result, gcry_mpi_t *data,
1485                  gcry_mpi_t *skey, int flags)
1486 {
1487   ECC_secret_key sk;
1488   mpi_point_t R;        /* Result that we return.  */
1489   mpi_point_t kG;
1490   mpi_ec_t ctx;
1491   gcry_mpi_t r;
1492   int err;
1493
1494   (void)algo;
1495   (void)flags;
1496
1497   *result = NULL;
1498
1499   if (!data || !data[0]
1500       || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4]
1501       || !skey[5] || !skey[6] )
1502     return GPG_ERR_BAD_MPI;
1503
1504   point_init (&kG);
1505   err = os2ec (&kG, data[0]);
1506   if (err)
1507     {
1508       point_free (&kG);
1509       return err;
1510     }
1511
1512
1513   sk.E.p = skey[0];
1514   sk.E.a = skey[1];
1515   sk.E.b = skey[2];
1516   point_init (&sk.E.G);
1517   err = os2ec (&sk.E.G, skey[3]);
1518   if (err)
1519     {
1520       point_free (&kG);
1521       point_free (&sk.E.G);
1522       return err;
1523     }
1524   sk.E.n = skey[4];
1525   point_init (&sk.Q);
1526   err = os2ec (&sk.Q, skey[5]);
1527   if (err)
1528     {
1529       point_free (&kG);
1530       point_free (&sk.E.G);
1531       point_free (&sk.Q);
1532       return err;
1533     }
1534   sk.d = skey[6];
1535
1536   ctx = _gcry_mpi_ec_init (sk.E.p, sk.E.a);
1537
1538   /* R = dkG */
1539   point_init (&R);
1540   _gcry_mpi_ec_mul_point (&R, sk.d, &kG, ctx);
1541
1542   point_free (&kG);
1543
1544   /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so:  */
1545   {
1546     gcry_mpi_t x, y;
1547
1548     x = mpi_new (0);
1549     y = mpi_new (0);
1550
1551     if (_gcry_mpi_ec_get_affine (x, y, &R, ctx))
1552       log_fatal ("ecdh: Failed to get affine coordinates\n");
1553
1554     r = ec2os (x, y, sk.E.p);
1555     mpi_free (x);
1556     mpi_free (y);
1557   }
1558
1559   point_free (&R);
1560   _gcry_mpi_ec_free (ctx);
1561   point_free (&kG);
1562   point_free (&sk.E.G);
1563   point_free (&sk.Q);
1564
1565   if (!r)
1566     return GPG_ERR_ENOMEM;
1567
1568   /* Success.  */
1569
1570   *result = r;
1571
1572   return 0;
1573 }
1574
1575
1576 static unsigned int
1577 ecc_get_nbits (int algo, gcry_mpi_t *pkey)
1578 {
1579   (void)algo;
1580
1581   return mpi_get_nbits (pkey[0]);
1582 }
1583
1584
1585 /* See rsa.c for a description of this function.  */
1586 static gpg_err_code_t
1587 compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
1588 {
1589 #define N_COMPONENTS 6
1590   static const char names[N_COMPONENTS+1] = "pabgnq";
1591   gpg_err_code_t ec = 0;
1592   gcry_sexp_t l1;
1593   gcry_mpi_t values[N_COMPONENTS];
1594   int idx;
1595
1596   /* Clear the values for easier error cleanup.  */
1597   for (idx=0; idx < N_COMPONENTS; idx++)
1598     values[idx] = NULL;
1599
1600   /* Fill values with all provided parameters.  */
1601   for (idx=0; idx < N_COMPONENTS; idx++)
1602     {
1603       l1 = gcry_sexp_find_token (keyparam, names+idx, 1);
1604       if (l1)
1605         {
1606           values[idx] = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1607           gcry_sexp_release (l1);
1608           if (!values[idx])
1609             {
1610               ec = GPG_ERR_INV_OBJ;
1611               goto leave;
1612             }
1613         }
1614     }
1615
1616   /* Check whether a curve parameter is available and use that to fill
1617      in missing values.  */
1618   l1 = gcry_sexp_find_token (keyparam, "curve", 5);
1619   if (l1)
1620     {
1621       char *curve;
1622       gcry_mpi_t tmpvalues[N_COMPONENTS];
1623
1624       for (idx = 0; idx < N_COMPONENTS; idx++)
1625         tmpvalues[idx] = NULL;
1626
1627       curve = _gcry_sexp_nth_string (l1, 1);
1628       gcry_sexp_release (l1);
1629       if (!curve)
1630         {
1631           ec = GPG_ERR_INV_OBJ; /* Name missing or out of core. */
1632           goto leave;
1633         }
1634       ec = ecc_get_param (curve, tmpvalues);
1635       gcry_free (curve);
1636       if (ec)
1637         goto leave;
1638
1639       for (idx = 0; idx < N_COMPONENTS; idx++)
1640         {
1641           if (!values[idx])
1642             values[idx] = tmpvalues[idx];
1643           else
1644             mpi_free (tmpvalues[idx]);
1645         }
1646     }
1647
1648   /* Check that all parameters are known and normalize all MPIs (that
1649      should not be required but we use an internal function later and
1650      thus we better make 100% sure that they are normalized). */
1651   for (idx = 0; idx < N_COMPONENTS; idx++)
1652     if (!values[idx])
1653       {
1654         ec = GPG_ERR_NO_OBJ;
1655         goto leave;
1656       }
1657     else
1658       _gcry_mpi_normalize (values[idx]);
1659
1660   /* Hash them all.  */
1661   for (idx = 0; idx < N_COMPONENTS; idx++)
1662     {
1663       char buf[30];
1664       unsigned char *rawmpi;
1665       unsigned int rawmpilen;
1666
1667       rawmpi = _gcry_mpi_get_buffer (values[idx], &rawmpilen, NULL);
1668       if (!rawmpi)
1669         {
1670           ec = gpg_err_code_from_syserror ();
1671           goto leave;
1672         }
1673       snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], rawmpilen);
1674       gcry_md_write (md, buf, strlen (buf));
1675       gcry_md_write (md, rawmpi, rawmpilen);
1676       gcry_md_write (md, ")", 1);
1677       gcry_free (rawmpi);
1678     }
1679
1680  leave:
1681   for (idx = 0; idx < N_COMPONENTS; idx++)
1682     _gcry_mpi_release (values[idx]);
1683
1684   return ec;
1685 #undef N_COMPONENTS
1686 }
1687
1688
1689
1690
1691 \f
1692 /*
1693      Self-test section.
1694  */
1695
1696
1697 static gpg_err_code_t
1698 selftests_ecdsa (selftest_report_func_t report)
1699 {
1700   const char *what;
1701   const char *errtxt;
1702
1703   what = "low-level";
1704   errtxt = NULL; /*selftest ();*/
1705   if (errtxt)
1706     goto failed;
1707
1708   /* FIXME:  need more tests.  */
1709
1710   return 0; /* Succeeded. */
1711
1712  failed:
1713   if (report)
1714     report ("pubkey", GCRY_PK_ECDSA, what, errtxt);
1715   return GPG_ERR_SELFTEST_FAILED;
1716 }
1717
1718
1719 /* Run a full self-test for ALGO and return 0 on success.  */
1720 static gpg_err_code_t
1721 run_selftests (int algo, int extended, selftest_report_func_t report)
1722 {
1723   gpg_err_code_t ec;
1724
1725   (void)extended;
1726
1727   switch (algo)
1728     {
1729     case GCRY_PK_ECDSA:
1730       ec = selftests_ecdsa (report);
1731       break;
1732     default:
1733       ec = GPG_ERR_PUBKEY_ALGO;
1734       break;
1735
1736     }
1737   return ec;
1738 }
1739
1740
1741
1742 \f
1743 static const char *ecdsa_names[] =
1744   {
1745     "ecdsa",
1746     "ecc",
1747     NULL,
1748   };
1749 static const char *ecdh_names[] =
1750   {
1751     "ecdh",
1752     "ecc",
1753     NULL,
1754   };
1755
1756 gcry_pk_spec_t _gcry_pubkey_spec_ecdsa =
1757   {
1758     "ECDSA", ecdsa_names,
1759     "pabgnq", "pabgnqd", "", "rs", "pabgnq",
1760     GCRY_PK_USAGE_SIGN,
1761     ecc_generate,
1762     ecc_check_secret_key,
1763     NULL,
1764     NULL,
1765     ecc_sign,
1766     ecc_verify,
1767     ecc_get_nbits
1768   };
1769
1770 gcry_pk_spec_t _gcry_pubkey_spec_ecdh =
1771   {
1772     "ECDH", ecdh_names,
1773     "pabgnq", "pabgnqd", "se", "", "pabgnq",
1774     GCRY_PK_USAGE_ENCR,
1775     ecc_generate,
1776     ecc_check_secret_key,
1777     ecc_encrypt_raw,
1778     ecc_decrypt_raw,
1779     NULL,
1780     NULL,
1781     ecc_get_nbits
1782   };
1783
1784
1785 pk_extra_spec_t _gcry_pubkey_extraspec_ecdsa =
1786   {
1787     run_selftests,
1788     ecc_generate_ext,
1789     compute_keygrip,
1790     ecc_get_param,
1791     ecc_get_curve,
1792     ecc_get_param_sexp
1793   };