Did some performance experiments and added code for Barrett reduction.
[libgcrypt.git] / cipher / ecc.c
1 /* ecc.c  -  ECElGamal Public Key encryption & ECDSA signature algorithm
2  * Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3  *
4  * This file is part of GnuPG.
5  *
6  * GnuPG is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * GnuPG 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 General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * 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
22 /* TODO wk
23
24   - Check whether we can LGPL the code.
25
26   - Use affine coordinates for points with the public API and format
27     them in the way described by BSI's TR-03111, 5.1.3.
28
29   - If we support point compression we need to decide how to compute
30     the keygrip it should not change due to compression.
31
32   - mpi_mulm is quite slow which has never been a problem for the
33     other algorithms.  However here we are using it several times in a
34     row and thus it is an important performance factor.
35
36   - We use mpi_powm for x^2 mod p: Either implement a special case in
37     mpi_powm or check whether mpi_mulm is faster.
38
39
40
41 Algorithm       generate  100*sign  100*verify
42 ----------------------------------------------
43 Orginal version:
44 ECDSA 192 bit      100ms    2630ms      5040ms
45 ECDSA 256 bit      120ms    2960ms      6070ms
46 ECDSA 384 bit      370ms    9570ms     18900ms
47
48 Using Barrett:
49 ECDSA 192 bit      130ms    3050ms      5620ms
50 ECDSA 256 bit      140ms    3410ms      6950ms
51 ECDSA 384 bit      400ms   10500ms     21670ms
52
53
54 */
55
56 /* This code is a based on the 
57  * Patch 0.1.6 for the gnupg 1.4.x branch
58  * as retrieved on 2007-03-21 from
59  * http://www.calcurco.cat/eccGnuPG/src/gnupg-1.4.6-ecc0.2.0beta1.diff.bz2
60  *
61  * Written by 
62  *  Sergi Blanch i Torne <d4372211 at alumnes.eup.udl.es>, 
63  *  Ramiro Moreno Chiral <ramiro at eup.udl.es>
64  * Maintainers
65  *  Sergi Blanch i Torne
66  *  Ramiro Moreno Chiral
67  *  Mikael Mylnikov (mmr)
68  */
69
70 /*
71  * This module are under development, it would not have to be used 
72  * in a production environments. It can have bugs!
73  * 
74  * Made work:
75  *  alex: found a bug over the passphrase.
76  *  mmr: signature bug found and solved (afine conversion).
77  *  mmr: found too many mistakes in the mathematical background transcription.
78  *  mmr: improve the mathematical performance.
79  *  mmr: solve ECElGamal IFP weakness.
80  *       more polite gen_k() and its calls.
81  *  mmr: extend the check_secret_key()
82  * In progress:
83  *  gen_big_point(): Randomize the point generation.
84  *  improve te memory uses.
85  *  Separation between sign & encrypt keys to facility the subkeys creation.
86  *  read & reread the code in a bug search!
87  * To do:
88  *  2-isogeny: randomize the elliptic curves.
89  *  E(F_{2^m})
90  */
91
92 #include <config.h>
93 #include <stdio.h>
94 #include <stdlib.h>
95 #include <string.h>
96
97 #include "g10lib.h"
98 #include "mpi.h"
99 #include "cipher.h"
100
101
102 /* 
103     ECC over F_p; E(F_p)
104     T=(p,a,b,G,n,h)
105              p:    big odd number
106              a,b:  curve generators
107              G:    Subgroup generator point
108              n:    big int, in G order
109              h:    cofactor
110      y^2=x^3+ax+b --> (Y^2)Z=X^3+aX(Z^2)+b(Z^3)
111     
112     
113              Q=[d]G, 1<=d<=n-1
114 */
115
116
117 /* An object to hold a computation context.  */
118 struct ecc_ctx_s
119 {
120   gcry_mpi_t m;   /* The modulus - may not be modified. */
121   int m_copied;   /* If true, M needs to be released.  */
122 };
123 typedef struct ecc_ctx_s *ecc_ctx_t;
124
125
126 /* Point representation in projective coordinates. */
127 typedef struct
128 {
129   gcry_mpi_t x_;
130   gcry_mpi_t y_;
131   gcry_mpi_t z_;
132 } point_t;
133
134
135 /* Definition of a curve.  */
136 typedef struct
137 {
138   gcry_mpi_t p_;  /* Prime specifying the field GF(p).  */
139   gcry_mpi_t a_;  /* First coefficient of the Weierstrass equation.  */
140   gcry_mpi_t b_;  /* Second coefficient of teh Weierstrass equation.  */
141   point_t G;      /* Base point (generator).  */
142   gcry_mpi_t n_;  /* Order of G.  */
143   /*gcry_mpi_t h_; =1  fixme: We will need to change this value in 2-isogeny */
144 } elliptic_curve_t;             /* Fixme: doubtful name */
145
146
147 typedef struct
148 {
149   elliptic_curve_t E;
150   point_t Q;                    /* Q=[d]G */
151 } ECC_public_key;               /* Q */
152
153 typedef struct
154 {
155   elliptic_curve_t E;
156   point_t Q;                    /* Q=[d]G */
157   gcry_mpi_t d;
158 } ECC_secret_key;               /* d */
159
160
161 /* This static table defines all available curves.  */
162 static const struct
163 {
164   const char *desc;           /* Description of the curve.  */
165   unsigned int nbits;         /* Number of bits.  */
166   const char  *p, *a, *b, *n; /* Parameters.  */
167   const char *g_x, *g_y;      /* G_z is always 1.  */
168 } domain_parms[] = 
169   {
170     { 
171       "NIST P-192", 192,
172       "0xfffffffffffffffffffffffffffffffeffffffffffffffff",
173       "0xfffffffffffffffffffffffffffffffefffffffffffffffc",
174       "0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1",
175       "0xffffffffffffffffffffffff99def836146bc9b1b4d22831",
176       
177       "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012",
178       "0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811"
179     },
180     { 
181       "NIST P-224", 224,
182       "0xffffffffffffffffffffffffffffffff000000000000000000000001",
183       "0xfffffffffffffffffffffffffffffffefffffffffffffffffffffffe",
184       "0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4",
185       "0xffffffffffffffffffffffffffff16a2e0b8f03e13dd29455c5c2a3d" ,
186
187       "0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21",
188       "0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34"
189     },
190     { 
191       "NIST P-256", 256,
192       "0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff",
193       "0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc",
194       "0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b",
195       "0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551",
196       
197       "0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296",
198       "0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5"
199     },
200     {
201       "NIST P-384", 384,
202       "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
203       "ffffffff0000000000000000ffffffff",
204       "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
205       "ffffffff0000000000000000fffffffc",  
206       "0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875a"
207       "c656398d8a2ed19d2a85c8edd3ec2aef",
208       "0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf"
209       "581a0db248b0a77aecec196accc52973",
210
211       "0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a38"
212       "5502f25dbf55296c3a545e3872760ab7",
213       "0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c0"
214       "0a60b1ce1d7e819d7a431d7c90ea0e5f"
215     },
216     {
217       "NIST P-521", 521,
218       "0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
219       "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
220       "0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
221       "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc",
222       "0x051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef10"
223       "9e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00",
224       "0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
225       "ffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409",
226
227       "0xc6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3d"
228       "baa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66",
229       "0x11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e6"
230       "62c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650"
231     },
232     { NULL, 0, NULL, NULL, NULL, NULL }
233   };
234
235
236 /* Registered progress function and its callback value. */
237 static void (*progress_cb) (void *, const char*, int, int, int);
238 static void *progress_cb_data;
239
240
241
242 \f
243 /* Local prototypes. */
244 static gcry_mpi_t gen_k (gcry_mpi_t p, int secure);
245 static void test_keys (ECC_secret_key * sk, unsigned int nbits);
246 static int check_secret_key (ECC_secret_key * sk);
247 static gpg_err_code_t sign (gcry_mpi_t input, ECC_secret_key *skey, 
248                             gcry_mpi_t r, gcry_mpi_t s);
249 static gpg_err_code_t verify (gcry_mpi_t input, ECC_public_key *pkey,
250                               gcry_mpi_t r, gcry_mpi_t s);
251
252
253 static int point_at_infinity (point_t query);
254
255 static gcry_mpi_t gen_y_2 (gcry_mpi_t x, elliptic_curve_t * base);
256
257
258
259 \f
260 void
261 _gcry_register_pk_ecc_progress (void (*cb) (void *, const char *,
262                                             int, int, int),
263                                 void *cb_data)
264 {
265   progress_cb = cb;
266   progress_cb_data = cb_data;
267 }
268
269 static void
270 progress (int c)
271 {
272   if (progress_cb)
273     progress_cb (progress_cb_data, "pk_dsa", c, 0, 0);
274   else
275     fputc (c, stderr);
276 }
277
278 \f
279 /*
280
281     M P I  W R A P P E R
282
283  */
284
285 static ecc_ctx_t 
286 ecc_ctx_init (gcry_mpi_t m, int copy)
287 {
288   ecc_ctx_t ctx;
289
290   ctx = gcry_xcalloc (1, sizeof *ctx);
291
292   if (copy)
293     {
294       ctx->m = mpi_copy (m);
295       ctx->m_copied = 1;
296     }
297   else
298     ctx->m = m;
299
300   return ctx;
301 }
302
303 static void
304 ecc_ctx_free (ecc_ctx_t ctx)
305 {
306   if (!ctx)
307     return;
308   if (ctx->m_copied)
309     mpi_free (ctx->m);
310   gcry_free (ctx);
311 }
312
313 /* Our version of mpi_mod which uses a reduction algorithm depending
314    on the the context.  The modulus is part of the context. */
315 static void
316 ecc_mod (gcry_mpi_t r, gcry_mpi_t x, ecc_ctx_t ctx)
317 {
318   mpi_mod (r, x, ctx->m);
319 }
320
321 /* Our version of mpi_mulm which uses a reduction algorithm depending
322    on the the context.  The modulus is part of the context. */
323 static void
324 ecc_mulm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, ecc_ctx_t ctx)
325 {
326   /* Barrett is actually slower, so we don't do any switching here.
327      Howerver, we should take advantage of fast reduction for the NIST
328      curves.  */
329   mpi_mulm (w, u, v, ctx->m);
330 }
331
332
333
334 \f
335 /*
336
337     O B J E C T   M A I N T E N A N C E
338
339  */
340
341 /* Intialize a point object, so that its elements may be sued directly
342    as MPI functions.  point_free is required for each initialzied
343    point. */
344 static void
345 point_init (point_t *P)
346 {
347   P->x_ = mpi_new (0);
348   P->y_ = mpi_new (0);
349   P->z_ = mpi_new (0);
350 }
351
352
353 /*
354  * Release a point object.
355  */
356 static void
357 point_free (point_t *P)
358 {
359   mpi_free (P->x_); P->x_ = NULL;
360   mpi_free (P->y_); P->y_ = NULL;
361   mpi_free (P->z_); P->z_ = NULL;
362 }
363
364
365 /*
366  * Return a copy of a point object.
367  */
368 static point_t
369 point_copy (point_t P)
370 {
371   point_t R;
372
373   R.x_ = mpi_copy (P.x_);
374   R.y_ = mpi_copy (P.y_);
375   R.z_ = mpi_copy (P.z_);
376
377   return R;
378 }
379
380
381 /*
382  * Release a curve object.
383  */
384 static void
385 curve_free (elliptic_curve_t *E)
386 {
387   mpi_free (E->p_); E->p_ = NULL;
388   mpi_free (E->a_); E->a_ = NULL;
389   mpi_free (E->b_);  E->b_ = NULL;
390   point_free (&E->G);
391   mpi_free (E->n_);  E->n_ = NULL;
392 }
393
394
395 /*
396  * Return a copy of a curve object.
397  */
398 static elliptic_curve_t
399 curve_copy (elliptic_curve_t E)
400 {
401   elliptic_curve_t R;
402
403   R.p_ = mpi_copy (E.p_);
404   R.a_ = mpi_copy (E.a_);
405   R.b_ = mpi_copy (E.b_);
406   R.G  = point_copy (E.G);
407   R.n_ = mpi_copy (E.n_);
408
409   return R;
410 }
411
412
413 \f
414 /*
415
416     A D D I T I O N A L   M P I   F U N C T I O N S
417
418  */
419
420
421 /****************
422  * Find, if it exist, the square root of one integer modulo a big prime.
423  * Return the square root or NULL if it is not found.
424  */
425 #if 0
426 static gcry_mpi_t
427 exist_square_root (gcry_mpi_t integer, gcry_mpi_t modulus)
428 {
429   unsigned long int i = 0;
430   gcry_mpi_t one, two, three, four, five, eight;
431   gcry_mpi_t k, r, z, k1;
432   gcry_mpi_t t1, t2, t3, t4;
433
434   one = mpi_alloc_set_ui (1);
435   two = mpi_alloc_set_ui (2);
436   three = mpi_alloc_set_ui (3);
437   four = mpi_alloc_set_ui (4);
438   five = mpi_alloc_set_ui (5);
439   eight = mpi_alloc_set_ui (8);
440   k = mpi_alloc (mpi_get_nlimbs (modulus));
441   r = mpi_alloc (mpi_get_nlimbs (modulus));
442   z = mpi_alloc (mpi_get_nlimbs (modulus));
443   k1 = mpi_alloc (mpi_get_nlimbs (modulus));
444   t1 = mpi_alloc (mpi_get_nlimbs (modulus));
445   t2 = mpi_alloc (mpi_get_nlimbs (modulus));
446   t3 = mpi_alloc (mpi_get_nlimbs (modulus));
447   t4 = mpi_alloc (mpi_get_nlimbs (modulus));
448
449   if (DBG_CIPHER)
450     log_mpidump ("?exist Square Root of ", integer);
451
452   mpi_fdiv_qr (k, r, modulus, four);
453   if (mpi_cmp (r, three))
454     {                           /* p=3 (mod 4) */
455       mpi_addm (k1, k, one, modulus);
456       mpi_powm (z, integer, k1, modulus);
457       if (DBG_CIPHER)
458         {
459           log_mpidump ("z=", z);
460         }
461       return z;                 /* value found */
462     }
463   mpi_fdiv_qr (k, r, modulus, eight);
464   if (mpi_cmp (r, five))
465     {                           /* p=5 (mod 8) */
466       mpi_mulm (t1, two, integer, modulus);
467       mpi_powm (t2, t1, k, modulus);
468       mpi_powm (t2, t2, two, modulus);
469       mpi_mulm (t2, t1, t2, modulus);
470       mpi_mulm (t3, integer, t1, modulus);
471       mpi_subm (t4, t2, one, modulus);
472       mpi_mulm (z, t3, t4, modulus);
473       if (DBG_CIPHER)
474         {
475           log_mpidump ("z=", z);
476         }
477       return z;                 /* value found */
478     }
479   if (mpi_cmp (r, one))
480     {                           /* p=1 (mod 8) */
481       while (i < 0xFF)
482         {                       /* while not find z after 256 iterations */
483           if (DBG_CIPHER)
484             log_debug ("Square root bucle.\n");
485           t1 = mpi_copy (integer);
486           t2 = gen_k (modulus, 0);
487           mpi_add_ui (t3, modulus, 1);  /* t3=p+1 */
488           mpi_rshift (t3, t3, 1);       /* t3=t3/2 */
489           lucas (t1, t2, t3, modulus, t4, t3);  /* t4=V_k */
490           mpi_rshift (z, t4, 1);        /* z=V/2 */
491           mpi_sub_ui (t3, modulus, 1);  /* t3=p-1 */
492           mpi_rshift (t4, t3, 2);       /* t4=t3/2 */
493           lucas (t1, t2, t4, modulus, t4, t1);  /* t1=Q_0 */
494           mpi_powm (t2, z, two, modulus);       /* t2=z^2 */
495           if (mpi_cmp (t1, integer))
496             {
497               if (DBG_CIPHER)
498                 {
499                   log_mpidump ("z=", z);
500                 }
501               return z;         /* value found */
502             }
503           if (t4 > mpi_alloc_set_ui (1) && t4 < t3)
504             {
505               if (DBG_CIPHER)
506                 log_debug ("Rejected.\n");
507               return (0);       /* NULL */
508             }
509           if (DBG_CIPHER)
510             log_debug ("Another loop.\n");
511         }
512     }
513   if (DBG_CIPHER)
514     log_debug ("iterations limit.\n");
515   return (0);                   /* because this algorithm not always finish. */
516 }
517 #endif /*0*/
518
519 /****************
520  * Formal definition:
521  * V_0 = 2; V_1 = p
522  * V_k = (p*V_(k-1)) - (q*V_(k-2))   for k >= 2
523  */
524 #if 0
525 static void
526 lucas (gcry_mpi_t n, gcry_mpi_t p_, gcry_mpi_t q_,
527        gcry_mpi_t k, gcry_mpi_t V_n, gcry_mpi_t Q_0)
528 {
529
530   gcry_mpi_t v0, v1, q0, q1;
531   gcry_mpi_t t1, t2;
532   unsigned int r, i;
533
534   v0 = mpi_alloc_set_ui (2);
535   v1 = mpi_copy (p_);
536   q0 = mpi_alloc_set_ui (1);
537   q1 = mpi_alloc_set_ui (1);
538   t1 = mpi_alloc_set_ui (0);
539   t2 = mpi_alloc_set_ui (0);
540
541   if (DBG_CIPHER)
542     {
543       log_debug ("Generating lucas sequence.\n");
544       log_mpidump ("k=", k);
545     }
546
547   r = mpi_get_nbits (k) - 1;
548   i = 0;
549   while (mpi_test_bit (k, i) != 1)
550     {                           /* search the first bit with value '1' */
551       i++;
552     }
553   while (i < r)
554     {
555       if (DBG_CIPHER)
556         {
557           log_debug ("Lucas sequence bucle.\n");
558           log_mpidump ("i=", mpi_alloc_set_ui (i));
559           log_mpidump ("r=", mpi_alloc_set_ui (r));
560         }
561       mpi_mulm (q0, q0, q1, n);
562       if (mpi_test_bit (k, i) == 1)
563         {
564           mpi_mulm (q1, q0, q_, n);
565           mpi_mul (t1, v0, v1);
566           mpi_mul (t2, p_, q0);
567           mpi_subm (v0, t1, t2, n);
568           mpi_powm (t1, v1, mpi_alloc_set_ui (2), n);
569           mpi_mul (t2, mpi_alloc_set_ui (2), q1);
570           mpi_subm (v1, t1, t2, n);
571         }
572       else
573         {
574           q1 = mpi_copy (q0);
575           mpi_mul (t1, v0, v1);
576           mpi_mul (t2, p_, q0);
577           mpi_subm (v1, t1, t2, n);
578           mpi_powm (t1, v0, mpi_alloc_set_ui (2), n);
579           mpi_mul (t2, mpi_alloc_set_ui (2), q0);
580           mpi_subm (v0, t1, t2, n);
581         }
582       i++;
583     }
584   V_n = mpi_copy (v0);
585   Q_0 = mpi_copy (q0);
586   if (DBG_CIPHER)
587     {
588       log_debug ("Lucas sequence generated.\n");
589       log_mpidump ("V_n=", V_n);
590       log_mpidump ("Q_0=", Q_0);
591     }
592 }
593 #endif /*0*/
594
595 \f
596 /* 
597
598    P O I N T   A N D   C U R V E   O P E R A T I O N S
599
600  */
601
602 /* fixme:
603  * The point at infinity is needed to make 
604  * a group structure to the elliptic curve.
605  * Know if one point is it, is needed so 
606  * much times in this code.
607  *
608  *  return true(1), false(0), or error(-1) for an invalid point
609  */
610 static int
611 point_at_infinity (point_t query)
612 {
613   if (!mpi_cmp_ui (query.z_, 0)) /* Z == 0 */
614     {
615       if ( /*mpi_cmp_ui(Query.x_,0) && */ mpi_cmp_ui (query.y_, 0))
616         {
617           /* X && Y != 0 & Z == 0 */
618           /* Fixme: The above condition is not asserted.  We may get
619              to here if X is 0 ! */
620           if (DBG_CIPHER)
621             log_debug ("True:It is a Point at Infinite.\n");
622           return 1;
623         }
624       if (DBG_CIPHER)
625         log_debug ("Error:It isn't an elliptic curve valid point.\n");
626       return -1;
627     }
628   return 0;  /* It is a valid curve point, but not the point at infinity.  */
629 }
630
631
632 /*
633  * Turn a projective coordinate P to affine.
634  * Returns 0 on success and the affine coordinates at X and Y.
635  *
636  * Note, that Y is never used as we can do without it.
637  */
638 static int
639 point_affine (point_t *P, gcry_mpi_t x, gcry_mpi_t y, elliptic_curve_t *base)
640 {
641   gcry_mpi_t z1, z2, z3;
642
643   if (point_at_infinity (*P))
644     {
645       if (DBG_CIPHER)
646         log_debug ("ecc point_affine: "
647                    "Point at Infinity does NOT exist in the affine plane!\n");
648       return 1;
649     }
650
651   z1 = mpi_new (0);
652   z2 = mpi_new (0);
653   z3 = mpi_new (0);
654
655   mpi_invm (z1, P->z_, base->p_);       /*       z1 =Z^{-1} (mod p) */
656   mpi_mulm (z2, z1, z1, base->p_);      /*       z2 =Z^(-2) (mod p) */
657   mpi_mulm (z3, z2, z1, base->p_);      /*       z3 =Z^(-3) (mod p) */
658   mpi_mulm (x, P->x_, z2, base->p_);
659   mpi_mulm (y, P->y_, z3, base->p_);
660
661   mpi_free (z1);
662   mpi_free (z2);
663   mpi_free (z3);
664   return 0;
665 }
666
667
668 /*
669  * The point inversion over F_p is a simple modular inversion of the Y
670  * coordinate.
671  */
672 static void
673 invert_point (point_t *P, elliptic_curve_t *base)
674 {
675   mpi_subm (P->y_, base->p_, P->y_, base->p_);  /* y = p - y mod p */
676 }
677
678
679 /*
680  * Scalar multiplication of one point, with the integer fixed to 2.
681  *  R = 2P
682  */
683 static void
684 duplicate_point (point_t *R, point_t *P, elliptic_curve_t *base,
685                  ecc_ctx_t pctx)
686 {
687   gcry_mpi_t one, two, three, four, eight;
688   gcry_mpi_t p_3, a;
689   gcry_mpi_t t1, t2, t3, t4, t5, t6, t7;
690   gcry_mpi_t aux;
691
692   one = mpi_alloc_set_ui (1);
693   two = mpi_alloc_set_ui (2);
694   three = mpi_alloc_set_ui (3);
695   four = mpi_alloc_set_ui (4);
696   eight = mpi_alloc_set_ui (8);
697
698   p_3 = mpi_alloc_like (base->p_);
699   mpi_sub_ui (p_3, base->p_, 3);      /* p_3 = p - 3 */
700
701   a  = mpi_copy (base->a_);
702   t1 = mpi_alloc_like (base->p_);
703   t2 = mpi_alloc_like (base->p_);
704   t3 = mpi_alloc_like (base->p_);
705   t4 = mpi_alloc_like (base->p_);
706   t5 = mpi_alloc_like (base->p_);
707   t6 = mpi_alloc_like (base->p_);
708   t7 = mpi_alloc_like (base->p_);
709   aux = mpi_alloc_like (base->p_);
710
711   t1 = mpi_copy (P->x_);        /* t1=x1 */
712   t2 = mpi_copy (P->y_);        /* t2=y1 */
713   t3 = mpi_copy (P->z_);        /* t3=z1 */
714
715   if (!mpi_cmp_ui (t2, 0) || !mpi_cmp_ui (t3, 0))
716     {                           /* t2==0 | t3==0 => [1:1:0] */
717       mpi_set_ui (R->x_, 1);
718       mpi_set_ui (R->y_, 1);
719       mpi_set_ui (R->z_, 0);
720     }
721   else
722     {
723       ecc_mod (a, a, pctx);        /* a mod p  FIXME: really needed? */
724       if (!mpi_cmp (a, p_3))
725         {                       /* a==p-3 */
726           mpi_powm (t4, t3, two, base->p_);    /* t4=t3^2 mod p */
727           mpi_subm (t5, t1, t4, base->p_);     /* t5=t1-t4 mod p */
728           mpi_addm (t4, t1, t4, base->p_);     /* t4=t1+t4 mod p */
729           ecc_mulm (t5, t4, t5, pctx);     /* t5=t4*t5 mod p */
730           ecc_mulm (t4, three, t5, pctx);  /* t4=3*t5 mod p */
731         }
732       else
733         {
734           mpi_set (t4, a);              /* t4=a */
735           mpi_powm (t5, t3, two, base->p_);    /* t5=t3^2 mod p */
736           mpi_powm (t5, t5, two, base->p_);    /* t5=t5^2 mod p */
737           ecc_mulm (t5, t4, t5, pctx);     /* t5=t4*t5 mod p */
738           mpi_powm (t4, t1, two, base->p_);    /* t4=t1^2 mod p */
739           ecc_mulm (t4, three, t4, pctx);  /* t4=3*t4 mod p */
740           mpi_addm (t4, t4, t5, base->p_);     /* t4=t4+t5 mod p */
741         }
742       ecc_mulm (t3, t2, t3, pctx);         /* t3=t2*t3 mod p */
743       ecc_mulm (t3, two, t3, pctx);        /* t3=2*t3 mod p  */
744       mpi_powm (aux, t2, two, base->p_);       /* t2=t2^2 mod p */
745       mpi_set (t2, aux);
746       ecc_mulm (t5, t1, t2, pctx);         /* t5=t1*t2 mod p */
747       ecc_mulm (t5, four, t5, pctx);       /* t5=4*t5 mod p */
748       mpi_powm (t1, t4, two, base->p_);        /* t1=t4^2 mod p */
749       ecc_mulm (aux, two, t5, pctx);
750       mpi_subm (t1, t1, aux, base->p_);        /* t1=t1-2*t5 mod p */
751       mpi_powm (aux, t2, two, base->p_);       /* t2=t2^2 mod p */
752       mpi_set (t2, aux);
753       ecc_mulm (t2, eight, t2, pctx);      /* t2=8*t2 mod p */
754       mpi_subm (t5, t5, t1, base->p_); /* t5=t5-t1 mod p */
755       ecc_mulm (t5, t4, t5, pctx); /* t5=t4*t5 mod p */
756       mpi_subm (t2, t5, t2, base->p_); /* t2=t5-t2 mod p */
757
758       mpi_set (R->x_, t1);
759       mpi_set (R->y_, t2);
760       mpi_set (R->z_, t3);
761     }
762
763   mpi_free (aux);
764   mpi_free (t7);
765   mpi_free (t6);
766   mpi_free (t5);
767   mpi_free (t4);
768   mpi_free (t3);
769   mpi_free (t2);
770   mpi_free (t1);
771   mpi_free (p_3);
772   mpi_free (a);
773   mpi_free (eight);
774   mpi_free (four);
775   mpi_free (three);
776   mpi_free (two);
777   mpi_free (one);
778 }
779
780
781 /*
782    Point addition is the group operation.
783
784    R = P0 + P1
785  */
786 static void
787 sum_points (point_t *R, point_t *P0, point_t *P1, elliptic_curve_t *base,
788             ecc_ctx_t pctx)
789 {
790
791   if ( (!mpi_cmp (P1->x_, P0->x_))
792        && (!mpi_cmp (P1->y_, P0->y_))
793        && (!mpi_cmp (P1->z_, P0->z_)) ) /* P1 == P0 */
794     {                           
795       duplicate_point (R, P0, base, pctx);
796     }
797   else if (point_at_infinity (*P0)) /* R == 0 && P1 == P1 */
798     {                           
799       mpi_set (R->x_, P1->x_);
800       mpi_set (R->y_, P1->y_);
801       mpi_set (R->z_, P1->z_);
802     }
803   else if (point_at_infinity (*P1)) /* R == P0 && P0 == 0 */
804     {           
805       mpi_set (R->x_, P0->x_);
806       mpi_set (R->y_, P0->y_);
807       mpi_set (R->z_, P0->z_);
808     }
809   else
810     {
811       gcry_mpi_t two;
812       gcry_mpi_t t1, t2, t3, t4, t5, t6, t7;
813
814       two = mpi_alloc_set_ui (2);
815
816       t1 = mpi_copy (P0->x_);   /* t1=x0 */
817       t2 = mpi_copy (P0->y_);   /* t2=y0 */
818       t3 = mpi_copy (P0->z_);   /* t3=z0 */
819       t4 = mpi_copy (P1->x_);   /* t4=x1 */
820       t5 = mpi_copy (P1->y_);   /* t5=y2 */
821       t6 = mpi_new (0);
822       t7 = mpi_new (0);
823
824       if (mpi_cmp_ui (P1->z_, 1))  /* z1 != 1 */
825         {                       
826           mpi_set (t6, P1->z_);         /* t6=z1 */
827           mpi_powm (t7, t6, two, base->p_);    /* t7=t6^2 mod p */
828           ecc_mulm (t1, t1, t7, pctx);     /* t1=t1*t7 mod p */
829           ecc_mulm (t7, t6, t7, pctx);     /* t7=t6*t7 mod p */
830           ecc_mulm (t2, t2, t7, pctx);     /* t2=t2*t7 mod p */
831         }
832       mpi_powm (t7, t3, two, base->p_);/* t7=t3^2 mod p */
833       ecc_mulm (t4, t4, t7, pctx); /* t4=t4*t7 mod p */
834       ecc_mulm (t7, t3, t7, pctx); /* t7=t3*t7 mod p */
835       ecc_mulm (t5, t5, t7, pctx); /* t5=t5*t7 mod p */
836       mpi_subm (t4, t1, t4, base->p_); /* t4=t1-t4 mod p */
837       mpi_subm (t5, t2, t5, base->p_); /* t5=t2-t5 mod p */
838
839       if (!mpi_cmp_ui (t4, 0)) /* t4==0 */
840         {                       
841           if (!mpi_cmp_ui (t5, 0))
842             {                   
843               /* return (0:0:0), it has a special mean. */
844               if (DBG_CIPHER)
845                 log_debug ("ecc sum_points: [0:0:0]!\n");
846               mpi_set_ui (R->x_, 0);
847               mpi_set_ui (R->y_, 0);
848               mpi_set_ui (R->z_, 0);
849             }
850           else
851             {           
852               if (DBG_CIPHER)
853                 log_debug ("ecc sum_points: [1:1:0]!\n");
854               mpi_set_ui (R->x_, 1);
855               mpi_set_ui (R->y_, 1);
856               mpi_set_ui (R->z_, 0);
857             }
858         }
859       else
860         {
861           ecc_mulm (t1, two, t1, pctx);
862           mpi_subm (t1, t1, t4, base->p_);     /* t1=2*t1-t4 mod p */
863           ecc_mulm (t2, two, t2, pctx);
864           mpi_subm (t2, t2, t5, base->p_);     /* t2=2*t2-t5 mod p */
865           if (mpi_cmp_ui (P1->z_, 1)) /* z1 != 1 */
866             {           
867               ecc_mulm (t3, t3, t6, pctx); /* t3=t3*t6 */
868             }
869           ecc_mulm (t3, t3, t4, pctx);     /* t3=t3*t4 mod p */
870           mpi_powm (t7, t4, two, base->p_);    /* t7=t4^2 mod p */
871           ecc_mulm (t4, t4, t7, pctx);     /* t4=t4*t7 mod p */
872           ecc_mulm (t7, t1, t7, pctx);     /* t7=t1*t7 mod p */
873           mpi_powm (t1, t5, two, base->p_);    /* t1=t5^2 mod p */
874           mpi_subm (t1, t1, t7, base->p_);     /* t1=t1-t7 mod p */
875           ecc_mulm (t6, two, t1, pctx);
876           mpi_subm (t7, t7, t6, base->p_);     /* t7=t7-2*t1 mod p */
877           ecc_mulm (t5, t5, t7, pctx);     /* t5=t5*t7 mod p */
878           ecc_mulm (t4, t2, t4, pctx);     /* t4=t2*t4 mod p */
879           mpi_subm (t2, t5, t4, base->p_);     /* t2=t5-t4 mod p */
880           mpi_invm (t6, two, base->p_);
881           ecc_mulm (t2, t2, t6, pctx);     /* t2 = t2/2 */
882
883           mpi_set (R->x_, t1);
884           mpi_set (R->y_, t2);
885           mpi_set (R->z_, t3);
886         }
887       mpi_free (t7);
888       mpi_free (t6);
889       mpi_free (t5);
890       mpi_free (t4);
891       mpi_free (t3);
892       mpi_free (t2);
893       mpi_free (t1);
894       mpi_free (two);
895     }
896 }
897
898 /****************
899  * The modular power used without EC, 
900  * is this function over EC.
901    return R = escalarP
902
903    ESCALAR = input
904    P       = input
905    BASE    = input
906    R       = output (caller must have intialized this point)
907
908  */
909 static void
910 escalar_mult (point_t *R, gcry_mpi_t escalar, point_t *P,
911               elliptic_curve_t *base, ecc_ctx_t pctx)
912 {
913   gcry_mpi_t one, two, three;
914   gcry_mpi_t x1, y1, z1, z2, z3, k, h; 
915   gcry_mpi_t xx, yy, zz;
916   unsigned int i, loops;
917   point_t P1, P2, P1_;
918
919   if (DBG_CIPHER)
920     log_debug ("escalar_mult: begin\n");
921
922   one   = mpi_alloc_set_ui (1);
923   two   = mpi_alloc_set_ui (2);
924   three = mpi_alloc_set_ui (3);
925
926   x1 = mpi_alloc_like (P->x_);
927   y1 = mpi_alloc_like (P->y_);
928   /* z1 is not yet intialized.  */
929   z2 = mpi_alloc_like (P->z_);
930   z3 = mpi_alloc_like (P->z_);
931   /* k is not yet intialized.  */
932   h  = mpi_alloc_like (P->z_);
933
934
935   if (!mpi_cmp_ui (escalar, 0) || mpi_cmp_ui (P->z_, 0))
936     {                           /* n=0 | Z=0 => [1:1:0] */
937       mpi_set_ui (R->x_, 1);
938       mpi_set_ui (R->y_, 1);
939       mpi_set_ui (R->z_, 0);
940     }
941   xx = mpi_copy (P->x_);
942   zz = mpi_copy (P->z_);
943   z1 = mpi_copy (one);
944
945   if (mpi_is_neg (escalar))
946     {                           /* (-n)P=n(-P) */
947       escalar->sign = 0;        /* +n */
948       k = mpi_copy (escalar);
949       yy = mpi_copy (P->y_);    /* -P */
950       mpi_invm (yy, yy, base->p_);
951     }
952   else
953     {
954       k = mpi_copy (escalar);
955       yy = mpi_copy (P->y_);
956     }
957   if (!mpi_cmp (zz, one))
958     {                           /* zz==1 */
959       x1 = mpi_copy (xx);
960       y1 = mpi_copy (yy);
961     }
962   else
963     {
964       ecc_mulm (z2, zz, zz, pctx); /* z^2 */
965       ecc_mulm (z3, zz, z2, pctx); /* z^3 */
966       mpi_invm (z2, z2, base->p_);     /* 1/Z^2 */
967       ecc_mulm (x1, xx, z2, pctx); /* xx/z^2 */
968       mpi_invm (z3, z3, base->p_);     /* 1/z^3 */
969       ecc_mulm (y1, yy, z3, pctx); /* yy/z^3 */
970     }
971   mpi_mul (h, three, k);        /* h=3k */
972   loops = mpi_get_nbits (h);
973   i = loops - 2;                /*  i = l-1 = loops-2 */
974   mpi_set (R->x_, xx);
975   mpi_set (R->y_, yy);
976   mpi_set (R->z_, zz);
977   P1.x_ = mpi_copy (x1);
978   P1.y_ = mpi_copy (y1);
979   P1.z_ = mpi_copy (z1);
980   while (i > 0)
981     {                           /*  A.10.9. step 11  i from l-1 downto 1 */
982       duplicate_point (R, R, base, pctx);
983       if (mpi_test_bit (h, i) == 1 && mpi_test_bit (k, i) == 0)
984         {                       /* h_i=1 & k_i=0 */
985           P2 = point_copy (*R);
986           sum_points (R, &P2, &P1, base, pctx); /* R=P2+P1 over the base elliptic curve */
987         }
988       if (mpi_test_bit (h, i) == 0 && mpi_test_bit (k, i) == 1)
989         {                       /* h_i=0 & k_i=1 */
990           P2 = point_copy (*R);
991           P1_ = point_copy (P1);
992           invert_point (&P1_, base);
993           sum_points (R, &P2, &P1_, base, pctx); /* R=P2+P1_ over the base elliptic curve */
994         }
995       i--;
996     }
997
998   if (DBG_CIPHER)
999     log_debug ("escalar_mult: ready\n");
1000
1001   point_free (&P1);
1002   point_free (&P2);
1003   point_free (&P1_);
1004   mpi_free (h);
1005   mpi_free (k);
1006   mpi_free (z3);
1007   mpi_free (z2);
1008   mpi_free (z1);
1009   mpi_free (y1);
1010   mpi_free (x1);
1011   mpi_free (zz);
1012   mpi_free (yy);
1013   mpi_free (xx);
1014   mpi_free (three);
1015   mpi_free (two);
1016   mpi_free (one);
1017 }
1018
1019
1020 /****************
1021  * Solve the right side of the equation that defines a curve.
1022  */
1023 static gcry_mpi_t
1024 gen_y_2 (gcry_mpi_t x, elliptic_curve_t *base)
1025 {
1026   gcry_mpi_t three;
1027   gcry_mpi_t x_3, ax, axb, y;
1028   gcry_mpi_t a, b, p;
1029   unsigned int nbits;
1030
1031   three = mpi_alloc_set_ui (3);
1032   a = mpi_copy (base->a_);
1033   b = mpi_copy (base->b_);
1034   p = mpi_copy (base->p_);
1035   nbits = mpi_get_nbits (p);
1036   x_3 = mpi_new (nbits);
1037   ax  = mpi_new (nbits);
1038   axb = mpi_new (nbits);
1039   y   = mpi_new (nbits);
1040
1041   if (DBG_CIPHER)
1042     log_debug ("ecc gen_y_2: Solving an elliptic equation.\n");
1043
1044   mpi_powm (x_3, x, three, p);  /* x_3=x^3 mod p */
1045   mpi_mulm (ax, a, x, p);       /* ax=a*x mod p */
1046   mpi_addm (axb, ax, b, p);     /* axb=ax+b mod p */
1047   mpi_addm (y, x_3, axb, p);    /* y=x^3+ax+b mod p */
1048
1049   if (DBG_CIPHER)
1050     log_debug ("ecc gen_y_2: Solved.\n");
1051
1052   return y; /* The quadratic value of the coordinate if it exist. */
1053 }
1054
1055
1056
1057
1058
1059 \f
1060 /*
1061
1062    E C C  C O R E  F U N C T I O N S
1063  
1064  */
1065
1066
1067
1068 /* Generate a random secret scalar k with an order of p
1069
1070    At the beginning this was identical to the code is in elgamal.c.
1071    Later imporved by mmr.   Further simplified by wk.  */
1072 static gcry_mpi_t
1073 gen_k (gcry_mpi_t p, int secure)
1074 {
1075   gcry_mpi_t k;
1076   unsigned int nbits;
1077
1078   nbits = mpi_get_nbits (p);
1079   k = (secure
1080        ? mpi_alloc_secure ( mpi_get_nlimbs (p) )
1081        : mpi_alloc ( mpi_get_nlimbs (p) ));
1082
1083   if (DBG_CIPHER)
1084     log_debug ("choosing a random k of %u bits\n", nbits);
1085   
1086   gcry_mpi_randomize (k, nbits, GCRY_STRONG_RANDOM);
1087
1088   mpi_mod (k, k, p);  /*  k = k mod p  */
1089
1090   if (DBG_CIPHER)
1091     progress ('\n');
1092
1093   return k;
1094 }
1095
1096
1097 /* Helper to scan a hex string. */
1098 static gcry_mpi_t
1099 scanval (const char *string)
1100 {
1101   gpg_error_t err;
1102   gcry_mpi_t val;
1103   
1104   err = gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL);
1105   if (err)
1106     log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (err));
1107   return val;
1108 }
1109
1110
1111 /****************
1112  * Generate the crypto system setup.
1113  * As of now the fix NIST recommended values are used.
1114  * The subgroup generator point is in another function: gen_big_point.
1115  */
1116 static gpg_err_code_t
1117 generate_curve (unsigned int nbits, elliptic_curve_t *curve)
1118 {
1119   int idx;
1120
1121   for (idx = 0; domain_parms[idx].desc; idx++)
1122     if (nbits == domain_parms[idx].nbits)
1123       break;
1124   if (!domain_parms[idx].desc)
1125     return GPG_ERR_INV_VALUE;
1126
1127   curve->p_ = scanval (domain_parms[idx].p);
1128   curve->a_ = scanval (domain_parms[idx].a);
1129   curve->b_ = scanval (domain_parms[idx].b);
1130   curve->n_ = scanval (domain_parms[idx].n);
1131   curve->G.x_ = scanval (domain_parms[idx].g_x);
1132   curve->G.y_ = scanval (domain_parms[idx].g_y);
1133   curve->G.z_ = mpi_alloc_set_ui (1);
1134
1135   /* Gx, Gy, Gz are planned to be generated by code like this:
1136      if ( gen_big_point (&curve->n_, curve, &curve->G, nbits) == -1)
1137       {
1138          log_fatal ("ECC operation: Point generation failed\n");
1139       }
1140
1141      A point of order 'n' is needed to generate a cyclic subgroup.
1142      Over this cyclic subgroup it's defined the ECDLP.  Now it use a
1143      fix values from NIST FIPS PUB 186-2.  Returns -1 if it isn't
1144      possible.
1145      static int
1146      gen_big_point (gcry_mpi_t * prime, elliptic_curve_t * base, point_t * G,
1147                     unsigned int nbits)
1148      {
1149          unsigned int i=0;
1150          gcry_mpi_t one;
1151          point_t Big, P;
1152     
1153          one = mpi_alloc_set_ui(1);
1154          G->x_ = mpi_alloc(mpi_get_nlimbs(*prime));
1155          G->y_ = mpi_alloc(mpi_get_nlimbs(*prime));
1156          G->z_ = mpi_alloc(mpi_get_nlimbs(*prime));
1157     
1158          if( DBG_CIPHER )log_debug("Generating a Big point.\n");
1159          do{
1160          do{
1161          *P = genPoint(*prime,*base);
1162          }while(PointAtInfinity(*P));//A random point in the curve that it's not PaI
1163          escalarMult(base.h,&P,&G,&base);//cofactor (1 o 2), could be improved
1164          }while(PointAtInfinity(G));
1165          if( DBG_CIPHER )log_debug("Big point generated.\n");
1166          if( DBG_CIPHER ){
1167          log_mpidump("Gx=",G->x_);log_mpidump("Gy=",G->y_);log_mpidump("Gz=",G->z_);
1168          }
1169      return 0;
1170      }
1171   */
1172
1173   if (DBG_CIPHER)
1174     {
1175       progress ('\n');
1176       log_mpidump ("ecc generation  p= ", curve->p_);
1177       log_mpidump ("ecc generation  a= ", curve->a_);
1178       log_mpidump ("ecc generation  b= ", curve->b_);
1179       log_mpidump ("ecc generation  n= ", curve->n_);
1180       log_mpidump ("ecc generation  Gx= ", curve->G.x_);
1181       log_mpidump ("ecc generation  Gy= ", curve->G.y_);
1182       log_mpidump ("ecc generation  Gz= ", curve->G.z_);
1183     }
1184   if (DBG_CIPHER)
1185     progress ('\n');
1186
1187   return 0;
1188 }
1189
1190
1191 /****************
1192  * First obtain the setup.  Over the finite field randomize an scalar
1193  * secret value, and calculate the public point.
1194  */
1195 static gpg_err_code_t
1196 generate_key (ECC_secret_key *sk, unsigned int nbits)
1197 {
1198   gpg_err_code_t err;
1199   elliptic_curve_t E;
1200   gcry_mpi_t d;
1201   point_t Q, G;
1202   ecc_ctx_t pctx;
1203
1204   err = generate_curve (nbits, &E);
1205   if (err)
1206     return err;
1207
1208   d = mpi_snew (nbits);
1209   if (DBG_CIPHER)
1210     log_debug ("choosing a random x of size %u\n", nbits);
1211   d = gen_k (E.n_, 2);          /* generate_secret_prime(nbits); */
1212   G = point_copy (E.G);
1213
1214   /* Compute Q.  */
1215   point_init (&Q);
1216   pctx = ecc_ctx_init (E.p_, 0);
1217   escalar_mult (&Q, d, &E.G, &E, pctx);
1218   ecc_ctx_free (pctx);
1219
1220   /* Copy the stuff to the key structures. */
1221   sk->E.p_ = mpi_copy (E.p_);
1222   sk->E.a_ = mpi_copy (E.a_);
1223   sk->E.b_ = mpi_copy (E.b_);
1224   sk->E.G  = point_copy (E.G);
1225   sk->E.n_ = mpi_copy (E.n_);
1226   sk->Q    = point_copy (Q);
1227   sk->d    = mpi_copy (d);
1228
1229   /* Now we can test our keys (this should never fail!). */
1230   test_keys (sk, nbits - 64);
1231
1232   point_free (&Q);
1233   mpi_free (d);
1234   curve_free (&E);
1235
1236   return 0;
1237 }
1238
1239
1240 /****************
1241  * To verify correct skey it use a random information.
1242  * First, encrypt and decrypt this dummy value, 
1243  * test if the information is recuperated.
1244  * Second, test with the sign and verify functions.
1245  */
1246 static void
1247 test_keys (ECC_secret_key *sk, unsigned int nbits)
1248 {
1249   ECC_public_key pk;
1250   gcry_mpi_t test = mpi_new (nbits);
1251   point_t R_;
1252   gcry_mpi_t c = mpi_new (nbits);
1253   gcry_mpi_t out = mpi_new (nbits);
1254   gcry_mpi_t r = mpi_new (nbits);
1255   gcry_mpi_t s = mpi_new (nbits);
1256
1257   if (DBG_CIPHER)
1258     log_debug ("Testing key.\n");
1259
1260   point_init (&R_);
1261
1262   pk.E = curve_copy (sk->E);
1263   pk.Q = point_copy (sk->Q);
1264
1265   gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM);
1266
1267 #if 0  
1268   doEncrypt (test, &pk, &R_, c);
1269
1270   out = decrypt (out, sk, R_, c);
1271
1272   if (mpi_cmp (test, out))      /* test!=out */
1273     log_fatal ("ECELG operation: encrypt, decrypt failed\n");
1274   if (DBG_CIPHER)
1275     log_debug ("ECELG operation: encrypt, decrypt ok.\n");
1276 #endif
1277
1278   if (sign (test, sk, r, s) )
1279     log_fatal ("ECDSA operation: sign failed\n");
1280
1281   if (verify (test, &pk, r, s))
1282     {
1283       log_fatal ("ECDSA operation: sign, verify failed\n");
1284     }
1285
1286   if (DBG_CIPHER)
1287     log_debug ("ECDSA operation: sign, verify ok.\n");
1288
1289   point_free (&pk.Q);
1290   curve_free (&pk.E);
1291
1292   point_free (&R_);
1293   mpi_free (s);
1294   mpi_free (r);
1295   mpi_free (out);
1296   mpi_free (c);
1297   mpi_free (test);
1298 }
1299
1300 /****************
1301  * To check the validity of the value, recalculate the correspondence
1302  * between the public value and de secret one.
1303  */
1304 static int
1305 check_secret_key (ECC_secret_key * sk)
1306 {
1307   point_t Q;
1308   gcry_mpi_t y_2, y2 = mpi_alloc (0);
1309   ecc_ctx_t pctx;
1310
1311   /* ?primarity test of 'p' */
1312   /*  (...) //!! */
1313   /* G in E(F_p) */
1314   y_2 = gen_y_2 (sk->E.G.x_, &sk->E);   /*  y^2=x^3+a*x+b */
1315   mpi_mulm (y2, sk->E.G.y_, sk->E.G.y_, sk->E.p_);      /*  y^2=y*y */
1316   if (mpi_cmp (y_2, y2))
1317     {
1318       if (DBG_CIPHER)
1319         log_debug ("Bad check: Point 'G' does not belong to curve 'E'!\n");
1320       return (1);
1321     }
1322   /* G != PaI */
1323   if (point_at_infinity (sk->E.G))
1324     {
1325       if (DBG_CIPHER)
1326         log_debug ("Bad check: 'G' cannot be Point at Infinity!\n");
1327       return (1);
1328     }
1329   /* ?primarity test of 'n' */
1330   /*  (...) //!! */
1331   /* ?(p-sqrt(p)) < n < (p+sqrt(p)) */
1332   /* ?n!=p */
1333   /* ?(n^k) mod p !=1 for k=1 to 31 (from GOST) or k=1 to 50 (from MIRACL) */
1334   /* Q=[n]G over E = PaI */
1335
1336   point_init (&Q);
1337   pctx = ecc_ctx_init (sk->E.p_, 0);
1338   escalar_mult (&Q, sk->E.n_, &sk->E.G, &sk->E, pctx);
1339   if (!point_at_infinity (Q))
1340     {
1341       if (DBG_CIPHER)
1342         log_debug ("check_secret_key: E is not a curve of order n\n");
1343       point_free (&Q);
1344       ecc_ctx_free (pctx);
1345       return 1;
1346     }
1347   /* pubkey cannot be PaI */
1348   if (point_at_infinity (sk->Q))
1349     {
1350       if (DBG_CIPHER)
1351         log_debug ("Bad check: Q can not be a Point at Infinity!\n");
1352       ecc_ctx_free (pctx);
1353       return (1);
1354     }
1355   /* pubkey = [d]G over E */
1356   escalar_mult (&Q, sk->d, &sk->E.G, &sk->E, pctx);
1357   if ((Q.x_ == sk->Q.x_) && (Q.y_ == sk->Q.y_) && (Q.z_ == sk->Q.z_))
1358     {
1359       if (DBG_CIPHER)
1360         log_debug
1361           ("Bad check: There is NO correspondence between 'd' and 'Q'!\n");
1362       ecc_ctx_free (pctx);
1363       return (1);
1364     }
1365   ecc_ctx_free (pctx);
1366   point_free (&Q);
1367   return 0;
1368 }
1369
1370
1371 #if 0
1372 /****************
1373  * Encrypt a number and obtain and struct (R,c)
1374  */
1375 static void
1376 doEncrypt (gcry_mpi_t input, ECC_public_key * pkey, point_t * R, gcry_mpi_t c)
1377 {
1378
1379   gcry_mpi_t k, p, x, y;
1380   point_t P, Q, G;
1381   elliptic_curve_t E;
1382
1383   k = mpi_alloc (0);
1384   p = mpi_copy (pkey->E.p_);
1385   x = mpi_alloc (0);
1386   y = mpi_alloc (0);
1387   Q = point_copy (pkey->Q);
1388   G = point_copy (pkey->E.G);
1389   E = curve_copy (pkey->E);
1390
1391   k = gen_k (p, 1);             /* 2nd parametre: how much security? */
1392   escalarMult (k, &Q, &P, &E);  /* P=[k]Q=[k]([d]G) */
1393   escalarMult (k, &G, R, &E);   /* R=[k]G */
1394   /* IFP weakness//mpi_mul(c,input,Q.x_);//c=input*Q_x */
1395   /* MMR Use affine conversion befor extract x-coordinate */
1396   if (point_affine (&P, x, y, &E))
1397     {                           /* Q cannot turn to affine coordinate */
1398       if (DBG_CIPHER)
1399         {
1400           log_debug ("Encrypting: Cannot turn to affine.\n");
1401         }
1402     }
1403   /* MMR According to the standard P1363 we can not use x-coordinate directly. */
1404   /*  It is necessary to add hash-operation later.  */
1405   /*  As the maximal length of a key for the symmetric cipher is 256 bit it is possible to take hash-function SHA256. */
1406   sha256_hashing (x, &x);
1407   aes256_encrypting (x, input, &c);
1408
1409   if (DBG_CIPHER)
1410     {
1411       log_debug ("doEncrypt: end.\n");
1412     }
1413 }
1414 #endif /*0*/
1415
1416 #if 0
1417 /****************
1418  * Undo the ciphertext
1419  */
1420 static gcry_mpi_t
1421 decrypt (gcry_mpi_t output, ECC_secret_key * skey, point_t R, gcry_mpi_t c)
1422 {
1423
1424   gcry_mpi_t p, inv, x, y;
1425   point_t P, Q;
1426   elliptic_curve_t E;
1427
1428   p = mpi_copy (skey->E.p_);
1429   inv = mpi_alloc (0);
1430   x = mpi_alloc (0);
1431   y = mpi_alloc (0);
1432   Q = point_copy (skey->Q);
1433   E = curve_copy (skey->E);
1434
1435   escalarMult (skey->d, &R, &P, &E);    /* P=[d]R */
1436   /* That is like: mpi_fdiv_q(output,c,Q.x_); */
1437   /* IFP weakness//mpi_invm(inv,Q.x_,p);//inv=Q{_x}^-1 (mod p) */
1438   /* IFP weakness//mpi_mulm(output,c,inv,p);//output=c*inv (mod p) */
1439   /* MMR Use affine conversion befor extract x-coordinate */
1440   if (point_affine (&P, x, y, &E))
1441     {                           /* Q cannot turn to affine coordinate */
1442       if (DBG_CIPHER)
1443         {
1444           log_debug ("Encrypting: Cannot turn to affine.\n");
1445         }
1446     }
1447   sha256_hashing (x, &x);
1448   aes256_decrypting (x, c, &output);
1449
1450   if (DBG_CIPHER)
1451     {
1452       log_debug ("decrypt: end.\n");
1453     }
1454   return (output);
1455 }
1456 #endif /*0*/
1457
1458
1459 /*
1460  * Return the signature struct (r,s) from the message hash.  The caller
1461  * must have allocated R and S.
1462  */
1463 static gpg_err_code_t
1464 sign (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s)
1465 {
1466   gpg_err_code_t err = 0;
1467   gcry_mpi_t k, dr, sum, k_1, x, y;
1468   point_t I;
1469   ecc_ctx_t pctx;
1470   
1471   k = NULL;
1472   dr = mpi_alloc (0);
1473   sum = mpi_alloc (0);
1474   k_1 = mpi_alloc (0);
1475   x = mpi_alloc (0);
1476   y = mpi_alloc (0);
1477   point_init (&I);
1478
1479   mpi_set_ui (s, 0);
1480   mpi_set_ui (r, 0);
1481
1482   pctx = ecc_ctx_init (skey->E.p_, 0);
1483
1484   while (!mpi_cmp_ui (s, 0)) /* s == 0 */
1485     {                           
1486       while (!mpi_cmp_ui (r, 0)) /* r == 0 */
1487         {               
1488           /* Note, that we are guaranteed to enter this loop at least
1489              once because r has been intialized to 0.  We can't use a
1490              do_while because we want to keep the value of R even if S
1491              has to be recomputed.  */
1492           mpi_free (k);
1493           k = gen_k (skey->E.p_, 1); /* fixme:  shouldn't that be E.n ? */
1494           escalar_mult (&I, k, &skey->E.G, &skey->E, pctx); /* I = [k]G */
1495           if (point_affine (&I, x, y, &skey->E))
1496             {
1497               if (DBG_CIPHER)
1498                 log_debug ("ecc sign: Cannot turn to affine. "
1499                            " Cannot complete sign.\n");
1500               err = GPG_ERR_BAD_SIGNATURE;
1501               goto leave;
1502             }
1503           mpi_mod (r, x, skey->E.n_);   /* r = x mod n */
1504         }
1505       mpi_mulm (dr, skey->d, r, skey->E.n_);/* dr = d*r mod n */
1506       mpi_addm (sum, input, dr, skey->E.n_);/* sum = hash + (d*r) mod n */
1507       mpi_invm (k_1, k, skey->E.n_);        /* k_1 = k^(-1) mod n */
1508       mpi_mulm (s, k_1, sum, skey->E.n_);   /* s = k^(-1)*(hash+(d*r)) mod n */
1509     }
1510
1511  leave:
1512   ecc_ctx_free (pctx);
1513   point_free (&I);
1514   mpi_free (y);
1515   mpi_free (x);
1516   mpi_free (k_1);
1517   mpi_free (sum);
1518   mpi_free (dr);
1519   mpi_free (k);
1520
1521   return err;
1522 }
1523
1524 /*
1525  * Check if R and S verifies INPUT.
1526  */
1527 static gpg_err_code_t
1528 verify (gcry_mpi_t input, ECC_public_key *pkey, gcry_mpi_t r, gcry_mpi_t s)
1529 {
1530   gpg_err_code_t err = 0;
1531   gcry_mpi_t h, h1, h2, x, y;
1532   point_t Q, Q1, Q2;
1533   ecc_ctx_t pctx;
1534
1535   if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n_) < 0) )
1536     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < r < n  failed.  */
1537   if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n_) < 0) )
1538     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < s < n  failed.  */
1539
1540   h  = mpi_alloc (0);
1541   h1 = mpi_alloc (0);
1542   h2 = mpi_alloc (0);
1543   x = mpi_alloc (0);
1544   y = mpi_alloc (0);
1545   point_init (&Q);
1546   point_init (&Q1);
1547   point_init (&Q2);
1548
1549   pctx = ecc_ctx_init (pkey->E.p_, 0);
1550
1551   /* h  = s^(-1) (mod n) */
1552   mpi_invm (h, s, pkey->E.n_);           
1553   /* h1 = hash * s^(-1) (mod n) */
1554   mpi_mulm (h1, input, h, pkey->E.n_); 
1555   /* Q1 = [ hash * s^(-1) ]G  */
1556   escalar_mult (&Q1, h1, &pkey->E.G, &pkey->E, pctx );
1557   /* h2 = r * s^(-1) (mod n) */
1558   mpi_mulm (h2, r, h, pkey->E.n_);             
1559   /* Q2 = [ r * s^(-1) ]Q */
1560   escalar_mult (&Q2, h2, &pkey->Q, &pkey->E, pctx);
1561   /* Q  = ([hash * s^(-1)]G) + ([r * s^(-1)]Q) */
1562   sum_points (&Q, &Q1, &Q2, &pkey->E, pctx);
1563
1564   if (point_at_infinity (Q))
1565     {
1566       if (DBG_CIPHER)
1567           log_debug ("ecc verification: Rejected.\n");
1568       err = GPG_ERR_BAD_SIGNATURE;
1569       goto leave;
1570     }
1571   if (point_affine (&Q, x, y, &pkey->E))
1572     {                   
1573       if (DBG_CIPHER)
1574         log_debug ("ecc verification: Cannot turn to affine. Rejected.\n");
1575       err = GPG_ERR_BAD_SIGNATURE;
1576       goto leave;
1577     }
1578   mpi_mod (x, x, pkey->E.n_); /* x = x mod E_n */
1579   if (mpi_cmp (x, r))   /* x != r */
1580     {                           
1581       if (DBG_CIPHER)
1582         log_debug ("ecc verification: Not verified.\n");
1583       err = GPG_ERR_BAD_SIGNATURE;
1584       goto leave;
1585     }
1586   if (DBG_CIPHER)
1587     log_debug ("ecc verification: Accepted.\n");
1588
1589  leave:
1590   ecc_ctx_free (pctx);
1591   point_free (&Q2);
1592   point_free (&Q1);
1593   point_free (&Q);
1594   mpi_free (y);
1595   mpi_free (x);
1596   mpi_free (h2);
1597   mpi_free (h1);
1598   mpi_free (h);
1599   return err;
1600 }
1601
1602
1603 /****************
1604  * Generate a random point over an Elliptic curve is the first step to
1605  * find a random cyclic subgroup generator.
1606  *
1607  *        !! At this moment it isn't used !!  //!!
1608  */
1609 #if 0
1610 static point_t
1611 gen_point (gcry_mpi_t prime, elliptic_curve_t base)
1612 {
1613
1614   unsigned int i = 0;
1615   gcry_mpi_t x, y_2, y;
1616   gcry_mpi_t one, one_neg, bit;
1617   point_t P;
1618
1619   x = mpi_alloc (mpi_get_nlimbs (base.p_));
1620   y_2 = mpi_alloc (mpi_get_nlimbs (base.p_));
1621   y = mpi_alloc (mpi_get_nlimbs (base.p_));
1622   one = mpi_alloc_set_ui (1);
1623   one_neg = mpi_alloc (mpi_get_nlimbs (one));
1624   mpi_invm (one_neg, one, base.p_);
1625
1626   if (DBG_CIPHER)
1627     log_debug ("Generating a normal point.\n");
1628   do
1629     {
1630       x = gen_k (base.p_, 1);   /* generate_public_prime(mpi_get_nlimbs(base.n_)*BITS_PER_MPI_LIMB); */
1631       do
1632         {
1633           y_2 = gen_y_2 (x, &base);     /* x^3+ax+b (mod p) */
1634           mpi_add_ui (x, x, 1);
1635           i++;
1636         }
1637       while (!mpi_cmp_ui (y_2, 0) && i < 0xf);  /* Try to find a valid value until 16 iterations. */
1638       i = 0;
1639       y = existSquareRoot (y_2, base.p_);
1640     }
1641   while (!mpi_cmp_ui (y, 0));   /* Repeat until a valid coordinate is found. */
1642   bit = gen_bit ();             /* generate one bit */
1643   if (mpi_cmp_ui (bit, 1))
1644     {                           /* choose the y coordinate */
1645       mpi_invm (y, y, base.p_); /* mpi_powm(y, y, one_neg,base.p_); */
1646     }
1647   if (DBG_CIPHER)
1648     log_debug ("Normal point generated.\n");
1649
1650   P.x_ = mpi_copy (x);
1651   P.y_ = mpi_copy (y);
1652   P.z_ = mpi_copy (one);
1653
1654   mpi_free (bit);
1655   mpi_free (one_neg);
1656   mpi_free (one);
1657   mpi_free (y);
1658   mpi_free (y_2);
1659   mpi_free (x);
1660
1661   return (P);
1662 }
1663 #endif /*0*/
1664
1665 /****************
1666  * Boolean generator to choose between to coordinates.
1667  */
1668 #if 0
1669 static gcry_mpi_t
1670 gen_bit ()
1671 {
1672   gcry_mpi_t aux = mpi_alloc_set_ui (0);
1673
1674   /* FIXME: This is highly ineffective but the whole function is used
1675      only at one place. */
1676
1677   /* Get one random bit, with less security level, and translate it to
1678      an MPI. */
1679   mpi_set_buffer (aux, get_random_bits (1, 0, 1), 1, 0);        /* gen_k(...) */
1680
1681   return aux;                   /* b; */
1682 }
1683 #endif /*0*/
1684
1685
1686 \f
1687 #if 0
1688 /* Function to solve an IFP ECElGamal weakness: */
1689 /*  sha256_hashing() */
1690 /*  aes256_encrypting() */
1691 /*  aes356_decrypting() */
1692
1693 /****************
1694  * Compute 256 bit hash value from input MPI.
1695  * Use SHA256 Algorithm.
1696  */
1697 static void
1698 sha256_hashing (gcry_mpi_t input, gcry_mpi_t * output)
1699 {                               /*   */
1700
1701   int sign;
1702   byte *hash_inp_buf;
1703   byte hash_out_buf[32];
1704   MD_HANDLE hash = md_open (8, 1);      /* algo SHA256 in secure mode */
1705
1706   unsigned int nbytes;
1707
1708   hash_inp_buf = mpi_get_secure_buffer (input, &nbytes, &sign); /* convert gcry_mpi_t input to string */
1709
1710   md_write (hash, hash_inp_buf, nbytes);        /* hashing input string */
1711   wipememory (hash_inp_buf, sizeof hash_inp_buf);       /*  burn temp value  */
1712   xfree (hash_inp_buf);
1713
1714   md_digest (hash, 8, hash_out_buf, 32);
1715   mpi_set_buffer (*output, hash_out_buf, 32, 0);        /*  convert 256 bit digest to MPI */
1716
1717   wipememory (hash_out_buf, sizeof hash_out_buf);       /*  burn temp value  */
1718   md_close (hash);              /*  destroy and free hash state. */
1719
1720 }
1721
1722 /****************
1723  * Encrypt input MPI.
1724  * Use AES256 algorithm.
1725  */
1726
1727 static void
1728 aes256_encrypting (gcry_mpi_t key, gcry_mpi_t input, gcry_mpi_t * output)
1729 {                               /*   */
1730
1731   int sign;
1732   byte *key_buf;
1733   byte *cipher_buf;
1734
1735   unsigned int keylength;
1736   unsigned int nbytes;
1737
1738
1739   CIPHER_HANDLE cipher = cipher_open (9, CIPHER_MODE_CFB, 1);   /* algo AES256 CFB mode in secure memory */
1740   cipher_setiv (cipher, NULL, 0);       /*  Zero IV */
1741
1742   key_buf = mpi_get_secure_buffer (key, &keylength, &sign);     /* convert MPI key to string */
1743   cipher_setkey (cipher, key_buf, keylength);
1744   wipememory (key_buf, sizeof key_buf); /*  burn temp value  */
1745   xfree (key_buf);
1746
1747   cipher_buf = mpi_get_secure_buffer (input, &nbytes, &sign);   /* convert MPI input to string */
1748
1749   cipher_encrypt (cipher, cipher_buf + 1, cipher_buf + 1, nbytes - 1);  /*  */
1750   cipher_close (cipher);        /*  destroy and free cipher state. */
1751
1752   mpi_set_buffer (*output, cipher_buf, nbytes, 0);      /*  convert encrypted string to MPI */
1753   wipememory (cipher_buf, sizeof cipher_buf);   /*  burn temp value  */
1754   xfree (cipher_buf);
1755 }
1756
1757 /****************
1758  * Decrypt input MPI.
1759  * Use AES256 algorithm.
1760  */
1761
1762 static void
1763 aes256_decrypting (gcry_mpi_t key, gcry_mpi_t input, gcry_mpi_t * output)
1764 {                               /*   */
1765
1766   int sign;
1767   byte *key_buf;
1768   byte *cipher_buf;
1769
1770   unsigned int keylength;
1771   unsigned int nbytes;
1772
1773
1774   CIPHER_HANDLE cipher = cipher_open (9, CIPHER_MODE_CFB, 1);   /* algo AES256 CFB mode in secure memory */
1775   cipher_setiv (cipher, NULL, 0);       /*  Zero IV */
1776
1777   key_buf = mpi_get_secure_buffer (key, &keylength, &sign);     /* convert MPI input to string */
1778   cipher_setkey (cipher, key_buf, keylength);
1779   wipememory (key_buf, sizeof key_buf); /*  burn temp value  */
1780   xfree (key_buf);
1781
1782   cipher_buf = mpi_get_secure_buffer (input, &nbytes, &sign);   /* convert MPI input to string; */
1783
1784   cipher_decrypt (cipher, cipher_buf + 1, cipher_buf + 1, nbytes - 1);  /*  */
1785   cipher_close (cipher);        /*  destroy and free cipher state. */
1786
1787   mpi_set_buffer (*output, cipher_buf, nbytes, 0);      /*  convert encrypted string to MPI */
1788   wipememory (cipher_buf, sizeof cipher_buf);   /*  burn temp value  */
1789   xfree (cipher_buf);
1790 }
1791
1792 /* End of IFP ECElGamal weakness functions. */
1793 #endif /*0*/
1794
1795 /*********************************************
1796  **************  interface  ******************
1797  *********************************************/
1798
1799 static gcry_err_code_t
1800 ecc_generate (int algo, unsigned int nbits, unsigned long dummy,
1801               gcry_mpi_t *skey, gcry_mpi_t **retfactors)
1802 {
1803   gpg_err_code_t err;
1804   ECC_secret_key sk;
1805
1806   (void)algo;
1807
1808   /* Make an empty list of factors.  */
1809   *retfactors = gcry_calloc ( 1, sizeof **retfactors );
1810   if (!*retfactors)
1811     return gpg_err_code_from_syserror ();
1812
1813   err = generate_key (&sk, nbits);
1814   if (err)
1815     {
1816       gcry_free (*retfactors);
1817       *retfactors = NULL;
1818       return err;
1819     }
1820
1821   skey[0] = sk.E.p_;
1822   skey[1] = sk.E.a_;
1823   skey[2] = sk.E.b_;
1824   skey[3] = sk.E.G.x_;
1825   skey[4] = sk.E.G.y_;
1826   skey[5] = sk.E.G.z_;
1827   skey[6] = sk.E.n_;
1828   skey[7] = sk.Q.x_;
1829   skey[8] = sk.Q.y_;
1830   skey[9] = sk.Q.z_;
1831   skey[10] = sk.d;
1832
1833   if (DBG_CIPHER)
1834     {
1835       progress ('\n');
1836
1837       log_mpidump ("[ecc]  p= ", skey[0]);
1838       log_mpidump ("[ecc]  a= ", skey[1]);
1839       log_mpidump ("[ecc]  b= ", skey[2]);
1840       log_mpidump ("[ecc]  Gx= ", skey[3]);
1841       log_mpidump ("[ecc]  Gy= ", skey[4]);
1842       log_mpidump ("[ecc]  Gz= ", skey[5]);
1843       log_mpidump ("[ecc]  n= ", skey[6]);
1844       log_mpidump ("[ecc]  Qx= ", skey[7]);
1845       log_mpidump ("[ecc]  Qy= ", skey[8]);
1846       log_mpidump ("[ecc]  Qz= ", skey[9]);
1847       log_mpidump ("[ecc]  d= ", skey[10]);
1848     }
1849
1850   if (DBG_CIPHER)
1851     {
1852       log_debug ("ECC key Generated.\n");
1853     }
1854   return 0;
1855 }
1856
1857
1858 static gcry_err_code_t
1859 ecc_check_secret_key (int algo, gcry_mpi_t *skey)
1860 {
1861   ECC_secret_key sk;
1862
1863   (void)algo;
1864
1865   if (!skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] || !skey[5]
1866       || !skey[6] || !skey[7] || !skey[8] || !skey[9] || !skey[10])
1867     return GPG_ERR_BAD_MPI;
1868
1869   if (DBG_CIPHER)
1870     {
1871       log_debug ("ECC check secret key.\n");
1872     }
1873   sk.E.p_ = skey[0];
1874   sk.E.a_ = skey[1];
1875   sk.E.b_ = skey[2];
1876   sk.E.G.x_ = skey[3];
1877   sk.E.G.y_ = skey[4];
1878   sk.E.G.z_ = skey[5];
1879   sk.E.n_ = skey[6];
1880   sk.Q.x_ = skey[7];
1881   sk.Q.y_ = skey[8];
1882   sk.Q.z_ = skey[9];
1883   sk.d = skey[10];
1884
1885   if (check_secret_key (&sk))
1886     {
1887       if (DBG_CIPHER)
1888         log_debug ("Bad check: Bad secret key.\n");
1889       return GPG_ERR_BAD_SECKEY;
1890     }
1891   return 0;
1892 }
1893
1894
1895 #if 0
1896 static int
1897 ecc_encrypt_FIXME (int algo, gcry_mpi_t * resarr, gcry_mpi_t data, gcry_mpi_t * pkey)
1898 {
1899   ECC_public_key pk;
1900   point R;
1901
1902   if (algo != PUBKEY_ALGO_ECC && algo != PUBKEY_ALGO_ECC_E)
1903     return G10ERR_PUBKEY_ALGO;
1904   if (!data || !pkey[0] || !pkey[1] || !pkey[2] || !pkey[3] || !pkey[4]
1905       || !pkey[5] || !pkey[6] || !pkey[7] || !pkey[8] || !pkey[9])
1906     return G10ERR_BAD_MPI;
1907
1908   if (DBG_CIPHER)
1909     {
1910       log_debug ("ECC encrypt.\n");
1911     }
1912   pk.E.p_ = pkey[0];
1913   pk.E.a_ = pkey[1];
1914   pk.E.b_ = pkey[2];
1915   pk.E.G.x_ = pkey[3];
1916   pk.E.G.y_ = pkey[4];
1917   pk.E.G.z_ = pkey[5];
1918   pk.E.n_ = pkey[6];
1919   pk.Q.x_ = pkey[7];
1920   pk.Q.y_ = pkey[8];
1921   pk.Q.z_ = pkey[9];
1922
1923   R.x_ = resarr[0] = mpi_alloc (mpi_get_nlimbs (pk.Q.x_));
1924   R.y_ = resarr[1] = mpi_alloc (mpi_get_nlimbs (pk.Q.y_));
1925   R.z_ = resarr[2] = mpi_alloc (mpi_get_nlimbs (pk.Q.z_));
1926   resarr[3] = mpi_alloc (mpi_get_nlimbs (pk.E.p_));
1927
1928   doEncrypt (data, &pk, &R, resarr[3]);
1929
1930   resarr[0] = mpi_copy (R.x_);
1931   resarr[1] = mpi_copy (R.y_);
1932   resarr[2] = mpi_copy (R.z_);
1933   return 0;
1934 }
1935
1936 int
1937 ecc_decrypt_FIXME (int algo, gcry_mpi_t * result, gcry_mpi_t * data, gcry_mpi_t * skey)
1938 {
1939   ECC_secret_key sk;
1940   point R;
1941
1942   if (algo != PUBKEY_ALGO_ECC && algo != PUBKEY_ALGO_ECC_E)
1943     return G10ERR_PUBKEY_ALGO;
1944   if (!data[0] || !data[1] || !data[2] || !data[3] || !skey[0] || !skey[1]
1945       || !skey[2] || !skey[3] || !skey[4] || !skey[5] || !skey[6] || !skey[7]
1946       || !skey[8] || !skey[9] || !skey[10])
1947     return G10ERR_BAD_MPI;
1948
1949   if (DBG_CIPHER)
1950     {
1951       log_debug ("ECC decrypt.\n");
1952     }
1953   R.x_ = data[0];
1954   R.y_ = data[1];
1955   R.z_ = data[2];
1956   sk.E.p_ = skey[0];
1957   sk.E.a_ = skey[1];
1958   sk.E.b_ = skey[2];
1959   sk.E.G.x_ = skey[3];
1960   sk.E.G.y_ = skey[4];
1961   sk.E.G.z_ = skey[5];
1962   sk.E.n_ = skey[6];
1963   sk.Q.x_ = skey[7];
1964   sk.Q.y_ = skey[8];
1965   sk.Q.z_ = skey[9];
1966   sk.d = skey[10];
1967
1968   *result = mpi_alloc_secure (mpi_get_nlimbs (sk.E.p_));
1969   *result = decrypt (*result, &sk, R, data[3]);
1970   return 0;
1971 }
1972 #endif /*0*/
1973
1974 static gcry_err_code_t
1975 ecc_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
1976 {
1977   gpg_err_code_t err;
1978   ECC_secret_key sk;
1979
1980   (void)algo;
1981
1982   if (!data || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4]
1983       || !skey[5] || !skey[6] || !skey[7] || !skey[8] || !skey[9]
1984       || !skey[10])
1985     return GPG_ERR_BAD_MPI;
1986
1987   sk.E.p_ = skey[0];
1988   sk.E.a_ = skey[1];
1989   sk.E.b_ = skey[2];
1990   sk.E.G.x_ = skey[3];
1991   sk.E.G.y_ = skey[4];
1992   sk.E.G.z_ = skey[5];
1993   sk.E.n_ = skey[6];
1994   sk.Q.x_ = skey[7];
1995   sk.Q.y_ = skey[8];
1996   sk.Q.z_ = skey[9];
1997   sk.d = skey[10];
1998
1999   resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.E.p_));
2000   resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.E.p_));
2001   err = sign (data, &sk, resarr[0], resarr[1]);
2002   if (err)
2003     {
2004       mpi_free (resarr[0]);
2005       mpi_free (resarr[1]);
2006       resarr[0] = NULL; /* Mark array as released.  */
2007     }
2008   return err;
2009 }
2010
2011 static gcry_err_code_t
2012 ecc_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
2013             int (*cmp)(void *, gcry_mpi_t), void *opaquev)
2014 {
2015   ECC_public_key pk;
2016
2017   (void)algo;
2018
2019   if (!data[0] || !data[1] || !hash || !pkey[0] || !pkey[1] || !pkey[2]
2020       || !pkey[3] || !pkey[4] || !pkey[5] || !pkey[6] || !pkey[7] || !pkey[8]
2021       || !pkey[9])
2022     return GPG_ERR_BAD_MPI;
2023
2024   if (DBG_CIPHER)
2025     log_debug ("ECC verify.\n");
2026   pk.E.p_ = pkey[0];
2027   pk.E.a_ = pkey[1];
2028   pk.E.b_ = pkey[2];
2029   pk.E.G.x_ = pkey[3];
2030   pk.E.G.y_ = pkey[4];
2031   pk.E.G.z_ = pkey[5];
2032   pk.E.n_ = pkey[6];
2033   pk.Q.x_ = pkey[7];
2034   pk.Q.y_ = pkey[8];
2035   pk.Q.z_ = pkey[9];
2036
2037   return verify (hash, &pk, data[0], data[1]);
2038 }
2039
2040
2041
2042 static unsigned int
2043 ecc_get_nbits (int algo, gcry_mpi_t *pkey)
2044 {
2045   (void)algo;
2046
2047   if (DBG_CIPHER)
2048     {
2049       log_debug ("ECC get nbits.\n");
2050     }
2051
2052   if (DBG_CIPHER)
2053     {
2054       progress ('\n');
2055
2056       log_mpidump ("[ecc]  p= ", pkey[0]);
2057       log_mpidump ("[ecc]  a= ", pkey[1]);
2058       log_mpidump ("[ecc]  b= ", pkey[2]);
2059       log_mpidump ("[ecc]  Gx= ", pkey[3]);
2060       log_mpidump ("[ecc]  Gy= ", pkey[4]);
2061       log_mpidump ("[ecc]  Gz= ", pkey[5]);
2062       log_mpidump ("[ecc]  n= ", pkey[6]);
2063       log_mpidump ("[ecc]  Qx= ", pkey[7]);
2064       log_mpidump ("[ecc]  Qy= ", pkey[8]);
2065       log_mpidump ("[ecc]  Qz= ", pkey[9]);
2066     }
2067
2068   return mpi_get_nbits (pkey[0]);
2069 }
2070
2071
2072 static const char *ecdsa_names[] =
2073   {
2074     "ecdsa",
2075     NULL,
2076   };
2077
2078 gcry_pk_spec_t _gcry_pubkey_spec_ecdsa =
2079   {
2080     "ECDSA", ecdsa_names, 
2081     "pabxyznXYZ", "pabxyznXYZd", "", "rs", "pabxyznXYZ",
2082     GCRY_PK_USAGE_SIGN,
2083     ecc_generate,
2084     ecc_check_secret_key,
2085     NULL,
2086     NULL,
2087     ecc_sign,
2088     ecc_verify,
2089     ecc_get_nbits
2090   };
2091
2092
2093