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