X-Git-Url: http://git.silcnet.org/gitweb/?p=silc.git;a=blobdiff_plain;f=lib%2Fsilcmath%2Fsilcprimegen.c;h=b2fe429db40e9ebcd574c204541365b266d9c1f4;hp=decb9538edbe46c2ea00675b5377f98359a2bdde;hb=e7b6c157b80152bf9fb9266e6bdd93f9fb0db776;hpb=04f41c4481381e8e7c1e685a4edb6be6ec5d2c66 diff --git a/lib/silcmath/silcprimegen.c b/lib/silcmath/silcprimegen.c index decb9538..b2fe429d 100644 --- a/lib/silcmath/silcprimegen.c +++ b/lib/silcmath/silcprimegen.c @@ -1,16 +1,15 @@ /* silcprimegen.c - - Author: Pekka Riikonen - Copyright (C) 1997 - 2000 Pekka Riikonen + Author: Pekka Riikonen + + Copyright (C) 1997 - 2007 Pekka Riikonen This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2 of the License, or - (at your option) any later version. - + the Free Software Foundation; version 2 of the License. + This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the @@ -20,19 +19,19 @@ /* Created: Mon Dec 8 16:35:37 GMT+0200 1997 */ /* $Id$ */ -#include "silcincludes.h" +#include "silc.h" -/* - Fixed primetable for small prime division. We use this primetable to - test if possible prime is divisible any of these. Primetable is NULL - terminated. This same primetable can be found in SSH and PGP except that - SSH don't have prime 2 in the table. This sort of prime table is easily +/* + Fixed primetable for small prime division. We use this primetable to + test if possible prime is divisible any of these. Primetable is NULL + terminated. This same primetable can be found in SSH and PGP except that + SSH don't have prime 2 in the table. This sort of prime table is easily created, for example, using sieve of Erastosthenes. - - Just to include; if somebody is interested about Erastosthenes. Creating a - small prime table using sieve of Erastosthenes would go like this: Write + + Just to include; if somebody is interested about Erastosthenes. Creating a + small prime table using sieve of Erastosthenes would go like this: Write down a list of integers in range of 2 to n. Here in example n = 20. - + 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Then mark all multiples of 2 (Note: 2 is a prime number): @@ -46,14 +45,14 @@ x x x x x x x x x x x And continue doing this, marking all multiples of the next unmarked - number until there are now new unmarked numbers. And there you have a + number until there are now new unmarked numbers. And there you have a prime table. So in this example, primes between 2 - 20 are: - + 2 3 5 7 11 13 17 19 */ -static unsigned int primetable[] = +static SilcUInt32 primetable[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, @@ -187,154 +186,185 @@ static unsigned int primetable[] = }; -/* Find appropriate prime. It generates a number by taking random bytes. - It then tests the number that it's not divisible by any of the small - primes and then it performs Fermat's prime test. I thank Rieks Joosten - (r.joosten@pijnenburg.nl) for such a good help with prime tests. +/* Find appropriate prime. It generates a number by taking random bytes. + It then tests the number that it's not divisible by any of the small + primes and then it performs Fermat's prime test. I thank Rieks Joosten + (r.joosten@pijnenburg.nl) for such a good help with prime tests. If argument verbose is TRUE this will display some status information about the progress of generation. */ -int silc_math_gen_prime(SilcInt *prime, unsigned int bits, int verbose) +SilcBool silc_math_gen_prime(SilcMPInt *prime, SilcUInt32 bits, + SilcBool verbose, SilcRng rng) { unsigned char *numbuf; - unsigned int i, b, k; - unsigned int *spmods; - SilcInt r, base, tmp, tmp2, oprime; + SilcUInt32 i, b, k; + SilcUInt32 *spmods; + SilcMPInt r, base, tmp, tmp2, oprime; + SilcBool valid = FALSE; silc_mp_init(&r); - silc_mp_init_set_ui(&base, 2); + silc_mp_init(&base); silc_mp_init(&tmp); silc_mp_init(&tmp2); silc_mp_init(&oprime); - SILC_LOG_DEBUG(("Generating new prime")); + silc_mp_set_ui(&base, 2); - /* Get random number */ - numbuf = silc_rng_global_get_rn_string((bits / 8)); - if (!numbuf) - return FALSE; - - /* Convert into MP and set the size */ - silc_mp_set_str(prime, numbuf, 16); - silc_mp_mod_2exp(prime, prime, bits); - - /* Empty buffer */ - memset(numbuf, 0, (bits / 8)); - silc_free(numbuf); + SILC_LOG_DEBUG(("Generating new prime")); - /* Number could be even number, so we'll make it odd. */ - silc_mp_set_ui(&tmp, 1); - silc_mp_ior(prime, prime, &tmp); /* OR operator */ + while (valid == FALSE) { + numbuf = silc_malloc((((bits + 7) / 8) + 1) * sizeof(*numbuf)); + if (!numbuf) + return FALSE; + + /* Get random number */ + if (rng) + silc_rng_get_rn_data(rng, (bits / 8), numbuf, (bits / 8)); + else + silc_rng_global_get_rn_data(rng, (bits / 8), numbuf, (bits / 8)); + + /* Convert into MP and set the size */ + silc_mp_bin2mp(numbuf, (bits / 8), prime); + silc_mp_mod_2exp(prime, prime, bits); + + /* Empty buffer */ + memset(numbuf, 0, (bits / 8)); + silc_free(numbuf); + + /* Set highest bit */ + silc_mp_set_ui(&tmp, 1); + silc_mp_mul_2exp(&tmp, &tmp, bits - 1); + silc_mp_or(prime, prime, &tmp); + + /* Number could be even number, so we'll make it odd. */ + silc_mp_set_ui(&tmp, 1); + silc_mp_or(prime, prime, &tmp); + + /* Init modulo table with the prime candidate and the primes + in the primetable. */ + spmods = silc_calloc(1, sizeof(primetable) * sizeof(SilcUInt32)); + for (i = 0; primetable[i] != 0; i++) { + silc_mp_mod_ui(&tmp, prime, primetable[i]); + spmods[i] = silc_mp_get_ui(&tmp); + } - /* Init modulo table with the prime candidate and the primes - in the primetable. */ - spmods = silc_calloc(1, sizeof(primetable) * sizeof(unsigned int)); - for (i = 0; primetable[i] != 0; i++) { - silc_mp_mod_ui(&tmp, prime, primetable[i]); - spmods[i] = silc_mp_get_ui(&tmp); - } + /* k is added by 2, this way we skip all even numbers (prime is odd). */ + silc_mp_set(&oprime, prime); + for (k = 0;; k += 2) { + silc_mp_add_ui(&oprime, prime, k); + + /* See if the prime has a divisor in primetable[]. + * If it has then it's a composite. We add k to the + * original modulo value, k is added by 2 on every roll. + * This way we don't have to re-init the whole table if + * the number is composite. + */ + for (b = 0; b < i; b++) { + silc_mp_set_ui(&tmp2, spmods[b]); + silc_mp_add_ui(&tmp2, &tmp2, k); + silc_mp_mod_ui(&tmp, &tmp2, primetable[b]); + + /* If mod is 0, the number is composite */ + if (silc_mp_cmp_ui(&tmp, 0) == 0) + break; + } + if (b < i) + continue; + + /* Passed the quick test. */ + + /* Does the prime pass the Fermat's prime test. + * r = 2 ^ p mod p, if r == 2, then p is probably a prime. + */ + silc_mp_pow_mod(&r, &base, &oprime, &oprime); + if (silc_mp_cmp_ui(&r, 2) != 0) { + if (verbose) { + printf("."); + fflush(stdout); + } + continue; + } - /* k is added by 2, this way we skip all even numbers (prime is odd). */ - silc_mp_set(&oprime, prime); - for (k = 0;; k += 2) { - silc_mp_add_ui(&oprime, prime, k); - - /* See if the prime has a divisor in primetable[]. - * If it has then it's a composite. We add k to the - * original modulo value, k is added by 2 on every roll. - * This way we don't have to re-init the whole table if - * the number is composite. - */ - for (b = 0; b < i; b++) { - silc_mp_set_ui(&tmp2, spmods[b]); - silc_mp_add_ui(&tmp2, &tmp2, k); - silc_mp_mod_ui(&tmp, &tmp2, primetable[b]); - - /* If mod is 0, the number is composite */ - if (silc_mp_cmp_ui(&tmp, 0) == 0) - break; + /* Passed the Fermat's test. And I don't think + * we have to do more tests. If anyone wants to do more + * tests, MP library has probability of prime test: + * + * if (silc_mp_probab_prime_p(prime, 25)) + * break; found a probable prime + * + * However, this is very slow. + */ + /* XXX: this could be done if some argument, say strict_primes, is + TRUE when we are willing to spend more time on the prime test and + to get, perhaps, better primes. */ + silc_mp_set(prime, &oprime); + break; } - if (b < i) - continue; - - /* Passed the quick test. */ - - /* Does the prime pass the Fermat's prime test. - * r = 2 ^ p mod p, if r == 2, then p is probably a prime. - */ - silc_mp_powm(&r, &base, &oprime, &oprime); - if (silc_mp_cmp_ui(&r, 2) != 0) { - if (verbose) { - printf("."); - fflush(stdout); - } - continue; + + /* Check highest bit */ + silc_mp_div_2exp(&tmp, prime, bits - 1); + if (silc_mp_get_ui(&tmp) == 1) { + valid = TRUE; + break; } - - /* Passed the Fermat's test. And I don't think - * we have to do more tests. If anyone wants to do more - * tests, MP library has probability of prime test: - * - * if (silc_mp_probab_prime_p(prime, 25)) - * break; found a probable prime - * - * However, this is very slow. - */ - /* XXX: this could be done if some argument, say strict_primes, is - TRUE when we are willing to spend more time on the prime test and - to get, perhaps, better primes. */ - silc_mp_set(prime, &oprime); - break; } silc_free(spmods); - silc_mp_clear(&r); - silc_mp_clear(&base); - silc_mp_clear(&tmp); - silc_mp_clear(&tmp2); - silc_mp_clear(&oprime); + silc_mp_uninit(&r); + silc_mp_uninit(&base); + silc_mp_uninit(&tmp); + silc_mp_uninit(&tmp2); + silc_mp_uninit(&oprime); - return TRUE; + return valid; } -/* Performs primality testings for given number. Returns TRUE if the +/* Performs primality testings for given number. Returns TRUE if the number is probably a prime. */ -int silc_math_prime_test(SilcInt *p) +SilcBool silc_math_prime_test(SilcMPInt *p) { - SilcInt r, base, tmp; + SilcMPInt r, base, tmp; int i, ret = 0; - + silc_mp_init(&r); silc_mp_init(&tmp); - silc_mp_init_set_ui(&base, 2); - + silc_mp_init(&base); + silc_mp_set_ui(&base, 2); + SILC_LOG_DEBUG(("Testing probability of prime")); /* See if the number is divisible by any of the small primes in primetable[]. */ for (i = 0; primetable[i] != 0; i++) { silc_mp_mod_ui(&tmp, p, primetable[i]); - + /* If mod is 0, the number is composite */ - if (silc_mp_cmp_ui(&tmp, 0) == 0) - ret = -1; + if (silc_mp_cmp_ui(&tmp, 0) == 0) { + SILC_LOG_DEBUG(("Number is not prime")); + silc_mp_uninit(&r); + silc_mp_uninit(&tmp); + silc_mp_uninit(&base); + return FALSE; + } } - + /* Does the prime pass the Fermat's prime test. * r = 2 ^ p mod p, if r == 2, then p is probably a prime. */ - silc_mp_powm(&r, &base, p, p); + silc_mp_pow_mod(&r, &base, p, p); if (silc_mp_cmp_ui(&r, 2) != 0) ret = -1; - silc_mp_clear(&r); - silc_mp_clear(&tmp); - silc_mp_clear(&base); - - if (ret) + silc_mp_uninit(&r); + silc_mp_uninit(&tmp); + silc_mp_uninit(&base); + + if (ret) { + SILC_LOG_DEBUG(("Number is not prime")); return FALSE; + } /* Number is probably a prime */ return TRUE;