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

   1 /* -*-c-*-
   2  *
   3  * Generate Diffie-Hellman parameters from Lim-Lee primes
   4  *
   5  * (c) 2000 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Header files ------------------------------------------------------*/
  29
  30 #include "dh.h"
  31 #include "limlee.h"
  32 #include "mpmont.h"
  33 #include "prim.h"
  34
  35 /*----- Main code ---------------------------------------------------------*/
  36
  37 /* --- @dh_limlee@ --- *
  38  *
  39  * Arguments:   @dh_param *dp@ = pointer to output parameter block
  40  *              @unsigned ql@ = length of smallest factor of %$(p - 1)/2$%
  41  *              @unsigned pl@ = length of %$p$% in bits
  42  *              @unsigned flags@ = other generation flags
  43  *              @unsigned steps@ = number of steps to go
  44  *              @grand *r@ = random number source
  45  *              @pgen_proc *oev@ = outer event handler function
  46  *              @void *oec@ = argument for the outer event handler
  47  *              @pgen_proc *iev@ = inner event handler function
  48  *              @void *iec@ = argument for the inner event handler
  49  *              @size_t *nf@, @mp ***f@ = output array for factors
  50  *
  51  * Returns:     @PGEN_DONE@ if it worked, @PGEN_ABORT@ if it didn't.
  52  *
  53  * Use:         Generates Diffie-Hellman parameters based on a Lim-Lee prime.
  54  *
  55  *              The modulus is a large prime %$p = 2 \prod q_i + 1$%, @pl@
  56  *              bits long, where the %$q_i$% are smaller primes each at least
  57  *              @ql@ bits long.  It is safe to set @nf@ and @f@ to zero if
  58  *              you're not interested in the factor values.
  59  *
  60  *              The returned %$g$% generates a subgroup of order %$q_0$% (the
  61  *              first factor, returned as @f[0]@), if the flag @DH_SUBGROUP@
  62  *              is set on entry; otherwise %$g$% will have order
  63  *              %$(p - 1)/2$%.
  64  */
  65
  66 int dh_limlee(dh_param *dp, unsigned ql, unsigned pl,
  67               unsigned flags, unsigned steps, grand *r,
  68               pgen_proc *oev, void *oec, pgen_proc *iev,
  69               void *iec, size_t *nf, mp ***f)
  70 {
  71   mp **ff;
  72   size_t nff;
  73   prim_ctx pc;
  74   size_t i;
  75   int j;
  76   mp *pp;
  77
  78   /* --- Generate the Lim-Lee prime --- */
  79
  80   if ((dp->p = limlee("p", MP_NEW, MP_NEW, ql, pl,
  81                       r, steps, oev, oec, iev, iec, &nff, &ff)) == 0)
  82     return (PGEN_ABORT);
  83
  84   /* --- Now find a primitive element --- */
  85
  86   mpmont_create(&pc.mm, dp->p);
  87   pp = mp_sub(MP_NEW, dp->p, MP_ONE);
  88   if (flags & DH_SUBGROUP) {
  89     dp->q = mp_copy(ff[0]);
  90     pc.exp = MP_NEW;
  91     mp_div(&pc.exp, 0, pp, dp->q);
  92     pc.n = 0;
  93     pc.f = 0;
  94   } else {
  95     dp->q = mp_lsr(MP_NEW, dp->p, 1);
  96     pc.exp = MP_TWO;
  97     pc.n = nff;
  98     pc.f = xmalloc(nff * sizeof(mp *));
  99     for (i = 0; i < nff; i++) {
 100       pc.f[i] = MP_NEW;
 101       mp_div(&pc.f[i], 0, pp, ff[i]);
 102     }
 103   }
 104
 105   j = 0;
 106   dp->g = pgen("g", MP_NEW, MP_NEW, oev, oec,
 107                0, prim_step, &j, 1, prim_test, &pc);
 108
 109   mp_drop(pp);
 110   if (pc.f) {
 111     for (i = 0; i < pc.n; i++)
 112       mp_drop(pc.f[i]);
 113     xfree(pc.f);
 114   }
 115   mpmont_destroy(&pc.mm);
 116
 117   /* --- Do something sensible with the list of primes --- */
 118
 119   if (dp->g && f) {
 120     *f = ff;
 121     *nf = nff;
 122   } else {
 123     for (i = 0; i < nff; i++)
 124       mp_drop(ff[i]);
 125     xfree(ff);
 126   }
 127
 128   /* --- Tidy up and return --- */
 129
 130   if (!dp->g) {
 131     mp_drop(dp->p);
 132     mp_drop(dp->q);
 133     return (PGEN_ABORT);
 134   }
 135   return (PGEN_DONE);
 136 }
 137
 138 /*----- That's all, folks -------------------------------------------------*/