Fix a special case bug in mpi_powm for e==0.
[libgcrypt.git] / mpi / mpicoder.c
1 /* mpicoder.c  -  Coder for the external representation of MPIs
2  * Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003
3  *               2008 Free Software Foundation, Inc.
4  *
5  * This file is part of Libgcrypt.
6  *
7  * Libgcrypt is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU Lesser General Public License as
9  * published by the Free Software Foundation; either version 2.1 of
10  * the License, or (at your option) any later version.
11  *
12  * Libgcrypt is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with this program; if not, see <http://www.gnu.org/licenses/>.
19  */
20
21 #include <config.h>
22 #include <stdio.h>
23 #include <string.h>
24 #include <stdlib.h>
25
26 #include "mpi-internal.h"
27 #include "g10lib.h"
28
29 #define MAX_EXTERN_MPI_BITS 16384
30
31 /* Helper used to scan PGP style MPIs.  Returns NULL on failure. */
32 static gcry_mpi_t
33 mpi_read_from_buffer (const unsigned char *buffer, unsigned *ret_nread,
34                       int secure)
35 {
36   int i, j;
37   unsigned int nbits, nbytes, nlimbs, nread=0;
38   mpi_limb_t a;
39   gcry_mpi_t val = MPI_NULL;
40
41   if ( *ret_nread < 2 )
42     goto leave;
43   nbits = buffer[0] << 8 | buffer[1];
44   if ( nbits > MAX_EXTERN_MPI_BITS )
45     {
46 /*       log_debug ("mpi too large (%u bits)\n", nbits); */
47       goto leave;
48     }
49   buffer += 2;
50   nread = 2;
51
52   nbytes = (nbits+7) / 8;
53   nlimbs = (nbytes+BYTES_PER_MPI_LIMB-1) / BYTES_PER_MPI_LIMB;
54   val = secure? mpi_alloc_secure (nlimbs) : mpi_alloc (nlimbs);
55   i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
56   i %= BYTES_PER_MPI_LIMB;
57   j= val->nlimbs = nlimbs;
58   val->sign = 0;
59   for ( ; j > 0; j-- )
60     {
61       a = 0;
62       for (; i < BYTES_PER_MPI_LIMB; i++ )
63         {
64           if ( ++nread > *ret_nread )
65             {
66 /*               log_debug ("mpi larger than buffer"); */
67               mpi_free (val);
68               val = NULL;
69               goto leave;
70             }
71           a <<= 8;
72           a |= *buffer++;
73         }
74       i = 0;
75       val->d[j-1] = a;
76     }
77
78  leave:
79   *ret_nread = nread;
80   return val;
81 }
82
83
84 /****************
85  * Fill the mpi VAL from the hex string in STR.
86  */
87 static int
88 mpi_fromstr (gcry_mpi_t val, const char *str)
89 {
90   int sign = 0;
91   int prepend_zero = 0;
92   int i, j, c, c1, c2;
93   unsigned int nbits, nbytes, nlimbs;
94   mpi_limb_t a;
95
96   if ( *str == '-' )
97     {
98       sign = 1;
99       str++;
100     }
101
102   /* Skip optional hex prefix.  */
103   if ( *str == '0' && str[1] == 'x' )
104     str += 2;
105
106   nbits = 4 * strlen (str);
107   if ((nbits % 8))
108     prepend_zero = 1;
109
110   nbytes = (nbits+7) / 8;
111   nlimbs = (nbytes+BYTES_PER_MPI_LIMB-1) / BYTES_PER_MPI_LIMB;
112
113   if ( val->alloced < nlimbs )
114     mpi_resize (val, nlimbs);
115
116   i = BYTES_PER_MPI_LIMB - (nbytes % BYTES_PER_MPI_LIMB);
117   i %= BYTES_PER_MPI_LIMB;
118   j = val->nlimbs = nlimbs;
119   val->sign = sign;
120   for (; j > 0; j--)
121     {
122       a = 0;
123       for (; i < BYTES_PER_MPI_LIMB; i++)
124         {
125           if (prepend_zero)
126             {
127               c1 = '0';
128               prepend_zero = 0;
129             }
130           else
131             c1 = *str++;
132
133           if (!c1)
134             {
135               mpi_clear (val);
136               return 1;  /* Error.  */
137             }
138           c2 = *str++;
139           if (!c2)
140             {
141               mpi_clear (val);
142               return 1;  /* Error.  */
143             }
144           if ( c1 >= '0' && c1 <= '9' )
145             c = c1 - '0';
146           else if ( c1 >= 'a' && c1 <= 'f' )
147             c = c1 - 'a' + 10;
148           else if ( c1 >= 'A' && c1 <= 'F' )
149             c = c1 - 'A' + 10;
150           else
151             {
152               mpi_clear (val);
153               return 1;  /* Error.  */
154             }
155           c <<= 4;
156           if ( c2 >= '0' && c2 <= '9' )
157             c |= c2 - '0';
158           else if( c2 >= 'a' && c2 <= 'f' )
159             c |= c2 - 'a' + 10;
160           else if( c2 >= 'A' && c2 <= 'F' )
161             c |= c2 - 'A' + 10;
162           else
163             {
164               mpi_clear(val);
165               return 1;  /* Error. */
166             }
167           a <<= 8;
168           a |= c;
169         }
170       i = 0;
171       val->d[j-1] = a;
172     }
173
174   return 0;  /* Okay.  */
175 }
176
177
178 /* Dump the value of A in a format suitable for debugging to
179    Libgcrypt's logging stream.  Note that one leading space but no
180    trailing space or linefeed will be printed.  It is okay to pass
181    NULL for A. */
182 void
183 gcry_mpi_dump (const gcry_mpi_t a)
184 {
185   int i;
186
187   log_printf (" ");
188   if (!a)
189     log_printf ("[MPI_NULL]");
190   else
191     {
192       if (a->sign)
193         log_printf ( "-");
194 #if BYTES_PER_MPI_LIMB == 2
195 # define X "4"
196 #elif BYTES_PER_MPI_LIMB == 4
197 # define X "8"
198 #elif BYTES_PER_MPI_LIMB == 8
199 # define X "16"
200 #elif BYTES_PER_MPI_LIMB == 16
201 # define X "32"
202 #else
203 # error please define the format here
204 #endif
205       for (i=a->nlimbs; i > 0 ; i-- )
206         {
207           log_printf (i != a->nlimbs? "%0" X "lX":"%lX", (ulong)a->d[i-1]);
208         }
209 #undef X
210       if (!a->nlimbs)
211         log_printf ("0");
212     }
213 }
214
215 /* Convience function used internally. */
216 void
217 _gcry_log_mpidump (const char *text, gcry_mpi_t a)
218 {
219   log_printf ("%s:", text);
220   gcry_mpi_dump (a);
221   log_printf ("\n");
222 }
223
224
225 /* Return an allocated buffer with the MPI (msb first).  NBYTES
226    receives the length of this buffer.  Caller must free the return
227    string.  This function returns an allocated buffer with NBYTES set
228    to zero if the value of A is zero.  If sign is not NULL, it will be
229    set to the sign of the A.  On error NULL is returned and ERRNO set
230    appropriately.  */
231 static unsigned char *
232 do_get_buffer (gcry_mpi_t a, unsigned int *nbytes, int *sign, int force_secure)
233 {
234   unsigned char *p, *buffer;
235   mpi_limb_t alimb;
236   int i;
237   size_t n;
238
239   if (sign)
240     *sign = a->sign;
241
242   *nbytes = a->nlimbs * BYTES_PER_MPI_LIMB;
243   n = *nbytes? *nbytes:1; /* Allocate at least one byte.  */
244   p = buffer = (force_secure || mpi_is_secure(a))? gcry_malloc_secure (n)
245                                                  : gcry_malloc (n);
246   if (!buffer)
247     return NULL;
248
249   for (i=a->nlimbs-1; i >= 0; i--)
250     {
251       alimb = a->d[i];
252 #if BYTES_PER_MPI_LIMB == 4
253       *p++ = alimb >> 24;
254       *p++ = alimb >> 16;
255       *p++ = alimb >>  8;
256       *p++ = alimb        ;
257 #elif BYTES_PER_MPI_LIMB == 8
258       *p++ = alimb >> 56;
259       *p++ = alimb >> 48;
260       *p++ = alimb >> 40;
261       *p++ = alimb >> 32;
262       *p++ = alimb >> 24;
263       *p++ = alimb >> 16;
264       *p++ = alimb >>  8;
265       *p++ = alimb        ;
266 #else
267 #     error please implement for this limb size.
268 #endif
269     }
270
271   /* This is sub-optimal but we need to do the shift operation because
272      the caller has to free the returned buffer.  */
273   for (p=buffer; *nbytes && !*p; p++, --*nbytes)
274     ;
275   if (p != buffer)
276     memmove (buffer,p, *nbytes);
277   return buffer;
278 }
279
280
281 byte *
282 _gcry_mpi_get_buffer (gcry_mpi_t a, unsigned int *nbytes, int *sign)
283 {
284   return do_get_buffer (a, nbytes, sign, 0);
285 }
286
287 byte *
288 _gcry_mpi_get_secure_buffer (gcry_mpi_t a, unsigned *nbytes, int *sign)
289 {
290   return do_get_buffer (a, nbytes, sign, 1);
291 }
292
293
294 /*
295  * Use the NBYTES at BUFFER_ARG to update A.  Set the sign of a to
296  * SIGN.
297  */
298 void
299 _gcry_mpi_set_buffer (gcry_mpi_t a, const void *buffer_arg,
300                       unsigned int nbytes, int sign)
301 {
302   const unsigned char *buffer = (const unsigned char*)buffer_arg;
303   const unsigned char *p;
304   mpi_limb_t alimb;
305   int nlimbs;
306   int i;
307
308   if (mpi_is_immutable (a))
309     {
310       mpi_immutable_failed ();
311       return;
312     }
313
314   nlimbs = (nbytes + BYTES_PER_MPI_LIMB - 1) / BYTES_PER_MPI_LIMB;
315   RESIZE_IF_NEEDED(a, nlimbs);
316   a->sign = sign;
317
318   for (i=0, p = buffer+nbytes-1; p >= buffer+BYTES_PER_MPI_LIMB; )
319     {
320 #if BYTES_PER_MPI_LIMB == 4
321       alimb  = *p--         ;
322       alimb |= *p-- <<  8 ;
323       alimb |= *p-- << 16 ;
324       alimb |= *p-- << 24 ;
325 #elif BYTES_PER_MPI_LIMB == 8
326       alimb  = (mpi_limb_t)*p-- ;
327       alimb |= (mpi_limb_t)*p-- <<  8 ;
328       alimb |= (mpi_limb_t)*p-- << 16 ;
329       alimb |= (mpi_limb_t)*p-- << 24 ;
330       alimb |= (mpi_limb_t)*p-- << 32 ;
331       alimb |= (mpi_limb_t)*p-- << 40 ;
332       alimb |= (mpi_limb_t)*p-- << 48 ;
333       alimb |= (mpi_limb_t)*p-- << 56 ;
334 #else
335 #       error please implement for this limb size.
336 #endif
337       a->d[i++] = alimb;
338     }
339   if ( p >= buffer )
340     {
341 #if BYTES_PER_MPI_LIMB == 4
342       alimb  = *p--;
343       if (p >= buffer)
344         alimb |= *p-- <<  8;
345       if (p >= buffer)
346         alimb |= *p-- << 16;
347       if (p >= buffer)
348         alimb |= *p-- << 24;
349 #elif BYTES_PER_MPI_LIMB == 8
350       alimb  = (mpi_limb_t)*p--;
351       if (p >= buffer)
352         alimb |= (mpi_limb_t)*p-- << 8;
353       if (p >= buffer)
354         alimb |= (mpi_limb_t)*p-- << 16;
355       if (p >= buffer)
356         alimb |= (mpi_limb_t)*p-- << 24;
357       if (p >= buffer)
358         alimb |= (mpi_limb_t)*p-- << 32;
359       if (p >= buffer)
360         alimb |= (mpi_limb_t)*p-- << 40;
361       if (p >= buffer)
362         alimb |= (mpi_limb_t)*p-- << 48;
363       if (p >= buffer)
364         alimb |= (mpi_limb_t)*p-- << 56;
365 #else
366 #     error please implement for this limb size.
367 #endif
368       a->d[i++] = alimb;
369     }
370   a->nlimbs = i;
371   gcry_assert (i == nlimbs);
372 }
373
374
375 /* Convert the external representation of an integer stored in BUFFER
376    with a length of BUFLEN into a newly create MPI returned in
377    RET_MPI.  If NBYTES is not NULL, it will receive the number of
378    bytes actually scanned after a successful operation.  */
379 gcry_error_t
380 gcry_mpi_scan (struct gcry_mpi **ret_mpi, enum gcry_mpi_format format,
381                const void *buffer_arg, size_t buflen, size_t *nscanned)
382 {
383   const unsigned char *buffer = (const unsigned char*)buffer_arg;
384   struct gcry_mpi *a = NULL;
385   unsigned int len;
386   int secure = (buffer && gcry_is_secure (buffer));
387
388   if (format == GCRYMPI_FMT_SSH)
389     len = 0;
390   else
391     len = buflen;
392
393   if (format == GCRYMPI_FMT_STD)
394     {
395       const unsigned char *s = buffer;
396
397       a = secure? mpi_alloc_secure ((len+BYTES_PER_MPI_LIMB-1)
398                                     /BYTES_PER_MPI_LIMB)
399                 : mpi_alloc ((len+BYTES_PER_MPI_LIMB-1)/BYTES_PER_MPI_LIMB);
400       if (len)
401         {
402           a->sign = !!(*s & 0x80);
403           if (a->sign)
404             {
405               /* FIXME: we have to convert from 2compl to magnitude format */
406               mpi_free (a);
407               return gcry_error (GPG_ERR_INTERNAL);
408             }
409           else
410             _gcry_mpi_set_buffer (a, s, len, 0);
411         }
412       if (ret_mpi)
413         {
414           mpi_normalize ( a );
415           *ret_mpi = a;
416         }
417       else
418         mpi_free(a);
419       return 0;
420     }
421   else if (format == GCRYMPI_FMT_USG)
422     {
423       a = secure? mpi_alloc_secure ((len+BYTES_PER_MPI_LIMB-1)
424                                     /BYTES_PER_MPI_LIMB)
425                 : mpi_alloc ((len+BYTES_PER_MPI_LIMB-1)/BYTES_PER_MPI_LIMB);
426
427       if (len)
428         _gcry_mpi_set_buffer (a, buffer, len, 0);
429       if (ret_mpi)
430         {
431           mpi_normalize ( a );
432           *ret_mpi = a;
433         }
434       else
435         mpi_free(a);
436       return 0;
437     }
438   else if (format == GCRYMPI_FMT_PGP)
439     {
440       a = mpi_read_from_buffer (buffer, &len, secure);
441       if (nscanned)
442         *nscanned = len;
443       if (ret_mpi && a)
444         {
445           mpi_normalize (a);
446           *ret_mpi = a;
447         }
448       else if (a)
449         {
450           mpi_free(a);
451           a = NULL;
452         }
453       return a? 0 : gcry_error (GPG_ERR_INV_OBJ);
454     }
455   else if (format == GCRYMPI_FMT_SSH)
456     {
457       const unsigned char *s = buffer;
458       size_t n;
459
460       /* This test is not strictly necessary and an assert (!len)
461          would be sufficient.  We keep this test in case we later
462          allow the BUFLEN argument to act as a sanitiy check.  Same
463          below. */
464       if (len && len < 4)
465         return gcry_error (GPG_ERR_TOO_SHORT);
466
467       n = (s[0] << 24 | s[1] << 16 | s[2] << 8 | s[3]);
468       s += 4;
469       if (len)
470         len -= 4;
471       if (len && n > len)
472         return gcry_error (GPG_ERR_TOO_LARGE);
473
474       a = secure? mpi_alloc_secure ((n+BYTES_PER_MPI_LIMB-1)
475                                     /BYTES_PER_MPI_LIMB)
476                 : mpi_alloc ((n+BYTES_PER_MPI_LIMB-1)/BYTES_PER_MPI_LIMB);
477       if (n)
478         {
479           a->sign = !!(*s & 0x80);
480           if (a->sign)
481             {
482               /* FIXME: we have to convert from 2compl to magnitude format */
483               mpi_free(a);
484               return gcry_error (GPG_ERR_INTERNAL);
485             }
486           else
487             _gcry_mpi_set_buffer( a, s, n, 0 );
488         }
489       if (nscanned)
490         *nscanned = n+4;
491       if (ret_mpi)
492         {
493           mpi_normalize ( a );
494           *ret_mpi = a;
495         }
496       else
497         mpi_free(a);
498       return 0;
499     }
500   else if (format == GCRYMPI_FMT_HEX)
501     {
502       /* We can only handle C strings for now.  */
503       if (buflen)
504         return gcry_error (GPG_ERR_INV_ARG);
505
506       a = secure? mpi_alloc_secure (0) : mpi_alloc(0);
507       if (mpi_fromstr (a, (const char *)buffer))
508         {
509           mpi_free (a);
510           return gcry_error (GPG_ERR_INV_OBJ);
511         }
512       if (ret_mpi)
513         {
514           mpi_normalize ( a );
515           *ret_mpi = a;
516         }
517       else
518         mpi_free(a);
519       return 0;
520     }
521   else
522     return gcry_error (GPG_ERR_INV_ARG);
523 }
524
525
526 /* Convert the big integer A into the external representation
527    described by FORMAT and store it in the provided BUFFER which has
528    been allocated by the user with a size of BUFLEN bytes.  NWRITTEN
529    receives the actual length of the external representation unless it
530    has been passed as NULL.  BUFFER may be NULL to query the required
531    length.  */
532 gcry_error_t
533 gcry_mpi_print (enum gcry_mpi_format format,
534                 unsigned char *buffer, size_t buflen,
535                 size_t *nwritten, struct gcry_mpi *a)
536 {
537   unsigned int nbits = mpi_get_nbits (a);
538   size_t len;
539   size_t dummy_nwritten;
540
541   if (!nwritten)
542     nwritten = &dummy_nwritten;
543
544   len = buflen;
545   *nwritten = 0;
546   if (format == GCRYMPI_FMT_STD)
547     {
548       unsigned char *tmp;
549       int extra = 0;
550       unsigned int n;
551
552       if (a->sign)
553         return gcry_error (GPG_ERR_INTERNAL); /* Can't handle it yet. */
554
555       tmp = _gcry_mpi_get_buffer (a, &n, NULL);
556       if (!tmp)
557         return gpg_error_from_syserror ();
558       if (n && (*tmp & 0x80))
559         {
560           n++;
561           extra=1;
562         }
563
564       if (buffer && n > len)
565         {
566           /* The provided buffer is too short. */
567           gcry_free (tmp);
568           return gcry_error (GPG_ERR_TOO_SHORT);
569         }
570       if (buffer)
571         {
572           unsigned char *s = buffer;
573
574           if (extra)
575             *s++ = 0;
576           memcpy (s, tmp, n-extra);
577         }
578       gcry_free(tmp);
579       *nwritten = n;
580       return 0;
581     }
582   else if (format == GCRYMPI_FMT_USG)
583     {
584       unsigned int n = (nbits + 7)/8;
585
586       /* Note:  We ignore the sign for this format.  */
587       /* FIXME: for performance reasons we should put this into
588          mpi_aprint because we can then use the buffer directly.  */
589       if (buffer && n > len)
590         return gcry_error (GPG_ERR_TOO_SHORT);
591       if (buffer)
592         {
593           unsigned char *tmp;
594
595           tmp = _gcry_mpi_get_buffer (a, &n, NULL);
596           if (!tmp)
597             return gpg_error_from_syserror ();
598           memcpy (buffer, tmp, n);
599           gcry_free (tmp);
600         }
601       *nwritten = n;
602       return 0;
603     }
604   else if (format == GCRYMPI_FMT_PGP)
605     {
606       unsigned int n = (nbits + 7)/8;
607
608       /* The PGP format can only handle unsigned integers.  */
609       if( a->sign )
610         return gcry_error (GPG_ERR_INV_ARG);
611
612       if (buffer && n+2 > len)
613         return gcry_error (GPG_ERR_TOO_SHORT);
614
615       if (buffer)
616         {
617           unsigned char *tmp;
618           unsigned char *s = buffer;
619
620           s[0] = nbits >> 8;
621           s[1] = nbits;
622
623           tmp = _gcry_mpi_get_buffer (a, &n, NULL);
624           if (!tmp)
625             return gpg_error_from_syserror ();
626           memcpy (s+2, tmp, n);
627           gcry_free (tmp);
628         }
629       *nwritten = n+2;
630       return 0;
631     }
632   else if (format == GCRYMPI_FMT_SSH)
633     {
634       unsigned char *tmp;
635       int extra = 0;
636       unsigned int n;
637
638       if (a->sign)
639         return gcry_error (GPG_ERR_INTERNAL); /* Can't handle it yet.  */
640
641       tmp = _gcry_mpi_get_buffer (a, &n, NULL);
642       if (!tmp)
643         return gpg_error_from_syserror ();
644       if (n && (*tmp & 0x80))
645         {
646           n++;
647           extra=1;
648         }
649
650       if (buffer && n+4 > len)
651         {
652           gcry_free(tmp);
653           return gcry_error (GPG_ERR_TOO_SHORT);
654         }
655
656       if (buffer)
657         {
658           unsigned char *s = buffer;
659
660           *s++ = n >> 24;
661           *s++ = n >> 16;
662           *s++ = n >> 8;
663           *s++ = n;
664           if (extra)
665             *s++ = 0;
666
667           memcpy (s, tmp, n-extra);
668         }
669       gcry_free (tmp);
670       *nwritten = 4+n;
671       return 0;
672     }
673   else if (format == GCRYMPI_FMT_HEX)
674     {
675       unsigned char *tmp;
676       int i;
677       int extra = 0;
678       unsigned int n = 0;
679
680       tmp = _gcry_mpi_get_buffer (a, &n, NULL);
681       if (!tmp)
682         return gpg_error_from_syserror ();
683       if (!n || (*tmp & 0x80))
684         extra = 2;
685
686       if (buffer && 2*n + extra + !!a->sign + 1 > len)
687         {
688           gcry_free(tmp);
689           return gcry_error (GPG_ERR_TOO_SHORT);
690         }
691       if (buffer)
692         {
693           unsigned char *s = buffer;
694
695           if (a->sign)
696             *s++ = '-';
697           if (extra)
698             {
699               *s++ = '0';
700               *s++ = '0';
701             }
702
703           for (i=0; i < n; i++)
704             {
705               unsigned int c = tmp[i];
706
707               *s++ = (c >> 4) < 10? '0'+(c>>4) : 'A'+(c>>4)-10 ;
708               c &= 15;
709               *s++ = c < 10? '0'+c : 'A'+c-10 ;
710             }
711           *s++ = 0;
712           *nwritten = s - buffer;
713         }
714       else
715         {
716           *nwritten = 2*n + extra + !!a->sign + 1;
717         }
718       gcry_free (tmp);
719       return 0;
720     }
721   else
722     return gcry_error (GPG_ERR_INV_ARG);
723 }
724
725
726 /*
727  * Like gcry_mpi_print but this function allocates the buffer itself.
728  * The caller has to supply the address of a pointer.  NWRITTEN may be
729  * NULL.
730  */
731 gcry_error_t
732 gcry_mpi_aprint (enum gcry_mpi_format format,
733                  unsigned char **buffer, size_t *nwritten,
734                  struct gcry_mpi *a)
735 {
736   size_t n;
737   gcry_error_t rc;
738
739   *buffer = NULL;
740   rc = gcry_mpi_print (format, NULL, 0, &n, a);
741   if (rc)
742     return rc;
743
744   *buffer = mpi_is_secure(a) ? gcry_malloc_secure (n) : gcry_malloc (n);
745   if (!*buffer)
746     return gpg_error_from_syserror ();
747   rc = gcry_mpi_print( format, *buffer, n, &n, a );
748   if (rc)
749     {
750       gcry_free(*buffer);
751       *buffer = NULL;
752     }
753   else if (nwritten)
754     *nwritten = n;
755   return rc;
756 }