3 * $Id: dh-prime.c,v 1.1 1999/11/20 22:24:44 mdw Exp $
5 * Generate (safe) Diffie-Hellman primes
7 * (c) 1999 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
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.
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.
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,
30 /*----- Revision history --------------------------------------------------*
32 * $Log: dh-prime.c,v $
33 * Revision 1.1 1999/11/20 22:24:44 mdw
34 * Add Diffie-Hellman support.
38 /*----- Header files ------------------------------------------------------*/
49 /*----- Main code ---------------------------------------------------------*/
51 /* --- @dh_prime@ --- *
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
58 * Returns: A prime number %$p$% where %$p = 2q + 1$% for prime %$q$%.
60 * Use: Finds a safe prime by sequential search from a given starting
61 * point. If it fails, a null pointer is returned.
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
68 mp
*dh_prime(mp
*s
, size_t n
,
69 int (*proc
)(int /*ev*/, void */
*p*/
), void *arg
)
76 /* --- Initialize prime generators --- */
78 rc_q
= pgen_create(&pq
, s
);
79 rc_p
= pgen_muladd(&pp
, &pq
, 2, 1);
80 mp_build(&b
, &bw
, &bw
+ 1);
82 /* --- Now step along until something crops up --- */
88 /* --- Don't do expensive testing unless necessary --- */
90 if (rc_q
== PGEN_PRIME
&& rc_p
== PGEN_PRIME
)
92 if (rc_q
== PGEN_COMPOSITE
|| rc_p
== PGEN_COMPOSITE
)
95 /* --- Initialize Rabin-Miller contexts --- */
97 if (rc_q
== PGEN_MAYBE
)
98 rabin_create(&rq
, pq
.m
);
99 if (rc_p
== PGEN_MAYBE
)
100 rabin_create(&rp
, pp
.m
);
102 /* --- Now run tests on each in turn --- *
104 * On the sorts of modulus sizes which work well in discrete log
105 * problems, five tests should be sufficient.
108 for (i
= 0; i
< 5; i
++) {
110 if (rc_q
== PGEN_MAYBE
&&
111 (rc_q
= rabin_test(&rq
, &b
)) == PGEN_COMPOSITE
)
113 if (rc_p
== PGEN_MAYBE
&&
114 (rc_p
= rabin_test(&rp
, &b
)) == PGEN_COMPOSITE
)
116 if (proc
&& proc(DHEV_PASS
, arg
))
119 if (rc_q
!= PGEN_PRIME
)
121 if (rc_p
!= PGEN_PRIME
)
124 /* --- If the tests passed, accept the numbers --- */
128 if (proc
&& proc(DHEV_FAIL
, arg
))
136 /* --- Step the contexts on --- */
139 rc_q
= pgen_step(&pq
, 2);
140 rc_p
= pgen_step(&pp
, 4);
143 /* --- Return a result --- */
146 mp
*p
= MP_COPY(pp
.m
);
152 /* --- Failure --- */
160 /*----- That's all, folks -------------------------------------------------*/