chiark - git - mdw - catacomb/blob - mprand.c

   1 /* -*-c-*-
   2  *
   3  * $Id: mprand.c,v 1.4 2001/05/07 17:31:19 mdw Exp $
   4  *
   5  * Generate a random multiprecision integer
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: mprand.c,v $
  33  * Revision 1.4  2001/05/07 17:31:19  mdw
  34  * Fix off-by one bug in mprand_range.  Probably security critical: the old
  35  * code generated numbers between zero and the highest power of 2 less than
  36  * the given range.
  37  *
  38  * Revision 1.3  2000/06/17 11:45:09  mdw
  39  * Major memory management overhaul.  Added arena support.  Use the secure
  40  * arena for secret integers.  Replace and improve the MP management macros
  41  * (e.g., replace MP_MODIFY by MP_DEST).
  42  *
  43  * Revision 1.2  1999/12/22 15:55:33  mdw
  44  * Modify `mprand' slightly.  Add `mprand_range'.
  45  *
  46  * Revision 1.1  1999/12/10 23:23:05  mdw
  47  * Support for generating random large integers.
  48  *
  49  */
  50
  51 /*----- Header files ------------------------------------------------------*/
  52
  53 #include <mLib/alloc.h>
  54
  55 #include "grand.h"
  56 #include "mp.h"
  57 #include "mprand.h"
  58
  59 /*----- Main code ---------------------------------------------------------*/
  60
  61 /* --- @mprand@ --- *
  62  *
  63  * Arguments:   @mp *d@ = destination integer
  64  *              @unsigned b@ = number of bits
  65  *              @grand *r@ = pointer to random number source
  66  *              @mpw or@ = mask to OR with low-order bits
  67  *
  68  * Returns:     A random integer with the requested number of bits.
  69  *
  70  * Use:         Constructs an arbitrarily large pseudorandom integer.
  71  *              Assuming that the generator @r@ is good, the result is
  72  *              uniformly distributed in the interval %$[2^{b - 1}, 2^b)$%.
  73  *              The result is then ORred with the given @or@ value.  This
  74  *              will often be 1, to make the result odd.
  75  */
  76
  77 mp *mprand(mp *d, unsigned b, grand *r, mpw or)
  78 {
  79   size_t sz = (b + 7) >> 3;
  80   arena *a = (d && (d->f & MP_BURN)) ? arena_secure : arena_global;
  81   octet *v = x_alloc(a, sz);
  82   unsigned m;
  83
  84   /* --- Fill buffer with random data --- */
  85
  86   r->ops->fill(r, v, sz);
  87
  88   /* --- Force into the correct range --- *
  89    *
  90    * This is slightly tricky.  Oh, well.
  91    */
  92
  93   b = (b - 1) & 7;
  94   m = (1 << b);
  95   v[0] = (v[0] & (m - 1)) | m;
  96
  97   /* --- Mask, load and return --- */
  98
  99   d = mp_loadb(d, v, sz);
 100   d->v[0] |= or;
 101   memset(v, 0, sz);
 102   x_free(a, v);
 103   return (d);
 104 }
 105
 106 /* --- @mprand_range@ --- *
 107  *
 108  * Arguments:   @mp *d@ = destination integer
 109  *              @mp *l@ = limit for random number
 110  *              @grand *r@ = random number source
 111  *              @mpw or@ = mask for low-order bits
 112  *
 113  * Returns:     A pseudorandom integer, unformly distributed over the
 114  *              interval %$[0, l)$%.
 115  *
 116  * Use:         Generates a uniformly-distributed pseudorandom number in the
 117  *              appropriate range.
 118  */
 119
 120 mp *mprand_range(mp *d, mp *l, grand *r, mpw or)
 121 {
 122   size_t b = mp_bits(l);
 123   size_t sz = (b + 7) >> 3;
 124   arena *a = (d && (d->f & MP_BURN)) ? arena_secure : arena_global;
 125   octet *v = x_alloc(a, sz);
 126   unsigned m;
 127
 128   /* --- The algorithm --- *
 129    *
 130    * Rather simpler than most.  Find the number of bits in the number %$l$%
 131    * (i.e., the integer %$b$% such that %$2^{b - 1} \le l < 2^b$%), and
 132    * generate pseudorandom integers with %$n$% bits (but not, unlike in the
 133    * function above, with the top bit forced to 1).  If the integer is
 134    * greater than or equal to %$l$%, try again.
 135    *
 136    * This is similar to the algorithms used in @lcrand_range@ and friends,
 137    * except that I've forced the `raw' range of the random numbers such that
 138    * %$l$% itself is the largest multiple of %$l$% in the range (since, by
 139    * the inequality above, %$2^b \le 2l$%).  This removes the need for costly
 140    * division and remainder operations.
 141    *
 142    * As usual, the number of iterations expected is two.
 143    */
 144
 145   b = ((b - 1) & 7) + 1;
 146   m = (1 << b) - 1;
 147   do {
 148     r->ops->fill(r, v, sz);
 149     v[0] &= m;
 150     d = mp_loadb(d, v, sz);
 151     d->v[0] |= or;
 152   } while (MP_CMP(d, >=, l));
 153
 154   /* --- Done --- */
 155
 156   memset(v, 0, sz);
 157   x_free(a, v);
 158   return (d);
 159 }
 160
 161 /*----- That's all, folks -------------------------------------------------*/