a0ae8f894d7d4eeb664d242d782a87930ce85b02
[libgcrypt.git] / mpi / mpicoder.c
1 /* mpicoder.c  -  Coder for the external representation of MPIs
2  * Copyright (C) 1998, 1999, 2000, 2001, 2002,
3  *               2003 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, write to the Free Software
19  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA   
20  */
21
22 #include <config.h>
23 #include <stdio.h>
24 #include <string.h>
25 #include <stdlib.h>
26 #include <assert.h>
27
28 #include "mpi-internal.h"
29 #include "g10lib.h"
30
31 #define MAX_EXTERN_MPI_BITS 16384
32
33
34 static gcry_mpi_t
35 mpi_read_from_buffer (const unsigned char *buffer, unsigned *ret_nread,
36                       int secure)
37 {
38   int i, j;
39   unsigned int nbits, nbytes, nlimbs, nread=0;
40   mpi_limb_t a;
41   gcry_mpi_t val = MPI_NULL;
42   
43   if ( *ret_nread < 2 )
44     goto leave;
45   nbits = buffer[0] << 8 | buffer[1];
46   if ( nbits > MAX_EXTERN_MPI_BITS )
47     {
48       log_error ("mpi too large (%u bits)\n", nbits);
49       goto leave;
50     }
51   else if( !nbits ) 
52     {
53       log_error ("an mpi of size 0 is not allowed\n");
54       goto leave;
55     }
56   buffer += 2;
57   nread = 2;
58
59   nbytes = (nbits+7) / 8;
60   nlimbs = (nbytes+BYTES_PER_MPI_LIMB-1) / BYTES_PER_MPI_LIMB;
61   val = secure? mpi_alloc_secure (nlimbs) : mpi_alloc( nlimbs );
62   i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
63   i %= BYTES_PER_MPI_LIMB;
64   j= val->nlimbs = nlimbs;
65   val->sign = 0;
66   for ( ; j > 0; j-- )
67     {
68       a = 0;
69       for (; i < BYTES_PER_MPI_LIMB; i++ ) 
70         {
71           if ( ++nread > *ret_nread )
72             log_bug ("mpi larger than buffer");
73           a <<= 8;
74           a |= *buffer++;
75         }
76       i = 0;
77       val->d[j-1] = a;
78     }
79   
80  leave:
81   *ret_nread = nread;
82   return val;
83 }
84
85
86 /****************
87  * Make an mpi from a hex character string.
88  */
89 static int
90 mpi_fromstr(gcry_mpi_t val, const char *str)
91 {
92     int sign=0, prepend_zero=0, i, j, c, c1, c2;
93     unsigned nbits, nbytes, nlimbs;
94     mpi_limb_t a;
95
96     if( *str == '-' ) {
97         sign = 1;
98         str++;
99     }
100
101     /* skip optional hex prefix */
102     if ( *str == '0' && str[1] == 'x' ) {
103         str += 2;
104     }
105
106     nbits = strlen(str)*4;
107     if( nbits % 8 )
108         prepend_zero = 1;
109     nbytes = (nbits+7) / 8;
110     nlimbs = (nbytes+BYTES_PER_MPI_LIMB-1) / BYTES_PER_MPI_LIMB;
111     if( val->alloced < nlimbs )
112         mpi_resize(val, nlimbs );
113     i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
114     i %= BYTES_PER_MPI_LIMB;
115     j= val->nlimbs = nlimbs;
116     val->sign = sign;
117     for( ; j > 0; j-- ) {
118         a = 0;
119         for(; i < BYTES_PER_MPI_LIMB; i++ ) {
120             if( prepend_zero ) {
121                 c1 = '0';
122                 prepend_zero = 0;
123             }
124             else
125                 c1 = *str++;
126             assert(c1);
127             c2 = *str++;
128             assert(c2);
129             if( c1 >= '0' && c1 <= '9' )
130                 c = c1 - '0';
131             else if( c1 >= 'a' && c1 <= 'f' )
132                 c = c1 - 'a' + 10;
133             else if( c1 >= 'A' && c1 <= 'F' )
134                 c = c1 - 'A' + 10;
135             else {
136                 mpi_clear(val);
137                 return 1;
138             }
139             c <<= 4;
140             if( c2 >= '0' && c2 <= '9' )
141                 c |= c2 - '0';
142             else if( c2 >= 'a' && c2 <= 'f' )
143                 c |= c2 - 'a' + 10;
144             else if( c2 >= 'A' && c2 <= 'F' )
145                 c |= c2 - 'A' + 10;
146             else {
147                 mpi_clear(val);
148                 return 1;
149             }
150             a <<= 8;
151             a |= c;
152         }
153         i = 0;
154         val->d[j-1] = a;
155     }
156
157     return 0;
158 }
159
160
161 /* Dump the value of A in a format suitable for debugging to
162    Libgcrypt's logging stream.  Note that one leading space but no
163    trailing space or linefeed will be printed.  It is okay to pass
164    NULL for A. */
165 void 
166 gcry_mpi_dump (const gcry_mpi_t a)
167 {
168   int i;
169
170   log_printf (" ");
171   if (!a)
172     log_printf ("[MPI_NULL]");
173   else 
174     {
175       if (a->sign)
176         log_printf ( "-");
177 #if BYTES_PER_MPI_LIMB == 2
178 # define X "4"
179 #elif BYTES_PER_MPI_LIMB == 4
180 # define X "8"
181 #elif BYTES_PER_MPI_LIMB == 8
182 # define X "16"
183 #elif BYTES_PER_MPI_LIMB == 16
184 # define X "32"
185 #else
186 # error please define the format here
187 #endif
188       for (i=a->nlimbs; i > 0 ; i-- )
189         {
190           log_printf (i != a->nlimbs? "%0" X "lX":"%lX", (ulong)a->d[i-1]);
191         }
192 #undef X
193       if (!a->nlimbs)
194         log_printf ("0");
195     }
196 }
197
198 /* Convience function used internally. */
199 void
200 _gcry_log_mpidump (const char *text, gcry_mpi_t a)
201 {
202   log_printf ("%s:", text);
203   gcry_mpi_dump (a);
204   log_printf ("\n");
205 }
206
207
208 /****************
209  * Return an m_alloced buffer with the MPI (msb first).
210  * NBYTES receives the length of this buffer. Caller must free the
211  * return string (This function does return a 0 byte buffer with NBYTES
212  * set to zero if the value of A is zero. If sign is not NULL, it will
213  * be set to the sign of the A.
214  */
215 static byte *
216 do_get_buffer( gcry_mpi_t a, unsigned *nbytes, int *sign, int force_secure )
217 {
218     byte *p, *buffer;
219     mpi_limb_t alimb;
220     int i;
221     size_t n;
222
223     if( sign )
224         *sign = a->sign;
225     *nbytes = a->nlimbs * BYTES_PER_MPI_LIMB;
226     n = *nbytes? *nbytes:1; /* allocate at least one byte */
227     p = buffer = force_secure || mpi_is_secure(a) ? gcry_xmalloc_secure(n)
228                                                   : gcry_xmalloc(n);
229
230     for(i=a->nlimbs-1; i >= 0; i-- ) {
231         alimb = a->d[i];
232 #if BYTES_PER_MPI_LIMB == 4
233         *p++ = alimb >> 24;
234         *p++ = alimb >> 16;
235         *p++ = alimb >>  8;
236         *p++ = alimb      ;
237 #elif BYTES_PER_MPI_LIMB == 8
238         *p++ = alimb >> 56;
239         *p++ = alimb >> 48;
240         *p++ = alimb >> 40;
241         *p++ = alimb >> 32;
242         *p++ = alimb >> 24;
243         *p++ = alimb >> 16;
244         *p++ = alimb >>  8;
245         *p++ = alimb      ;
246 #else
247         #error please implement for this limb size.
248 #endif
249     }
250
251     /* this is sub-optimal but we need to do the shift oepration because
252      * the caller has to free the returned buffer */
253     for(p=buffer; !*p && *nbytes; p++, --*nbytes )
254         ;
255     if( p != buffer )
256         memmove(buffer,p, *nbytes);
257     return buffer;
258 }
259
260
261 byte *
262 _gcry_mpi_get_buffer( gcry_mpi_t a, unsigned *nbytes, int *sign )
263 {
264     return do_get_buffer( a, nbytes, sign, 0 );
265 }
266
267 byte *
268 _gcry_mpi_get_secure_buffer( gcry_mpi_t a, unsigned *nbytes, int *sign )
269 {
270     return do_get_buffer( a, nbytes, sign, 1 );
271 }
272
273 /****************
274  * Use BUFFER to update MPI.
275  */
276 void
277 _gcry_mpi_set_buffer ( gcry_mpi_t a, const void *buffer_arg,
278                        unsigned int nbytes, int sign )
279 {
280     const unsigned char *buffer = (const unsigned char*)buffer_arg;
281     const byte *p;
282     mpi_limb_t alimb;
283     int nlimbs;
284     int i;
285
286     nlimbs = (nbytes + BYTES_PER_MPI_LIMB - 1) / BYTES_PER_MPI_LIMB;
287     RESIZE_IF_NEEDED(a, nlimbs);
288     a->sign = sign;
289
290     for(i=0, p = buffer+nbytes-1; p >= buffer+BYTES_PER_MPI_LIMB; ) {
291 #if BYTES_PER_MPI_LIMB == 4
292         alimb  = *p--       ;
293         alimb |= *p-- <<  8 ;
294         alimb |= *p-- << 16 ;
295         alimb |= *p-- << 24 ;
296 #elif BYTES_PER_MPI_LIMB == 8
297         alimb  = (mpi_limb_t)*p--       ;
298         alimb |= (mpi_limb_t)*p-- <<  8 ;
299         alimb |= (mpi_limb_t)*p-- << 16 ;
300         alimb |= (mpi_limb_t)*p-- << 24 ;
301         alimb |= (mpi_limb_t)*p-- << 32 ;
302         alimb |= (mpi_limb_t)*p-- << 40 ;
303         alimb |= (mpi_limb_t)*p-- << 48 ;
304         alimb |= (mpi_limb_t)*p-- << 56 ;
305 #else
306         #error please implement for this limb size.
307 #endif
308         a->d[i++] = alimb;
309     }
310     if( p >= buffer ) {
311 #if BYTES_PER_MPI_LIMB == 4
312         alimb  = *p--       ;
313         if( p >= buffer ) alimb |= *p-- <<  8 ;
314         if( p >= buffer ) alimb |= *p-- << 16 ;
315         if( p >= buffer ) alimb |= *p-- << 24 ;
316 #elif BYTES_PER_MPI_LIMB == 8
317         alimb  = (mpi_limb_t)*p-- ;
318         if( p >= buffer ) alimb |= (mpi_limb_t)*p-- <<  8 ;
319         if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 16 ;
320         if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 24 ;
321         if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 32 ;
322         if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 40 ;
323         if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 48 ;
324         if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 56 ;
325 #else
326         #error please implement for this limb size.
327 #endif
328         a->d[i++] = alimb;
329     }
330     a->nlimbs = i;
331     assert( i == nlimbs );
332 }
333
334
335
336 /* Convert the external representation of an integer stored in BUFFER
337    with a length of BUFLEN into a newly create MPI returned in
338    RET_MPI.  If NBYTES is not NULL, it will receive the number of
339    bytes actually scanned after a successful operation. */
340 gcry_error_t
341 gcry_mpi_scan( struct gcry_mpi **ret_mpi, enum gcry_mpi_format format,
342                const void *buffer_arg, size_t buflen, size_t *nscanned )
343 {
344     const unsigned char *buffer = (const unsigned char*)buffer_arg;
345     struct gcry_mpi *a = NULL;
346     unsigned int len;
347     int secure = (buffer && gcry_is_secure (buffer));
348
349     if (format == GCRYMPI_FMT_SSH)
350       len = 0;
351     else
352       len = buflen;
353
354     if( format == GCRYMPI_FMT_STD ) {
355         const byte *s = buffer;
356
357         a = secure? mpi_alloc_secure ((len+BYTES_PER_MPI_LIMB-1)
358                                       /BYTES_PER_MPI_LIMB)
359                   : mpi_alloc ((len+BYTES_PER_MPI_LIMB-1)/BYTES_PER_MPI_LIMB);
360         if( len ) { /* not zero */
361             a->sign = *s & 0x80;
362             if( a->sign ) {
363                 /* FIXME: we have to convert from 2compl to magnitude format */
364                 mpi_free(a);
365                 return gcry_error (GPG_ERR_INTERNAL);
366             }
367             else
368                 _gcry_mpi_set_buffer( a, s, len, 0 );
369         }
370         if( ret_mpi ) {
371             mpi_normalize ( a );
372             *ret_mpi = a;
373         }
374         else
375             mpi_free(a);
376         return gcry_error (GPG_ERR_NO_ERROR);
377     }
378     else if( format == GCRYMPI_FMT_USG ) {
379         a = secure? mpi_alloc_secure ((len+BYTES_PER_MPI_LIMB-1)
380                                       /BYTES_PER_MPI_LIMB)
381                   : mpi_alloc ((len+BYTES_PER_MPI_LIMB-1)/BYTES_PER_MPI_LIMB);
382
383         if( len )  /* not zero */
384             _gcry_mpi_set_buffer( a, buffer, len, 0 );
385         if( ret_mpi ) {
386             mpi_normalize ( a );
387             *ret_mpi = a;
388         }
389         else
390             mpi_free(a);
391         return gcry_error (GPG_ERR_NO_ERROR);
392     }
393     else if( format == GCRYMPI_FMT_PGP ) {
394         a = mpi_read_from_buffer (buffer, &len, secure);
395         if( nscanned )
396             *nscanned = len;
397         if( ret_mpi && a ) {
398             mpi_normalize ( a );
399             *ret_mpi = a;
400         }
401         else
402             mpi_free(a);
403         return gcry_error (a ? GPG_ERR_NO_ERROR : GPG_ERR_INV_OBJ);
404     }
405     else if( format == GCRYMPI_FMT_SSH ) {
406         const unsigned char *s = buffer;
407         size_t n;
408
409         if( len && len < 4 )
410             return gcry_error (GPG_ERR_TOO_SHORT);
411         n = s[0] << 24 | s[1] << 16 | s[2] << 8 | s[3];
412         s += 4; 
413         if (len)
414           len -= 4;
415         if( len && n > len )
416             return gcry_error (GPG_ERR_TOO_LARGE); /* or should it be
417                                                       too_short */
418
419         a = secure? mpi_alloc_secure ((n+BYTES_PER_MPI_LIMB-1)
420                                       /BYTES_PER_MPI_LIMB)
421                   : mpi_alloc ((n+BYTES_PER_MPI_LIMB-1)/BYTES_PER_MPI_LIMB);
422         if( n ) { /* not zero */
423             a->sign = *s & 0x80;
424             if( a->sign ) {
425                 /* FIXME: we have to convert from 2compl to magnitude format */
426                 mpi_free(a);
427                 return gcry_error (GPG_ERR_INTERNAL);
428             }
429             else
430                 _gcry_mpi_set_buffer( a, s, n, 0 );
431         }
432         if( nscanned )
433             *nscanned = n+4;
434         if( ret_mpi ) {
435             mpi_normalize ( a );
436             *ret_mpi = a;
437         }
438         else
439             mpi_free(a);
440         return gcry_error (GPG_ERR_NO_ERROR);
441     }
442     else if( format == GCRYMPI_FMT_HEX ) {
443         if( buflen )
444             return gcry_error (GPG_ERR_INV_ARG); /* can only handle C
445                                                     strings for now */
446         a = secure? mpi_alloc_secure (0) : mpi_alloc(0);
447         if( mpi_fromstr ( a, (const char *)buffer ) )
448             return gcry_error (GPG_ERR_INV_OBJ);
449         if( ret_mpi ) {
450             mpi_normalize ( a );
451             *ret_mpi = a;
452         }
453         else
454             mpi_free(a);
455         return gcry_error (GPG_ERR_NO_ERROR);
456     }
457     else
458         return gcry_error (GPG_ERR_INV_ARG);
459 }
460
461 /* Convert the big integer A into the external representation
462    described by FORMAT and store it in the provided BUFFER which has
463    been allocated by the user with a size of BUFLEN bytes.  NWRITTEN
464    receives the actual length of the external representation unless it
465    has been passed as NULL.  BUFFER may be NULL to query the required
466    length.*/
467 gcry_error_t
468 gcry_mpi_print( enum gcry_mpi_format format,
469                 unsigned char *buffer, size_t buflen,
470                 size_t *nwritten, struct gcry_mpi *a)
471 {
472     unsigned int nbits = mpi_get_nbits(a);
473     size_t len;
474     size_t dummy_nwritten;
475
476     if (!nwritten)
477       nwritten = &dummy_nwritten;
478
479     len = buflen;
480     *nwritten = 0;
481     if( format == GCRYMPI_FMT_STD ) {
482         unsigned char *tmp;
483         int extra = 0;
484         unsigned int n;
485
486         if( a->sign )
487             return gcry_error (GPG_ERR_INTERNAL); /* can't handle it yet */
488
489         tmp = _gcry_mpi_get_buffer( a, &n, NULL );
490         if( n && (*tmp & 0x80) ) {
491             n++;
492             extra=1;
493         }
494
495         if (buffer && n > len) {
496             /* The provided buffer is too short. */
497             gcry_free (tmp);
498             return gcry_error (GPG_ERR_TOO_SHORT);  
499         }
500         if( buffer ) {
501             unsigned char *s = buffer;
502             if( extra )
503                 *s++ = 0;
504
505             memcpy( s, tmp, n-extra );
506         }
507         gcry_free(tmp);
508         *nwritten = n;
509         return gcry_error (GPG_ERR_NO_ERROR);
510     }
511     else if( format == GCRYMPI_FMT_USG ) {
512         unsigned int n = (nbits + 7)/8;
513
514         /* we ignore the sign for this format */
515         /* FIXME: for performance reasons we should put this into
516          * mpi_aprint becuase we can then use the buffer directly */
517         if (buffer && n > len)
518             return gcry_error (GPG_ERR_TOO_SHORT);  /* the provided buffer is too short */
519         if( buffer ) {
520             unsigned char *tmp;
521             tmp = _gcry_mpi_get_buffer( a, &n, NULL );
522             memcpy( buffer, tmp, n );
523             gcry_free(tmp);
524         }
525         *nwritten = n;
526         return gcry_error (GPG_ERR_NO_ERROR);
527     }
528     else if( format == GCRYMPI_FMT_PGP ) {
529         unsigned int n = (nbits + 7)/8;
530
531         if( a->sign )
532             return gcry_error (GPG_ERR_INV_ARG); /* pgp format can only handle unsigned */
533
534         if (buffer && n+2 > len)
535             return gcry_error (GPG_ERR_TOO_SHORT);  /* the provided buffer is too short */
536         if( buffer ) {
537             unsigned char *tmp;
538             unsigned char *s = buffer;
539             s[0] = nbits >> 8;
540             s[1] = nbits;
541
542             tmp = _gcry_mpi_get_buffer( a, &n, NULL );
543             memcpy( s+2, tmp, n );
544             gcry_free(tmp);
545         }
546         *nwritten = n+2;
547         return gcry_error (GPG_ERR_NO_ERROR);
548     }
549     else if( format == GCRYMPI_FMT_SSH ) {
550         unsigned char *tmp;
551         int extra = 0;
552         unsigned int n;
553
554         if( a->sign )
555             return gcry_error (GPG_ERR_INTERNAL); /* can't handle it yet */
556
557         tmp = _gcry_mpi_get_buffer( a, &n, NULL );
558         if( n && (*tmp & 0x80) ) {
559             n++;
560             extra=1;
561         }
562
563         if (buffer && n+4 > len) {
564             gcry_free(tmp);
565             return gcry_error (GPG_ERR_TOO_SHORT);  /* the provided buffer is too short */
566         }
567         if( buffer ) {
568             byte *s = buffer;
569             *s++ = n >> 24;
570             *s++ = n >> 16;
571             *s++ = n >> 8;
572             *s++ = n;
573             if( extra )
574                 *s++ = 0;
575
576             memcpy( s, tmp, n-extra );
577         }
578         gcry_free(tmp);
579         *nwritten = 4+n;
580         return gcry_error (GPG_ERR_NO_ERROR);
581     }
582     else if( format == GCRYMPI_FMT_HEX ) {
583         byte *tmp;
584         int i;
585         int extra = 0;
586         unsigned int n=0;
587
588         tmp = _gcry_mpi_get_buffer( a, &n, NULL );
589         if( !n || (*tmp & 0x80) )
590             extra=2;
591
592         if(buffer && 2*n + extra + !!a->sign + 1 > len) {
593             gcry_free(tmp);
594             return gcry_error (GPG_ERR_TOO_SHORT);  /* the provided buffer is too short */
595         }
596         if( buffer ) {
597             byte *s = buffer;
598             if( a->sign )
599                 *s++ = '-';
600             if( extra ) {
601                 *s++ = '0';
602                 *s++ = '0';
603             }
604
605             for(i=0; i < n; i++ ) {
606                 unsigned int c = tmp[i];
607                 *s++ = (c >> 4) < 10? '0'+(c>>4) : 'A'+(c>>4)-10 ;
608                 c &= 15;
609                 *s++ = c < 10? '0'+c : 'A'+c-10 ;
610             }
611             *s++ = 0;
612             *nwritten = s - buffer;
613         }
614         else {
615             *nwritten = 2*n + extra + !!a->sign + 1;
616         }
617         gcry_free(tmp);
618         return gcry_error (GPG_ERR_NO_ERROR);
619     }
620     else
621         return gcry_error (GPG_ERR_INV_ARG);
622 }
623
624 /****************
625  * Like gcry_mpi_print but this function allocates the buffer itself.
626  * The caller has to supply the address of a pointer. NWRITTEN may be
627  * NULL.
628  */
629 gcry_error_t
630 gcry_mpi_aprint( enum gcry_mpi_format format,
631                  unsigned char **buffer, size_t *nwritten,
632                  struct gcry_mpi *a )
633 {
634     size_t n;
635     gcry_error_t rc;
636
637     *buffer = NULL;
638     rc = gcry_mpi_print( format, NULL, 0, &n, a );
639     if( rc )
640         return rc;
641     *buffer = mpi_is_secure(a) ? gcry_xmalloc_secure( n ) : gcry_xmalloc( n );
642     rc = gcry_mpi_print( format, *buffer, n, &n, a );
643     if( rc ) {
644         gcry_free(*buffer);
645         *buffer = NULL;
646     }
647     else if( nwritten )
648         *nwritten = n;
649     return rc;
650 }
651