Line data Source code
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 63 : _gcry_ecc_curve_free (elliptic_curve_t *E)
40 : {
41 63 : mpi_free (E->p); E->p = NULL;
42 63 : mpi_free (E->a); E->a = NULL;
43 63 : mpi_free (E->b); E->b = NULL;
44 63 : _gcry_mpi_point_free_parts (&E->G);
45 63 : mpi_free (E->n); E->n = NULL;
46 63 : mpi_free (E->h); E->h = NULL;
47 63 : }
48 :
49 :
50 : /*
51 : * Return a copy of a curve object.
52 : */
53 : elliptic_curve_t
54 15 : _gcry_ecc_curve_copy (elliptic_curve_t E)
55 : {
56 : elliptic_curve_t R;
57 :
58 15 : R.model = E.model;
59 15 : R.dialect = E.dialect;
60 15 : R.name = E.name;
61 15 : R.p = mpi_copy (E.p);
62 15 : R.a = mpi_copy (E.a);
63 15 : R.b = mpi_copy (E.b);
64 15 : _gcry_mpi_point_init (&R.G);
65 15 : point_set (&R.G, &E.G);
66 15 : R.n = mpi_copy (E.n);
67 15 : R.h = mpi_copy (E.h);
68 :
69 15 : return R;
70 : }
71 :
72 :
73 : /*
74 : * Return a description of the curve model.
75 : */
76 : const char *
77 0 : _gcry_ecc_model2str (enum gcry_mpi_ec_models model)
78 : {
79 0 : const char *str = "?";
80 0 : switch (model)
81 : {
82 0 : case MPI_EC_WEIERSTRASS: str = "Weierstrass"; break;
83 0 : case MPI_EC_MONTGOMERY: str = "Montgomery"; break;
84 0 : case MPI_EC_EDWARDS: str = "Edwards"; break;
85 : }
86 0 : return str;
87 : }
88 :
89 :
90 : /*
91 : * Return a description of the curve dialect.
92 : */
93 : const char *
94 0 : _gcry_ecc_dialect2str (enum ecc_dialects dialect)
95 : {
96 0 : const char *str = "?";
97 0 : switch (dialect)
98 : {
99 0 : case ECC_DIALECT_STANDARD: str = "Standard"; break;
100 0 : case ECC_DIALECT_ED25519: str = "Ed25519"; break;
101 : }
102 0 : return str;
103 : }
104 :
105 :
106 : gcry_mpi_t
107 51 : _gcry_ecc_ec2os (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t p)
108 : {
109 : gpg_err_code_t rc;
110 51 : int pbytes = (mpi_get_nbits (p)+7)/8;
111 : size_t n;
112 : unsigned char *buf, *ptr;
113 : gcry_mpi_t result;
114 :
115 51 : buf = xmalloc ( 1 + 2*pbytes );
116 51 : *buf = 04; /* Uncompressed point. */
117 51 : ptr = buf+1;
118 51 : rc = _gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, x);
119 51 : if (rc)
120 0 : log_fatal ("mpi_print failed: %s\n", gpg_strerror (rc));
121 51 : if (n < pbytes)
122 : {
123 4 : memmove (ptr+(pbytes-n), ptr, n);
124 4 : memset (ptr, 0, (pbytes-n));
125 : }
126 51 : ptr += pbytes;
127 51 : rc = _gcry_mpi_print (GCRYMPI_FMT_USG, ptr, pbytes, &n, y);
128 51 : if (rc)
129 0 : log_fatal ("mpi_print failed: %s\n", gpg_strerror (rc));
130 51 : if (n < pbytes)
131 : {
132 2 : memmove (ptr+(pbytes-n), ptr, n);
133 2 : memset (ptr, 0, (pbytes-n));
134 : }
135 :
136 51 : rc = _gcry_mpi_scan (&result, GCRYMPI_FMT_USG, buf, 1+2*pbytes, NULL);
137 51 : if (rc)
138 0 : log_fatal ("mpi_scan failed: %s\n", gpg_strerror (rc));
139 51 : xfree (buf);
140 :
141 51 : 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 18 : _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 18 : g_x = mpi_new (0);
154 18 : g_y = mpi_new (0);
155 18 : if (_gcry_mpi_ec_get_affine (g_x, g_y, point, ectx))
156 0 : result = NULL;
157 : else
158 18 : result = _gcry_ecc_ec2os (g_x, g_y, ectx->p);
159 18 : mpi_free (g_x);
160 18 : mpi_free (g_y);
161 :
162 18 : 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 206 : _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 206 : if (mpi_is_opaque (value))
178 193 : {
179 : unsigned int nbits;
180 :
181 193 : buf = mpi_get_opaque (value, &nbits);
182 193 : if (!buf)
183 0 : return GPG_ERR_INV_OBJ;
184 193 : n = (nbits + 7)/8;
185 193 : buf_memory = NULL;
186 : }
187 : else
188 : {
189 13 : n = (mpi_get_nbits (value)+7)/8;
190 13 : buf_memory = xmalloc (n);
191 13 : rc = _gcry_mpi_print (GCRYMPI_FMT_USG, buf_memory, n, &n, value);
192 13 : if (rc)
193 : {
194 0 : xfree (buf_memory);
195 0 : return rc;
196 : }
197 13 : buf = buf_memory;
198 : }
199 :
200 206 : if (n < 1)
201 : {
202 0 : xfree (buf_memory);
203 0 : return GPG_ERR_INV_OBJ;
204 : }
205 206 : if (*buf != 4)
206 : {
207 0 : xfree (buf_memory);
208 0 : return GPG_ERR_NOT_IMPLEMENTED; /* No support for point compression. */
209 : }
210 206 : if ( ((n-1)%2) )
211 : {
212 0 : xfree (buf_memory);
213 0 : return GPG_ERR_INV_OBJ;
214 : }
215 206 : n = (n-1)/2;
216 206 : rc = _gcry_mpi_scan (&x, GCRYMPI_FMT_USG, buf+1, n, NULL);
217 206 : if (rc)
218 : {
219 0 : xfree (buf_memory);
220 0 : return rc;
221 : }
222 206 : rc = _gcry_mpi_scan (&y, GCRYMPI_FMT_USG, buf+1+n, n, NULL);
223 206 : xfree (buf_memory);
224 206 : if (rc)
225 : {
226 0 : mpi_free (x);
227 0 : return rc;
228 : }
229 :
230 206 : mpi_set (result->x, x);
231 206 : mpi_set (result->y, y);
232 206 : mpi_set_ui (result->z, 1);
233 :
234 206 : mpi_free (x);
235 206 : mpi_free (y);
236 :
237 206 : 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 24 : _gcry_ecc_compute_public (mpi_point_t Q, mpi_ec_t ec,
248 : mpi_point_t G, gcry_mpi_t d)
249 : {
250 24 : if (!G)
251 4 : G = ec->G;
252 24 : if (!d)
253 4 : d = ec->d;
254 :
255 24 : if (!d || !G || !ec->p || !ec->a)
256 2 : return NULL;
257 22 : if (ec->model == MPI_EC_EDWARDS && !ec->b)
258 0 : return NULL;
259 :
260 22 : if (ec->dialect == ECC_DIALECT_ED25519
261 9 : && (ec->flags & PUBKEY_FLAG_EDDSA))
262 3 : {
263 : gcry_mpi_t a;
264 : unsigned char *digest;
265 :
266 3 : if (_gcry_ecc_eddsa_compute_h_d (&digest, d, ec))
267 0 : return NULL;
268 :
269 3 : a = mpi_snew (0);
270 3 : _gcry_mpi_set_buffer (a, digest, 32, 0);
271 3 : xfree (digest);
272 :
273 : /* And finally the public key. */
274 3 : if (!Q)
275 1 : Q = mpi_point_new (0);
276 3 : if (Q)
277 3 : _gcry_mpi_ec_mul_point (Q, a, G, ec);
278 3 : mpi_free (a);
279 : }
280 : else
281 : {
282 19 : if (!Q)
283 1 : Q = mpi_point_new (0);
284 19 : if (Q)
285 19 : _gcry_mpi_ec_mul_point (Q, d, G, ec);
286 : }
287 :
288 22 : return Q;
289 : }
290 :
291 :
292 : gpg_err_code_t
293 19 : _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 19 : if (mpi_is_opaque (pk))
299 19 : {
300 : const unsigned char *buf;
301 : unsigned char *p;
302 :
303 19 : buf = mpi_get_opaque (pk, &rawmpilen);
304 19 : if (!buf)
305 0 : return GPG_ERR_INV_OBJ;
306 19 : rawmpilen = (rawmpilen + 7)/8;
307 :
308 19 : if (rawmpilen > 1 && (rawmpilen%2) && buf[0] == 0x40)
309 : {
310 0 : rawmpilen--;
311 0 : buf++;
312 : }
313 :
314 19 : rawmpi = xtrymalloc (rawmpilen? rawmpilen:1);
315 19 : if (!rawmpi)
316 0 : return gpg_err_code_from_syserror ();
317 :
318 19 : p = rawmpi + rawmpilen;
319 646 : while (p > rawmpi)
320 608 : *--p = *buf++;
321 : }
322 : else
323 : {
324 0 : unsigned int nbytes = (ctx->nbits+7)/8;
325 :
326 0 : rawmpi = _gcry_mpi_get_buffer (pk, nbytes, &rawmpilen, NULL);
327 0 : if (!rawmpi)
328 0 : 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 0 : 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 0 : unsigned int len = pk->nlimbs * BYTES_PER_MPI_LIMB;
349 :
350 0 : memmove (rawmpi + nbytes - len, rawmpi, len);
351 0 : 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 0 : rawmpilen = nbytes;
361 : }
362 :
363 19 : rawmpi[0] &= (1 << (ctx->nbits % 8)) - 1;
364 19 : _gcry_mpi_set_buffer (result->x, rawmpi, rawmpilen, 0);
365 19 : xfree (rawmpi);
366 19 : mpi_set_ui (result->z, 1);
367 :
368 19 : return 0;
369 : }
|
