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

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