More optimized CRC implementations
[libgcrypt.git] / cipher / ecc-misc.c
1 /* ecc-misc.c  -  Elliptic Curve miscellaneous functions
2  * Copyright (C) 2007, 2008, 2010, 2011 Free Software Foundation, Inc.
3  * Copyright (C) 2013 g10 Code GmbH
4  *
5  * This file is part of Libgcrypt.
6  *
7  * Libgcrypt is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU Lesser General Public License as
9  * published by the Free Software Foundation; either version 2.1 of
10  * the License, or (at your option) any later version.
11  *
12  * Libgcrypt is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with this program; if not, see <http://www.gnu.org/licenses/>.
19  */
20
21 #include <config.h>
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include <errno.h>
26
27 #include "g10lib.h"
28 #include "mpi.h"
29 #include "cipher.h"
30 #include "context.h"
31 #include "ec-context.h"
32 #include "ecc-common.h"
33
34
35 /*
36  * Release a curve object.
37  */
38 void
39 _gcry_ecc_curve_free (elliptic_curve_t *E)
40 {
41   mpi_free (E->p); E->p = NULL;
42   mpi_free (E->a); E->a = NULL;
43   mpi_free (E->b);  E->b = NULL;
44   _gcry_mpi_point_free_parts (&E->G);
45   mpi_free (E->n);  E->n = NULL;
46   mpi_free (E->h);  E->h = NULL;
47 }
48
49
50 /*
51  * Return a copy of a curve object.
52  */
53 elliptic_curve_t
54 _gcry_ecc_curve_copy (elliptic_curve_t E)
55 {
56   elliptic_curve_t R;
57
58   R.model = E.model;
59   R.dialect = E.dialect;
60   R.name = E.name;
61   R.p = mpi_copy (E.p);
62   R.a = mpi_copy (E.a);
63   R.b = mpi_copy (E.b);
64   _gcry_mpi_point_init (&R.G);
65   point_set (&R.G, &E.G);
66   R.n = mpi_copy (E.n);
67   R.h = mpi_copy (E.h);
68
69   return R;
70 }
71
72
73 /*
74  * Return a description of the curve model.
75  */
76 const char *
77 _gcry_ecc_model2str (enum gcry_mpi_ec_models model)
78 {
79   const char *str = "?";
80   switch (model)
81     {
82     case MPI_EC_WEIERSTRASS:    str = "Weierstrass"; break;
83     case MPI_EC_MONTGOMERY:     str = "Montgomery";  break;
84     case MPI_EC_EDWARDS:        str = "Edwards"; break;
85     }
86   return str;
87 }
88
89
90 /*
91  * Return a description of the curve dialect.
92  */
93 const char *
94 _gcry_ecc_dialect2str (enum ecc_dialects dialect)
95 {
96   const char *str = "?";
97   switch (dialect)
98     {
99     case ECC_DIALECT_STANDARD:  str = "Standard"; break;
100     case ECC_DIALECT_ED25519:   str = "Ed25519"; break;
101     }
102   return str;
103 }
104
105
106 gcry_mpi_t
107 _gcry_ecc_ec2os (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t p)
108 {
109   gpg_err_code_t rc;
110   int pbytes = (mpi_get_nbits (p)+7)/8;
111   size_t n;
112   unsigned char *buf, *ptr;
113   gcry_mpi_t result;
114
115   buf = xmalloc ( 1 + 2*pbytes );
116   *buf = 04; /* Uncompressed point.  */
117   ptr = buf+1;
118   rc = _gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, x);
119   if (rc)
120     log_fatal ("mpi_print failed: %s\n", gpg_strerror (rc));
121   if (n < pbytes)
122     {
123       memmove (ptr+(pbytes-n), ptr, n);
124       memset (ptr, 0, (pbytes-n));
125     }
126   ptr += pbytes;
127   rc = _gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, y);
128   if (rc)
129     log_fatal ("mpi_print failed: %s\n", gpg_strerror (rc));
130   if (n < pbytes)
131     {
132       memmove (ptr+(pbytes-n), ptr, n);
133       memset (ptr, 0, (pbytes-n));
134     }
135
136   rc = _gcry_mpi_scan (&result, GCRYMPI_FMT_USG, buf, 1+2*pbytes, NULL);
137   if (rc)
138     log_fatal ("mpi_scan failed: %s\n", gpg_strerror (rc));
139   xfree (buf);
140
141   return result;
142 }
143
144
145 /* Convert POINT into affine coordinates using the context CTX and
146    return a newly allocated MPI.  If the conversion is not possible
147    NULL is returned.  This function won't print an error message.  */
148 gcry_mpi_t
149 _gcry_mpi_ec_ec2os (gcry_mpi_point_t point, mpi_ec_t ectx)
150 {
151   gcry_mpi_t g_x, g_y, result;
152
153   g_x = mpi_new (0);
154   g_y = mpi_new (0);
155   if (_gcry_mpi_ec_get_affine (g_x, g_y, point, ectx))
156     result = NULL;
157   else
158     result = _gcry_ecc_ec2os (g_x, g_y, ectx->p);
159   mpi_free (g_x);
160   mpi_free (g_y);
161
162   return result;
163 }
164
165
166 /* RESULT must have been initialized and is set on success to the
167    point given by VALUE.  */
168 gcry_err_code_t
169 _gcry_ecc_os2ec (mpi_point_t result, gcry_mpi_t value)
170 {
171   gcry_err_code_t rc;
172   size_t n;
173   const unsigned char *buf;
174   unsigned char *buf_memory;
175   gcry_mpi_t x, y;
176
177   if (mpi_is_opaque (value))
178     {
179       unsigned int nbits;
180
181       buf = mpi_get_opaque (value, &nbits);
182       if (!buf)
183         return GPG_ERR_INV_OBJ;
184       n = (nbits + 7)/8;
185       buf_memory = NULL;
186     }
187   else
188     {
189       n = (mpi_get_nbits (value)+7)/8;
190       buf_memory = xmalloc (n);
191       rc = _gcry_mpi_print (GCRYMPI_FMT_USG, buf_memory, n, &n, value);
192       if (rc)
193         {
194           xfree (buf_memory);
195           return rc;
196         }
197       buf = buf_memory;
198     }
199
200   if (n < 1)
201     {
202       xfree (buf_memory);
203       return GPG_ERR_INV_OBJ;
204     }
205   if (*buf != 4)
206     {
207       xfree (buf_memory);
208       return GPG_ERR_NOT_IMPLEMENTED; /* No support for point compression.  */
209     }
210   if ( ((n-1)%2) )
211     {
212       xfree (buf_memory);
213       return GPG_ERR_INV_OBJ;
214     }
215   n = (n-1)/2;
216   rc = _gcry_mpi_scan (&x, GCRYMPI_FMT_USG, buf+1, n, NULL);
217   if (rc)
218     {
219       xfree (buf_memory);
220       return rc;
221     }
222   rc = _gcry_mpi_scan (&y, GCRYMPI_FMT_USG, buf+1+n, n, NULL);
223   xfree (buf_memory);
224   if (rc)
225     {
226       mpi_free (x);
227       return rc;
228     }
229
230   mpi_set (result->x, x);
231   mpi_set (result->y, y);
232   mpi_set_ui (result->z, 1);
233
234   mpi_free (x);
235   mpi_free (y);
236
237   return 0;
238 }
239
240
241 /* Compute the public key from the the context EC.  Obviously a
242    requirement is that the secret key is available in EC.  On success
243    Q is returned; on error NULL.  If Q is NULL a newly allocated point
244    is returned.  If G or D are given they override the values taken
245    from EC. */
246 mpi_point_t
247 _gcry_ecc_compute_public (mpi_point_t Q, mpi_ec_t ec,
248                           mpi_point_t G, gcry_mpi_t d)
249 {
250   if (!G)
251     G = ec->G;
252   if (!d)
253     d = ec->d;
254
255   if (!d || !G || !ec->p || !ec->a)
256     return NULL;
257   if (ec->model == MPI_EC_EDWARDS && !ec->b)
258     return NULL;
259
260   if (ec->dialect == ECC_DIALECT_ED25519
261       && (ec->flags & PUBKEY_FLAG_EDDSA))
262     {
263       gcry_mpi_t a;
264       unsigned char *digest;
265
266       if (_gcry_ecc_eddsa_compute_h_d (&digest, d, ec))
267         return NULL;
268
269       a = mpi_snew (0);
270       _gcry_mpi_set_buffer (a, digest, 32, 0);
271       xfree (digest);
272
273       /* And finally the public key.  */
274       if (!Q)
275         Q = mpi_point_new (0);
276       if (Q)
277         _gcry_mpi_ec_mul_point (Q, a, G, ec);
278       mpi_free (a);
279     }
280   else
281     {
282       if (!Q)
283         Q = mpi_point_new (0);
284       if (Q)
285         _gcry_mpi_ec_mul_point (Q, d, G, ec);
286     }
287
288   return Q;
289 }