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