chiark - git - mdw - catacomb/blob - dh-gen.c

   1 /* -*-c-*-
   2  *
   3  * $Id: dh-gen.c,v 1.2 2000/07/29 10:01:58 mdw Exp $
   4  *
   5  * Generate Diffie-Hellman parameters
   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: dh-gen.c,v $
  33  * Revision 1.2  2000/07/29 10:01:58  mdw
  34  * Track change in primitive-element generation.
  35  *
  36  * Revision 1.1  2000/02/12 18:21:02  mdw
  37  * Overhaul of key management (again).
  38  *
  39  */
  40
  41 /*----- Header files ------------------------------------------------------*/
  42
  43 #include "dh.h"
  44 #include "grand.h"
  45 #include "mp.h"
  46 #include "mpmont.h"
  47 #include "mprand.h"
  48 #include "pfilt.h"
  49 #include "pgen.h"
  50 #include "prim.h"
  51 #include "rabin.h"
  52
  53 /*----- Main code ---------------------------------------------------------*/
  54
  55 /* --- @dh_gen@ --- *
  56  *
  57  * Arguments:   @dh_param *dp@ = pointer to output parameter block
  58  *              @unsigned ql@ = length of %$q$% in bits, or zero
  59  *              @unsigned pl@ = length of %$p$% in bits
  60  *              @unsigned steps@ = number of steps to go
  61  *              @grand *r@ = random number source
  62  *              @pgen_proc *event@ = event handler function
  63  *              @void *ectx@ = argument for the event handler
  64  *
  65  * Returns:     @PGEN_DONE@ if it worked, @PGEN_ABORT@ if it didn't.
  66  *
  67  * Use:         Generates Diffie-Hellman parameters.
  68  *
  69  *              The parameters are a prime %$q$%, relatively small, and a
  70  *              large prime %$p = kq + 1$% for some %$k$%, together with a
  71  *              generator %$g$% of the cyclic subgroup of order %$q$%.  These
  72  *              are actually the same as the DSA parameter set, but the
  73  *              generation algorithm is different.  Also, if @ql@ is zero,
  74  *              this algorithm forces %$k = 2$%, and chooses %$g = 4$%.  Make
  75  *              sure you have something interesting to do if you choose this
  76  *              option.
  77  */
  78
  79 int dh_gen(dh_param *dp, unsigned ql, unsigned pl, unsigned steps, grand *r,
  80            pgen_proc *event, void *ectx)
  81 {
  82   /* --- If @ql@ is zero, do the time consuming safe-prime thing --- */
  83
  84   if (!ql) {
  85     pgen_safetestctx c;
  86
  87     mp *m = mprand(MP_NEW, pl, r, 3);
  88     dp->p = pgen("p", MP_NEW, m, event, ectx, steps, pgen_safestep, &c.c,
  89                  rabin_iters(pl), pgen_safetest, &c);
  90     mp_drop(m);
  91     if (!dp->p)
  92       return (PGEN_ABORT);
  93     dp->q = mp_lsr(MP_NEW, dp->p, 1);
  94     dp->g = MP_FOUR;
  95     return (PGEN_DONE);
  96   }
  97
  98   /* --- Otherwise the job is much simpler --- *
  99    *
 100    * But doesn't look it...
 101    */
 102
 103   else {
 104     pgen_filterctx c;
 105     pgen_jumpctx j;
 106     rabin rb;
 107     prim_ctx p;
 108     int i;
 109     mp *m = MP_NEW;
 110     mp *x, *y;
 111
 112     /* --- Generate @q@ first --- */
 113
 114     c.step = 2;
 115     m = mprand(MP_NEW, ql, r, 1);
 116     dp->q = pgen("q", MP_NEW, m, event, ectx, steps, pgen_filter, &c,
 117                  rabin_iters(ql), pgen_test, &rb);
 118     if (!dp->q)
 119       goto fail_q;
 120
 121     /* --- Now pick a suitable @p@ --- */
 122
 123     m = mp_lsl(m, dp->q, 1);
 124     x = mprand(MP_NEW, pl, r, 0);
 125     y = MP_NEW; mp_div(0, &y, x, m);
 126     x = mp_sub(x, x, y);
 127     x = mp_add(x, x, MP_ONE);
 128     mp_drop(y);
 129     pfilt_create(&c.f, m);
 130     j.j = &c.f;
 131     dp->p = pgen("p", MP_NEW, x, event, ectx, steps, pgen_jump, &j,
 132                  rabin_iters(pl), pgen_test, &rb);
 133     pfilt_destroy(&c.f);
 134     mp_drop(x);
 135     if (!dp->p)
 136       goto fail_p;
 137
 138     /* --- And finally a suitable @g@ --- */
 139
 140     mpmont_create(&p.mm, dp->p);
 141     mp_div(&m, 0, dp->p, dp->q);
 142     i = 0;
 143     p.exp = m;
 144     p.n = 0;
 145     dp->g = pgen("g", MP_NEW, MP_NEW, event, ectx, 0, prim_step, &i,
 146                  1, prim_test, &p);
 147     mpmont_destroy(&p.mm);
 148     if (!dp->g)
 149       goto fail_g;
 150     mp_drop(m);
 151     return (PGEN_DONE);
 152
 153     /* --- Tidy up --- */
 154
 155   fail_g:
 156     mp_drop(dp->q);
 157   fail_q:
 158     mp_drop(dp->p);
 159   fail_p:
 160     mp_drop(m);
 161     return (PGEN_ABORT);
 162   }
 163 }
 164
 165 /*----- That's all, folks -------------------------------------------------*/