ecc: Add cofactor to domain parameters.
[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_neg (t, 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_neg (t, 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 /* Ed25519 version of the key generation.  */
469 gpg_err_code_t
470 _gcry_ecc_eddsa_genkey (ECC_secret_key *sk, elliptic_curve_t *E, mpi_ec_t ctx,
471                         gcry_random_level_t random_level)
472 {
473   gpg_err_code_t rc;
474   int b = 256/8;             /* The only size we currently support.  */
475   gcry_mpi_t a, x, y;
476   mpi_point_struct Q;
477   char *dbuf;
478   size_t dlen;
479   gcry_buffer_t hvec[1];
480   unsigned char *hash_d = NULL;
481
482   point_init (&Q);
483   memset (hvec, 0, sizeof hvec);
484
485   a = mpi_snew (0);
486   x = mpi_new (0);
487   y = mpi_new (0);
488
489   /* Generate a secret.  */
490   hash_d = xtrymalloc_secure (2*b);
491   if (!hash_d)
492     {
493       rc = gpg_error_from_syserror ();
494       goto leave;
495     }
496   dlen = b;
497   dbuf = _gcry_random_bytes_secure (dlen, random_level);
498
499   /* Compute the A value.  */
500   hvec[0].data = dbuf;
501   hvec[0].len = dlen;
502   rc = _gcry_md_hash_buffers (GCRY_MD_SHA512, 0, hash_d, hvec, 1);
503   if (rc)
504     goto leave;
505   sk->d = _gcry_mpi_set_opaque (NULL, dbuf, dlen*8);
506   dbuf = NULL;
507   reverse_buffer (hash_d, 32);  /* Only the first half of the hash.  */
508   hash_d[0] = (hash_d[0] & 0x7f) | 0x40;
509   hash_d[31] &= 0xf8;
510   _gcry_mpi_set_buffer (a, hash_d, 32, 0);
511   xfree (hash_d); hash_d = NULL;
512   /* log_printmpi ("ecgen         a", a); */
513
514   /* Compute Q.  */
515   _gcry_mpi_ec_mul_point (&Q, a, &E->G, ctx);
516   if (DBG_CIPHER)
517     log_printpnt ("ecgen      pk", &Q, ctx);
518
519   /* Copy the stuff to the key structures. */
520   sk->E.model = E->model;
521   sk->E.dialect = E->dialect;
522   sk->E.p = mpi_copy (E->p);
523   sk->E.a = mpi_copy (E->a);
524   sk->E.b = mpi_copy (E->b);
525   point_init (&sk->E.G);
526   point_set (&sk->E.G, &E->G);
527   sk->E.n = mpi_copy (E->n);
528   sk->E.h = mpi_copy (E->h);
529   point_init (&sk->Q);
530   point_set (&sk->Q, &Q);
531
532  leave:
533   point_free (&Q);
534   _gcry_mpi_release (a);
535   _gcry_mpi_release (x);
536   _gcry_mpi_release (y);
537   xfree (hash_d);
538   return rc;
539 }
540
541
542 /* Compute an EdDSA signature. See:
543  *   [ed25519] 23pp. (PDF) Daniel J. Bernstein, Niels Duif, Tanja
544  *   Lange, Peter Schwabe, Bo-Yin Yang. High-speed high-security
545  *   signatures.  Journal of Cryptographic Engineering 2 (2012), 77-89.
546  *   Document ID: a1a62a2f76d23f65d622484ddd09caf8.
547  *   URL: http://cr.yp.to/papers.html#ed25519. Date: 2011.09.26.
548  *
549  * Despite that this function requires the specification of a hash
550  * algorithm, we only support what has been specified by the paper.
551  * This may change in the future.  Note that we don't check the used
552  * curve; the user is responsible to use Ed25519.
553  *
554  * Return the signature struct (r,s) from the message hash.  The caller
555  * must have allocated R_R and S.
556  */
557 gpg_err_code_t
558 _gcry_ecc_eddsa_sign (gcry_mpi_t input, ECC_secret_key *skey,
559                       gcry_mpi_t r_r, gcry_mpi_t s, int hashalgo, gcry_mpi_t pk)
560 {
561   int rc;
562   mpi_ec_t ctx = NULL;
563   int b;
564   unsigned int tmp;
565   unsigned char *digest;
566   gcry_buffer_t hvec[3];
567   const void *mbuf;
568   size_t mlen;
569   unsigned char *rawmpi = NULL;
570   unsigned int rawmpilen;
571   unsigned char *encpk = NULL; /* Encoded public key.  */
572   unsigned int encpklen;
573   mpi_point_struct I;          /* Intermediate value.  */
574   mpi_point_struct Q;          /* Public key.  */
575   gcry_mpi_t a, x, y, r;
576
577   memset (hvec, 0, sizeof hvec);
578
579   if (!mpi_is_opaque (input))
580     return GPG_ERR_INV_DATA;
581
582   /* Initialize some helpers.  */
583   point_init (&I);
584   point_init (&Q);
585   a = mpi_snew (0);
586   x = mpi_new (0);
587   y = mpi_new (0);
588   r = mpi_new (0);
589   ctx = _gcry_mpi_ec_p_internal_new (skey->E.model, skey->E.dialect, 0,
590                                      skey->E.p, skey->E.a, skey->E.b);
591   b = (ctx->nbits+7)/8;
592   if (b != 256/8)
593     return GPG_ERR_INTERNAL; /* We only support 256 bit. */
594
595   rc = _gcry_ecc_eddsa_compute_h_d (&digest, skey->d, ctx);
596   if (rc)
597     goto leave;
598   _gcry_mpi_set_buffer (a, digest, 32, 0);
599
600   /* Compute the public key if it has not been supplied as optional
601      parameter.  */
602   if (pk)
603     {
604       rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q,  &encpk, &encpklen);
605       if (rc)
606         goto leave;
607       if (DBG_CIPHER)
608         log_printhex ("* e_pk", encpk, encpklen);
609       if (!_gcry_mpi_ec_curve_point (&Q, ctx))
610         {
611           rc = GPG_ERR_BROKEN_PUBKEY;
612           goto leave;
613         }
614     }
615   else
616     {
617       _gcry_mpi_ec_mul_point (&Q, a, &skey->E.G, ctx);
618       rc = _gcry_ecc_eddsa_encodepoint (&Q, ctx, x, y, 0, &encpk, &encpklen);
619       if (rc)
620         goto leave;
621       if (DBG_CIPHER)
622         log_printhex ("  e_pk", encpk, encpklen);
623     }
624
625   /* Compute R.  */
626   mbuf = mpi_get_opaque (input, &tmp);
627   mlen = (tmp +7)/8;
628   if (DBG_CIPHER)
629     log_printhex ("     m", mbuf, mlen);
630
631   hvec[0].data = digest;
632   hvec[0].off  = 32;
633   hvec[0].len  = 32;
634   hvec[1].data = (char*)mbuf;
635   hvec[1].len  = mlen;
636   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2);
637   if (rc)
638     goto leave;
639   reverse_buffer (digest, 64);
640   if (DBG_CIPHER)
641     log_printhex ("     r", digest, 64);
642   _gcry_mpi_set_buffer (r, digest, 64, 0);
643   _gcry_mpi_ec_mul_point (&I, r, &skey->E.G, ctx);
644   if (DBG_CIPHER)
645     log_printpnt ("   r", &I, ctx);
646
647   /* Convert R into affine coordinates and apply encoding.  */
648   rc = _gcry_ecc_eddsa_encodepoint (&I, ctx, x, y, 0, &rawmpi, &rawmpilen);
649   if (rc)
650     goto leave;
651   if (DBG_CIPHER)
652     log_printhex ("   e_r", rawmpi, rawmpilen);
653
654   /* S = r + a * H(encodepoint(R) + encodepoint(pk) + m) mod n  */
655   hvec[0].data = rawmpi;  /* (this is R) */
656   hvec[0].off  = 0;
657   hvec[0].len  = rawmpilen;
658   hvec[1].data = encpk;
659   hvec[1].off  = 0;
660   hvec[1].len  = encpklen;
661   hvec[2].data = (char*)mbuf;
662   hvec[2].off  = 0;
663   hvec[2].len  = mlen;
664   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
665   if (rc)
666     goto leave;
667
668   /* No more need for RAWMPI thus we now transfer it to R_R.  */
669   mpi_set_opaque (r_r, rawmpi, rawmpilen*8);
670   rawmpi = NULL;
671
672   reverse_buffer (digest, 64);
673   if (DBG_CIPHER)
674     log_printhex (" H(R+)", digest, 64);
675   _gcry_mpi_set_buffer (s, digest, 64, 0);
676   mpi_mulm (s, s, a, skey->E.n);
677   mpi_addm (s, s, r, skey->E.n);
678   rc = eddsa_encodempi (s, b, &rawmpi, &rawmpilen);
679   if (rc)
680     goto leave;
681   if (DBG_CIPHER)
682     log_printhex ("   e_s", rawmpi, rawmpilen);
683   mpi_set_opaque (s, rawmpi, rawmpilen*8);
684   rawmpi = NULL;
685
686   rc = 0;
687
688  leave:
689   _gcry_mpi_release (a);
690   _gcry_mpi_release (x);
691   _gcry_mpi_release (y);
692   _gcry_mpi_release (r);
693   xfree (digest);
694   _gcry_mpi_ec_free (ctx);
695   point_free (&I);
696   point_free (&Q);
697   xfree (encpk);
698   xfree (rawmpi);
699   return rc;
700 }
701
702
703 /* Verify an EdDSA signature.  See sign_eddsa for the reference.
704  * Check if R_IN and S_IN verifies INPUT.  PKEY has the curve
705  * parameters and PK is the EdDSA style encoded public key.
706  */
707 gpg_err_code_t
708 _gcry_ecc_eddsa_verify (gcry_mpi_t input, ECC_public_key *pkey,
709                         gcry_mpi_t r_in, gcry_mpi_t s_in, int hashalgo,
710                         gcry_mpi_t pk)
711 {
712   int rc;
713   mpi_ec_t ctx = NULL;
714   int b;
715   unsigned int tmp;
716   mpi_point_struct Q;          /* Public key.  */
717   unsigned char *encpk = NULL; /* Encoded public key.  */
718   unsigned int encpklen;
719   const void *mbuf, *rbuf;
720   unsigned char *tbuf = NULL;
721   size_t mlen, rlen;
722   unsigned int tlen;
723   unsigned char digest[64];
724   gcry_buffer_t hvec[3];
725   gcry_mpi_t h, s;
726   mpi_point_struct Ia, Ib;
727
728   if (!mpi_is_opaque (input) || !mpi_is_opaque (r_in) || !mpi_is_opaque (s_in))
729     return GPG_ERR_INV_DATA;
730   if (hashalgo != GCRY_MD_SHA512)
731     return GPG_ERR_DIGEST_ALGO;
732
733   point_init (&Q);
734   point_init (&Ia);
735   point_init (&Ib);
736   h = mpi_new (0);
737   s = mpi_new (0);
738
739   ctx = _gcry_mpi_ec_p_internal_new (pkey->E.model, pkey->E.dialect, 0,
740                                      pkey->E.p, pkey->E.a, pkey->E.b);
741   b = ctx->nbits/8;
742   if (b != 256/8)
743     return GPG_ERR_INTERNAL; /* We only support 256 bit. */
744
745   /* Decode and check the public key.  */
746   rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q, &encpk, &encpklen);
747   if (rc)
748     goto leave;
749   if (!_gcry_mpi_ec_curve_point (&Q, ctx))
750     {
751       rc = GPG_ERR_BROKEN_PUBKEY;
752       goto leave;
753     }
754   if (DBG_CIPHER)
755     log_printhex ("  e_pk", encpk, encpklen);
756   if (encpklen != b)
757     {
758       rc = GPG_ERR_INV_LENGTH;
759       goto leave;
760     }
761
762   /* Convert the other input parameters.  */
763   mbuf = mpi_get_opaque (input, &tmp);
764   mlen = (tmp +7)/8;
765   if (DBG_CIPHER)
766     log_printhex ("     m", mbuf, mlen);
767   rbuf = mpi_get_opaque (r_in, &tmp);
768   rlen = (tmp +7)/8;
769   if (DBG_CIPHER)
770     log_printhex ("     r", rbuf, rlen);
771   if (rlen != b)
772     {
773       rc = GPG_ERR_INV_LENGTH;
774       goto leave;
775     }
776
777   /* h = H(encodepoint(R) + encodepoint(pk) + m)  */
778   hvec[0].data = (char*)rbuf;
779   hvec[0].off  = 0;
780   hvec[0].len  = rlen;
781   hvec[1].data = encpk;
782   hvec[1].off  = 0;
783   hvec[1].len  = encpklen;
784   hvec[2].data = (char*)mbuf;
785   hvec[2].off  = 0;
786   hvec[2].len  = mlen;
787   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
788   if (rc)
789     goto leave;
790   reverse_buffer (digest, 64);
791   if (DBG_CIPHER)
792     log_printhex (" H(R+)", digest, 64);
793   _gcry_mpi_set_buffer (h, digest, 64, 0);
794
795   /* According to the paper the best way for verification is:
796          encodepoint(sG - h·Q) = encodepoint(r)
797      because we don't need to decode R. */
798   {
799     void *sbuf;
800     unsigned int slen;
801
802     sbuf = _gcry_mpi_get_opaque_copy (s_in, &tmp);
803     slen = (tmp +7)/8;
804     reverse_buffer (sbuf, slen);
805     if (DBG_CIPHER)
806       log_printhex ("     s", sbuf, slen);
807     _gcry_mpi_set_buffer (s, sbuf, slen, 0);
808     xfree (sbuf);
809     if (slen != b)
810       {
811         rc = GPG_ERR_INV_LENGTH;
812         goto leave;
813       }
814   }
815
816   _gcry_mpi_ec_mul_point (&Ia, s, &pkey->E.G, ctx);
817   _gcry_mpi_ec_mul_point (&Ib, h, &Q, ctx);
818   _gcry_mpi_neg (Ib.x, Ib.x);
819   _gcry_mpi_ec_add_points (&Ia, &Ia, &Ib, ctx);
820   rc = _gcry_ecc_eddsa_encodepoint (&Ia, ctx, s, h, 0, &tbuf, &tlen);
821   if (rc)
822     goto leave;
823   if (tlen != rlen || memcmp (tbuf, rbuf, tlen))
824     {
825       rc = GPG_ERR_BAD_SIGNATURE;
826       goto leave;
827     }
828
829   rc = 0;
830
831  leave:
832   xfree (encpk);
833   xfree (tbuf);
834   _gcry_mpi_ec_free (ctx);
835   _gcry_mpi_release (s);
836   _gcry_mpi_release (h);
837   point_free (&Ia);
838   point_free (&Ib);
839   point_free (&Q);
840   return rc;
841 }