Speed-up SHA-1 NEON assembly implementation
[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_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.  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 = 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       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   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       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 = 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 = xtrymalloc (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     xfree (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 /* Compute the A value as used by EdDSA.  The caller needs to provide
372    the context EC and the actual secret D as an MPI.  The function
373    returns a newly allocated 64 byte buffer at r_digest; the first 32
374    bytes represent the A value.  NULL is returned on error and NULL
375    stored at R_DIGEST.  */
376 gpg_err_code_t
377 _gcry_ecc_eddsa_compute_h_d (unsigned char **r_digest,
378                              gcry_mpi_t d, mpi_ec_t ec)
379 {
380   gpg_err_code_t rc;
381   unsigned char *rawmpi = NULL;
382   unsigned int rawmpilen;
383   unsigned char *digest;
384   gcry_buffer_t hvec[2];
385   int hashalgo, b;
386
387   *r_digest = NULL;
388
389   hashalgo = GCRY_MD_SHA512;
390   if (hashalgo != GCRY_MD_SHA512)
391     return GPG_ERR_DIGEST_ALGO;
392
393   b = (ec->nbits+7)/8;
394   if (b != 256/8)
395     return GPG_ERR_INTERNAL; /* We only support 256 bit. */
396
397   /* Note that we clear DIGEST so we can use it as input to left pad
398      the key with zeroes for hashing.  */
399   digest = xtrycalloc_secure (2, b);
400   if (!digest)
401     return gpg_err_code_from_syserror ();
402
403   memset (hvec, 0, sizeof hvec);
404
405   rawmpi = _gcry_mpi_get_buffer (d, 0, &rawmpilen, NULL);
406   if (!rawmpi)
407     {
408       xfree (digest);
409       return gpg_err_code_from_syserror ();
410     }
411
412   hvec[0].data = digest;
413   hvec[0].off = 0;
414   hvec[0].len = b > rawmpilen? b - rawmpilen : 0;
415   hvec[1].data = rawmpi;
416   hvec[1].off = 0;
417   hvec[1].len = rawmpilen;
418   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2);
419   xfree (rawmpi);
420   if (rc)
421     {
422       xfree (digest);
423       return rc;
424     }
425
426   /* Compute the A value.  */
427   reverse_buffer (digest, 32);  /* Only the first half of the hash.  */
428   digest[0]   = (digest[0] & 0x7f) | 0x40;
429   digest[31] &= 0xf8;
430
431   *r_digest = digest;
432   return 0;
433 }
434
435
436 /* Ed25519 version of the key generation.  */
437 gpg_err_code_t
438 _gcry_ecc_eddsa_genkey (ECC_secret_key *sk, elliptic_curve_t *E, mpi_ec_t ctx,
439                         gcry_random_level_t random_level)
440 {
441   gpg_err_code_t rc;
442   int b = 256/8;             /* The only size we currently support.  */
443   gcry_mpi_t a, x, y;
444   mpi_point_struct Q;
445   char *dbuf;
446   size_t dlen;
447   gcry_buffer_t hvec[1];
448   unsigned char *hash_d = NULL;
449
450   point_init (&Q);
451   memset (hvec, 0, sizeof hvec);
452
453   a = mpi_snew (0);
454   x = mpi_new (0);
455   y = mpi_new (0);
456
457   /* Generate a secret.  */
458   hash_d = xtrymalloc_secure (2*b);
459   if (!hash_d)
460     {
461       rc = gpg_error_from_syserror ();
462       goto leave;
463     }
464   dlen = b;
465   dbuf = _gcry_random_bytes_secure (dlen, random_level);
466
467   /* Compute the A value.  */
468   hvec[0].data = dbuf;
469   hvec[0].len = dlen;
470   rc = _gcry_md_hash_buffers (GCRY_MD_SHA512, 0, hash_d, hvec, 1);
471   if (rc)
472     goto leave;
473   sk->d = _gcry_mpi_set_opaque (NULL, dbuf, dlen*8);
474   dbuf = NULL;
475   reverse_buffer (hash_d, 32);  /* Only the first half of the hash.  */
476   hash_d[0] = (hash_d[0] & 0x7f) | 0x40;
477   hash_d[31] &= 0xf8;
478   _gcry_mpi_set_buffer (a, hash_d, 32, 0);
479   xfree (hash_d); hash_d = NULL;
480   /* log_printmpi ("ecgen         a", a); */
481
482   /* Compute Q.  */
483   _gcry_mpi_ec_mul_point (&Q, a, &E->G, ctx);
484   if (DBG_CIPHER)
485     log_printpnt ("ecgen      pk", &Q, ctx);
486
487   /* Copy the stuff to the key structures. */
488   sk->E.model = E->model;
489   sk->E.dialect = E->dialect;
490   sk->E.p = mpi_copy (E->p);
491   sk->E.a = mpi_copy (E->a);
492   sk->E.b = mpi_copy (E->b);
493   point_init (&sk->E.G);
494   point_set (&sk->E.G, &E->G);
495   sk->E.n = mpi_copy (E->n);
496   point_init (&sk->Q);
497   point_set (&sk->Q, &Q);
498
499  leave:
500   point_free (&Q);
501   _gcry_mpi_release (a);
502   _gcry_mpi_release (x);
503   _gcry_mpi_release (y);
504   xfree (hash_d);
505   return rc;
506 }
507
508
509 /* Compute an EdDSA signature. See:
510  *   [ed25519] 23pp. (PDF) Daniel J. Bernstein, Niels Duif, Tanja
511  *   Lange, Peter Schwabe, Bo-Yin Yang. High-speed high-security
512  *   signatures.  Journal of Cryptographic Engineering 2 (2012), 77-89.
513  *   Document ID: a1a62a2f76d23f65d622484ddd09caf8.
514  *   URL: http://cr.yp.to/papers.html#ed25519. Date: 2011.09.26.
515  *
516  * Despite that this function requires the specification of a hash
517  * algorithm, we only support what has been specified by the paper.
518  * This may change in the future.  Note that we don't check the used
519  * curve; the user is responsible to use Ed25519.
520  *
521  * Return the signature struct (r,s) from the message hash.  The caller
522  * must have allocated R_R and S.
523  */
524 gpg_err_code_t
525 _gcry_ecc_eddsa_sign (gcry_mpi_t input, ECC_secret_key *skey,
526                       gcry_mpi_t r_r, gcry_mpi_t s, int hashalgo, gcry_mpi_t pk)
527 {
528   int rc;
529   mpi_ec_t ctx = NULL;
530   int b;
531   unsigned int tmp;
532   unsigned char *digest;
533   gcry_buffer_t hvec[3];
534   const void *mbuf;
535   size_t mlen;
536   unsigned char *rawmpi = NULL;
537   unsigned int rawmpilen;
538   unsigned char *encpk = NULL; /* Encoded public key.  */
539   unsigned int encpklen;
540   mpi_point_struct I;          /* Intermediate value.  */
541   mpi_point_struct Q;          /* Public key.  */
542   gcry_mpi_t a, x, y, r;
543
544   memset (hvec, 0, sizeof hvec);
545
546   if (!mpi_is_opaque (input))
547     return GPG_ERR_INV_DATA;
548
549   /* Initialize some helpers.  */
550   point_init (&I);
551   point_init (&Q);
552   a = mpi_snew (0);
553   x = mpi_new (0);
554   y = mpi_new (0);
555   r = mpi_new (0);
556   ctx = _gcry_mpi_ec_p_internal_new (skey->E.model, skey->E.dialect, 0,
557                                      skey->E.p, skey->E.a, skey->E.b);
558   b = (ctx->nbits+7)/8;
559   if (b != 256/8)
560     return GPG_ERR_INTERNAL; /* We only support 256 bit. */
561
562   rc = _gcry_ecc_eddsa_compute_h_d (&digest, skey->d, ctx);
563   if (rc)
564     goto leave;
565   _gcry_mpi_set_buffer (a, digest, 32, 0);
566
567   /* Compute the public key if it has not been supplied as optional
568      parameter.  */
569   if (pk)
570     {
571       rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q,  &encpk, &encpklen);
572       if (rc)
573         goto leave;
574       if (DBG_CIPHER)
575         log_printhex ("* e_pk", encpk, encpklen);
576       if (!_gcry_mpi_ec_curve_point (&Q, ctx))
577         {
578           rc = GPG_ERR_BROKEN_PUBKEY;
579           goto leave;
580         }
581     }
582   else
583     {
584       _gcry_mpi_ec_mul_point (&Q, a, &skey->E.G, ctx);
585       rc = _gcry_ecc_eddsa_encodepoint (&Q, ctx, x, y, &encpk, &encpklen);
586       if (rc)
587         goto leave;
588       if (DBG_CIPHER)
589         log_printhex ("  e_pk", encpk, encpklen);
590     }
591
592   /* Compute R.  */
593   mbuf = mpi_get_opaque (input, &tmp);
594   mlen = (tmp +7)/8;
595   if (DBG_CIPHER)
596     log_printhex ("     m", mbuf, mlen);
597
598   hvec[0].data = digest;
599   hvec[0].off  = 32;
600   hvec[0].len  = 32;
601   hvec[1].data = (char*)mbuf;
602   hvec[1].len  = mlen;
603   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2);
604   if (rc)
605     goto leave;
606   reverse_buffer (digest, 64);
607   if (DBG_CIPHER)
608     log_printhex ("     r", digest, 64);
609   _gcry_mpi_set_buffer (r, digest, 64, 0);
610   _gcry_mpi_ec_mul_point (&I, r, &skey->E.G, ctx);
611   if (DBG_CIPHER)
612     log_printpnt ("   r", &I, ctx);
613
614   /* Convert R into affine coordinates and apply encoding.  */
615   rc = _gcry_ecc_eddsa_encodepoint (&I, ctx, x, y, &rawmpi, &rawmpilen);
616   if (rc)
617     goto leave;
618   if (DBG_CIPHER)
619     log_printhex ("   e_r", rawmpi, rawmpilen);
620
621   /* S = r + a * H(encodepoint(R) + encodepoint(pk) + m) mod n  */
622   hvec[0].data = rawmpi;  /* (this is R) */
623   hvec[0].off  = 0;
624   hvec[0].len  = rawmpilen;
625   hvec[1].data = encpk;
626   hvec[1].off  = 0;
627   hvec[1].len  = encpklen;
628   hvec[2].data = (char*)mbuf;
629   hvec[2].off  = 0;
630   hvec[2].len  = mlen;
631   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
632   if (rc)
633     goto leave;
634
635   /* No more need for RAWMPI thus we now transfer it to R_R.  */
636   mpi_set_opaque (r_r, rawmpi, rawmpilen*8);
637   rawmpi = NULL;
638
639   reverse_buffer (digest, 64);
640   if (DBG_CIPHER)
641     log_printhex (" H(R+)", digest, 64);
642   _gcry_mpi_set_buffer (s, digest, 64, 0);
643   mpi_mulm (s, s, a, skey->E.n);
644   mpi_addm (s, s, r, skey->E.n);
645   rc = eddsa_encodempi (s, b, &rawmpi, &rawmpilen);
646   if (rc)
647     goto leave;
648   if (DBG_CIPHER)
649     log_printhex ("   e_s", rawmpi, rawmpilen);
650   mpi_set_opaque (s, rawmpi, rawmpilen*8);
651   rawmpi = NULL;
652
653   rc = 0;
654
655  leave:
656   _gcry_mpi_release (a);
657   _gcry_mpi_release (x);
658   _gcry_mpi_release (y);
659   _gcry_mpi_release (r);
660   xfree (digest);
661   _gcry_mpi_ec_free (ctx);
662   point_free (&I);
663   point_free (&Q);
664   xfree (encpk);
665   xfree (rawmpi);
666   return rc;
667 }
668
669
670 /* Verify an EdDSA signature.  See sign_eddsa for the reference.
671  * Check if R_IN and S_IN verifies INPUT.  PKEY has the curve
672  * parameters and PK is the EdDSA style encoded public key.
673  */
674 gpg_err_code_t
675 _gcry_ecc_eddsa_verify (gcry_mpi_t input, ECC_public_key *pkey,
676                         gcry_mpi_t r_in, gcry_mpi_t s_in, int hashalgo,
677                         gcry_mpi_t pk)
678 {
679   int rc;
680   mpi_ec_t ctx = NULL;
681   int b;
682   unsigned int tmp;
683   mpi_point_struct Q;          /* Public key.  */
684   unsigned char *encpk = NULL; /* Encoded public key.  */
685   unsigned int encpklen;
686   const void *mbuf, *rbuf;
687   unsigned char *tbuf = NULL;
688   size_t mlen, rlen;
689   unsigned int tlen;
690   unsigned char digest[64];
691   gcry_buffer_t hvec[3];
692   gcry_mpi_t h, s;
693   mpi_point_struct Ia, Ib;
694
695   if (!mpi_is_opaque (input) || !mpi_is_opaque (r_in) || !mpi_is_opaque (s_in))
696     return GPG_ERR_INV_DATA;
697   if (hashalgo != GCRY_MD_SHA512)
698     return GPG_ERR_DIGEST_ALGO;
699
700   point_init (&Q);
701   point_init (&Ia);
702   point_init (&Ib);
703   h = mpi_new (0);
704   s = mpi_new (0);
705
706   ctx = _gcry_mpi_ec_p_internal_new (pkey->E.model, pkey->E.dialect, 0,
707                                      pkey->E.p, pkey->E.a, pkey->E.b);
708   b = ctx->nbits/8;
709   if (b != 256/8)
710     return GPG_ERR_INTERNAL; /* We only support 256 bit. */
711
712   /* Decode and check the public key.  */
713   rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q, &encpk, &encpklen);
714   if (rc)
715     goto leave;
716   if (!_gcry_mpi_ec_curve_point (&Q, ctx))
717     {
718       rc = GPG_ERR_BROKEN_PUBKEY;
719       goto leave;
720     }
721   if (DBG_CIPHER)
722     log_printhex ("  e_pk", encpk, encpklen);
723   if (encpklen != b)
724     {
725       rc = GPG_ERR_INV_LENGTH;
726       goto leave;
727     }
728
729   /* Convert the other input parameters.  */
730   mbuf = mpi_get_opaque (input, &tmp);
731   mlen = (tmp +7)/8;
732   if (DBG_CIPHER)
733     log_printhex ("     m", mbuf, mlen);
734   rbuf = mpi_get_opaque (r_in, &tmp);
735   rlen = (tmp +7)/8;
736   if (DBG_CIPHER)
737     log_printhex ("     r", rbuf, rlen);
738   if (rlen != b)
739     {
740       rc = GPG_ERR_INV_LENGTH;
741       goto leave;
742     }
743
744   /* h = H(encodepoint(R) + encodepoint(pk) + m)  */
745   hvec[0].data = (char*)rbuf;
746   hvec[0].off  = 0;
747   hvec[0].len  = rlen;
748   hvec[1].data = encpk;
749   hvec[1].off  = 0;
750   hvec[1].len  = encpklen;
751   hvec[2].data = (char*)mbuf;
752   hvec[2].off  = 0;
753   hvec[2].len  = mlen;
754   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
755   if (rc)
756     goto leave;
757   reverse_buffer (digest, 64);
758   if (DBG_CIPHER)
759     log_printhex (" H(R+)", digest, 64);
760   _gcry_mpi_set_buffer (h, digest, 64, 0);
761
762   /* According to the paper the best way for verification is:
763          encodepoint(sG - h·Q) = encodepoint(r)
764      because we don't need to decode R. */
765   {
766     void *sbuf;
767     unsigned int slen;
768
769     sbuf = _gcry_mpi_get_opaque_copy (s_in, &tmp);
770     slen = (tmp +7)/8;
771     reverse_buffer (sbuf, slen);
772     if (DBG_CIPHER)
773       log_printhex ("     s", sbuf, slen);
774     _gcry_mpi_set_buffer (s, sbuf, slen, 0);
775     xfree (sbuf);
776     if (slen != b)
777       {
778         rc = GPG_ERR_INV_LENGTH;
779         goto leave;
780       }
781   }
782
783   _gcry_mpi_ec_mul_point (&Ia, s, &pkey->E.G, ctx);
784   _gcry_mpi_ec_mul_point (&Ib, h, &Q, ctx);
785   _gcry_mpi_neg (Ib.x, Ib.x);
786   _gcry_mpi_ec_add_points (&Ia, &Ia, &Ib, ctx);
787   rc = _gcry_ecc_eddsa_encodepoint (&Ia, ctx, s, h, &tbuf, &tlen);
788   if (rc)
789     goto leave;
790   if (tlen != rlen || memcmp (tbuf, rbuf, tlen))
791     {
792       rc = GPG_ERR_BAD_SIGNATURE;
793       goto leave;
794     }
795
796   rc = 0;
797
798  leave:
799   xfree (encpk);
800   xfree (tbuf);
801   _gcry_mpi_ec_free (ctx);
802   _gcry_mpi_release (s);
803   _gcry_mpi_release (h);
804   point_free (&Ia);
805   point_free (&Ib);
806   point_free (&Q);
807   return rc;
808 }