sshprime.c

来自「远程登陆工具软件源码 用于远程登陆unix」· C语言 代码 · 共 1,398 行 · 第 1/4 页

    56891, 56893,
    56897, 56909, 56911, 56921, 56923, 56929, 56941, 56951, 56957, 56963,
    56983, 56989,
    56993, 56999, 57037, 57041, 57047, 57059, 57073, 57077, 57089, 57097,
    57107, 57119,
    57131, 57139, 57143, 57149, 57163, 57173, 57179, 57191, 57193, 57203,
    57221, 57223,
    57241, 57251, 57259, 57269, 57271, 57283, 57287, 57301, 57329, 57331,
    57347, 57349,
    57367, 57373, 57383, 57389, 57397, 57413, 57427, 57457, 57467, 57487,
    57493, 57503,
    57527, 57529, 57557, 57559, 57571, 57587, 57593, 57601, 57637, 57641,
    57649, 57653,
    57667, 57679, 57689, 57697, 57709, 57713, 57719, 57727, 57731, 57737,
    57751, 57773,
    57781, 57787, 57791, 57793, 57803, 57809, 57829, 57839, 57847, 57853,
    57859, 57881,
    57899, 57901, 57917, 57923, 57943, 57947, 57973, 57977, 57991, 58013,
    58027, 58031,
    58043, 58049, 58057, 58061, 58067, 58073, 58099, 58109, 58111, 58129,
    58147, 58151,
    58153, 58169, 58171, 58189, 58193, 58199, 58207, 58211, 58217, 58229,
    58231, 58237,
    58243, 58271, 58309, 58313, 58321, 58337, 58363, 58367, 58369, 58379,
    58391, 58393,
    58403, 58411, 58417, 58427, 58439, 58441, 58451, 58453, 58477, 58481,
    58511, 58537,
    58543, 58549, 58567, 58573, 58579, 58601, 58603, 58613, 58631, 58657,
    58661, 58679,
    58687, 58693, 58699, 58711, 58727, 58733, 58741, 58757, 58763, 58771,
    58787, 58789,
    58831, 58889, 58897, 58901, 58907, 58909, 58913, 58921, 58937, 58943,
    58963, 58967,
    58979, 58991, 58997, 59009, 59011, 59021, 59023, 59029, 59051, 59053,
    59063, 59069,
    59077, 59083, 59093, 59107, 59113, 59119, 59123, 59141, 59149, 59159,
    59167, 59183,
    59197, 59207, 59209, 59219, 59221, 59233, 59239, 59243, 59263, 59273,
    59281, 59333,
    59341, 59351, 59357, 59359, 59369, 59377, 59387, 59393, 59399, 59407,
    59417, 59419,
    59441, 59443, 59447, 59453, 59467, 59471, 59473, 59497, 59509, 59513,
    59539, 59557,
    59561, 59567, 59581, 59611, 59617, 59621, 59627, 59629, 59651, 59659,
    59663, 59669,
    59671, 59693, 59699, 59707, 59723, 59729, 59743, 59747, 59753, 59771,
    59779, 59791,
    59797, 59809, 59833, 59863, 59879, 59887, 59921, 59929, 59951, 59957,
    59971, 59981,
    59999, 60013, 60017, 60029, 60037, 60041, 60077, 60083, 60089, 60091,
    60101, 60103,
    60107, 60127, 60133, 60139, 60149, 60161, 60167, 60169, 60209, 60217,
    60223, 60251,
    60257, 60259, 60271, 60289, 60293, 60317, 60331, 60337, 60343, 60353,
    60373, 60383,
    60397, 60413, 60427, 60443, 60449, 60457, 60493, 60497, 60509, 60521,
    60527, 60539,
    60589, 60601, 60607, 60611, 60617, 60623, 60631, 60637, 60647, 60649,
    60659, 60661,
    60679, 60689, 60703, 60719, 60727, 60733, 60737, 60757, 60761, 60763,
    60773, 60779,
    60793, 60811, 60821, 60859, 60869, 60887, 60889, 60899, 60901, 60913,
    60917, 60919,
    60923, 60937, 60943, 60953, 60961, 61001, 61007, 61027, 61031, 61043,
    61051, 61057,
    61091, 61099, 61121, 61129, 61141, 61151, 61153, 61169, 61211, 61223,
    61231, 61253,
    61261, 61283, 61291, 61297, 61331, 61333, 61339, 61343, 61357, 61363,
    61379, 61381,
    61403, 61409, 61417, 61441, 61463, 61469, 61471, 61483, 61487, 61493,
    61507, 61511,
    61519, 61543, 61547, 61553, 61559, 61561, 61583, 61603, 61609, 61613,
    61627, 61631,
    61637, 61643, 61651, 61657, 61667, 61673, 61681, 61687, 61703, 61717,
    61723, 61729,
    61751, 61757, 61781, 61813, 61819, 61837, 61843, 61861, 61871, 61879,
    61909, 61927,
    61933, 61949, 61961, 61967, 61979, 61981, 61987, 61991, 62003, 62011,
    62017, 62039,
    62047, 62053, 62057, 62071, 62081, 62099, 62119, 62129, 62131, 62137,
    62141, 62143,
    62171, 62189, 62191, 62201, 62207, 62213, 62219, 62233, 62273, 62297,
    62299, 62303,
    62311, 62323, 62327, 62347, 62351, 62383, 62401, 62417, 62423, 62459,
    62467, 62473,
    62477, 62483, 62497, 62501, 62507, 62533, 62539, 62549, 62563, 62581,
    62591, 62597,
    62603, 62617, 62627, 62633, 62639, 62653, 62659, 62683, 62687, 62701,
    62723, 62731,
    62743, 62753, 62761, 62773, 62791, 62801, 62819, 62827, 62851, 62861,
    62869, 62873,
    62897, 62903, 62921, 62927, 62929, 62939, 62969, 62971, 62981, 62983,
    62987, 62989,
    63029, 63031, 63059, 63067, 63073, 63079, 63097, 63103, 63113, 63127,
    63131, 63149,
    63179, 63197, 63199, 63211, 63241, 63247, 63277, 63281, 63299, 63311,
    63313, 63317,
    63331, 63337, 63347, 63353, 63361, 63367, 63377, 63389, 63391, 63397,
    63409, 63419,
    63421, 63439, 63443, 63463, 63467, 63473, 63487, 63493, 63499, 63521,
    63527, 63533,
    63541, 63559, 63577, 63587, 63589, 63599, 63601, 63607, 63611, 63617,
    63629, 63647,
    63649, 63659, 63667, 63671, 63689, 63691, 63697, 63703, 63709, 63719,
    63727, 63737,
    63743, 63761, 63773, 63781, 63793, 63799, 63803, 63809, 63823, 63839,
    63841, 63853,
    63857, 63863, 63901, 63907, 63913, 63929, 63949, 63977, 63997, 64007,
    64013, 64019,
    64033, 64037, 64063, 64067, 64081, 64091, 64109, 64123, 64151, 64153,
    64157, 64171,
    64187, 64189, 64217, 64223, 64231, 64237, 64271, 64279, 64283, 64301,
    64303, 64319,
    64327, 64333, 64373, 64381, 64399, 64403, 64433, 64439, 64451, 64453,
    64483, 64489,
    64499, 64513, 64553, 64567, 64577, 64579, 64591, 64601, 64609, 64613,
    64621, 64627,
    64633, 64661, 64663, 64667, 64679, 64693, 64709, 64717, 64747, 64763,
    64781, 64783,
    64793, 64811, 64817, 64849, 64853, 64871, 64877, 64879, 64891, 64901,
    64919, 64921,
    64927, 64937, 64951, 64969, 64997, 65003, 65011, 65027, 65029, 65033,
    65053, 65063,
    65071, 65089, 65099, 65101, 65111, 65119, 65123, 65129, 65141, 65147,
    65167, 65171,
    65173, 65179, 65183, 65203, 65213, 65239, 65257, 65267, 65269, 65287,
    65293, 65309,
    65323, 65327, 65353, 65357, 65371, 65381, 65393, 65407, 65413, 65419,
    65423, 65437,
    65447, 65449, 65479, 65497, 65519, 65521,
};

#define NPRIMES (sizeof(primes) / sizeof(*primes))

/*
 * Generate a prime. We can deal with various extra properties of
 * the prime:
 * 
 *  - to speed up use in RSA, we can arrange to select a prime with
 *    the property (prime % modulus) != residue.
 * 
 *  - for use in DSA, we can arrange to select a prime which is one
 *    more than a multiple of a dirty great bignum. In this case
 *    `bits' gives the size of the factor by which we _multiply_
 *    that bignum, rather than the size of the whole number.
 */
Bignum primegen(int bits, int modulus, int residue, Bignum factor,
		int phase, progfn_t pfn, void *pfnparam)
{
    int i, k, v, byte, bitsleft, check, checks;
    unsigned long delta;
    unsigned long moduli[NPRIMES + 1];
    unsigned long residues[NPRIMES + 1];
    unsigned long multipliers[NPRIMES + 1];
    Bignum p, pm1, q, wqp, wqp2;
    int progress = 0;

    byte = 0;
    bitsleft = 0;

  STARTOVER:

    pfn(pfnparam, PROGFN_PROGRESS, phase, ++progress);

    /*
     * Generate a k-bit random number with top and bottom bits set.
     * Alternatively, if `factor' is nonzero, generate a k-bit
     * random number with the top bit set and the bottom bit clear,
     * multiply it by `factor', and add one.
     */
    p = bn_power_2(bits - 1);
    for (i = 0; i < bits; i++) {
	if (i == 0 || i == bits - 1)
	    v = (i != 0 || !factor) ? 1 : 0;
	else {
	    if (bitsleft <= 0)
		bitsleft = 8, byte = random_byte();
	    v = byte & 1;
	    byte >>= 1;
	    bitsleft--;
	}
	bignum_set_bit(p, i, v);
    }
    if (factor) {
	Bignum tmp = p;
	p = bigmul(tmp, factor);
	freebn(tmp);
	assert(bignum_bit(p, 0) == 0);
	bignum_set_bit(p, 0, 1);
    }

    /*
     * Ensure this random number is coprime to the first few
     * primes, by repeatedly adding either 2 or 2*factor to it
     * until it is.
     */
    for (i = 0; i < NPRIMES; i++) {
	moduli[i] = primes[i];
	residues[i] = bignum_mod_short(p, primes[i]);
	if (factor)
	    multipliers[i] = bignum_mod_short(factor, primes[i]);
	else
	    multipliers[i] = 1;
    }
    moduli[NPRIMES] = modulus;
    residues[NPRIMES] = (bignum_mod_short(p, (unsigned short) modulus)
			 + modulus - residue);
    if (factor)
	multipliers[NPRIMES] = bignum_mod_short(factor, modulus);
    else
	multipliers[NPRIMES] = 1;
    delta = 0;
    while (1) {
	for (i = 0; i < (sizeof(moduli) / sizeof(*moduli)); i++)
	    if (!((residues[i] + delta * multipliers[i]) % moduli[i]))
		break;
	if (i < (sizeof(moduli) / sizeof(*moduli))) {	/* we broke */
	    delta += 2;
	    if (delta > 65536) {
		freebn(p);
		goto STARTOVER;
	    }
	    continue;
	}
	break;
    }
    q = p;
    if (factor) {
	Bignum tmp;
	tmp = bignum_from_long(delta);
	p = bigmuladd(tmp, factor, q);
	freebn(tmp);
    } else {
	p = bignum_add_long(q, delta);
    }
    freebn(q);

    /*
     * Now apply the Miller-Rabin primality test a few times. First
     * work out how many checks are needed.
     */
    checks = 27;
    if (bits >= 150)
	checks = 18;
    if (bits >= 200)
	checks = 15;
    if (bits >= 250)
	checks = 12;
    if (bits >= 300)
	checks = 9;
    if (bits >= 350)
	checks = 8;
    if (bits >= 400)
	checks = 7;
    if (bits >= 450)
	checks = 6;
    if (bits >= 550)
	checks = 5;
    if (bits >= 650)
	checks = 4;
    if (bits >= 850)
	checks = 3;
    if (bits >= 1300)
	checks = 2;

    /*
     * Next, write p-1 as q*2^k.
     */
    for (k = 0; bignum_bit(p, k) == !k; k++)
	continue;	/* find first 1 bit in p-1 */
    q = bignum_rshift(p, k);
    /* And store p-1 itself, which we'll need. */
    pm1 = copybn(p);
    decbn(pm1);

    /*
     * Now, for each check ...
     */
    for (check = 0; check < checks; check++) {
	Bignum w;

	/*
	 * Invent a random number between 1 and p-1 inclusive.
	 */
	while (1) {
	    w = bn_power_2(bits - 1);
	    for (i = 0; i < bits; i++) {
		if (bitsleft <= 0)
		    bitsleft = 8, byte = random_byte();
		v = byte & 1;
		byte >>= 1;
		bitsleft--;
		bignum_set_bit(w, i, v);
	    }
	    bn_restore_invariant(w);
	    if (bignum_cmp(w, p) >= 0 || bignum_cmp(w, Zero) == 0) {
		freebn(w);
		continue;
	    }
	    break;
	}

	pfn(pfnparam, PROGFN_PROGRESS, phase, ++progress);

	/*
	 * Compute w^q mod p.
	 */
	wqp = modpow(w, q, p);
	freebn(w);

	/*
	 * See if this is 1, or if it is -1, or if it becomes -1
	 * when squared at most k-1 times.
	 */
	if (bignum_cmp(wqp, One) == 0 || bignum_cmp(wqp, pm1) == 0) {
	    freebn(wqp);
	    continue;
	}
	for (i = 0; i < k - 1; i++) {
	    wqp2 = modmul(wqp, wqp, p);
	    freebn(wqp);
	    wqp = wqp2;
	    if (bignum_cmp(wqp, pm1) == 0)
		break;
	}
	if (i < k - 1) {
	    freebn(wqp);
	    continue;
	}

	/*
	 * It didn't. Therefore, w is a witness for the
	 * compositeness of p.
	 */
	freebn(p);
	freebn(pm1);
	freebn(q);
	goto STARTOVER;
    }

    /*
     * We have a prime!
     */
    freebn(q);
    freebn(pm1);
    return p;
}