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

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