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