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