cryrand.cal

早期freebsd实现

     * firewall - avoid bogus args and very trivial lengths
     */
    /* catch the case of no args - compute a different quadratic residue */
    if (isnull(seed) && isnull(len1) && isnull(len2)) {

	/* generate the next quadratic residue */
	do {
	    newres = cryres(cryrand_n);
	} while (newres == cryrand_r);
	cryrand_r = newres;
	cryrand_exp = cryrand_r;

	/* clear the internal bits */
	cryrand_left = 0;
	cryrand_bitcnt = 0;

	/* return the current seed early */
	return (cry_seed);
    }
    if (!isint(seed)) {
	quit "bad arg: seed arg (1st) must be an integer";
    }
    if (param(0) == 4) {
	if (seed < -1) {
	    quit "bad arg: with 4 args: a seed < -1 is reserved for future use";
	}
    } else if (param(0) > 0 && seed < 0) {
	quit "bad arg: a seed arg (1st) < 0 is reserved for future use";
    }

    /*
     * 4 arg case: select or search for 'p', 'q' and 'r' from given values
     */
    if (param(0) == 4) {

	/* set initial values */
	ip = len1;
	iq = len2;
	ir = arg4;

	/*
	 * Unless prohibited by a seed of -1, force minimum values on
	 * 'ip', 'iq' and 'ir'.
	 */
	if (seed >= 0) {
	    /*
	     * Due to the initial quadratic residue selection process,
	     * the smallest Blum prime that is usable is 19.  This
	     * in turn implies that the smallest 'n' is 19*19 = 361.
	     * This in turn imples that the smallest initial residue
	     * that is possible is 128 (for the value 'n = 23*23 = 529).
	     */
	    if (!isint(ip) || ip < 19) {
	       ip = 19;
	    }
	    if (!isint(iq) || iq < 19) {
	       iq = 19;
	    }
	    if (!isint(ir) || ir < 128) {
	       ir = 128;
	    }
	}

	/*
	 * Determine our prime search points
	 *
	 * Unless we have a seed <= 0, we will add a random 64 bit
	 * value to the initial search points.
	 */
	if (seed > 0) {
	    /* add in a random value */
	    oldseed = srand(seed);
	    ip += rand(ip);
	    iq += rand(iq);
	}

	/*
	 * force ip <= iq
	 */
	if (ip > iq) {
	    swap(ip, iq);
	}

	/*
	 * find the first Blum prime 'p'
	 */
	if (seed >= 0) {
	    cryrand_p = nxtprime(ip,3,4);
	} else {
	    /* seed == -1: assume 'ip' is a Blum prime */
	    cryrand_p = ip;
	}

	/*
	 * find the 2nd Blum prime 'q' > 'p', if needed
	 */
	if (seed >= 0) {
	    if (iq <= cryrand_p) {
		iq = cryrand_p + 2;
	    }
	    cryrand_q = nxtprime(iq,3,4);
	} else {
	    /* seed == -1: assume 'iq' is a Blum prime */
	    cryrand_q = iq;
	}

	/* remember our p*q Blum prime product as well */
	cryrand_n = cryrand_p*cryrand_q;

	/*
	 * search for a quadratic residue
	 */
	if (seed >= 0) {

	    /* 
	     * add in a random value to 'ir' if seeded 
	     *
	     * Unless we have a seed <= 0, we will add a random 64 bit
	     * value to the initial search point.
	     */
	    if (seed > 0) {
		ir += rand(ir);
	    }

	    /*
	     * increment until we find a quadratic value
	     *
	     * p is prime and J(r,p) == 1  ==>  r is a quadratic residue of p
	     * q is prime and J(q,p) == 1  ==>  r is a quadratic residue of q
	     *
	     * J(r,p)*J(r,q) == J(r,p*q)
	     * J(r,p) and J(q,p) == 1	   ==>  J(r,p*q) == 1
	     * J(r,p*q) == 1		   ==>  r is a quadratic residue of p*q
	     *
	     * We could simply compute the square of a value mod n like
	     * we do in cryres(), but here we want to climb a little higher 
	     * than the ir value given.  We will start sequentially searching
	     * values starting at the initial search point 'ir', while at
	     * same time confining our search to the interval [2^sqrpow,n-100],
	     * where 2^sqrpow is the smallest power of 2 >= n^(3/4).  This
	     * range helps us avoid selecting trivial residues.
	     *
	     * We will also reject any quadratic residue whose square mod n 
	     * is outside of the [2^sqrpow,n-100] range, or whose square mod n 
	     * is within 100 of itself.
	     */
	    minres = 2^(highbit(floor(power(cryrand_n,0.75)))+1);
	    maxres = cryrand_n - 100;
	    --ir;
	    do {
		/* consdier the next residue that is in the allowed range */
		++ir;
		if (ir < minres || ir > maxres) {
		    ir = minres;
		}
		sqir = pmod(ir, 2, cryrand_n);
	    } while (jacobi(ir,cryrand_p) != 1 || 		\
	    	     jacobi(ir,cryrand_q) != 1 ||		\
		     sqir < minres || sqir > maxres ||		\
		     abs(sqir-ir) <= 100);
	}
	cryrand_r = ir;

	/*
	 * clear the previously unused cryrand bits & other misc setup
	 */
	cryrand_left = 0;
	cryrand_bitcnt = 0;
	cryrand_exp = cryrand_r;

	/*
	 * reseed the generator, if needed
	 *
	 * The crypto generator no longer needs the additive 55 and shuffle
	 * generators.  We however, restore the additive 55 and shuffle
	 * generators back to its seeded state in order to be sure that it
	 * will be left in the same state.
	 *
	 * This will make more reproducible, calls to the additive 55 and
	 * shuffle generator; or more reproducible, calls to this function
	 * without args.
	 */
	if (seed > 0) {
	    ir = srand(seed);   /* ignore this return value */
	    return(oldseed);
	} else {
	    /* no seed change, return the current seed */
	    return (cry_seed);
	}
    }

    /*
     * If not the 4 arg case:
     *
     * convert explicit -1 args into default values
     * convert missing args into -1 values (use precomputed tables)
     */
    if ((isint(len1) && len1 != -1 && len1 < 5) ||
	(isint(len2) && len2 != -1 && len2 < 5) ||
	(!isint(len1) && isint(len2)) ||
	(isint(len1) && !isint(len2))) {
	quit "bad args: 2 & 3: if 2nd is given, must be -1 or ints > 4";
    }
    if (isint(len1) && len1 == -1) {
	len1 = 248;	/* default len1 value */
    }
    if (isint(len2) && len2 == -1) {
	len2 = 264;	/* default len2 value */
    }
    if (!isint(len1) && !isint(len2)) {
	/* from here down, -1 means use precomputed values */
	len1 = -1;
	len2 = -1;
    }

    /*
     * force len1 <= len2
     */
    if (len1 > len2) {
	swap(len1, len2);
    }

    /*
     * seed the generator
     */
    oldseed = srand(seed);

    /*
     * generate p and q Blum primes
     *
     * The Blum process requires the primes to be of the form 3 mod 4.
     * We also generate n=p*q for future reference.
     *
     * We make sure that the lengths are the minimum lengths possible.
     * We want some range to select a random prime from, so we
     * go at least 3 bits higher, and as much as 3% plus 3 bits
     * higher.  Since the section is a random, how high really
     * does not matter that much, but we want to avoid going to
     * an extreme to keep the execution time from getting too long.
     *
     * Finally, we generate a quadratic residue of n=p*q.
     */
    if (len1 > 0) {
	/* generate a pseudo-random prime ~len1 bits long */
	rval = rand(2^(len1-1), 2^((int(len1*1.03))+3));
	cryrand_p = nxtprime(rval,3,4);
    } else {
	/* use precomputed 'p' value */
	cryrand_p = cryrand_init_p;
    }
    if (len2 > 0) {
	/* generate a pseudo-random prime ~len1 bits long */
	rval = rand(2^(len2-1), 2^((int(len2*1.03))+3));
	cryrand_q = nxtprime(rval,3,4);
    } else {
	/* use precomputed 'q' value */
	cryrand_q = cryrand_init_q;
    }

    /*
     * find the quadratic residue
     */
    cryrand_n = cryrand_p*cryrand_q;
    if (len1 == 248 && len2 == 264 && seed == 0) {
	cryrand_r = cryrand_init_r;
    } else {
	cryrand_r = cryres(cryrand_n);
    }

    /*
     * clear the previously unused cryrand bits & other misc setup
     */
    cryrand_left = 0;
    cryrand_bitcnt = 0;
    cryrand_exp = cryrand_r;

    /*
     * reseed the generator
     *
     * The crypto generator no longer needs the additive 55 and shuffle
     * generators.  We however, restore the additive 55 and shuffle
     * generators back to its seeded state in order to be sure that it
     * will be left in the same state.
     *
     * This will make more reproducible, calls to the additive 55 and
     * shuffle generator; or more reproducible, calls to this function
     * without args.
     */
    /* we do not care about this old seed */
    rval = srand(seed);

    /*
     * return the old seed
     */
    return(oldseed);
}


/*
 * random - a cryptographically strong pseudo-random number generator
 *
 * usage:
 *	random() 	- generate a pseudo-random integer >=0 and < 2^64
 *	random(a) 	- generate a pseudo-random integer >=0 and < a
 *	random(a,b)	- generate a pseudo-random integer >=a and <= b
 *
 * returns:
 *	a large cryptographically strong pseudo-random number  (see usage)
 *
 * This function is just another interface to the crypto generator.
 * (see the cryrand() function).
 *
 * When no arguments are given, a pseudo-random number in the half open
 * interval [0,2^64) is produced.  This form is identical to calling
 * cryrand(64).
 *
 * When 1 argument is given, a pseudo-random number in the half open interval
 * [0,a) is produced.
 *
 * When 2 arguments are given, a pseudo-random number in the closed interval
 * [a,b] is produced.
 *
 * This generator uses the crypto to return a large pseudo-random number.
 *
 * The input values a and b, if given, must be integers.
 *
 * 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(), srandom() or cryrand(len,1)
 * will clear out all unused bits.
 *
 * NOTE: The BSD random() function returns only 31 bits, while we return 64.
 *
 * NOTE: This function is the Blum cryptographically strong
 *	 pseudo-random number generator.
 */
define
random(a,b)
{
    local range;		/* we must generate [0,range) first */
    local offset;		/* what to add to get a adjusted range */
    local rangebits;		/* the number of bits in range */
    local ret;			/* pseudo-random bit value */

    /*
     * setup and special cases
     */
    /* deal with the rand() case */
    if (isnull(a) && isnull(b)) {
	/* no args means return 64 bits */
	return(cryrand(64));
    }
    /* firewall - args, if given must be in integers */
    if (!isint(a) || (!isnull(b) && !isint(b))) {
	quit "bad args: args, if given, must be integers";
    }
    /* convert rand(x) into rand(0,x-1) */
    if (isnull(b)) {
	/* convert call into a closed interval */
	b = a-1;
	a = 0;
	/* firewall - rand(0) should act like rand(0,0) */
	if (b == -1) {
	    return(0);
	}
    }
    /* determine the range and offset */
    if (a >= b) {
	/* deal with the case of rand(a,a) */
	if (a == b) {
	    /* not very random, but it is true! */
	    return(a);
	}
	range = a-b+1;
	offset = b;