sexp: Improve argument checking of sexp parser.
[libgcrypt.git] / mpi / mpiutil.c
1 /* mpiutil.ac  -  Utility functions for MPI
2  * Copyright (C) 1998, 2000, 2001, 2002, 2003,
3  *               2007  Free Software Foundation, Inc.
4  * Copyright (C) 2013  g10 Code GmbH
5  *
6  * This file is part of Libgcrypt.
7  *
8  * Libgcrypt is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License as
10  * published by the Free Software Foundation; either version 2.1 of
11  * the License, or (at your option) any later version.
12  *
13  * Libgcrypt is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU Lesser General Public License for more details.
17  *
18  * You should have received a copy of the GNU Lesser General Public
19  * License along with this program; if not, see <http://www.gnu.org/licenses/>.
20  */
21
22 #include <config.h>
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <string.h>
26
27 #include "g10lib.h"
28 #include "mpi-internal.h"
29 #include "mod-source-info.h"
30
31
32 #if SIZEOF_UNSIGNED_INT == 2
33 # define MY_UINT_MAX 0xffff
34 /* (visual check:      0123 ) */
35 #elif SIZEOF_UNSIGNED_INT == 4
36 # define MY_UINT_MAX 0xffffffff
37 /* (visual check:      01234567 ) */
38 #elif SIZEOF_UNSIGNED_INT == 8
39 # define MY_UINT_MAX 0xffffffffffffffff
40 /* (visual check:      0123456789abcdef ) */
41 #else
42 # error Need MY_UINT_MAX for this limb size
43 #endif
44
45
46 /* Constants allocated right away at startup.  */
47 static gcry_mpi_t constants[MPI_NUMBER_OF_CONSTANTS];
48
49
50
51 const char *
52 _gcry_mpi_get_hw_config (void)
53 {
54   return mod_source_info + 1;
55 }
56
57
58 /* Initialize the MPI subsystem.  This is called early and allows to
59    do some initialization without taking care of threading issues.  */
60 gcry_err_code_t
61 _gcry_mpi_init (void)
62 {
63   int idx;
64   unsigned long value;
65
66   for (idx=0; idx < MPI_NUMBER_OF_CONSTANTS; idx++)
67     {
68       switch (idx)
69         {
70         case MPI_C_ZERO:  value = 0; break;
71         case MPI_C_ONE:   value = 1; break;
72         case MPI_C_TWO:   value = 2; break;
73         case MPI_C_THREE: value = 3; break;
74         case MPI_C_FOUR:  value = 4; break;
75         case MPI_C_EIGHT: value = 8; break;
76         default: log_bug ("invalid mpi_const selector %d\n", idx);
77         }
78       constants[idx] = mpi_alloc_set_ui (value);
79       constants[idx]->flags = (16|32);
80     }
81
82   return 0;
83 }
84
85
86 /****************
87  * Note:  It was a bad idea to use the number of limbs to allocate
88  *        because on a alpha the limbs are large but we normally need
89  *        integers of n bits - So we should change this to bits (or bytes).
90  *
91  *        But mpi_alloc is used in a lot of places :-(.  New code
92  *        should use mpi_new.
93  */
94 gcry_mpi_t
95 _gcry_mpi_alloc( unsigned nlimbs )
96 {
97     gcry_mpi_t a;
98
99     a = xmalloc( sizeof *a );
100     a->d = nlimbs? mpi_alloc_limb_space( nlimbs, 0 ) : NULL;
101     a->alloced = nlimbs;
102     a->nlimbs = 0;
103     a->sign = 0;
104     a->flags = 0;
105     return a;
106 }
107
108 void
109 _gcry_mpi_m_check( gcry_mpi_t a )
110 {
111     _gcry_check_heap(a);
112     _gcry_check_heap(a->d);
113 }
114
115 gcry_mpi_t
116 _gcry_mpi_alloc_secure( unsigned nlimbs )
117 {
118     gcry_mpi_t a;
119
120     a = xmalloc( sizeof *a );
121     a->d = nlimbs? mpi_alloc_limb_space( nlimbs, 1 ) : NULL;
122     a->alloced = nlimbs;
123     a->flags = 1;
124     a->nlimbs = 0;
125     a->sign = 0;
126     return a;
127 }
128
129
130
131 mpi_ptr_t
132 _gcry_mpi_alloc_limb_space( unsigned int nlimbs, int secure )
133 {
134     mpi_ptr_t p;
135     size_t len;
136
137     len = (nlimbs ? nlimbs : 1) * sizeof (mpi_limb_t);
138     p = secure ? xmalloc_secure (len) : xmalloc (len);
139     if (! nlimbs)
140       *p = 0;
141
142     return p;
143 }
144
145 void
146 _gcry_mpi_free_limb_space( mpi_ptr_t a, unsigned int nlimbs)
147 {
148   if (a)
149     {
150       size_t len = nlimbs * sizeof(mpi_limb_t);
151
152       /* If we have information on the number of allocated limbs, we
153          better wipe that space out.  This is a failsafe feature if
154          secure memory has been disabled or was not properly
155          implemented in user provided allocation functions. */
156       if (len)
157         wipememory (a, len);
158       xfree(a);
159     }
160 }
161
162
163 void
164 _gcry_mpi_assign_limb_space( gcry_mpi_t a, mpi_ptr_t ap, unsigned int nlimbs )
165 {
166   _gcry_mpi_free_limb_space (a->d, a->alloced);
167   a->d = ap;
168   a->alloced = nlimbs;
169 }
170
171
172
173 /****************
174  * Resize the array of A to NLIMBS. The additional space is cleared
175  * (set to 0).
176  */
177 void
178 _gcry_mpi_resize (gcry_mpi_t a, unsigned nlimbs)
179 {
180   size_t i;
181
182   if (nlimbs <= a->alloced)
183     {
184       /* We only need to clear the new space (this is a nop if the
185          limb space is already of the correct size. */
186       for (i=a->nlimbs; i < a->alloced; i++)
187         a->d[i] = 0;
188       return;
189     }
190
191   /* Actually resize the limb space.  */
192   if (a->d)
193     {
194       a->d = xrealloc (a->d, nlimbs * sizeof (mpi_limb_t));
195       for (i=a->alloced; i < nlimbs; i++)
196         a->d[i] = 0;
197     }
198   else
199     {
200       if (a->flags & 1)
201         /* Secure memory is wanted.  */
202         a->d = xcalloc_secure (nlimbs , sizeof (mpi_limb_t));
203       else
204         /* Standard memory.  */
205         a->d = xcalloc (nlimbs , sizeof (mpi_limb_t));
206     }
207   a->alloced = nlimbs;
208 }
209
210 void
211 _gcry_mpi_clear( gcry_mpi_t a )
212 {
213   if (mpi_is_immutable (a))
214     {
215       mpi_immutable_failed ();
216       return;
217     }
218   a->nlimbs = 0;
219   a->flags = 0;
220 }
221
222
223 void
224 _gcry_mpi_free( gcry_mpi_t a )
225 {
226   if (!a )
227     return;
228   if ((a->flags & 32))
229   {
230 #if GPGRT_VERSION_NUMBER >= 0x011600  /* 1.22 */
231     gpgrt_annotate_leaked_object(a);
232 #endif
233     return; /* Never release a constant. */
234   }
235   if ((a->flags & 4))
236     xfree( a->d );
237   else
238     {
239       _gcry_mpi_free_limb_space(a->d, a->alloced);
240     }
241   /* Check that the flags makes sense.  We better allow for bit 1
242      (value 2) for backward ABI compatibility.  */
243   if ((a->flags & ~(1|2|4|16
244                     |GCRYMPI_FLAG_USER1
245                     |GCRYMPI_FLAG_USER2
246                     |GCRYMPI_FLAG_USER3
247                     |GCRYMPI_FLAG_USER4)))
248     log_bug("invalid flag value in mpi_free\n");
249   xfree (a);
250 }
251
252
253 void
254 _gcry_mpi_immutable_failed (void)
255 {
256   log_info ("Warning: trying to change an immutable MPI\n");
257 }
258
259
260 static void
261 mpi_set_secure( gcry_mpi_t a )
262 {
263   mpi_ptr_t ap, bp;
264
265   if ( (a->flags & 1) )
266     return;
267   a->flags |= 1;
268   ap = a->d;
269   if (!a->nlimbs)
270     {
271       gcry_assert (!ap);
272       return;
273     }
274   bp = mpi_alloc_limb_space (a->alloced, 1);
275   MPN_COPY( bp, ap, a->nlimbs );
276   a->d = bp;
277   _gcry_mpi_free_limb_space (ap, a->alloced);
278 }
279
280
281 gcry_mpi_t
282 _gcry_mpi_set_opaque (gcry_mpi_t a, void *p, unsigned int nbits)
283 {
284   if (!a)
285     a = mpi_alloc(0);
286
287   if (mpi_is_immutable (a))
288     {
289       mpi_immutable_failed ();
290       return a;
291     }
292
293   if( a->flags & 4 )
294     xfree (a->d);
295   else
296     _gcry_mpi_free_limb_space (a->d, a->alloced);
297
298   a->d = p;
299   a->alloced = 0;
300   a->nlimbs = 0;
301   a->sign  = nbits;
302   a->flags = 4 | (a->flags & (GCRYMPI_FLAG_USER1|GCRYMPI_FLAG_USER2
303                               |GCRYMPI_FLAG_USER3|GCRYMPI_FLAG_USER4));
304   if (_gcry_is_secure (a->d))
305     a->flags |= 1;
306   return a;
307 }
308
309
310 gcry_mpi_t
311 _gcry_mpi_set_opaque_copy (gcry_mpi_t a, const void *p, unsigned int nbits)
312 {
313   void *d;
314   unsigned int n;
315
316   n = (nbits+7)/8;
317   d = _gcry_is_secure (p)? xtrymalloc_secure (n) : xtrymalloc (n);
318   if (!d)
319     return NULL;
320   memcpy (d, p, n);
321   return mpi_set_opaque (a, d, nbits);
322 }
323
324
325 void *
326 _gcry_mpi_get_opaque (gcry_mpi_t a, unsigned int *nbits)
327 {
328     if( !(a->flags & 4) )
329         log_bug("mpi_get_opaque on normal mpi\n");
330     if( nbits )
331         *nbits = a->sign;
332     return a->d;
333 }
334
335
336 void *
337 _gcry_mpi_get_opaque_copy (gcry_mpi_t a, unsigned int *nbits)
338 {
339   const void *s;
340   void *d;
341   unsigned int n;
342
343   s = mpi_get_opaque (a, nbits);
344   if (!s && nbits)
345     return NULL;
346   n = (*nbits+7)/8;
347   d = _gcry_is_secure (s)? xtrymalloc_secure (n) : xtrymalloc (n);
348   if (d)
349     memcpy (d, s, n);
350   return d;
351 }
352
353 /****************
354  * Note: This copy function should not interpret the MPI
355  *       but copy it transparently.
356  */
357 gcry_mpi_t
358 _gcry_mpi_copy (gcry_mpi_t a)
359 {
360     int i;
361     gcry_mpi_t b;
362
363     if( a && (a->flags & 4) ) {
364         void *p = _gcry_is_secure(a->d)? xmalloc_secure ((a->sign+7)/8)
365                                        : xmalloc ((a->sign+7)/8);
366         if (a->d)
367           memcpy( p, a->d, (a->sign+7)/8 );
368         b = mpi_set_opaque( NULL, p, a->sign );
369         b->flags &= ~(16|32); /* Reset the immutable and constant flags.  */
370     }
371     else if( a ) {
372         b = mpi_is_secure(a)? mpi_alloc_secure( a->nlimbs )
373                             : mpi_alloc( a->nlimbs );
374         b->nlimbs = a->nlimbs;
375         b->sign = a->sign;
376         b->flags  = a->flags;
377         b->flags &= ~(16|32); /* Reset the immutable and constant flags.  */
378         for(i=0; i < b->nlimbs; i++ )
379             b->d[i] = a->d[i];
380     }
381     else
382         b = NULL;
383     return b;
384 }
385
386
387 /* Return true if A is negative.  */
388 int
389 _gcry_mpi_is_neg (gcry_mpi_t a)
390 {
391   if (a->sign && _gcry_mpi_cmp_ui (a, 0))
392     return 1;
393   else
394     return 0;
395 }
396
397
398 /* W = - U */
399 void
400 _gcry_mpi_neg (gcry_mpi_t w, gcry_mpi_t u)
401 {
402   if (w != u)
403     mpi_set (w, u);
404   else if (mpi_is_immutable (w))
405     {
406       mpi_immutable_failed ();
407       return;
408     }
409
410   w->sign = !u->sign;
411 }
412
413
414 /* W = [W] */
415 void
416 _gcry_mpi_abs (gcry_mpi_t w)
417 {
418   if (mpi_is_immutable (w))
419     {
420       mpi_immutable_failed ();
421       return;
422     }
423
424   w->sign = 0;
425 }
426
427
428 /****************
429  * This function allocates an MPI which is optimized to hold
430  * a value as large as the one given in the argument and allocates it
431  * with the same flags as A.
432  */
433 gcry_mpi_t
434 _gcry_mpi_alloc_like( gcry_mpi_t a )
435 {
436     gcry_mpi_t b;
437
438     if( a && (a->flags & 4) ) {
439         int n = (a->sign+7)/8;
440         void *p = _gcry_is_secure(a->d)? xtrymalloc_secure (n)
441                                        : xtrymalloc (n);
442         memcpy( p, a->d, n );
443         b = mpi_set_opaque( NULL, p, a->sign );
444     }
445     else if( a ) {
446         b = mpi_is_secure(a)? mpi_alloc_secure( a->nlimbs )
447                             : mpi_alloc( a->nlimbs );
448         b->nlimbs = 0;
449         b->sign = 0;
450         b->flags = a->flags;
451     }
452     else
453         b = NULL;
454     return b;
455 }
456
457
458 /* Set U into W and release U.  If W is NULL only U will be released. */
459 void
460 _gcry_mpi_snatch (gcry_mpi_t w, gcry_mpi_t u)
461 {
462   if (w)
463     {
464       if (mpi_is_immutable (w))
465         {
466           mpi_immutable_failed ();
467           return;
468         }
469       _gcry_mpi_assign_limb_space (w, u->d, u->alloced);
470       w->nlimbs = u->nlimbs;
471       w->sign   = u->sign;
472       w->flags  = u->flags;
473       u->alloced = 0;
474       u->nlimbs = 0;
475       u->d = NULL;
476     }
477   _gcry_mpi_free (u);
478 }
479
480
481 gcry_mpi_t
482 _gcry_mpi_set (gcry_mpi_t w, gcry_mpi_t u)
483 {
484   mpi_ptr_t wp, up;
485   mpi_size_t usize = u->nlimbs;
486   int usign = u->sign;
487
488   if (!w)
489     w = _gcry_mpi_alloc( mpi_get_nlimbs(u) );
490   if (mpi_is_immutable (w))
491     {
492       mpi_immutable_failed ();
493       return w;
494     }
495   RESIZE_IF_NEEDED(w, usize);
496   wp = w->d;
497   up = u->d;
498   MPN_COPY( wp, up, usize );
499   w->nlimbs = usize;
500   w->flags = u->flags;
501   w->flags &= ~(16|32); /* Reset the immutable and constant flags.  */
502   w->sign = usign;
503   return w;
504 }
505
506 /****************
507  * Set the value of W by the one of U, when SET is 1.
508  * Leave the value when SET is 0.
509  * This implementation should be constant-time regardless of SET.
510  */
511 gcry_mpi_t
512 _gcry_mpi_set_cond (gcry_mpi_t w, const gcry_mpi_t u, unsigned long set)
513 {
514   mpi_size_t i;
515   mpi_size_t nlimbs = u->alloced;
516   mpi_limb_t mask = ((mpi_limb_t)0) - set;
517   mpi_limb_t x;
518
519   if (w->alloced != u->alloced)
520     log_bug ("mpi_set_cond: different sizes\n");
521
522   for (i = 0; i < nlimbs; i++)
523     {
524       x = mask & (w->d[i] ^ u->d[i]);
525       w->d[i] = w->d[i] ^ x;
526     }
527
528   x = mask & (w->nlimbs ^ u->nlimbs);
529   w->nlimbs = w->nlimbs ^ x;
530
531   x = mask & (w->sign ^ u->sign);
532   w->sign = w->sign ^ x;
533   return w;
534 }
535
536
537 gcry_mpi_t
538 _gcry_mpi_set_ui (gcry_mpi_t w, unsigned long u)
539 {
540   if (!w)
541     w = _gcry_mpi_alloc (1);
542   /* FIXME: If U is 0 we have no need to resize and thus possible
543      allocating the the limbs. */
544   if (mpi_is_immutable (w))
545     {
546       mpi_immutable_failed ();
547       return w;
548     }
549   RESIZE_IF_NEEDED(w, 1);
550   w->d[0] = u;
551   w->nlimbs = u? 1:0;
552   w->sign = 0;
553   w->flags = 0;
554   return w;
555 }
556
557 /* If U is non-negative and small enough store it as an unsigned int
558  * at W.  If the value does not fit into an unsigned int or is
559  * negative return GPG_ERR_ERANGE.  Note that we return an unsigned
560  * int so that the value can be used with the bit test functions; in
561  * contrast the other _ui functions take an unsigned long so that on
562  * some platforms they may accept a larger value.  On error the value
563  * at U is not changed. */
564 gcry_err_code_t
565 _gcry_mpi_get_ui (unsigned int *w, gcry_mpi_t u)
566 {
567   mpi_limb_t x;
568
569   if (u->nlimbs > 1 || u->sign)
570     return GPG_ERR_ERANGE;
571
572   x = (u->nlimbs == 1) ? u->d[0] : 0;
573   if (sizeof (x) > sizeof (unsigned int) && x > MY_UINT_MAX)
574     return GPG_ERR_ERANGE;
575
576   *w = x;
577   return 0;
578 }
579
580
581 gcry_mpi_t
582 _gcry_mpi_alloc_set_ui( unsigned long u)
583 {
584     gcry_mpi_t w = mpi_alloc(1);
585     w->d[0] = u;
586     w->nlimbs = u? 1:0;
587     w->sign = 0;
588     return w;
589 }
590
591 void
592 _gcry_mpi_swap (gcry_mpi_t a, gcry_mpi_t b)
593 {
594     struct gcry_mpi tmp;
595
596     tmp = *a; *a = *b; *b = tmp;
597 }
598
599
600 /****************
601  * Swap the value of A and B, when SWAP is 1.
602  * Leave the value when SWAP is 0.
603  * This implementation should be constant-time regardless of SWAP.
604  */
605 void
606 _gcry_mpi_swap_cond (gcry_mpi_t a, gcry_mpi_t b, unsigned long swap)
607 {
608   mpi_size_t i;
609   mpi_size_t nlimbs;
610   mpi_limb_t mask = ((mpi_limb_t)0) - swap;
611   mpi_limb_t x;
612
613   if (a->alloced > b->alloced)
614     nlimbs = b->alloced;
615   else
616     nlimbs = a->alloced;
617   if (a->nlimbs > nlimbs || b->nlimbs > nlimbs)
618     log_bug ("mpi_swap_cond: different sizes\n");
619
620   for (i = 0; i < nlimbs; i++)
621     {
622       x = mask & (a->d[i] ^ b->d[i]);
623       a->d[i] = a->d[i] ^ x;
624       b->d[i] = b->d[i] ^ x;
625     }
626
627   x = mask & (a->nlimbs ^ b->nlimbs);
628   a->nlimbs = a->nlimbs ^ x;
629   b->nlimbs = b->nlimbs ^ x;
630
631   x = mask & (a->sign ^ b->sign);
632   a->sign = a->sign ^ x;
633   b->sign = b->sign ^ x;
634 }
635
636
637 gcry_mpi_t
638 _gcry_mpi_new (unsigned int nbits)
639 {
640     return _gcry_mpi_alloc ( (nbits+BITS_PER_MPI_LIMB-1)
641                              / BITS_PER_MPI_LIMB );
642 }
643
644
645 gcry_mpi_t
646 _gcry_mpi_snew (unsigned int nbits)
647 {
648   return _gcry_mpi_alloc_secure ( (nbits+BITS_PER_MPI_LIMB-1)
649                                   / BITS_PER_MPI_LIMB );
650 }
651
652 void
653 _gcry_mpi_release( gcry_mpi_t a )
654 {
655     _gcry_mpi_free( a );
656 }
657
658 void
659 _gcry_mpi_randomize (gcry_mpi_t w,
660                      unsigned int nbits, enum gcry_random_level level)
661 {
662   unsigned char *p;
663   size_t nbytes = (nbits+7)/8;
664
665   if (mpi_is_immutable (w))
666     {
667       mpi_immutable_failed ();
668       return;
669     }
670   if (level == GCRY_WEAK_RANDOM)
671     {
672       p = mpi_is_secure(w) ? xmalloc_secure (nbytes)
673                            : xmalloc (nbytes);
674       _gcry_create_nonce (p, nbytes);
675     }
676   else
677     {
678       p = mpi_is_secure(w) ? _gcry_random_bytes_secure (nbytes, level)
679                            : _gcry_random_bytes (nbytes, level);
680     }
681   _gcry_mpi_set_buffer( w, p, nbytes, 0 );
682   xfree (p);
683 }
684
685
686 void
687 _gcry_mpi_set_flag (gcry_mpi_t a, enum gcry_mpi_flag flag)
688 {
689   switch (flag)
690     {
691     case GCRYMPI_FLAG_SECURE:     mpi_set_secure(a); break;
692     case GCRYMPI_FLAG_CONST:      a->flags |= (16|32); break;
693     case GCRYMPI_FLAG_IMMUTABLE:  a->flags |= 16; break;
694
695     case GCRYMPI_FLAG_USER1:
696     case GCRYMPI_FLAG_USER2:
697     case GCRYMPI_FLAG_USER3:
698     case GCRYMPI_FLAG_USER4:      a->flags |= flag; break;
699
700     case GCRYMPI_FLAG_OPAQUE:
701     default: log_bug("invalid flag value\n");
702     }
703 }
704
705 void
706 _gcry_mpi_clear_flag (gcry_mpi_t a, enum gcry_mpi_flag flag)
707 {
708   (void)a; /* Not yet used. */
709
710   switch (flag)
711     {
712     case GCRYMPI_FLAG_IMMUTABLE:
713       if (!(a->flags & 32))
714         a->flags &= ~16;
715       break;
716
717     case GCRYMPI_FLAG_USER1:
718     case GCRYMPI_FLAG_USER2:
719     case GCRYMPI_FLAG_USER3:
720     case GCRYMPI_FLAG_USER4:
721       a->flags &= ~flag;
722       break;
723
724     case GCRYMPI_FLAG_CONST:
725     case GCRYMPI_FLAG_SECURE:
726     case GCRYMPI_FLAG_OPAQUE:
727     default: log_bug("invalid flag value\n");
728     }
729 }
730
731 int
732 _gcry_mpi_get_flag (gcry_mpi_t a, enum gcry_mpi_flag flag)
733 {
734   switch (flag)
735     {
736     case GCRYMPI_FLAG_SECURE:    return !!(a->flags & 1);
737     case GCRYMPI_FLAG_OPAQUE:    return !!(a->flags & 4);
738     case GCRYMPI_FLAG_IMMUTABLE: return !!(a->flags & 16);
739     case GCRYMPI_FLAG_CONST:     return !!(a->flags & 32);
740     case GCRYMPI_FLAG_USER1:
741     case GCRYMPI_FLAG_USER2:
742     case GCRYMPI_FLAG_USER3:
743     case GCRYMPI_FLAG_USER4:     return !!(a->flags & flag);
744     default: log_bug("invalid flag value\n");
745     }
746   /*NOTREACHED*/
747   return 0;
748 }
749
750
751 /* Return a constant MPI descripbed by NO which is one of the
752    MPI_C_xxx macros.  There is no need to copy this returned value; it
753    may be used directly.  */
754 gcry_mpi_t
755 _gcry_mpi_const (enum gcry_mpi_constants no)
756 {
757   if ((int)no < 0 || no > MPI_NUMBER_OF_CONSTANTS)
758     log_bug("invalid mpi_const selector %d\n", no);
759   if (!constants[no])
760     log_bug("MPI subsystem not initialized\n");
761   return constants[no];
762 }