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  mpi_point_t Q;
646  gcry_mpi_t y_2, y2 = mpi_alloc (0);
647  mpi_ec_t ctx;
648
649  /* ?primarity test of 'p' */
650  /*  (...) //!! */
651  /* G in E(F_p) */
652  y_2 = gen_y_2 (sk->E.G.x, &sk->E);   /*  y^2=x^3+a*x+b */
653  mpi_mulm (y2, sk->E.G.y, sk->E.G.y, sk->E.p);      /*  y^2=y*y */
654  if (mpi_cmp (y_2, y2))
655    {
656      if (DBG_CIPHER)
657        log_debug ("Bad check: Point 'G' does not belong to curve 'E'!\n");
658      return (1);
659    }
660  /* G != PaI */
661  if (!mpi_cmp_ui (sk->E.G.z, 0))
662    {
663      if (DBG_CIPHER)
664        log_debug ("Bad check: 'G' cannot be Point at Infinity!\n");
665      return (1);
666    }
667
668  point_init (&Q);
669  ctx = _gcry_mpi_ec_init (sk->E.p, sk->E.a);
670  _gcry_mpi_ec_mul_point (&Q, sk->E.n, &sk->E.G, ctx);
671  if (mpi_cmp_ui (Q.z, 0))
672    {
673      if (DBG_CIPHER)
674        log_debug ("check_secret_key: E is not a curve of order n\n");
675      point_free (&Q);
676      _gcry_mpi_ec_free (ctx);
677      return 1;
678    }
679  /* pubkey cannot be PaI */
680  if (!mpi_cmp_ui (sk->Q.z, 0))
681    {
682      if (DBG_CIPHER)
683        log_debug ("Bad check: Q can not be a Point at Infinity!\n");
684      _gcry_mpi_ec_free (ctx);
685      return (1);
686    }
687  /* pubkey = [d]G over E */
688  _gcry_mpi_ec_mul_point (&Q, sk->d, &sk->E.G, ctx);
689  if ((Q.x == sk->Q.x) && (Q.y == sk->Q.y) && (Q.z == sk->Q.z))
690    {
691      if (DBG_CIPHER)
692        log_debug
693          ("Bad check: There is NO correspondence between 'd' and 'Q'!\n");
694      _gcry_mpi_ec_free (ctx);
695      return (1);
696    }
697  _gcry_mpi_ec_free (ctx);
698  point_free (&Q);
699  return 0;
700}
701
702
703/*
704 * Return the signature struct (r,s) from the message hash.  The caller
705 * must have allocated R and S.
706 */
707static gpg_err_code_t
708sign (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s)
709{
710  gpg_err_code_t err = 0;
711  gcry_mpi_t k, dr, sum, k_1, x;
712  mpi_point_t I;
713  mpi_ec_t ctx;
714
715  if (DBG_CIPHER)
716    log_mpidump ("ecdsa sign hash  ", input );
717
718  k = NULL;
719  dr = mpi_alloc (0);
720  sum = mpi_alloc (0);
721  k_1 = mpi_alloc (0);
722  x = mpi_alloc (0);
723  point_init (&I);
724
725  mpi_set_ui (s, 0);
726  mpi_set_ui (r, 0);
727
728  ctx = _gcry_mpi_ec_init (skey->E.p, skey->E.a);
729
730  while (!mpi_cmp_ui (s, 0)) /* s == 0 */
731    {
732      while (!mpi_cmp_ui (r, 0)) /* r == 0 */
733        {
734          /* Note, that we are guaranteed to enter this loop at least
735             once because r has been intialized to 0.  We can't use a
736             do_while because we want to keep the value of R even if S
737             has to be recomputed.  */
738          mpi_free (k);
739          k = gen_k (skey->E.n, GCRY_STRONG_RANDOM);
740          _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx);
741          if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx))
742            {
743              if (DBG_CIPHER)
744                log_debug ("ecc sign: Failed to get affine coordinates\n");
745              err = GPG_ERR_BAD_SIGNATURE;
746              goto leave;
747            }
748          mpi_mod (r, x, skey->E.n);  /* r = x mod n */
749        }
750      mpi_mulm (dr, skey->d, r, skey->E.n); /* dr = d*r mod n  */
751      mpi_addm (sum, input, dr, skey->E.n); /* sum = hash + (d*r) mod n  */
752      mpi_invm (k_1, k, skey->E.n);         /* k_1 = k^(-1) mod n  */
753      mpi_mulm (s, k_1, sum, skey->E.n);    /* s = k^(-1)*(hash+(d*r)) mod n */
754    }
755
756  if (DBG_CIPHER)
757    {
758      log_mpidump ("ecdsa sign result r ", r);
759      log_mpidump ("ecdsa sign result s ", s);
760    }
761
762 leave:
763  _gcry_mpi_ec_free (ctx);
764  point_free (&I);
765  mpi_free (x);
766  mpi_free (k_1);
767  mpi_free (sum);
768  mpi_free (dr);
769  mpi_free (k);
770
771  return err;
772}
773
774
775/*
776 * Check if R and S verifies INPUT.
777 */
778static gpg_err_code_t
779verify (gcry_mpi_t input, ECC_public_key *pkey, gcry_mpi_t r, gcry_mpi_t s)
780{
781  gpg_err_code_t err = 0;
782  gcry_mpi_t h, h1, h2, x, y;
783  mpi_point_t Q, Q1, Q2;
784  mpi_ec_t ctx;
785
786  if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) )
787    return GPG_ERR_BAD_SIGNATURE; /* Assertion	0 < r < n  failed.  */
788  if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) )
789    return GPG_ERR_BAD_SIGNATURE; /* Assertion	0 < s < n  failed.  */
790
791  h  = mpi_alloc (0);
792  h1 = mpi_alloc (0);
793  h2 = mpi_alloc (0);
794  x = mpi_alloc (0);
795  y = mpi_alloc (0);
796  point_init (&Q);
797  point_init (&Q1);
798  point_init (&Q2);
799
800  ctx = _gcry_mpi_ec_init (pkey->E.p, pkey->E.a);
801
802  /* h  = s^(-1) (mod n) */
803  mpi_invm (h, s, pkey->E.n);
804/*   log_mpidump ("   h", h); */
805  /* h1 = hash * s^(-1) (mod n) */
806  mpi_mulm (h1, input, h, pkey->E.n);
807/*   log_mpidump ("  h1", h1); */
808  /* Q1 = [ hash * s^(-1) ]G  */
809  _gcry_mpi_ec_mul_point (&Q1, h1, &pkey->E.G, ctx);
810/*   log_mpidump ("Q1.x", Q1.x); */
811/*   log_mpidump ("Q1.y", Q1.y); */
812/*   log_mpidump ("Q1.z", Q1.z); */
813  /* h2 = r * s^(-1) (mod n) */
814  mpi_mulm (h2, r, h, pkey->E.n);
815/*   log_mpidump ("  h2", h2); */
816  /* Q2 = [ r * s^(-1) ]Q */
817  _gcry_mpi_ec_mul_point (&Q2, h2, &pkey->Q, ctx);
818/*   log_mpidump ("Q2.x", Q2.x); */
819/*   log_mpidump ("Q2.y", Q2.y); */
820/*   log_mpidump ("Q2.z", Q2.z); */
821  /* Q  = ([hash * s^(-1)]G) + ([r * s^(-1)]Q) */
822  _gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ctx);
823/*   log_mpidump (" Q.x", Q.x); */
824/*   log_mpidump (" Q.y", Q.y); */
825/*   log_mpidump (" Q.z", Q.z); */
826
827  if (!mpi_cmp_ui (Q.z, 0))
828    {
829      if (DBG_CIPHER)
830          log_debug ("ecc verify: Rejected\n");
831      err = GPG_ERR_BAD_SIGNATURE;
832      goto leave;
833    }
834  if (_gcry_mpi_ec_get_affine (x, y, &Q, ctx))
835    {
836      if (DBG_CIPHER)
837        log_debug ("ecc verify: Failed to get affine coordinates\n");
838      err = GPG_ERR_BAD_SIGNATURE;
839      goto leave;
840    }
841  mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */
842  if (mpi_cmp (x, r))   /* x != r */
843    {
844      if (DBG_CIPHER)
845        {
846          log_mpidump ("     x", x);
847          log_mpidump ("     y", y);
848          log_mpidump ("     r", r);
849          log_mpidump ("     s", s);
850          log_debug ("ecc verify: Not verified\n");
851        }
852      err = GPG_ERR_BAD_SIGNATURE;
853      goto leave;
854    }
855  if (DBG_CIPHER)
856    log_debug ("ecc verify: Accepted\n");
857
858 leave:
859  _gcry_mpi_ec_free (ctx);
860  point_free (&Q2);
861  point_free (&Q1);
862  point_free (&Q);
863  mpi_free (y);
864  mpi_free (x);
865  mpi_free (h2);
866  mpi_free (h1);
867  mpi_free (h);
868  return err;
869}
870
871
872
873/*********************************************
874 **************  interface  ******************
875 *********************************************/
876static gcry_mpi_t
877ec2os (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t p)
878{
879  gpg_error_t err;
880  int pbytes = (mpi_get_nbits (p)+7)/8;
881  size_t n;
882  unsigned char *buf, *ptr;
883  gcry_mpi_t result;
884
885  buf = gcry_xmalloc ( 1 + 2*pbytes );
886  *buf = 04; /* Uncompressed point.  */
887  ptr = buf+1;
888  err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, x);
889  if (err)
890    log_fatal ("mpi_print failed: %s\n", gpg_strerror (err));
891  if (n < pbytes)
892    {
893      memmove (ptr+(pbytes-n), ptr, n);
894      memset (ptr, 0, (pbytes-n));
895    }
896  ptr += pbytes;
897  err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, y);
898  if (err)
899    log_fatal ("mpi_print failed: %s\n", gpg_strerror (err));
900  if (n < pbytes)
901    {
902      memmove (ptr+(pbytes-n), ptr, n);
903      memset (ptr, 0, (pbytes-n));
904    }
905
906  err = gcry_mpi_scan (&result, GCRYMPI_FMT_USG, buf, 1+2*pbytes, NULL);
907  if (err)
908    log_fatal ("mpi_scan failed: %s\n", gpg_strerror (err));
909  gcry_free (buf);
910
911  return result;
912}
913
914
915/* RESULT must have been initialized and is set on success to the
916   point given by VALUE.  */
917static gcry_error_t
918os2ec (mpi_point_t *result, gcry_mpi_t value)
919{
920  gcry_error_t err;
921  size_t n;
922  unsigned char *buf;
923  gcry_mpi_t x, y;
924
925  n = (mpi_get_nbits (value)+7)/8;
926  buf = gcry_xmalloc (n);
927  err = gcry_mpi_print (GCRYMPI_FMT_USG, buf, n, &n, value);
928  if (err)
929    {
930      gcry_free (buf);
931      return err;
932    }
933  if (n < 1)
934    {
935      gcry_free (buf);
936      return GPG_ERR_INV_OBJ;
937    }
938  if (*buf != 4)
939    {
940      gcry_free (buf);
941      return GPG_ERR_NOT_IMPLEMENTED; /* No support for point compression.  */
942    }
943  if ( ((n-1)%2) )
944    {
945      gcry_free (buf);
946      return GPG_ERR_INV_OBJ;
947    }
948  n = (n-1)/2;
949  err = gcry_mpi_scan (&x, GCRYMPI_FMT_USG, buf+1, n, NULL);
950  if (err)
951    {
952      gcry_free (buf);
953      return err;
954    }
955  err = gcry_mpi_scan (&y, GCRYMPI_FMT_USG, buf+1+n, n, NULL);
956  gcry_free (buf);
957  if (err)
958    {
959      mpi_free (x);
960      return err;
961    }
962
963  mpi_set (result->x, x);
964  mpi_set (result->y, y);
965  mpi_set_ui (result->z, 1);
966
967  mpi_free (x);
968  mpi_free (y);
969
970  return 0;
971}
972
973
974/* Extended version of ecc_generate.  */
975static gcry_err_code_t
976ecc_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
977                  const gcry_sexp_t genparms,
978                  gcry_mpi_t *skey, gcry_mpi_t **retfactors,
979                  gcry_sexp_t *r_extrainfo)
980{
981  gpg_err_code_t ec;
982  ECC_secret_key sk;
983  gcry_mpi_t g_x, g_y, q_x, q_y;
984  char *curve_name = NULL;
985  gcry_sexp_t l1;
986  int transient_key = 0;
987  const char *usedcurve = NULL;
988
989  (void)algo;
990  (void)evalue;
991
992  if (genparms)
993    {
994      /* Parse the optional "curve" parameter. */
995      l1 = gcry_sexp_find_token (genparms, "curve", 0);
996      if (l1)
997        {
998          curve_name = _gcry_sexp_nth_string (l1, 1);
999          gcry_sexp_release (l1);
1000          if (!curve_name)
1001            return GPG_ERR_INV_OBJ; /* No curve name or value too large. */
1002        }
1003
1004      /* Parse the optional transient-key flag.  */
1005      l1 = gcry_sexp_find_token (genparms, "transient-key", 0);
1006      if (l1)
1007        {
1008          transient_key = 1;
1009          gcry_sexp_release (l1);
1010        }
1011    }
1012
1013  /* NBITS is required if no curve name has been given.  */
1014  if (!nbits && !curve_name)
1015    return GPG_ERR_NO_OBJ; /* No NBITS parameter. */
1016
1017  g_x = mpi_new (0);
1018  g_y = mpi_new (0);
1019  q_x = mpi_new (0);
1020  q_y = mpi_new (0);
1021  ec = generate_key (&sk, nbits, curve_name, transient_key, g_x, g_y, q_x, q_y,
1022                     &usedcurve);
1023  gcry_free (curve_name);
1024  if (ec)
1025    return ec;
1026  if (usedcurve)  /* Fixme: No error return checking.  */
1027    gcry_sexp_build (r_extrainfo, NULL, "(curve %s)", usedcurve);
1028
1029  skey[0] = sk.E.p;
1030  skey[1] = sk.E.a;
1031  skey[2] = sk.E.b;
1032  skey[3] = ec2os (g_x, g_y, sk.E.p);
1033  skey[4] = sk.E.n;
1034  skey[5] = ec2os (q_x, q_y, sk.E.p);
1035  skey[6] = sk.d;
1036
1037  mpi_free (g_x);
1038  mpi_free (g_y);
1039  mpi_free (q_x);
1040  mpi_free (q_y);
1041
1042  point_free (&sk.E.G);
1043  point_free (&sk.Q);
1044
1045  /* Make an empty list of factors.  */
1046  *retfactors = gcry_calloc ( 1, sizeof **retfactors );
1047  if (!*retfactors)
1048    return gpg_err_code_from_syserror ();  /* Fixme: relase mem?  */
1049
1050  if (DBG_CIPHER)
1051    {
1052      log_mpidump ("ecgen result p", skey[0]);
1053      log_mpidump ("ecgen result a", skey[1]);
1054      log_mpidump ("ecgen result b", skey[2]);
1055      log_mpidump ("ecgen result G", skey[3]);
1056      log_mpidump ("ecgen result n", skey[4]);
1057      log_mpidump ("ecgen result Q", skey[5]);
1058      log_mpidump ("ecgen result d", skey[6]);
1059    }
1060
1061  return 0;
1062}
1063
1064
1065static gcry_err_code_t
1066ecc_generate (int algo, unsigned int nbits, unsigned long evalue,
1067              gcry_mpi_t *skey, gcry_mpi_t **retfactors)
1068{
1069  (void)evalue;
1070  return ecc_generate_ext (algo, nbits, 0, NULL, skey, retfactors, NULL);
1071}
1072
1073
1074/* Return the parameters of the curve NAME in an MPI array.  */
1075static gcry_err_code_t
1076ecc_get_param (const char *name, gcry_mpi_t *pkey)
1077{
1078  gpg_err_code_t err;
1079  unsigned int nbits;
1080  elliptic_curve_t E;
1081  mpi_ec_t ctx;
1082  gcry_mpi_t g_x, g_y;
1083
1084  err = fill_in_curve (0, name, &E, &nbits);
1085  if (err)
1086    return err;
1087
1088  g_x = mpi_new (0);
1089  g_y = mpi_new (0);
1090  ctx = _gcry_mpi_ec_init (E.p, E.a);
1091  if (_gcry_mpi_ec_get_affine (g_x, g_y, &E.G, ctx))
1092    log_fatal ("ecc get param: Failed to get affine coordinates\n");
1093  _gcry_mpi_ec_free (ctx);
1094  point_free (&E.G);
1095
1096  pkey[0] = E.p;
1097  pkey[1] = E.a;
1098  pkey[2] = E.b;
1099  pkey[3] = ec2os (g_x, g_y, E.p);
1100  pkey[4] = E.n;
1101  pkey[5] = NULL;
1102
1103  mpi_free (g_x);
1104  mpi_free (g_y);
1105
1106  return 0;
1107}
1108
1109
1110/* Return the parameters of the curve NAME as an S-expression.  */
1111static gcry_sexp_t
1112ecc_get_param_sexp (const char *name)
1113{
1114  gcry_mpi_t pkey[6];
1115  gcry_sexp_t result;
1116  int i;
1117
1118  if (ecc_get_param (name, pkey))
1119    return NULL;
1120
1121  if (gcry_sexp_build (&result, NULL,
1122                       "(public-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)))",
1123                       pkey[0], pkey[1], pkey[2], pkey[3], pkey[4]))
1124    result = NULL;
1125
1126  for (i=0; pkey[i]; i++)
1127    gcry_mpi_release (pkey[i]);
1128
1129  return result;
1130}
1131
1132
1133/* Return the name matching the parameters in PKEY.  */
1134static const char *
1135ecc_get_curve (gcry_mpi_t *pkey, int iterator, unsigned int *r_nbits)
1136{
1137  gpg_err_code_t err;
1138  elliptic_curve_t E;
1139  int idx;
1140  gcry_mpi_t tmp;
1141  const char *result = NULL;
1142
1143  if (r_nbits)
1144    *r_nbits = 0;
1145
1146  if (!pkey)
1147    {
1148      idx = iterator;
1149      if (idx >= 0 && idx < DIM (domain_parms))
1150        {
1151          result = domain_parms[idx].desc;
1152          if (r_nbits)
1153            *r_nbits = domain_parms[idx].nbits;
1154        }
1155      return result;
1156    }
1157
1158  if (!pkey[0] || !pkey[1] || !pkey[2] || !pkey[3] || !pkey[4])
1159    return NULL;
1160
1161  E.p = pkey[0];
1162  E.a = pkey[1];
1163  E.b = pkey[2];
1164  point_init (&E.G);
1165  err = os2ec (&E.G, pkey[3]);
1166  if (err)
1167    {
1168      point_free (&E.G);
1169      return NULL;
1170    }
1171  E.n = pkey[4];
1172
1173  for (idx = 0; domain_parms[idx].desc; idx++)
1174    {
1175      tmp = scanval (domain_parms[idx].p);
1176      if (!mpi_cmp (tmp, E.p))
1177        {
1178          mpi_free (tmp);
1179          tmp = scanval (domain_parms[idx].a);
1180          if (!mpi_cmp (tmp, E.a))
1181            {
1182              mpi_free (tmp);
1183              tmp = scanval (domain_parms[idx].b);
1184              if (!mpi_cmp (tmp, E.b))
1185                {
1186                  mpi_free (tmp);
1187                  tmp = scanval (domain_parms[idx].n);
1188                  if (!mpi_cmp (tmp, E.n))
1189                    {
1190                      mpi_free (tmp);
1191                      tmp = scanval (domain_parms[idx].g_x);
1192                      if (!mpi_cmp (tmp, E.G.x))
1193                        {
1194                          mpi_free (tmp);
1195                          tmp = scanval (domain_parms[idx].g_y);
1196                          if (!mpi_cmp (tmp, E.G.y))
1197                            {
1198                              result = domain_parms[idx].desc;
1199                              if (r_nbits)
1200                                *r_nbits = domain_parms[idx].nbits;
1201                              break;
1202                            }
1203                        }
1204                    }
1205                }
1206            }
1207        }
1208      mpi_free (tmp);
1209    }
1210
1211  point_free (&E.G);
1212
1213  return result;
1214}
1215
1216
1217static gcry_err_code_t
1218ecc_check_secret_key (int algo, gcry_mpi_t *skey)
1219{
1220  gpg_err_code_t err;
1221  ECC_secret_key sk;
1222
1223  (void)algo;
1224
1225  /* FIXME:  This check looks a bit fishy:  Now long is the array?  */
1226  if (!skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] || !skey[5]
1227      || !skey[6])
1228    return GPG_ERR_BAD_MPI;
1229
1230  sk.E.p = skey[0];
1231  sk.E.a = skey[1];
1232  sk.E.b = skey[2];
1233  point_init (&sk.E.G);
1234  err = os2ec (&sk.E.G, skey[3]);
1235  if (err)
1236    {
1237      point_free (&sk.E.G);
1238      return err;
1239    }
1240  sk.E.n = skey[4];
1241  point_init (&sk.Q);
1242  err = os2ec (&sk.Q, skey[5]);
1243  if (err)
1244    {
1245      point_free (&sk.E.G);
1246      point_free (&sk.Q);
1247      return err;
1248    }
1249
1250  sk.d = skey[6];
1251
1252  if (check_secret_key (&sk))
1253    {
1254      point_free (&sk.E.G);
1255      point_free (&sk.Q);
1256      return GPG_ERR_BAD_SECKEY;
1257    }
1258  point_free (&sk.E.G);
1259  point_free (&sk.Q);
1260  return 0;
1261}
1262
1263
1264static gcry_err_code_t
1265ecc_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
1266{
1267  gpg_err_code_t err;
1268  ECC_secret_key sk;
1269
1270  (void)algo;
1271
1272  if (!data || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4]
1273      || !skey[5] || !skey[6] )
1274    return GPG_ERR_BAD_MPI;
1275
1276  sk.E.p = skey[0];
1277  sk.E.a = skey[1];
1278  sk.E.b = skey[2];
1279  point_init (&sk.E.G);
1280  err = os2ec (&sk.E.G, skey[3]);
1281  if (err)
1282    {
1283      point_free (&sk.E.G);
1284      return err;
1285    }
1286  sk.E.n = skey[4];
1287  point_init (&sk.Q);
1288  err = os2ec (&sk.Q, skey[5]);
1289  if (err)
1290    {
1291      point_free (&sk.E.G);
1292      point_free (&sk.Q);
1293      return err;
1294    }
1295  sk.d = skey[6];
1296
1297  resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.E.p));
1298  resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.E.p));
1299  err = sign (data, &sk, resarr[0], resarr[1]);
1300  if (err)
1301    {
1302      mpi_free (resarr[0]);
1303      mpi_free (resarr[1]);
1304      resarr[0] = NULL; /* Mark array as released.  */
1305    }
1306  point_free (&sk.E.G);
1307  point_free (&sk.Q);
1308  return err;
1309}
1310
1311
1312static gcry_err_code_t
1313ecc_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
1314            int (*cmp)(void *, gcry_mpi_t), void *opaquev)
1315{
1316  gpg_err_code_t err;
1317  ECC_public_key pk;
1318
1319  (void)algo;
1320  (void)cmp;
1321  (void)opaquev;
1322
1323  if (!data[0] || !data[1] || !hash || !pkey[0] || !pkey[1] || !pkey[2]
1324      || !pkey[3] || !pkey[4] || !pkey[5] )
1325    return GPG_ERR_BAD_MPI;
1326
1327  pk.E.p = pkey[0];
1328  pk.E.a = pkey[1];
1329  pk.E.b = pkey[2];
1330  point_init (&pk.E.G);
1331  err = os2ec (&pk.E.G, pkey[3]);
1332  if (err)
1333    {
1334      point_free (&pk.E.G);
1335      return err;
1336    }
1337  pk.E.n = pkey[4];
1338  point_init (&pk.Q);
1339  err = os2ec (&pk.Q, pkey[5]);
1340  if (err)
1341    {
1342      point_free (&pk.E.G);
1343      point_free (&pk.Q);
1344      return err;
1345    }
1346
1347  err = verify (hash, &pk, data[0], data[1]);
1348
1349  point_free (&pk.E.G);
1350  point_free (&pk.Q);
1351  return err;
1352}
1353
1354
1355/* ecdh raw is classic 2-round DH protocol published in 1976.
1356 *
1357 * Overview of ecc_encrypt_raw and ecc_decrypt_raw.
1358 *
1359 * As with any PK operation, encrypt version uses a public key and
1360 * decrypt -- private.
1361 *
1362 * Symbols used below:
1363 *     G - field generator point
1364 *     d - private long-term scalar
1365 *    dG - public long-term key
1366 *     k - ephemeral scalar
1367 *    kG - ephemeral public key
1368 *   dkG - shared secret
1369 *
1370 * ecc_encrypt_raw description:
1371 *   input:
1372 *     data[0] : private scalar (k)
1373 *   output:
1374 *     result[0] : shared point (kdG)
1375 *     result[1] : generated ephemeral public key (kG)
1376 *
1377 * ecc_decrypt_raw description:
1378 *   input:
1379 *     data[0] : a point kG (ephemeral public key)
1380 *   output:
1381 *     result[0] : shared point (kdG)
1382 */
1383static gcry_err_code_t
1384ecc_encrypt_raw (int algo, gcry_mpi_t *resarr, gcry_mpi_t k,
1385                 gcry_mpi_t *pkey, int flags)
1386{
1387  ECC_public_key pk;
1388  mpi_ec_t ctx;
1389  gcry_mpi_t result[2];
1390  int err;
1391
1392  (void)algo;
1393  (void)flags;
1394
1395  if (!k
1396      || !pkey[0] || !pkey[1] || !pkey[2] || !pkey[3] || !pkey[4] || !pkey[5])
1397    return GPG_ERR_BAD_MPI;
1398
1399  pk.E.p = pkey[0];
1400  pk.E.a = pkey[1];
1401  pk.E.b = pkey[2];
1402  point_init (&pk.E.G);
1403  err = os2ec (&pk.E.G, pkey[3]);
1404  if (err)
1405    {
1406      point_free (&pk.E.G);
1407      return err;
1408    }
1409  pk.E.n = pkey[4];
1410  point_init (&pk.Q);
1411  err = os2ec (&pk.Q, pkey[5]);
1412  if (err)
1413    {
1414      point_free (&pk.E.G);
1415      point_free (&pk.Q);
1416      return err;
1417    }
1418
1419  ctx = _gcry_mpi_ec_init (pk.E.p, pk.E.a);
1420
1421  /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so */
1422  {
1423    mpi_point_t R;	/* Result that we return.  */
1424    gcry_mpi_t x, y;
1425
1426    x = mpi_new (0);
1427    y = mpi_new (0);
1428
1429    point_init (&R);
1430
1431    /* R = kQ  <=>  R = kdG  */
1432    _gcry_mpi_ec_mul_point (&R, k, &pk.Q, ctx);
1433
1434    if (_gcry_mpi_ec_get_affine (x, y, &R, ctx))
1435      log_fatal ("ecdh: Failed to get affine coordinates for kdG\n");
1436
1437    result[0] = ec2os (x, y, pk.E.p);
1438
1439    /* R = kG */
1440    _gcry_mpi_ec_mul_point (&R, k, &pk.E.G, ctx);
1441
1442    if (_gcry_mpi_ec_get_affine (x, y, &R, ctx))
1443      log_fatal ("ecdh: Failed to get affine coordinates for kG\n");
1444
1445    result[1] = ec2os (x, y, pk.E.p);
1446
1447    mpi_free (x);
1448    mpi_free (y);
1449
1450    point_free (&R);
1451  }
1452
1453  _gcry_mpi_ec_free (ctx);
1454  point_free (&pk.E.G);
1455  point_free (&pk.Q);
1456
1457  if (!result[0] || !result[1])
1458    {
1459      mpi_free (result[0]);
1460      mpi_free (result[1]);
1461      return GPG_ERR_ENOMEM;
1462    }
1463
1464  /* Success.  */
1465  resarr[0] = result[0];
1466  resarr[1] = result[1];
1467
1468  return 0;
1469}
1470
1471/*  input:
1472 *     data[0] : a point kG (ephemeral public key)
1473 *   output:
1474 *     resaddr[0] : shared point kdG
1475 *
1476 *  see ecc_encrypt_raw for details.
1477 */
1478static gcry_err_code_t
1479ecc_decrypt_raw (int algo, gcry_mpi_t *result, gcry_mpi_t *data,
1480                 gcry_mpi_t *skey, int flags)
1481{
1482  ECC_secret_key sk;
1483  mpi_point_t R;	/* Result that we return.  */
1484  mpi_point_t kG;
1485  mpi_ec_t ctx;
1486  gcry_mpi_t r;
1487  int err;
1488
1489  (void)algo;
1490  (void)flags;
1491
1492  *result = NULL;
1493
1494  if (!data || !data[0]
1495      || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4]
1496      || !skey[5] || !skey[6] )
1497    return GPG_ERR_BAD_MPI;
1498
1499  point_init (&kG);
1500  err = os2ec (&kG, data[0]);
1501  if (err)
1502    {
1503      point_free (&kG);
1504      return err;
1505    }
1506
1507
1508  sk.E.p = skey[0];
1509  sk.E.a = skey[1];
1510  sk.E.b = skey[2];
1511  point_init (&sk.E.G);
1512  err = os2ec (&sk.E.G, skey[3]);
1513  if (err)
1514    {
1515      point_free (&kG);
1516      point_free (&sk.E.G);
1517      return err;
1518    }
1519  sk.E.n = skey[4];
1520  point_init (&sk.Q);
1521  err = os2ec (&sk.Q, skey[5]);
1522  if (err)
1523    {
1524      point_free (&kG);
1525      point_free (&sk.E.G);
1526      point_free (&sk.Q);
1527      return err;
1528    }
1529  sk.d = skey[6];
1530
1531  ctx = _gcry_mpi_ec_init (sk.E.p, sk.E.a);
1532
1533  /* R = dkG */
1534  point_init (&R);
1535  _gcry_mpi_ec_mul_point (&R, sk.d, &kG, ctx);
1536
1537  point_free (&kG);
1538
1539  /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so:  */
1540  {
1541    gcry_mpi_t x, y;
1542
1543    x = mpi_new (0);
1544    y = mpi_new (0);
1545
1546    if (_gcry_mpi_ec_get_affine (x, y, &R, ctx))
1547      log_fatal ("ecdh: Failed to get affine coordinates\n");
1548
1549    r = ec2os (x, y, sk.E.p);
1550    mpi_free (x);
1551    mpi_free (y);
1552  }
1553
1554  point_free (&R);
1555  _gcry_mpi_ec_free (ctx);
1556  point_free (&kG);
1557  point_free (&sk.E.G);
1558  point_free (&sk.Q);
1559
1560  if (!r)
1561    return GPG_ERR_ENOMEM;
1562
1563  /* Success.  */
1564
1565  *result = r;
1566
1567  return 0;
1568}
1569
1570
1571static unsigned int
1572ecc_get_nbits (int algo, gcry_mpi_t *pkey)
1573{
1574  (void)algo;
1575
1576  return mpi_get_nbits (pkey[0]);
1577}
1578
1579
1580/* See rsa.c for a description of this function.  */
1581static gpg_err_code_t
1582compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
1583{
1584#define N_COMPONENTS 6
1585  static const char names[N_COMPONENTS+1] = "pabgnq";
1586  gpg_err_code_t ec = 0;
1587  gcry_sexp_t l1;
1588  gcry_mpi_t values[N_COMPONENTS];
1589  int idx;
1590
1591  /* Clear the values for easier error cleanup.  */
1592  for (idx=0; idx < N_COMPONENTS; idx++)
1593    values[idx] = NULL;
1594
1595  /* Fill values with all provided parameters.  */
1596  for (idx=0; idx < N_COMPONENTS; idx++)
1597    {
1598      l1 = gcry_sexp_find_token (keyparam, names+idx, 1);
1599      if (l1)
1600        {
1601          values[idx] = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1602	  gcry_sexp_release (l1);
1603	  if (!values[idx])
1604            {
1605              ec = GPG_ERR_INV_OBJ;
1606              goto leave;
1607            }
1608	}
1609    }
1610
1611  /* Check whether a curve parameter is available and use that to fill
1612     in missing values.  */
1613  l1 = gcry_sexp_find_token (keyparam, "curve", 5);
1614  if (l1)
1615    {
1616      char *curve;
1617      gcry_mpi_t tmpvalues[N_COMPONENTS];
1618
1619      for (idx = 0; idx < N_COMPONENTS; idx++)
1620        tmpvalues[idx] = NULL;
1621
1622      curve = _gcry_sexp_nth_string (l1, 1);
1623      gcry_sexp_release (l1);
1624      if (!curve)
1625        {
1626          ec = GPG_ERR_INV_OBJ; /* Name missing or out of core. */
1627          goto leave;
1628        }
1629      ec = ecc_get_param (curve, tmpvalues);
1630      gcry_free (curve);
1631      if (ec)
1632        goto leave;
1633
1634      for (idx = 0; idx < N_COMPONENTS; idx++)
1635        {
1636          if (!values[idx])
1637            values[idx] = tmpvalues[idx];
1638          else
1639            mpi_free (tmpvalues[idx]);
1640        }
1641    }
1642
1643  /* Check that all parameters are known and normalize all MPIs (that
1644     should not be required but we use an internal function later and
1645     thus we better make 100% sure that they are normalized). */
1646  for (idx = 0; idx < N_COMPONENTS; idx++)
1647    if (!values[idx])
1648      {
1649        ec = GPG_ERR_NO_OBJ;
1650        goto leave;
1651      }
1652    else
1653      _gcry_mpi_normalize (values[idx]);
1654
1655  /* Hash them all.  */
1656  for (idx = 0; idx < N_COMPONENTS; idx++)
1657    {
1658      char buf[30];
1659      unsigned char *rawmpi;
1660      unsigned int rawmpilen;
1661
1662      rawmpi = _gcry_mpi_get_buffer (values[idx], &rawmpilen, NULL);
1663      if (!rawmpi)
1664        {
1665          ec = gpg_err_code_from_syserror ();
1666          goto leave;
1667        }
1668      snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], rawmpilen);
1669      gcry_md_write (md, buf, strlen (buf));
1670      gcry_md_write (md, rawmpi, rawmpilen);
1671      gcry_md_write (md, ")", 1);
1672      gcry_free (rawmpi);
1673    }
1674
1675 leave:
1676  for (idx = 0; idx < N_COMPONENTS; idx++)
1677    _gcry_mpi_release (values[idx]);
1678
1679  return ec;
1680#undef N_COMPONENTS
1681}
1682
1683
1684
1685
1686
1687/*
1688     Self-test section.
1689 */
1690
1691
1692static gpg_err_code_t
1693selftests_ecdsa (selftest_report_func_t report)
1694{
1695  const char *what;
1696  const char *errtxt;
1697
1698  what = "low-level";
1699  errtxt = NULL; /*selftest ();*/
1700  if (errtxt)
1701    goto failed;
1702
1703  /* FIXME:  need more tests.  */
1704
1705  return 0; /* Succeeded. */
1706
1707 failed:
1708  if (report)
1709    report ("pubkey", GCRY_PK_ECDSA, what, errtxt);
1710  return GPG_ERR_SELFTEST_FAILED;
1711}
1712
1713
1714/* Run a full self-test for ALGO and return 0 on success.  */
1715static gpg_err_code_t
1716run_selftests (int algo, int extended, selftest_report_func_t report)
1717{
1718  gpg_err_code_t ec;
1719
1720  (void)extended;
1721
1722  switch (algo)
1723    {
1724    case GCRY_PK_ECDSA:
1725      ec = selftests_ecdsa (report);
1726      break;
1727    default:
1728      ec = GPG_ERR_PUBKEY_ALGO;
1729      break;
1730
1731    }
1732  return ec;
1733}
1734
1735
1736
1737
1738static const char *ecdsa_names[] =
1739  {
1740    "ecdsa",
1741    "ecc",
1742    NULL,
1743  };
1744static const char *ecdh_names[] =
1745  {
1746    "ecdh",
1747    "ecc",
1748    NULL,
1749  };
1750
1751gcry_pk_spec_t _gcry_pubkey_spec_ecdsa =
1752  {
1753    "ECDSA", ecdsa_names,
1754    "pabgnq", "pabgnqd", "", "rs", "pabgnq",
1755    GCRY_PK_USAGE_SIGN,
1756    ecc_generate,
1757    ecc_check_secret_key,
1758    NULL,
1759    NULL,
1760    ecc_sign,
1761    ecc_verify,
1762    ecc_get_nbits
1763  };
1764
1765gcry_pk_spec_t _gcry_pubkey_spec_ecdh =
1766  {
1767    "ECDH", ecdh_names,
1768    "pabgnq", "pabgnqd", "se", "", "pabgnq",
1769    GCRY_PK_USAGE_ENCR,
1770    ecc_generate,
1771    ecc_check_secret_key,
1772    ecc_encrypt_raw,
1773    ecc_decrypt_raw,
1774    NULL,
1775    NULL,
1776    ecc_get_nbits
1777  };
1778
1779
1780pk_extra_spec_t _gcry_pubkey_extraspec_ecdsa =
1781  {
1782    run_selftests,
1783    ecc_generate_ext,
1784    compute_keygrip,
1785    ecc_get_param,
1786    ecc_get_curve,
1787    ecc_get_param_sexp
1788  };
1789