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