Switched to GPLv3.
[gnupg.git] / mpi / mpicoder.c
1 /* mpicoder.c  -  Coder for the external representation of MPIs
2  * Copyright (C) 1998, 1999, 2005 Free Software Foundation, Inc.
3  *
4  * This file is part of GnuPG.
5  *
6  * GnuPG is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 3 of the License, or
9  * (at your option) any later version.
10  *
11  * GnuPG 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 General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, see <http://www.gnu.org/licenses/>.
18  */
19
20 #include <config.h>
21 #include <stdio.h>
22 #include <string.h>
23 #include <stdlib.h>
24 #include <assert.h>
25
26 #include "mpi.h"
27 #include "mpi-internal.h"
28 #include "iobuf.h"
29 #include "memory.h"
30 #include "util.h"
31
32 #ifdef M_DEBUG
33 #undef mpi_read
34 #endif
35
36 #define MAX_EXTERN_MPI_BITS 16384
37
38 /****************
39  * write an mpi to out.
40  */
41 int
42 mpi_write( IOBUF out, MPI a )
43 {
44     int rc;
45     unsigned nbits = mpi_get_nbits(a);
46     byte *p, *buf;
47     unsigned n;
48
49     if( nbits > MAX_EXTERN_MPI_BITS )
50         log_bug("mpi_encode: mpi too large (%u bits)\n", nbits);
51
52     iobuf_put(out, (nbits >>8) );
53     iobuf_put(out, (nbits) );
54
55     p = buf = mpi_get_buffer( a, &n, NULL );
56     rc = iobuf_write( out, p, n );
57     xfree(buf);
58     return rc;
59 }
60
61
62 /****************
63  * Read an external representation of an mpi and return the MPI
64  * The external format is a 16 bit unsigned value stored in network byte order,
65  * giving the number of bits for the following integer. The integer is stored
66  * with MSB first (left padded with zeroes to align on a byte boundary).
67  */
68 MPI
69 #ifdef M_DEBUG
70 mpi_debug_read(IOBUF inp, unsigned *ret_nread, int secure, const char *info)
71 #else
72 mpi_read(IOBUF inp, unsigned *ret_nread, int secure)
73 #endif
74 {
75     int c, i, j;
76     unsigned int nmax = *ret_nread;
77     unsigned nbits, nbytes, nlimbs, nread=0;
78     mpi_limb_t a;
79     MPI val = NULL;
80
81     if (nread == nmax)
82         goto overflow;
83     if( (c = iobuf_get(inp)) == -1 )
84         goto leave;
85     nread++;
86     nbits = c << 8;
87
88     if (nread == nmax)
89         goto overflow;
90     if( (c = iobuf_get(inp)) == -1 )
91         goto leave;
92     nread++;
93     nbits |= c;
94
95     if( nbits > MAX_EXTERN_MPI_BITS ) {
96         log_error("mpi too large for this implementation (%u bits)\n", nbits);
97         goto leave;
98     }
99
100     nbytes = (nbits+7) / 8;
101     nlimbs = (nbytes+BYTES_PER_MPI_LIMB-1) / BYTES_PER_MPI_LIMB;
102 #ifdef M_DEBUG
103     val = secure? mpi_debug_alloc_secure( nlimbs, info )
104                 : mpi_debug_alloc( nlimbs, info );
105 #else
106     val = secure? mpi_alloc_secure( nlimbs )
107                 : mpi_alloc( nlimbs );
108 #endif
109     i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
110     i %= BYTES_PER_MPI_LIMB;
111     val->nbits = nbits;
112     j= val->nlimbs = nlimbs;
113     val->sign = 0;
114     for( ; j > 0; j-- ) {
115         a = 0;
116         for(; i < BYTES_PER_MPI_LIMB; i++ ) {
117             if (nread == nmax) {
118 #ifdef M_DEBUG
119                 mpi_debug_free (val);
120 #else
121                 mpi_free (val);
122 #endif
123                 val = NULL;
124                 goto overflow;
125             }
126             a <<= 8;
127             a |= iobuf_get(inp) & 0xff; nread++;
128         }
129         i = 0;
130         val->d[j-1] = a;
131     }
132
133   leave:
134     *ret_nread = nread;
135     return val;
136   overflow:
137     log_error ("mpi larger than indicated length (%u bytes)\n", nmax);
138     *ret_nread = nread;
139     return val;
140 }
141
142
143 MPI
144 mpi_read_from_buffer(byte *buffer, unsigned int *ret_nread, int secure)
145 {
146     int i, j;
147     unsigned nbits, nbytes, nlimbs, nread=0;
148     mpi_limb_t a;
149     MPI val = NULL;
150
151     if( *ret_nread < 2 )
152         goto leave;
153     nbits = buffer[0] << 8 | buffer[1];
154     if( nbits > MAX_EXTERN_MPI_BITS ) {
155         log_info ("mpi too large (%u bits)\n", nbits);
156         goto leave;
157     }
158     buffer += 2;
159     nread = 2;
160
161     nbytes = (nbits+7) / 8;
162     nlimbs = (nbytes+BYTES_PER_MPI_LIMB-1) / BYTES_PER_MPI_LIMB;
163     val = secure? mpi_alloc_secure( nlimbs )
164                 : mpi_alloc( nlimbs );
165     i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
166     i %= BYTES_PER_MPI_LIMB;
167     val->nbits = nbits;
168     j= val->nlimbs = nlimbs;
169     val->sign = 0;
170     for( ; j > 0; j-- ) {
171         a = 0;
172         for(; i < BYTES_PER_MPI_LIMB; i++ ) {
173           if( ++nread > *ret_nread ) {
174               /* This (as well as the above error condition) may
175                  happen if we use this function to parse a decrypted
176                  MPI which didn't turn out to be a real MPI - possible
177                  because the supplied key was wrong but the OpenPGP
178                  checksum didn't caught it. */
179                 log_info ("mpi larger than buffer\n");
180                 mpi_free (val);
181                 val = NULL;
182                 goto leave;
183           }
184           a <<= 8;
185           a |= *buffer++;
186         }
187         i = 0;
188         val->d[j-1] = a;
189     }
190
191   leave:
192     *ret_nread = nread;
193     return val;
194 }
195
196
197 /****************
198  * Make an mpi from a character string.
199  */
200 int
201 mpi_fromstr(MPI val, const char *str)
202 {
203     int hexmode=0, sign=0, prepend_zero=0, i, j, c, c1, c2;
204     unsigned nbits, nbytes, nlimbs;
205     mpi_limb_t a;
206
207     if( *str == '-' ) {
208         sign = 1;
209         str++;
210     }
211     if( *str == '0' && str[1] == 'x' )
212         hexmode = 1;
213     else
214         return 1; /* other bases are not yet supported */
215     str += 2;
216
217     nbits = strlen(str)*4;
218     if( nbits % 8 )
219         prepend_zero = 1;
220     nbytes = (nbits+7) / 8;
221     nlimbs = (nbytes+BYTES_PER_MPI_LIMB-1) / BYTES_PER_MPI_LIMB;
222     if( val->alloced < nlimbs )
223         mpi_resize(val, nlimbs );
224     i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
225     i %= BYTES_PER_MPI_LIMB;
226     j= val->nlimbs = nlimbs;
227     val->sign = sign;
228     for( ; j > 0; j-- ) {
229         a = 0;
230         for(; i < BYTES_PER_MPI_LIMB; i++ ) {
231             if( prepend_zero ) {
232                 c1 = '0';
233                 prepend_zero = 0;
234             }
235             else
236                 c1 = *str++;
237             assert(c1);
238             c2 = *str++;
239             assert(c2);
240             if( c1 >= '0' && c1 <= '9' )
241                 c = c1 - '0';
242             else if( c1 >= 'a' && c1 <= 'f' )
243                 c = c1 - 'a' + 10;
244             else if( c1 >= 'A' && c1 <= 'F' )
245                 c = c1 - 'A' + 10;
246             else {
247                 mpi_clear(val);
248                 return 1;
249             }
250             c <<= 4;
251             if( c2 >= '0' && c2 <= '9' )
252                 c |= c2 - '0';
253             else if( c2 >= 'a' && c2 <= 'f' )
254                 c |= c2 - 'a' + 10;
255             else if( c2 >= 'A' && c2 <= 'F' )
256                 c |= c2 - 'A' + 10;
257             else {
258                 mpi_clear(val);
259                 return 1;
260             }
261             a <<= 8;
262             a |= c;
263         }
264         i = 0;
265         val->d[j-1] = a;
266     }
267
268     return 0;
269 }
270
271
272 /****************
273  * print an MPI to the given stream and return the number of characters
274  * printed.
275  */
276 int
277 mpi_print( FILE *fp, MPI a, int mode )
278 {
279     int i, n=0;
280
281     if( a == NULL )
282         return fprintf(fp, "[MPI_NULL]");
283     if( !mode ) {
284         unsigned int n1;
285
286         n1 = mpi_get_nbits(a);
287         n += fprintf(fp, "[%u bits]", n1);
288     }
289     else {
290         if( a->sign )
291             putc('-', fp);
292 #if BYTES_PER_MPI_LIMB == 2
293 #define X "4"
294 #elif BYTES_PER_MPI_LIMB == 4
295 #define X "8"
296 #elif BYTES_PER_MPI_LIMB == 8
297 #define X "16"
298 #else
299 #error please define the format here
300 #endif
301         for(i=a->nlimbs; i > 0 ; i-- ) {
302             n += fprintf(fp, i!=a->nlimbs? "%0" X "lX":"%lX", (ulong)a->d[i-1]);
303 #undef X
304         }
305         if( !a->nlimbs )
306             putc('0', fp );
307     }
308     return n;
309 }
310
311
312 void
313 g10_log_mpidump( const char *text, MPI a )
314 {
315     FILE *fp = log_stream();
316
317     g10_log_print_prefix(text);
318     mpi_print(fp, a, 1 );
319     fputc('\n', fp);
320 }
321
322 /****************
323  * Special function to get the low 8 bytes from an mpi.
324  * This can be used as a keyid; KEYID is an 2 element array.
325  * Return the low 4 bytes.
326  */
327 u32
328 mpi_get_keyid( MPI a, u32 *keyid )
329 {
330 #if BYTES_PER_MPI_LIMB == 4
331     if( keyid ) {
332         keyid[0] = a->nlimbs >= 2? a->d[1] : 0;
333         keyid[1] = a->nlimbs >= 1? a->d[0] : 0;
334     }
335     return a->nlimbs >= 1? a->d[0] : 0;
336 #elif BYTES_PER_MPI_LIMB == 8
337     if( keyid ) {
338         keyid[0] = a->nlimbs? (u32)(a->d[0] >> 32) : 0;
339         keyid[1] = a->nlimbs? (u32)(a->d[0] & 0xffffffff) : 0;
340     }
341     return a->nlimbs? (u32)(a->d[0] & 0xffffffff) : 0;
342 #else
343 #error Make this function work with other LIMB sizes
344 #endif
345 }
346
347
348 /****************
349  * Return an xmalloced buffer with the MPI (msb first).
350  * NBYTES receives the length of this buffer. Caller must free the
351  * return string (This function does return a 0 byte buffer with NBYTES
352  * set to zero if the value of A is zero. If sign is not NULL, it will
353  * be set to the sign of the A.
354  */
355 static byte *
356 do_get_buffer( MPI a, unsigned *nbytes, int *sign, int force_secure )
357 {
358     byte *p, *buffer;
359     mpi_limb_t alimb;
360     int i;
361     unsigned int n;
362
363     if( sign )
364         *sign = a->sign;
365     *nbytes = n = a->nlimbs * BYTES_PER_MPI_LIMB;
366     if (!n)
367       n++; /* avoid zero length allocation */
368     p = buffer = force_secure || mpi_is_secure(a) ? xmalloc_secure(n)
369                                                   : xmalloc(n);
370
371     for(i=a->nlimbs-1; i >= 0; i-- ) {
372         alimb = a->d[i];
373 #if BYTES_PER_MPI_LIMB == 4
374         *p++ = alimb >> 24;
375         *p++ = alimb >> 16;
376         *p++ = alimb >>  8;
377         *p++ = alimb      ;
378 #elif BYTES_PER_MPI_LIMB == 8
379         *p++ = alimb >> 56;
380         *p++ = alimb >> 48;
381         *p++ = alimb >> 40;
382         *p++ = alimb >> 32;
383         *p++ = alimb >> 24;
384         *p++ = alimb >> 16;
385         *p++ = alimb >>  8;
386         *p++ = alimb      ;
387 #else
388 #error please implement for this limb size.
389 #endif
390     }
391
392     /* this is sub-optimal but we need to do the shift operation
393      * because the caller has to free the returned buffer */
394     for(p=buffer; !*p && *nbytes; p++, --*nbytes )
395       ;
396     if( p != buffer )
397       memmove(buffer,p, *nbytes);
398
399     return buffer;
400 }
401
402
403 byte *
404 mpi_get_buffer( MPI a, unsigned *nbytes, int *sign )
405 {
406     return do_get_buffer( a, nbytes, sign, 0 );
407 }
408
409 byte *
410 mpi_get_secure_buffer( MPI a, unsigned *nbytes, int *sign )
411 {
412     return do_get_buffer( a, nbytes, sign, 1 );
413 }
414
415 /****************
416  * Use BUFFER to update MPI.
417  */
418 void
419 mpi_set_buffer( MPI a, const byte *buffer, unsigned nbytes, int sign )
420 {
421     const byte *p;
422     mpi_limb_t alimb;
423     int nlimbs;
424     int i;
425
426     nlimbs = (nbytes + BYTES_PER_MPI_LIMB - 1) / BYTES_PER_MPI_LIMB;
427     RESIZE_IF_NEEDED(a, nlimbs);
428     a->sign = sign;
429
430     for(i=0, p = buffer+nbytes-1; p >= buffer+BYTES_PER_MPI_LIMB; ) {
431 #if BYTES_PER_MPI_LIMB == 4
432         alimb  = (mpi_limb_t)*p-- ;
433         alimb |= (mpi_limb_t)*p-- <<  8 ;
434         alimb |= (mpi_limb_t)*p-- << 16 ;
435         alimb |= (mpi_limb_t)*p-- << 24 ;
436 #elif BYTES_PER_MPI_LIMB == 8
437         alimb  = (mpi_limb_t)*p--       ;
438         alimb |= (mpi_limb_t)*p-- <<  8 ;
439         alimb |= (mpi_limb_t)*p-- << 16 ;
440         alimb |= (mpi_limb_t)*p-- << 24 ;
441         alimb |= (mpi_limb_t)*p-- << 32 ;
442         alimb |= (mpi_limb_t)*p-- << 40 ;
443         alimb |= (mpi_limb_t)*p-- << 48 ;
444         alimb |= (mpi_limb_t)*p-- << 56 ;
445 #else
446 #error please implement for this limb size.
447 #endif
448         a->d[i++] = alimb;
449     }
450     if( p >= buffer ) {
451 #if BYTES_PER_MPI_LIMB == 4
452         alimb  = *p--       ;
453         if( p >= buffer ) alimb |= (mpi_limb_t)*p-- <<  8 ;
454         if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 16 ;
455         if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 24 ;
456 #elif BYTES_PER_MPI_LIMB == 8
457         alimb  = (mpi_limb_t)*p-- ;
458         if( p >= buffer ) alimb |= (mpi_limb_t)*p-- <<  8 ;
459         if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 16 ;
460         if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 24 ;
461         if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 32 ;
462         if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 40 ;
463         if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 48 ;
464         if( p >= buffer ) alimb |= (mpi_limb_t)*p-- << 56 ;
465 #else
466 #error please implement for this limb size.
467 #endif
468         a->d[i++] = alimb;
469     }
470     a->nlimbs = i;
471     assert( i == nlimbs );
472 }