git.distorted.org.uk Git - u/mdw/catacomb/blob - dh-limlee.c

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