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

   1 /* -*-c-*-
   2  *
   3  * $Id: dh-limlee.c,v 1.3 2004/04/08 01:36:15 mdw Exp $
   4  *
   5  * Generate Diffie-Hellman parameters from Lim-Lee primes
   6  *
   7  * (c) 2000 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 "dh.h"
  33 #include "limlee.h"
  34 #include "mpmont.h"
  35 #include "prim.h"
  36
  37 /*----- Main code ---------------------------------------------------------*/
  38
  39 /* --- @dh_limlee@ --- *
  40  *
  41  * Arguments:   @dh_param *dp@ = pointer to output parameter block
  42  *              @unsigned ql@ = length of smallest factor of %$(p - 1)/2$%
  43  *              @unsigned pl@ = length of %$p$% in bits
  44  *              @unsigned flags@ = other generation flags
  45  *              @unsigned steps@ = number of steps to go
  46  *              @grand *r@ = random number source
  47  *              @pgen_proc *oev@ = outer event handler function
  48  *              @void *oec@ = argument for the outer event handler
  49  *              @pgen_proc *iev@ = inner event handler function
  50  *              @void *iec@ = argument for the inner event handler
  51  *              @size_t *nf@, @mp ***f@ = output array for factors
  52  *
  53  * Returns:     @PGEN_DONE@ if it worked, @PGEN_ABORT@ if it didn't.
  54  *
  55  * Use:         Generates Diffie-Hellman parameters based on a Lim-Lee prime.
  56  *
  57  *              The modulus is a large prime %$p = 2 \prod q_i + 1$%, @pl@
  58  *              bits long, where the %$q_i$% are smaller primes each at least
  59  *              @ql@ bits long.  It is safe to set @nf@ and @f@ to zero if
  60  *              you're not interested in the factor values.
  61  *
  62  *              The returned %$g$% generates a subgroup of order %$q_0$% (the
  63  *              first factor, returned as @f[0]@), if the flag @DH_SUBGROUP@
  64  *              is set on entry; otherwise %$g$% will have order
  65  *              %$(p - 1)/2$%.
  66  */
  67
  68 int dh_limlee(dh_param *dp, unsigned ql, unsigned pl,
  69               unsigned flags, unsigned steps, grand *r,
  70               pgen_proc *oev, void *oec, pgen_proc *iev,
  71               void *iec, size_t *nf, mp ***f)
  72 {
  73   mp **ff;
  74   size_t nff;
  75   prim_ctx pc;
  76   size_t i;
  77   int j;
  78   mp *pp;
  79
  80   /* --- Generate the Lim-Lee prime --- */
  81
  82   if ((dp->p = limlee("p", MP_NEW, MP_NEW, ql, pl,
  83                       r, steps, oev, oec, iev, iec, &nff, &ff)) == 0)
  84     return (PGEN_ABORT);
  85
  86   /* --- Now find a primitive element --- */
  87
  88   mpmont_create(&pc.mm, dp->p);
  89   pp = mp_sub(MP_NEW, dp->p, MP_ONE);
  90   if (flags & DH_SUBGROUP) {
  91     dp->q = mp_copy(ff[0]);
  92     pc.exp = MP_NEW;
  93     mp_div(&pc.exp, 0, pp, dp->q);
  94     pc.n = 0;
  95     pc.f = 0;
  96   } else {
  97     dp->q = mp_lsr(MP_NEW, dp->p, 1);
  98     pc.exp = MP_TWO;
  99     pc.n = nff;
 100     pc.f = xmalloc(nff * sizeof(mp *));
 101     for (i = 0; i < nff; i++) {
 102       pc.f[i] = MP_NEW;
 103       mp_div(&pc.f[i], 0, pp, ff[i]);
 104     }
 105   }
 106
 107   j = 0;
 108   dp->g = pgen("g", MP_NEW, MP_NEW, oev, oec,
 109                0, prim_step, &j, 1, prim_test, &pc);
 110
 111   mp_drop(pp);
 112   if (pc.f) {
 113     for (i = 0; i < pc.n; i++)
 114       mp_drop(pc.f[i]);
 115     xfree(pc.f);
 116   }
 117   mpmont_destroy(&pc.mm);
 118
 119   /* --- Do something sensible with the list of primes --- */
 120
 121   if (dp->g && f) {
 122     *f = ff;
 123     *nf = nff;
 124   } else {
 125     for (i = 0; i < nff; i++)
 126       mp_drop(ff[i]);
 127     xfree(ff);
 128   }
 129
 130   /* --- Tidy up and return --- */
 131
 132   if (!dp->g) {
 133     mp_drop(dp->p);
 134     mp_drop(dp->q);
 135     return (PGEN_ABORT);
 136   }
 137   return (PGEN_DONE);
 138 }
 139
 140 /*----- That's all, folks -------------------------------------------------*/