Add Curve25519 support.
[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 }
290
291
292 gpg_err_code_t
293 _gcry_ecc_mont_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result)
294 {
295   unsigned char *rawmpi;
296   unsigned int rawmpilen;
297
298   if (mpi_is_opaque (pk))
299     {
300       const unsigned char *buf;
301       unsigned char *p;
302
303       buf = mpi_get_opaque (pk, &rawmpilen);
304       if (!buf)
305         return GPG_ERR_INV_OBJ;
306       rawmpilen = (rawmpilen + 7)/8;
307
308       if (rawmpilen > 1 && (rawmpilen%2) && buf[0] == 0x40)
309         {
310           rawmpilen--;
311           buf++;
312         }
313
314       rawmpi = xtrymalloc (rawmpilen? rawmpilen:1);
315       if (!rawmpi)
316         return gpg_err_code_from_syserror ();
317
318       p = rawmpi + rawmpilen;
319       while (p > rawmpi)
320         *--p = *buf++;
321     }
322   else
323     {
324       /* Note: Without using an opaque MPI it is not reliable possible
325          to find out whether the public key has been given in
326          uncompressed format.  Thus we expect native EdDSA format.  */
327       rawmpi = _gcry_mpi_get_buffer (pk, ctx->nbits/8, &rawmpilen, NULL);
328       if (!rawmpi)
329         return gpg_err_code_from_syserror ();
330     }
331
332   _gcry_mpi_set_buffer (result->x, rawmpi, rawmpilen, 0);
333   xfree (rawmpi);
334   mpi_set_ui (result->z, 1);
335
336   return 0;
337 }