Line data Source code
1 : /* ecc-eddsa.c - Elliptic Curve EdDSA signatures
2 : * Copyright (C) 2013, 2014 g10 Code GmbH
3 : *
4 : * This file is part of Libgcrypt.
5 : *
6 : * Libgcrypt is free software; you can redistribute it and/or modify
7 : * it under the terms of the GNU Lesser General Public License as
8 : * published by the Free Software Foundation; either version 2.1 of
9 : * the License, or (at your option) any later version.
10 : *
11 : * Libgcrypt is distributed in the hope that it will be useful,
12 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : * GNU Lesser General Public License for more details.
15 : *
16 : * You should have received a copy of the GNU Lesser General Public
17 : * License along with this program; if not, see <http://www.gnu.org/licenses/>.
18 : */
19 :
20 : #include <config.h>
21 : #include <stdio.h>
22 : #include <stdlib.h>
23 : #include <string.h>
24 : #include <errno.h>
25 :
26 : #include "g10lib.h"
27 : #include "mpi.h"
28 : #include "cipher.h"
29 : #include "context.h"
30 : #include "ec-context.h"
31 : #include "ecc-common.h"
32 :
33 :
34 :
35 : static void
36 7285 : reverse_buffer (unsigned char *buffer, unsigned int length)
37 : {
38 : unsigned int tmp, i;
39 :
40 173573 : for (i=0; i < length/2; i++)
41 : {
42 166288 : tmp = buffer[i];
43 166288 : buffer[i] = buffer[length-1-i];
44 166288 : buffer[length-1-i] = tmp;
45 : }
46 7285 : }
47 :
48 :
49 : /* Helper to scan a hex string. */
50 : static gcry_mpi_t
51 7 : scanval (const char *string)
52 : {
53 : gpg_err_code_t rc;
54 : gcry_mpi_t val;
55 :
56 7 : rc = _gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL);
57 7 : if (rc)
58 0 : log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (rc));
59 7 : return val;
60 : }
61 :
62 :
63 :
64 : /* Encode MPI using the EdDSA scheme. MINLEN specifies the required
65 : length of the buffer in bytes. On success 0 is returned an a
66 : malloced buffer with the encoded point is stored at R_BUFFER; the
67 : length of this buffer is stored at R_BUFLEN. */
68 : static gpg_err_code_t
69 1036 : eddsa_encodempi (gcry_mpi_t mpi, unsigned int minlen,
70 : unsigned char **r_buffer, unsigned int *r_buflen)
71 : {
72 : unsigned char *rawmpi;
73 : unsigned int rawmpilen;
74 :
75 1036 : rawmpi = _gcry_mpi_get_buffer (mpi, minlen, &rawmpilen, NULL);
76 1036 : if (!rawmpi)
77 0 : return gpg_err_code_from_syserror ();
78 :
79 1036 : *r_buffer = rawmpi;
80 1036 : *r_buflen = rawmpilen;
81 1036 : return 0;
82 : }
83 :
84 :
85 : /* Encode (X,Y) using the EdDSA scheme. MINLEN is the required length
86 : in bytes for the result. If WITH_PREFIX is set the returned buffer
87 : is prefixed with a 0x40 byte. On success 0 is returned and a
88 : malloced buffer with the encoded point is stored at R_BUFFER; the
89 : length of this buffer is stored at R_BUFLEN. */
90 : static gpg_err_code_t
91 3108 : eddsa_encode_x_y (gcry_mpi_t x, gcry_mpi_t y, unsigned int minlen,
92 : int with_prefix,
93 : unsigned char **r_buffer, unsigned int *r_buflen)
94 : {
95 : unsigned char *rawmpi;
96 : unsigned int rawmpilen;
97 3108 : int off = with_prefix? 1:0;
98 :
99 3108 : rawmpi = _gcry_mpi_get_buffer_extra (y, minlen, off?-1:0, &rawmpilen, NULL);
100 3108 : if (!rawmpi)
101 0 : return gpg_err_code_from_syserror ();
102 3108 : if (mpi_test_bit (x, 0) && rawmpilen)
103 1542 : rawmpi[off + rawmpilen - 1] |= 0x80; /* Set sign bit. */
104 3108 : if (off)
105 0 : rawmpi[0] = 0x40;
106 :
107 3108 : *r_buffer = rawmpi;
108 3108 : *r_buflen = rawmpilen + off;
109 3108 : return 0;
110 : }
111 :
112 : /* Encode POINT using the EdDSA scheme. X and Y are either scratch
113 : variables supplied by the caller or NULL. CTX is the usual
114 : context. If WITH_PREFIX is set the returned buffer is prefixed
115 : with a 0x40 byte. On success 0 is returned and a malloced buffer
116 : with the encoded point is stored at R_BUFFER; the length of this
117 : buffer is stored at R_BUFLEN. */
118 : gpg_err_code_t
119 3106 : _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ec,
120 : gcry_mpi_t x_in, gcry_mpi_t y_in,
121 : int with_prefix,
122 : unsigned char **r_buffer, unsigned int *r_buflen)
123 : {
124 : gpg_err_code_t rc;
125 : gcry_mpi_t x, y;
126 :
127 3106 : x = x_in? x_in : mpi_new (0);
128 3106 : y = y_in? y_in : mpi_new (0);
129 :
130 3106 : if (_gcry_mpi_ec_get_affine (x, y, point, ec))
131 : {
132 0 : log_error ("eddsa_encodepoint: Failed to get affine coordinates\n");
133 0 : rc = GPG_ERR_INTERNAL;
134 : }
135 : else
136 3106 : rc = eddsa_encode_x_y (x, y, ec->nbits/8, with_prefix, r_buffer, r_buflen);
137 :
138 3106 : if (!x_in)
139 3 : mpi_free (x);
140 3106 : if (!y_in)
141 3 : mpi_free (y);
142 3106 : return rc;
143 : }
144 :
145 :
146 : /* Make sure that the opaque MPI VALUE is in compact EdDSA format.
147 : This function updates MPI if needed. */
148 : gpg_err_code_t
149 3 : _gcry_ecc_eddsa_ensure_compact (gcry_mpi_t value, unsigned int nbits)
150 : {
151 : gpg_err_code_t rc;
152 : const unsigned char *buf;
153 : unsigned int rawmpilen;
154 : gcry_mpi_t x, y;
155 : unsigned char *enc;
156 : unsigned int enclen;
157 :
158 3 : if (!mpi_is_opaque (value))
159 0 : return GPG_ERR_INV_OBJ;
160 3 : buf = mpi_get_opaque (value, &rawmpilen);
161 3 : if (!buf)
162 0 : return GPG_ERR_INV_OBJ;
163 3 : rawmpilen = (rawmpilen + 7)/8;
164 :
165 3 : if (rawmpilen > 1 && (rawmpilen%2))
166 : {
167 2 : if (buf[0] == 0x04)
168 : {
169 : /* Buffer is in SEC1 uncompressed format. Extract y and
170 : compress. */
171 2 : rc = _gcry_mpi_scan (&x, GCRYMPI_FMT_STD,
172 2 : buf+1, (rawmpilen-1)/2, NULL);
173 1 : if (rc)
174 0 : return rc;
175 2 : rc = _gcry_mpi_scan (&y, GCRYMPI_FMT_STD,
176 2 : buf+1+(rawmpilen-1)/2, (rawmpilen-1)/2, NULL);
177 1 : if (rc)
178 : {
179 0 : mpi_free (x);
180 0 : return rc;
181 : }
182 :
183 1 : rc = eddsa_encode_x_y (x, y, nbits/8, 0, &enc, &enclen);
184 1 : mpi_free (x);
185 1 : mpi_free (y);
186 1 : if (rc)
187 0 : return rc;
188 :
189 1 : mpi_set_opaque (value, enc, 8*enclen);
190 : }
191 1 : else if (buf[0] == 0x40)
192 : {
193 : /* Buffer is compressed but with our SEC1 alike compression
194 : indicator. Remove that byte. FIXME: We should write and
195 : use a function to manipulate an opaque MPI in place. */
196 1 : if (!_gcry_mpi_set_opaque_copy (value, buf + 1, (rawmpilen - 1)*8))
197 0 : return gpg_err_code_from_syserror ();
198 : }
199 : }
200 :
201 3 : return 0;
202 : }
203 :
204 :
205 : /* Recover X from Y and SIGN (which actually is a parity bit). */
206 : gpg_err_code_t
207 1055 : _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign, mpi_ec_t ec)
208 : {
209 1055 : gpg_err_code_t rc = 0;
210 : gcry_mpi_t u, v, v3, t;
211 : static gcry_mpi_t p58, seven;
212 :
213 1055 : if (ec->dialect != ECC_DIALECT_ED25519)
214 0 : return GPG_ERR_NOT_IMPLEMENTED;
215 :
216 1055 : if (!p58)
217 4 : p58 = scanval ("0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
218 : "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD");
219 1055 : if (!seven)
220 4 : seven = mpi_set_ui (NULL, 7);
221 :
222 1055 : u = mpi_new (0);
223 1055 : v = mpi_new (0);
224 1055 : v3 = mpi_new (0);
225 1055 : t = mpi_new (0);
226 :
227 : /* Compute u and v */
228 : /* u = y^2 */
229 1055 : mpi_mulm (u, y, y, ec->p);
230 : /* v = b*y^2 */
231 1055 : mpi_mulm (v, ec->b, u, ec->p);
232 : /* u = y^2-1 */
233 1055 : mpi_sub_ui (u, u, 1);
234 : /* v = b*y^2+1 */
235 1055 : mpi_add_ui (v, v, 1);
236 :
237 : /* Compute sqrt(u/v) */
238 : /* v3 = v^3 */
239 1055 : mpi_powm (v3, v, mpi_const (MPI_C_THREE), ec->p);
240 : /* t = v3 * v3 * u * v = u * v^7 */
241 1055 : mpi_powm (t, v, seven, ec->p);
242 1055 : mpi_mulm (t, t, u, ec->p);
243 : /* t = t^((p-5)/8) = (u * v^7)^((p-5)/8) */
244 1055 : mpi_powm (t, t, p58, ec->p);
245 : /* x = t * u * v^3 = (u * v^3) * (u * v^7)^((p-5)/8) */
246 1055 : mpi_mulm (t, t, u, ec->p);
247 1055 : mpi_mulm (x, t, v3, ec->p);
248 :
249 : /* Adjust if needed. */
250 : /* t = v * x^2 */
251 1055 : mpi_mulm (t, x, x, ec->p);
252 1055 : mpi_mulm (t, t, v, ec->p);
253 : /* -t == u ? x = x * sqrt(-1) */
254 1055 : mpi_sub (t, ec->p, t);
255 1055 : if (!mpi_cmp (t, u))
256 : {
257 : static gcry_mpi_t m1; /* Fixme: this is not thread-safe. */
258 556 : if (!m1)
259 3 : m1 = scanval ("2B8324804FC1DF0B2B4D00993DFBD7A7"
260 : "2F431806AD2FE478C4EE1B274A0EA0B0");
261 556 : mpi_mulm (x, x, m1, ec->p);
262 : /* t = v * x^2 */
263 556 : mpi_mulm (t, x, x, ec->p);
264 556 : mpi_mulm (t, t, v, ec->p);
265 : /* -t == u ? x = x * sqrt(-1) */
266 556 : mpi_sub (t, ec->p, t);
267 556 : if (!mpi_cmp (t, u))
268 0 : rc = GPG_ERR_INV_OBJ;
269 : }
270 :
271 : /* Choose the desired square root according to parity */
272 1055 : if (mpi_test_bit (x, 0) != !!sign)
273 526 : mpi_sub (x, ec->p, x);
274 :
275 1055 : mpi_free (t);
276 1055 : mpi_free (v3);
277 1055 : mpi_free (v);
278 1055 : mpi_free (u);
279 :
280 1055 : return rc;
281 : }
282 :
283 :
284 : /* Decode the EdDSA style encoded PK and set it into RESULT. CTX is
285 : the usual curve context. If R_ENCPK is not NULL, the encoded PK is
286 : stored at that address; this is a new copy to be released by the
287 : caller. In contrast to the supplied PK, this is not an MPI and
288 : thus guaranteed to be properly padded. R_ENCPKLEN receives the
289 : length of that encoded key. */
290 : gpg_err_code_t
291 1060 : _gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result,
292 : unsigned char **r_encpk, unsigned int *r_encpklen)
293 : {
294 : gpg_err_code_t rc;
295 : unsigned char *rawmpi;
296 : unsigned int rawmpilen;
297 : int sign;
298 :
299 1060 : if (mpi_is_opaque (pk))
300 1055 : {
301 : const unsigned char *buf;
302 :
303 1060 : buf = mpi_get_opaque (pk, &rawmpilen);
304 1060 : if (!buf)
305 0 : return GPG_ERR_INV_OBJ;
306 1060 : rawmpilen = (rawmpilen + 7)/8;
307 :
308 : /* Handle compression prefixes. The size of the buffer will be
309 : odd in this case. */
310 1060 : if (rawmpilen > 1 && (rawmpilen%2))
311 : {
312 : /* First check whether the public key has been given in
313 : standard uncompressed format (SEC1). No need to recover
314 : x in this case. */
315 6 : if (buf[0] == 0x04)
316 : {
317 : gcry_mpi_t x, y;
318 :
319 10 : rc = _gcry_mpi_scan (&x, GCRYMPI_FMT_STD,
320 10 : buf+1, (rawmpilen-1)/2, NULL);
321 5 : if (rc)
322 0 : return rc;
323 10 : rc = _gcry_mpi_scan (&y, GCRYMPI_FMT_STD,
324 10 : buf+1+(rawmpilen-1)/2, (rawmpilen-1)/2,NULL);
325 5 : if (rc)
326 : {
327 0 : mpi_free (x);
328 0 : return rc;
329 : }
330 :
331 5 : if (r_encpk)
332 : {
333 1 : rc = eddsa_encode_x_y (x, y, ctx->nbits/8, 0,
334 : r_encpk, r_encpklen);
335 1 : if (rc)
336 : {
337 0 : mpi_free (x);
338 0 : mpi_free (y);
339 0 : return rc;
340 : }
341 : }
342 5 : mpi_snatch (result->x, x);
343 5 : mpi_snatch (result->y, y);
344 5 : mpi_set_ui (result->z, 1);
345 5 : return 0;
346 : }
347 :
348 : /* Check whether the public key has been prefixed with a 0x40
349 : byte to explicitly indicate compressed format using a SEC1
350 : alike prefix byte. This is a Libgcrypt extension. */
351 1 : if (buf[0] == 0x40)
352 : {
353 1 : rawmpilen--;
354 1 : buf++;
355 : }
356 : }
357 :
358 : /* EdDSA compressed point. */
359 1055 : rawmpi = xtrymalloc (rawmpilen? rawmpilen:1);
360 1055 : if (!rawmpi)
361 0 : return gpg_err_code_from_syserror ();
362 1055 : memcpy (rawmpi, buf, rawmpilen);
363 1055 : reverse_buffer (rawmpi, rawmpilen);
364 : }
365 : else
366 : {
367 : /* Note: Without using an opaque MPI it is not reliable possible
368 : to find out whether the public key has been given in
369 : uncompressed format. Thus we expect native EdDSA format. */
370 0 : rawmpi = _gcry_mpi_get_buffer (pk, ctx->nbits/8, &rawmpilen, NULL);
371 0 : if (!rawmpi)
372 0 : return gpg_err_code_from_syserror ();
373 : }
374 :
375 1055 : if (rawmpilen)
376 : {
377 1055 : sign = !!(rawmpi[0] & 0x80);
378 1055 : rawmpi[0] &= 0x7f;
379 : }
380 : else
381 0 : sign = 0;
382 1055 : _gcry_mpi_set_buffer (result->y, rawmpi, rawmpilen, 0);
383 1055 : if (r_encpk)
384 : {
385 : /* Revert to little endian. */
386 1045 : if (sign && rawmpilen)
387 524 : rawmpi[0] |= 0x80;
388 1045 : reverse_buffer (rawmpi, rawmpilen);
389 1045 : *r_encpk = rawmpi;
390 1045 : if (r_encpklen)
391 1045 : *r_encpklen = rawmpilen;
392 : }
393 : else
394 10 : xfree (rawmpi);
395 :
396 1055 : rc = _gcry_ecc_eddsa_recover_x (result->x, result->y, sign, ctx);
397 1055 : mpi_set_ui (result->z, 1);
398 :
399 1055 : return rc;
400 : }
401 :
402 :
403 : /* Compute the A value as used by EdDSA. The caller needs to provide
404 : the context EC and the actual secret D as an MPI. The function
405 : returns a newly allocated 64 byte buffer at r_digest; the first 32
406 : bytes represent the A value. NULL is returned on error and NULL
407 : stored at R_DIGEST. */
408 : gpg_err_code_t
409 1039 : _gcry_ecc_eddsa_compute_h_d (unsigned char **r_digest,
410 : gcry_mpi_t d, mpi_ec_t ec)
411 : {
412 : gpg_err_code_t rc;
413 1039 : unsigned char *rawmpi = NULL;
414 : unsigned int rawmpilen;
415 : unsigned char *digest;
416 : gcry_buffer_t hvec[2];
417 : int hashalgo, b;
418 :
419 1039 : *r_digest = NULL;
420 :
421 1039 : hashalgo = GCRY_MD_SHA512;
422 1039 : if (hashalgo != GCRY_MD_SHA512)
423 0 : return GPG_ERR_DIGEST_ALGO;
424 :
425 1039 : b = (ec->nbits+7)/8;
426 1039 : if (b != 256/8)
427 0 : return GPG_ERR_INTERNAL; /* We only support 256 bit. */
428 :
429 : /* Note that we clear DIGEST so we can use it as input to left pad
430 : the key with zeroes for hashing. */
431 1039 : digest = xtrycalloc_secure (2, b);
432 1039 : if (!digest)
433 0 : return gpg_err_code_from_syserror ();
434 :
435 1039 : memset (hvec, 0, sizeof hvec);
436 :
437 1039 : rawmpi = _gcry_mpi_get_buffer (d, 0, &rawmpilen, NULL);
438 1039 : if (!rawmpi)
439 : {
440 0 : xfree (digest);
441 0 : return gpg_err_code_from_syserror ();
442 : }
443 :
444 1039 : hvec[0].data = digest;
445 1039 : hvec[0].off = 0;
446 1039 : hvec[0].len = b > rawmpilen? b - rawmpilen : 0;
447 1039 : hvec[1].data = rawmpi;
448 1039 : hvec[1].off = 0;
449 1039 : hvec[1].len = rawmpilen;
450 1039 : rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2);
451 1039 : xfree (rawmpi);
452 1039 : if (rc)
453 : {
454 0 : xfree (digest);
455 0 : return rc;
456 : }
457 :
458 : /* Compute the A value. */
459 1039 : reverse_buffer (digest, 32); /* Only the first half of the hash. */
460 1039 : digest[0] = (digest[0] & 0x7f) | 0x40;
461 1039 : digest[31] &= 0xf8;
462 :
463 1039 : *r_digest = digest;
464 1039 : return 0;
465 : }
466 :
467 :
468 : /**
469 : * _gcry_ecc_eddsa_genkey - EdDSA version of the key generation.
470 : *
471 : * @sk: A struct to receive the secret key.
472 : * @E: Parameters of the curve.
473 : * @ctx: Elliptic curve computation context.
474 : * @flags: Flags controlling aspects of the creation.
475 : *
476 : * Return: An error code.
477 : *
478 : * The only @flags bit used by this function is %PUBKEY_FLAG_TRANSIENT
479 : * to use a faster RNG.
480 : */
481 : gpg_err_code_t
482 2 : _gcry_ecc_eddsa_genkey (ECC_secret_key *sk, elliptic_curve_t *E, mpi_ec_t ctx,
483 : int flags)
484 : {
485 : gpg_err_code_t rc;
486 2 : int b = 256/8; /* The only size we currently support. */
487 : gcry_mpi_t a, x, y;
488 : mpi_point_struct Q;
489 : gcry_random_level_t random_level;
490 : char *dbuf;
491 : size_t dlen;
492 : gcry_buffer_t hvec[1];
493 2 : unsigned char *hash_d = NULL;
494 :
495 2 : point_init (&Q);
496 2 : memset (hvec, 0, sizeof hvec);
497 :
498 2 : if ((flags & PUBKEY_FLAG_TRANSIENT_KEY))
499 0 : random_level = GCRY_STRONG_RANDOM;
500 : else
501 2 : random_level = GCRY_VERY_STRONG_RANDOM;
502 :
503 2 : a = mpi_snew (0);
504 2 : x = mpi_new (0);
505 2 : y = mpi_new (0);
506 :
507 : /* Generate a secret. */
508 2 : hash_d = xtrymalloc_secure (2*b);
509 2 : if (!hash_d)
510 : {
511 0 : rc = gpg_err_code_from_syserror ();
512 0 : goto leave;
513 : }
514 2 : dlen = b;
515 2 : dbuf = _gcry_random_bytes_secure (dlen, random_level);
516 :
517 : /* Compute the A value. */
518 2 : hvec[0].data = dbuf;
519 2 : hvec[0].len = dlen;
520 2 : rc = _gcry_md_hash_buffers (GCRY_MD_SHA512, 0, hash_d, hvec, 1);
521 2 : if (rc)
522 0 : goto leave;
523 2 : sk->d = _gcry_mpi_set_opaque (NULL, dbuf, dlen*8);
524 2 : dbuf = NULL;
525 2 : reverse_buffer (hash_d, 32); /* Only the first half of the hash. */
526 2 : hash_d[0] = (hash_d[0] & 0x7f) | 0x40;
527 2 : hash_d[31] &= 0xf8;
528 2 : _gcry_mpi_set_buffer (a, hash_d, 32, 0);
529 2 : xfree (hash_d); hash_d = NULL;
530 : /* log_printmpi ("ecgen a", a); */
531 :
532 : /* Compute Q. */
533 2 : _gcry_mpi_ec_mul_point (&Q, a, &E->G, ctx);
534 2 : if (DBG_CIPHER)
535 0 : log_printpnt ("ecgen pk", &Q, ctx);
536 :
537 : /* Copy the stuff to the key structures. */
538 2 : sk->E.model = E->model;
539 2 : sk->E.dialect = E->dialect;
540 2 : sk->E.p = mpi_copy (E->p);
541 2 : sk->E.a = mpi_copy (E->a);
542 2 : sk->E.b = mpi_copy (E->b);
543 2 : point_init (&sk->E.G);
544 2 : point_set (&sk->E.G, &E->G);
545 2 : sk->E.n = mpi_copy (E->n);
546 2 : sk->E.h = mpi_copy (E->h);
547 2 : point_init (&sk->Q);
548 2 : point_set (&sk->Q, &Q);
549 :
550 : leave:
551 2 : point_free (&Q);
552 2 : _gcry_mpi_release (a);
553 2 : _gcry_mpi_release (x);
554 2 : _gcry_mpi_release (y);
555 2 : xfree (hash_d);
556 2 : return rc;
557 : }
558 :
559 :
560 : /* Compute an EdDSA signature. See:
561 : * [ed25519] 23pp. (PDF) Daniel J. Bernstein, Niels Duif, Tanja
562 : * Lange, Peter Schwabe, Bo-Yin Yang. High-speed high-security
563 : * signatures. Journal of Cryptographic Engineering 2 (2012), 77-89.
564 : * Document ID: a1a62a2f76d23f65d622484ddd09caf8.
565 : * URL: http://cr.yp.to/papers.html#ed25519. Date: 2011.09.26.
566 : *
567 : * Despite that this function requires the specification of a hash
568 : * algorithm, we only support what has been specified by the paper.
569 : * This may change in the future. Note that we don't check the used
570 : * curve; the user is responsible to use Ed25519.
571 : *
572 : * Return the signature struct (r,s) from the message hash. The caller
573 : * must have allocated R_R and S.
574 : */
575 : gpg_err_code_t
576 1036 : _gcry_ecc_eddsa_sign (gcry_mpi_t input, ECC_secret_key *skey,
577 : gcry_mpi_t r_r, gcry_mpi_t s, int hashalgo, gcry_mpi_t pk)
578 : {
579 : int rc;
580 1036 : mpi_ec_t ctx = NULL;
581 : int b;
582 : unsigned int tmp;
583 1036 : unsigned char *digest = NULL;
584 : gcry_buffer_t hvec[3];
585 : const void *mbuf;
586 : size_t mlen;
587 1036 : unsigned char *rawmpi = NULL;
588 : unsigned int rawmpilen;
589 1036 : unsigned char *encpk = NULL; /* Encoded public key. */
590 : unsigned int encpklen;
591 : mpi_point_struct I; /* Intermediate value. */
592 : mpi_point_struct Q; /* Public key. */
593 : gcry_mpi_t a, x, y, r;
594 :
595 1036 : memset (hvec, 0, sizeof hvec);
596 :
597 1036 : if (!mpi_is_opaque (input))
598 0 : return GPG_ERR_INV_DATA;
599 :
600 : /* Initialize some helpers. */
601 1036 : point_init (&I);
602 1036 : point_init (&Q);
603 1036 : a = mpi_snew (0);
604 1036 : x = mpi_new (0);
605 1036 : y = mpi_new (0);
606 1036 : r = mpi_new (0);
607 1036 : ctx = _gcry_mpi_ec_p_internal_new (skey->E.model, skey->E.dialect, 0,
608 : skey->E.p, skey->E.a, skey->E.b);
609 1036 : b = (ctx->nbits+7)/8;
610 1036 : if (b != 256/8) {
611 0 : rc = GPG_ERR_INTERNAL; /* We only support 256 bit. */
612 0 : goto leave;
613 : }
614 :
615 1036 : rc = _gcry_ecc_eddsa_compute_h_d (&digest, skey->d, ctx);
616 1036 : if (rc)
617 0 : goto leave;
618 1036 : _gcry_mpi_set_buffer (a, digest, 32, 0);
619 :
620 : /* Compute the public key if it has not been supplied as optional
621 : parameter. */
622 1036 : if (pk)
623 : {
624 10 : rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q, &encpk, &encpklen);
625 10 : if (rc)
626 0 : goto leave;
627 10 : if (DBG_CIPHER)
628 0 : log_printhex ("* e_pk", encpk, encpklen);
629 10 : if (!_gcry_mpi_ec_curve_point (&Q, ctx))
630 : {
631 0 : rc = GPG_ERR_BROKEN_PUBKEY;
632 0 : goto leave;
633 : }
634 : }
635 : else
636 : {
637 1026 : _gcry_mpi_ec_mul_point (&Q, a, &skey->E.G, ctx);
638 1026 : rc = _gcry_ecc_eddsa_encodepoint (&Q, ctx, x, y, 0, &encpk, &encpklen);
639 1026 : if (rc)
640 0 : goto leave;
641 1026 : if (DBG_CIPHER)
642 0 : log_printhex (" e_pk", encpk, encpklen);
643 : }
644 :
645 : /* Compute R. */
646 1036 : mbuf = mpi_get_opaque (input, &tmp);
647 1036 : mlen = (tmp +7)/8;
648 1036 : if (DBG_CIPHER)
649 0 : log_printhex (" m", mbuf, mlen);
650 :
651 1036 : hvec[0].data = digest;
652 1036 : hvec[0].off = 32;
653 1036 : hvec[0].len = 32;
654 1036 : hvec[1].data = (char*)mbuf;
655 1036 : hvec[1].len = mlen;
656 1036 : rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2);
657 1036 : if (rc)
658 0 : goto leave;
659 1036 : reverse_buffer (digest, 64);
660 1036 : if (DBG_CIPHER)
661 0 : log_printhex (" r", digest, 64);
662 1036 : _gcry_mpi_set_buffer (r, digest, 64, 0);
663 1036 : _gcry_mpi_ec_mul_point (&I, r, &skey->E.G, ctx);
664 1036 : if (DBG_CIPHER)
665 0 : log_printpnt (" r", &I, ctx);
666 :
667 : /* Convert R into affine coordinates and apply encoding. */
668 1036 : rc = _gcry_ecc_eddsa_encodepoint (&I, ctx, x, y, 0, &rawmpi, &rawmpilen);
669 1036 : if (rc)
670 0 : goto leave;
671 1036 : if (DBG_CIPHER)
672 0 : log_printhex (" e_r", rawmpi, rawmpilen);
673 :
674 : /* S = r + a * H(encodepoint(R) + encodepoint(pk) + m) mod n */
675 1036 : hvec[0].data = rawmpi; /* (this is R) */
676 1036 : hvec[0].off = 0;
677 1036 : hvec[0].len = rawmpilen;
678 1036 : hvec[1].data = encpk;
679 1036 : hvec[1].off = 0;
680 1036 : hvec[1].len = encpklen;
681 1036 : hvec[2].data = (char*)mbuf;
682 1036 : hvec[2].off = 0;
683 1036 : hvec[2].len = mlen;
684 1036 : rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
685 1036 : if (rc)
686 0 : goto leave;
687 :
688 : /* No more need for RAWMPI thus we now transfer it to R_R. */
689 1036 : mpi_set_opaque (r_r, rawmpi, rawmpilen*8);
690 1036 : rawmpi = NULL;
691 :
692 1036 : reverse_buffer (digest, 64);
693 1036 : if (DBG_CIPHER)
694 0 : log_printhex (" H(R+)", digest, 64);
695 1036 : _gcry_mpi_set_buffer (s, digest, 64, 0);
696 1036 : mpi_mulm (s, s, a, skey->E.n);
697 1036 : mpi_addm (s, s, r, skey->E.n);
698 1036 : rc = eddsa_encodempi (s, b, &rawmpi, &rawmpilen);
699 1036 : if (rc)
700 0 : goto leave;
701 1036 : if (DBG_CIPHER)
702 0 : log_printhex (" e_s", rawmpi, rawmpilen);
703 1036 : mpi_set_opaque (s, rawmpi, rawmpilen*8);
704 1036 : rawmpi = NULL;
705 :
706 1036 : rc = 0;
707 :
708 : leave:
709 1036 : _gcry_mpi_release (a);
710 1036 : _gcry_mpi_release (x);
711 1036 : _gcry_mpi_release (y);
712 1036 : _gcry_mpi_release (r);
713 1036 : xfree (digest);
714 1036 : _gcry_mpi_ec_free (ctx);
715 1036 : point_free (&I);
716 1036 : point_free (&Q);
717 1036 : xfree (encpk);
718 1036 : xfree (rawmpi);
719 1036 : return rc;
720 : }
721 :
722 :
723 : /* Verify an EdDSA signature. See sign_eddsa for the reference.
724 : * Check if R_IN and S_IN verifies INPUT. PKEY has the curve
725 : * parameters and PK is the EdDSA style encoded public key.
726 : */
727 : gpg_err_code_t
728 1036 : _gcry_ecc_eddsa_verify (gcry_mpi_t input, ECC_public_key *pkey,
729 : gcry_mpi_t r_in, gcry_mpi_t s_in, int hashalgo,
730 : gcry_mpi_t pk)
731 : {
732 : int rc;
733 1036 : mpi_ec_t ctx = NULL;
734 : int b;
735 : unsigned int tmp;
736 : mpi_point_struct Q; /* Public key. */
737 1036 : unsigned char *encpk = NULL; /* Encoded public key. */
738 : unsigned int encpklen;
739 : const void *mbuf, *rbuf;
740 1036 : unsigned char *tbuf = NULL;
741 : size_t mlen, rlen;
742 : unsigned int tlen;
743 : unsigned char digest[64];
744 : gcry_buffer_t hvec[3];
745 : gcry_mpi_t h, s;
746 : mpi_point_struct Ia, Ib;
747 :
748 1036 : if (!mpi_is_opaque (input) || !mpi_is_opaque (r_in) || !mpi_is_opaque (s_in))
749 0 : return GPG_ERR_INV_DATA;
750 1036 : if (hashalgo != GCRY_MD_SHA512)
751 0 : return GPG_ERR_DIGEST_ALGO;
752 :
753 1036 : point_init (&Q);
754 1036 : point_init (&Ia);
755 1036 : point_init (&Ib);
756 1036 : h = mpi_new (0);
757 1036 : s = mpi_new (0);
758 :
759 1036 : ctx = _gcry_mpi_ec_p_internal_new (pkey->E.model, pkey->E.dialect, 0,
760 : pkey->E.p, pkey->E.a, pkey->E.b);
761 1036 : b = ctx->nbits/8;
762 1036 : if (b != 256/8)
763 0 : return GPG_ERR_INTERNAL; /* We only support 256 bit. */
764 :
765 : /* Decode and check the public key. */
766 1036 : rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q, &encpk, &encpklen);
767 1036 : if (rc)
768 0 : goto leave;
769 1036 : if (!_gcry_mpi_ec_curve_point (&Q, ctx))
770 : {
771 0 : rc = GPG_ERR_BROKEN_PUBKEY;
772 0 : goto leave;
773 : }
774 1036 : if (DBG_CIPHER)
775 0 : log_printhex (" e_pk", encpk, encpklen);
776 1036 : if (encpklen != b)
777 : {
778 0 : rc = GPG_ERR_INV_LENGTH;
779 0 : goto leave;
780 : }
781 :
782 : /* Convert the other input parameters. */
783 1036 : mbuf = mpi_get_opaque (input, &tmp);
784 1036 : mlen = (tmp +7)/8;
785 1036 : if (DBG_CIPHER)
786 0 : log_printhex (" m", mbuf, mlen);
787 1036 : rbuf = mpi_get_opaque (r_in, &tmp);
788 1036 : rlen = (tmp +7)/8;
789 1036 : if (DBG_CIPHER)
790 0 : log_printhex (" r", rbuf, rlen);
791 1036 : if (rlen != b)
792 : {
793 0 : rc = GPG_ERR_INV_LENGTH;
794 0 : goto leave;
795 : }
796 :
797 : /* h = H(encodepoint(R) + encodepoint(pk) + m) */
798 1036 : hvec[0].data = (char*)rbuf;
799 1036 : hvec[0].off = 0;
800 1036 : hvec[0].len = rlen;
801 1036 : hvec[1].data = encpk;
802 1036 : hvec[1].off = 0;
803 1036 : hvec[1].len = encpklen;
804 1036 : hvec[2].data = (char*)mbuf;
805 1036 : hvec[2].off = 0;
806 1036 : hvec[2].len = mlen;
807 1036 : rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
808 1036 : if (rc)
809 0 : goto leave;
810 1036 : reverse_buffer (digest, 64);
811 1036 : if (DBG_CIPHER)
812 0 : log_printhex (" H(R+)", digest, 64);
813 1036 : _gcry_mpi_set_buffer (h, digest, 64, 0);
814 :
815 : /* According to the paper the best way for verification is:
816 : encodepoint(sG - h·Q) = encodepoint(r)
817 : because we don't need to decode R. */
818 : {
819 : void *sbuf;
820 : unsigned int slen;
821 :
822 1036 : sbuf = _gcry_mpi_get_opaque_copy (s_in, &tmp);
823 1036 : slen = (tmp +7)/8;
824 1036 : reverse_buffer (sbuf, slen);
825 1036 : if (DBG_CIPHER)
826 0 : log_printhex (" s", sbuf, slen);
827 1036 : _gcry_mpi_set_buffer (s, sbuf, slen, 0);
828 1036 : xfree (sbuf);
829 1036 : if (slen != b)
830 : {
831 0 : rc = GPG_ERR_INV_LENGTH;
832 0 : goto leave;
833 : }
834 : }
835 :
836 1036 : _gcry_mpi_ec_mul_point (&Ia, s, &pkey->E.G, ctx);
837 1036 : _gcry_mpi_ec_mul_point (&Ib, h, &Q, ctx);
838 1036 : _gcry_mpi_sub (Ib.x, ctx->p, Ib.x);
839 1036 : _gcry_mpi_ec_add_points (&Ia, &Ia, &Ib, ctx);
840 1036 : rc = _gcry_ecc_eddsa_encodepoint (&Ia, ctx, s, h, 0, &tbuf, &tlen);
841 1036 : if (rc)
842 0 : goto leave;
843 1036 : if (tlen != rlen || memcmp (tbuf, rbuf, tlen))
844 : {
845 0 : rc = GPG_ERR_BAD_SIGNATURE;
846 0 : goto leave;
847 : }
848 :
849 1036 : rc = 0;
850 :
851 : leave:
852 1036 : xfree (encpk);
853 1036 : xfree (tbuf);
854 1036 : _gcry_mpi_ec_free (ctx);
855 1036 : _gcry_mpi_release (s);
856 1036 : _gcry_mpi_release (h);
857 1036 : point_free (&Ia);
858 1036 : point_free (&Ib);
859 1036 : point_free (&Q);
860 1036 : return rc;
861 : }
|
