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 void
reverse_buffer(unsigned char * buffer,unsigned int length)36 reverse_buffer (unsigned char *buffer, unsigned int length)
37 {
38 unsigned int tmp, i;
39
40 for (i=0; i < length/2; i++)
41 {
42 tmp = buffer[i];
43 buffer[i] = buffer[length-1-i];
44 buffer[length-1-i] = tmp;
45 }
46 }
47
48
49 /* Helper to scan a hex string. */
50 static gcry_mpi_t
scanval(const char * string)51 scanval (const char *string)
52 {
53 gpg_err_code_t rc;
54 gcry_mpi_t val;
55
56 rc = _gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL);
57 if (rc)
58 log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (rc));
59 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
eddsa_encodempi(gcry_mpi_t mpi,unsigned int nbits,unsigned char ** r_buffer,unsigned int * r_buflen)69 eddsa_encodempi (gcry_mpi_t mpi, unsigned int nbits,
70 unsigned char **r_buffer, unsigned int *r_buflen)
71 {
72 unsigned char *rawmpi;
73 unsigned int rawmpilen;
74 unsigned int minlen = (nbits%8) == 0 ? (nbits/8 + 1): (nbits+7)/8;
75
76 rawmpi = _gcry_mpi_get_buffer (mpi, minlen, &rawmpilen, NULL);
77 if (!rawmpi)
78 return gpg_err_code_from_syserror ();
79
80 *r_buffer = rawmpi;
81 *r_buflen = rawmpilen;
82 return 0;
83 }
84
85
86 /* Encode (X,Y) using the EdDSA scheme. NBITS is the number of bits
87 of the field of the curve. If WITH_PREFIX is set the returned
88 buffer is prefixed with a 0x40 byte. On success 0 is returned and
89 a malloced buffer with the encoded point is stored at R_BUFFER; the
90 length of this buffer is stored at R_BUFLEN. */
91 static gpg_err_code_t
eddsa_encode_x_y(gcry_mpi_t x,gcry_mpi_t y,unsigned int nbits,int with_prefix,unsigned char ** r_buffer,unsigned int * r_buflen)92 eddsa_encode_x_y (gcry_mpi_t x, gcry_mpi_t y, unsigned int nbits,
93 int with_prefix,
94 unsigned char **r_buffer, unsigned int *r_buflen)
95 {
96 unsigned char *rawmpi;
97 unsigned int rawmpilen;
98 int off = with_prefix? 1:0;
99 unsigned int minlen = (nbits%8) == 0 ? (nbits/8 + 1): (nbits+7)/8;
100
101 rawmpi = _gcry_mpi_get_buffer_extra (y, minlen, off?-1:0, &rawmpilen, NULL);
102 if (!rawmpi)
103 return gpg_err_code_from_syserror ();
104 if (mpi_test_bit (x, 0) && rawmpilen)
105 rawmpi[off + rawmpilen - 1] |= 0x80; /* Set sign bit. */
106 if (off)
107 rawmpi[0] = 0x40;
108
109 *r_buffer = rawmpi;
110 *r_buflen = rawmpilen + off;
111 return 0;
112 }
113
114 /* Encode POINT using the EdDSA scheme. X and Y are either scratch
115 variables supplied by the caller or NULL. CTX is the usual
116 context. If WITH_PREFIX is set the returned buffer is prefixed
117 with a 0x40 byte. On success 0 is returned and a malloced buffer
118 with the encoded point is stored at R_BUFFER; the length of this
119 buffer is stored at R_BUFLEN. */
120 gpg_err_code_t
_gcry_ecc_eddsa_encodepoint(mpi_point_t point,mpi_ec_t ec,gcry_mpi_t x_in,gcry_mpi_t y_in,int with_prefix,unsigned char ** r_buffer,unsigned int * r_buflen)121 _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ec,
122 gcry_mpi_t x_in, gcry_mpi_t y_in,
123 int with_prefix,
124 unsigned char **r_buffer, unsigned int *r_buflen)
125 {
126 gpg_err_code_t rc;
127 gcry_mpi_t x, y;
128
129 x = x_in? x_in : mpi_new (0);
130 y = y_in? y_in : mpi_new (0);
131
132 if (_gcry_mpi_ec_get_affine (x, y, point, ec))
133 {
134 log_error ("eddsa_encodepoint: Failed to get affine coordinates\n");
135 rc = GPG_ERR_INTERNAL;
136 }
137 else
138 rc = eddsa_encode_x_y (x, y, ec->nbits, with_prefix, r_buffer, r_buflen);
139
140 if (!x_in)
141 mpi_free (x);
142 if (!y_in)
143 mpi_free (y);
144 return rc;
145 }
146
147
148 /* Make sure that the opaque MPI VALUE is in compact EdDSA format.
149 This function updates MPI if needed. */
150 gpg_err_code_t
_gcry_ecc_eddsa_ensure_compact(gcry_mpi_t value,unsigned int nbits)151 _gcry_ecc_eddsa_ensure_compact (gcry_mpi_t value, unsigned int nbits)
152 {
153 gpg_err_code_t rc;
154 const unsigned char *buf;
155 unsigned int rawmpilen;
156 gcry_mpi_t x, y;
157 unsigned char *enc;
158 unsigned int enclen;
159
160 if (!mpi_is_opaque (value))
161 return GPG_ERR_INV_OBJ;
162 buf = mpi_get_opaque (value, &rawmpilen);
163 if (!buf)
164 return GPG_ERR_INV_OBJ;
165 rawmpilen = (rawmpilen + 7)/8;
166
167 if (rawmpilen > 1 && (rawmpilen%2))
168 {
169 if (buf[0] == 0x04)
170 {
171 /* Buffer is in SEC1 uncompressed format. Extract y and
172 compress. */
173 rc = _gcry_mpi_scan (&x, GCRYMPI_FMT_USG,
174 buf+1, (rawmpilen-1)/2, NULL);
175 if (rc)
176 return rc;
177 rc = _gcry_mpi_scan (&y, GCRYMPI_FMT_USG,
178 buf+1+(rawmpilen-1)/2, (rawmpilen-1)/2, NULL);
179 if (rc)
180 {
181 mpi_free (x);
182 return rc;
183 }
184
185 rc = eddsa_encode_x_y (x, y, nbits, 0, &enc, &enclen);
186 mpi_free (x);
187 mpi_free (y);
188 if (rc)
189 return rc;
190
191 mpi_set_opaque (value, enc, 8*enclen);
192 }
193 else if (buf[0] == 0x40)
194 {
195 /* Buffer is compressed but with our SEC1 alike compression
196 indicator. Remove that byte. FIXME: We should write and
197 use a function to manipulate an opaque MPI in place. */
198 if (!_gcry_mpi_set_opaque_copy (value, buf + 1, (rawmpilen - 1)*8))
199 return gpg_err_code_from_syserror ();
200 }
201 }
202
203 return 0;
204 }
205
206
207 static gpg_err_code_t
ecc_ed448_recover_x(gcry_mpi_t x,gcry_mpi_t y,int x_0,mpi_ec_t ec)208 ecc_ed448_recover_x (gcry_mpi_t x, gcry_mpi_t y, int x_0, mpi_ec_t ec)
209 {
210 gpg_err_code_t rc = 0;
211 gcry_mpi_t u, v, u3, v3, t;
212 static gcry_mpi_t p34; /* Hard coded (P-3)/4 */
213
214 if (mpi_cmp (y, ec->p) >= 0)
215 rc = GPG_ERR_INV_OBJ;
216
217 if (!p34)
218 p34 = scanval ("3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
219 "BFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
220
221 u = mpi_new (0);
222 v = mpi_new (0);
223 u3 = mpi_new (0);
224 v3 = mpi_new (0);
225 t = mpi_new (0);
226
227 /* Compute u and v */
228 /* u = y^2 */
229 mpi_mulm (u, y, y, ec->p);
230 /* v = b*y^2 */
231 mpi_mulm (v, ec->b, u, ec->p);
232 /* u = y^2-1 */
233 mpi_sub_ui (u, u, 1);
234 /* v = b*y^2-1 */
235 mpi_sub_ui (v, v, 1);
236
237 /* Compute sqrt(u/v) */
238 /* u3 = u^3 */
239 mpi_powm (u3, u, mpi_const (MPI_C_THREE), ec->p);
240 mpi_powm (v3, v, mpi_const (MPI_C_THREE), ec->p);
241 /* t = u^4 * u * v3 = u^5 * v^3 */
242 mpi_powm (t, u, mpi_const (MPI_C_FOUR), ec->p);
243 mpi_mulm (t, t, u, ec->p);
244 mpi_mulm (t, t, v3, ec->p);
245 /* t = t^((p-3)/4) = (u^5 * v^3)^((p-3)/4) */
246 mpi_powm (t, t, p34, ec->p);
247 /* x = t * u^3 * v = (u^3 * v) * (u^5 * v^3)^((p-3)/4) */
248 mpi_mulm (t, t, u3, ec->p);
249 mpi_mulm (x, t, v, ec->p);
250
251 /* t = v * x^2 */
252 mpi_mulm (t, x, x, ec->p);
253 mpi_mulm (t, t, v, ec->p);
254
255 if (mpi_cmp (t, u) != 0)
256 rc = GPG_ERR_INV_OBJ;
257 else
258 {
259 if (!mpi_cmp_ui (x, 0) && x_0)
260 rc = GPG_ERR_INV_OBJ;
261
262 /* Choose the desired square root according to parity */
263 if (mpi_test_bit (x, 0) != !!x_0)
264 mpi_sub (x, ec->p, x);
265 }
266
267 mpi_free (t);
268 mpi_free (u3);
269 mpi_free (v3);
270 mpi_free (v);
271 mpi_free (u);
272
273 return rc;
274 }
275
276
277 /* Recover X from Y and SIGN (which actually is a parity bit). */
278 gpg_err_code_t
_gcry_ecc_eddsa_recover_x(gcry_mpi_t x,gcry_mpi_t y,int sign,mpi_ec_t ec)279 _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign, mpi_ec_t ec)
280 {
281 gpg_err_code_t rc = 0;
282 gcry_mpi_t u, v, v3, t;
283 static gcry_mpi_t p58, seven;
284
285 /*
286 * This routine is actually curve specific. Now, only supports
287 * Ed25519 and Ed448.
288 */
289
290 if (ec->dialect != ECC_DIALECT_ED25519)
291 /* For now, it's only Ed448. */
292 return ecc_ed448_recover_x (x, y, sign, ec);
293
294 /* It's Ed25519. */
295
296 if (!p58)
297 p58 = scanval ("0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
298 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD");
299 if (!seven)
300 seven = mpi_set_ui (NULL, 7);
301
302 u = mpi_new (0);
303 v = mpi_new (0);
304 v3 = mpi_new (0);
305 t = mpi_new (0);
306
307 /* Compute u and v */
308 /* u = y^2 */
309 mpi_mulm (u, y, y, ec->p);
310 /* v = b*y^2 */
311 mpi_mulm (v, ec->b, u, ec->p);
312 /* u = y^2-1 */
313 mpi_sub_ui (u, u, 1);
314 /* v = b*y^2+1 */
315 mpi_add_ui (v, v, 1);
316
317 /* Compute sqrt(u/v) */
318 /* v3 = v^3 */
319 mpi_powm (v3, v, mpi_const (MPI_C_THREE), ec->p);
320 /* t = v3 * v3 * u * v = u * v^7 */
321 mpi_powm (t, v, seven, ec->p);
322 mpi_mulm (t, t, u, ec->p);
323 /* t = t^((p-5)/8) = (u * v^7)^((p-5)/8) */
324 mpi_powm (t, t, p58, ec->p);
325 /* x = t * u * v^3 = (u * v^3) * (u * v^7)^((p-5)/8) */
326 mpi_mulm (t, t, u, ec->p);
327 mpi_mulm (x, t, v3, ec->p);
328
329 /* Adjust if needed. */
330 /* t = v * x^2 */
331 mpi_mulm (t, x, x, ec->p);
332 mpi_mulm (t, t, v, ec->p);
333 /* -t == u ? x = x * sqrt(-1) */
334 mpi_sub (t, ec->p, t);
335 if (!mpi_cmp (t, u))
336 {
337 static gcry_mpi_t m1; /* Fixme: this is not thread-safe. */
338 if (!m1)
339 m1 = scanval ("2B8324804FC1DF0B2B4D00993DFBD7A7"
340 "2F431806AD2FE478C4EE1B274A0EA0B0");
341 mpi_mulm (x, x, m1, ec->p);
342 /* t = v * x^2 */
343 mpi_mulm (t, x, x, ec->p);
344 mpi_mulm (t, t, v, ec->p);
345 /* -t == u ? x = x * sqrt(-1) */
346 mpi_sub (t, ec->p, t);
347 if (!mpi_cmp (t, u))
348 rc = GPG_ERR_INV_OBJ;
349 }
350
351 /* Choose the desired square root according to parity */
352 if (mpi_test_bit (x, 0) != !!sign)
353 mpi_sub (x, ec->p, x);
354
355 mpi_free (t);
356 mpi_free (v3);
357 mpi_free (v);
358 mpi_free (u);
359
360 return rc;
361 }
362
363
364 /* Decode the EdDSA style encoded PK and set it into RESULT. CTX is
365 the usual curve context. If R_ENCPK is not NULL, the encoded PK is
366 stored at that address; this is a new copy to be released by the
367 caller. In contrast to the supplied PK, this is not an MPI and
368 thus guaranteed to be properly padded. R_ENCPKLEN receives the
369 length of that encoded key. */
370 gpg_err_code_t
_gcry_ecc_eddsa_decodepoint(gcry_mpi_t pk,mpi_ec_t ctx,mpi_point_t result,unsigned char ** r_encpk,unsigned int * r_encpklen)371 _gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result,
372 unsigned char **r_encpk, unsigned int *r_encpklen)
373 {
374 gpg_err_code_t rc;
375 unsigned char *rawmpi;
376 unsigned int rawmpilen;
377 int sign;
378
379 if (mpi_is_opaque (pk))
380 {
381 const unsigned char *buf;
382 unsigned int len;
383
384 len = (ctx->nbits%8) == 0 ? (ctx->nbits/8 + 1): (ctx->nbits+7)/8;
385
386 buf = mpi_get_opaque (pk, &rawmpilen);
387 if (!buf)
388 return GPG_ERR_INV_OBJ;
389 rawmpilen = (rawmpilen + 7)/8;
390
391 if (!(rawmpilen == len
392 || rawmpilen == len + 1
393 || rawmpilen == len * 2 + 1))
394 return GPG_ERR_INV_OBJ;
395
396 /* Handle compression prefixes. The size of the buffer will be
397 odd in this case. */
398 if (rawmpilen > 1 && (rawmpilen == len + 1 || rawmpilen == len * 2 + 1))
399 {
400 /* First check whether the public key has been given in
401 standard uncompressed format (SEC1). No need to recover
402 x in this case. */
403 if (buf[0] == 0x04)
404 {
405 gcry_mpi_t x, y;
406
407 rc = _gcry_mpi_scan (&x, GCRYMPI_FMT_USG,
408 buf+1, (rawmpilen-1)/2, NULL);
409 if (rc)
410 return rc;
411 rc = _gcry_mpi_scan (&y, GCRYMPI_FMT_USG,
412 buf+1+(rawmpilen-1)/2, (rawmpilen-1)/2,NULL);
413 if (rc)
414 {
415 mpi_free (x);
416 return rc;
417 }
418
419 if (r_encpk)
420 {
421 rc = eddsa_encode_x_y (x, y, ctx->nbits, 0,
422 r_encpk, r_encpklen);
423 if (rc)
424 {
425 mpi_free (x);
426 mpi_free (y);
427 return rc;
428 }
429 }
430 mpi_snatch (result->x, x);
431 mpi_snatch (result->y, y);
432 mpi_set_ui (result->z, 1);
433 return 0;
434 }
435
436 /* Check whether the public key has been prefixed with a 0x40
437 byte to explicitly indicate compressed format using a SEC1
438 alike prefix byte. This is a Libgcrypt extension. */
439 if (buf[0] == 0x40)
440 {
441 rawmpilen--;
442 buf++;
443 }
444 }
445
446 /* EdDSA compressed point. */
447 rawmpi = xtrymalloc (rawmpilen);
448 if (!rawmpi)
449 return gpg_err_code_from_syserror ();
450 memcpy (rawmpi, buf, rawmpilen);
451 reverse_buffer (rawmpi, rawmpilen);
452 }
453 else
454 {
455 /* Note: Without using an opaque MPI it is not reliable possible
456 to find out whether the public key has been given in
457 uncompressed format. Thus we expect native EdDSA format. */
458 rawmpi = _gcry_mpi_get_buffer (pk, (ctx->nbits+7)/8, &rawmpilen, NULL);
459 if (!rawmpi)
460 return gpg_err_code_from_syserror ();
461 }
462
463 if (rawmpilen)
464 {
465 sign = !!(rawmpi[0] & 0x80);
466 rawmpi[0] &= 0x7f;
467 }
468 else
469 sign = 0;
470 _gcry_mpi_set_buffer (result->y, rawmpi, rawmpilen, 0);
471 if (r_encpk)
472 {
473 /* Revert to little endian. */
474 if (sign && rawmpilen)
475 rawmpi[0] |= 0x80;
476 reverse_buffer (rawmpi, rawmpilen);
477 *r_encpk = rawmpi;
478 if (r_encpklen)
479 *r_encpklen = rawmpilen;
480 }
481 else
482 xfree (rawmpi);
483
484 rc = _gcry_ecc_eddsa_recover_x (result->x, result->y, sign, ctx);
485 mpi_set_ui (result->z, 1);
486
487 return rc;
488 }
489
490
491 /* Compute the A value as used by EdDSA. The caller needs to provide
492 the context EC and the actual secret D as an MPI. The function
493 returns a newly allocated 64 byte buffer at r_digest; the first 32
494 bytes represent the A value. NULL is returned on error and NULL
495 stored at R_DIGEST. */
496 gpg_err_code_t
_gcry_ecc_eddsa_compute_h_d(unsigned char ** r_digest,mpi_ec_t ec)497 _gcry_ecc_eddsa_compute_h_d (unsigned char **r_digest, mpi_ec_t ec)
498 {
499 gpg_err_code_t rc;
500 unsigned char *rawmpi = NULL;
501 unsigned int rawmpilen;
502 unsigned char *digest;
503 int hashalgo, b;
504
505 *r_digest = NULL;
506
507 b = (ec->nbits+7)/8;
508
509 /*
510 * Choice of hashalgo is curve specific.
511 * For now, it's determine by the bit size of the field.
512 */
513 if (ec->nbits == 255)
514 hashalgo = GCRY_MD_SHA512;
515 else if (ec->nbits == 448)
516 {
517 b++;
518 hashalgo = GCRY_MD_SHAKE256;
519 }
520 else
521 return GPG_ERR_NOT_IMPLEMENTED;
522
523 /* Note that we clear DIGEST so we can use it as input to left pad
524 the key with zeroes for hashing. */
525 digest = xtrycalloc_secure (2, b);
526 if (!digest)
527 return gpg_err_code_from_syserror ();
528
529 rawmpi = _gcry_mpi_get_buffer (ec->d, 0, &rawmpilen, NULL);
530 if (!rawmpi)
531 {
532 xfree (digest);
533 return gpg_err_code_from_syserror ();
534 }
535
536 if (hashalgo == GCRY_MD_SHAKE256)
537 {
538 gcry_error_t err;
539 gcry_md_hd_t hd;
540
541 err = _gcry_md_open (&hd, hashalgo, 0);
542 if (err)
543 rc = gcry_err_code (err);
544 else
545 {
546 _gcry_md_write (hd, rawmpi, rawmpilen);
547 _gcry_md_ctl (hd, GCRYCTL_FINALIZE, NULL, 0);
548 _gcry_md_extract (hd, GCRY_MD_SHAKE256, digest, 2*b);
549 _gcry_md_close (hd);
550 rc = 0;
551 }
552 }
553 else
554 {
555 gcry_buffer_t hvec[2];
556
557 memset (hvec, 0, sizeof hvec);
558
559 hvec[0].data = digest;
560 hvec[0].len = b > rawmpilen? b - rawmpilen : 0;
561 hvec[1].data = rawmpi;
562 hvec[1].len = rawmpilen;
563 rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2);
564 }
565
566 xfree (rawmpi);
567 if (rc)
568 {
569 xfree (digest);
570 return rc;
571 }
572
573 /* Compute the A value. */
574 reverse_buffer (digest, b); /* Only the first half of the hash. */
575
576 /* Field specific handling of clearing/setting bits. */
577 if (ec->nbits == 255)
578 {
579 digest[0] = (digest[0] & 0x7f) | 0x40;
580 digest[31] &= 0xf8;
581 }
582 else
583 {
584 digest[0] = 0;
585 digest[1] |= 0x80;
586 digest[56] &= 0xfc;
587 }
588
589 *r_digest = digest;
590 return 0;
591 }
592
593
594 /**
595 * _gcry_ecc_eddsa_genkey - EdDSA version of the key generation.
596 *
597 * @ec: Elliptic curve computation context.
598 * @flags: Flags controlling aspects of the creation.
599 *
600 * Return: An error code.
601 *
602 * The only @flags bit used by this function is %PUBKEY_FLAG_TRANSIENT
603 * to use a faster RNG.
604 */
605 gpg_err_code_t
_gcry_ecc_eddsa_genkey(mpi_ec_t ec,int flags)606 _gcry_ecc_eddsa_genkey (mpi_ec_t ec, int flags)
607 {
608 gpg_err_code_t rc;
609 int b;
610 gcry_mpi_t a, x, y;
611 mpi_point_struct Q;
612 gcry_random_level_t random_level;
613 char *dbuf;
614 size_t dlen;
615 unsigned char *hash_d = NULL;
616
617 point_init (&Q);
618
619 if ((flags & PUBKEY_FLAG_TRANSIENT_KEY))
620 random_level = GCRY_STRONG_RANDOM;
621 else
622 random_level = GCRY_VERY_STRONG_RANDOM;
623
624 b = (ec->nbits+7)/8;
625
626 if (ec->nbits == 255)
627 ;
628 else if (ec->nbits == 448)
629 b++;
630 else
631 return GPG_ERR_NOT_IMPLEMENTED;
632
633 dlen = b;
634
635 a = mpi_snew (0);
636 x = mpi_new (0);
637 y = mpi_new (0);
638
639 /* Generate a secret. */
640 dbuf = _gcry_random_bytes_secure (dlen, random_level);
641 ec->d = _gcry_mpi_set_opaque (NULL, dbuf, dlen*8);
642 rc = _gcry_ecc_eddsa_compute_h_d (&hash_d, ec);
643 if (rc)
644 goto leave;
645
646 _gcry_mpi_set_buffer (a, hash_d, b, 0);
647 xfree (hash_d);
648 /* log_printmpi ("ecgen a", a); */
649
650 /* Compute Q. */
651 _gcry_mpi_ec_mul_point (&Q, a, ec->G, ec);
652 if (DBG_CIPHER)
653 log_printpnt ("ecgen pk", &Q, ec);
654
655 ec->Q = mpi_point_snatch_set (NULL, Q.x, Q.y, Q.z);
656 Q.x = NULL;
657 Q.y = NULL;
658 Q.x = NULL;
659
660 leave:
661 _gcry_mpi_release (a);
662 _gcry_mpi_release (x);
663 _gcry_mpi_release (y);
664 return rc;
665 }
666
667
668 /* Compute an EdDSA signature. See:
669 * [ed25519] 23pp. (PDF) Daniel J. Bernstein, Niels Duif, Tanja
670 * Lange, Peter Schwabe, Bo-Yin Yang. High-speed high-security
671 * signatures. Journal of Cryptographic Engineering 2 (2012), 77-89.
672 * Document ID: a1a62a2f76d23f65d622484ddd09caf8.
673 * URL: http://cr.yp.to/papers.html#ed25519. Date: 2011.09.26.
674 *
675 * Despite that this function requires the specification of a hash
676 * algorithm, we only support what has been specified by the paper.
677 * This may change in the future.
678 *
679 * Return the signature struct (r,s) from the message hash. The caller
680 * must have allocated R_R and S.
681 */
682
683 /* String to be used with Ed448 */
684 #define DOM25519 "SigEd25519 no Ed25519 collisions"
685 #define DOM25519_LEN 32
686 #define DOM448 "SigEd448"
687 #define DOM448_LEN 8
688
689 gpg_err_code_t
_gcry_ecc_eddsa_sign(gcry_mpi_t input,mpi_ec_t ec,gcry_mpi_t r_r,gcry_mpi_t s,struct pk_encoding_ctx * ctx)690 _gcry_ecc_eddsa_sign (gcry_mpi_t input, mpi_ec_t ec,
691 gcry_mpi_t r_r, gcry_mpi_t s,
692 struct pk_encoding_ctx *ctx)
693 {
694 int rc;
695 unsigned int tmp;
696 unsigned char *digest = NULL;
697 const void *mbuf;
698 size_t mlen;
699 unsigned char *rawmpi = NULL;
700 unsigned int rawmpilen;
701 unsigned char *encpk = NULL; /* Encoded public key. */
702 unsigned int encpklen;
703 mpi_point_struct I; /* Intermediate value. */
704 gcry_mpi_t a, x, y, r;
705 int b;
706 unsigned char x_olen[2];
707 unsigned char prehashed_msg[64];
708
709 b = (ec->nbits+7)/8;
710
711 if (ec->nbits == 255)
712 ;
713 else if (ec->nbits == 448)
714 b++;
715 else
716 return GPG_ERR_NOT_IMPLEMENTED;
717
718 if (!mpi_is_opaque (input))
719 return GPG_ERR_INV_DATA;
720
721 /* Initialize some helpers. */
722 point_init (&I);
723 a = mpi_snew (0);
724 x = mpi_new (0);
725 y = mpi_new (0);
726 r = mpi_snew (0);
727
728 rc = _gcry_ecc_eddsa_compute_h_d (&digest, ec);
729 if (rc)
730 goto leave;
731 _gcry_mpi_set_buffer (a, digest, b, 0);
732
733 /* Compute the public key if it's not available (only secret part). */
734 if (ec->Q == NULL)
735 {
736 mpi_point_struct Q;
737
738 point_init (&Q);
739 _gcry_mpi_ec_mul_point (&Q, a, ec->G, ec);
740 ec->Q = mpi_point_snatch_set (NULL, Q.x, Q.y, Q.z);
741 }
742 rc = _gcry_ecc_eddsa_encodepoint (ec->Q, ec, x, y, 0, &encpk, &encpklen);
743 if (rc)
744 goto leave;
745 if (DBG_CIPHER)
746 log_printhex (" e_pk", encpk, encpklen);
747
748 /* Compute R. */
749 mbuf = mpi_get_opaque (input, &tmp);
750 mlen = (tmp +7)/8;
751 if (DBG_CIPHER)
752 log_printhex (" m", mbuf, mlen);
753
754 if (ctx->hash_algo == GCRY_MD_SHAKE256)
755 {
756 gcry_error_t err;
757 gcry_md_hd_t hd;
758
759 err = _gcry_md_open (&hd, ctx->hash_algo, 0);
760 if (err)
761 rc = gcry_err_code (err);
762 else
763 {
764 _gcry_md_write (hd, DOM448, DOM448_LEN);
765 x_olen[0] = !!(ctx->flags & PUBKEY_FLAG_PREHASH);
766 x_olen[1] = ctx->labellen;
767 _gcry_md_write (hd, x_olen, 2);
768 if (ctx->labellen)
769 _gcry_md_write (hd, ctx->label, ctx->labellen);
770 _gcry_md_write (hd, digest+b, b);
771 if ((ctx->flags & PUBKEY_FLAG_PREHASH))
772 {
773 gcry_md_hd_t hd2;
774
775 err = _gcry_md_open (&hd2, ctx->hash_algo, 0);
776 if (err)
777 {
778 rc = gcry_err_code (err);
779 _gcry_md_close (hd);
780 goto leave;
781 }
782 _gcry_md_write (hd2, mbuf, mlen);
783 _gcry_md_ctl (hd2, GCRYCTL_FINALIZE, NULL, 0);
784 _gcry_md_extract (hd2, GCRY_MD_SHAKE256, prehashed_msg, 64);
785 _gcry_md_close (hd2);
786 _gcry_md_write (hd, prehashed_msg, 64);
787 }
788 else
789 _gcry_md_write (hd, mbuf, mlen);
790 _gcry_md_ctl (hd, GCRYCTL_FINALIZE, NULL, 0);
791 _gcry_md_extract (hd, GCRY_MD_SHAKE256, digest, 2*b);
792 _gcry_md_close (hd);
793 rc = 0;
794 }
795 }
796 else
797 {
798 gcry_buffer_t hvec[6];
799 int i = 0;
800
801 memset (hvec, 0, sizeof hvec);
802
803 if ((ctx->flags & PUBKEY_FLAG_PREHASH) || ctx->labellen)
804 {
805 hvec[i].data = (void *)DOM25519;
806 hvec[i].len = DOM25519_LEN;
807 i++;
808 x_olen[0] = !!(ctx->flags & PUBKEY_FLAG_PREHASH);
809 x_olen[1] = ctx->labellen;
810 hvec[i].data = x_olen;
811 hvec[i].len = 2;
812 i++;
813 if (ctx->labellen)
814 {
815 hvec[i].data = ctx->label;
816 hvec[i].len = ctx->labellen;
817 i++;
818 }
819 }
820
821 hvec[i].data = digest;
822 hvec[i].off = b;
823 hvec[i].len = b;
824 i++;
825 if ((ctx->flags & PUBKEY_FLAG_PREHASH))
826 {
827 _gcry_md_hash_buffer (ctx->hash_algo, prehashed_msg, mbuf, mlen);
828 hvec[i].data = (char*)prehashed_msg;
829 hvec[i].len = 64;
830 }
831 else
832 {
833 hvec[i].data = (char*)mbuf;
834 hvec[i].len = mlen;
835 }
836 i++;
837 rc = _gcry_md_hash_buffers (ctx->hash_algo, 0, digest, hvec, i);
838 }
839
840 if (rc)
841 goto leave;
842 reverse_buffer (digest, 2*b);
843 if (DBG_CIPHER)
844 log_printhex (" r", digest, 2*b);
845 _gcry_mpi_set_buffer (r, digest, 2*b, 0);
846 mpi_mod (r, r, ec->n);
847 _gcry_mpi_ec_mul_point (&I, r, ec->G, ec);
848 if (DBG_CIPHER)
849 log_printpnt (" r", &I, ec);
850
851 /* Convert R into affine coordinates and apply encoding. */
852 rc = _gcry_ecc_eddsa_encodepoint (&I, ec, x, y, 0, &rawmpi, &rawmpilen);
853 if (rc)
854 goto leave;
855 if (DBG_CIPHER)
856 log_printhex (" e_r", rawmpi, rawmpilen);
857
858 if (ctx->hash_algo == GCRY_MD_SHAKE256)
859 {
860 gcry_error_t err;
861 gcry_md_hd_t hd;
862
863 err = _gcry_md_open (&hd, ctx->hash_algo, 0);
864 if (err)
865 rc = gcry_err_code (err);
866 else
867 {
868 _gcry_md_write (hd, DOM448, DOM448_LEN);
869 x_olen[0] = !!(ctx->flags & PUBKEY_FLAG_PREHASH);
870 x_olen[1] = ctx->labellen;
871 _gcry_md_write (hd, x_olen, 2);
872 if (ctx->labellen)
873 _gcry_md_write (hd, ctx->label, ctx->labellen);
874 _gcry_md_write (hd, rawmpi, rawmpilen);
875 _gcry_md_write (hd, encpk, encpklen);
876 if ((ctx->flags & PUBKEY_FLAG_PREHASH))
877 _gcry_md_write (hd, prehashed_msg, 64);
878 else
879 _gcry_md_write (hd, mbuf, mlen);
880 _gcry_md_ctl (hd, GCRYCTL_FINALIZE, NULL, 0);
881 _gcry_md_extract (hd, GCRY_MD_SHAKE256, digest, 2*b);
882 _gcry_md_close (hd);
883 rc = 0;
884 }
885 }
886 else
887 {
888 gcry_buffer_t hvec[6];
889 int i = 0;
890
891 memset (hvec, 0, sizeof hvec);
892
893 if ((ctx->flags & PUBKEY_FLAG_PREHASH) || ctx->labellen)
894 {
895 hvec[i].data = (void *)DOM25519;
896 hvec[i].len = DOM25519_LEN;
897 i++;
898 x_olen[0] = !!(ctx->flags & PUBKEY_FLAG_PREHASH);
899 x_olen[1] = ctx->labellen;
900 hvec[i].data = x_olen;
901 hvec[i].len = 2;
902 i++;
903 if (ctx->labellen)
904 {
905 hvec[i].data = ctx->label;
906 hvec[i].len = ctx->labellen;
907 i++;
908 }
909 }
910
911 /* S = r + a * H(dom2(F,C)+encodepoint(R)+encodepoint(pk)+m) mod n */
912 hvec[i].data = rawmpi; /* (this is R) */
913 hvec[i].len = rawmpilen;
914 i++;
915 hvec[i].data = encpk;
916 hvec[i].len = encpklen;
917 i++;
918 if ((ctx->flags & PUBKEY_FLAG_PREHASH))
919 {
920 hvec[i].data = (char*)prehashed_msg;
921 hvec[i].len = 64;
922 }
923 else
924 {
925 hvec[i].data = (char*)mbuf;
926 hvec[i].len = mlen;
927 }
928 i++;
929 rc = _gcry_md_hash_buffers (ctx->hash_algo, 0, digest, hvec, i);
930 }
931
932 if (rc)
933 goto leave;
934
935 /* No more need for RAWMPI thus we now transfer it to R_R. */
936 mpi_set_opaque (r_r, rawmpi, rawmpilen*8);
937 rawmpi = NULL;
938
939 reverse_buffer (digest, 2*b);
940 if (DBG_CIPHER)
941 log_printhex (" H(R+)", digest, 2*b);
942 _gcry_mpi_set_buffer (s, digest, 2*b, 0);
943 mpi_mulm (s, s, a, ec->n);
944 mpi_addm (s, s, r, ec->n);
945 rc = eddsa_encodempi (s, ec->nbits, &rawmpi, &rawmpilen);
946 if (rc)
947 goto leave;
948 if (DBG_CIPHER)
949 log_printhex (" e_s", rawmpi, rawmpilen);
950 mpi_set_opaque (s, rawmpi, rawmpilen*8);
951 rawmpi = NULL;
952
953 rc = 0;
954
955 leave:
956 _gcry_mpi_release (a);
957 _gcry_mpi_release (x);
958 _gcry_mpi_release (y);
959 _gcry_mpi_release (r);
960 xfree (digest);
961 point_free (&I);
962 xfree (encpk);
963 xfree (rawmpi);
964 return rc;
965 }
966
967
968 /* Verify an EdDSA signature. See sign_eddsa for the reference.
969 * Check if R_IN and S_IN verifies INPUT.
970 */
971 gpg_err_code_t
_gcry_ecc_eddsa_verify(gcry_mpi_t input,mpi_ec_t ec,gcry_mpi_t r_in,gcry_mpi_t s_in,struct pk_encoding_ctx * ctx)972 _gcry_ecc_eddsa_verify (gcry_mpi_t input, mpi_ec_t ec,
973 gcry_mpi_t r_in, gcry_mpi_t s_in,
974 struct pk_encoding_ctx *ctx)
975 {
976 int rc;
977 int b;
978 unsigned int tmp;
979 unsigned char *encpk = NULL; /* Encoded public key. */
980 unsigned int encpklen;
981 const void *mbuf, *rbuf;
982 unsigned char *tbuf = NULL;
983 size_t mlen, rlen;
984 unsigned int tlen;
985 unsigned char digest[114];
986 gcry_mpi_t h, s;
987 mpi_point_struct Ia, Ib;
988 unsigned char x_olen[2];
989 unsigned char prehashed_msg[64];
990
991 if (!mpi_is_opaque (input) || !mpi_is_opaque (r_in) || !mpi_is_opaque (s_in))
992 return GPG_ERR_INV_DATA;
993
994 point_init (&Ia);
995 point_init (&Ib);
996 h = mpi_new (0);
997 s = mpi_new (0);
998
999 b = (ec->nbits+7)/8;
1000
1001 if (ec->nbits == 255)
1002 ;
1003 else if (ec->nbits == 448)
1004 b++;
1005 else
1006 return GPG_ERR_NOT_IMPLEMENTED;
1007
1008 /* Encode and check the public key. */
1009 rc = _gcry_ecc_eddsa_encodepoint (ec->Q, ec, NULL, NULL, 0,
1010 &encpk, &encpklen);
1011 if (rc)
1012 goto leave;
1013 if (!_gcry_mpi_ec_curve_point (ec->Q, ec))
1014 {
1015 rc = GPG_ERR_BROKEN_PUBKEY;
1016 goto leave;
1017 }
1018 if (DBG_CIPHER)
1019 log_printhex (" e_pk", encpk, encpklen);
1020 if (encpklen != b)
1021 {
1022 rc = GPG_ERR_INV_LENGTH;
1023 goto leave;
1024 }
1025
1026 /* Convert the other input parameters. */
1027 mbuf = mpi_get_opaque (input, &tmp);
1028 mlen = (tmp +7)/8;
1029 if (DBG_CIPHER)
1030 log_printhex (" m", mbuf, mlen);
1031 rbuf = mpi_get_opaque (r_in, &tmp);
1032 rlen = (tmp +7)/8;
1033 if (DBG_CIPHER)
1034 log_printhex (" r", rbuf, rlen);
1035 if (rlen != b)
1036 {
1037 rc = GPG_ERR_INV_LENGTH;
1038 goto leave;
1039 }
1040
1041 if (ctx->hash_algo == GCRY_MD_SHAKE256)
1042 {
1043 gcry_error_t err;
1044 gcry_md_hd_t hd;
1045
1046 err = _gcry_md_open (&hd, ctx->hash_algo, 0);
1047 if (err)
1048 rc = gcry_err_code (err);
1049 else
1050 {
1051 _gcry_md_write (hd, DOM448, DOM448_LEN);
1052 x_olen[0] = !!(ctx->flags & PUBKEY_FLAG_PREHASH);
1053 x_olen[1] = ctx->labellen;
1054 _gcry_md_write (hd, x_olen, 2);
1055 if (ctx->labellen)
1056 _gcry_md_write (hd, ctx->label, ctx->labellen);
1057 _gcry_md_write (hd, rbuf, rlen);
1058 _gcry_md_write (hd, encpk, encpklen);
1059 if ((ctx->flags & PUBKEY_FLAG_PREHASH))
1060 {
1061 gcry_md_hd_t hd2;
1062
1063 err = _gcry_md_open (&hd2, ctx->hash_algo, 0);
1064 if (err)
1065 {
1066 rc = gcry_err_code (err);
1067 _gcry_md_close (hd);
1068 goto leave;
1069 }
1070 _gcry_md_write (hd2, mbuf, mlen);
1071 _gcry_md_ctl (hd2, GCRYCTL_FINALIZE, NULL, 0);
1072 _gcry_md_extract (hd2, GCRY_MD_SHAKE256, prehashed_msg, 64);
1073 _gcry_md_close (hd2);
1074 _gcry_md_write (hd, prehashed_msg, 64);
1075 }
1076 else
1077 _gcry_md_write (hd, mbuf, mlen);
1078 _gcry_md_ctl (hd, GCRYCTL_FINALIZE, NULL, 0);
1079 _gcry_md_extract (hd, GCRY_MD_SHAKE256, digest, 2*b);
1080 _gcry_md_close (hd);
1081 rc = 0;
1082 }
1083 }
1084 else
1085 {
1086 gcry_buffer_t hvec[6];
1087 int i = 0;
1088
1089 memset (hvec, 0, sizeof hvec);
1090
1091 /* h = H(dom2(F,C)+encodepoint(R)+encodepoint(pk)+m) */
1092 if ((ctx->flags & PUBKEY_FLAG_PREHASH) || ctx->labellen)
1093 {
1094 hvec[i].data = (void *)DOM25519;
1095 hvec[i].len = DOM25519_LEN;
1096 i++;
1097 x_olen[0] = !!(ctx->flags & PUBKEY_FLAG_PREHASH);
1098 x_olen[1] = ctx->labellen;
1099 hvec[i].data = x_olen;
1100 hvec[i].len = 2;
1101 i++;
1102 if (ctx->labellen)
1103 {
1104 hvec[i].data = ctx->label;
1105 hvec[i].len = ctx->labellen;
1106 i++;
1107 }
1108 }
1109
1110 hvec[i].data = (char*)rbuf;
1111 hvec[i].len = rlen;
1112 i++;
1113 hvec[i].data = encpk;
1114 hvec[i].len = encpklen;
1115 i++;
1116 if ((ctx->flags & PUBKEY_FLAG_PREHASH))
1117 {
1118 _gcry_md_hash_buffer (ctx->hash_algo, prehashed_msg, mbuf, mlen);
1119 hvec[i].data = (char*)prehashed_msg;
1120 hvec[i].len = 64;
1121 }
1122 else
1123 {
1124 hvec[i].data = (char*)mbuf;
1125 hvec[i].len = mlen;
1126 }
1127 i++;
1128 rc = _gcry_md_hash_buffers (ctx->hash_algo, 0, digest, hvec, i);
1129 }
1130
1131 if (rc)
1132 goto leave;
1133 reverse_buffer (digest, 2*b);
1134 if (DBG_CIPHER)
1135 log_printhex (" H(R+)", digest, 2*b);
1136 _gcry_mpi_set_buffer (h, digest, 2*b, 0);
1137
1138 /* According to the paper the best way for verification is:
1139 encodepoint(sG - h·Q) = encodepoint(r)
1140 because we don't need to decode R. */
1141 {
1142 void *sbuf;
1143 unsigned int slen;
1144
1145 sbuf = _gcry_mpi_get_opaque_copy (s_in, &tmp);
1146 slen = (tmp +7)/8;
1147 reverse_buffer (sbuf, slen);
1148 if (DBG_CIPHER)
1149 log_printhex (" s", sbuf, slen);
1150 _gcry_mpi_set_buffer (s, sbuf, slen, 0);
1151 xfree (sbuf);
1152 if (slen != b)
1153 {
1154 rc = GPG_ERR_INV_LENGTH;
1155 goto leave;
1156 }
1157 }
1158
1159 _gcry_mpi_ec_mul_point (&Ia, s, ec->G, ec);
1160 _gcry_mpi_ec_mul_point (&Ib, h, ec->Q, ec);
1161 _gcry_mpi_sub (Ib.x, ec->p, Ib.x);
1162 _gcry_mpi_ec_add_points (&Ia, &Ia, &Ib, ec);
1163 rc = _gcry_ecc_eddsa_encodepoint (&Ia, ec, s, h, 0, &tbuf, &tlen);
1164 if (rc)
1165 goto leave;
1166 if (tlen != rlen || memcmp (tbuf, rbuf, tlen))
1167 {
1168 rc = GPG_ERR_BAD_SIGNATURE;
1169 goto leave;
1170 }
1171
1172 rc = 0;
1173
1174 leave:
1175 xfree (encpk);
1176 xfree (tbuf);
1177 _gcry_mpi_release (s);
1178 _gcry_mpi_release (h);
1179 point_free (&Ia);
1180 point_free (&Ib);
1181 return rc;
1182 }
1183