44c240ee |
1 | /* -*-c-*- |
2 | * |
ef5f4810 |
3 | * $Id: dh-prime.c,v 1.2 1999/12/10 23:18:38 mdw Exp $ |
44c240ee |
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 $ |
ef5f4810 |
33 | * Revision 1.2 1999/12/10 23:18:38 mdw |
34 | * Change interface for suggested destinations. |
35 | * |
44c240ee |
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" |
ef5f4810 |
48 | #include "fibrand.h" |
44c240ee |
49 | #include "mp.h" |
ef5f4810 |
50 | #include "mprand.h" |
44c240ee |
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; |
ef5f4810 |
78 | grand *gr = fibrand_create(0); |
79 | mp *b = MP_NEW; |
80 | size_t sz = mp_bits(s); |
44c240ee |
81 | |
82 | /* --- Initialize prime generators --- */ |
83 | |
84 | rc_q = pgen_create(&pq, s); |
85 | rc_p = pgen_muladd(&pp, &pq, 2, 1); |
44c240ee |
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++) { |
ef5f4810 |
114 | b = mprand(b, sz, gr, 1); |
44c240ee |
115 | if (rc_q == PGEN_MAYBE && |
ef5f4810 |
116 | (rc_q = rabin_test(&rq, b)) == PGEN_COMPOSITE) |
44c240ee |
117 | break; |
118 | if (rc_p == PGEN_MAYBE && |
ef5f4810 |
119 | (rc_p = rabin_test(&rp, b)) == PGEN_COMPOSITE) |
44c240ee |
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); |
ef5f4810 |
154 | mp_drop(b); |
155 | gr->ops->destroy(gr); |
44c240ee |
156 | return (p); |
157 | } |
158 | |
159 | /* --- Failure --- */ |
160 | |
161 | fail: |
162 | pgen_destroy(&pq); |
163 | pgen_destroy(&pp); |
ef5f4810 |
164 | mp_drop(b); |
165 | gr->ops->destroy(gr); |
44c240ee |
166 | return (0); |
167 | } |
168 | |
169 | /*----- That's all, folks -------------------------------------------------*/ |