git.distorted.org.uk Git - u/mdw/catacomb/blob - strongprime.c

   1 /* -*-c-*-
   2  *
   3  * $Id: strongprime.c,v 1.2 2000/02/12 18:21:03 mdw Exp $
   4  *
   5  * Generate `strong' prime numbers
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: strongprime.c,v $
  33  * Revision 1.2  2000/02/12 18:21:03  mdw
  34  * Overhaul of key management (again).
  35  *
  36  * Revision 1.1  1999/12/22 15:51:22  mdw
  37  * Find `strong' RSA primes using Gordon's algorithm.
  38  *
  39  */
  40
  41 /*----- Header files ------------------------------------------------------*/
  42
  43 #include <mLib/dstr.h>
  44
  45 #include "grand.h"
  46 #include "rand.h"
  47 #include "mp.h"
  48 #include "mpmont.h"
  49 #include "mprand.h"
  50 #include "pgen.h"
  51 #include "pfilt.h"
  52 #include "rabin.h"
  53
  54 /*----- Main code ---------------------------------------------------------*/
  55
  56 /* --- @strongprime_setup@ --- *
  57  *
  58  * Arguments:   @const char *name@ = pointer to name root
  59  *              @mp *d@ = destination for search start point
  60  *              @pfilt *f@ = where to store filter jump context
  61  *              @unsigned nbits@ = number of bits wanted
  62  *              @grand *r@ = random number source
  63  *              @unsigned n@ = number of attempts to make
  64  *              @pgen_proc *event@ = event handler function
  65  *              @void *ectx@ = argument for the event handler
  66  *
  67  * Returns:     A starting point for a `strong' prime search, or zero.
  68  *
  69  * Use:         Sets up for a strong prime search, so that primes with
  70  *              particular properties can be found.  It's probably important
  71  *              to note that the number left in the filter context @f@ is
  72  *              congruent to 2 (mod 4).
  73  */
  74
  75 mp *strongprime_setup(const char *name, mp *d, pfilt *f, unsigned nbits,
  76                       grand *r, unsigned n, pgen_proc *event, void *ectx)
  77 {
  78   mp *s, *t, *q;
  79   dstr dn = DSTR_INIT;
  80
  81   mp *rr = d;
  82   pgen_filterctx c;
  83   pgen_jumpctx j;
  84   rabin rb;
  85
  86   /* --- The bitslop parameter --- *
  87    *
  88    * There's quite a lot of prime searching to be done.  The constant
  89    * @BITSLOP@ is a (low) approximation to the base-2 log of the expected
  90    * number of steps to find a prime number.  Experimentation shows that
  91    * numbers around 10 seem to be good.
  92    */
  93
  94 #define BITSLOP 12
  95
  96   /* --- Choose two primes %$s$% and %$t$% of half the required size --- */
  97
  98   nbits = nbits/2 - BITSLOP;
  99   c.step = 1;
 100
 101   rr = mprand(rr, nbits, r, 1);
 102   DRESET(&dn); dstr_putf(&dn, "%s [s]", name);
 103   if ((s = pgen(dn.buf, MP_NEW, rr, event, ectx, n, pgen_filter, &c,
 104            rabin_iters(nbits), pgen_test, &rb)) == 0)
 105     goto fail_s;
 106   mp_burn(s);
 107
 108   rr = mprand(rr, nbits, r, 1);
 109   DRESET(&dn); dstr_putf(&dn, "%s [t]", name);
 110   if ((t = pgen(dn.buf, MP_NEW, rr, event, ectx, n, pgen_filter, &c,
 111                 rabin_iters(nbits), pgen_test, &rb)) == 0)
 112     goto fail_t;
 113   mp_burn(t);
 114
 115   /* --- Choose a suitable value for %$r = 2it + 1$% for some %$i$% --- */
 116
 117   rr = mp_lsl(rr, t, 1);
 118   pfilt_create(&c.f, rr);
 119   rr = mp_lsl(rr, rr, BITSLOP - 1);
 120   rr = mp_add(rr, rr, MP_ONE);
 121   DRESET(&dn); dstr_putf(&dn, "%s [r]", name);
 122   j.j = &c.f;
 123   nbits += BITSLOP;
 124   q = pgen(dn.buf, MP_NEW, rr, event, ectx, n, pgen_jump, &j,
 125            rabin_iters(nbits), pgen_test, &rb);
 126   pfilt_destroy(&c.f);
 127   if (!q)
 128     goto fail_r;
 129
 130   /* --- Select a suitable starting-point for finding %$p$% --- *
 131    *
 132    * This computes %$p_0 = 2(s^{r - 2} \bmod r)s - 1$%.
 133    */
 134
 135   {
 136     mpmont mm;
 137
 138     mpmont_create(&mm, q);
 139     rr = mp_sub(rr, q, MP_TWO);
 140     rr = mpmont_exp(&mm, rr, s, rr);
 141     mpmont_destroy(&mm);
 142     rr = mp_mul(rr, rr, s);
 143     rr = mp_lsl(rr, rr, 1);
 144     rr = mp_sub(rr, rr, MP_ONE);
 145   }
 146
 147   /* --- Now find %$p = p_0 + 2jrs$% for some %$j$% --- */
 148
 149   {
 150     mp *x;
 151     x = mp_mul(MP_NEW, q, s);
 152     x = mp_lsl(x, x, 1);
 153     pfilt_create(f, x);
 154     x = mp_lsl(x, x, BITSLOP - 1);
 155     rr = mp_add(rr, rr, x);
 156     mp_drop(x);
 157   }
 158
 159   /* --- Return the result --- */
 160
 161 #if 0
 162 fputs("r = ", stdout); mp_writefile(q, stdout, 10); putchar('\n');
 163 fputs("s = ", stdout); mp_writefile(s, stdout, 10); putchar('\n');
 164 fputs("t = ", stdout); mp_writefile(t, stdout, 10); putchar('\n');
 165 #endif
 166
 167   mp_drop(q);
 168   mp_drop(t);
 169   mp_drop(s);
 170   dstr_destroy(&dn);
 171   return (rr);
 172
 173   /* --- Tidy up if something failed --- */
 174
 175 fail_r:
 176   mp_drop(t);
 177 fail_t:
 178   mp_drop(s);
 179 fail_s:
 180   mp_drop(rr);
 181   dstr_destroy(&dn);
 182   return (0);
 183
 184 #undef BITSLOP
 185 }
 186
 187 /* --- @strongprime@ --- *
 188  *
 189  * Arguments:   @const char *name@ = pointer to name root
 190  *              @mp *d@ = destination integer
 191  *              @unsigned nbits@ = number of bits wanted
 192  *              @grand *r@ = random number source
 193  *              @unsigned n@ = number of attempts to make
 194  *              @pgen_proc *event@ = event handler function
 195  *              @void *ectx@ = argument for the event handler
 196  *
 197  * Returns:     A `strong' prime, or zero.
 198  *
 199  * Use:         Finds `strong' primes.  A strong prime %$p$% is such that
 200  *
 201  *                * %$p - 1$% has a large prime factor %$r$%,
 202  *                * %$p + 1$% has a large prime factor %$s$%, and
 203  *                * %$r - 1$% has a large prime factor %$t$%.
 204  *
 205  *              The numbers produced may be slightly larger than requested,
 206  *              by a few bits.
 207  */
 208
 209 mp *strongprime(const char *name, mp *d, unsigned nbits, grand *r,
 210                 unsigned n, pgen_proc *event, void *ectx)
 211 {
 212   pfilt f;
 213   pgen_jumpctx j;
 214   rabin rb;
 215
 216   d = strongprime_setup(name, d, &f, nbits, r, n, event, ectx);
 217   j.j = &f;
 218   d = pgen(name, d, d, event, ectx, n, pgen_jump, &j,
 219            rabin_iters(nbits), pgen_test, &rb);
 220   pfilt_destroy(&f);
 221   return (d);
 222 }
 223
 224 /*----- That's all, folks -------------------------------------------------*/