Add crypto hash SM3.
[libgcrypt.git] / cipher / ecc-eddsa.c
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 \f
35 static void
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
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 \f
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 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   rawmpi = _gcry_mpi_get_buffer (mpi, minlen, &rawmpilen, NULL);
76   if (!rawmpi)
77     return gpg_err_code_from_syserror ();
78
79   *r_buffer = rawmpi;
80   *r_buflen = rawmpilen;
81   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 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   int off = with_prefix? 1:0;
98
99   rawmpi = _gcry_mpi_get_buffer_extra (y, minlen, off?-1:0, &rawmpilen, NULL);
100   if (!rawmpi)
101     return gpg_err_code_from_syserror ();
102   if (mpi_test_bit (x, 0) && rawmpilen)
103     rawmpi[off + rawmpilen - 1] |= 0x80;  /* Set sign bit.  */
104   if (off)
105     rawmpi[0] = 0x40;
106
107   *r_buffer = rawmpi;
108   *r_buflen = rawmpilen + off;
109   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 _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   x = x_in? x_in : mpi_new (0);
128   y = y_in? y_in : mpi_new (0);
129
130   if (_gcry_mpi_ec_get_affine (x, y, point, ec))
131     {
132       log_error ("eddsa_encodepoint: Failed to get affine coordinates\n");
133       rc = GPG_ERR_INTERNAL;
134     }
135   else
136     rc = eddsa_encode_x_y (x, y, ec->nbits/8, with_prefix, r_buffer, r_buflen);
137
138   if (!x_in)
139     mpi_free (x);
140   if (!y_in)
141     mpi_free (y);
142   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 _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   if (!mpi_is_opaque (value))
159     return GPG_ERR_INV_OBJ;
160   buf = mpi_get_opaque (value, &rawmpilen);
161   if (!buf)
162     return GPG_ERR_INV_OBJ;
163   rawmpilen = (rawmpilen + 7)/8;
164
165   if (rawmpilen > 1 && (rawmpilen%2))
166     {
167       if (buf[0] == 0x04)
168         {
169           /* Buffer is in SEC1 uncompressed format.  Extract y and
170              compress.  */
171           rc = _gcry_mpi_scan (&x, GCRYMPI_FMT_STD,
172                                buf+1, (rawmpilen-1)/2, NULL);
173           if (rc)
174             return rc;
175           rc = _gcry_mpi_scan (&y, GCRYMPI_FMT_STD,
176                                buf+1+(rawmpilen-1)/2, (rawmpilen-1)/2, NULL);
177           if (rc)
178             {
179               mpi_free (x);
180               return rc;
181             }
182
183           rc = eddsa_encode_x_y (x, y, nbits/8, 0, &enc, &enclen);
184           mpi_free (x);
185           mpi_free (y);
186           if (rc)
187             return rc;
188
189           mpi_set_opaque (value, enc, 8*enclen);
190         }
191       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           if (!_gcry_mpi_set_opaque_copy (value, buf + 1, (rawmpilen - 1)*8))
197             return gpg_err_code_from_syserror ();
198         }
199     }
200
201   return 0;
202 }
203
204
205 /* Recover X from Y and SIGN (which actually is a parity bit).  */
206 gpg_err_code_t
207 _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign, mpi_ec_t ec)
208 {
209   gpg_err_code_t rc = 0;
210   gcry_mpi_t u, v, v3, t;
211   static gcry_mpi_t p58, seven;
212
213   if (ec->dialect != ECC_DIALECT_ED25519)
214     return GPG_ERR_NOT_IMPLEMENTED;
215
216   if (!p58)
217     p58 = scanval ("0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
218                    "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD");
219   if (!seven)
220     seven = mpi_set_ui (NULL, 7);
221
222   u   = mpi_new (0);
223   v   = 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_add_ui (v, v, 1);
236
237   /* Compute sqrt(u/v) */
238   /* v3 = v^3 */
239   mpi_powm (v3, v, mpi_const (MPI_C_THREE), ec->p);
240   /* t = v3 * v3 * u * v = u * v^7 */
241   mpi_powm (t, v, seven, ec->p);
242   mpi_mulm (t, t, u, ec->p);
243   /* t = t^((p-5)/8) = (u * v^7)^((p-5)/8)  */
244   mpi_powm (t, t, p58, ec->p);
245   /* x = t * u * v^3 = (u * v^3) * (u * v^7)^((p-5)/8) */
246   mpi_mulm (t, t, u, ec->p);
247   mpi_mulm (x, t, v3, ec->p);
248
249   /* Adjust if needed.  */
250   /* t = v * x^2  */
251   mpi_mulm (t, x, x, ec->p);
252   mpi_mulm (t, t, v, ec->p);
253   /* -t == u ? x = x * sqrt(-1) */
254   mpi_sub (t, ec->p, t);
255   if (!mpi_cmp (t, u))
256     {
257       static gcry_mpi_t m1;  /* Fixme: this is not thread-safe.  */
258       if (!m1)
259         m1 = scanval ("2B8324804FC1DF0B2B4D00993DFBD7A7"
260                       "2F431806AD2FE478C4EE1B274A0EA0B0");
261       mpi_mulm (x, x, m1, ec->p);
262       /* t = v * x^2  */
263       mpi_mulm (t, x, x, ec->p);
264       mpi_mulm (t, t, v, ec->p);
265       /* -t == u ? x = x * sqrt(-1) */
266       mpi_sub (t, ec->p, t);
267       if (!mpi_cmp (t, u))
268         rc = GPG_ERR_INV_OBJ;
269     }
270
271   /* Choose the desired square root according to parity */
272   if (mpi_test_bit (x, 0) != !!sign)
273     mpi_sub (x, ec->p, x);
274
275   mpi_free (t);
276   mpi_free (v3);
277   mpi_free (v);
278   mpi_free (u);
279
280   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 _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   if (mpi_is_opaque (pk))
300     {
301       const unsigned char *buf;
302
303       buf = mpi_get_opaque (pk, &rawmpilen);
304       if (!buf)
305         return GPG_ERR_INV_OBJ;
306       rawmpilen = (rawmpilen + 7)/8;
307
308       /* Handle compression prefixes.  The size of the buffer will be
309          odd in this case.  */
310       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           if (buf[0] == 0x04)
316             {
317               gcry_mpi_t x, y;
318
319               rc = _gcry_mpi_scan (&x, GCRYMPI_FMT_STD,
320                                    buf+1, (rawmpilen-1)/2, NULL);
321               if (rc)
322                 return rc;
323               rc = _gcry_mpi_scan (&y, GCRYMPI_FMT_STD,
324                                    buf+1+(rawmpilen-1)/2, (rawmpilen-1)/2,NULL);
325               if (rc)
326                 {
327                   mpi_free (x);
328                   return rc;
329                 }
330
331               if (r_encpk)
332                 {
333                   rc = eddsa_encode_x_y (x, y, ctx->nbits/8, 0,
334                                          r_encpk, r_encpklen);
335                   if (rc)
336                     {
337                       mpi_free (x);
338                       mpi_free (y);
339                       return rc;
340                     }
341                 }
342               mpi_snatch (result->x, x);
343               mpi_snatch (result->y, y);
344               mpi_set_ui (result->z, 1);
345               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           if (buf[0] == 0x40)
352             {
353               rawmpilen--;
354               buf++;
355             }
356         }
357
358       /* EdDSA compressed point.  */
359       rawmpi = xtrymalloc (rawmpilen? rawmpilen:1);
360       if (!rawmpi)
361         return gpg_err_code_from_syserror ();
362       memcpy (rawmpi, buf, rawmpilen);
363       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       rawmpi = _gcry_mpi_get_buffer (pk, ctx->nbits/8, &rawmpilen, NULL);
371       if (!rawmpi)
372         return gpg_err_code_from_syserror ();
373     }
374
375   if (rawmpilen)
376     {
377       sign = !!(rawmpi[0] & 0x80);
378       rawmpi[0] &= 0x7f;
379     }
380   else
381     sign = 0;
382   _gcry_mpi_set_buffer (result->y, rawmpi, rawmpilen, 0);
383   if (r_encpk)
384     {
385       /* Revert to little endian.  */
386       if (sign && rawmpilen)
387         rawmpi[0] |= 0x80;
388       reverse_buffer (rawmpi, rawmpilen);
389       *r_encpk = rawmpi;
390       if (r_encpklen)
391         *r_encpklen = rawmpilen;
392     }
393   else
394     xfree (rawmpi);
395
396   rc = _gcry_ecc_eddsa_recover_x (result->x, result->y, sign, ctx);
397   mpi_set_ui (result->z, 1);
398
399   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 _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   unsigned char *rawmpi = NULL;
414   unsigned int rawmpilen;
415   unsigned char *digest;
416   gcry_buffer_t hvec[2];
417   int hashalgo, b;
418
419   *r_digest = NULL;
420
421   hashalgo = GCRY_MD_SHA512;
422   if (hashalgo != GCRY_MD_SHA512)
423     return GPG_ERR_DIGEST_ALGO;
424
425   b = (ec->nbits+7)/8;
426   if (b != 256/8)
427     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   digest = xtrycalloc_secure (2, b);
432   if (!digest)
433     return gpg_err_code_from_syserror ();
434
435   memset (hvec, 0, sizeof hvec);
436
437   rawmpi = _gcry_mpi_get_buffer (d, 0, &rawmpilen, NULL);
438   if (!rawmpi)
439     {
440       xfree (digest);
441       return gpg_err_code_from_syserror ();
442     }
443
444   hvec[0].data = digest;
445   hvec[0].off = 0;
446   hvec[0].len = b > rawmpilen? b - rawmpilen : 0;
447   hvec[1].data = rawmpi;
448   hvec[1].off = 0;
449   hvec[1].len = rawmpilen;
450   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2);
451   xfree (rawmpi);
452   if (rc)
453     {
454       xfree (digest);
455       return rc;
456     }
457
458   /* Compute the A value.  */
459   reverse_buffer (digest, 32);  /* Only the first half of the hash.  */
460   digest[0]   = (digest[0] & 0x7f) | 0x40;
461   digest[31] &= 0xf8;
462
463   *r_digest = digest;
464   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 _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   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   unsigned char *hash_d = NULL;
494
495   point_init (&Q);
496   memset (hvec, 0, sizeof hvec);
497
498   if ((flags & PUBKEY_FLAG_TRANSIENT_KEY))
499     random_level = GCRY_STRONG_RANDOM;
500   else
501     random_level = GCRY_VERY_STRONG_RANDOM;
502
503   a = mpi_snew (0);
504   x = mpi_new (0);
505   y = mpi_new (0);
506
507   /* Generate a secret.  */
508   hash_d = xtrymalloc_secure (2*b);
509   if (!hash_d)
510     {
511       rc = gpg_err_code_from_syserror ();
512       goto leave;
513     }
514   dlen = b;
515   dbuf = _gcry_random_bytes_secure (dlen, random_level);
516
517   /* Compute the A value.  */
518   hvec[0].data = dbuf;
519   hvec[0].len = dlen;
520   rc = _gcry_md_hash_buffers (GCRY_MD_SHA512, 0, hash_d, hvec, 1);
521   if (rc)
522     goto leave;
523   sk->d = _gcry_mpi_set_opaque (NULL, dbuf, dlen*8);
524   dbuf = NULL;
525   reverse_buffer (hash_d, 32);  /* Only the first half of the hash.  */
526   hash_d[0] = (hash_d[0] & 0x7f) | 0x40;
527   hash_d[31] &= 0xf8;
528   _gcry_mpi_set_buffer (a, hash_d, 32, 0);
529   xfree (hash_d); hash_d = NULL;
530   /* log_printmpi ("ecgen         a", a); */
531
532   /* Compute Q.  */
533   _gcry_mpi_ec_mul_point (&Q, a, &E->G, ctx);
534   if (DBG_CIPHER)
535     log_printpnt ("ecgen      pk", &Q, ctx);
536
537   /* Copy the stuff to the key structures. */
538   sk->E.model = E->model;
539   sk->E.dialect = E->dialect;
540   sk->E.p = mpi_copy (E->p);
541   sk->E.a = mpi_copy (E->a);
542   sk->E.b = mpi_copy (E->b);
543   point_init (&sk->E.G);
544   point_set (&sk->E.G, &E->G);
545   sk->E.n = mpi_copy (E->n);
546   sk->E.h = mpi_copy (E->h);
547   point_init (&sk->Q);
548   point_set (&sk->Q, &Q);
549
550  leave:
551   point_free (&Q);
552   _gcry_mpi_release (a);
553   _gcry_mpi_release (x);
554   _gcry_mpi_release (y);
555   xfree (hash_d);
556   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 _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   mpi_ec_t ctx = NULL;
581   int b;
582   unsigned int tmp;
583   unsigned char *digest = NULL;
584   gcry_buffer_t hvec[3];
585   const void *mbuf;
586   size_t mlen;
587   unsigned char *rawmpi = NULL;
588   unsigned int rawmpilen;
589   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   memset (hvec, 0, sizeof hvec);
596
597   if (!mpi_is_opaque (input))
598     return GPG_ERR_INV_DATA;
599
600   /* Initialize some helpers.  */
601   point_init (&I);
602   point_init (&Q);
603   a = mpi_snew (0);
604   x = mpi_new (0);
605   y = mpi_new (0);
606   r = mpi_snew (0);
607   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   b = (ctx->nbits+7)/8;
610   if (b != 256/8) {
611     rc = GPG_ERR_INTERNAL; /* We only support 256 bit. */
612     goto leave;
613   }
614
615   rc = _gcry_ecc_eddsa_compute_h_d (&digest, skey->d, ctx);
616   if (rc)
617     goto leave;
618   _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   if (pk)
623     {
624       rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q,  &encpk, &encpklen);
625       if (rc)
626         goto leave;
627       if (DBG_CIPHER)
628         log_printhex ("* e_pk", encpk, encpklen);
629       if (!_gcry_mpi_ec_curve_point (&Q, ctx))
630         {
631           rc = GPG_ERR_BROKEN_PUBKEY;
632           goto leave;
633         }
634     }
635   else
636     {
637       _gcry_mpi_ec_mul_point (&Q, a, &skey->E.G, ctx);
638       rc = _gcry_ecc_eddsa_encodepoint (&Q, ctx, x, y, 0, &encpk, &encpklen);
639       if (rc)
640         goto leave;
641       if (DBG_CIPHER)
642         log_printhex ("  e_pk", encpk, encpklen);
643     }
644
645   /* Compute R.  */
646   mbuf = mpi_get_opaque (input, &tmp);
647   mlen = (tmp +7)/8;
648   if (DBG_CIPHER)
649     log_printhex ("     m", mbuf, mlen);
650
651   hvec[0].data = digest;
652   hvec[0].off  = 32;
653   hvec[0].len  = 32;
654   hvec[1].data = (char*)mbuf;
655   hvec[1].len  = mlen;
656   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2);
657   if (rc)
658     goto leave;
659   reverse_buffer (digest, 64);
660   if (DBG_CIPHER)
661     log_printhex ("     r", digest, 64);
662   _gcry_mpi_set_buffer (r, digest, 64, 0);
663   _gcry_mpi_ec_mul_point (&I, r, &skey->E.G, ctx);
664   if (DBG_CIPHER)
665     log_printpnt ("   r", &I, ctx);
666
667   /* Convert R into affine coordinates and apply encoding.  */
668   rc = _gcry_ecc_eddsa_encodepoint (&I, ctx, x, y, 0, &rawmpi, &rawmpilen);
669   if (rc)
670     goto leave;
671   if (DBG_CIPHER)
672     log_printhex ("   e_r", rawmpi, rawmpilen);
673
674   /* S = r + a * H(encodepoint(R) + encodepoint(pk) + m) mod n  */
675   hvec[0].data = rawmpi;  /* (this is R) */
676   hvec[0].off  = 0;
677   hvec[0].len  = rawmpilen;
678   hvec[1].data = encpk;
679   hvec[1].off  = 0;
680   hvec[1].len  = encpklen;
681   hvec[2].data = (char*)mbuf;
682   hvec[2].off  = 0;
683   hvec[2].len  = mlen;
684   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
685   if (rc)
686     goto leave;
687
688   /* No more need for RAWMPI thus we now transfer it to R_R.  */
689   mpi_set_opaque (r_r, rawmpi, rawmpilen*8);
690   rawmpi = NULL;
691
692   reverse_buffer (digest, 64);
693   if (DBG_CIPHER)
694     log_printhex (" H(R+)", digest, 64);
695   _gcry_mpi_set_buffer (s, digest, 64, 0);
696   mpi_mulm (s, s, a, skey->E.n);
697   mpi_addm (s, s, r, skey->E.n);
698   rc = eddsa_encodempi (s, b, &rawmpi, &rawmpilen);
699   if (rc)
700     goto leave;
701   if (DBG_CIPHER)
702     log_printhex ("   e_s", rawmpi, rawmpilen);
703   mpi_set_opaque (s, rawmpi, rawmpilen*8);
704   rawmpi = NULL;
705
706   rc = 0;
707
708  leave:
709   _gcry_mpi_release (a);
710   _gcry_mpi_release (x);
711   _gcry_mpi_release (y);
712   _gcry_mpi_release (r);
713   xfree (digest);
714   _gcry_mpi_ec_free (ctx);
715   point_free (&I);
716   point_free (&Q);
717   xfree (encpk);
718   xfree (rawmpi);
719   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 _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   mpi_ec_t ctx = NULL;
734   int b;
735   unsigned int tmp;
736   mpi_point_struct Q;          /* Public key.  */
737   unsigned char *encpk = NULL; /* Encoded public key.  */
738   unsigned int encpklen;
739   const void *mbuf, *rbuf;
740   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   if (!mpi_is_opaque (input) || !mpi_is_opaque (r_in) || !mpi_is_opaque (s_in))
749     return GPG_ERR_INV_DATA;
750   if (hashalgo != GCRY_MD_SHA512)
751     return GPG_ERR_DIGEST_ALGO;
752
753   point_init (&Q);
754   point_init (&Ia);
755   point_init (&Ib);
756   h = mpi_new (0);
757   s = mpi_new (0);
758
759   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   b = ctx->nbits/8;
762   if (b != 256/8)
763     return GPG_ERR_INTERNAL; /* We only support 256 bit. */
764
765   /* Decode and check the public key.  */
766   rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q, &encpk, &encpklen);
767   if (rc)
768     goto leave;
769   if (!_gcry_mpi_ec_curve_point (&Q, ctx))
770     {
771       rc = GPG_ERR_BROKEN_PUBKEY;
772       goto leave;
773     }
774   if (DBG_CIPHER)
775     log_printhex ("  e_pk", encpk, encpklen);
776   if (encpklen != b)
777     {
778       rc = GPG_ERR_INV_LENGTH;
779       goto leave;
780     }
781
782   /* Convert the other input parameters.  */
783   mbuf = mpi_get_opaque (input, &tmp);
784   mlen = (tmp +7)/8;
785   if (DBG_CIPHER)
786     log_printhex ("     m", mbuf, mlen);
787   rbuf = mpi_get_opaque (r_in, &tmp);
788   rlen = (tmp +7)/8;
789   if (DBG_CIPHER)
790     log_printhex ("     r", rbuf, rlen);
791   if (rlen != b)
792     {
793       rc = GPG_ERR_INV_LENGTH;
794       goto leave;
795     }
796
797   /* h = H(encodepoint(R) + encodepoint(pk) + m)  */
798   hvec[0].data = (char*)rbuf;
799   hvec[0].off  = 0;
800   hvec[0].len  = rlen;
801   hvec[1].data = encpk;
802   hvec[1].off  = 0;
803   hvec[1].len  = encpklen;
804   hvec[2].data = (char*)mbuf;
805   hvec[2].off  = 0;
806   hvec[2].len  = mlen;
807   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
808   if (rc)
809     goto leave;
810   reverse_buffer (digest, 64);
811   if (DBG_CIPHER)
812     log_printhex (" H(R+)", digest, 64);
813   _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     sbuf = _gcry_mpi_get_opaque_copy (s_in, &tmp);
823     slen = (tmp +7)/8;
824     reverse_buffer (sbuf, slen);
825     if (DBG_CIPHER)
826       log_printhex ("     s", sbuf, slen);
827     _gcry_mpi_set_buffer (s, sbuf, slen, 0);
828     xfree (sbuf);
829     if (slen != b)
830       {
831         rc = GPG_ERR_INV_LENGTH;
832         goto leave;
833       }
834   }
835
836   _gcry_mpi_ec_mul_point (&Ia, s, &pkey->E.G, ctx);
837   _gcry_mpi_ec_mul_point (&Ib, h, &Q, ctx);
838   _gcry_mpi_sub (Ib.x, ctx->p, Ib.x);
839   _gcry_mpi_ec_add_points (&Ia, &Ia, &Ib, ctx);
840   rc = _gcry_ecc_eddsa_encodepoint (&Ia, ctx, s, h, 0, &tbuf, &tlen);
841   if (rc)
842     goto leave;
843   if (tlen != rlen || memcmp (tbuf, rbuf, tlen))
844     {
845       rc = GPG_ERR_BAD_SIGNATURE;
846       goto leave;
847     }
848
849   rc = 0;
850
851  leave:
852   xfree (encpk);
853   xfree (tbuf);
854   _gcry_mpi_ec_free (ctx);
855   _gcry_mpi_release (s);
856   _gcry_mpi_release (h);
857   point_free (&Ia);
858   point_free (&Ib);
859   point_free (&Q);
860   return rc;
861 }