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. */
32static gcry_mpi_t
33mpi_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 */
87static int
88mpi_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. */
182void
183gcry_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. */
216void
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.  */
231static unsigned char *
232do_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
281byte *
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
287byte *
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 */
298void
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  nlimbs = (nbytes + BYTES_PER_MPI_LIMB - 1) / BYTES_PER_MPI_LIMB;
309  RESIZE_IF_NEEDED(a, nlimbs);
310  a->sign = sign;
311
312  for (i=0, p = buffer+nbytes-1; p >= buffer+BYTES_PER_MPI_LIMB; )
313    {
314#if BYTES_PER_MPI_LIMB == 4
315      alimb  = *p--	    ;
316      alimb |= *p-- <<  8 ;
317      alimb |= *p-- << 16 ;
318      alimb |= *p-- << 24 ;
319#elif BYTES_PER_MPI_LIMB == 8
320      alimb  = (mpi_limb_t)*p--	;
321      alimb |= (mpi_limb_t)*p-- <<  8 ;
322      alimb |= (mpi_limb_t)*p-- << 16 ;
323      alimb |= (mpi_limb_t)*p-- << 24 ;
324      alimb |= (mpi_limb_t)*p-- << 32 ;
325      alimb |= (mpi_limb_t)*p-- << 40 ;
326      alimb |= (mpi_limb_t)*p-- << 48 ;
327      alimb |= (mpi_limb_t)*p-- << 56 ;
328#else
329#       error please implement for this limb size.
330#endif
331      a->d[i++] = alimb;
332    }
333  if ( p >= buffer )
334    {
335#if BYTES_PER_MPI_LIMB == 4
336      alimb  = *p--;
337      if (p >= buffer)
338        alimb |= *p-- <<  8;
339      if (p >= buffer)
340        alimb |= *p-- << 16;
341      if (p >= buffer)
342        alimb |= *p-- << 24;
343#elif BYTES_PER_MPI_LIMB == 8
344      alimb  = (mpi_limb_t)*p--;
345      if (p >= buffer)
346        alimb |= (mpi_limb_t)*p-- << 8;
347      if (p >= buffer)
348        alimb |= (mpi_limb_t)*p-- << 16;
349      if (p >= buffer)
350        alimb |= (mpi_limb_t)*p-- << 24;
351      if (p >= buffer)
352        alimb |= (mpi_limb_t)*p-- << 32;
353      if (p >= buffer)
354        alimb |= (mpi_limb_t)*p-- << 40;
355      if (p >= buffer)
356        alimb |= (mpi_limb_t)*p-- << 48;
357      if (p >= buffer)
358        alimb |= (mpi_limb_t)*p-- << 56;
359#else
360#     error please implement for this limb size.
361#endif
362      a->d[i++] = alimb;
363    }
364  a->nlimbs = i;
365  gcry_assert (i == nlimbs);
366}
367
368
369/* Convert the external representation of an integer stored in BUFFER
370   with a length of BUFLEN into a newly create MPI returned in
371   RET_MPI.  If NBYTES is not NULL, it will receive the number of
372   bytes actually scanned after a successful operation.  */
373gcry_error_t
374gcry_mpi_scan (struct gcry_mpi **ret_mpi, enum gcry_mpi_format format,
375               const void *buffer_arg, size_t buflen, size_t *nscanned)
376{
377  const unsigned char *buffer = (const unsigned char*)buffer_arg;
378  struct gcry_mpi *a = NULL;
379  unsigned int len;
380  int secure = (buffer && gcry_is_secure (buffer));
381
382  if (format == GCRYMPI_FMT_SSH)
383    len = 0;
384  else
385    len = buflen;
386
387  if (format == GCRYMPI_FMT_STD)
388    {
389      const unsigned char *s = buffer;
390
391      a = secure? mpi_alloc_secure ((len+BYTES_PER_MPI_LIMB-1)
392                                    /BYTES_PER_MPI_LIMB)
393                : mpi_alloc ((len+BYTES_PER_MPI_LIMB-1)/BYTES_PER_MPI_LIMB);
394      if (len)
395        {
396          a->sign = !!(*s & 0x80);
397          if (a->sign)
398            {
399              /* FIXME: we have to convert from 2compl to magnitude format */
400              mpi_free (a);
401              return gcry_error (GPG_ERR_INTERNAL);
402	    }
403          else
404            _gcry_mpi_set_buffer (a, s, len, 0);
405	}
406      if (ret_mpi)
407        {
408          mpi_normalize ( a );
409          *ret_mpi = a;
410	}
411      else
412        mpi_free(a);
413      return 0;
414    }
415  else if (format == GCRYMPI_FMT_USG)
416    {
417      a = secure? mpi_alloc_secure ((len+BYTES_PER_MPI_LIMB-1)
418                                    /BYTES_PER_MPI_LIMB)
419                : mpi_alloc ((len+BYTES_PER_MPI_LIMB-1)/BYTES_PER_MPI_LIMB);
420
421      if (len)
422        _gcry_mpi_set_buffer (a, buffer, len, 0);
423      if (ret_mpi)
424        {
425          mpi_normalize ( a );
426          *ret_mpi = a;
427	}
428      else
429        mpi_free(a);
430      return 0;
431    }
432  else if (format == GCRYMPI_FMT_PGP)
433    {
434      a = mpi_read_from_buffer (buffer, &len, secure);
435      if (nscanned)
436        *nscanned = len;
437      if (ret_mpi && a)
438        {
439          mpi_normalize (a);
440          *ret_mpi = a;
441	}
442      else if (a)
443        {
444          mpi_free(a);
445          a = NULL;
446        }
447      return a? 0 : gcry_error (GPG_ERR_INV_OBJ);
448    }
449  else if (format == GCRYMPI_FMT_SSH)
450    {
451      const unsigned char *s = buffer;
452      size_t n;
453
454      /* This test is not strictly necessary and an assert (!len)
455         would be sufficient.  We keep this test in case we later
456         allow the BUFLEN argument to act as a sanitiy check.  Same
457         below. */
458      if (len && len < 4)
459        return gcry_error (GPG_ERR_TOO_SHORT);
460
461      n = (s[0] << 24 | s[1] << 16 | s[2] << 8 | s[3]);
462      s += 4;
463      if (len)
464        len -= 4;
465      if (len && n > len)
466        return gcry_error (GPG_ERR_TOO_LARGE);
467
468      a = secure? mpi_alloc_secure ((n+BYTES_PER_MPI_LIMB-1)
469                                    /BYTES_PER_MPI_LIMB)
470                : mpi_alloc ((n+BYTES_PER_MPI_LIMB-1)/BYTES_PER_MPI_LIMB);
471      if (n)
472        {
473          a->sign = !!(*s & 0x80);
474          if (a->sign)
475            {
476              /* FIXME: we have to convert from 2compl to magnitude format */
477              mpi_free(a);
478              return gcry_error (GPG_ERR_INTERNAL);
479	    }
480          else
481            _gcry_mpi_set_buffer( a, s, n, 0 );
482	}
483      if (nscanned)
484        *nscanned = n+4;
485      if (ret_mpi)
486        {
487          mpi_normalize ( a );
488          *ret_mpi = a;
489        }
490      else
491        mpi_free(a);
492      return 0;
493    }
494  else if (format == GCRYMPI_FMT_HEX)
495    {
496      /* We can only handle C strings for now.  */
497      if (buflen)
498        return gcry_error (GPG_ERR_INV_ARG);
499
500      a = secure? mpi_alloc_secure (0) : mpi_alloc(0);
501      if (mpi_fromstr (a, (const char *)buffer))
502        {
503          mpi_free (a);
504          return gcry_error (GPG_ERR_INV_OBJ);
505        }
506      if (ret_mpi)
507        {
508          mpi_normalize ( a );
509          *ret_mpi = a;
510	}
511      else
512        mpi_free(a);
513      return 0;
514    }
515  else
516    return gcry_error (GPG_ERR_INV_ARG);
517}
518
519
520/* Convert the big integer A into the external representation
521   described by FORMAT and store it in the provided BUFFER which has
522   been allocated by the user with a size of BUFLEN bytes.  NWRITTEN
523   receives the actual length of the external representation unless it
524   has been passed as NULL.  BUFFER may be NULL to query the required
525   length.  */
526gcry_error_t
527gcry_mpi_print (enum gcry_mpi_format format,
528                unsigned char *buffer, size_t buflen,
529                size_t *nwritten, struct gcry_mpi *a)
530{
531  unsigned int nbits = mpi_get_nbits (a);
532  size_t len;
533  size_t dummy_nwritten;
534
535  if (!nwritten)
536    nwritten = &dummy_nwritten;
537
538  len = buflen;
539  *nwritten = 0;
540  if (format == GCRYMPI_FMT_STD)
541    {
542      unsigned char *tmp;
543      int extra = 0;
544      unsigned int n;
545
546      if (a->sign)
547        return gcry_error (GPG_ERR_INTERNAL); /* Can't handle it yet. */
548
549      tmp = _gcry_mpi_get_buffer (a, &n, NULL);
550      if (!tmp)
551        return gpg_error_from_syserror ();
552      if (n && (*tmp & 0x80))
553        {
554          n++;
555          extra=1;
556	}
557
558      if (buffer && n > len)
559        {
560          /* The provided buffer is too short. */
561          gcry_free (tmp);
562          return gcry_error (GPG_ERR_TOO_SHORT);
563	}
564      if (buffer)
565        {
566          unsigned char *s = buffer;
567
568          if (extra)
569            *s++ = 0;
570          memcpy (s, tmp, n-extra);
571	}
572      gcry_free(tmp);
573      *nwritten = n;
574      return 0;
575    }
576  else if (format == GCRYMPI_FMT_USG)
577    {
578      unsigned int n = (nbits + 7)/8;
579
580      /* Note:  We ignore the sign for this format.  */
581      /* FIXME: for performance reasons we should put this into
582	 mpi_aprint because we can then use the buffer directly.  */
583      if (buffer && n > len)
584        return gcry_error (GPG_ERR_TOO_SHORT);
585      if (buffer)
586        {
587          unsigned char *tmp;
588
589          tmp = _gcry_mpi_get_buffer (a, &n, NULL);
590          if (!tmp)
591            return gpg_error_from_syserror ();
592          memcpy (buffer, tmp, n);
593          gcry_free (tmp);
594	}
595      *nwritten = n;
596      return 0;
597    }
598  else if (format == GCRYMPI_FMT_PGP)
599    {
600      unsigned int n = (nbits + 7)/8;
601
602      /* The PGP format can only handle unsigned integers.  */
603      if( a->sign )
604        return gcry_error (GPG_ERR_INV_ARG);
605
606      if (buffer && n+2 > len)
607        return gcry_error (GPG_ERR_TOO_SHORT);
608
609      if (buffer)
610        {
611          unsigned char *tmp;
612          unsigned char *s = buffer;
613
614          s[0] = nbits >> 8;
615          s[1] = nbits;
616
617          tmp = _gcry_mpi_get_buffer (a, &n, NULL);
618          if (!tmp)
619            return gpg_error_from_syserror ();
620          memcpy (s+2, tmp, n);
621          gcry_free (tmp);
622	}
623      *nwritten = n+2;
624      return 0;
625    }
626  else if (format == GCRYMPI_FMT_SSH)
627    {
628      unsigned char *tmp;
629      int extra = 0;
630      unsigned int n;
631
632      if (a->sign)
633        return gcry_error (GPG_ERR_INTERNAL); /* Can't handle it yet.  */
634
635      tmp = _gcry_mpi_get_buffer (a, &n, NULL);
636      if (!tmp)
637        return gpg_error_from_syserror ();
638      if (n && (*tmp & 0x80))
639        {
640          n++;
641          extra=1;
642	}
643
644      if (buffer && n+4 > len)
645        {
646          gcry_free(tmp);
647          return gcry_error (GPG_ERR_TOO_SHORT);
648	}
649
650      if (buffer)
651        {
652          unsigned char *s = buffer;
653
654          *s++ = n >> 24;
655          *s++ = n >> 16;
656          *s++ = n >> 8;
657          *s++ = n;
658          if (extra)
659            *s++ = 0;
660
661          memcpy (s, tmp, n-extra);
662	}
663      gcry_free (tmp);
664      *nwritten = 4+n;
665      return 0;
666    }
667  else if (format == GCRYMPI_FMT_HEX)
668    {
669      unsigned char *tmp;
670      int i;
671      int extra = 0;
672      unsigned int n = 0;
673
674      tmp = _gcry_mpi_get_buffer (a, &n, NULL);
675      if (!tmp)
676        return gpg_error_from_syserror ();
677      if (!n || (*tmp & 0x80))
678        extra = 2;
679
680      if (buffer && 2*n + extra + !!a->sign + 1 > len)
681        {
682          gcry_free(tmp);
683          return gcry_error (GPG_ERR_TOO_SHORT);
684	}
685      if (buffer)
686        {
687          unsigned char *s = buffer;
688
689          if (a->sign)
690            *s++ = '-';
691          if (extra)
692            {
693              *s++ = '0';
694              *s++ = '0';
695	    }
696
697          for (i=0; i < n; i++)
698            {
699              unsigned int c = tmp[i];
700
701              *s++ = (c >> 4) < 10? '0'+(c>>4) : 'A'+(c>>4)-10 ;
702              c &= 15;
703              *s++ = c < 10? '0'+c : 'A'+c-10 ;
704	    }
705          *s++ = 0;
706          *nwritten = s - buffer;
707	}
708      else
709        {
710          *nwritten = 2*n + extra + !!a->sign + 1;
711	}
712      gcry_free (tmp);
713      return 0;
714    }
715  else
716    return gcry_error (GPG_ERR_INV_ARG);
717}
718
719
720/*
721 * Like gcry_mpi_print but this function allocates the buffer itself.
722 * The caller has to supply the address of a pointer.  NWRITTEN may be
723 * NULL.
724 */
725gcry_error_t
726gcry_mpi_aprint (enum gcry_mpi_format format,
727                 unsigned char **buffer, size_t *nwritten,
728		 struct gcry_mpi *a)
729{
730  size_t n;
731  gcry_error_t rc;
732
733  *buffer = NULL;
734  rc = gcry_mpi_print (format, NULL, 0, &n, a);
735  if (rc)
736    return rc;
737
738  *buffer = mpi_is_secure(a) ? gcry_malloc_secure (n) : gcry_malloc (n);
739  if (!*buffer)
740    return gpg_error_from_syserror ();
741  rc = gcry_mpi_print( format, *buffer, n, &n, a );
742  if (rc)
743    {
744      gcry_free(*buffer);
745      *buffer = NULL;
746    }
747  else if (nwritten)
748    *nwritten = n;
749  return rc;
750}
751