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