ecc: Fully implement Ed25519 compression in ECDSA mode.
[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 }
47
48
49 /*
50  * Return a copy of a curve object.
51  */
52 elliptic_curve_t
53 _gcry_ecc_curve_copy (elliptic_curve_t E)
54 {
55   elliptic_curve_t R;
56
57   R.model = E.model;
58   R.dialect = E.dialect;
59   R.name = E.name;
60   R.p = mpi_copy (E.p);
61   R.a = mpi_copy (E.a);
62   R.b = mpi_copy (E.b);
63   _gcry_mpi_point_init (&R.G);
64   point_set (&R.G, &E.G);
65   R.n = mpi_copy (E.n);
66
67   return R;
68 }
69
70
71 /*
72  * Return a description of the curve model.
73  */
74 const char *
75 _gcry_ecc_model2str (enum gcry_mpi_ec_models model)
76 {
77   const char *str = "?";
78   switch (model)
79     {
80     case MPI_EC_WEIERSTRASS:    str = "Weierstrass"; break;
81     case MPI_EC_MONTGOMERY:     str = "Montgomery";  break;
82     case MPI_EC_TWISTEDEDWARDS: str = "Twisted Edwards"; break;
83     }
84   return str;
85 }
86
87
88 /*
89  * Return a description of the curve dialect.
90  */
91 const char *
92 _gcry_ecc_dialect2str (enum ecc_dialects dialect)
93 {
94   const char *str = "?";
95   switch (dialect)
96     {
97     case ECC_DIALECT_STANDARD:  str = "Standard"; break;
98     case ECC_DIALECT_ED25519:   str = "Ed25519"; break;
99     }
100   return str;
101 }
102
103
104 gcry_mpi_t
105 _gcry_ecc_ec2os (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t p)
106 {
107   gpg_error_t err;
108   int pbytes = (mpi_get_nbits (p)+7)/8;
109   size_t n;
110   unsigned char *buf, *ptr;
111   gcry_mpi_t result;
112
113   buf = gcry_xmalloc ( 1 + 2*pbytes );
114   *buf = 04; /* Uncompressed point.  */
115   ptr = buf+1;
116   err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, x);
117   if (err)
118     log_fatal ("mpi_print failed: %s\n", gpg_strerror (err));
119   if (n < pbytes)
120     {
121       memmove (ptr+(pbytes-n), ptr, n);
122       memset (ptr, 0, (pbytes-n));
123     }
124   ptr += pbytes;
125   err = gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, y);
126   if (err)
127     log_fatal ("mpi_print failed: %s\n", gpg_strerror (err));
128   if (n < pbytes)
129     {
130       memmove (ptr+(pbytes-n), ptr, n);
131       memset (ptr, 0, (pbytes-n));
132     }
133
134   err = gcry_mpi_scan (&result, GCRYMPI_FMT_USG, buf, 1+2*pbytes, NULL);
135   if (err)
136     log_fatal ("mpi_scan failed: %s\n", gpg_strerror (err));
137   gcry_free (buf);
138
139   return result;
140 }
141
142
143 /* Convert POINT into affine coordinates using the context CTX and
144    return a newly allocated MPI.  If the conversion is not possible
145    NULL is returned.  This function won't print an error message.  */
146 gcry_mpi_t
147 _gcry_mpi_ec_ec2os (gcry_mpi_point_t point, mpi_ec_t ectx)
148 {
149   gcry_mpi_t g_x, g_y, result;
150
151   g_x = mpi_new (0);
152   g_y = mpi_new (0);
153   if (_gcry_mpi_ec_get_affine (g_x, g_y, point, ectx))
154     result = NULL;
155   else
156     result = _gcry_ecc_ec2os (g_x, g_y, ectx->p);
157   mpi_free (g_x);
158   mpi_free (g_y);
159
160   return result;
161 }
162
163
164 /* RESULT must have been initialized and is set on success to the
165    point given by VALUE.  */
166 gcry_error_t
167 _gcry_ecc_os2ec (mpi_point_t result, gcry_mpi_t value)
168 {
169   gcry_error_t err;
170   size_t n;
171   const unsigned char *buf;
172   unsigned char *buf_memory;
173   gcry_mpi_t x, y;
174
175   if (mpi_is_opaque (value))
176     {
177       unsigned int nbits;
178
179       buf = gcry_mpi_get_opaque (value, &nbits);
180       if (!buf)
181         return GPG_ERR_INV_OBJ;
182       n = (nbits + 7)/8;
183       buf_memory = NULL;
184     }
185   else
186     {
187       n = (mpi_get_nbits (value)+7)/8;
188       buf_memory= gcry_xmalloc (n);
189       err = gcry_mpi_print (GCRYMPI_FMT_USG, buf_memory, n, &n, value);
190       if (err)
191         {
192           gcry_free (buf_memory);
193           return err;
194         }
195       buf = buf_memory;
196     }
197
198   if (n < 1)
199     {
200       gcry_free (buf_memory);
201       return GPG_ERR_INV_OBJ;
202     }
203   if (*buf != 4)
204     {
205       gcry_free (buf_memory);
206       return GPG_ERR_NOT_IMPLEMENTED; /* No support for point compression.  */
207     }
208   if ( ((n-1)%2) )
209     {
210       gcry_free (buf_memory);
211       return GPG_ERR_INV_OBJ;
212     }
213   n = (n-1)/2;
214   err = gcry_mpi_scan (&x, GCRYMPI_FMT_USG, buf+1, n, NULL);
215   if (err)
216     {
217       gcry_free (buf_memory);
218       return err;
219     }
220   err = gcry_mpi_scan (&y, GCRYMPI_FMT_USG, buf+1+n, n, NULL);
221   gcry_free (buf_memory);
222   if (err)
223     {
224       mpi_free (x);
225       return err;
226     }
227
228   mpi_set (result->x, x);
229   mpi_set (result->y, y);
230   mpi_set_ui (result->z, 1);
231
232   mpi_free (x);
233   mpi_free (y);
234
235   return 0;
236 }
237
238
239 static void
240 reverse_buffer (unsigned char *buffer, unsigned int length)
241 {
242   unsigned int tmp, i;
243
244   for (i=0; i < length/2; i++)
245     {
246       tmp = buffer[i];
247       buffer[i] = buffer[length-1-i];
248       buffer[length-1-i] = tmp;
249     }
250 }
251
252
253 /* Compute the public key from the the context EC.  Obviously a
254    requirement is that the secret key is available in EC.  On success
255    Q is returned; on error NULL.  If Q is NULL a newly allocated point
256    is returned.  */
257 mpi_point_t
258 _gcry_ecc_compute_public (mpi_point_t Q, mpi_ec_t ec)
259 {
260   int rc;
261
262   if (!ec->d || !ec->G || !ec->p || !ec->a)
263     return NULL;
264   if (ec->model == MPI_EC_TWISTEDEDWARDS && !ec->b)
265     return NULL;
266
267   if (ec->dialect == ECC_DIALECT_ED25519
268       && !(ec->flags & PUBKEY_FLAG_ECDSA))
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   else
318     {
319       if (!Q)
320         Q = gcry_mpi_point_new (0);
321       if (Q)
322         _gcry_mpi_ec_mul_point (Q, ec->d, ec->G, ec);
323     }
324
325   return Q;
326 }