cryrand.cal

早期freebsd实现

 * 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.
 */
define
a55rand()
{
    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: