Date: Tue, 4 Feb 2003 16:47:14 +0300 From: "Andrey A. Chernov" <ache@nagual.pp.ru> To: Dag-Erling Smorgrav <des@ofug.org> Cc: David Schultz <dschultz@uclink.Berkeley.EDU>, Kris Kennaway <kris@obsecurity.org>, current@FreeBSD.ORG Subject: Re: rand() is broken Message-ID: <20030204134714.GA92940@nagual.pp.ru> In-Reply-To: <20030204132845.GA92674@nagual.pp.ru> References: <20030202090422.GA59750@nagual.pp.ru> <20030203002639.GB44914@HAL9000.homeunix.com> <20030203100002.GA73386@nagual.pp.ru> <20030204054020.GA2447@HAL9000.homeunix.com> <20030204094659.GA87303@nagual.pp.ru> <20030204115237.GA6483@HAL9000.homeunix.com> <xzpfzr4b3pw.fsf@flood.ping.uio.no> <20030204131006.GB92301@nagual.pp.ru> <20030204131748.GA92510@nagual.pp.ru> <20030204132845.GA92674@nagual.pp.ru>
next in thread | previous in thread | raw e-mail | index | archive | help
--2fHTh5uZTiUOsy+g Content-Type: text/plain; charset=us-ascii Content-Disposition: inline On Tue, Feb 04, 2003 at 16:28:45 +0300, Andrey A. Chernov wrote: > > I'll produce working variant based on your patch... > When all done correctly, there is repeated pattern still, so some NSHUFF drop required too: 1 7 e 4 a 0 7 d 3 a 0 6 See attached patch based on -current sources. -- Andrey A. Chernov http://ache.pp.ru/ --2fHTh5uZTiUOsy+g Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="rand1.patch" --- /usr/src/lib/libc/stdlib/rand.c Tue Feb 4 14:24:08 2003 +++ ./rand.c Tue Feb 4 16:40:24 2003 @@ -51,10 +51,8 @@ #include <stdio.h> #endif /* TEST */ -#define NSHUFF 100 /* to drop part of seed -> 1st value correlation */ - static int -do_rand(unsigned long *ctx) +do_rand(uint32_t *ctx) { #ifdef USE_WEAK_SEEDING /* @@ -65,24 +63,25 @@ return ((*ctx = *ctx * 1103515245 + 12345) % ((u_long)RAND_MAX + 1)); #else /* !USE_WEAK_SEEDING */ /* - * Compute x = (7^5 * x) mod (2^31 - 1) - * wihout overflowing 31 bits: - * (2^31 - 1) = 127773 * (7^5) + 2836 - * From "Random number generators: good ones are hard to find", - * Park and Miller, Communications of the ACM, vol. 31, no. 10, - * October 1988, p. 1195. + * New algorithm derived from + * The Laws of Cryptography: Pseudo-random Number Generation + * by Neal R. Wagner + * http://www.cs.utsa.edu/~wagner/laws/rng.html + * which itself is derived from work by Donald E. Knuth. + * + * This is a linear congruence generator using the equation + * + * x(n+1) = (k * x(n) + a) mod m + * + * where m is 2^31 - 1, k is 62089911 and a is 0. */ - long hi, lo, x; + uint64_t tmp; /* Can't be initialized with 0, so use another value. */ if (*ctx == 0) *ctx = 123459876; - hi = *ctx / 127773; - lo = *ctx % 127773; - x = 16807 * lo - 2836 * hi; - if (x < 0) - x += 0x7fffffff; - return ((*ctx = x) % ((u_long)RAND_MAX + 1)); + tmp = ((uint64_t)*ctx * 62089911) % 2147483647; + return ((*ctx = tmp) % ((uint32_t)RAND_MAX + 1)); #endif /* !USE_WEAK_SEEDING */ } @@ -90,7 +89,7 @@ int rand_r(unsigned int *ctx) { - u_long val = (u_long) *ctx; + uint32_t val = (uint32_t)*ctx; int r = do_rand(&val); *ctx = (unsigned int) val; @@ -98,7 +97,7 @@ } -static u_long next = 1; +static uint32_t next = 1; int rand() @@ -110,11 +109,7 @@ srand(seed) u_int seed; { - int i; - next = seed; - for (i = 0; i < NSHUFF; i++) - (void)do_rand(&next); } --2fHTh5uZTiUOsy+g-- To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-current" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20030204134714.GA92940>