ecc: Change keygrip computation for Ed25519+EdDSA.
[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     gcry_mpi_neg (x, 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 received 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   gcry_mpi_release (a);
436   gcry_mpi_release (x);
437   gcry_mpi_release (y);
438   gcry_free (hash_d);
439   return rc;
440 }
441
442
443 /* Compute an EdDSA signature. See:
444  *   [ed25519] 23pp. (PDF) Daniel J. Bernstein, Niels Duif, Tanja
445  *   Lange, Peter Schwabe, Bo-Yin Yang. High-speed high-security
446  *   signatures.  Journal of Cryptographic Engineering 2 (2012), 77-89.
447  *   Document ID: a1a62a2f76d23f65d622484ddd09caf8.
448  *   URL: http://cr.yp.to/papers.html#ed25519. Date: 2011.09.26.
449  *
450  * Despite that this function requires the specification of a hash
451  * algorithm, we only support what has been specified by the paper.
452  * This may change in the future.  Note that we don't check the used
453  * curve; the user is responsible to use Ed25519.
454  *
455  * Return the signature struct (r,s) from the message hash.  The caller
456  * must have allocated R_R and S.
457  */
458 gpg_err_code_t
459 _gcry_ecc_eddsa_sign (gcry_mpi_t input, ECC_secret_key *skey,
460                       gcry_mpi_t r_r, gcry_mpi_t s, int hashalgo, gcry_mpi_t pk)
461 {
462   int rc;
463   mpi_ec_t ctx = NULL;
464   int b;
465   unsigned int tmp;
466   unsigned char *digest;
467   gcry_buffer_t hvec[3];
468   const void *mbuf;
469   size_t mlen;
470   unsigned char *rawmpi = NULL;
471   unsigned int rawmpilen;
472   unsigned char *encpk = NULL; /* Encoded public key.  */
473   unsigned int encpklen;
474   mpi_point_struct I;          /* Intermediate value.  */
475   mpi_point_struct Q;          /* Public key.  */
476   gcry_mpi_t a, x, y, r;
477
478   memset (hvec, 0, sizeof hvec);
479
480   if (!mpi_is_opaque (input))
481     return GPG_ERR_INV_DATA;
482   if (hashalgo != GCRY_MD_SHA512)
483     return GPG_ERR_DIGEST_ALGO;
484
485   /* Initialize some helpers.  */
486   point_init (&I);
487   point_init (&Q);
488   a = mpi_snew (0);
489   x = mpi_new (0);
490   y = mpi_new (0);
491   r = mpi_new (0);
492   ctx = _gcry_mpi_ec_p_internal_new (skey->E.model, skey->E.dialect, 0,
493                                      skey->E.p, skey->E.a, skey->E.b);
494   b = (ctx->nbits+7)/8;
495   if (b != 256/8)
496     return GPG_ERR_INTERNAL; /* We only support 256 bit. */
497
498   digest = gcry_calloc_secure (2, b);
499   if (!digest)
500     {
501       rc = gpg_err_code_from_syserror ();
502       goto leave;
503     }
504
505   /* Hash the secret key.  We clear DIGEST so we can use it as input
506      to left pad the key with zeroes for hashing.  */
507   rawmpi = _gcry_mpi_get_buffer (skey->d, 0, &rawmpilen, NULL);
508   if (!rawmpi)
509     {
510       rc = gpg_err_code_from_syserror ();
511       goto leave;
512     }
513   hvec[0].data = digest;
514   hvec[0].off = 0;
515   hvec[0].len = b > rawmpilen? b - rawmpilen : 0;
516   hvec[1].data = rawmpi;
517   hvec[1].off = 0;
518   hvec[1].len = rawmpilen;
519   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2);
520   gcry_free (rawmpi); rawmpi = NULL;
521   if (rc)
522     goto leave;
523
524   /* Compute the A value (this modifies DIGEST).  */
525   reverse_buffer (digest, 32);  /* Only the first half of the hash.  */
526   digest[0] = (digest[0] & 0x7f) | 0x40;
527   digest[31] &= 0xf8;
528   _gcry_mpi_set_buffer (a, digest, 32, 0);
529
530   /* Compute the public key if it has not been supplied as optional
531      parameter.  */
532   if (pk)
533     {
534       rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q,  &encpk, &encpklen);
535       if (rc)
536         goto leave;
537       if (DBG_CIPHER)
538         log_printhex ("* e_pk", encpk, encpklen);
539       if (!_gcry_mpi_ec_curve_point (&Q, ctx))
540         {
541           rc = GPG_ERR_BROKEN_PUBKEY;
542           goto leave;
543         }
544     }
545   else
546     {
547       _gcry_mpi_ec_mul_point (&Q, a, &skey->E.G, ctx);
548       rc = _gcry_ecc_eddsa_encodepoint (&Q, ctx, x, y, &encpk, &encpklen);
549       if (rc)
550         goto leave;
551       if (DBG_CIPHER)
552         log_printhex ("  e_pk", encpk, encpklen);
553     }
554
555   /* Compute R.  */
556   mbuf = gcry_mpi_get_opaque (input, &tmp);
557   mlen = (tmp +7)/8;
558   if (DBG_CIPHER)
559     log_printhex ("     m", mbuf, mlen);
560
561   hvec[0].data = digest;
562   hvec[0].off  = 32;
563   hvec[0].len  = 32;
564   hvec[1].data = (char*)mbuf;
565   hvec[1].len  = mlen;
566   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2);
567   if (rc)
568     goto leave;
569   reverse_buffer (digest, 64);
570   if (DBG_CIPHER)
571     log_printhex ("     r", digest, 64);
572   _gcry_mpi_set_buffer (r, digest, 64, 0);
573   _gcry_mpi_ec_mul_point (&I, r, &skey->E.G, ctx);
574   if (DBG_CIPHER)
575     log_printpnt ("   r", &I, ctx);
576
577   /* Convert R into affine coordinates and apply encoding.  */
578   rc = _gcry_ecc_eddsa_encodepoint (&I, ctx, x, y, &rawmpi, &rawmpilen);
579   if (rc)
580     goto leave;
581   if (DBG_CIPHER)
582     log_printhex ("   e_r", rawmpi, rawmpilen);
583
584   /* S = r + a * H(encodepoint(R) + encodepoint(pk) + m) mod n  */
585   hvec[0].data = rawmpi;  /* (this is R) */
586   hvec[0].off  = 0;
587   hvec[0].len  = rawmpilen;
588   hvec[1].data = encpk;
589   hvec[1].off  = 0;
590   hvec[1].len  = encpklen;
591   hvec[2].data = (char*)mbuf;
592   hvec[2].off  = 0;
593   hvec[2].len  = mlen;
594   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
595   if (rc)
596     goto leave;
597
598   /* No more need for RAWMPI thus we now transfer it to R_R.  */
599   gcry_mpi_set_opaque (r_r, rawmpi, rawmpilen*8);
600   rawmpi = NULL;
601
602   reverse_buffer (digest, 64);
603   if (DBG_CIPHER)
604     log_printhex (" H(R+)", digest, 64);
605   _gcry_mpi_set_buffer (s, digest, 64, 0);
606   mpi_mulm (s, s, a, skey->E.n);
607   mpi_addm (s, s, r, skey->E.n);
608   rc = eddsa_encodempi (s, b, &rawmpi, &rawmpilen);
609   if (rc)
610     goto leave;
611   if (DBG_CIPHER)
612     log_printhex ("   e_s", rawmpi, rawmpilen);
613   gcry_mpi_set_opaque (s, rawmpi, rawmpilen*8);
614   rawmpi = NULL;
615
616   rc = 0;
617
618  leave:
619   gcry_mpi_release (a);
620   gcry_mpi_release (x);
621   gcry_mpi_release (y);
622   gcry_mpi_release (r);
623   gcry_free (digest);
624   _gcry_mpi_ec_free (ctx);
625   point_free (&I);
626   point_free (&Q);
627   gcry_free (encpk);
628   gcry_free (rawmpi);
629   return rc;
630 }
631
632
633 /* Verify an EdDSA signature.  See sign_eddsa for the reference.
634  * Check if R_IN and S_IN verifies INPUT.  PKEY has the curve
635  * parameters and PK is the EdDSA style encoded public key.
636  */
637 gpg_err_code_t
638 _gcry_ecc_eddsa_verify (gcry_mpi_t input, ECC_public_key *pkey,
639                         gcry_mpi_t r_in, gcry_mpi_t s_in, int hashalgo,
640                         gcry_mpi_t pk)
641 {
642   int rc;
643   mpi_ec_t ctx = NULL;
644   int b;
645   unsigned int tmp;
646   mpi_point_struct Q;          /* Public key.  */
647   unsigned char *encpk = NULL; /* Encoded public key.  */
648   unsigned int encpklen;
649   const void *mbuf, *rbuf;
650   unsigned char *tbuf = NULL;
651   size_t mlen, rlen;
652   unsigned int tlen;
653   unsigned char digest[64];
654   gcry_buffer_t hvec[3];
655   gcry_mpi_t h, s;
656   mpi_point_struct Ia, Ib;
657
658   if (!mpi_is_opaque (input) || !mpi_is_opaque (r_in) || !mpi_is_opaque (s_in))
659     return GPG_ERR_INV_DATA;
660   if (hashalgo != GCRY_MD_SHA512)
661     return GPG_ERR_DIGEST_ALGO;
662
663   point_init (&Q);
664   point_init (&Ia);
665   point_init (&Ib);
666   h = mpi_new (0);
667   s = mpi_new (0);
668
669   ctx = _gcry_mpi_ec_p_internal_new (pkey->E.model, pkey->E.dialect, 0,
670                                      pkey->E.p, pkey->E.a, pkey->E.b);
671   b = ctx->nbits/8;
672   if (b != 256/8)
673     return GPG_ERR_INTERNAL; /* We only support 256 bit. */
674
675   /* Decode and check the public key.  */
676   rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q, &encpk, &encpklen);
677   if (rc)
678     goto leave;
679   if (!_gcry_mpi_ec_curve_point (&Q, ctx))
680     {
681       rc = GPG_ERR_BROKEN_PUBKEY;
682       goto leave;
683     }
684   if (DBG_CIPHER)
685     log_printhex ("  e_pk", encpk, encpklen);
686   if (encpklen != b)
687     {
688       rc = GPG_ERR_INV_LENGTH;
689       goto leave;
690     }
691
692   /* Convert the other input parameters.  */
693   mbuf = gcry_mpi_get_opaque (input, &tmp);
694   mlen = (tmp +7)/8;
695   if (DBG_CIPHER)
696     log_printhex ("     m", mbuf, mlen);
697   rbuf = gcry_mpi_get_opaque (r_in, &tmp);
698   rlen = (tmp +7)/8;
699   if (DBG_CIPHER)
700     log_printhex ("     r", rbuf, rlen);
701   if (rlen != b)
702     {
703       rc = GPG_ERR_INV_LENGTH;
704       goto leave;
705     }
706
707   /* h = H(encodepoint(R) + encodepoint(pk) + m)  */
708   hvec[0].data = (char*)rbuf;
709   hvec[0].off  = 0;
710   hvec[0].len  = rlen;
711   hvec[1].data = encpk;
712   hvec[1].off  = 0;
713   hvec[1].len  = encpklen;
714   hvec[2].data = (char*)mbuf;
715   hvec[2].off  = 0;
716   hvec[2].len  = mlen;
717   rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
718   if (rc)
719     goto leave;
720   reverse_buffer (digest, 64);
721   if (DBG_CIPHER)
722     log_printhex (" H(R+)", digest, 64);
723   _gcry_mpi_set_buffer (h, digest, 64, 0);
724
725   /* According to the paper the best way for verification is:
726          encodepoint(sG - h·Q) = encodepoint(r)
727      because we don't need to decode R. */
728   {
729     void *sbuf;
730     unsigned int slen;
731
732     sbuf = _gcry_mpi_get_opaque_copy (s_in, &tmp);
733     slen = (tmp +7)/8;
734     reverse_buffer (sbuf, slen);
735     if (DBG_CIPHER)
736       log_printhex ("     s", sbuf, slen);
737     _gcry_mpi_set_buffer (s, sbuf, slen, 0);
738     gcry_free (sbuf);
739     if (slen != b)
740       {
741         rc = GPG_ERR_INV_LENGTH;
742         goto leave;
743       }
744   }
745
746   _gcry_mpi_ec_mul_point (&Ia, s, &pkey->E.G, ctx);
747   _gcry_mpi_ec_mul_point (&Ib, h, &Q, ctx);
748   _gcry_mpi_neg (Ib.x, Ib.x);
749   _gcry_mpi_ec_add_points (&Ia, &Ia, &Ib, ctx);
750   rc = _gcry_ecc_eddsa_encodepoint (&Ia, ctx, s, h, &tbuf, &tlen);
751   if (rc)
752     goto leave;
753   if (tlen != rlen || memcmp (tbuf, rbuf, tlen))
754     {
755       rc = GPG_ERR_BAD_SIGNATURE;
756       goto leave;
757     }
758
759   rc = 0;
760
761  leave:
762   gcry_free (encpk);
763   gcry_free (tbuf);
764   _gcry_mpi_ec_free (ctx);
765   gcry_mpi_release (s);
766   gcry_mpi_release (h);
767   point_free (&Ia);
768   point_free (&Ib);
769   point_free (&Q);
770   return rc;
771 }