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

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