From: mdw Date: Sat, 20 Nov 1999 22:24:53 +0000 (+0000) Subject: Add Diffie-Hellman support. X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/commitdiff_plain/44c240eef3706e9b1a0451fb4d584ba7caea0cdf Add Diffie-Hellman support. --- diff --git a/Makefile.m4 b/Makefile.m4 index cb65285..a8385d1 100644 --- a/Makefile.m4 +++ b/Makefile.m4 @@ -1,6 +1,6 @@ ## -*-makefile-*- ## -## $Id: Makefile.m4,v 1.10 1999/11/19 19:28:24 mdw Exp $ +## $Id: Makefile.m4,v 1.11 1999/11/20 22:24:53 mdw Exp $ ## ## Makefile for Catacomb ## @@ -29,8 +29,11 @@ ##----- Revision history ---------------------------------------------------- ## ## $Log: Makefile.m4,v $ -## Revision 1.10 1999/11/19 19:28:24 mdw -## Add DSA files and tests. +## Revision 1.11 1999/11/20 22:24:53 mdw +## Add Diffie-Hellman support. +## +## Revision 1.11 1999/11/20 22:24:53 mdw +## Add Diffie-Hellman support. ## ## Revision 1.10 1999/11/19 19:28:24 mdw ## Add DSA files and tests. @@ -137,7 +140,7 @@ pkginclude_HEADERS = \ blkc.h hash.h \ rc4.h \ rand.h noise.h \ - dsa.h \ + key.h \ mpx.h mpw.h mpscan.h mparena.h mp.h mptext.h mpmont.h \ ptab.h pgen.h rabin.h \ dsa.h dh.h \ @@ -154,6 +157,7 @@ libcatacomb_la_SOURCES = \ mp-misc.c mp-mem.c mp-const.c mp-io.c mp-arith.c mp-test.c \ mp-gcd.c \ mptext.c mptext-file.c mptext-string.c mptext-dstr.c \ + mpmont.c mpmont-mexp.c \ ptab.c pgen.c rabin.c \ dsa-sign.c dsa-verify.c dsa-gen.c \ dh-prime.c \ diff --git a/dh-prime.c b/dh-prime.c new file mode 100644 index 0000000..81dc423 --- /dev/null +++ b/dh-prime.c @@ -0,0 +1,160 @@ +/* -*-c-*- + * + * $Id: dh-prime.c,v 1.1 1999/11/20 22:24:44 mdw Exp $ + * + * Generate (safe) Diffie-Hellman primes + * + * (c) 1999 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: dh-prime.c,v $ + * Revision 1.1 1999/11/20 22:24:44 mdw + * Add Diffie-Hellman support. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include +#include +#include + +#include "dh.h" +#include "mp.h" +#include "pgen.h" +#include "rabin.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @dh_prime@ --- * + * + * Arguments: @mp *s@ = start point for search (must be odd) + * @size_t n@ = number of concerted attempts to make, or zero + * @void (*proc)(int ev, void *p)@ = event handler + * @void *p@ = argument for event handler + * + * Returns: A prime number %$p$% where %$p = 2q + 1$% for prime %$q$%. + * + * Use: Finds a safe prime by sequential search from a given starting + * point. If it fails, a null pointer is returned. + * + * The event handler is informed of the progress of the search. + * It may abort the search at any time by returning a nonzero + * value. + */ + +mp *dh_prime(mp *s, size_t n, + int (*proc)(int /*ev*/, void */*p*/), void *arg) +{ + pgen pq, pp; + int rc_q, rc_p; + mpw bw; + mp b; + + /* --- Initialize prime generators --- */ + + rc_q = pgen_create(&pq, s); + rc_p = pgen_muladd(&pp, &pq, 2, 1); + mp_build(&b, &bw, &bw + 1); + + /* --- Now step along until something crops up --- */ + + for (;;) { + rabin rq, rp; + int i; + + /* --- Don't do expensive testing unless necessary --- */ + + if (rc_q == PGEN_PRIME && rc_p == PGEN_PRIME) + break; + if (rc_q == PGEN_COMPOSITE || rc_p == PGEN_COMPOSITE) + goto next; + + /* --- Initialize Rabin-Miller contexts --- */ + + if (rc_q == PGEN_MAYBE) + rabin_create(&rq, pq.m); + if (rc_p == PGEN_MAYBE) + rabin_create(&rp, pp.m); + + /* --- Now run tests on each in turn --- * + * + * On the sorts of modulus sizes which work well in discrete log + * problems, five tests should be sufficient. + */ + + for (i = 0; i < 5; i++) { + bw = ptab[i]; + if (rc_q == PGEN_MAYBE && + (rc_q = rabin_test(&rq, &b)) == PGEN_COMPOSITE) + break; + if (rc_p == PGEN_MAYBE && + (rc_p = rabin_test(&rp, &b)) == PGEN_COMPOSITE) + break; + if (proc && proc(DHEV_PASS, arg)) + break; + } + if (rc_q != PGEN_PRIME) + rabin_destroy(&rq); + if (rc_p != PGEN_PRIME) + rabin_destroy(&rp); + + /* --- If the tests passed, accept the numbers --- */ + + if (i >= 5) + break; + if (proc && proc(DHEV_FAIL, arg)) + goto fail; + if (n) { + n--; + if (!n) + goto fail; + } + + /* --- Step the contexts on --- */ + + next: + rc_q = pgen_step(&pq, 2); + rc_p = pgen_step(&pp, 4); + } + + /* --- Return a result --- */ + + { + mp *p = MP_COPY(pp.m); + pgen_destroy(&pq); + pgen_destroy(&pp); + return (p); + } + + /* --- Failure --- */ + +fail: + pgen_destroy(&pq); + pgen_destroy(&pp); + return (0); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/dh.h b/dh.h new file mode 100644 index 0000000..330c258 --- /dev/null +++ b/dh.h @@ -0,0 +1,87 @@ +/* -*-c-*- + * + * $Id: dh.h,v 1.1 1999/11/20 22:24:44 mdw Exp $ + * + * [Diffie-Hellman key negotiation * + * (c) 1999 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: dh.h,v $ + * Revision 1.1 1999/11/20 22:24:44 mdw + * Add Diffie-Hellman support. + * + */ + +#ifndef DH_H +#define DH_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#ifndef MP_H +# include "mp.h" +#endif + +/*----- Event codes -------------------------------------------------------*/ + +enum { + DHEV_OK, + + DHEV_FAIL, + DHEV_PASS +}; + +/*----- Functions provided ------------------------------------------------*/ + +/* --- @dh_prime@ --- * + * + * Arguments: @mp *s@ = start point for search (must be odd) + * @size_t n@ = number of concerted attempts to make, or zero + * @void (*proc)(int ev, void *p)@ = event handler + * @void *p@ = argument for event handler + * + * Returns: A prime number %$p$% where %$p = 2q + 1$% for prime %$q$%. + * + * Use: Finds a safe prime by sequential search from a given starting + * point. If it fails, a null pointer is returned. + * + * The event handler is informed of the progress of the search. + * It may abort the search at any time by returning a nonzero + * value. + */ + +extern mp *dh_prime(mp */*s*/, size_t /*n*/, + int (*proc)(int /*ev*/, void */*p*/), void */*p*/); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif