OSX/libsecurity_cryptkit/lib/feeRandom.c

   1 /* Copyright (c) 1998,2011,2014 Apple Inc.  All Rights Reserved.
   2  *
   3  * NOTICE: USE OF THE MATERIALS ACCOMPANYING THIS NOTICE IS SUBJECT
   4  * TO THE TERMS OF THE SIGNED "FAST ELLIPTIC ENCRYPTION (FEE) REFERENCE
   5  * SOURCE CODE EVALUATION AGREEMENT" BETWEEN APPLE, INC. AND THE
   6  * ORIGINAL LICENSEE THAT OBTAINED THESE MATERIALS FROM APPLE,
   7  * INC.  ANY USE OF THESE MATERIALS NOT PERMITTED BY SUCH AGREEMENT WILL
   8  * EXPOSE YOU TO LIABILITY.
   9  ***************************************************************************
  10  *
  11  * FeeRandom.c - generic, portable random number generator object
  12  *
  13  * Revision History
  14  * ----------------
  15  * 10/06/98             ap
  16  *      Changed to compile with C++.
  17  * 19 Jun 97 at Apple
  18  *      Eliminated predictability of bytes 4 thru 15 of random data
  19  * 18 Jun 97 at Apple
  20  *      Reduced size of per-instance giants from 128 to 32 shorts
  21  * 23 Aug 96 at NeXT
  22  *      Created, based on Blaine Garst's NSRandomNumberGenerator class
  23  */
  24
  25 #include "feeRandom.h"
  26 #include "giantIntegers.h"
  27 #include "elliptic.h"
  28 #include "falloc.h"
  29 #include "feeDebug.h"
  30 #include "byteRep.h"
  31 #include <stdlib.h>
  32 #include "platform.h"
  33
  34 /*
  35  * 1 ==> do extra nextNum on feeRandAllocWithSeed()
  36  */
  37 #define EXTRA_NEXT_NUM  0
  38
  39 #define RANDBITS                        128             /* must be 0 mod GIANT_BITS_PER_DIGIT */
  40 #define RAND_GIANT_DIGITS       (RANDBITS/GIANT_BITS_PER_DIGIT)
  41
  42 typedef struct {
  43         giant A;
  44         giant C;
  45         giant SEED;
  46         giant x;
  47 } randInst;
  48
  49 #if             GIANTS_VIA_STACK
  50
  51 /*
  52  * Prime the curveParams and giants modules for quick allocs of giants.
  53  */
  54 static int giantsInitd = 0;
  55
  56 static void feeRandInitGiants()
  57 {
  58         if(giantsInitd) {
  59                 return;
  60         }
  61         curveParamsInitGiants();
  62         giantsInitd = 1;
  63 }
  64 #endif
  65
  66 static void pmod(giant x, int bits) {
  67         /* Force x to be x (mod 2^bits). */
  68         int j;
  69         int digits = bits / GIANT_BITS_PER_DIGIT;
  70
  71         for(j = (digits-1); j >= 0; j--) {
  72                 if(x->n[j] != 0) break;
  73         }
  74         x->sign = j+1;
  75 }
  76
  77
  78 feeRand feeRandAllocWithSeed(unsigned seed)
  79 {
  80         randInst *rinst = (randInst *) fmalloc(sizeof(randInst));
  81         int digits = RAND_GIANT_DIGITS * 4;
  82         unsigned j;
  83
  84         #if             GIANTS_VIA_STACK
  85         feeRandInitGiants();
  86         #endif
  87         rinst->SEED = newGiant(digits);
  88         rinst->C    = newGiant(digits);
  89         rinst->A    = newGiant(digits);
  90         rinst->x    = newGiant(digits);
  91         rinst->C->sign = rinst->A->sign = rinst->SEED->sign = RAND_GIANT_DIGITS;
  92         for(j=0; j<RAND_GIANT_DIGITS; j++) {
  93             rinst->C->n[j]    = (giantDigit)(seed + 0xdddddddd - j);
  94             rinst->A->n[j]    = (giantDigit)(seed + 0xfff12223 + j);
  95             rinst->SEED->n[j] = (giantDigit)(seed + j);
  96         }
  97
  98         /*
  99          * on the first feeRandBytes or feeRandNextNum, bytes 4 and 5 of
 100          * the result are duplicated 4.5 times (up to byte 15). Subsequent
 101          * data is indeed random. Thus...
 102          */
 103         #if     EXTRA_NEXT_NUM
 104         feeRandNextNum(rinst);
 105         #endif  // EXTRA_NEXT_NUM
 106         return rinst;
 107 }
 108
 109 feeRand feeRandAlloc(void)
 110 {
 111         return feeRandAllocWithSeed(createRandomSeed());
 112 }
 113
 114 void feeRandFree(feeRand frand)
 115 {
 116         randInst *rinst = (randInst *) frand;
 117
 118         clearGiant(rinst->A);
 119         freeGiant(rinst->A);
 120         clearGiant(rinst->C);
 121         freeGiant(rinst->C);
 122         clearGiant(rinst->SEED);
 123         freeGiant(rinst->SEED);
 124         clearGiant(rinst->x);
 125         freeGiant(rinst->x);
 126         ffree(rinst);
 127 }
 128
 129 unsigned feeRandNextNum(feeRand frand)
 130 {
 131         randInst *rinst = (randInst *) frand;
 132         unsigned rtn;
 133
 134         mulg(rinst->A, rinst->SEED);
 135         addg(rinst->C, rinst->SEED);
 136         pmod(rinst->SEED, RANDBITS);
 137         gtog(rinst->SEED, rinst->x);
 138
 139         /*
 140          * FIXME - this is not quite correct; rinst->x only has 4 bytes
 141          * of valid data if RANDBITS is known to be greater than or equal
 142          * to 32.
 143          */
 144         rtn = byteRepToInt((unsigned char *)&rinst->x->n);
 145         return rtn;
 146 }
 147
 148 void feeRandBytes(feeRand frand,
 149         unsigned char *bytes,           /* must be alloc'd by caller */
 150         unsigned numBytes)
 151 {
 152         randInst *rinst = (randInst *) frand;
 153         int length;
 154         unsigned toCopy;
 155         unsigned char *cp = bytes;
 156
 157         for (length = numBytes; length > 0; length -= RANDBITS/8) {
 158                 mulg(rinst->A, rinst->SEED);
 159                 addg(rinst->C, rinst->SEED);
 160                 pmod(rinst->SEED, RANDBITS);
 161                 gtog(rinst->SEED, rinst->x);
 162
 163                 toCopy = RANDBITS/8;
 164                 if(length < toCopy) {
 165                         toCopy = length;
 166                 }
 167
 168                 /*
 169                  * FIXME - not 100% platform independent....
 170                  */
 171                 bcopy(rinst->x->n, cp, toCopy);
 172                 cp += toCopy;
 173         }
 174 }
 175
 176 /* new function, 5 March 1999 - dmitch */
 177 void feeRandAddEntropy(feeRand frand, unsigned entropy)
 178 {
 179         randInst *rinst = (randInst *) frand;
 180         giant tmp = borrowGiant(RAND_GIANT_DIGITS);
 181         unsigned i;
 182
 183         if(entropy == 0) {
 184                 /* boy would that be a mistake */
 185                 entropy = 0x12345;
 186         }
 187         for(i=0; i<RAND_GIANT_DIGITS; i++) {
 188                 tmp->n[i] = (giantDigit)entropy;
 189         }
 190         tmp->sign = RAND_GIANT_DIGITS;
 191         mulg(tmp, rinst->SEED);
 192         addg(rinst->C, rinst->SEED);
 193         pmod(rinst->SEED, RANDBITS);
 194         entropy ^= 0xff0ff0ff;
 195         if(entropy == 0) {
 196                 entropy = 0x12345;
 197         }
 198         for(i=0; i<RAND_GIANT_DIGITS; i++) {
 199                 tmp->n[i] = (giantDigit)entropy;
 200         }
 201         mulg(tmp, rinst->A);
 202         addg(rinst->C, rinst->A);
 203         pmod(rinst->A, RANDBITS);
 204         /* leave C alone */
 205         returnGiant(tmp);
 206 }