sexp: Add function gcry_sexp_extract_param.
[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 "context.h"
30 #include "ec-context.h"
31 #include "ecc-common.h"
32
33
34 /*
35  * Release a curve object.
36  */
37 void
38 _gcry_ecc_curve_free (elliptic_curve_t *E)
39 {
40   mpi_free (E->p); E->p = NULL;
41   mpi_free (E->a); E->a = NULL;
42   mpi_free (E->b);  E->b = NULL;
43   _gcry_mpi_point_free_parts (&E->G);
44   mpi_free (E->n);  E->n = NULL;
45 }
46
47
48 /*
49  * Return a copy of a curve object.
50  */
51 elliptic_curve_t
52 _gcry_ecc_curve_copy (elliptic_curve_t E)
53 {
54   elliptic_curve_t R;
55
56   R.model = E.model;
57   R.dialect = E.dialect;
58   R.name = E.name;
59   R.p = mpi_copy (E.p);
60   R.a = mpi_copy (E.a);
61   R.b = mpi_copy (E.b);
62   _gcry_mpi_point_init (&R.G);
63   point_set (&R.G, &E.G);
64   R.n = mpi_copy (E.n);
65
66   return R;
67 }
68
69
70 /*
71  * Return a description of the curve model.
72  */
73 const char *
74 _gcry_ecc_model2str (enum gcry_mpi_ec_models model)
75 {
76   const char *str = "?";
77   switch (model)
78     {
79     case MPI_EC_WEIERSTRASS:    str = "Weierstrass"; break;
80     case MPI_EC_MONTGOMERY:     str = "Montgomery";  break;
81     case MPI_EC_TWISTEDEDWARDS: str = "Twisted Edwards"; break;
82     }
83   return str;
84 }
85
86
87 /*
88  * Return a description of the curve dialect.
89  */
90 const char *
91 _gcry_ecc_dialect2str (enum ecc_dialects dialect)
92 {
93   const char *str = "?";
94   switch (dialect)
95     {
96     case ECC_DIALECT_STANDARD:  str = "Standard"; break;
97     case ECC_DIALECT_ED25519:   str = "Ed25519"; break;
98     }
99   return str;
100 }
101
102
103 gcry_mpi_t
104 _gcry_ecc_ec2os (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t p)
105 {
106   gpg_error_t err;
107   int pbytes = (mpi_get_nbits (p)+7)/8;
108   size_t n;
109   unsigned char *buf, *ptr;
110   gcry_mpi_t result;
111
112   buf = gcry_xmalloc ( 1 + 2*pbytes );
113   *buf = 04; /* Uncompressed point.  */
114   ptr = buf+1;
115   err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, x);
116   if (err)
117     log_fatal ("mpi_print failed: %s\n", gpg_strerror (err));
118   if (n < pbytes)
119     {
120       memmove (ptr+(pbytes-n), ptr, n);
121       memset (ptr, 0, (pbytes-n));
122     }
123   ptr += pbytes;
124   err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, y);
125   if (err)
126     log_fatal ("mpi_print failed: %s\n", gpg_strerror (err));
127   if (n < pbytes)
128     {
129       memmove (ptr+(pbytes-n), ptr, n);
130       memset (ptr, 0, (pbytes-n));
131     }
132
133   err = gcry_mpi_scan (&result, GCRYMPI_FMT_USG, buf, 1+2*pbytes, NULL);
134   if (err)
135     log_fatal ("mpi_scan failed: %s\n", gpg_strerror (err));
136   gcry_free (buf);
137
138   return result;
139 }
140
141
142 /* Convert POINT into affine coordinates using the context CTX and
143    return a newly allocated MPI.  If the conversion is not possible
144    NULL is returned.  This function won't print an error message.  */
145 gcry_mpi_t
146 _gcry_mpi_ec_ec2os (gcry_mpi_point_t point, mpi_ec_t ectx)
147 {
148   gcry_mpi_t g_x, g_y, result;
149
150   g_x = mpi_new (0);
151   g_y = mpi_new (0);
152   if (_gcry_mpi_ec_get_affine (g_x, g_y, point, ectx))
153     result = NULL;
154   else
155     result = _gcry_ecc_ec2os (g_x, g_y, ectx->p);
156   mpi_free (g_x);
157   mpi_free (g_y);
158
159   return result;
160 }
161
162
163 /* RESULT must have been initialized and is set on success to the
164    point given by VALUE.  */
165 gcry_error_t
166 _gcry_ecc_os2ec (mpi_point_t result, gcry_mpi_t value)
167 {
168   gcry_error_t err;
169   size_t n;
170   const unsigned char *buf;
171   unsigned char *buf_memory;
172   gcry_mpi_t x, y;
173
174   if (mpi_is_opaque (value))
175     {
176       unsigned int nbits;
177
178       buf = gcry_mpi_get_opaque (value, &nbits);
179       if (!buf)
180         return GPG_ERR_INV_OBJ;
181       n = (nbits + 7)/8;
182       buf_memory = NULL;
183     }
184   else
185     {
186       n = (mpi_get_nbits (value)+7)/8;
187       buf_memory= gcry_xmalloc (n);
188       err = gcry_mpi_print (GCRYMPI_FMT_USG, buf_memory, n, &n, value);
189       if (err)
190         {
191           gcry_free (buf_memory);
192           return err;
193         }
194       buf = buf_memory;
195     }
196
197   if (n < 1)
198     {
199       gcry_free (buf_memory);
200       return GPG_ERR_INV_OBJ;
201     }
202   if (*buf != 4)
203     {
204       gcry_free (buf_memory);
205       return GPG_ERR_NOT_IMPLEMENTED; /* No support for point compression.  */
206     }
207   if ( ((n-1)%2) )
208     {
209       gcry_free (buf_memory);
210       return GPG_ERR_INV_OBJ;
211     }
212   n = (n-1)/2;
213   err = gcry_mpi_scan (&x, GCRYMPI_FMT_USG, buf+1, n, NULL);
214   if (err)
215     {
216       gcry_free (buf_memory);
217       return err;
218     }
219   err = gcry_mpi_scan (&y, GCRYMPI_FMT_USG, buf+1+n, n, NULL);
220   gcry_free (buf_memory);
221   if (err)
222     {
223       mpi_free (x);
224       return err;
225     }
226
227   mpi_set (result->x, x);
228   mpi_set (result->y, y);
229   mpi_set_ui (result->z, 1);
230
231   mpi_free (x);
232   mpi_free (y);
233
234   return 0;
235 }
236
237
238 static void
239 reverse_buffer (unsigned char *buffer, unsigned int length)
240 {
241   unsigned int tmp, i;
242
243   for (i=0; i < length/2; i++)
244     {
245       tmp = buffer[i];
246       buffer[i] = buffer[length-1-i];
247       buffer[length-1-i] = tmp;
248     }
249 }
250
251
252 /* Compute the public key from the the context EC.  Obviously a
253    requirement is that the secret key is available in EC.  On success
254    Q is returned; on error NULL.  If Q is NULL a newly allocated point
255    is returned.  */
256 mpi_point_t
257 _gcry_ecc_compute_public (mpi_point_t Q, mpi_ec_t ec)
258 {
259   int rc;
260
261   if (!ec->d || !ec->G || !ec->p || !ec->a)
262     return NULL;
263   if (ec->model == MPI_EC_TWISTEDEDWARDS && !ec->b)
264     return NULL;
265
266   switch (ec->dialect)
267     {
268     case ECC_DIALECT_ED25519:
269       {
270         gcry_mpi_t a;
271         unsigned char *rawmpi = NULL;
272         unsigned int rawmpilen;
273         unsigned char *digest;
274         gcry_buffer_t hvec[2];
275         int b = (ec->nbits+7)/8;
276
277         gcry_assert (b >= 32);
278         digest = gcry_calloc_secure (2, b);
279         if (!digest)
280           return NULL;
281         memset (hvec, 0, sizeof hvec);
282
283         rawmpi = _gcry_mpi_get_buffer (ec->d, 0, &rawmpilen, NULL);
284         if (!rawmpi)
285           return NULL;
286         memset (digest, 0, b);
287         hvec[0].data = digest;
288         hvec[0].off = 0;
289         hvec[0].len = b > rawmpilen? b - rawmpilen : 0;
290         hvec[1].data = rawmpi;
291         hvec[1].off = 0;
292         hvec[1].len = rawmpilen;
293         /* FIXME: Put and take the hash algo from the context.  */
294         rc = _gcry_md_hash_buffers (GCRY_MD_SHA512, 0, digest, hvec, 2);
295         gcry_free (rawmpi);
296         if (rc)
297           {
298             gcry_free (digest);
299             return NULL;
300           }
301
302         /* Compute the A value.  */
303         reverse_buffer (digest, 32);  /* Only the first half of the hash.  */
304         digest[0] = (digest[0] & 0x7f) | 0x40;
305         digest[31] &= 0xf8;
306         a = mpi_snew (0);
307         _gcry_mpi_set_buffer (a, digest, 32, 0);
308         gcry_free (digest);
309
310         /* And finally the public key.  */
311         if (!Q)
312           Q = gcry_mpi_point_new (0);
313         if (Q)
314           _gcry_mpi_ec_mul_point (Q, a, ec->G, ec);
315         mpi_free (a);
316       }
317       break;
318
319     default:
320       {
321         if (!Q)
322           Q = gcry_mpi_point_new (0);
323         if (Q)
324           _gcry_mpi_ec_mul_point (Q, ec->d, ec->G, ec);
325       }
326       break;
327     }
328
329   return Q;
330 }