3 * $Id: dh-prime.c,v 1.2 1999/12/10 23:18:38 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.2 1999/12/10 23:18:38 mdw
34 * Change interface for suggested destinations.
36 * Revision 1.1 1999/11/20 22:24:44 mdw
37 * Add Diffie-Hellman support.
41 /*----- Header files ------------------------------------------------------*/
54 /*----- Main code ---------------------------------------------------------*/
56 /* --- @dh_prime@ --- *
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
63 * Returns: A prime number %$p$% where %$p = 2q + 1$% for prime %$q$%.
65 * Use: Finds a safe prime by sequential search from a given starting
66 * point. If it fails, a null pointer is returned.
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
73 mp
*dh_prime(mp
*s
, size_t n
,
74 int (*proc
)(int /*ev*/, void */
*p*/
), void *arg
)
78 grand
*gr
= fibrand_create(0);
80 size_t sz
= mp_bits(s
);
82 /* --- Initialize prime generators --- */
84 rc_q
= pgen_create(&pq
, s
);
85 rc_p
= pgen_muladd(&pp
, &pq
, 2, 1);
87 /* --- Now step along until something crops up --- */
93 /* --- Don't do expensive testing unless necessary --- */
95 if (rc_q
== PGEN_PRIME
&& rc_p
== PGEN_PRIME
)
97 if (rc_q
== PGEN_COMPOSITE
|| rc_p
== PGEN_COMPOSITE
)
100 /* --- Initialize Rabin-Miller contexts --- */
102 if (rc_q
== PGEN_MAYBE
)
103 rabin_create(&rq
, pq
.m
);
104 if (rc_p
== PGEN_MAYBE
)
105 rabin_create(&rp
, pp
.m
);
107 /* --- Now run tests on each in turn --- *
109 * On the sorts of modulus sizes which work well in discrete log
110 * problems, five tests should be sufficient.
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
)
118 if (rc_p
== PGEN_MAYBE
&&
119 (rc_p
= rabin_test(&rp
, b
)) == PGEN_COMPOSITE
)
121 if (proc
&& proc(DHEV_PASS
, arg
))
124 if (rc_q
!= PGEN_PRIME
)
126 if (rc_p
!= PGEN_PRIME
)
129 /* --- If the tests passed, accept the numbers --- */
133 if (proc
&& proc(DHEV_FAIL
, arg
))
141 /* --- Step the contexts on --- */
144 rc_q
= pgen_step(&pq
, 2);
145 rc_p
= pgen_step(&pp
, 4);
148 /* --- Return a result --- */
151 mp
*p
= MP_COPY(pp
.m
);
155 gr
->ops
->destroy(gr
);
159 /* --- Failure --- */
165 gr
->ops
->destroy(gr
);
169 /*----- That's all, folks -------------------------------------------------*/