sshprime.c

大名鼎鼎的远程登录软件putty的Symbian版源码

    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;
}