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

   1 /* -*-c-*-
   2  *
   3  * $Id: dh-prime.c,v 1.2 1999/12/10 23:18:38 mdw Exp $
   4  *
   5  * Generate (safe) Diffie-Hellman primes
   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 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: dh-prime.c,v $
  33  * Revision 1.2  1999/12/10 23:18:38  mdw
  34  * Change interface for suggested destinations.
  35  *
  36  * Revision 1.1  1999/11/20 22:24:44  mdw
  37  * Add Diffie-Hellman support.
  38  *
  39  */
  40
  41 /*----- Header files ------------------------------------------------------*/
  42
  43 #include <stdio.h>
  44 #include <stdlib.h>
  45 #include <string.h>
  46
  47 #include "dh.h"
  48 #include "fibrand.h"
  49 #include "mp.h"
  50 #include "mprand.h"
  51 #include "pgen.h"
  52 #include "rabin.h"
  53
  54 /*----- Main code ---------------------------------------------------------*/
  55
  56 /* --- @dh_prime@ --- *
  57  *
  58  * Arguments:   @mp *s@ = start point for search (must be odd)
  59  *              @size_t n@ = number of concerted attempts to make, or zero
  60  *              @void (*proc)(int ev, void *p)@ = event handler
  61  *              @void *p@ = argument for event handler
  62  *
  63  * Returns:     A prime number %$p$% where %$p = 2q + 1$% for prime %$q$%.
  64  *
  65  * Use:         Finds a safe prime by sequential search from a given starting
  66  *              point.  If it fails, a null pointer is returned.
  67  *
  68  *              The event handler is informed of the progress of the search.
  69  *              It may abort the search at any time by returning a nonzero
  70  *              value.
  71  */
  72
  73 mp *dh_prime(mp *s, size_t n,
  74              int (*proc)(int /*ev*/, void */*p*/), void *arg)
  75 {
  76   pgen pq, pp;
  77   int rc_q, rc_p;
  78   grand *gr = fibrand_create(0);
  79   mp *b = MP_NEW;
  80   size_t sz = mp_bits(s);
  81
  82   /* --- Initialize prime generators --- */
  83
  84   rc_q = pgen_create(&pq, s);
  85   rc_p = pgen_muladd(&pp, &pq, 2, 1);
  86
  87   /* --- Now step along until something crops up --- */
  88
  89   for (;;) {
  90     rabin rq, rp;
  91     int i;
  92
  93     /* --- Don't do expensive testing unless necessary --- */
  94
  95     if (rc_q == PGEN_PRIME && rc_p == PGEN_PRIME)
  96       break;
  97     if (rc_q == PGEN_COMPOSITE || rc_p == PGEN_COMPOSITE)
  98       goto next;
  99
 100     /* --- Initialize Rabin-Miller contexts --- */
 101
 102     if (rc_q == PGEN_MAYBE)
 103       rabin_create(&rq, pq.m);
 104     if (rc_p == PGEN_MAYBE)
 105       rabin_create(&rp, pp.m);
 106
 107     /* --- Now run tests on each in turn --- *
 108      *
 109      * On the sorts of modulus sizes which work well in discrete log
 110      * problems, five tests should be sufficient.
 111      */
 112
 113     for (i = 0; i < 5; i++) {
 114       b = mprand(b, sz, gr, 1);
 115       if (rc_q == PGEN_MAYBE &&
 116           (rc_q = rabin_test(&rq, b)) == PGEN_COMPOSITE)
 117         break;
 118       if (rc_p == PGEN_MAYBE &&
 119           (rc_p = rabin_test(&rp, b)) == PGEN_COMPOSITE)
 120         break;
 121       if (proc && proc(DHEV_PASS, arg))
 122         break;
 123     }
 124     if (rc_q != PGEN_PRIME)
 125       rabin_destroy(&rq);
 126     if (rc_p != PGEN_PRIME)
 127       rabin_destroy(&rp);
 128
 129     /* --- If the tests passed, accept the numbers --- */
 130
 131     if (i >= 5)
 132       break;
 133     if (proc && proc(DHEV_FAIL, arg))
 134       goto fail;
 135     if (n) {
 136       n--;
 137       if (!n)
 138         goto fail;
 139     }
 140
 141     /* --- Step the contexts on --- */
 142
 143   next:
 144     rc_q = pgen_step(&pq, 2);
 145     rc_p = pgen_step(&pp, 4);
 146   }
 147
 148   /* --- Return a result --- */
 149
 150   {
 151     mp *p = MP_COPY(pp.m);
 152     pgen_destroy(&pq);
 153     pgen_destroy(&pp);
 154     mp_drop(b);
 155     gr->ops->destroy(gr);
 156     return (p);
 157   }
 158
 159   /* --- Failure --- */
 160
 161 fail:
 162   pgen_destroy(&pq);
 163   pgen_destroy(&pp);
 164   mp_drop(b);
 165   gr->ops->destroy(gr);
 166   return (0);
 167 }
 168
 169 /*----- That's all, folks -------------------------------------------------*/