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