/* * cryrand - cryptographically strong pseudo-random number generator library *//* * Copyright (c) 1994 by Landon Curt Noll.  All Rights Reserved. * * Permission to use, copy, modify, and distribute this software and * its documentation for any purpose and without fee is hereby granted, * provided that the above copyright, this permission notice and text * this comment, and the disclaimer below appear in all of the following: * *	supporting documentation *	source copies *	source works derived from this source *	binaries derived from this source or from derived source * * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR * PERFORMANCE OF THIS SOFTWARE. * * chongo was here	/\../\ *//* * These routines are written in the calc language.  At the time of this * notice, calc was at version 2.9.2 (We refer to calc, as in the C * program, not the Emacs subsystem). * * Calc is available by anonymous ftp from ftp.uu.net under the  * directory /pub/calc. * * If you can't get calc any other way, EMail a request to my EMail * address as shown below. * * Comments, suggestions, bug fixes and questions about these routines * are welcome.  Send EMail to the address given below. * * Happy bit twiddling, * *			Landon Curt Noll * *			chongo@toad.com *			...!{pyramid,sun,uunet}!hoptoad!chongo *//* * AN OVERVIEW OF THE FUNCTIONS: * * This calc library contains several pseudo-random number generators: * *   additive 55: * *	a55rand	  - external interface to the additive 55 generator *	sa55rand  - seed the additive 55 generator * *	This is a generator based on the additive 55 generator as *	described in Knuth's "The Art of Computer Programming - *	Seminumerical Algorithms", vol 2, 2nd edition (1981), *	Section 3.2.2, page 27, Algorithm A. * *	The period and other properties of this generator make it very *	useful to 'seed' other generators. * *	This generator is used by other other generators to produce *	various internal values.  In fact, the lower 64 bits of seed *	given to other other generators is passed to sa55rand(). * *      If you need a fast generator and do not need a crypto strong one, *      you should consider using the shuffle generator instead. * *   shuffle: * *	shufrand  - generate a pseudo-random value via a shuffle process *	sshufrand - seed the shufrand generator *	rand      - generate a pseudo-random value over a given range *	srand     - seed the random stream generator * *	This is a generator based on the shuffle generator as described in *	Knuth's "The Art of Computer Programming - Seminumerical Algorithms", *	vol 2, 2nd edition (1981), Section 3.2.2, page 32, Algorithm B. * *	The shuffle generator is fast and serves as a fairly good standard *	pseudo-random generator. * *	The shuffle generator is feed random values by the additive 55 *	generator via a55rand().  Calling a55rand() or sa55rand() will *	affect the shuffle generator output. * *	The rand function is really another interface to the shuffle *	generator.  Unlike shufrand(), rand() can return a value of any *	given size.  The value returned by rand() may be confined to *	either a half open [0,a) (0 <= value < a) or closed interval *	[a,b] (a <= value <= b).  By default, a 64 bit value is returned. * *	Calling srand() simply calls sshufrand() with the same seed. * *   crypto: * *	cryrand   - produce a cryptographically strong pseudo-random number *	scryrand  - seed the crypto generator *	random    - produce a cryptographically strong pseudo-random number *		    over a given range * 	srandom   - seed random * *	This generator is described in the papers: * *	    Blum, Blum, and Shub, "Comparison of Two Pseudorandom Number *	    Generators", in Chaum, D. et. al., "Advances in Cryptology: *	    Proceedings Crypto 82", pp. 61-79, Plenum Press, 1983. * *	    Blum, Blum, and Shub, "A Simple Unpredictable Pseudo-Random *	    Number Generator", SIAM Journal of Computing, v. 15, n. 2, *	    1986, pp. 364-383. * *	    U. V. Vazirani and V. V. Vazirani, "Trapdoor Pseudo-Random *	    Number Generators with Applications to Protocol Design", *	    Proceedings of the 24th  IEEE Symposium on the Foundations *	    of Computer Science, 1983, pp. 23-30. * *	    U. V. Vazirani and V. V. Vazirani, "Efficient and Secure *	    Pseudo-Random Number Generation", Proceedings of the 24th *	    IEEE Symposium on the Foundations of Computer Science, *	    1984, pp. 458-463. * *	    U. V. Vazirani and V. V. Vazirani, "Efficient and Secure *	    Pseudo-Random Number Generation", Advances in Cryptology - *	    Proceedings of CRYPTO '84, Berlin: Springer-Verlag, 1985, *	    pp. 193-202. * *	    "Probabilistic Encryption", Journal of Computer & System *	    Sciences 28, pp. 270-299. * *	We also refer to this generator as the 'Blum' generator. * *	This generator is considered 'strong' in that it passes all *	polynomial-time statistical tests. * *	The crypto generator is not as fast as most generators, though *	it is not painfully slow either. * *	One may fully seed this generator via scryrand().  Calling *	scryrand() with 1 or 3 arguments will result in the additive *	55 generator being seeded with the same seed.  Calling * 	scryrand() with 4 arguments, where the first argument *	is >= 0 will also result in the additive 55 generator *	being seeded with the same seed. * *	The random() generator is really another interface to the *	crypto generator.  Unlike cryrand(), random() can return a *	value confined to either a half open (0 <= value < a) or closed *	interval (a <= value <= b).  By default, a 64 bit value is *	returned. * *	Calling srandom() simply calls scryrand(seed).  The additive *	55 generator will be seeded with the same seed. * * As a bonus, the function 'nxtprime' is provided to produce a probable * prime number. * * All generators come already seeded with precomputed initial constants. * Thus, it is not required to seed a generator before using it. * * Using a seed of '0' will reload generators with their initial states. * In the case of scryrand(), lengths of -1 must also be supplied. * *	sa55rand(0)		initializes only additive 55 *	sshufrand(0)		initializes additive 55 and shuffle *	srand(0)		initializes additive 55 and shuffle *	scryrand(0,-1,-1)	initializes all generators *	scryrand(0)		initializes all generators *	srandom(0)		initializes all generators *	randstate(0)		initializes all generators * * All of the above single arg calls are fairly fast.  In fact, passing * seeding with a non-zero seed, in the above cases, where seed is * not excessively large (many bits long), is also reasonably fast. * * The call: * *	scryrand(-1, ip, iq, ir) * * is fast because no checking is performed on the 'ip', 'iq', or 'ir' * when seed is -1.  NOTE: One must ensure that 'ip', 'iq', are valid * Blum primes and that 'ir' is a quadratic residue of their product! * * A call of scryrand(seed,len1,len2), with len1,len2 > 4, (3 args) * is a somewhat slow as the length args increase.  This type of * call selects 2 primes that are used internally by the crypto * generator.  A call of scryrand(seed,ip,iq,ir) where seed >= 0 * is as slow as the 3 arg case.  See scryrand() for more information. * * A call of scryrand() (no args) may be used to quickly change the * internal state of the crypto and random generators.  Only one major * internal crypto generator value (a quadratic residue) is randomly * selected via the additive 55 generator.  The other 2 major internal * values (the 2 Blum primes) are preserved.  In this form, the additive * 55 is not seeded. * * Calling scryrand(seed,[len1,len2]) (1 or 3 args), or calling * srandom(seed) will leave the additive 55 and shuffle generator in a * seeded state as if srand(seed) has been called.  Calling * scryrand(seed,ip,iq,ir) (4 args), with seed>0 will also leave * the additive 55 generator in the same scryrand(seed) state. * * Calling scryrand() (no args) will not seed the additive * 55 or shuffle generator before or afterwards.  The additive 55 * and shuffle generators will be changed as a side effect of that call. * * Calling srandom(seed) produces the same results as calling scryrand(seed). * * The states of all generators (additive 55, shuffle and crypto) can be * saved and restored via the randstate() function.  Saving the state just * after seeding a generator and restoring it later as a very fast way * to reseed a generator. * * TRUTH IN ADVERTISING: * * The word 'probable', in reference to the nxtprime() function, is used * because of an extremely extremely small chance that a composite (a * non-prime) may be returned.  In no cases will a prime be skipped. * For our purposes, this is sufficient as the chance of returning a * composite is much smaller than the chance that a hardware glitch * will cause nxtprime() to return a bogus result. * * Another "truth in advertising" issue is the use of the term * 'pseudo-random'.  All deterministic generators are pseudo random. * This is opposed to true random generators based on some special * physical device. * * The crypto generator is 'pseudo-random'.  There is no statistical * test, which runs in polynomial time, that can distinguish the crypto * generator from a truly random source. * * A final "truth in advertising" issue deals with how the magic numbers * found in this library were generated.  Detains can be found in the * various functions, while a overview can be found in the SOURCE FOR * MAGIC NUMBERS section below. * **** * * ON THE GENERATORS: * * The additive 55 generator has a good period, and is fast.  It is * reasonable as generators go, though there are better ones available. * We use it in seeding the crypto generator as its period and * other statistical properties are good enough for our purposes. * * This shuffle generator has a very good period, and is fast.  It is * fairly good as generators go, and is better than the additive 55 * generator.  Casual direct use of the shuffle generator may be * acceptable.  Because of this, the interface to the shuffle generator, * but not the additive 55 generator, is advertised when this file is * loaded. * * The shuffle generator functions, shufrand() and rand() use the same * seed and tables.  The shuffle generator shuffles the values produced * by the additive 55 generator.  Calling or seeding the additive 55 * generator will affect the output of the shuffle generator. * * The crypto generator is the best generator in this package.  It * produces a cryptographically strong pseudo-random bit sequence. * Internally, a fixed number of bits are generated after each * generator iteration.  Any unused bits are saved for the next call * to the generator.  The crypto generator is not too slow, though * seeding the generator from scratch is slow.  Shortcuts and * pre-computer seeds have been provided for this reason.  Use of * crypto should be more than acceptable for many applications. * * The crypto seed is in 4 parts, the additive 55 seed (lower 64 * bits of seed), the shuffle seed (all but the lower 64 bits of * seed), and two lengths.  The two lengths specifies the minimum * bit size of two primes used internal to the crypto generator. * Not specifying the lengths, or using -1 will cause crypto to * use the default minimum lengths of 248 and 264 bits, respectively. * * The random() function just another interface to the crypto * generator.  Like rand(), random() provides an interval capability * (closed or open) as well as a 64 bit default return value. * The random() function as good as crypto, and produces numbers * that are equally cryptographically strong.  One may use the * seed functions srandom() or scryrand() for either the random() * or cryrand() functions. * * The seed for all of the generators may be of any size.  Only the * lower 64 bits of seed affect the additive 55 generator.  Bits * beyond the lower 64 bits affect the shuffle generators.  Excessively * large values of seed will result in increased memory usage as * well as a larger seed time for the shuffle and crypto generators. * See REGARDING SEEDS below, for more information. * * One may save and restore the state of all generators via the * randstate() function. * **** * * REGARDING SEEDS: * * Because the generators are interrelated, seeding one generator * will directly or indirectly affect the other generators.  Seeding * the shuffle generator seeds the additive 55 generator.  Seeding * the crypto generator seeds the shuffle generator. * * The seed of '0' implies that a generator should be seeded back * to its initial default state. * * For the moment, seeds < -1 are reserved for future use.  The * value of -1 is used as a special indicator to the fourth form * of scryrand(), and it not a real seed. * * A seed may be of any size.  The additive 55 generator uses only * the lower 64 bits, while the shuffle generator uses bytes beyond * the lower 64 bits. * * To help make the generator produced by seed S, significantly * different from S+1, seeds are scrambled prior to use.  The * function randreseed64() maps [0,2^64) into [0,2^64) in a 1-to-1 * and onto fashion. * * The purpose of the randreseed64() is not to add security.  It * simply helps remove the human perception of the relationship * between the seed and the production of the generator. * * The randreseed64() process does not reduce the security of the * generators.  Every seed is converted into a different unique seed. * No seed is ignored or favored. * * There is no limit on the size of a seed.  On the other hand, * extremely large seeds require large tables and long seed times. * Using a seed in the range of [2^64, 2^64 * 128!) should be * sufficient for most purposes.  An easy way to stay within this * range to to use seeds that are between 21 and 215 digits, or 64 to * 780 bits long. * **** * * SOURCE OF MAGIC NUMBERS: * * Most of the magic constants used on this library ultimately are * based on the Rand book of random numbers.  The Rand book contains * 10^6 decimal digits, generated by a physical process.  This book, * produced by the Rand corporation in the 1950's is considered * a standard against which other generators may be measured. * * The Rand book of numbers was groups into groups of 20 digits. * The first 55 groups < 2^64 were used to initialize add55_init_tbl. * The size of 20 digits was used because 2^64 is 20 digits long. * The restriction of < 2^64 was used to prevent modulus biasing. * (see the note on  modulus biasing in rand()). * * The additive 55 generator during seeding is used 128 times to help * remove the initial seed state from the initial values produced. * The loop count of 128 was a power of 2 that permits each of the * 55 table entries to be processed at least twice. * * The function, randreseed64(), uses 4 primes to scramble 64 bits * into 64 bits.  These primes were also extracted from the Rand * book of numbers.  See sshufrand() for details. * * The default shuffle table size of 128 entries is the power of 2 * that is longer than the 100 entries recommended by Knuth for * the shuffle algorithm (see the text cited in shufrand()). * We use a power of 2 shuffle table length so that the shuffle * process can select a table entry from a new additive 55 value * by extracting its top most bits. * * The quadratic residue search performed by cryres() starts at * a value that is in the interval [2^sqrpow,n-100], where '2^sqrpow' * is the smallest power of 2 >= 'n^(3/4)' where 'n=p*q'.  We also * reject any initial residue whose square (mod n) does not fit * this same restriction.  Finally, we reject any residue that * is within 100 of its square (mod n). * * The use of 'n^(3/4)' insures that the quadratic residue is * large, but not too large.  We want to avoid residues that are * near 0 or that are near 'n'.  Such residues are trivial or