?? sshprime.c
字號:
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;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -