1*c5c4113dSnw141292 2*c5c4113dSnw141292 #pragma ident "%Z%%M% %I% %E% SMI" 3*c5c4113dSnw141292 4*c5c4113dSnw141292 /* 5*c5c4113dSnw141292 ** 2001 September 15 6*c5c4113dSnw141292 ** 7*c5c4113dSnw141292 ** The author disclaims copyright to this source code. In place of 8*c5c4113dSnw141292 ** a legal notice, here is a blessing: 9*c5c4113dSnw141292 ** 10*c5c4113dSnw141292 ** May you do good and not evil. 11*c5c4113dSnw141292 ** May you find forgiveness for yourself and forgive others. 12*c5c4113dSnw141292 ** May you share freely, never taking more than you give. 13*c5c4113dSnw141292 ** 14*c5c4113dSnw141292 ************************************************************************* 15*c5c4113dSnw141292 ** This file contains code to implement a pseudo-random number 16*c5c4113dSnw141292 ** generator (PRNG) for SQLite. 17*c5c4113dSnw141292 ** 18*c5c4113dSnw141292 ** Random numbers are used by some of the database backends in order 19*c5c4113dSnw141292 ** to generate random integer keys for tables or random filenames. 20*c5c4113dSnw141292 ** 21*c5c4113dSnw141292 ** $Id: random.c,v 1.11 2004/02/11 09:46:33 drh Exp $ 22*c5c4113dSnw141292 */ 23*c5c4113dSnw141292 #include "sqliteInt.h" 24*c5c4113dSnw141292 #include "os.h" 25*c5c4113dSnw141292 26*c5c4113dSnw141292 27*c5c4113dSnw141292 /* 28*c5c4113dSnw141292 ** Get a single 8-bit random value from the RC4 PRNG. The Mutex 29*c5c4113dSnw141292 ** must be held while executing this routine. 30*c5c4113dSnw141292 ** 31*c5c4113dSnw141292 ** Why not just use a library random generator like lrand48() for this? 32*c5c4113dSnw141292 ** Because the OP_NewRecno opcode in the VDBE depends on having a very 33*c5c4113dSnw141292 ** good source of random numbers. The lrand48() library function may 34*c5c4113dSnw141292 ** well be good enough. But maybe not. Or maybe lrand48() has some 35*c5c4113dSnw141292 ** subtle problems on some systems that could cause problems. It is hard 36*c5c4113dSnw141292 ** to know. To minimize the risk of problems due to bad lrand48() 37*c5c4113dSnw141292 ** implementations, SQLite uses this random number generator based 38*c5c4113dSnw141292 ** on RC4, which we know works very well. 39*c5c4113dSnw141292 */ 40*c5c4113dSnw141292 static int randomByte(){ 41*c5c4113dSnw141292 unsigned char t; 42*c5c4113dSnw141292 43*c5c4113dSnw141292 /* All threads share a single random number generator. 44*c5c4113dSnw141292 ** This structure is the current state of the generator. 45*c5c4113dSnw141292 */ 46*c5c4113dSnw141292 static struct { 47*c5c4113dSnw141292 unsigned char isInit; /* True if initialized */ 48*c5c4113dSnw141292 unsigned char i, j; /* State variables */ 49*c5c4113dSnw141292 unsigned char s[256]; /* State variables */ 50*c5c4113dSnw141292 } prng; 51*c5c4113dSnw141292 52*c5c4113dSnw141292 /* Initialize the state of the random number generator once, 53*c5c4113dSnw141292 ** the first time this routine is called. The seed value does 54*c5c4113dSnw141292 ** not need to contain a lot of randomness since we are not 55*c5c4113dSnw141292 ** trying to do secure encryption or anything like that... 56*c5c4113dSnw141292 ** 57*c5c4113dSnw141292 ** Nothing in this file or anywhere else in SQLite does any kind of 58*c5c4113dSnw141292 ** encryption. The RC4 algorithm is being used as a PRNG (pseudo-random 59*c5c4113dSnw141292 ** number generator) not as an encryption device. 60*c5c4113dSnw141292 */ 61*c5c4113dSnw141292 if( !prng.isInit ){ 62*c5c4113dSnw141292 int i; 63*c5c4113dSnw141292 char k[256]; 64*c5c4113dSnw141292 prng.j = 0; 65*c5c4113dSnw141292 prng.i = 0; 66*c5c4113dSnw141292 sqliteOsRandomSeed(k); 67*c5c4113dSnw141292 for(i=0; i<256; i++){ 68*c5c4113dSnw141292 prng.s[i] = i; 69*c5c4113dSnw141292 } 70*c5c4113dSnw141292 for(i=0; i<256; i++){ 71*c5c4113dSnw141292 prng.j += prng.s[i] + k[i]; 72*c5c4113dSnw141292 t = prng.s[prng.j]; 73*c5c4113dSnw141292 prng.s[prng.j] = prng.s[i]; 74*c5c4113dSnw141292 prng.s[i] = t; 75*c5c4113dSnw141292 } 76*c5c4113dSnw141292 prng.isInit = 1; 77*c5c4113dSnw141292 } 78*c5c4113dSnw141292 79*c5c4113dSnw141292 /* Generate and return single random byte 80*c5c4113dSnw141292 */ 81*c5c4113dSnw141292 prng.i++; 82*c5c4113dSnw141292 t = prng.s[prng.i]; 83*c5c4113dSnw141292 prng.j += t; 84*c5c4113dSnw141292 prng.s[prng.i] = prng.s[prng.j]; 85*c5c4113dSnw141292 prng.s[prng.j] = t; 86*c5c4113dSnw141292 t += prng.s[prng.i]; 87*c5c4113dSnw141292 return prng.s[t]; 88*c5c4113dSnw141292 } 89*c5c4113dSnw141292 90*c5c4113dSnw141292 /* 91*c5c4113dSnw141292 ** Return N random bytes. 92*c5c4113dSnw141292 */ 93*c5c4113dSnw141292 void sqliteRandomness(int N, void *pBuf){ 94*c5c4113dSnw141292 unsigned char *zBuf = pBuf; 95*c5c4113dSnw141292 sqliteOsEnterMutex(); 96*c5c4113dSnw141292 while( N-- ){ 97*c5c4113dSnw141292 *(zBuf++) = randomByte(); 98*c5c4113dSnw141292 } 99*c5c4113dSnw141292 sqliteOsLeaveMutex(); 100*c5c4113dSnw141292 } 101