X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/a30942cc806b11f8ddca146c16a46b69a4b6ef52..097fb6f2f97575ce17738b4afb3216e9492de2b4:/strongprime.c diff --git a/strongprime.c b/strongprime.c index 4a7ddb8..866533d 100644 --- a/strongprime.c +++ b/strongprime.c @@ -1,13 +1,13 @@ /* -*-c-*- * - * $Id: strongprime.c,v 1.1 1999/12/22 15:51:22 mdw Exp $ + * $Id: strongprime.c,v 1.5 2004/04/08 01:36:15 mdw Exp $ * * Generate `strong' prime numbers * * (c) 1999 Straylight/Edgeware */ -/*----- Licensing notice --------------------------------------------------* +/*----- Licensing notice --------------------------------------------------* * * This file is part of Catacomb. * @@ -15,26 +15,18 @@ * it under the terms of the GNU Library General Public License as * published by the Free Software Foundation; either version 2 of the * License, or (at your option) any later version. - * + * * Catacomb 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 Library General Public License for more details. - * + * * You should have received a copy of the GNU Library General Public * License along with Catacomb; if not, write to the Free * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, * MA 02111-1307, USA. */ -/*----- Revision history --------------------------------------------------* - * - * $Log: strongprime.c,v $ - * Revision 1.1 1999/12/22 15:51:22 mdw - * Find `strong' RSA primes using Gordon's algorithm. - * - */ - /*----- Header files ------------------------------------------------------*/ #include @@ -50,37 +42,34 @@ /*----- Main code ---------------------------------------------------------*/ -/* --- @strongprime@ --- * +/* --- @strongprime_setup@ --- * * * Arguments: @const char *name@ = pointer to name root - * @mp *d@ = destination integer + * @mp *d@ = destination for search start point + * @pfilt *f@ = where to store filter jump context * @unsigned nbits@ = number of bits wanted * @grand *r@ = random number source * @unsigned n@ = number of attempts to make * @pgen_proc *event@ = event handler function * @void *ectx@ = argument for the event handler * - * Returns: A `strong' prime, or zero. - * - * Use: Finds `strong' primes. A strong prime %$p$% is such that - * - * * %$p - 1$% has a large prime factor %$r$%, - * * %$p + 1$% has a large prime factor %$s$%, and - * * %$r - 1$% has a large prime factor %$t$%. + * Returns: A starting point for a `strong' prime search, or zero. * - * The numbers produced may be slightly larger than requested, - * by a few bits. + * Use: Sets up for a strong prime search, so that primes with + * particular properties can be found. It's probably important + * to note that the number left in the filter context @f@ is + * congruent to 2 (mod 4). */ -mp *strongprime(const char *name, mp *d, unsigned nbits, grand *r, - unsigned n, pgen_proc *event, void *ectx) +mp *strongprime_setup(const char *name, mp *d, pfilt *f, unsigned nbits, + grand *r, unsigned n, pgen_proc *event, void *ectx) { - mp *s, *t, *q, *p = 0; + mp *s, *t, *q; dstr dn = DSTR_INIT; - mp *rr = MP_NEW; + mp *rr = d; pgen_filterctx c; - pgen_jumpctx cj; + pgen_jumpctx j; rabin rb; /* --- The bitslop parameter --- * @@ -91,26 +80,25 @@ mp *strongprime(const char *name, mp *d, unsigned nbits, grand *r, * numbers around 10 seem to be good. */ -#define BITSLOP 10 +#define BITSLOP 12 /* --- Choose two primes %$s$% and %$t$% of half the required size --- */ + assert(((void)"nbits too small in strongprime_setup", nbits/2 > BITSLOP)); nbits = nbits/2 - BITSLOP; c.step = 1; rr = mprand(rr, nbits, r, 1); DRESET(&dn); dstr_putf(&dn, "%s [s]", name); - if ((s = pgen(dn.buf, MP_NEW, rr, event, ectx, n, pgen_filter, &c, - rabin_iters(nbits), pgen_test, &rb)) == 0) + if ((s = pgen(dn.buf, MP_NEWSEC, rr, event, ectx, n, pgen_filter, &c, + rabin_iters(nbits), pgen_test, &rb)) == 0) goto fail_s; - mp_burn(s); rr = mprand(rr, nbits, r, 1); DRESET(&dn); dstr_putf(&dn, "%s [t]", name); - if ((t = pgen(dn.buf, MP_NEW, rr, event, ectx, n, pgen_filter, &c, + if ((t = pgen(dn.buf, MP_NEWSEC, rr, event, ectx, n, pgen_filter, &c, rabin_iters(nbits), pgen_test, &rb)) == 0) goto fail_t; - mp_burn(t); /* --- Choose a suitable value for %$r = 2it + 1$% for some %$i$% --- */ @@ -119,12 +107,13 @@ mp *strongprime(const char *name, mp *d, unsigned nbits, grand *r, rr = mp_lsl(rr, rr, BITSLOP - 1); rr = mp_add(rr, rr, MP_ONE); DRESET(&dn); dstr_putf(&dn, "%s [r]", name); - cj.j = &c.f; + j.j = &c.f; nbits += BITSLOP; - if ((q = pgen(dn.buf, MP_NEW, rr, event, ectx, n, pgen_jump, &cj, - rabin_iters(nbits), pgen_test, &rb)) == 0) - goto fail_r; + q = pgen(dn.buf, MP_NEW, rr, event, ectx, n, pgen_jump, &j, + rabin_iters(nbits), pgen_test, &rb); pfilt_destroy(&c.f); + if (!q) + goto fail_r; /* --- Select a suitable starting-point for finding %$p$% --- * * @@ -149,32 +138,69 @@ mp *strongprime(const char *name, mp *d, unsigned nbits, grand *r, mp *x; x = mp_mul(MP_NEW, q, s); x = mp_lsl(x, x, 1); - pfilt_create(&c.f, x); + pfilt_create(f, x); x = mp_lsl(x, x, BITSLOP - 1); rr = mp_add(rr, rr, x); mp_drop(x); } - if ((p = pgen(name, d, rr, event, ectx, n, pgen_jump, &cj, - rabin_iters(nbits * 2), pgen_test, &rb)) == 0) - goto fail_p; + /* --- Return the result --- */ - /* --- Tidy up because we've finished --- */ - -fail_p: mp_drop(q); + mp_drop(t); + mp_drop(s); + dstr_destroy(&dn); + return (rr); + + /* --- Tidy up if something failed --- */ + fail_r: - pfilt_destroy(&c.f); mp_drop(t); fail_t: mp_drop(s); fail_s: mp_drop(rr); dstr_destroy(&dn); - - return (p); + return (0); #undef BITSLOP } +/* --- @strongprime@ --- * + * + * Arguments: @const char *name@ = pointer to name root + * @mp *d@ = destination integer + * @unsigned nbits@ = number of bits wanted + * @grand *r@ = random number source + * @unsigned n@ = number of attempts to make + * @pgen_proc *event@ = event handler function + * @void *ectx@ = argument for the event handler + * + * Returns: A `strong' prime, or zero. + * + * Use: Finds `strong' primes. A strong prime %$p$% is such that + * + * * %$p - 1$% has a large prime factor %$r$%, + * * %$p + 1$% has a large prime factor %$s$%, and + * * %$r - 1$% has a large prime factor %$t$%. + * + * The numbers produced may be slightly larger than requested, + * by a few bits. + */ + +mp *strongprime(const char *name, mp *d, unsigned nbits, grand *r, + unsigned n, pgen_proc *event, void *ectx) +{ + pfilt f; + pgen_jumpctx j; + rabin rb; + + d = strongprime_setup(name, d, &f, nbits, r, n, event, ectx); + j.j = &f; + d = pgen(name, d, d, event, ectx, n, pgen_jump, &j, + rabin_iters(nbits), pgen_test, &rb); + pfilt_destroy(&f); + return (d); +} + /*----- That's all, folks -------------------------------------------------*/