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