ecc: Fix Curve25519 for data by older implementation.
[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       unsigned int nbytes = (ctx->nbits+7)/8;
325
326       rawmpi = _gcry_mpi_get_buffer (pk, nbytes, &rawmpilen, NULL);
327       if (!rawmpi)
328         return gpg_err_code_from_syserror ();
329       /*
330        * It is not reliable to assume that 0x40 means the prefix.
331        *
332        * For newer implementation, it is reliable since we always put
333        * 0x40 for x-only coordinate.
334        *
335        * For data with older implementation (non-released development
336        * version), it is possibe to have the 0x40 as a part of data.
337        * Besides, when data was parsed as MPI, we might have 0x00
338        * prefix.
339        *
340        * So, we need to check if it's really the prefix or not.
341        * Only when it's the prefix, we remove it.
342        */
343       if (pk->nlimbs * BYTES_PER_MPI_LIMB < nbytes)
344         {/*
345           * It is possible for data created by older implementation
346           * to have shorter length when it was parsed as MPI.
347           */
348           unsigned int len = pk->nlimbs * BYTES_PER_MPI_LIMB;
349
350           memmove (rawmpi + nbytes - len, rawmpi, len);
351           memset (rawmpi, 0, nbytes - len);
352         }
353
354       /*
355        * When we have the prefix (0x40 or 0x00), it comes at the end,
356        * since it is taken by _gcry_mpi_get_buffer with little endian.
357        * Just setting RAWMPILEN to NBYTES is enough in this case.
358        * Othewise, RAWMPILEN is NBYTES already.
359        */
360       rawmpilen = nbytes;
361     }
362
363   rawmpi[0] &= (1 << (ctx->nbits % 8)) - 1;
364   _gcry_mpi_set_buffer (result->x, rawmpi, rawmpilen, 0);
365   xfree (rawmpi);
366   mpi_set_ui (result->z, 1);
367
368   return 0;
369 }