/*
silcprimegen.c
-
- Author: Pekka Riikonen <priikone@poseidon.pspt.fi>
- Copyright (C) 1997 - 2000 Pekka Riikonen
+ Author: Pekka Riikonen <priikone@silcnet.org>
+
+ 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
GNU General Public License for more details.
*/
+/* Created: Mon Dec 8 16:35:37 GMT+0200 1997 */
+/* $Id$ */
+
+#include "silc.h"
+
/*
- * Created: Mon Dec 8 16:35:37 GMT+0200 1997
- */
-/*
- * $Id$
- * $Log$
- * Revision 1.1 2000/06/27 11:36:51 priikone
- * Initial revision
- *
- *
- */
-
-#include "silcincludes.h"
-
-/* XXX This must be temporary solution!! yucky! */
-/* Global random pool used for all prime generation. All primes generated
- in SILC uses this same pool. Before primes can be generated one must
- call silc_math_primegen_init. */
-static SilcRng primegen_rng;
-
-/*
- 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):
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,
};
-/* 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;
-
- /* XXX */
- assert(primegen_rng != NULL);
+ 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"));
-
- /* Get random number */
- numbuf = silc_rng_get_rn_string(primegen_rng, (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);
+ silc_mp_set_ui(&base, 2);
- /* 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_malloc(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;
}
-
-/* XXX This must temporary solution!! */
-/* Initializes the random pool used to generated primes */
-
-void silc_math_primegen_init()
-{
- SILC_LOG_DEBUG(("Start"));
-
- if (primegen_rng == NULL) {
- primegen_rng = silc_rng_alloc();
- silc_rng_init(primegen_rng);
- }
-}
-
-/* XXX This must temporary solution!! */
-/* Uninitializes random pool */
-
-void silc_math_primegen_uninit()
-{
- silc_rng_free(primegen_rng);
-}