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