cryrand.cal

早期freebsd实现

/*
 * 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
 *
 *			[e-mail]
 *			...!{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