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

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