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