* semi-trivial.  Applying the same restriction to the square * of the initial residue avoid initial residues near 'sqrt(n)'. * Such residues are trivial or semi-trivial as well. * * Avoiding residues whose squares (mod n) are not within 100 of  * itself helps avoid selecting residue sequences (repeated  * squaring mod n) that initally do not change very much. * Such residues might be somewhat trivial, so we play it safe. * * Taking some care to select a good initial residue helps * eliminate cheep search attacks.  It is true that a subsequent * residue could be one of the residues that we would initially * avoid.  However such an occurance will happen after the * generator is well underway and any such information * has been lost. * * The use of '100' in the above initial residue selection is * somewhat arbitrary.  It could be argued that a value as * small as 10 are sufficient.  The value '100' was selected * because it is the first 3 digits of the Rand Book of Numbers. * We used 3 digits instead of 2 or 1 because '10' was too close * for comfort and '1' was clearly too small. * * Because of the initial 'n-100' upper bound part of the initial * residue selection range, the smallest Blum prime that may be * used is 19.  The first 3 Blum primes 3, 7, and 11 cannot be * used.  The largest value of 'n' that is a product of those * Blum primes is 121.  The 'n-100' value (21) is already smaller * than the smallest power of 2 >= 'n^(3/4)'.  The next Blum prime, * 19, produces the smallest value of 'n' (19*19=361) for which * one can find an initial residue that can satisfy the above. * By not considering Blum primes that are less than 5 bits long, * we avoid the smaller problem values. * * The final magic numbers: '248' and '264' are the exponents the * largest powers of 2 that are < the two default Blum primes 'p' * and 'q' used by the crypto generator.  The values of '248' and * '264' implies that the product n=p*q > 2^512.  Each iteration * of the crypto generator produces log2(log2(n=p*q)) random bits. * The crypto generator is the most efficient when n is slightly > * 2^(2^b).  The product n > 2^(2^9)) produces 9 bits as efficiently * as possible under the crypto generator process. * * Not being able to factor 'n=p*q' into 'p' and 'q' does not directly * improve the crypto generator.  On the other hand, it can't hurt. * The two len values differ slightly to avoid factorization attacks * that work on numbers that are a perfect square, or where the two * primes are nearly the same.  I elected to have the sizes differ * by 3% of the product size.  The difference between '248' and * '264', is '16', which is ~3.125% of '512'.  Now 3% of '512' is * '~15.36', and the next largest whole number is '16'. * * The product n=p*q > 2^512 implies a product if at least 155 digits. * A product of two primes that is at least 155 digits is slightly * beyond Number Theory and computer power of Nov 1992, though this * will likely change in the future. * * Again, the ability (or lack thereof) to factor 'n=p*q' does not * directly relate to the strength of the crypto generator.  We * selected n=p*q > 2^512 mainly because '512 was a power of 2 and * only slightly because it is up in the range where it is difficult * to factor. * **** * * FOR THE PARANOID: * * The truly paranoid might suggest that my claims in the MAGIC NUMBERS * section are a lie intended to entrap people.  Well they are not, but * you need not take my word for it. * * The random numbers from the Rand book of random numbers can be * verified by anyone who obtains the book.  As these numbers were * created before I (Landon Curt Noll) was born (you can look up * my birth record if you want), I claim to have no possible influence * on their generation. * * There is a very slight chance that the electronic copy of the * Rand book that I was given access to differs from the printed text. * I am willing to provide access to this electronic copy should * anyone wants to compare it to the printed text. * * One might object to the complexity of the seed scramble/mapping * via the randreseed64() function.  The randreseed64() function maps: * *	1 ==> 4967126403401436567 * * calling srand(1) with the randreseed64() process would be the same * as calling srand(4967126403401436567) without it.  No extra security * is gained or reduced by using the randreseed64() process.  The meaning * of seeds are exchanged, but not lost or favored (used by more than * one input seed). * * One could take issue with my selection of the default sizes '248' * and '264'.   As far as I know, 155 digits (512 bits) is beyond the * state of the art of Number Theory and Computation as of 01 Sep 92. * It will likely be true that 155 digit products of two primes could * come within reach in the next few years, but so what?  If you are * truly paranoid, why would you want to use the default seed, which * is well known? * * The paranoid today might consider using the lengths of at least '345' * and '325' will produce a product of two primes that is 202 digits. * (the 2nd and 3rd args of scryrand > 345 & >325 respectively)  Factoring * 200+ digit product of two primes is well beyond the current hopes of * Number Theory and Computer power, though even this limit may be passed * someday. * * One might ask if value of '100' is too small with respect to the * initial residue selection.  Showing that '100' is too small would * be difficult.  Even if one could make that case, the chance that * a 'problem' initial reside would be used would be very very small * for non-trivial values of 'p' and 'q'. * * If all the above fails to pacify the truly paranoid, then one may * select by some independent means, 2 Blum primes (primes mod 4 == 3, * p < q), and a quadratic residue if p*q.  Then by calling: * *	scryrand(-1, p, q, r) * * and then calling cryrand() or random(), one may bypass all magic * numbers and use the pure generator. * * Note that randstate() may also be used by the truly paranoid. * Even though it holds state for the other generators, their states * are independent. * **** * * GOALS: * * The goals of this package are: * *	all magic numbers are explained * *	    I distrust systems with constants (magic numbers) and tables *	    that have no justification (e.g., DES).  I believe that I have *	    done my best to justify all of the magic numbers used. * *	 full documentation * *	    You have this source file, plus background publications, *	    what more could you ask? * *	large selection of seeds * *	    Seeds are not limited to a small number of bits.  A seed *	    may be of any size. * *	the strength of the generators may be tuned to meet the application need * *	    By using the appropriate seed arguments, one may increase *	    the strength of the generator to suit the need of the *	    application.  One does not have just a few levels. * * This calc lib file is intended for demonstration purposes.  Writing * a C program (with possible assembly or libmp assist) would produce * a faster generator. * * Even though I have done my best to implement a good system, you still * must use these routines your own risk. * * Share and enjoy!  :-) *//* * These constants are used by all of the generators in various direct and * indirect forms. */static cry_seed = 0;			/* master seed */static cry_mask = 0xffffffffffffffff;	/* 64 bit work mask *//* * Initial magic values for the additive 55 generator - used by sa55rand() * * These values were generated from the Rand book of random numbers. * In groups of 20 digits, we took the first 55 groups < 2^64.  Leading  * 0 digits were dropped off to avoid confusion with octal values. */static mat add55_init_tbl[55] = {    10097325337652013586,	8422689531964509303,	   9376707153831131165,    12807999708015736147,      12171768336606574717,	   2051656926866574818,     3529647783580834282,      13746700781847540610,	  17468509505804776974,    14385537637435099817,      14225685144642756788,	  11100020401286074697,     7207317906119690446,      15474452669527079953,      16868487670307112059,     4493524947524633824,      13021248927856520106,	  15956600001874392423,     1758753794041921585,	1540354560501451176,	   5335129695612719255,     9973334408846123356,	2295368703230757546,	  15020099946907494138,    10518216150184876938,	9188200973282539527,	   4220863048338987374,      682273982071453295,	7706178130835869910,	   4618975533122308420,      397583911260717646,	5686731560708285046,	  10123916228549657560,     1304775865627110086,      15501295782182641134,	   3061180729620744156,     6958929830512809719,      10850627469959910507,	  13499063195307571839,     6410193623982098952,	4111084083850807341,	  17719042079595449953,     5462692006544395659,      18288274374963224041,	   8337656769629990836,     7477446061798548911,	9815931464890815877,	   6913451974267278601,    11883095286301198901,      14974403441045516019,	  14210337129134237821,    12883973436502761184,	4285013921797415077,	  16435915296724552670,     3742838738308012451};/* * additive 55 tables - used by a55rand() and sa55rand() */static add55_j = 23;		/* the first walking table pointer */static add55_k = 54;		/* the second walking table pointer */static add55_seed64 = 0;	/* lower 64 bits of the reseeded seed */static mat add55_tbl[55];	/* additive 55 state table *//* * cryobj - cryptographic pseudo-random state object */obj cryobj {							\    p,		/* first Blum prime (prime 3 mod 4) */		\    q,		/* second Blum prime (prime 3 mod 4) */		\    r,		/* quadratic residue of n=p*q */		\    exp,	/* used in computing crypto good bits */	\    left,	/* bits unused from the last cryrand() call */	\    bitcnt,	/* left contains bitcnt crypto good bits */	\    a55j,	/* 1st additive 55 table pointer */		\    a55k,	/* 2nd additive 55 table pointer */		\    seed,	/* last seed set by sa55rand() or 0 */		\    shufy,	/* Y (previous a55rand output for shuffle) */	\    shufsz,	/* size of the shuffle table */			\    shuftbl,	/* a matrix of shufsz entries */		\    a55tbl	/* additive 55 generator state table */		\}/* * initial cryptographic pseudo-random values - used by scryrand() * * These values are what the crypto generator is initialized with * with this library first read.  These values may be reproduced the * hard way by calling scryrand(0,248,264) or scryrand(0,-1,-1). * * We will build up these values a piece at a time to avoid long lines * that are difficult to send via EMail. *//* p, first Blum prime */static cryrand_init_p = 0x1aa9e726a735044;cryrand_init_p <<= 200;cryrand_init_p |= 0x73b7457c5297122310880fcbfa8d4e38380a00396d533300bb;/* q, second Blum prime */static cryrand_init_q = 0xa62ee0481aa12059c3;cryrand_init_q <<= 200;cryrand_init_q |= 0x79ef44e72ff58ea70cacabbe9d264a0b16db72117d96f77e17;/* quadratic residue of n=p*q */static cryrand_init_r = 0x3d214853f9a5bb4b12f467c9052129a9;cryrand_init_r <<= 200;cryrand_init_r |= 0xd215cc6b3c2eae8c7090591b16d8044a886b3c6a58759b1a07;cryrand_init_r <<= 200;cryrand_init_r |= 0x2b50a914b42e1b6f9703be86742837c4bc637804c2dc668c5b;/* * cryptographic pseudo-random values - used by cryrand() and scryrand() *//* p, first Blum prime */static cryrand_p = cryrand_init_p;/* q, second Blum prime */static cryrand_q = cryrand_init_q;/* n = p*q */static cryrand_n = cryrand_p*cryrand_q;/* quad residue of n */static cryrand_r = cryrand_init_r;/* this cryrand() running exp used in computing crypto good bits */static cryrand_exp = cryrand_r;/* good crypto bits unused from the last cryrand() call */static cryrand_left = 0;/* the value cryrand_left contains cryrand_bitcnt crypto good bits */static cryrand_bitcnt = 0;/* * shufrand - shuffle generator constants */static shuf_size = 128;			/* entries in shuffle table */static shuf_shift = (64-highbit(shuf_size));	/* shift a55 value to get tbl indx */static shuf_y;				/* Y value (previous output) */static mat shuf_tbl[shuf_size];		/* shuffle state table *//* * products of consecutive primes - used by nxtprime() * * We compute these products now to avoid recalculating them on each call. * These values help weed out numbers that have a prime factor < 1000. */static nxtprime_pfact10 = pfact(10);static nxtprime_pfact100 = pfact(100)/nxtprime_pfact10;static nxtprime_pfact1000 = pfact(1000)/nxtprime_pfact100;/* * a55rand - additive 55 pseudo-random number generator * * returns: *	A number in the half open interval [0,2^64) * * This function implements the additive 55 pseudo-random number 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. * * This function is called from the shuffle generator function shufrand(). * * NOTE: This is NOT Blum's method.  This is used by Blum's method to *       generate some internal values. * * NOTE: If you need a fast generator and do not need a crypto strong one, *       you should consider using the shuffle generator (see shufrand() *	 and rand()).  Direct use of this function is not recommended. */definea55rand(){    local ret;			/* the pseudo-random number to return */    /* generate the next value using the additive 55 generator method */    ret = add55_tbl[add55_k] + add55_tbl[add55_j];    ret &= cry_mask;    add55_tbl[add55_k] = ret;    /* post-process out data with the seed */    ret = xor(ret, add55_seed64);    /* step the pointers */    --add55_j;    if (add55_j < 0) {	add55_j = 54;    }    --add55_k;    if (add55_k < 0) {	add55_k = 54;    }    /* return the new pseudo-random number */    return(ret);}/* * sa55rand - initialize the additive 55 pseudo-random generator * * given: *	seed * * returns: *	old_seed * * This function seeds the additive 55 pseudo-random 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. * * Unlike Knuth's description, we will let a seed post process our data. * * We do not apply the seed processing to the additive 55 table * data as this would disturb its pseudo-random generator properties. * Instead, we xor the output with the low 64 bits of seed. * * If seed == 0: * *    This function produces values in exactly the same way *    described by Knuth. * * else seed > 0: * *    Each value produced is xor-ed by a 64 bit value.  This value *    is the result of randreseed64(rand), which produces a 64 *    bit value. * * else seed == -1: