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