./
[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
102     { "NIST P-256", "1.2.840.10045.3.1.7" }, 
103     { "NIST P-256", "prime256v1" },          
104     { "NIST P-256", "secp256r1"  },          
105
106     { "NIST P-384", "secp384r1" },
107
108     { "NIST P-521", "secp521r1" },
109
110     { NULL, NULL}
111   };
112
113
114
115 /* This static table defines all available curves.  */
116 static const struct
117 {
118   const char *desc;           /* Description of the curve.  */
119   unsigned int nbits;         /* Number of bits.  */
120   const char  *p;             /* Order of the prime field.  */
121   const char *a, *b;          /* The coefficients. */
122   const char *n;              /* The order of the base point.  */
123   const char *g_x, *g_y;      /* Base point.  */
124 } domain_parms[] =
125   {
126     { "secp160r1", 160,
127       "0x",
128       "0x",
129       "0x",
130       "0x",
131
132       "0x",
133       "0x"
134     }, 
135
136     {
137       "NIST P-192", 192,
138       "0xfffffffffffffffffffffffffffffffeffffffffffffffff",
139       "0xfffffffffffffffffffffffffffffffefffffffffffffffc",
140       "0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1",
141       "0xffffffffffffffffffffffff99def836146bc9b1b4d22831",
142
143       "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012",
144       "0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
145     },
146     {
147       "NIST P-224", 224,
148       "0xffffffffffffffffffffffffffffffff000000000000000000000001",
149       "0xfffffffffffffffffffffffffffffffefffffffffffffffffffffffe",
150       "0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4",
151       "0xffffffffffffffffffffffffffff16a2e0b8f03e13dd29455c5c2a3d" ,
152
153       "0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21",
154       "0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34"
155     },
156     {
157       "NIST P-256", 256,
158       "0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff",
159       "0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc",
160       "0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b",
161       "0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551",
162
163       "0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296",
164       "0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5"
165     },
166     {
167       "NIST P-384", 384,
168       "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
169       "ffffffff0000000000000000ffffffff",
170       "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
171       "ffffffff0000000000000000fffffffc",
172       "0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875a"
173       "c656398d8a2ed19d2a85c8edd3ec2aef",
174       "0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf"
175       "581a0db248b0a77aecec196accc52973",
176
177       "0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a38"
178       "5502f25dbf55296c3a545e3872760ab7",
179       "0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c0"
180       "0a60b1ce1d7e819d7a431d7c90ea0e5f"
181     },
182     {
183       "NIST P-521", 521,
184       "0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
185       "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
186       "0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
187       "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc",
188       "0x051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef10"
189       "9e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00",
190       "0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
191       "ffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409",
192
193       "0xc6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3d"
194       "baa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66",
195       "0x11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e6"
196       "62c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650"
197     },
198     { NULL, 0, NULL, NULL, NULL, NULL }
199   };
200
201
202 /* Registered progress function and its callback value. */
203 static void (*progress_cb) (void *, const char*, int, int, int);
204 static void *progress_cb_data;
205
206
207 #define point_init(a)  _gcry_mpi_ec_point_init ((a))
208 #define point_free(a)  _gcry_mpi_ec_point_free ((a))
209
210
211 \f
212 /* Local prototypes. */
213 static gcry_mpi_t gen_k (gcry_mpi_t p, int security_level);
214 static void test_keys (ECC_secret_key * sk, unsigned int nbits);
215 static int check_secret_key (ECC_secret_key * sk);
216 static gpg_err_code_t sign (gcry_mpi_t input, ECC_secret_key *skey,
217                             gcry_mpi_t r, gcry_mpi_t s);
218 static gpg_err_code_t verify (gcry_mpi_t input, ECC_public_key *pkey,
219                               gcry_mpi_t r, gcry_mpi_t s);
220
221
222 static gcry_mpi_t gen_y_2 (gcry_mpi_t x, elliptic_curve_t * base);
223
224
225
226 \f
227 void
228 _gcry_register_pk_ecc_progress (void (*cb) (void *, const char *,
229                                             int, int, int),
230                                 void *cb_data)
231 {
232   progress_cb = cb;
233   progress_cb_data = cb_data;
234 }
235
236 /* static void */
237 /* progress (int c) */
238 /* { */
239 /*   if (progress_cb) */
240 /*     progress_cb (progress_cb_data, "pk_ecc", c, 0, 0); */
241 /* } */
242
243
244 \f
245
246 /* Set the value from S into D.  */
247 static void
248 point_set (mpi_point_t *d, mpi_point_t *s)
249 {
250   mpi_set (d->x, s->x);
251   mpi_set (d->y, s->y);
252   mpi_set (d->z, s->z);
253 }
254
255
256 /*
257  * Release a curve object.
258  */
259 static void
260 curve_free (elliptic_curve_t *E)
261 {
262   mpi_free (E->p); E->p = NULL;
263   mpi_free (E->a); E->a = NULL;
264   mpi_free (E->b);  E->b = NULL;
265   point_free (&E->G);
266   mpi_free (E->n);  E->n = NULL;
267 }
268
269
270 /*
271  * Return a copy of a curve object.
272  */
273 static elliptic_curve_t
274 curve_copy (elliptic_curve_t E)
275 {
276   elliptic_curve_t R;
277
278   R.p = mpi_copy (E.p);
279   R.a = mpi_copy (E.a);
280   R.b = mpi_copy (E.b);
281   point_init (&R.G);
282   point_set (&R.G, &E.G);
283   R.n = mpi_copy (E.n);
284
285   return R;
286 }
287
288
289
290 /* Helper to scan a hex string. */
291 static gcry_mpi_t
292 scanval (const char *string)
293 {
294   gpg_error_t err;
295   gcry_mpi_t val;
296
297   err = gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL);
298   if (err)
299     log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (err));
300   return val;
301 }
302
303
304
305 \f
306
307 /****************
308  * Solve the right side of the equation that defines a curve.
309  */
310 static gcry_mpi_t
311 gen_y_2 (gcry_mpi_t x, elliptic_curve_t *base)
312 {
313   gcry_mpi_t three, x_3, axb, y;
314
315   three = mpi_alloc_set_ui (3);
316   x_3 = mpi_new (0);
317   axb = mpi_new (0);
318   y   = mpi_new (0);
319
320   mpi_powm (x_3, x, three, base->p);  
321   mpi_mulm (axb, base->a, x, base->p); 
322   mpi_addm (axb, axb, base->b, base->p);     
323   mpi_addm (y, x_3, axb, base->p);    
324
325   mpi_free (x_3);
326   mpi_free (axb);
327   mpi_free (three);
328   return y; /* The quadratic value of the coordinate if it exist. */
329 }
330
331
332
333
334
335 /* Generate a random secret scalar k with an order of p
336
337    At the beginning this was identical to the code is in elgamal.c.
338    Later imporved by mmr.   Further simplified by wk.  */
339 static gcry_mpi_t
340 gen_k (gcry_mpi_t p, int security_level)
341 {
342   gcry_mpi_t k;
343   unsigned int nbits;
344
345   nbits = mpi_get_nbits (p);
346   k = mpi_snew (nbits);
347   if (DBG_CIPHER)
348     log_debug ("choosing a random k of %u bits\n", nbits);
349
350   gcry_mpi_randomize (k, nbits, security_level);
351
352   mpi_mod (k, k, p);  /*  k = k mod p  */
353
354   return k;
355 }
356
357 /****************
358  * Generate the crypto system setup.
359  * As of now the fix NIST recommended values are used.
360  * The subgroup generator point is in another function: gen_big_point.
361  */
362 static gpg_err_code_t
363 generate_curve (unsigned int nbits, const char *name, 
364                 elliptic_curve_t *curve, unsigned int *r_nbits)
365 {
366   int idx;
367
368   if (name)
369     {
370       for (idx = 0; domain_parms[idx].desc; idx++)
371         if (!strcmp (name, domain_parms[idx].desc))
372           break;
373     }
374   else
375     {
376       for (idx = 0; domain_parms[idx].desc; idx++)
377         if (nbits == domain_parms[idx].nbits)
378           break;
379     }
380   if (!domain_parms[idx].desc)
381     return GPG_ERR_INV_VALUE;
382
383   *r_nbits = domain_parms[idx].nbits;
384   curve->p = scanval (domain_parms[idx].p);
385   curve->a = scanval (domain_parms[idx].a);
386   curve->b = scanval (domain_parms[idx].b);
387   curve->n = scanval (domain_parms[idx].n);
388   curve->G.x = scanval (domain_parms[idx].g_x);
389   curve->G.y = scanval (domain_parms[idx].g_y);
390   curve->G.z = mpi_alloc_set_ui (1);
391
392   return 0;
393 }
394
395
396 /*
397  * First obtain the setup.  Over the finite field randomize an scalar
398  * secret value, and calculate the public point.
399  */
400 static gpg_err_code_t
401 generate_key (ECC_secret_key *sk, unsigned int nbits, const char *name,
402               gcry_mpi_t g_x, gcry_mpi_t g_y,
403               gcry_mpi_t q_x, gcry_mpi_t q_y)
404 {
405   gpg_err_code_t err;
406   elliptic_curve_t E;
407   gcry_mpi_t d;
408   mpi_point_t Q, G;
409   mpi_ec_t ctx;
410
411   err = generate_curve (nbits, name, &E, &nbits);
412   if (err)
413     return err;
414
415   if (DBG_CIPHER)
416     {
417       log_mpidump ("ecc generation   p", E.p);
418       log_mpidump ("ecc generation   a", E.a);
419       log_mpidump ("ecc generation   b", E.b);
420       log_mpidump ("ecc generation   n", E.n);
421       log_mpidump ("ecc generation  Gx", E.G.x);
422       log_mpidump ("ecc generation  Gy", E.G.y);
423       log_mpidump ("ecc generation  Gz", E.G.z);
424     }
425
426   d = mpi_snew (nbits);
427   if (DBG_CIPHER)
428     log_debug ("choosing a random x of size %u\n", nbits);
429   d = gen_k (E.n, GCRY_VERY_STRONG_RANDOM); 
430   point_init (&G);
431   point_set (&G, &E.G);
432
433   /* Compute Q.  */
434   point_init (&Q);
435   ctx = _gcry_mpi_ec_init (E.p, E.a);
436   _gcry_mpi_ec_mul_point (&Q, d, &E.G, ctx);
437
438   /* Copy the stuff to the key structures. */
439   sk->E.p = mpi_copy (E.p);
440   sk->E.a = mpi_copy (E.a);
441   sk->E.b = mpi_copy (E.b);
442   point_init (&sk->E.G);
443   point_set (&sk->E.G, &E.G);
444   sk->E.n = mpi_copy (E.n);
445   point_init (&sk->Q);
446   point_set (&sk->Q, &Q);
447   sk->d    = mpi_copy (d);
448   /* We also return copies of G and Q in affine coordinates if
449      requested.  */
450   if (g_x && q_x)
451     {
452       if (_gcry_mpi_ec_get_affine (g_x, g_y, &sk->E.G, ctx))
453         log_fatal ("ecc generate: Failed to get affine coordinates\n");
454     }
455   if (q_x && q_x)
456     {
457       if (_gcry_mpi_ec_get_affine (q_x, q_y, &sk->Q, ctx))
458         log_fatal ("ecc generate: Failed to get affine coordinates\n");
459     }
460   _gcry_mpi_ec_free (ctx);
461
462   point_free (&Q);
463   mpi_free (d);
464   curve_free (&E);
465
466   /* Now we can test our keys (this should never fail!). */
467   test_keys (sk, nbits - 64);
468
469   return 0;
470 }
471
472
473 /****************
474  * To verify correct skey it use a random information.
475  * First, encrypt and decrypt this dummy value,
476  * test if the information is recuperated.
477  * Second, test with the sign and verify functions.
478  */
479 static void
480 test_keys (ECC_secret_key *sk, unsigned int nbits)
481 {
482   ECC_public_key pk;
483   gcry_mpi_t test = mpi_new (nbits);
484   mpi_point_t R_;
485   gcry_mpi_t c = mpi_new (nbits);
486   gcry_mpi_t out = mpi_new (nbits);
487   gcry_mpi_t r = mpi_new (nbits);
488   gcry_mpi_t s = mpi_new (nbits);
489
490   if (DBG_CIPHER)
491     log_debug ("Testing key.\n");
492
493   point_init (&R_);
494
495   pk.E = curve_copy (sk->E);
496   point_init (&pk.Q);
497   point_set (&pk.Q, &sk->Q);
498
499   gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM);
500
501   if (sign (test, sk, r, s) )
502     log_fatal ("ECDSA operation: sign failed\n");
503
504   if (verify (test, &pk, r, s))
505     {
506       log_fatal ("ECDSA operation: sign, verify failed\n");
507     }
508
509   if (DBG_CIPHER)
510     log_debug ("ECDSA operation: sign, verify ok.\n");
511
512   point_free (&pk.Q);
513   curve_free (&pk.E);
514
515   point_free (&R_);
516   mpi_free (s);
517   mpi_free (r);
518   mpi_free (out);
519   mpi_free (c);
520   mpi_free (test);
521 }
522
523 /****************
524  * To check the validity of the value, recalculate the correspondence
525  * between the public value and the secret one.
526  */
527 static int
528 check_secret_key (ECC_secret_key * sk)
529 {
530   mpi_point_t Q;
531   gcry_mpi_t y_2, y2 = mpi_alloc (0);
532   mpi_ec_t ctx;
533
534   /* ?primarity test of 'p' */
535   /*  (...) //!! */
536   /* G in E(F_p) */
537   y_2 = gen_y_2 (sk->E.G.x, &sk->E);   /*  y^2=x^3+a*x+b */
538   mpi_mulm (y2, sk->E.G.y, sk->E.G.y, sk->E.p);      /*  y^2=y*y */
539   if (mpi_cmp (y_2, y2))
540     {
541       if (DBG_CIPHER)
542         log_debug ("Bad check: Point 'G' does not belong to curve 'E'!\n");
543       return (1);
544     }
545   /* G != PaI */
546   if (!mpi_cmp_ui (sk->E.G.z, 0))
547     {
548       if (DBG_CIPHER)
549         log_debug ("Bad check: 'G' cannot be Point at Infinity!\n");
550       return (1);
551     }
552
553   point_init (&Q);
554   ctx = _gcry_mpi_ec_init (sk->E.p, sk->E.a);
555   _gcry_mpi_ec_mul_point (&Q, sk->E.n, &sk->E.G, ctx);
556   if (mpi_cmp_ui (Q.z, 0))
557     {
558       if (DBG_CIPHER)
559         log_debug ("check_secret_key: E is not a curve of order n\n");
560       point_free (&Q);
561       _gcry_mpi_ec_free (ctx);
562       return 1;
563     }
564   /* pubkey cannot be PaI */
565   if (!mpi_cmp_ui (sk->Q.z, 0))
566     {
567       if (DBG_CIPHER)
568         log_debug ("Bad check: Q can not be a Point at Infinity!\n");
569       _gcry_mpi_ec_free (ctx);
570       return (1);
571     }
572   /* pubkey = [d]G over E */
573   _gcry_mpi_ec_mul_point (&Q, sk->d, &sk->E.G, ctx);
574   if ((Q.x == sk->Q.x) && (Q.y == sk->Q.y) && (Q.z == sk->Q.z))
575     {
576       if (DBG_CIPHER)
577         log_debug
578           ("Bad check: There is NO correspondence between 'd' and 'Q'!\n");
579       _gcry_mpi_ec_free (ctx);
580       return (1);
581     }
582   _gcry_mpi_ec_free (ctx);
583   point_free (&Q);
584   return 0;
585 }
586
587
588 /*
589  * Return the signature struct (r,s) from the message hash.  The caller
590  * must have allocated R and S.
591  */
592 static gpg_err_code_t
593 sign (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s)
594 {
595   gpg_err_code_t err = 0;
596   gcry_mpi_t k, dr, sum, k_1, x;
597   mpi_point_t I;
598   mpi_ec_t ctx;
599
600   k = NULL;
601   dr = mpi_alloc (0);
602   sum = mpi_alloc (0);
603   k_1 = mpi_alloc (0);
604   x = mpi_alloc (0);
605   point_init (&I);
606
607   mpi_set_ui (s, 0);
608   mpi_set_ui (r, 0);
609
610   ctx = _gcry_mpi_ec_init (skey->E.p, skey->E.a);
611
612   while (!mpi_cmp_ui (s, 0)) /* s == 0 */
613     {
614       while (!mpi_cmp_ui (r, 0)) /* r == 0 */
615         {
616           /* Note, that we are guaranteed to enter this loop at least
617              once because r has been intialized to 0.  We can't use a
618              do_while because we want to keep the value of R even if S
619              has to be recomputed.  */
620           mpi_free (k);
621           k = gen_k (skey->E.n, GCRY_STRONG_RANDOM);
622           _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx); 
623           if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx))
624             {
625               if (DBG_CIPHER)
626                 log_debug ("ecc sign: Failed to get affine coordinates\n");
627               err = GPG_ERR_BAD_SIGNATURE;
628               goto leave;
629             }
630           mpi_mod (r, x, skey->E.n);  /* r = x mod n */
631         }
632       mpi_mulm (dr, skey->d, r, skey->E.n); /* dr = d*r mod n  */
633       mpi_addm (sum, input, dr, skey->E.n); /* sum = hash + (d*r) mod n  */
634       mpi_invm (k_1, k, skey->E.n);         /* k_1 = k^(-1) mod n  */
635       mpi_mulm (s, k_1, sum, skey->E.n);    /* s = k^(-1)*(hash+(d*r)) mod n */
636     }
637
638  leave:
639   _gcry_mpi_ec_free (ctx);
640   point_free (&I);
641   mpi_free (x);
642   mpi_free (k_1);
643   mpi_free (sum);
644   mpi_free (dr);
645   mpi_free (k);
646
647   return err;
648 }
649
650 /*
651  * Check if R and S verifies INPUT.
652  */
653 static gpg_err_code_t
654 verify (gcry_mpi_t input, ECC_public_key *pkey, gcry_mpi_t r, gcry_mpi_t s)
655 {
656   gpg_err_code_t err = 0;
657   gcry_mpi_t h, h1, h2, x, y;
658   mpi_point_t Q, Q1, Q2;
659   mpi_ec_t ctx;
660
661   if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) )
662     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < r < n  failed.  */
663   if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) )
664     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < s < n  failed.  */
665
666   h  = mpi_alloc (0);
667   h1 = mpi_alloc (0);
668   h2 = mpi_alloc (0);
669   x = mpi_alloc (0);
670   y = mpi_alloc (0);
671   point_init (&Q);
672   point_init (&Q1);
673   point_init (&Q2);
674
675   ctx = _gcry_mpi_ec_init (pkey->E.p, pkey->E.a);
676
677   /* h  = s^(-1) (mod n) */
678   mpi_invm (h, s, pkey->E.n);
679 /*   log_mpidump ("   h", h); */
680   /* h1 = hash * s^(-1) (mod n) */
681   mpi_mulm (h1, input, h, pkey->E.n);
682 /*   log_mpidump ("  h1", h1); */
683   /* Q1 = [ hash * s^(-1) ]G  */
684   _gcry_mpi_ec_mul_point (&Q1, h1, &pkey->E.G, ctx);
685 /*   log_mpidump ("Q1.x", Q1.x); */
686 /*   log_mpidump ("Q1.y", Q1.y); */
687 /*   log_mpidump ("Q1.z", Q1.z); */
688   /* h2 = r * s^(-1) (mod n) */
689   mpi_mulm (h2, r, h, pkey->E.n);
690 /*   log_mpidump ("  h2", h2); */
691   /* Q2 = [ r * s^(-1) ]Q */
692   _gcry_mpi_ec_mul_point (&Q2, h2, &pkey->Q, ctx);
693 /*   log_mpidump ("Q2.x", Q2.x); */
694 /*   log_mpidump ("Q2.y", Q2.y); */
695 /*   log_mpidump ("Q2.z", Q2.z); */
696   /* Q  = ([hash * s^(-1)]G) + ([r * s^(-1)]Q) */
697   _gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ctx);
698 /*   log_mpidump (" Q.x", Q.x); */
699 /*   log_mpidump (" Q.y", Q.y); */
700 /*   log_mpidump (" Q.z", Q.z); */
701
702   if (!mpi_cmp_ui (Q.z, 0))
703     {
704       if (DBG_CIPHER)
705           log_debug ("ecc verify: Rejected\n");
706       err = GPG_ERR_BAD_SIGNATURE;
707       goto leave;
708     }
709   if (_gcry_mpi_ec_get_affine (x, y, &Q, ctx))
710     {
711       if (DBG_CIPHER)
712         log_debug ("ecc verify: Failed to get affine coordinates\n");
713       err = GPG_ERR_BAD_SIGNATURE;
714       goto leave;
715     }
716   mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */
717   if (mpi_cmp (x, r))   /* x != r */
718     {
719       if (DBG_CIPHER)
720         {
721           log_mpidump ("   x", x);
722           log_mpidump ("   y", y);
723           log_mpidump ("   r", r);
724           log_mpidump ("   s", s);
725           log_debug ("ecc verify: Not verified\n");
726         }
727       err = GPG_ERR_BAD_SIGNATURE;
728       goto leave;
729     }
730   if (DBG_CIPHER)
731     log_debug ("ecc verify: Accepted\n");
732
733  leave:
734   _gcry_mpi_ec_free (ctx);
735   point_free (&Q2);
736   point_free (&Q1);
737   point_free (&Q);
738   mpi_free (y);
739   mpi_free (x);
740   mpi_free (h2);
741   mpi_free (h1);
742   mpi_free (h);
743   return err;
744 }
745
746
747
748 /*********************************************
749  **************  interface  ******************
750  *********************************************/
751 static gcry_mpi_t
752 ec2os (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t p)
753 {
754   gpg_error_t err;
755   int pbytes = (mpi_get_nbits (p)+7)/8;
756   size_t n;
757   unsigned char *buf, *ptr;
758   gcry_mpi_t result;
759
760   buf = gcry_xmalloc ( 1 + 2*pbytes );
761   *buf = 04; /* Uncompressed point.  */
762   ptr = buf+1;
763   err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, x);
764   if (err)
765     log_fatal ("mpi_print failed: %s\n", gpg_strerror (err));
766   if (n < pbytes)
767     {
768       memmove (ptr+(pbytes-n), buf+1, n);
769       memset (ptr, 0, (pbytes-n));
770     }
771   ptr += pbytes;
772   err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, y);
773   if (err)
774     log_fatal ("mpi_print failed: %s\n", gpg_strerror (err));
775   if (n < pbytes)
776     {
777       memmove (ptr+(pbytes-n), buf+1, n);
778       memset (ptr, 0, (pbytes-n));
779     }
780   
781   err = gcry_mpi_scan (&result, GCRYMPI_FMT_USG, buf, 1+2*pbytes, NULL);
782   if (err)
783     log_fatal ("mpi_scan failed: %s\n", gpg_strerror (err));
784   gcry_free (buf);
785
786   mpi_free (x);
787   mpi_free (y);
788
789   return result;
790 }
791
792 /* RESULT must have been initialized and is set on success to the
793    point given by VALUE.  */
794 static gcry_error_t
795 os2ec (mpi_point_t *result, gcry_mpi_t value)
796 {
797   gcry_error_t err;
798   size_t n;
799   unsigned char *buf;
800   gcry_mpi_t x, y;
801
802   n = (mpi_get_nbits (value)+7)/8;
803   buf = gcry_xmalloc (n);
804   err = gcry_mpi_print (GCRYMPI_FMT_USG, buf, n, &n, value);
805   if (err)
806     {
807       gcry_free (buf);
808       return err;
809     }
810   if (n < 1) 
811     {
812       gcry_free (buf);
813       return GPG_ERR_INV_OBJ;
814     }
815   if (*buf != 4)
816     {
817       gcry_free (buf);
818       return GPG_ERR_NOT_IMPLEMENTED; /* No support for point compression.  */
819     }
820   if ( ((n-1)%2) ) 
821     {
822       gcry_free (buf);
823       return GPG_ERR_INV_OBJ;
824     }
825   n = (n-1)/2;
826   err = gcry_mpi_scan (&x, GCRYMPI_FMT_USG, buf+1, n, NULL);
827   if (err)
828     {
829       gcry_free (buf);
830       return err;
831     }
832   err = gcry_mpi_scan (&y, GCRYMPI_FMT_USG, buf+1+n, n, NULL);
833   gcry_free (buf);
834   if (err)
835     {
836       mpi_free (x);
837       return err;
838     }
839
840   mpi_set (result->x, x);
841   mpi_set (result->y, y);
842   mpi_set_ui (result->z, 1);
843
844   mpi_free (x);
845   mpi_free (y);
846   
847   return 0;
848 }
849
850 /* Extended version of ecc_generate which is called directly by
851    pubkey.c.  If CURVE is not NULL, that name will be used to select
852    the domain parameters.  NBITS is not used in this case.  */
853 gcry_err_code_t
854 _gcry_ecc_generate (int algo, unsigned int nbits, const char *curve,
855                     gcry_mpi_t *skey, gcry_mpi_t **retfactors)
856 {
857   gpg_err_code_t err;
858   ECC_secret_key sk;
859   gcry_mpi_t g_x, g_y, q_x, q_y;
860
861   (void)algo;
862
863   /* Make an empty list of factors.  */
864   *retfactors = gcry_calloc ( 1, sizeof **retfactors );
865   if (!*retfactors)
866     return gpg_err_code_from_syserror ();
867
868   g_x = mpi_new (0);
869   g_y = mpi_new (0);
870   q_x = mpi_new (0);
871   q_y = mpi_new (0);
872   err = generate_key (&sk, nbits, curve, g_x, g_y, q_x, q_y);
873   if (err)
874     {
875       gcry_free (*retfactors);
876       *retfactors = NULL;
877       return err;
878     }
879
880   skey[0] = sk.E.p;
881   skey[1] = sk.E.a;
882   skey[2] = sk.E.b;
883   skey[3] = ec2os (g_x, g_y, sk.E.p);
884   skey[4] = sk.E.n;
885   skey[5] = ec2os (q_x, q_y, sk.E.p);
886   skey[6] = sk.d;
887
888   return 0;
889 }
890
891
892 static gcry_err_code_t
893 ecc_generate (int algo, unsigned int nbits, unsigned long dummy,
894               gcry_mpi_t *skey, gcry_mpi_t **retfactors)
895 {
896   (void)dummy;
897   return _gcry_ecc_generate (algo, nbits, NULL, skey, retfactors);
898 }
899
900
901 static gcry_err_code_t
902 ecc_check_secret_key (int algo, gcry_mpi_t *skey)
903 {
904   gpg_err_code_t err;
905   ECC_secret_key sk;
906
907   (void)algo;
908
909   if (!skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] || !skey[5]
910       || !skey[6] || !skey[7] || !skey[8] || !skey[9] || !skey[10])
911     return GPG_ERR_BAD_MPI;
912
913   sk.E.p = skey[0];
914   sk.E.a = skey[1];
915   sk.E.b = skey[2];
916   point_init (&sk.E.G);
917   err = os2ec (&sk.E.G, skey[3]);
918   if (err)
919     {
920       point_free (&sk.E.G);
921       return err;
922     }
923   sk.E.n = skey[4];
924   point_init (&sk.Q);
925   err = os2ec (&sk.Q, skey[5]);
926   if (err)
927     {
928       point_free (&sk.E.G);
929       point_free (&sk.Q);
930       return err;
931     }
932
933   sk.d = skey[6];
934
935   if (check_secret_key (&sk))
936     {
937       point_free (&sk.E.G);
938       point_free (&sk.Q);
939       return GPG_ERR_BAD_SECKEY;
940     }
941   point_free (&sk.E.G);
942   point_free (&sk.Q);
943   return 0;
944 }
945
946
947 static gcry_err_code_t
948 ecc_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
949 {
950   gpg_err_code_t err;
951   ECC_secret_key sk;
952
953   (void)algo;
954
955   if (!data || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4]
956       || !skey[5] || !skey[6] )
957     return GPG_ERR_BAD_MPI;
958
959   sk.E.p = skey[0];
960   sk.E.a = skey[1];
961   sk.E.b = skey[2];
962   point_init (&sk.E.G);
963   err = os2ec (&sk.E.G, skey[3]);
964   if (err)
965     {
966       point_free (&sk.E.G);
967       return err;
968     }
969   sk.E.n = skey[4];
970   point_init (&sk.Q);
971   err = os2ec (&sk.Q, skey[5]);
972   if (err)
973     {
974       point_free (&sk.E.G);
975       point_free (&sk.Q);
976       return err;
977     }
978   sk.d = skey[6];
979
980   resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.E.p));
981   resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.E.p));
982   err = sign (data, &sk, resarr[0], resarr[1]);
983   if (err)
984     {
985       mpi_free (resarr[0]);
986       mpi_free (resarr[1]);
987       resarr[0] = NULL; /* Mark array as released.  */
988     }
989   point_free (&sk.E.G);
990   point_free (&sk.Q);
991   return err;
992 }
993
994 static gcry_err_code_t
995 ecc_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
996             int (*cmp)(void *, gcry_mpi_t), void *opaquev)
997 {
998   gpg_err_code_t err;
999   ECC_public_key pk;
1000
1001   (void)algo;
1002   (void)cmp;
1003   (void)opaquev;
1004
1005   if (!data[0] || !data[1] || !hash || !pkey[0] || !pkey[1] || !pkey[2]
1006       || !pkey[3] || !pkey[4] || !pkey[5] )
1007     return GPG_ERR_BAD_MPI;
1008
1009   pk.E.p = pkey[0];
1010   pk.E.a = pkey[1];
1011   pk.E.b = pkey[2];
1012   point_init (&pk.E.G);
1013   err = os2ec (&pk.E.G, pkey[3]);
1014   if (err)
1015     {
1016       point_free (&pk.E.G);
1017       return err;
1018     }
1019   pk.E.n = pkey[4];
1020   point_init (&pk.Q);
1021   err = os2ec (&pk.Q, pkey[5]);
1022   if (err)
1023     {
1024       point_free (&pk.E.G);
1025       point_free (&pk.Q);
1026       return err;
1027     }
1028
1029   err = verify (hash, &pk, data[0], data[1]);
1030
1031   point_free (&pk.E.G);
1032   point_free (&pk.Q);
1033   return err;
1034 }
1035
1036
1037
1038 static unsigned int
1039 ecc_get_nbits (int algo, gcry_mpi_t *pkey)
1040 {
1041   (void)algo;
1042
1043   return mpi_get_nbits (pkey[0]);
1044 }
1045
1046
1047 static const char *ecdsa_names[] =
1048   {
1049     "ecdsa",
1050     NULL,
1051   };
1052
1053 gcry_pk_spec_t _gcry_pubkey_spec_ecdsa =
1054   {
1055     "ECDSA", ecdsa_names,
1056     "pabgnq", "pabgnqd", "", "rs", "pabgnq",
1057     GCRY_PK_USAGE_SIGN,
1058     ecc_generate,
1059     ecc_check_secret_key,
1060     NULL,
1061     NULL,
1062     ecc_sign,
1063     ecc_verify,
1064     ecc_get_nbits
1065   };
1066