29145f8274e5411e3af49473cab4c8fcbbdc4589
[libgcrypt.git] / cipher / ecc-eddsa.c
1 /* ecc-eddsa.c  -  Elliptic Curve EdDSA signatures
2  * Copyright (C) 2013 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_error_t err;
54   gcry_mpi_t val;
55
56   err = gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL);
57   if (err)
58     log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (err));
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.  On success 0 is returned and a malloced
87    buffer with the encoded point is stored at R_BUFFER; the length of
88    this buffer is stored at R_BUFLEN.  */
89 static gpg_err_code_t
90 eddsa_encode_x_y (gcry_mpi_t x, gcry_mpi_t y, unsigned int minlen,
91                   unsigned char **r_buffer, unsigned int *r_buflen)
92 {
93   unsigned char *rawmpi;
94   unsigned int rawmpilen;
95
96   rawmpi = _gcry_mpi_get_buffer (y, minlen, &rawmpilen, NULL);
97   if (!rawmpi)
98     return gpg_err_code_from_syserror ();
99   if (mpi_test_bit (x, 0) && rawmpilen)
100     rawmpi[rawmpilen - 1] |= 0x80;  /* Set sign bit.  */
101
102   *r_buffer = rawmpi;
103   *r_buflen = rawmpilen;
104   return 0;
105 }
106
107 /* Encode POINT using the EdDSA scheme.  X and Y are either scratch
108    variables supplied by the caller or NULL.  CTX is the usual
109    context.  On success 0 is returned and a malloced buffer with the
110    encoded point is stored at R_BUFFER; the length of this buffer is
111    stored at R_BUFLEN.  */
112 gpg_err_code_t
113 _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ec,
114                              gcry_mpi_t x_in, gcry_mpi_t y_in,
115                              unsigned char **r_buffer, unsigned int *r_buflen)
116 {
117   gpg_err_code_t rc;
118   gcry_mpi_t x, y;
119
120   x = x_in? x_in : mpi_new (0);
121   y = y_in? y_in : mpi_new (0);
122
123   if (_gcry_mpi_ec_get_affine (x, y, point, ec))
124     {
125       log_error ("eddsa_encodepoint: Failed to get affine coordinates\n");
126       rc = GPG_ERR_INTERNAL;
127     }
128   else
129     rc = eddsa_encode_x_y (x, y, ec->nbits/8, r_buffer, r_buflen);
130
131   if (!x_in)
132     mpi_free (x);
133   if (!y_in)
134     mpi_free (y);
135   return rc;
136 }
137
138
139 /* Make sure that the opaque MPI VALUE is in compact EdDSA format.
140    This function updates MPI if needed.  */
141 gpg_err_code_t
142 _gcry_ecc_eddsa_ensure_compact (gcry_mpi_t value, unsigned int nbits)
143 {
144   gpg_err_code_t rc;
145   const unsigned char *buf;
146   unsigned int rawmpilen;
147   gcry_mpi_t x, y;
148   unsigned char *enc;
149   unsigned int enclen;
150
151   if (!mpi_is_opaque (value))
152     return GPG_ERR_INV_OBJ;
153   buf = gcry_mpi_get_opaque (value, &rawmpilen);
154   if (!buf)
155     return GPG_ERR_INV_OBJ;
156   rawmpilen = (rawmpilen + 7)/8;
157
158   /* Check whether the public key has been given in standard
159      uncompressed format.  In this case extract y and compress.  */
160   if (rawmpilen > 1 && buf[0] == 0x04 && (rawmpilen%2))
161     {
162       rc = gcry_mpi_scan (&x, GCRYMPI_FMT_STD,
163                           buf+1, (rawmpilen-1)/2, NULL);
164       if (rc)
165         return rc;
166       rc = gcry_mpi_scan (&y, GCRYMPI_FMT_STD,
167                           buf+1+(rawmpilen-1)/2, (rawmpilen-1)/2, NULL);
168       if (rc)
169         {
170           mpi_free (x);
171           return rc;
172         }
173
174       rc = eddsa_encode_x_y (x, y, nbits/8, &enc, &enclen);
175       mpi_free (x);
176       mpi_free (y);
177       if (rc)
178         return rc;
179
180       gcry_mpi_set_opaque (value, enc, 8*enclen);
181     }
182
183   return 0;
184 }
185
186
187 /* Recover X from Y and SIGN (which actually is a parity bit).  */
188 gpg_err_code_t
189 _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign, mpi_ec_t ec)
190 {
191   gpg_err_code_t rc = 0;
192   gcry_mpi_t u, v, v3, t;
193   static gcry_mpi_t p58, seven;
194
195   if (ec->dialect != ECC_DIALECT_ED25519)
196     return GPG_ERR_NOT_IMPLEMENTED;
197
198   if (!p58)
199     p58 = scanval ("0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
200                    "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD");
201   if (!seven)
202     seven = mpi_set_ui (NULL, 7);
203
204   u   = mpi_new (0);
205   v   = mpi_new (0);
206   v3  = mpi_new (0);
207   t   = mpi_new (0);
208
209   /* Compute u and v */
210   /* u = y^2    */
211   mpi_mulm (u, y, y, ec->p);
212   /* v = b*y^2   */
213   mpi_mulm (v, ec->b, u, ec->p);
214   /* u = y^2-1  */
215   mpi_sub_ui (u, u, 1);
216   /* v = b*y^2+1 */
217   mpi_add_ui (v, v, 1);
218
219   /* Compute sqrt(u/v) */
220   /* v3 = v^3 */
221   mpi_powm (v3, v, mpi_const (MPI_C_THREE), ec->p);
222   /* t = v3 * v3 * u * v = u * v^7 */
223   mpi_powm (t, v, seven, ec->p);
224   mpi_mulm (t, t, u, ec->p);
225   /* t = t^((p-5)/8) = (u * v^7)^((p-5)/8)  */
226   mpi_powm (t, t, p58, ec->p);
227   /* x = t * u * v^3 = (u * v^3) * (u * v^7)^((p-5)/8) */
228   mpi_mulm (t, t, u, ec->p);
229   mpi_mulm (x, t, v3, ec->p);
230
231   /* Adjust if needed.  */
232   /* t = v * x^2  */
233   mpi_mulm (t, x, x, ec->p);
234   mpi_mulm (t, t, v, ec->p);
235   /* -t == u ? x = x * sqrt(-1) */
236   gcry_mpi_neg (t, t);
237   if (!mpi_cmp (t, u))
238     {
239       static gcry_mpi_t m1;  /* Fixme: this is not thread-safe.  */
240       if (!m1)
241         m1 = scanval ("2B8324804FC1DF0B2B4D00993DFBD7A7"
242                       "2F431806AD2FE478C4EE1B274A0EA0B0");
243       mpi_mulm (x, x, m1, ec->p);
244       /* t = v * x^2  */
245       mpi_mulm (t, x, x, ec->p);
246       mpi_mulm (t, t, v, ec->p);
247       /* -t == u ? x = x * sqrt(-1) */
248       gcry_mpi_neg (t, t);
249       if (!mpi_cmp (t, u))
250         rc = GPG_ERR_INV_OBJ;
251     }
252
253   /* Choose the desired square root according to parity */
254   if (mpi_test_bit (x, 0) != !!sign)
255     mpi_sub (x, ec->p, x);
256
257   mpi_free (t);
258   mpi_free (v3);
259   mpi_free (v);
260   mpi_free (u);
261
262   return rc;
263 }
264
265
266 /* Decode the EdDSA style encoded PK and set it into RESULT.  CTX is
267    the usual curve context.  If R_ENCPK is not NULL, the encoded PK is
268    stored at that address; this is a new copy to be released by the
269    caller.  In contrast to the supplied PK, this is not an MPI and
270    thus guarnateed to be properly padded.  R_ENCPKLEN receives the
271    length of that encoded key.  */
272 gpg_err_code_t
273 _gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result,
274                              unsigned char **r_encpk, unsigned int *r_encpklen)
275 {
276   gpg_err_code_t rc;
277   unsigned char *rawmpi;
278   unsigned int rawmpilen;
279   int sign;
280
281   if (mpi_is_opaque (pk))
282     {
283       const unsigned char *buf;
284
285       buf = gcry_mpi_get_opaque (pk, &rawmpilen);
286       if (!buf)
287         return GPG_ERR_INV_OBJ;
288       rawmpilen = (rawmpilen + 7)/8;
289
290       /* First check whether the public key has been given in standard
291          uncompressed format.  No need to recover x in this case.
292          Detection is easy: The size of the buffer will be odd and the
293          first byte be 0x04.  */
294       if (rawmpilen > 1 && buf[0] == 0x04 && (rawmpilen%2))
295         {
296           gcry_mpi_t x, y;
297
298           rc = gcry_mpi_scan (&x, GCRYMPI_FMT_STD,
299                               buf+1, (rawmpilen-1)/2, NULL);
300           if (rc)
301             return rc;
302           rc = gcry_mpi_scan (&y, GCRYMPI_FMT_STD,
303                               buf+1+(rawmpilen-1)/2, (rawmpilen-1)/2, NULL);
304           if (rc)
305             {
306               mpi_free (x);
307               return rc;
308             }
309
310           if (r_encpk)
311             {
312               rc = eddsa_encode_x_y (x, y, ctx->nbits/8, r_encpk, r_encpklen);
313               if (rc)
314                 {
315                   mpi_free (x);
316                   mpi_free (y);
317                   return rc;
318                 }
319             }
320           mpi_snatch (result->x, x);
321           mpi_snatch (result->y, y);
322           mpi_set_ui (result->z, 1);
323           return 0;
324         }
325
326       /* EdDSA compressed point.  */
327       rawmpi = gcry_malloc (rawmpilen? rawmpilen:1);
328       if (!rawmpi)
329         return gpg_err_code_from_syserror ();
330       memcpy (rawmpi, buf, rawmpilen);
331       reverse_buffer (rawmpi, rawmpilen);
332     }
333   else
334     {
335       /* Note: Without using an opaque MPI it is not reliable possible
336          to find out whether the public key has been given in
337          uncompressed format.  Thus we expect EdDSA format here.  */
338       rawmpi = _gcry_mpi_get_buffer (pk, ctx->nbits/8, &rawmpilen, NULL);
339       if (!rawmpi)
340         return gpg_err_code_from_syserror ();
341     }
342
343   if (rawmpilen)
344     {
345       sign = !!(rawmpi[0] & 0x80);
346       rawmpi[0] &= 0x7f;
347     }
348   else
349     sign = 0;
350   _gcry_mpi_set_buffer (result->y, rawmpi, rawmpilen, 0);
351   if (r_encpk)
352     {
353       /* Revert to little endian.  */
354       if (sign && rawmpilen)
355         rawmpi[0] |= 0x80;
356       reverse_buffer (rawmpi, rawmpilen);
357       *r_encpk = rawmpi;
358       if (r_encpklen)
359         *r_encpklen = rawmpilen;
360     }
361   else
362     gcry_free (rawmpi);
363
364   rc = _gcry_ecc_eddsa_recover_x (result->x, result->y, sign, ctx);
365   mpi_set_ui (result->z, 1);
366
367   return rc;
368 }
369
370
371 /* Ed25519 version of the key generation.  */
372 gpg_err_code_t
373 _gcry_ecc_eddsa_genkey (ECC_secret_key *sk, elliptic_curve_t *E, mpi_ec_t ctx,
374                         gcry_random_level_t random_level)
375 {
376   gpg_err_code_t rc;
377   int b = 256/8;             /* The only size we currently support.  */
378   gcry_mpi_t a, x, y;
379   mpi_point_struct Q;
380   char *dbuf;
381   size_t dlen;
382   gcry_buffer_t hvec[1];
383   unsigned char *hash_d = NULL;
384
385   point_init (&Q);
386   memset (hvec, 0, sizeof hvec);
387
388   a = mpi_snew (0);
389   x = mpi_new (0);
390   y = mpi_new (0);
391
392   /* Generate a secret.  */
393   hash_d = gcry_malloc_secure (2*b);
394   if (!hash_d)
395     {
396       rc = gpg_error_from_syserror ();
397       goto leave;
398     }
399   dlen = b;
400   dbuf = gcry_random_bytes_secure (dlen, random_level);
401
402   /* Compute the A value.  */
403   hvec[0].data = dbuf;
404   hvec[0].len = dlen;
405   rc = _gcry_md_hash_buffers (GCRY_MD_SHA512, 0, hash_d, hvec, 1);
406   if (rc)
407     goto leave;
408   sk->d = _gcry_mpi_set_opaque (NULL, dbuf, dlen*8);
409   dbuf = NULL;
410   reverse_buffer (hash_d, 32);  /* Only the first half of the hash.  */
411   hash_d[0] = (hash_d[0] & 0x7f) | 0x40;
412   hash_d[31] &= 0xf8;
413   _gcry_mpi_set_buffer (a, hash_d, 32, 0);
414   gcry_free (hash_d); hash_d = NULL;
415   /* log_printmpi ("ecgen         a", a); */
416
417   /* Compute Q.  */
418   _gcry_mpi_ec_mul_point (&Q, a, &E->G, ctx);
419   if (DBG_CIPHER)
420     log_printpnt ("ecgen      pk", &Q, ctx);
421
422   /* Copy the stuff to the key structures. */
423   sk->E.model = E->model;
424   sk->E.dialect = E->dialect;
425   sk->E.p = mpi_copy (E->p);
426   sk->E.a = mpi_copy (E->a);
427   sk->E.b = mpi_copy (E->b);
428   point_init (&sk->E.G);
429   point_set (&sk->E.G, &E->G);
430   sk->E.n = mpi_copy (E->n);
431   point_init (&sk->Q);
432   point_set (&sk->Q, &Q);
433
434  leave:
435   point_free (&Q);
436   gcry_mpi_release (a);
437   gcry_mpi_release (x);
438   gcry_mpi_release (y);
439   gcry_free (hash_d);
440   return rc;
441 }
442
443
444 /* Compute an EdDSA signature. See:
445  *   [ed25519] 23pp. (PDF) Daniel J. Bernstein, Niels Duif, Tanja
446  *   Lange, Peter Schwabe, Bo-Yin Yang. High-speed high-security
447  *   signatures.  Journal of Cryptographic Engineering 2 (2012), 77-89.
448  *   Document ID: a1a62a2f76d23f65d622484ddd09caf8.
449  *   URL: http://cr.yp.to/papers.html#ed25519. Date: 2011.09.26.
450  *
451  * Despite that this function requires the specification of a hash
452  * algorithm, we only support what has been specified by the paper.
453  * This may change in the future.  Note that we don't check the used
454  * curve; the user is responsible to use Ed25519.
455  *
456  * Return the signature struct (r,s) from the message hash.  The caller
457  * must have allocated R_R and S.
458  */
459 gpg_err_code_t
460 _gcry_ecc_eddsa_sign (gcry_mpi_t input, ECC_secret_key *skey,
461                       gcry_mpi_t r_r, gcry_mpi_t s, int hashalgo, gcry_mpi_t pk)
462 {
463   int rc;
464   mpi_ec_t ctx = NULL;
465   int b;
466   unsigned int tmp;
467   unsigned char *digest;
468   gcry_buffer_t hvec[3];
469   const void *mbuf;
470   size_t mlen;
471   unsigned char *rawmpi = NULL;
472   unsigned int rawmpilen;
473   unsigned char *encpk = NULL; /* Encoded public key.  */
474   unsigned int encpklen;
475   mpi_point_struct I;          /* Intermediate value.  */
476   mpi_point_struct Q;          /* Public key.  */
477   gcry_mpi_t a, x, y, r;
478
479   memset (hvec, 0, sizeof hvec);
480
481   if (!mpi_is_opaque (input))
482     return GPG_ERR_INV_DATA;
483   if (hashalgo != GCRY_MD_SHA512)
484     return GPG_ERR_DIGEST_ALGO;
485
486   /* Initialize some helpers.  */
487   point_init (&I);
488   point_init (&Q);
489   a = mpi_snew (0);
490   x = mpi_new (0);
491   y = mpi_new (0);
492   r = mpi_new (0);
493   ctx = _gcry_mpi_ec_p_internal_new (skey->E.model, skey->E.dialect, 0,
494                                      skey->E.p, skey->E.a, skey->E.b);
495   b = (ctx->nbits+7)/8;
496   if (b != 256/8)
497     return GPG_ERR_INTERNAL; /* We only support 256 bit. */
498
499   digest = gcry_calloc_secure (2, b);
500   if (!digest)
501     {
502       rc = gpg_err_code_from_syserror ();
503       goto leave;
504     }
505
506   /* Hash the secret key.  We clear DIGEST so we can use it as input
507      to left pad the key with zeroes for hashing.  */
508   rawmpi = _gcry_mpi_get_buffer (skey->d, 0, &rawmpilen, NULL);
509   if (!rawmpi)
510     {
511       rc = gpg_err_code_from_syserror ();
512       goto leave;
513     }
514   hvec[0].data = digest;
515   hvec[0].off = 0;
516   hvec[0].len = b > rawmpilen? b - rawmpilen : 0;
517   hvec[1].data = rawmpi;
518   hvec[1].off = 0;
519   hvec[1].len = rawmpilen;
520   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2);
521   gcry_free (rawmpi); rawmpi = NULL;
522   if (rc)
523     goto leave;
524
525   /* Compute the A value (this modifies DIGEST).  */
526   reverse_buffer (digest, 32);  /* Only the first half of the hash.  */
527   digest[0] = (digest[0] & 0x7f) | 0x40;
528   digest[31] &= 0xf8;
529   _gcry_mpi_set_buffer (a, digest, 32, 0);
530
531   /* Compute the public key if it has not been supplied as optional
532      parameter.  */
533   if (pk)
534     {
535       rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q,  &encpk, &encpklen);
536       if (rc)
537         goto leave;
538       if (DBG_CIPHER)
539         log_printhex ("* e_pk", encpk, encpklen);
540       if (!_gcry_mpi_ec_curve_point (&Q, ctx))
541         {
542           rc = GPG_ERR_BROKEN_PUBKEY;
543           goto leave;
544         }
545     }
546   else
547     {
548       _gcry_mpi_ec_mul_point (&Q, a, &skey->E.G, ctx);
549       rc = _gcry_ecc_eddsa_encodepoint (&Q, ctx, x, y, &encpk, &encpklen);
550       if (rc)
551         goto leave;
552       if (DBG_CIPHER)
553         log_printhex ("  e_pk", encpk, encpklen);
554     }
555
556   /* Compute R.  */
557   mbuf = gcry_mpi_get_opaque (input, &tmp);
558   mlen = (tmp +7)/8;
559   if (DBG_CIPHER)
560     log_printhex ("     m", mbuf, mlen);
561
562   hvec[0].data = digest;
563   hvec[0].off  = 32;
564   hvec[0].len  = 32;
565   hvec[1].data = (char*)mbuf;
566   hvec[1].len  = mlen;
567   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2);
568   if (rc)
569     goto leave;
570   reverse_buffer (digest, 64);
571   if (DBG_CIPHER)
572     log_printhex ("     r", digest, 64);
573   _gcry_mpi_set_buffer (r, digest, 64, 0);
574   _gcry_mpi_ec_mul_point (&I, r, &skey->E.G, ctx);
575   if (DBG_CIPHER)
576     log_printpnt ("   r", &I, ctx);
577
578   /* Convert R into affine coordinates and apply encoding.  */
579   rc = _gcry_ecc_eddsa_encodepoint (&I, ctx, x, y, &rawmpi, &rawmpilen);
580   if (rc)
581     goto leave;
582   if (DBG_CIPHER)
583     log_printhex ("   e_r", rawmpi, rawmpilen);
584
585   /* S = r + a * H(encodepoint(R) + encodepoint(pk) + m) mod n  */
586   hvec[0].data = rawmpi;  /* (this is R) */
587   hvec[0].off  = 0;
588   hvec[0].len  = rawmpilen;
589   hvec[1].data = encpk;
590   hvec[1].off  = 0;
591   hvec[1].len  = encpklen;
592   hvec[2].data = (char*)mbuf;
593   hvec[2].off  = 0;
594   hvec[2].len  = mlen;
595   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
596   if (rc)
597     goto leave;
598
599   /* No more need for RAWMPI thus we now transfer it to R_R.  */
600   gcry_mpi_set_opaque (r_r, rawmpi, rawmpilen*8);
601   rawmpi = NULL;
602
603   reverse_buffer (digest, 64);
604   if (DBG_CIPHER)
605     log_printhex (" H(R+)", digest, 64);
606   _gcry_mpi_set_buffer (s, digest, 64, 0);
607   mpi_mulm (s, s, a, skey->E.n);
608   mpi_addm (s, s, r, skey->E.n);
609   rc = eddsa_encodempi (s, b, &rawmpi, &rawmpilen);
610   if (rc)
611     goto leave;
612   if (DBG_CIPHER)
613     log_printhex ("   e_s", rawmpi, rawmpilen);
614   gcry_mpi_set_opaque (s, rawmpi, rawmpilen*8);
615   rawmpi = NULL;
616
617   rc = 0;
618
619  leave:
620   gcry_mpi_release (a);
621   gcry_mpi_release (x);
622   gcry_mpi_release (y);
623   gcry_mpi_release (r);
624   gcry_free (digest);
625   _gcry_mpi_ec_free (ctx);
626   point_free (&I);
627   point_free (&Q);
628   gcry_free (encpk);
629   gcry_free (rawmpi);
630   return rc;
631 }
632
633
634 /* Verify an EdDSA signature.  See sign_eddsa for the reference.
635  * Check if R_IN and S_IN verifies INPUT.  PKEY has the curve
636  * parameters and PK is the EdDSA style encoded public key.
637  */
638 gpg_err_code_t
639 _gcry_ecc_eddsa_verify (gcry_mpi_t input, ECC_public_key *pkey,
640                         gcry_mpi_t r_in, gcry_mpi_t s_in, int hashalgo,
641                         gcry_mpi_t pk)
642 {
643   int rc;
644   mpi_ec_t ctx = NULL;
645   int b;
646   unsigned int tmp;
647   mpi_point_struct Q;          /* Public key.  */
648   unsigned char *encpk = NULL; /* Encoded public key.  */
649   unsigned int encpklen;
650   const void *mbuf, *rbuf;
651   unsigned char *tbuf = NULL;
652   size_t mlen, rlen;
653   unsigned int tlen;
654   unsigned char digest[64];
655   gcry_buffer_t hvec[3];
656   gcry_mpi_t h, s;
657   mpi_point_struct Ia, Ib;
658
659   if (!mpi_is_opaque (input) || !mpi_is_opaque (r_in) || !mpi_is_opaque (s_in))
660     return GPG_ERR_INV_DATA;
661   if (hashalgo != GCRY_MD_SHA512)
662     return GPG_ERR_DIGEST_ALGO;
663
664   point_init (&Q);
665   point_init (&Ia);
666   point_init (&Ib);
667   h = mpi_new (0);
668   s = mpi_new (0);
669
670   ctx = _gcry_mpi_ec_p_internal_new (pkey->E.model, pkey->E.dialect, 0,
671                                      pkey->E.p, pkey->E.a, pkey->E.b);
672   b = ctx->nbits/8;
673   if (b != 256/8)
674     return GPG_ERR_INTERNAL; /* We only support 256 bit. */
675
676   /* Decode and check the public key.  */
677   rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q, &encpk, &encpklen);
678   if (rc)
679     goto leave;
680   if (!_gcry_mpi_ec_curve_point (&Q, ctx))
681     {
682       rc = GPG_ERR_BROKEN_PUBKEY;
683       goto leave;
684     }
685   if (DBG_CIPHER)
686     log_printhex ("  e_pk", encpk, encpklen);
687   if (encpklen != b)
688     {
689       rc = GPG_ERR_INV_LENGTH;
690       goto leave;
691     }
692
693   /* Convert the other input parameters.  */
694   mbuf = gcry_mpi_get_opaque (input, &tmp);
695   mlen = (tmp +7)/8;
696   if (DBG_CIPHER)
697     log_printhex ("     m", mbuf, mlen);
698   rbuf = gcry_mpi_get_opaque (r_in, &tmp);
699   rlen = (tmp +7)/8;
700   if (DBG_CIPHER)
701     log_printhex ("     r", rbuf, rlen);
702   if (rlen != b)
703     {
704       rc = GPG_ERR_INV_LENGTH;
705       goto leave;
706     }
707
708   /* h = H(encodepoint(R) + encodepoint(pk) + m)  */
709   hvec[0].data = (char*)rbuf;
710   hvec[0].off  = 0;
711   hvec[0].len  = rlen;
712   hvec[1].data = encpk;
713   hvec[1].off  = 0;
714   hvec[1].len  = encpklen;
715   hvec[2].data = (char*)mbuf;
716   hvec[2].off  = 0;
717   hvec[2].len  = mlen;
718   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
719   if (rc)
720     goto leave;
721   reverse_buffer (digest, 64);
722   if (DBG_CIPHER)
723     log_printhex (" H(R+)", digest, 64);
724   _gcry_mpi_set_buffer (h, digest, 64, 0);
725
726   /* According to the paper the best way for verification is:
727          encodepoint(sG - h·Q) = encodepoint(r)
728      because we don't need to decode R. */
729   {
730     void *sbuf;
731     unsigned int slen;
732
733     sbuf = _gcry_mpi_get_opaque_copy (s_in, &tmp);
734     slen = (tmp +7)/8;
735     reverse_buffer (sbuf, slen);
736     if (DBG_CIPHER)
737       log_printhex ("     s", sbuf, slen);
738     _gcry_mpi_set_buffer (s, sbuf, slen, 0);
739     gcry_free (sbuf);
740     if (slen != b)
741       {
742         rc = GPG_ERR_INV_LENGTH;
743         goto leave;
744       }
745   }
746
747   _gcry_mpi_ec_mul_point (&Ia, s, &pkey->E.G, ctx);
748   _gcry_mpi_ec_mul_point (&Ib, h, &Q, ctx);
749   _gcry_mpi_neg (Ib.x, Ib.x);
750   _gcry_mpi_ec_add_points (&Ia, &Ia, &Ib, ctx);
751   rc = _gcry_ecc_eddsa_encodepoint (&Ia, ctx, s, h, &tbuf, &tlen);
752   if (rc)
753     goto leave;
754   if (tlen != rlen || memcmp (tbuf, rbuf, tlen))
755     {
756       rc = GPG_ERR_BAD_SIGNATURE;
757       goto leave;
758     }
759
760   rc = 0;
761
762  leave:
763   gcry_free (encpk);
764   gcry_free (tbuf);
765   _gcry_mpi_ec_free (ctx);
766   gcry_mpi_release (s);
767   gcry_mpi_release (h);
768   point_free (&Ia);
769   point_free (&Ib);
770   point_free (&Q);
771   return rc;
772 }