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