Changed ecdh parameter names and fixed MPI allocation.
[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.  */
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 static gcry_err_code_t
1111 ecc_check_secret_key (int algo, gcry_mpi_t *skey)
1112 {
1113   gpg_err_code_t err;
1114   ECC_secret_key sk;
1115
1116   (void)algo;
1117
1118   /* FIXME:  This check looks a bit fishy:  Now long is the array?  */
1119   if (!skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] || !skey[5]
1120       || !skey[6])
1121     return GPG_ERR_BAD_MPI;
1122
1123   sk.E.p = skey[0];
1124   sk.E.a = skey[1];
1125   sk.E.b = skey[2];
1126   point_init (&sk.E.G);
1127   err = os2ec (&sk.E.G, skey[3]);
1128   if (err)
1129     {
1130       point_free (&sk.E.G);
1131       return err;
1132     }
1133   sk.E.n = skey[4];
1134   point_init (&sk.Q);
1135   err = os2ec (&sk.Q, skey[5]);
1136   if (err)
1137     {
1138       point_free (&sk.E.G);
1139       point_free (&sk.Q);
1140       return err;
1141     }
1142
1143   sk.d = skey[6];
1144
1145   if (check_secret_key (&sk))
1146     {
1147       point_free (&sk.E.G);
1148       point_free (&sk.Q);
1149       return GPG_ERR_BAD_SECKEY;
1150     }
1151   point_free (&sk.E.G);
1152   point_free (&sk.Q);
1153   return 0;
1154 }
1155
1156
1157 static gcry_err_code_t
1158 ecc_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
1159 {
1160   gpg_err_code_t err;
1161   ECC_secret_key sk;
1162
1163   (void)algo;
1164
1165   if (!data || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4]
1166       || !skey[5] || !skey[6] )
1167     return GPG_ERR_BAD_MPI;
1168
1169   sk.E.p = skey[0];
1170   sk.E.a = skey[1];
1171   sk.E.b = skey[2];
1172   point_init (&sk.E.G);
1173   err = os2ec (&sk.E.G, skey[3]);
1174   if (err)
1175     {
1176       point_free (&sk.E.G);
1177       return err;
1178     }
1179   sk.E.n = skey[4];
1180   point_init (&sk.Q);
1181   err = os2ec (&sk.Q, skey[5]);
1182   if (err)
1183     {
1184       point_free (&sk.E.G);
1185       point_free (&sk.Q);
1186       return err;
1187     }
1188   sk.d = skey[6];
1189
1190   resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.E.p));
1191   resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.E.p));
1192   err = sign (data, &sk, resarr[0], resarr[1]);
1193   if (err)
1194     {
1195       mpi_free (resarr[0]);
1196       mpi_free (resarr[1]);
1197       resarr[0] = NULL; /* Mark array as released.  */
1198     }
1199   point_free (&sk.E.G);
1200   point_free (&sk.Q);
1201   return err;
1202 }
1203
1204
1205 static gcry_err_code_t
1206 ecc_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
1207             int (*cmp)(void *, gcry_mpi_t), void *opaquev)
1208 {
1209   gpg_err_code_t err;
1210   ECC_public_key pk;
1211
1212   (void)algo;
1213   (void)cmp;
1214   (void)opaquev;
1215
1216   if (!data[0] || !data[1] || !hash || !pkey[0] || !pkey[1] || !pkey[2]
1217       || !pkey[3] || !pkey[4] || !pkey[5] )
1218     return GPG_ERR_BAD_MPI;
1219
1220   pk.E.p = pkey[0];
1221   pk.E.a = pkey[1];
1222   pk.E.b = pkey[2];
1223   point_init (&pk.E.G);
1224   err = os2ec (&pk.E.G, pkey[3]);
1225   if (err)
1226     {
1227       point_free (&pk.E.G);
1228       return err;
1229     }
1230   pk.E.n = pkey[4];
1231   point_init (&pk.Q);
1232   err = os2ec (&pk.Q, pkey[5]);
1233   if (err)
1234     {
1235       point_free (&pk.E.G);
1236       point_free (&pk.Q);
1237       return err;
1238     }
1239
1240   err = verify (hash, &pk, data[0], data[1]);
1241
1242   point_free (&pk.E.G);
1243   point_free (&pk.Q);
1244   return err;
1245 }
1246
1247
1248 /* ecdh raw is classic 2-round DH protocol published in 1976.
1249  *
1250  * Overview of ecc_encrypt_raw and ecc_decrypt_raw.
1251  *
1252  * As with any PK operation, encrypt version uses a public key and
1253  * decrypt -- private.
1254  *
1255  * Symbols used below:
1256  *     G - field generator point
1257  *     d - private long-term scalar
1258  *    dG - public long-term key
1259  *     k - ephemeral scalar
1260  *    kG - ephemeral public key
1261  *   dkG - shared secret
1262  *
1263  * ecc_encrypt_raw description:
1264  *   input:
1265  *     data[0] : private scalar (k)
1266  *   output:
1267  *     result[0] : shared point (kdG)
1268  *     result[1] : generated ephemeral public key (kG)
1269  *
1270  * ecc_decrypt_raw description:
1271  *   input:
1272  *     data[0] : a point kG (ephemeral public key)
1273  *   output:
1274  *     result[0] : shared point (kdG)
1275  */
1276 static gcry_err_code_t
1277 ecc_encrypt_raw (int algo, gcry_mpi_t *resarr, gcry_mpi_t k,
1278                  gcry_mpi_t *pkey, int flags)
1279 {
1280   ECC_public_key pk;
1281   mpi_ec_t ctx;
1282   gcry_mpi_t result[2];
1283   int err;
1284
1285   (void)algo;
1286   (void)flags;
1287
1288   if (!k
1289       || !pkey[0] || !pkey[1] || !pkey[2] || !pkey[3] || !pkey[4] || !pkey[5])
1290     return GPG_ERR_BAD_MPI;
1291
1292   pk.E.p = pkey[0];
1293   pk.E.a = pkey[1];
1294   pk.E.b = pkey[2];
1295   point_init (&pk.E.G);
1296   err = os2ec (&pk.E.G, pkey[3]);
1297   if (err)
1298     {
1299       point_free (&pk.E.G);
1300       return err;
1301     }
1302   pk.E.n = pkey[4];
1303   point_init (&pk.Q);
1304   err = os2ec (&pk.Q, pkey[5]);
1305   if (err)
1306     {
1307       point_free (&pk.E.G);
1308       point_free (&pk.Q);
1309       return err;
1310     }
1311
1312   ctx = _gcry_mpi_ec_init (pk.E.p, pk.E.a);
1313
1314   /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so */
1315   {
1316     mpi_point_t R;      /* Result that we return.  */
1317     gcry_mpi_t x, y;
1318
1319     x = mpi_new (0);
1320     y = mpi_new (0);
1321
1322     point_init (&R);
1323
1324     /* R = kQ  <=>  R = kdG  */
1325     _gcry_mpi_ec_mul_point (&R, k, &pk.Q, ctx);
1326
1327     if (_gcry_mpi_ec_get_affine (x, y, &R, ctx))
1328       log_fatal ("ecdh: Failed to get affine coordinates for kdG\n");
1329
1330     result[0] = ec2os (x, y, pk.E.p);
1331
1332     /* R = kG */
1333     _gcry_mpi_ec_mul_point (&R, k, &pk.E.G, ctx);
1334
1335     if (_gcry_mpi_ec_get_affine (x, y, &R, ctx))
1336       log_fatal ("ecdh: Failed to get affine coordinates for kG\n");
1337
1338     result[1] = ec2os (x, y, pk.E.p);
1339
1340     mpi_free (x);
1341     mpi_free (y);
1342
1343     point_free (&R);
1344   }
1345
1346   _gcry_mpi_ec_free (ctx);
1347   point_free (&pk.E.G);
1348   point_free (&pk.Q);
1349
1350   if (!result[0] || !result[1])
1351     {
1352       mpi_free (result[0]);
1353       mpi_free (result[1]);
1354       return GPG_ERR_ENOMEM;
1355     }
1356
1357   /* Success.  */
1358   resarr[0] = result[0];
1359   resarr[1] = result[1];
1360
1361   return 0;
1362 }
1363
1364 /*  input:
1365  *     data[0] : a point kG (ephemeral public key)
1366  *   output:
1367  *     resaddr[0] : shared point kdG
1368  *
1369  *  see ecc_encrypt_raw for details.
1370  */
1371 static gcry_err_code_t
1372 ecc_decrypt_raw (int algo, gcry_mpi_t *result, gcry_mpi_t *data,
1373                  gcry_mpi_t *skey, int flags)
1374 {
1375   ECC_secret_key sk;
1376   mpi_point_t R;        /* Result that we return.  */
1377   mpi_point_t kG;
1378   mpi_ec_t ctx;
1379   gcry_mpi_t r;
1380   int err;
1381
1382   (void)algo;
1383   (void)flags;
1384
1385   *result = NULL;
1386
1387   if (!data || !data[0]
1388       || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4]
1389       || !skey[5] || !skey[6] )
1390     return GPG_ERR_BAD_MPI;
1391
1392   point_init (&kG);
1393   err = os2ec (&kG, data[0]);
1394   if (err)
1395     {
1396       point_free (&kG);
1397       return err;
1398     }
1399
1400
1401   sk.E.p = skey[0];
1402   sk.E.a = skey[1];
1403   sk.E.b = skey[2];
1404   point_init (&sk.E.G);
1405   err = os2ec (&sk.E.G, skey[3]);
1406   if (err)
1407     {
1408       point_free (&kG);
1409       point_free (&sk.E.G);
1410       return err;
1411     }
1412   sk.E.n = skey[4];
1413   point_init (&sk.Q);
1414   err = os2ec (&sk.Q, skey[5]);
1415   if (err)
1416     {
1417       point_free (&kG);
1418       point_free (&sk.E.G);
1419       point_free (&sk.Q);
1420       return err;
1421     }
1422   sk.d = skey[6];
1423
1424   ctx = _gcry_mpi_ec_init (sk.E.p, sk.E.a);
1425
1426   /* R = dkG */
1427   point_init (&R);
1428   _gcry_mpi_ec_mul_point (&R, sk.d, &kG, ctx);
1429
1430   point_free (&kG);
1431
1432   /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so:  */
1433   {
1434     gcry_mpi_t x, y;
1435
1436     x = mpi_new (0);
1437     y = mpi_new (0);
1438
1439     if (_gcry_mpi_ec_get_affine (x, y, &R, ctx))
1440       log_fatal ("ecdh: Failed to get affine coordinates\n");
1441
1442     r = ec2os (x, y, sk.E.p);
1443     mpi_free (x);
1444     mpi_free (y);
1445   }
1446
1447   point_free (&R);
1448   _gcry_mpi_ec_free (ctx);
1449   point_free (&kG);
1450   point_free (&sk.E.G);
1451   point_free (&sk.Q);
1452
1453   if (!r)
1454     return GPG_ERR_ENOMEM;
1455
1456   /* Success.  */
1457
1458   *result = r;
1459
1460   return 0;
1461 }
1462
1463
1464 static unsigned int
1465 ecc_get_nbits (int algo, gcry_mpi_t *pkey)
1466 {
1467   (void)algo;
1468
1469   return mpi_get_nbits (pkey[0]);
1470 }
1471
1472
1473 /* See rsa.c for a description of this function.  */
1474 static gpg_err_code_t
1475 compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
1476 {
1477 #define N_COMPONENTS 6
1478   static const char names[N_COMPONENTS+1] = "pabgnq";
1479   gpg_err_code_t ec = 0;
1480   gcry_sexp_t l1;
1481   gcry_mpi_t values[N_COMPONENTS];
1482   int idx;
1483
1484   /* Clear the values for easier error cleanup.  */
1485   for (idx=0; idx < N_COMPONENTS; idx++)
1486     values[idx] = NULL;
1487
1488   /* Fill values with all provided parameters.  */
1489   for (idx=0; idx < N_COMPONENTS; idx++)
1490     {
1491       l1 = gcry_sexp_find_token (keyparam, names+idx, 1);
1492       if (l1)
1493         {
1494           values[idx] = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1495           gcry_sexp_release (l1);
1496           if (!values[idx])
1497             {
1498               ec = GPG_ERR_INV_OBJ;
1499               goto leave;
1500             }
1501         }
1502     }
1503
1504   /* Check whether a curve parameter is available and use that to fill
1505      in missing values.  */
1506   l1 = gcry_sexp_find_token (keyparam, "curve", 5);
1507   if (l1)
1508     {
1509       char *curve;
1510       gcry_mpi_t tmpvalues[N_COMPONENTS];
1511
1512       for (idx = 0; idx < N_COMPONENTS; idx++)
1513         tmpvalues[idx] = NULL;
1514
1515       curve = _gcry_sexp_nth_string (l1, 1);
1516       if (!curve)
1517         {
1518           ec = GPG_ERR_INV_OBJ; /* Name missing or out of core. */
1519           goto leave;
1520         }
1521       ec = ecc_get_param (curve, tmpvalues);
1522       gcry_free (curve);
1523       if (ec)
1524         goto leave;
1525
1526       for (idx = 0; idx < N_COMPONENTS; idx++)
1527         {
1528           if (!values[idx])
1529             values[idx] = tmpvalues[idx];
1530           else
1531             mpi_free (tmpvalues[idx]);
1532         }
1533     }
1534
1535   /* Check that all parameters are known and normalize all MPIs (that
1536      should not be required but we use an internal function later and
1537      thus we better make 100% sure that they are normalized). */
1538   for (idx = 0; idx < N_COMPONENTS; idx++)
1539     if (!values[idx])
1540       {
1541         ec = GPG_ERR_NO_OBJ;
1542         goto leave;
1543       }
1544     else
1545       _gcry_mpi_normalize (values[idx]);
1546
1547   /* Hash them all.  */
1548   for (idx = 0; idx < N_COMPONENTS; idx++)
1549     {
1550       char buf[30];
1551       unsigned char *rawmpi;
1552       unsigned int rawmpilen;
1553
1554       rawmpi = _gcry_mpi_get_buffer (values[idx], &rawmpilen, NULL);
1555       if (!rawmpi)
1556         {
1557           ec = gpg_err_code_from_syserror ();
1558           goto leave;
1559         }
1560       snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], rawmpilen);
1561       gcry_md_write (md, buf, strlen (buf));
1562       gcry_md_write (md, rawmpi, rawmpilen);
1563       gcry_md_write (md, ")", 1);
1564       gcry_free (rawmpi);
1565     }
1566
1567  leave:
1568   for (idx = 0; idx < N_COMPONENTS; idx++)
1569     _gcry_mpi_release (values[idx]);
1570
1571   return ec;
1572 #undef N_COMPONENTS
1573 }
1574
1575
1576
1577
1578 \f
1579 /*
1580      Self-test section.
1581  */
1582
1583
1584 static gpg_err_code_t
1585 selftests_ecdsa (selftest_report_func_t report)
1586 {
1587   const char *what;
1588   const char *errtxt;
1589
1590   what = "low-level";
1591   errtxt = NULL; /*selftest ();*/
1592   if (errtxt)
1593     goto failed;
1594
1595   /* FIXME:  need more tests.  */
1596
1597   return 0; /* Succeeded. */
1598
1599  failed:
1600   if (report)
1601     report ("pubkey", GCRY_PK_ECDSA, what, errtxt);
1602   return GPG_ERR_SELFTEST_FAILED;
1603 }
1604
1605
1606 /* Run a full self-test for ALGO and return 0 on success.  */
1607 static gpg_err_code_t
1608 run_selftests (int algo, int extended, selftest_report_func_t report)
1609 {
1610   gpg_err_code_t ec;
1611
1612   (void)extended;
1613
1614   switch (algo)
1615     {
1616     case GCRY_PK_ECDSA:
1617       ec = selftests_ecdsa (report);
1618       break;
1619     default:
1620       ec = GPG_ERR_PUBKEY_ALGO;
1621       break;
1622
1623     }
1624   return ec;
1625 }
1626
1627
1628
1629 \f
1630 static const char *ecdsa_names[] =
1631   {
1632     "ecdsa",
1633     "ecc",
1634     NULL,
1635   };
1636 static const char *ecdh_names[] =
1637   {
1638     "ecdh",
1639     "ecc",
1640     NULL,
1641   };
1642
1643 gcry_pk_spec_t _gcry_pubkey_spec_ecdsa =
1644   {
1645     "ECDSA", ecdsa_names,
1646     "pabgnq", "pabgnqd", "", "rs", "pabgnq",
1647     GCRY_PK_USAGE_SIGN,
1648     ecc_generate,
1649     ecc_check_secret_key,
1650     NULL,
1651     NULL,
1652     ecc_sign,
1653     ecc_verify,
1654     ecc_get_nbits
1655   };
1656
1657 gcry_pk_spec_t _gcry_pubkey_spec_ecdh =
1658   {
1659     "ECDH", ecdh_names,
1660     "pabgnq", "pabgnqd", "se", "", "pabgnq",
1661     GCRY_PK_USAGE_ENCR,
1662     ecc_generate,
1663     ecc_check_secret_key,
1664     ecc_encrypt_raw,
1665     ecc_decrypt_raw,
1666     NULL,
1667     NULL,
1668     ecc_get_nbits
1669   };
1670
1671
1672 pk_extra_spec_t _gcry_pubkey_extraspec_ecdsa =
1673   {
1674     run_selftests,
1675     ecc_generate_ext,
1676     compute_keygrip,
1677     ecc_get_param
1678   };