cipher/
[libgcrypt.git] / cipher / ecc.c
1 /* ecc.c  -  Elliptic Curve Cryptography
2    Copyright (C) 2007 Free Software Foundation, Inc.
3
4    This file is part of Libgcrypt.
5   
6    Libgcrypt is free software; you can redistribute it and/or modify
7    it under the terms of the GNU Lesser General Public License as
8    published by the Free Software Foundation; either version 2.1 of
9    the License, or (at your option) any later version.
10   
11    Libgcrypt is distributed in the hope that it will be useful,
12    but WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14    GNU Lesser General Public License for more details.
15   
16    You should have received a copy of the GNU Lesser General Public
17    License along with this program; if not, write to the Free Software
18    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
19    USA.  */
20
21 /* This code is originally based on the Patch 0.1.6 for the gnupg
22    1.4.x branch as retrieved on 2007-03-21 from
23    http://www.calcurco.cat/eccGnuPG/src/gnupg-1.4.6-ecc0.2.0beta1.diff.bz2
24    The original authors are:
25      Written by
26       Sergi Blanch i Torne <d4372211 at alumnes.eup.udl.es>,
27       Ramiro Moreno Chiral <ramiro at eup.udl.es>
28      Maintainers
29       Sergi Blanch i Torne
30       Ramiro Moreno Chiral
31       Mikael Mylnikov (mmr)
32   For use in Libgcrypt the code has been heavily modified and cleaned
33   up. In fact there is not much left of the orginally code except for
34   some variable names and the text book implementaion of the sign and
35   verification algorithms.  The arithmetic functions have entirely
36   been rewritten and moved to mpi/ec.c.  */
37
38
39 /* TODO:
40
41   - If we support point compression we need to decide how to compute
42     the keygrip - it should not change due to compression.
43
44   - In mpi/ec.c we use mpi_powm for x^2 mod p: Either implement a
45     special case in mpi_powm or check whether mpi_mulm is faster.
46
47   - Decide whether we should hide the mpi_point_t definition.
48
49   - Support more than just ECDSA.
50 */
51
52
53 #include <config.h>
54 #include <stdio.h>
55 #include <stdlib.h>
56 #include <string.h>
57 #include <assert.h>
58
59 #include "g10lib.h"
60 #include "mpi.h"
61 #include "cipher.h"
62
63
64 /* Definition of a curve.  */
65 typedef struct
66 {
67   gcry_mpi_t p;   /* Prime specifying the field GF(p).  */
68   gcry_mpi_t a;   /* First coefficient of the Weierstrass equation.  */
69   gcry_mpi_t b;   /* Second coefficient of the Weierstrass equation.  */
70   mpi_point_t G;  /* Base point (generator).  */
71   gcry_mpi_t n;   /* Order of G.  */
72 } elliptic_curve_t; 
73
74
75 typedef struct
76 {
77   elliptic_curve_t E;
78   mpi_point_t Q;  /* Q = [d]G  */
79 } ECC_public_key;
80
81 typedef struct
82 {
83   elliptic_curve_t E;
84   mpi_point_t Q;
85   gcry_mpi_t d;
86 } ECC_secret_key;
87
88
89 /* This tables defines aliases for curve names.  */
90 static const struct
91 {
92   const char *name;  /* Our name.  */
93   const char *other; /* Other name. */
94 } curve_aliases[] = 
95   {
96     { "NIST P-192", "1.2.840.10045.3.1.1" }, /* X9.62 OID  */
97     { "NIST P-192", "prime192v1" },          /* X9.62 name.  */
98     { "NIST P-192", "secp192r1"  },          /* SECP name.  */
99
100     { "NIST P-224", "secp224r1" },
101     { "NIST P-224", "1.3.132.0.33" },        /* SECP OID.  */
102
103     { "NIST P-256", "1.2.840.10045.3.1.7" }, 
104     { "NIST P-256", "prime256v1" },          
105     { "NIST P-256", "secp256r1"  },          
106
107     { "NIST P-384", "secp384r1" },
108     { "NIST P-384", "1.3.132.0.34" },       
109
110     { "NIST P-521", "secp521r1" },
111     { "NIST P-521", "1.3.132.0.35" },
112
113     { "brainpoolP160r1", "1.3.36.3.3.2.8.1.1.1" },
114     { "brainpoolP192r1", "1.3.36.3.3.2.8.1.1.3" },
115     { "brainpoolP224r1", "1.3.36.3.3.2.8.1.1.5" },
116     { "brainpoolP256r1", "1.3.36.3.3.2.8.1.1.7" },
117     { "brainpoolP320r1", "1.3.36.3.3.2.8.1.1.9" },
118     { "brainpoolP384r1", "1.3.36.3.3.2.8.1.1.11"},
119     { "brainpoolP512r1", "1.3.36.3.3.2.8.1.1.13"},
120
121     { NULL, NULL}
122   };
123
124
125
126 /* This static table defines all available curves.  */
127 static const struct
128 {
129   const char *desc;           /* Description of the curve.  */
130   unsigned int nbits;         /* Number of bits.  */
131   const char  *p;             /* Order of the prime field.  */
132   const char *a, *b;          /* The coefficients. */
133   const char *n;              /* The order of the base point.  */
134   const char *g_x, *g_y;      /* Base point.  */
135 } domain_parms[] =
136   {
137     {
138       "NIST P-192", 192,
139       "0xfffffffffffffffffffffffffffffffeffffffffffffffff",
140       "0xfffffffffffffffffffffffffffffffefffffffffffffffc",
141       "0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1",
142       "0xffffffffffffffffffffffff99def836146bc9b1b4d22831",
143
144       "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012",
145       "0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
146     },
147     {
148       "NIST P-224", 224,
149       "0xffffffffffffffffffffffffffffffff000000000000000000000001",
150       "0xfffffffffffffffffffffffffffffffefffffffffffffffffffffffe",
151       "0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4",
152       "0xffffffffffffffffffffffffffff16a2e0b8f03e13dd29455c5c2a3d" ,
153
154       "0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21",
155       "0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34"
156     },
157     {
158       "NIST P-256", 256,
159       "0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff",
160       "0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc",
161       "0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b",
162       "0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551",
163
164       "0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296",
165       "0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5"
166     },
167     {
168       "NIST P-384", 384,
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,
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,
201       "0xe95e4a5f737059dc60dfc7ad95b3d8139515620f",
202       "0x340e7be2a280eb74e2be61bada745d97e8f7c300",
203       "0x1e589a8595423412134faa2dbdec95c8d8675e58",
204       "0xe95e4a5f737059dc60df5991d45029409e60fc09",
205       "0xbed5af16ea3f6a4f62938c4631eb5af7bdbcdbc3",
206       "0x1667cb477a1a8ec338f94741669c976316da6321"
207     },
208
209     { "brainpoolP192r1", 192,
210       "0xc302f41d932a36cda7a3463093d18db78fce476de1a86297",
211       "0x6a91174076b1e0e19c39c031fe8685c1cae040e5c69a28ef",
212       "0x469a28ef7c28cca3dc721d044f4496bcca7ef4146fbf25c9",
213       "0xc302f41d932a36cda7a3462f9e9e916b5be8f1029ac4acc1",
214       "0xc0a0647eaab6a48753b033c56cb0f0900a2f5c4853375fd6",
215       "0x14b690866abd5bb88b5f4828c1490002e6773fa2fa299b8f"
216     },
217
218     { "brainpoolP224r1", 224,
219       "0xd7c134aa264366862a18302575d1d787b09f075797da89f57ec8c0ff",
220       "0x68a5e62ca9ce6c1c299803a6c1530b514e182ad8b0042a59cad29f43",
221       "0x2580f63ccfe44138870713b1a92369e33e2135d266dbb372386c400b",
222       "0xd7c134aa264366862a18302575d0fb98d116bc4b6ddebca3a5a7939f",
223       "0x0d9029ad2c7e5cf4340823b2a87dc68c9e4ce3174c1e6efdee12c07d",
224       "0x58aa56f772c0726f24c6b89e4ecdac24354b9e99caa3f6d3761402cd"
225     },
226
227     { "brainpoolP256r1", 256, 
228       "0xa9fb57dba1eea9bc3e660a909d838d726e3bf623d52620282013481d1f6e5377",
229       "0x7d5a0975fc2c3057eef67530417affe7fb8055c126dc5c6ce94a4b44f330b5d9",
230       "0x26dc5c6ce94a4b44f330b5d9bbd77cbf958416295cf7e1ce6bccdc18ff8c07b6",
231       "0xa9fb57dba1eea9bc3e660a909d838d718c397aa3b561a6f7901e0e82974856a7",
232       "0x8bd2aeb9cb7e57cb2c4b482ffc81b7afb9de27e1e3bd23c23a4453bd9ace3262",
233       "0x547ef835c3dac4fd97f8461a14611dc9c27745132ded8e545c1d54c72f046997"
234     },
235
236     { "brainpoolP320r1", 320, 
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, 
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,
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, NULL, NULL, NULL, NULL }
282   };
283
284
285 /* Registered progress function and its callback value. */
286 static void (*progress_cb) (void *, const char*, int, int, int);
287 static void *progress_cb_data;
288
289
290 #define point_init(a)  _gcry_mpi_ec_point_init ((a))
291 #define point_free(a)  _gcry_mpi_ec_point_free ((a))
292
293
294 \f
295 /* Local prototypes. */
296 static gcry_mpi_t gen_k (gcry_mpi_t p, int security_level);
297 static void test_keys (ECC_secret_key * sk, unsigned int nbits);
298 static int check_secret_key (ECC_secret_key * sk);
299 static gpg_err_code_t sign (gcry_mpi_t input, ECC_secret_key *skey,
300                             gcry_mpi_t r, gcry_mpi_t s);
301 static gpg_err_code_t verify (gcry_mpi_t input, ECC_public_key *pkey,
302                               gcry_mpi_t r, gcry_mpi_t s);
303
304
305 static gcry_mpi_t gen_y_2 (gcry_mpi_t x, elliptic_curve_t * base);
306
307
308
309 \f
310 void
311 _gcry_register_pk_ecc_progress (void (*cb) (void *, const char *,
312                                             int, int, int),
313                                 void *cb_data)
314 {
315   progress_cb = cb;
316   progress_cb_data = cb_data;
317 }
318
319 /* static void */
320 /* progress (int c) */
321 /* { */
322 /*   if (progress_cb) */
323 /*     progress_cb (progress_cb_data, "pk_ecc", c, 0, 0); */
324 /* } */
325
326
327 \f
328
329 /* Set the value from S into D.  */
330 static void
331 point_set (mpi_point_t *d, mpi_point_t *s)
332 {
333   mpi_set (d->x, s->x);
334   mpi_set (d->y, s->y);
335   mpi_set (d->z, s->z);
336 }
337
338
339 /*
340  * Release a curve object.
341  */
342 static void
343 curve_free (elliptic_curve_t *E)
344 {
345   mpi_free (E->p); E->p = NULL;
346   mpi_free (E->a); E->a = NULL;
347   mpi_free (E->b);  E->b = NULL;
348   point_free (&E->G);
349   mpi_free (E->n);  E->n = NULL;
350 }
351
352
353 /*
354  * Return a copy of a curve object.
355  */
356 static elliptic_curve_t
357 curve_copy (elliptic_curve_t E)
358 {
359   elliptic_curve_t R;
360
361   R.p = mpi_copy (E.p);
362   R.a = mpi_copy (E.a);
363   R.b = mpi_copy (E.b);
364   point_init (&R.G);
365   point_set (&R.G, &E.G);
366   R.n = mpi_copy (E.n);
367
368   return R;
369 }
370
371
372
373 /* Helper to scan a hex string. */
374 static gcry_mpi_t
375 scanval (const char *string)
376 {
377   gpg_error_t err;
378   gcry_mpi_t val;
379
380   err = gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL);
381   if (err)
382     log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (err));
383   return val;
384 }
385
386
387
388 \f
389
390 /****************
391  * Solve the right side of the equation that defines a curve.
392  */
393 static gcry_mpi_t
394 gen_y_2 (gcry_mpi_t x, elliptic_curve_t *base)
395 {
396   gcry_mpi_t three, x_3, axb, y;
397
398   three = mpi_alloc_set_ui (3);
399   x_3 = mpi_new (0);
400   axb = mpi_new (0);
401   y   = mpi_new (0);
402
403   mpi_powm (x_3, x, three, base->p);  
404   mpi_mulm (axb, base->a, x, base->p); 
405   mpi_addm (axb, axb, base->b, base->p);     
406   mpi_addm (y, x_3, axb, base->p);    
407
408   mpi_free (x_3);
409   mpi_free (axb);
410   mpi_free (three);
411   return y; /* The quadratic value of the coordinate if it exist. */
412 }
413
414
415
416
417
418 /* Generate a random secret scalar k with an order of p
419
420    At the beginning this was identical to the code is in elgamal.c.
421    Later imporved by mmr.   Further simplified by wk.  */
422 static gcry_mpi_t
423 gen_k (gcry_mpi_t p, int security_level)
424 {
425   gcry_mpi_t k;
426   unsigned int nbits;
427
428   nbits = mpi_get_nbits (p);
429   k = mpi_snew (nbits);
430   if (DBG_CIPHER)
431     log_debug ("choosing a random k of %u bits\n", nbits);
432
433   gcry_mpi_randomize (k, nbits, security_level);
434
435   mpi_mod (k, k, p);  /*  k = k mod p  */
436
437   return k;
438 }
439
440 /****************
441  * Generate the crypto system setup.
442  * As of now the fix NIST recommended values are used.
443  * The subgroup generator point is in another function: gen_big_point.
444  */
445 static gpg_err_code_t
446 generate_curve (unsigned int nbits, const char *name, 
447                 elliptic_curve_t *curve, unsigned int *r_nbits)
448 {
449   int idx, aliasno;
450
451   if (name)
452     {
453       /* First check nor native curves.  */
454       for (idx = 0; domain_parms[idx].desc; idx++)
455         if (!strcmp (name, domain_parms[idx].desc))
456           break;
457       /* If not found consult the alias table.  */
458       if (!domain_parms[idx].desc)
459         {
460           for (aliasno = 0; curve_aliases[aliasno].name; aliasno++)
461             if (!strcmp (name, curve_aliases[aliasno].other))
462               break;
463           if (curve_aliases[aliasno].name)
464             {
465               for (idx = 0; domain_parms[idx].desc; idx++)
466                 if (!strcmp (curve_aliases[aliasno].name,
467                              domain_parms[idx].desc))
468                   break;
469             }
470         }
471     }
472   else
473     {
474       for (idx = 0; domain_parms[idx].desc; idx++)
475         if (nbits == domain_parms[idx].nbits)
476           break;
477     }
478   if (!domain_parms[idx].desc)
479     return GPG_ERR_INV_VALUE;
480
481   *r_nbits = domain_parms[idx].nbits;
482   curve->p = scanval (domain_parms[idx].p);
483   curve->a = scanval (domain_parms[idx].a);
484   curve->b = scanval (domain_parms[idx].b);
485   curve->n = scanval (domain_parms[idx].n);
486   curve->G.x = scanval (domain_parms[idx].g_x);
487   curve->G.y = scanval (domain_parms[idx].g_y);
488   curve->G.z = mpi_alloc_set_ui (1);
489
490   return 0;
491 }
492
493
494 /*
495  * First obtain the setup.  Over the finite field randomize an scalar
496  * secret value, and calculate the public point.
497  */
498 static gpg_err_code_t
499 generate_key (ECC_secret_key *sk, unsigned int nbits, const char *name,
500               gcry_mpi_t g_x, gcry_mpi_t g_y,
501               gcry_mpi_t q_x, gcry_mpi_t q_y)
502 {
503   gpg_err_code_t err;
504   elliptic_curve_t E;
505   gcry_mpi_t d;
506   mpi_point_t Q;
507   mpi_ec_t ctx;
508
509   err = generate_curve (nbits, name, &E, &nbits);
510   if (err)
511     return err;
512
513   if (DBG_CIPHER)
514     {
515       log_mpidump ("ecc generation   p", E.p);
516       log_mpidump ("ecc generation   a", E.a);
517       log_mpidump ("ecc generation   b", E.b);
518       log_mpidump ("ecc generation   n", E.n);
519       log_mpidump ("ecc generation  Gx", E.G.x);
520       log_mpidump ("ecc generation  Gy", E.G.y);
521       log_mpidump ("ecc generation  Gz", E.G.z);
522     }
523
524   if (DBG_CIPHER)
525     log_debug ("choosing a random x of size %u\n", nbits);
526   d = gen_k (E.n, GCRY_VERY_STRONG_RANDOM); 
527
528   /* Compute Q.  */
529   point_init (&Q);
530   ctx = _gcry_mpi_ec_init (E.p, E.a);
531   _gcry_mpi_ec_mul_point (&Q, d, &E.G, ctx);
532
533   /* Copy the stuff to the key structures. */
534   sk->E.p = mpi_copy (E.p);
535   sk->E.a = mpi_copy (E.a);
536   sk->E.b = mpi_copy (E.b);
537   point_init (&sk->E.G);
538   point_set (&sk->E.G, &E.G);
539   sk->E.n = mpi_copy (E.n);
540   point_init (&sk->Q);
541   point_set (&sk->Q, &Q);
542   sk->d    = mpi_copy (d);
543   /* We also return copies of G and Q in affine coordinates if
544      requested.  */
545   if (g_x && g_y)
546     {
547       if (_gcry_mpi_ec_get_affine (g_x, g_y, &sk->E.G, ctx))
548         log_fatal ("ecc generate: Failed to get affine coordinates\n");
549     }
550   if (q_x && q_y)
551     {
552       if (_gcry_mpi_ec_get_affine (q_x, q_y, &sk->Q, ctx))
553         log_fatal ("ecc generate: Failed to get affine coordinates\n");
554     }
555   _gcry_mpi_ec_free (ctx);
556
557   point_free (&Q);
558   mpi_free (d);
559   curve_free (&E);
560
561   /* Now we can test our keys (this should never fail!). */
562   test_keys (sk, nbits - 64);
563
564   return 0;
565 }
566
567
568 /****************
569  * To verify correct skey it use a random information.
570  * First, encrypt and decrypt this dummy value,
571  * test if the information is recuperated.
572  * Second, test with the sign and verify functions.
573  */
574 static void
575 test_keys (ECC_secret_key *sk, unsigned int nbits)
576 {
577   ECC_public_key pk;
578   gcry_mpi_t test = mpi_new (nbits);
579   mpi_point_t R_;
580   gcry_mpi_t c = mpi_new (nbits);
581   gcry_mpi_t out = mpi_new (nbits);
582   gcry_mpi_t r = mpi_new (nbits);
583   gcry_mpi_t s = mpi_new (nbits);
584
585   if (DBG_CIPHER)
586     log_debug ("Testing key.\n");
587
588   point_init (&R_);
589
590   pk.E = curve_copy (sk->E);
591   point_init (&pk.Q);
592   point_set (&pk.Q, &sk->Q);
593
594   gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM);
595
596   if (sign (test, sk, r, s) )
597     log_fatal ("ECDSA operation: sign failed\n");
598
599   if (verify (test, &pk, r, s))
600     {
601       log_fatal ("ECDSA operation: sign, verify failed\n");
602     }
603
604   if (DBG_CIPHER)
605     log_debug ("ECDSA operation: sign, verify ok.\n");
606
607   point_free (&pk.Q);
608   curve_free (&pk.E);
609
610   point_free (&R_);
611   mpi_free (s);
612   mpi_free (r);
613   mpi_free (out);
614   mpi_free (c);
615   mpi_free (test);
616 }
617
618 /****************
619  * To check the validity of the value, recalculate the correspondence
620  * between the public value and the secret one.
621  */
622 static int
623 check_secret_key (ECC_secret_key * sk)
624 {
625   mpi_point_t Q;
626   gcry_mpi_t y_2, y2 = mpi_alloc (0);
627   mpi_ec_t ctx;
628
629   /* ?primarity test of 'p' */
630   /*  (...) //!! */
631   /* G in E(F_p) */
632   y_2 = gen_y_2 (sk->E.G.x, &sk->E);   /*  y^2=x^3+a*x+b */
633   mpi_mulm (y2, sk->E.G.y, sk->E.G.y, sk->E.p);      /*  y^2=y*y */
634   if (mpi_cmp (y_2, y2))
635     {
636       if (DBG_CIPHER)
637         log_debug ("Bad check: Point 'G' does not belong to curve 'E'!\n");
638       return (1);
639     }
640   /* G != PaI */
641   if (!mpi_cmp_ui (sk->E.G.z, 0))
642     {
643       if (DBG_CIPHER)
644         log_debug ("Bad check: 'G' cannot be Point at Infinity!\n");
645       return (1);
646     }
647
648   point_init (&Q);
649   ctx = _gcry_mpi_ec_init (sk->E.p, sk->E.a);
650   _gcry_mpi_ec_mul_point (&Q, sk->E.n, &sk->E.G, ctx);
651   if (mpi_cmp_ui (Q.z, 0))
652     {
653       if (DBG_CIPHER)
654         log_debug ("check_secret_key: E is not a curve of order n\n");
655       point_free (&Q);
656       _gcry_mpi_ec_free (ctx);
657       return 1;
658     }
659   /* pubkey cannot be PaI */
660   if (!mpi_cmp_ui (sk->Q.z, 0))
661     {
662       if (DBG_CIPHER)
663         log_debug ("Bad check: Q can not be a Point at Infinity!\n");
664       _gcry_mpi_ec_free (ctx);
665       return (1);
666     }
667   /* pubkey = [d]G over E */
668   _gcry_mpi_ec_mul_point (&Q, sk->d, &sk->E.G, ctx);
669   if ((Q.x == sk->Q.x) && (Q.y == sk->Q.y) && (Q.z == sk->Q.z))
670     {
671       if (DBG_CIPHER)
672         log_debug
673           ("Bad check: There is NO correspondence between 'd' and 'Q'!\n");
674       _gcry_mpi_ec_free (ctx);
675       return (1);
676     }
677   _gcry_mpi_ec_free (ctx);
678   point_free (&Q);
679   return 0;
680 }
681
682
683 /*
684  * Return the signature struct (r,s) from the message hash.  The caller
685  * must have allocated R and S.
686  */
687 static gpg_err_code_t
688 sign (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s)
689 {
690   gpg_err_code_t err = 0;
691   gcry_mpi_t k, dr, sum, k_1, x;
692   mpi_point_t I;
693   mpi_ec_t ctx;
694
695   k = NULL;
696   dr = mpi_alloc (0);
697   sum = mpi_alloc (0);
698   k_1 = mpi_alloc (0);
699   x = mpi_alloc (0);
700   point_init (&I);
701
702   mpi_set_ui (s, 0);
703   mpi_set_ui (r, 0);
704
705   ctx = _gcry_mpi_ec_init (skey->E.p, skey->E.a);
706
707   while (!mpi_cmp_ui (s, 0)) /* s == 0 */
708     {
709       while (!mpi_cmp_ui (r, 0)) /* r == 0 */
710         {
711           /* Note, that we are guaranteed to enter this loop at least
712              once because r has been intialized to 0.  We can't use a
713              do_while because we want to keep the value of R even if S
714              has to be recomputed.  */
715           mpi_free (k);
716           k = gen_k (skey->E.n, GCRY_STRONG_RANDOM);
717           _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx); 
718           if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx))
719             {
720               if (DBG_CIPHER)
721                 log_debug ("ecc sign: Failed to get affine coordinates\n");
722               err = GPG_ERR_BAD_SIGNATURE;
723               goto leave;
724             }
725           mpi_mod (r, x, skey->E.n);  /* r = x mod n */
726         }
727       mpi_mulm (dr, skey->d, r, skey->E.n); /* dr = d*r mod n  */
728       mpi_addm (sum, input, dr, skey->E.n); /* sum = hash + (d*r) mod n  */
729       mpi_invm (k_1, k, skey->E.n);         /* k_1 = k^(-1) mod n  */
730       mpi_mulm (s, k_1, sum, skey->E.n);    /* s = k^(-1)*(hash+(d*r)) mod n */
731     }
732
733  leave:
734   _gcry_mpi_ec_free (ctx);
735   point_free (&I);
736   mpi_free (x);
737   mpi_free (k_1);
738   mpi_free (sum);
739   mpi_free (dr);
740   mpi_free (k);
741
742   return err;
743 }
744
745 /*
746  * Check if R and S verifies INPUT.
747  */
748 static gpg_err_code_t
749 verify (gcry_mpi_t input, ECC_public_key *pkey, gcry_mpi_t r, gcry_mpi_t s)
750 {
751   gpg_err_code_t err = 0;
752   gcry_mpi_t h, h1, h2, x, y;
753   mpi_point_t Q, Q1, Q2;
754   mpi_ec_t ctx;
755
756   if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) )
757     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < r < n  failed.  */
758   if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) )
759     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < s < n  failed.  */
760
761   h  = mpi_alloc (0);
762   h1 = mpi_alloc (0);
763   h2 = mpi_alloc (0);
764   x = mpi_alloc (0);
765   y = mpi_alloc (0);
766   point_init (&Q);
767   point_init (&Q1);
768   point_init (&Q2);
769
770   ctx = _gcry_mpi_ec_init (pkey->E.p, pkey->E.a);
771
772   /* h  = s^(-1) (mod n) */
773   mpi_invm (h, s, pkey->E.n);
774 /*   log_mpidump ("   h", h); */
775   /* h1 = hash * s^(-1) (mod n) */
776   mpi_mulm (h1, input, h, pkey->E.n);
777 /*   log_mpidump ("  h1", h1); */
778   /* Q1 = [ hash * s^(-1) ]G  */
779   _gcry_mpi_ec_mul_point (&Q1, h1, &pkey->E.G, ctx);
780 /*   log_mpidump ("Q1.x", Q1.x); */
781 /*   log_mpidump ("Q1.y", Q1.y); */
782 /*   log_mpidump ("Q1.z", Q1.z); */
783   /* h2 = r * s^(-1) (mod n) */
784   mpi_mulm (h2, r, h, pkey->E.n);
785 /*   log_mpidump ("  h2", h2); */
786   /* Q2 = [ r * s^(-1) ]Q */
787   _gcry_mpi_ec_mul_point (&Q2, h2, &pkey->Q, ctx);
788 /*   log_mpidump ("Q2.x", Q2.x); */
789 /*   log_mpidump ("Q2.y", Q2.y); */
790 /*   log_mpidump ("Q2.z", Q2.z); */
791   /* Q  = ([hash * s^(-1)]G) + ([r * s^(-1)]Q) */
792   _gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ctx);
793 /*   log_mpidump (" Q.x", Q.x); */
794 /*   log_mpidump (" Q.y", Q.y); */
795 /*   log_mpidump (" Q.z", Q.z); */
796
797   if (!mpi_cmp_ui (Q.z, 0))
798     {
799       if (DBG_CIPHER)
800           log_debug ("ecc verify: Rejected\n");
801       err = GPG_ERR_BAD_SIGNATURE;
802       goto leave;
803     }
804   if (_gcry_mpi_ec_get_affine (x, y, &Q, ctx))
805     {
806       if (DBG_CIPHER)
807         log_debug ("ecc verify: Failed to get affine coordinates\n");
808       err = GPG_ERR_BAD_SIGNATURE;
809       goto leave;
810     }
811   mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */
812   if (mpi_cmp (x, r))   /* x != r */
813     {
814       if (DBG_CIPHER)
815         {
816           log_mpidump ("   x", x);
817           log_mpidump ("   y", y);
818           log_mpidump ("   r", r);
819           log_mpidump ("   s", s);
820           log_debug ("ecc verify: Not verified\n");
821         }
822       err = GPG_ERR_BAD_SIGNATURE;
823       goto leave;
824     }
825   if (DBG_CIPHER)
826     log_debug ("ecc verify: Accepted\n");
827
828  leave:
829   _gcry_mpi_ec_free (ctx);
830   point_free (&Q2);
831   point_free (&Q1);
832   point_free (&Q);
833   mpi_free (y);
834   mpi_free (x);
835   mpi_free (h2);
836   mpi_free (h1);
837   mpi_free (h);
838   return err;
839 }
840
841
842
843 /*********************************************
844  **************  interface  ******************
845  *********************************************/
846 static gcry_mpi_t
847 ec2os (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t p)
848 {
849   gpg_error_t err;
850   int pbytes = (mpi_get_nbits (p)+7)/8;
851   size_t n;
852   unsigned char *buf, *ptr;
853   gcry_mpi_t result;
854
855   buf = gcry_xmalloc ( 1 + 2*pbytes );
856   *buf = 04; /* Uncompressed point.  */
857   ptr = buf+1;
858   err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, x);
859   if (err)
860     log_fatal ("mpi_print failed: %s\n", gpg_strerror (err));
861   if (n < pbytes)
862     {
863       memmove (ptr+(pbytes-n), ptr, n);
864       memset (ptr, 0, (pbytes-n));
865     }
866   ptr += pbytes;
867   err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, y);
868   if (err)
869     log_fatal ("mpi_print failed: %s\n", gpg_strerror (err));
870   if (n < pbytes)
871     {
872       memmove (ptr+(pbytes-n), ptr, n);
873       memset (ptr, 0, (pbytes-n));
874     }
875   
876   err = gcry_mpi_scan (&result, GCRYMPI_FMT_USG, buf, 1+2*pbytes, NULL);
877   if (err)
878     log_fatal ("mpi_scan failed: %s\n", gpg_strerror (err));
879   gcry_free (buf);
880
881   mpi_free (x);
882   mpi_free (y);
883
884   return result;
885 }
886
887 /* RESULT must have been initialized and is set on success to the
888    point given by VALUE.  */
889 static gcry_error_t
890 os2ec (mpi_point_t *result, gcry_mpi_t value)
891 {
892   gcry_error_t err;
893   size_t n;
894   unsigned char *buf;
895   gcry_mpi_t x, y;
896
897   n = (mpi_get_nbits (value)+7)/8;
898   buf = gcry_xmalloc (n);
899   err = gcry_mpi_print (GCRYMPI_FMT_USG, buf, n, &n, value);
900   if (err)
901     {
902       gcry_free (buf);
903       return err;
904     }
905   if (n < 1) 
906     {
907       gcry_free (buf);
908       return GPG_ERR_INV_OBJ;
909     }
910   if (*buf != 4)
911     {
912       gcry_free (buf);
913       return GPG_ERR_NOT_IMPLEMENTED; /* No support for point compression.  */
914     }
915   if ( ((n-1)%2) ) 
916     {
917       gcry_free (buf);
918       return GPG_ERR_INV_OBJ;
919     }
920   n = (n-1)/2;
921   err = gcry_mpi_scan (&x, GCRYMPI_FMT_USG, buf+1, n, NULL);
922   if (err)
923     {
924       gcry_free (buf);
925       return err;
926     }
927   err = gcry_mpi_scan (&y, GCRYMPI_FMT_USG, buf+1+n, n, NULL);
928   gcry_free (buf);
929   if (err)
930     {
931       mpi_free (x);
932       return err;
933     }
934
935   mpi_set (result->x, x);
936   mpi_set (result->y, y);
937   mpi_set_ui (result->z, 1);
938
939   mpi_free (x);
940   mpi_free (y);
941   
942   return 0;
943 }
944
945 /* Extended version of ecc_generate which is called directly by
946    pubkey.c.  If CURVE is not NULL, that name will be used to select
947    the domain parameters.  NBITS is not used in this case.  */
948 gcry_err_code_t
949 _gcry_ecc_generate (int algo, unsigned int nbits, const char *curve,
950                     gcry_mpi_t *skey, gcry_mpi_t **retfactors)
951 {
952   gpg_err_code_t err;
953   ECC_secret_key sk;
954   gcry_mpi_t g_x, g_y, q_x, q_y;
955
956   (void)algo;
957
958   /* Make an empty list of factors.  */
959   *retfactors = gcry_calloc ( 1, sizeof **retfactors );
960   if (!*retfactors)
961     return gpg_err_code_from_syserror ();
962
963   g_x = mpi_new (0);
964   g_y = mpi_new (0);
965   q_x = mpi_new (0);
966   q_y = mpi_new (0);
967   err = generate_key (&sk, nbits, curve, g_x, g_y, q_x, q_y);
968   if (err)
969     {
970       gcry_free (*retfactors);
971       *retfactors = NULL;
972       return err;
973     }
974
975   skey[0] = sk.E.p;
976   skey[1] = sk.E.a;
977   skey[2] = sk.E.b;
978   /* The function ec2os releases g_x and g_y.  */
979   skey[3] = ec2os (g_x, g_y, sk.E.p);
980   skey[4] = sk.E.n;
981   /* The function ec2os releases g_x and g_y.  */
982   skey[5] = ec2os (q_x, q_y, sk.E.p);
983   skey[6] = sk.d;
984
985   point_free (&sk.E.G);
986   point_free (&sk.Q);
987
988   return 0;
989 }
990
991 /* Return the parameters of the curve NAME.  */
992 gcry_err_code_t
993 _gcry_ecc_get_param (const char *name, gcry_mpi_t *pkey)
994 {
995   gpg_err_code_t err;
996   unsigned int nbits;
997   elliptic_curve_t E;
998   mpi_ec_t ctx;
999   gcry_mpi_t g_x, g_y;
1000   
1001   err = generate_curve (0, name, &E, &nbits);
1002   if (err)
1003     return err;
1004
1005   g_x = mpi_new (0);
1006   g_y = mpi_new (0);
1007   ctx = _gcry_mpi_ec_init (E.p, E.a);
1008   if (_gcry_mpi_ec_get_affine (g_x, g_y, &E.G, ctx))
1009     log_fatal ("ecc get param: Failed to get affine coordinates\n");
1010   _gcry_mpi_ec_free (ctx);
1011   point_free (&E.G);
1012
1013   pkey[0] = E.p;
1014   pkey[1] = E.a;
1015   pkey[2] = E.b;
1016   pkey[3] = ec2os (g_x, g_y, E.p);
1017   pkey[4] = E.n;
1018   pkey[5] = NULL;
1019
1020   return 0;
1021 }
1022
1023 static gcry_err_code_t
1024 ecc_generate (int algo, unsigned int nbits, unsigned long dummy,
1025               gcry_mpi_t *skey, gcry_mpi_t **retfactors)
1026 {
1027   (void)dummy;
1028   return _gcry_ecc_generate (algo, nbits, NULL, skey, retfactors);
1029 }
1030
1031
1032 static gcry_err_code_t
1033 ecc_check_secret_key (int algo, gcry_mpi_t *skey)
1034 {
1035   gpg_err_code_t err;
1036   ECC_secret_key sk;
1037
1038   (void)algo;
1039
1040   if (!skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] || !skey[5]
1041       || !skey[6] || !skey[7] || !skey[8] || !skey[9] || !skey[10])
1042     return GPG_ERR_BAD_MPI;
1043
1044   sk.E.p = skey[0];
1045   sk.E.a = skey[1];
1046   sk.E.b = skey[2];
1047   point_init (&sk.E.G);
1048   err = os2ec (&sk.E.G, skey[3]);
1049   if (err)
1050     {
1051       point_free (&sk.E.G);
1052       return err;
1053     }
1054   sk.E.n = skey[4];
1055   point_init (&sk.Q);
1056   err = os2ec (&sk.Q, skey[5]);
1057   if (err)
1058     {
1059       point_free (&sk.E.G);
1060       point_free (&sk.Q);
1061       return err;
1062     }
1063
1064   sk.d = skey[6];
1065
1066   if (check_secret_key (&sk))
1067     {
1068       point_free (&sk.E.G);
1069       point_free (&sk.Q);
1070       return GPG_ERR_BAD_SECKEY;
1071     }
1072   point_free (&sk.E.G);
1073   point_free (&sk.Q);
1074   return 0;
1075 }
1076
1077
1078 static gcry_err_code_t
1079 ecc_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
1080 {
1081   gpg_err_code_t err;
1082   ECC_secret_key sk;
1083
1084   (void)algo;
1085
1086   if (!data || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4]
1087       || !skey[5] || !skey[6] )
1088     return GPG_ERR_BAD_MPI;
1089
1090   sk.E.p = skey[0];
1091   sk.E.a = skey[1];
1092   sk.E.b = skey[2];
1093   point_init (&sk.E.G);
1094   err = os2ec (&sk.E.G, skey[3]);
1095   if (err)
1096     {
1097       point_free (&sk.E.G);
1098       return err;
1099     }
1100   sk.E.n = skey[4];
1101   point_init (&sk.Q);
1102   err = os2ec (&sk.Q, skey[5]);
1103   if (err)
1104     {
1105       point_free (&sk.E.G);
1106       point_free (&sk.Q);
1107       return err;
1108     }
1109   sk.d = skey[6];
1110
1111   resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.E.p));
1112   resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.E.p));
1113   err = sign (data, &sk, resarr[0], resarr[1]);
1114   if (err)
1115     {
1116       mpi_free (resarr[0]);
1117       mpi_free (resarr[1]);
1118       resarr[0] = NULL; /* Mark array as released.  */
1119     }
1120   point_free (&sk.E.G);
1121   point_free (&sk.Q);
1122   return err;
1123 }
1124
1125 static gcry_err_code_t
1126 ecc_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
1127             int (*cmp)(void *, gcry_mpi_t), void *opaquev)
1128 {
1129   gpg_err_code_t err;
1130   ECC_public_key pk;
1131
1132   (void)algo;
1133   (void)cmp;
1134   (void)opaquev;
1135
1136   if (!data[0] || !data[1] || !hash || !pkey[0] || !pkey[1] || !pkey[2]
1137       || !pkey[3] || !pkey[4] || !pkey[5] )
1138     return GPG_ERR_BAD_MPI;
1139
1140   pk.E.p = pkey[0];
1141   pk.E.a = pkey[1];
1142   pk.E.b = pkey[2];
1143   point_init (&pk.E.G);
1144   err = os2ec (&pk.E.G, pkey[3]);
1145   if (err)
1146     {
1147       point_free (&pk.E.G);
1148       return err;
1149     }
1150   pk.E.n = pkey[4];
1151   point_init (&pk.Q);
1152   err = os2ec (&pk.Q, pkey[5]);
1153   if (err)
1154     {
1155       point_free (&pk.E.G);
1156       point_free (&pk.Q);
1157       return err;
1158     }
1159
1160   err = verify (hash, &pk, data[0], data[1]);
1161
1162   point_free (&pk.E.G);
1163   point_free (&pk.Q);
1164   return err;
1165 }
1166
1167
1168
1169 static unsigned int
1170 ecc_get_nbits (int algo, gcry_mpi_t *pkey)
1171 {
1172   (void)algo;
1173
1174   return mpi_get_nbits (pkey[0]);
1175 }
1176
1177
1178 static const char *ecdsa_names[] =
1179   {
1180     "ecdsa",
1181     "ecc",
1182     NULL,
1183   };
1184
1185 gcry_pk_spec_t _gcry_pubkey_spec_ecdsa =
1186   {
1187     "ECDSA", ecdsa_names,
1188     "pabgnq", "pabgnqd", "", "rs", "pabgnq",
1189     GCRY_PK_USAGE_SIGN,
1190     ecc_generate,
1191     ecc_check_secret_key,
1192     NULL,
1193     NULL,
1194     ecc_sign,
1195     ecc_verify,
1196     ecc_get_nbits
1197   };
1198