Enhanced support for ECDSA.
[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, aliasno;
367
368   if (name)
369     {
370       /* First check nor native curves.  */
371       for (idx = 0; domain_parms[idx].desc; idx++)
372         if (!strcmp (name, domain_parms[idx].desc))
373           break;
374       /* If not found consult the alias table.  */
375       if (!domain_parms[idx].desc)
376         {
377           for (aliasno = 0; curve_aliases[aliasno].name; aliasno++)
378             if (!strcmp (name, curve_aliases[aliasno].other))
379               break;
380           if (curve_aliases[aliasno].name)
381             {
382               for (idx = 0; domain_parms[idx].desc; idx++)
383                 if (!strcmp (curve_aliases[aliasno].name,
384                              domain_parms[idx].desc))
385                   break;
386             }
387         }
388     }
389   else
390     {
391       for (idx = 0; domain_parms[idx].desc; idx++)
392         if (nbits == domain_parms[idx].nbits)
393           break;
394     }
395   if (!domain_parms[idx].desc)
396     return GPG_ERR_INV_VALUE;
397
398   *r_nbits = domain_parms[idx].nbits;
399   curve->p = scanval (domain_parms[idx].p);
400   curve->a = scanval (domain_parms[idx].a);
401   curve->b = scanval (domain_parms[idx].b);
402   curve->n = scanval (domain_parms[idx].n);
403   curve->G.x = scanval (domain_parms[idx].g_x);
404   curve->G.y = scanval (domain_parms[idx].g_y);
405   curve->G.z = mpi_alloc_set_ui (1);
406
407   return 0;
408 }
409
410
411 /*
412  * First obtain the setup.  Over the finite field randomize an scalar
413  * secret value, and calculate the public point.
414  */
415 static gpg_err_code_t
416 generate_key (ECC_secret_key *sk, unsigned int nbits, const char *name,
417               gcry_mpi_t g_x, gcry_mpi_t g_y,
418               gcry_mpi_t q_x, gcry_mpi_t q_y)
419 {
420   gpg_err_code_t err;
421   elliptic_curve_t E;
422   gcry_mpi_t d;
423   mpi_point_t Q, G;
424   mpi_ec_t ctx;
425
426   err = generate_curve (nbits, name, &E, &nbits);
427   if (err)
428     return err;
429
430   if (DBG_CIPHER)
431     {
432       log_mpidump ("ecc generation   p", E.p);
433       log_mpidump ("ecc generation   a", E.a);
434       log_mpidump ("ecc generation   b", E.b);
435       log_mpidump ("ecc generation   n", E.n);
436       log_mpidump ("ecc generation  Gx", E.G.x);
437       log_mpidump ("ecc generation  Gy", E.G.y);
438       log_mpidump ("ecc generation  Gz", E.G.z);
439     }
440
441   d = mpi_snew (nbits);
442   if (DBG_CIPHER)
443     log_debug ("choosing a random x of size %u\n", nbits);
444   d = gen_k (E.n, GCRY_VERY_STRONG_RANDOM); 
445   point_init (&G);
446   point_set (&G, &E.G);
447
448   /* Compute Q.  */
449   point_init (&Q);
450   ctx = _gcry_mpi_ec_init (E.p, E.a);
451   _gcry_mpi_ec_mul_point (&Q, d, &E.G, ctx);
452
453   /* Copy the stuff to the key structures. */
454   sk->E.p = mpi_copy (E.p);
455   sk->E.a = mpi_copy (E.a);
456   sk->E.b = mpi_copy (E.b);
457   point_init (&sk->E.G);
458   point_set (&sk->E.G, &E.G);
459   sk->E.n = mpi_copy (E.n);
460   point_init (&sk->Q);
461   point_set (&sk->Q, &Q);
462   sk->d    = mpi_copy (d);
463   /* We also return copies of G and Q in affine coordinates if
464      requested.  */
465   if (g_x && q_x)
466     {
467       if (_gcry_mpi_ec_get_affine (g_x, g_y, &sk->E.G, ctx))
468         log_fatal ("ecc generate: Failed to get affine coordinates\n");
469     }
470   if (q_x && q_x)
471     {
472       if (_gcry_mpi_ec_get_affine (q_x, q_y, &sk->Q, ctx))
473         log_fatal ("ecc generate: Failed to get affine coordinates\n");
474     }
475   _gcry_mpi_ec_free (ctx);
476
477   point_free (&Q);
478   mpi_free (d);
479   curve_free (&E);
480
481   /* Now we can test our keys (this should never fail!). */
482   test_keys (sk, nbits - 64);
483
484   return 0;
485 }
486
487
488 /****************
489  * To verify correct skey it use a random information.
490  * First, encrypt and decrypt this dummy value,
491  * test if the information is recuperated.
492  * Second, test with the sign and verify functions.
493  */
494 static void
495 test_keys (ECC_secret_key *sk, unsigned int nbits)
496 {
497   ECC_public_key pk;
498   gcry_mpi_t test = mpi_new (nbits);
499   mpi_point_t R_;
500   gcry_mpi_t c = mpi_new (nbits);
501   gcry_mpi_t out = mpi_new (nbits);
502   gcry_mpi_t r = mpi_new (nbits);
503   gcry_mpi_t s = mpi_new (nbits);
504
505   if (DBG_CIPHER)
506     log_debug ("Testing key.\n");
507
508   point_init (&R_);
509
510   pk.E = curve_copy (sk->E);
511   point_init (&pk.Q);
512   point_set (&pk.Q, &sk->Q);
513
514   gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM);
515
516   if (sign (test, sk, r, s) )
517     log_fatal ("ECDSA operation: sign failed\n");
518
519   if (verify (test, &pk, r, s))
520     {
521       log_fatal ("ECDSA operation: sign, verify failed\n");
522     }
523
524   if (DBG_CIPHER)
525     log_debug ("ECDSA operation: sign, verify ok.\n");
526
527   point_free (&pk.Q);
528   curve_free (&pk.E);
529
530   point_free (&R_);
531   mpi_free (s);
532   mpi_free (r);
533   mpi_free (out);
534   mpi_free (c);
535   mpi_free (test);
536 }
537
538 /****************
539  * To check the validity of the value, recalculate the correspondence
540  * between the public value and the secret one.
541  */
542 static int
543 check_secret_key (ECC_secret_key * sk)
544 {
545   mpi_point_t Q;
546   gcry_mpi_t y_2, y2 = mpi_alloc (0);
547   mpi_ec_t ctx;
548
549   /* ?primarity test of 'p' */
550   /*  (...) //!! */
551   /* G in E(F_p) */
552   y_2 = gen_y_2 (sk->E.G.x, &sk->E);   /*  y^2=x^3+a*x+b */
553   mpi_mulm (y2, sk->E.G.y, sk->E.G.y, sk->E.p);      /*  y^2=y*y */
554   if (mpi_cmp (y_2, y2))
555     {
556       if (DBG_CIPHER)
557         log_debug ("Bad check: Point 'G' does not belong to curve 'E'!\n");
558       return (1);
559     }
560   /* G != PaI */
561   if (!mpi_cmp_ui (sk->E.G.z, 0))
562     {
563       if (DBG_CIPHER)
564         log_debug ("Bad check: 'G' cannot be Point at Infinity!\n");
565       return (1);
566     }
567
568   point_init (&Q);
569   ctx = _gcry_mpi_ec_init (sk->E.p, sk->E.a);
570   _gcry_mpi_ec_mul_point (&Q, sk->E.n, &sk->E.G, ctx);
571   if (mpi_cmp_ui (Q.z, 0))
572     {
573       if (DBG_CIPHER)
574         log_debug ("check_secret_key: E is not a curve of order n\n");
575       point_free (&Q);
576       _gcry_mpi_ec_free (ctx);
577       return 1;
578     }
579   /* pubkey cannot be PaI */
580   if (!mpi_cmp_ui (sk->Q.z, 0))
581     {
582       if (DBG_CIPHER)
583         log_debug ("Bad check: Q can not be a Point at Infinity!\n");
584       _gcry_mpi_ec_free (ctx);
585       return (1);
586     }
587   /* pubkey = [d]G over E */
588   _gcry_mpi_ec_mul_point (&Q, sk->d, &sk->E.G, ctx);
589   if ((Q.x == sk->Q.x) && (Q.y == sk->Q.y) && (Q.z == sk->Q.z))
590     {
591       if (DBG_CIPHER)
592         log_debug
593           ("Bad check: There is NO correspondence between 'd' and 'Q'!\n");
594       _gcry_mpi_ec_free (ctx);
595       return (1);
596     }
597   _gcry_mpi_ec_free (ctx);
598   point_free (&Q);
599   return 0;
600 }
601
602
603 /*
604  * Return the signature struct (r,s) from the message hash.  The caller
605  * must have allocated R and S.
606  */
607 static gpg_err_code_t
608 sign (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s)
609 {
610   gpg_err_code_t err = 0;
611   gcry_mpi_t k, dr, sum, k_1, x;
612   mpi_point_t I;
613   mpi_ec_t ctx;
614
615   k = NULL;
616   dr = mpi_alloc (0);
617   sum = mpi_alloc (0);
618   k_1 = mpi_alloc (0);
619   x = mpi_alloc (0);
620   point_init (&I);
621
622   mpi_set_ui (s, 0);
623   mpi_set_ui (r, 0);
624
625   ctx = _gcry_mpi_ec_init (skey->E.p, skey->E.a);
626
627   while (!mpi_cmp_ui (s, 0)) /* s == 0 */
628     {
629       while (!mpi_cmp_ui (r, 0)) /* r == 0 */
630         {
631           /* Note, that we are guaranteed to enter this loop at least
632              once because r has been intialized to 0.  We can't use a
633              do_while because we want to keep the value of R even if S
634              has to be recomputed.  */
635           mpi_free (k);
636           k = gen_k (skey->E.n, GCRY_STRONG_RANDOM);
637           _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx); 
638           if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx))
639             {
640               if (DBG_CIPHER)
641                 log_debug ("ecc sign: Failed to get affine coordinates\n");
642               err = GPG_ERR_BAD_SIGNATURE;
643               goto leave;
644             }
645           mpi_mod (r, x, skey->E.n);  /* r = x mod n */
646         }
647       mpi_mulm (dr, skey->d, r, skey->E.n); /* dr = d*r mod n  */
648       mpi_addm (sum, input, dr, skey->E.n); /* sum = hash + (d*r) mod n  */
649       mpi_invm (k_1, k, skey->E.n);         /* k_1 = k^(-1) mod n  */
650       mpi_mulm (s, k_1, sum, skey->E.n);    /* s = k^(-1)*(hash+(d*r)) mod n */
651     }
652
653  leave:
654   _gcry_mpi_ec_free (ctx);
655   point_free (&I);
656   mpi_free (x);
657   mpi_free (k_1);
658   mpi_free (sum);
659   mpi_free (dr);
660   mpi_free (k);
661
662   return err;
663 }
664
665 /*
666  * Check if R and S verifies INPUT.
667  */
668 static gpg_err_code_t
669 verify (gcry_mpi_t input, ECC_public_key *pkey, gcry_mpi_t r, gcry_mpi_t s)
670 {
671   gpg_err_code_t err = 0;
672   gcry_mpi_t h, h1, h2, x, y;
673   mpi_point_t Q, Q1, Q2;
674   mpi_ec_t ctx;
675
676   if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) )
677     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < r < n  failed.  */
678   if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) )
679     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < s < n  failed.  */
680
681   h  = mpi_alloc (0);
682   h1 = mpi_alloc (0);
683   h2 = mpi_alloc (0);
684   x = mpi_alloc (0);
685   y = mpi_alloc (0);
686   point_init (&Q);
687   point_init (&Q1);
688   point_init (&Q2);
689
690   ctx = _gcry_mpi_ec_init (pkey->E.p, pkey->E.a);
691
692   /* h  = s^(-1) (mod n) */
693   mpi_invm (h, s, pkey->E.n);
694 /*   log_mpidump ("   h", h); */
695   /* h1 = hash * s^(-1) (mod n) */
696   mpi_mulm (h1, input, h, pkey->E.n);
697 /*   log_mpidump ("  h1", h1); */
698   /* Q1 = [ hash * s^(-1) ]G  */
699   _gcry_mpi_ec_mul_point (&Q1, h1, &pkey->E.G, ctx);
700 /*   log_mpidump ("Q1.x", Q1.x); */
701 /*   log_mpidump ("Q1.y", Q1.y); */
702 /*   log_mpidump ("Q1.z", Q1.z); */
703   /* h2 = r * s^(-1) (mod n) */
704   mpi_mulm (h2, r, h, pkey->E.n);
705 /*   log_mpidump ("  h2", h2); */
706   /* Q2 = [ r * s^(-1) ]Q */
707   _gcry_mpi_ec_mul_point (&Q2, h2, &pkey->Q, ctx);
708 /*   log_mpidump ("Q2.x", Q2.x); */
709 /*   log_mpidump ("Q2.y", Q2.y); */
710 /*   log_mpidump ("Q2.z", Q2.z); */
711   /* Q  = ([hash * s^(-1)]G) + ([r * s^(-1)]Q) */
712   _gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ctx);
713 /*   log_mpidump (" Q.x", Q.x); */
714 /*   log_mpidump (" Q.y", Q.y); */
715 /*   log_mpidump (" Q.z", Q.z); */
716
717   if (!mpi_cmp_ui (Q.z, 0))
718     {
719       if (DBG_CIPHER)
720           log_debug ("ecc verify: Rejected\n");
721       err = GPG_ERR_BAD_SIGNATURE;
722       goto leave;
723     }
724   if (_gcry_mpi_ec_get_affine (x, y, &Q, ctx))
725     {
726       if (DBG_CIPHER)
727         log_debug ("ecc verify: Failed to get affine coordinates\n");
728       err = GPG_ERR_BAD_SIGNATURE;
729       goto leave;
730     }
731   mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */
732   if (mpi_cmp (x, r))   /* x != r */
733     {
734       if (DBG_CIPHER)
735         {
736           log_mpidump ("   x", x);
737           log_mpidump ("   y", y);
738           log_mpidump ("   r", r);
739           log_mpidump ("   s", s);
740           log_debug ("ecc verify: Not verified\n");
741         }
742       err = GPG_ERR_BAD_SIGNATURE;
743       goto leave;
744     }
745   if (DBG_CIPHER)
746     log_debug ("ecc verify: Accepted\n");
747
748  leave:
749   _gcry_mpi_ec_free (ctx);
750   point_free (&Q2);
751   point_free (&Q1);
752   point_free (&Q);
753   mpi_free (y);
754   mpi_free (x);
755   mpi_free (h2);
756   mpi_free (h1);
757   mpi_free (h);
758   return err;
759 }
760
761
762
763 /*********************************************
764  **************  interface  ******************
765  *********************************************/
766 static gcry_mpi_t
767 ec2os (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t p)
768 {
769   gpg_error_t err;
770   int pbytes = (mpi_get_nbits (p)+7)/8;
771   size_t n;
772   unsigned char *buf, *ptr;
773   gcry_mpi_t result;
774
775   buf = gcry_xmalloc ( 1 + 2*pbytes );
776   *buf = 04; /* Uncompressed point.  */
777   ptr = buf+1;
778   err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, x);
779   if (err)
780     log_fatal ("mpi_print failed: %s\n", gpg_strerror (err));
781   if (n < pbytes)
782     {
783       memmove (ptr+(pbytes-n), buf+1, n);
784       memset (ptr, 0, (pbytes-n));
785     }
786   ptr += pbytes;
787   err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, y);
788   if (err)
789     log_fatal ("mpi_print failed: %s\n", gpg_strerror (err));
790   if (n < pbytes)
791     {
792       memmove (ptr+(pbytes-n), buf+1, n);
793       memset (ptr, 0, (pbytes-n));
794     }
795   
796   err = gcry_mpi_scan (&result, GCRYMPI_FMT_USG, buf, 1+2*pbytes, NULL);
797   if (err)
798     log_fatal ("mpi_scan failed: %s\n", gpg_strerror (err));
799   gcry_free (buf);
800
801   mpi_free (x);
802   mpi_free (y);
803
804   return result;
805 }
806
807 /* RESULT must have been initialized and is set on success to the
808    point given by VALUE.  */
809 static gcry_error_t
810 os2ec (mpi_point_t *result, gcry_mpi_t value)
811 {
812   gcry_error_t err;
813   size_t n;
814   unsigned char *buf;
815   gcry_mpi_t x, y;
816
817   n = (mpi_get_nbits (value)+7)/8;
818   buf = gcry_xmalloc (n);
819   err = gcry_mpi_print (GCRYMPI_FMT_USG, buf, n, &n, value);
820   if (err)
821     {
822       gcry_free (buf);
823       return err;
824     }
825   if (n < 1) 
826     {
827       gcry_free (buf);
828       return GPG_ERR_INV_OBJ;
829     }
830   if (*buf != 4)
831     {
832       gcry_free (buf);
833       return GPG_ERR_NOT_IMPLEMENTED; /* No support for point compression.  */
834     }
835   if ( ((n-1)%2) ) 
836     {
837       gcry_free (buf);
838       return GPG_ERR_INV_OBJ;
839     }
840   n = (n-1)/2;
841   err = gcry_mpi_scan (&x, GCRYMPI_FMT_USG, buf+1, n, NULL);
842   if (err)
843     {
844       gcry_free (buf);
845       return err;
846     }
847   err = gcry_mpi_scan (&y, GCRYMPI_FMT_USG, buf+1+n, n, NULL);
848   gcry_free (buf);
849   if (err)
850     {
851       mpi_free (x);
852       return err;
853     }
854
855   mpi_set (result->x, x);
856   mpi_set (result->y, y);
857   mpi_set_ui (result->z, 1);
858
859   mpi_free (x);
860   mpi_free (y);
861   
862   return 0;
863 }
864
865 /* Extended version of ecc_generate which is called directly by
866    pubkey.c.  If CURVE is not NULL, that name will be used to select
867    the domain parameters.  NBITS is not used in this case.  */
868 gcry_err_code_t
869 _gcry_ecc_generate (int algo, unsigned int nbits, const char *curve,
870                     gcry_mpi_t *skey, gcry_mpi_t **retfactors)
871 {
872   gpg_err_code_t err;
873   ECC_secret_key sk;
874   gcry_mpi_t g_x, g_y, q_x, q_y;
875
876   (void)algo;
877
878   /* Make an empty list of factors.  */
879   *retfactors = gcry_calloc ( 1, sizeof **retfactors );
880   if (!*retfactors)
881     return gpg_err_code_from_syserror ();
882
883   g_x = mpi_new (0);
884   g_y = mpi_new (0);
885   q_x = mpi_new (0);
886   q_y = mpi_new (0);
887   err = generate_key (&sk, nbits, curve, g_x, g_y, q_x, q_y);
888   if (err)
889     {
890       gcry_free (*retfactors);
891       *retfactors = NULL;
892       return err;
893     }
894
895   skey[0] = sk.E.p;
896   skey[1] = sk.E.a;
897   skey[2] = sk.E.b;
898   skey[3] = ec2os (g_x, g_y, sk.E.p);
899   skey[4] = sk.E.n;
900   skey[5] = ec2os (q_x, q_y, sk.E.p);
901   skey[6] = sk.d;
902
903   return 0;
904 }
905
906 /* Return the parameters of the curve NAME.  */
907 gcry_err_code_t
908 _gcry_ecc_get_param (const char *name, gcry_mpi_t *pkey)
909 {
910   gpg_err_code_t err;
911   unsigned int nbits;
912   elliptic_curve_t E;
913   mpi_ec_t ctx;
914   gcry_mpi_t g_x, g_y;
915   
916   err = generate_curve (0, name, &E, &nbits);
917   if (err)
918     return err;
919
920   g_x = mpi_new (0);
921   g_y = mpi_new (0);
922   ctx = _gcry_mpi_ec_init (E.p, E.a);
923   if (_gcry_mpi_ec_get_affine (g_x, g_y, &E.G, ctx))
924     log_fatal ("ecc get param: Failed to get affine coordinates\n");
925   _gcry_mpi_ec_free (ctx);
926   point_free (&E.G);
927
928   pkey[0] = E.p;
929   pkey[1] = E.a;
930   pkey[2] = E.b;
931   pkey[3] = ec2os (g_x, g_y, E.p);
932   pkey[4] = E.n;
933   pkey[5] = NULL;
934
935   return 0;
936 }
937
938 static gcry_err_code_t
939 ecc_generate (int algo, unsigned int nbits, unsigned long dummy,
940               gcry_mpi_t *skey, gcry_mpi_t **retfactors)
941 {
942   (void)dummy;
943   return _gcry_ecc_generate (algo, nbits, NULL, skey, retfactors);
944 }
945
946
947 static gcry_err_code_t
948 ecc_check_secret_key (int algo, gcry_mpi_t *skey)
949 {
950   gpg_err_code_t err;
951   ECC_secret_key sk;
952
953   (void)algo;
954
955   if (!skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] || !skey[5]
956       || !skey[6] || !skey[7] || !skey[8] || !skey[9] || !skey[10])
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
979   sk.d = skey[6];
980
981   if (check_secret_key (&sk))
982     {
983       point_free (&sk.E.G);
984       point_free (&sk.Q);
985       return GPG_ERR_BAD_SECKEY;
986     }
987   point_free (&sk.E.G);
988   point_free (&sk.Q);
989   return 0;
990 }
991
992
993 static gcry_err_code_t
994 ecc_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
995 {
996   gpg_err_code_t err;
997   ECC_secret_key sk;
998
999   (void)algo;
1000
1001   if (!data || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4]
1002       || !skey[5] || !skey[6] )
1003     return GPG_ERR_BAD_MPI;
1004
1005   sk.E.p = skey[0];
1006   sk.E.a = skey[1];
1007   sk.E.b = skey[2];
1008   point_init (&sk.E.G);
1009   err = os2ec (&sk.E.G, skey[3]);
1010   if (err)
1011     {
1012       point_free (&sk.E.G);
1013       return err;
1014     }
1015   sk.E.n = skey[4];
1016   point_init (&sk.Q);
1017   err = os2ec (&sk.Q, skey[5]);
1018   if (err)
1019     {
1020       point_free (&sk.E.G);
1021       point_free (&sk.Q);
1022       return err;
1023     }
1024   sk.d = skey[6];
1025
1026   resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.E.p));
1027   resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.E.p));
1028   err = sign (data, &sk, resarr[0], resarr[1]);
1029   if (err)
1030     {
1031       mpi_free (resarr[0]);
1032       mpi_free (resarr[1]);
1033       resarr[0] = NULL; /* Mark array as released.  */
1034     }
1035   point_free (&sk.E.G);
1036   point_free (&sk.Q);
1037   return err;
1038 }
1039
1040 static gcry_err_code_t
1041 ecc_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
1042             int (*cmp)(void *, gcry_mpi_t), void *opaquev)
1043 {
1044   gpg_err_code_t err;
1045   ECC_public_key pk;
1046
1047   (void)algo;
1048   (void)cmp;
1049   (void)opaquev;
1050
1051   if (!data[0] || !data[1] || !hash || !pkey[0] || !pkey[1] || !pkey[2]
1052       || !pkey[3] || !pkey[4] || !pkey[5] )
1053     return GPG_ERR_BAD_MPI;
1054
1055   pk.E.p = pkey[0];
1056   pk.E.a = pkey[1];
1057   pk.E.b = pkey[2];
1058   point_init (&pk.E.G);
1059   err = os2ec (&pk.E.G, pkey[3]);
1060   if (err)
1061     {
1062       point_free (&pk.E.G);
1063       return err;
1064     }
1065   pk.E.n = pkey[4];
1066   point_init (&pk.Q);
1067   err = os2ec (&pk.Q, pkey[5]);
1068   if (err)
1069     {
1070       point_free (&pk.E.G);
1071       point_free (&pk.Q);
1072       return err;
1073     }
1074
1075   err = verify (hash, &pk, data[0], data[1]);
1076
1077   point_free (&pk.E.G);
1078   point_free (&pk.Q);
1079   return err;
1080 }
1081
1082
1083
1084 static unsigned int
1085 ecc_get_nbits (int algo, gcry_mpi_t *pkey)
1086 {
1087   (void)algo;
1088
1089   return mpi_get_nbits (pkey[0]);
1090 }
1091
1092
1093 static const char *ecdsa_names[] =
1094   {
1095     "ecdsa",
1096     "ecc",
1097     NULL,
1098   };
1099
1100 gcry_pk_spec_t _gcry_pubkey_spec_ecdsa =
1101   {
1102     "ECDSA", ecdsa_names,
1103     "pabgnq", "pabgnqd", "", "rs", "pabgnq",
1104     GCRY_PK_USAGE_SIGN,
1105     ecc_generate,
1106     ecc_check_secret_key,
1107     NULL,
1108     NULL,
1109     ecc_sign,
1110     ecc_verify,
1111     ecc_get_nbits
1112   };
1113