cryrand.cal

早期freebsd实现

	    ret = ((ret << 64) | shufrand());
	}

	/* load the highest chunk */
	ret <<= (highbit(finalmask)+1);
	ret |= (shufrand() >> (64-highbit(finalmask)-1));
    } while (ret >= range);

    /*
     * return the adjusted range value
     */
    return(ret+offset);
}


/*
 * srand - seed the pseudo-random additive 55 generator
 *
 * input:
 *	seed
 *
 * returns:
 *	old_seed
 *
 * This function actually seeds the shuffle generator (and indirectly
 * the additive 55 generator used by rand() and a55rand().
 *
 * See sshufrand() and sa55rand() for information about a seed.
 *
 * 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 long, or
 * 64 to 780 bits long.
 *
 * NOTE: This is NOT Blum's method.  This is used by Blum's method to
 *       generate some internal values.
 *
 * NOTE: If you do not need a crypto strong pseudo-random generator
 *	 this function may very well serve your needs.
 */
define
srand(seed)
{
    if (!isint(seed)) {
	quit "bad arg: seed must be an integer";
    }
    if (seed < 0) {
	quit "bad arg: seed < 0 is reserved for future use";
    }
    return(sshufrand(seed));
}


/*
 * cryrand - cryptographically strong pseudo-random number generator
 *
 * usage:
 *	cryrand(len)
 *
 * given:
 *	len	    number of pseudo-random bits to generate
 *
 * returns:
 *	a cryptographically strong pseudo-random number of len bits
 *
 * Internally, bits are produced log2(log2(n=p*q)) at a time.  If a
 * call to this function does not exhaust all of the collected bits,
 * the unused bits will be saved away and used at a later call.
 * Setting the seed via scryrand() or srandom() will clear out all
 * unused bits.  Thus:
 *
 *	scryrand(0);			<-- restore generator to initial state
 *	cryrand(16);			<-- 16 bits
 *
 * will produce the same value as:
 *
 *	scryrand(0);			<-- restore generator to initial state
 *	cryrand(4)<<12 | cryrand(12);	<-- 4+12 = 16 bits
 *
 * and will produce the same value as:
 *
 *	scryrand(0);			<-- restore generator to initial state
 *	cryrand(3)<<13 | cryrand(7)<<6 | cryrand(6);	<-- 3+7+6 = 16 bits
 *
 * The crypto generator is not as fast as most generators, though it is not
 * painfully slow either.
 *
 * NOTE: This function is the Blum cryptographically strong
 *	 pseudo-random number generator.
 */
define
cryrand(len)
{
    local goodbits;	/* the number of good bits generated each pass */
    local goodmask;	/* mask for the low order good bits */
    local randval;	/* pseudo-random value being generated */

    /*
     * firewall
     */
    if (!isint(len) || len < 1) {
	quit "bad arg: len must be an integer > 0";
    }

    /*
     * Determine how many bits may be generated each pass.
     *
     * The result by Alexi et. al., says that the log2(log2(n=p*q))
     * least significant bits are secure, where log2(x) is log base 2.
     */
    goodbits = highbit(highbit(cryrand_n));
    goodmask = (1 << goodbits)-1;

    /*
     * If we have bits left over from the previous call, collect
     * them now.
     */
    if (cryrand_bitcnt > 0) {

	/* case where the left over bits are enough for this call */
	if (len <= cryrand_bitcnt) {

	    /* we need only len bits */
	    randval = (cryrand_left >> (cryrand_bitcnt-len));

	    /* save the unused bits for later use */
	    cryrand_left &= ((1 << (cryrand_bitcnt-len))-1);

	    /* save away the number of bits that we will not use */
	    cryrand_bitcnt -= len;

	    /* return our complete result */
	    return(randval);

	/* case where we need more than just the left over bits */
	} else {

	    /* clear out the number of left over bits */
	    len -= cryrand_bitcnt;
	    cryrand_bitcnt = 0;

	    /* collect all of the left over bits for now */
	    randval = cryrand_left;
	}

    /* case where we have no previously left over bits */
    } else {
	randval = 0;
    }

    /*
     * Pump out len cryptographically strong pseudo-random bits,
     * 'goodbits' at a time using Blum's process.
     */
    while (len >= goodbits) {

	/* generate the bits */
	cryrand_exp = (cryrand_exp^2) % cryrand_n;
	randval <<= goodbits;
	randval |= (cryrand_exp & goodmask);

	/* reduce the need count */
	len -= goodbits;
    }

    /* if needed, save the unused bits for later use */
    if (len > 0) {

	/* generate the bits */
	cryrand_exp = (cryrand_exp^2) % cryrand_n;
	randval <<= len;
	randval |= ((cryrand_exp&goodmask) >> (goodbits-len));

	/* save away the number of bits that we will not use */
	cryrand_left = cryrand_exp & ((1 << (goodbits-len))-1);
	cryrand_bitcnt = goodbits-len;
    }

    /*
     * return our pseudo-random bits
     */
     return(randval);
}


/*
 * scryrand - seed the cryptographically strong pseudo-random number generator
 *
 * usage:
 *	scryrand(seed)
 *	scryrand()
 *	scryrand(seed,len1,len2)
 *	scryrand(seed,ip,iq,ir)
 *
 * input:
 *	[seed		pseudo-random seed
 *	[len1 len2]	minimum bit length of the Blum primes 'p' and 'q'
 *			-1 => default lengths
 *	[ip iq ir]	Initial search values for Blum primes 'p', 'q' and
 *			a quadratic residue 'r'
 *
 * returns:
 *	the previous seed
 *
 *
 * This function will seed and setup the generator needed to produce
 * cryptographically strong pseudo-random numbers.  See the function
 * a55rand() and sshufrand() for information about how 'seed' works.
 *
 * The first form of this function are fairly fast if the seed is not
 * excessively large.  The second form is also fairly fast if the internal
 * primes are not too large.  The third form, can take a long time to call.
 * (see below)   The fourth form, if the 'seed' arg is not -1, can take
 * as long as the third form to call.  If the fourth form is called with
 * a 'seed' arg of -1, then it is fairly fast.
 *
 * Calling scryrand() with 1 or 3 args (first and third forms), or
 * calling srandom(), or calling scryrand() with 4 args with the first
 * arg >0, will leave the shuffle generator in a seeded state as if
 * sshufrand(seed) has been called.
 *
 * Calling scryrand() with no args will not seed the shuffle generator,
 * before or afterwards, however the shuffle generator will have been
 * changed as a side effect of that call.
 *
 * Calling scryrand() with 4 args where the first arg is 0 or '-1'
 * will not change the other generators.
 *
 *
 * First form of call:  scryrand(seed)
 *
 * The first form of this function will seed the shuffle generator
 * (via srand).  The default precomputed constants will be used.
 *
 *
 * Second form of call:  scryrand()
 *
 * Only a new quadratic residue of n=p*q is recomputed.  The previous prime
 * values are kept.
 *
 * Unlike the first and second forms of this function, the shuffle
 * generator function is not seeded before or after the call.  The
 * current state is used to generate a new quadratic residue of n=p*q.
 *
 *
 * Third form of call:  scryrand(seed,len1,len2)
 *
 * In the third form, 'len1' and 'len2' guide this function in selecting
 * internally used prime numbers.  The larger the lengths, the longer
 * the time this function will take.  The impact on execution time of
 * cryrand() and random() may also be noticed, but not as much.
 *
 * If a length is '-1', then the default lengths (248 for len1, and 264
 * for len2) are used.  The call scryrand(0,-1,-1) recreates the initial
 * crypto state the slow and hard way.  (use scryrand(0) or srandom(0))
 *
 * This function can take a long time to call given reasonable values
 * of len1 and len2.  On an R3000, the time to seed was:
 *
 *	Approx value	digits   seed time
 *      of len1+len2   in n=p*q	   in sec
 *	------------   --------	   ------
 *	      8		   3	     0.53
 *	     16		   5	     0.54
 *	     32		  10	     0.79
 *	     64		  20	     1.17
 *	    128		  39	     2.89
 *	    200		  61	     4.68
 *	    256		  78	     7.49
 *	    322		 100	    12.47
 *	    464		 140	    35.56
 *	    512		 155	    53.57
 *	    664		 200	    83.97
 *	    830		 250	   122.93
 *	    996		 300	   242.49
 *	   1024		 309	   295.66
 *	   1328		 400	   663.44
 *	   1586		 478	  2002.10
 *	   1660		 500	  1643.45  (Faster mult/square methods kick in
 *	   1992		 600	  2885.81   in certain cases. Type  help config
 *	   2048		 617	  1578.06   in calc for more details.)
 *
 *	 NOTE: The small lengths above are given for comparison
 *	       purposes and are NOT recommended for actual use.
 *
 *	 NOTE: Generating crypto pseudo-random numbers is MUCH
 *	       faster than seeding a crypto generator.
 *
 *	 NOTE: This calc lib file is intended for demonstration
 *	       purposes.  Writing a C program (with possible assembly
 *	       or libmp assist) would produce a faster generator.
 *
 *
 * Fourth form of call:  scryrand(seed,ip,iq,ir)
 *
 * In the fourth form, 'ip', 'iq' and 'ir' serve as initial search
 * values for the two Blum primes 'p' and 'q' and an associated
 * quadratic residue 'r' respectively.  Unlike the 3rd form, where
 * lengths are given, the fourth form allows one to specify minimum
 * search values.
 *
 * The 'seed' value is interpreted as follows:
 *
 *   If seed > 0:
 *
 *	Seed and use the shuffle generator to generate 3 jump values
 *	that are in the range '[0,ip)', '[0,iq)' and '[0,ir)' respectively.
 *	Start searching for legal 'p', 'q' and 'r' values by adding
 *	the jump values to their respective argument values.
 *
 *   If seed == 0:
 *
 *	Start searching for legal 'p', 'q' and 'r' values from
 *	'ip', 'iq' and 'ir' respectively.
 *
 *	This form does not change/seed the other generators.
 *
 *   If seed == -1:
 *
 *	Let 'p' == 'ip', 'q' == 'iq' and 'r' == 'ir'.  Do not check
 *	if the value given are legal Blum primes or an associated
 *	quadratic residue respectively.
 *
 *	This form does not change/seed the other generators.
 *
 *	WARNING: No checks are performed on the args passed.
 *		 Passing improper values will likely produce
 *		 poor results, or worse!
 *
 *
 * It should be noted that calling scryrand() while using the default
 * primes took only 0.04 seconds.  Calling scryrand(0,-1,-1) took
 * 47.19 seconds.
 *
 * The paranoid, when giving explicit lengths, should keep in mind that
 * len1 and len2 are the largest powers of 2 that are less than the two
 * probable primes ('p' and 'q').  These two primes  will be used
 * internally to cryrand().  For simplicity, we refer to len1 and len2
 * as bit lengths, even though they are actually 1 less then the
 * minimum possible prime length.
 *
 * The actual lengths may exceed the lengths by slightly more than 3%.
 * Furthermore, part of the strength of this generator rests on the
 * difficultly to factor 'p*q'.  Thus one should select 'len1' and 'len2'
 * (from which 'p' and 'q' are selected) such that factoring a 'len1+len2'
 * bit number is difficult.
 *
 * 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.
 *
 * 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 long, or
 * 64 to 780 bits long.
 *
 * NOTE: This function will clear any internally buffer bits.  See
 *	 cryrand() for details.
 *
 * NOTE: This function seeds the Blum cryptographically strong
 *	 pseudo-random number generator.
 */
define
scryrand(seed,len1,len2,arg4)
{
    local rval;		/* a temporary pseudo-random value */
    local oldseed;	/* the previous seed */
    local newres;	/* the new quad res */
    local ip;		/* initial Blum prime 'p' search value */
    local iq;		/* initial Blum prime 'q' search value */
    local ir;		/* initial quadratic residue search value */
    local sqir;		/* square of ir mod n */
    local minres;	/* minimum residue allowed */
    local maxres;	/* maximum residue allowed */

    /*