5d4a6be9 |
1 | /* -*-c-*- |
2 | * |
3 | * $Id: dsarand.c,v 1.1 1999/12/22 15:53:12 mdw Exp $ |
4 | * |
5 | * Random number generator for DSA |
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: dsarand.c,v $ |
33 | * Revision 1.1 1999/12/22 15:53:12 mdw |
34 | * Random number generator for finding DSA parameters. |
35 | * |
36 | */ |
37 | |
38 | /*----- Header files ------------------------------------------------------*/ |
39 | |
40 | #include <stdarg.h> |
41 | #include <string.h> |
42 | |
43 | #include <mLib/bits.h> |
44 | #include <mLib/sub.h> |
45 | |
46 | #include "dsarand.h" |
47 | #include "grand.h" |
48 | #include "sha.h" |
49 | |
50 | /*----- Main code ---------------------------------------------------------*/ |
51 | |
52 | /* --- @STEP@ --- * |
53 | * |
54 | * Arguments: @dsarand *d@ = pointer to context |
55 | * |
56 | * Use: Increments the buffer by one, interpreting it as a big-endian |
57 | * integer. Carries outside the integer are discarded. |
58 | */ |
59 | |
60 | #define STEP(d) do { \ |
61 | dsarand *_d = (d); \ |
62 | octet *_p = _d->p; \ |
63 | octet *_q = _p + _d->sz; \ |
64 | unsigned _c = 1; \ |
65 | while (_c && _q > _p) { \ |
66 | _c += *--_q; \ |
67 | *_q = U8(_c); \ |
68 | _c >>= 8; \ |
69 | } \ |
70 | } while (0) |
71 | |
72 | /* --- @dsarand_init@ --- * |
73 | * |
74 | * Arguments: @dsarand *d@ = pointer to context |
75 | * @const void *p@ = pointer to seed buffer |
76 | * @size_t sz@ = size of the buffer |
77 | * |
78 | * Returns: --- |
79 | * |
80 | * Use: Initializes a DSA random number generator. |
81 | */ |
82 | |
83 | void dsarand_init(dsarand *d, const void *p, size_t sz) |
84 | { |
85 | d->p = xmalloc(sz); |
86 | d->sz = sz; |
87 | if (p) |
88 | memcpy(d->p, p, sz); |
89 | } |
90 | |
91 | /* --- @dsarand_reseed@ --- * |
92 | * |
93 | * Arguments: @dsarand *d@ = pointer to context |
94 | * @const void *p@ = pointer to seed buffer |
95 | * @size_t sz@ = size of the buffer |
96 | * |
97 | * Returns: --- |
98 | * |
99 | * Use: Initializes a DSA random number generator. |
100 | */ |
101 | |
102 | void dsarand_reseed(dsarand *d, const void *p, size_t sz) |
103 | { |
104 | free(d->p); |
105 | d->p = xmalloc(sz); |
106 | d->sz = sz; |
107 | d->passes = 1; |
108 | if (p) |
109 | memcpy(d->p, p, sz); |
110 | } |
111 | |
112 | /* --- @dsarand_destroy@ --- * |
113 | * |
114 | * Arguments: @dsarand *d@ = pointer to context |
115 | * |
116 | * Returns: --- |
117 | * |
118 | * Use: Disposes of a DSA random number generation context. |
119 | */ |
120 | |
121 | void dsarand_destroy(dsarand *d) |
122 | { |
123 | free(d->p); |
124 | } |
125 | |
126 | /* --- @dsarand_fill@ --- * |
127 | * |
128 | * Arguments: @dsarand *d@ = pointer to context |
129 | * @void *p@ = pointer to output buffer |
130 | * @size_t sz@ = size of output buffer |
131 | * |
132 | * Returns: --- |
133 | * |
134 | * Use: Fills an output buffer with pseudorandom data. |
135 | * |
136 | * Let %$p$% be the numerical value of the input buffer, and let |
137 | * %$b$% be the number of bytes required. Let |
138 | * %$z = \lceil b / 20 \rceil%$ be the number of SHA outputs |
139 | * required. Then the output of pass %$n$% is |
140 | * |
141 | * %$P_n = \sum_{0 \le i < z} 2^{160i} SHA(p + nz + i)$% |
142 | * %${} \bmod 2^{8b}$% |
143 | * |
144 | * and the actual result in the output buffer is the XOR of all |
145 | * of the output passes. |
146 | * |
147 | * The DSA procedure for choosing @q@ involves two passes with |
148 | * %$z = 1$%; the procedure for choosing @p@ involves one pass |
149 | * with larger %$z$%. This generalization of the DSA generation |
150 | * procedure is my own invention but it seems relatively sound. |
151 | */ |
152 | |
153 | void dsarand_fill(dsarand *d, void *p, size_t sz) |
154 | { |
155 | octet *q = p; |
156 | unsigned n = d->passes; |
157 | |
158 | /* --- Write out the first pass --- * |
159 | * |
160 | * This can write directly to the output buffer, so it's done differently |
161 | * from the latter passes. |
162 | */ |
163 | |
164 | { |
165 | size_t o = sz; |
166 | |
167 | while (o) { |
168 | sha_ctx h; |
169 | |
170 | /* --- Hash the input buffer --- */ |
171 | |
172 | sha_init(&h); |
173 | sha_hash(&h, d->p, d->sz); |
174 | |
175 | /* --- If enough space, extract the hash output directly --- */ |
176 | |
177 | if (o >= SHA_HASHSZ) { |
178 | o -= SHA_HASHSZ; |
179 | sha_done(&h, q + o); |
180 | } |
181 | |
182 | /* --- Otherwise take the hash result out of line and copy it --- */ |
183 | |
184 | else { |
185 | octet hash[SHA_HASHSZ]; |
186 | sha_done(&h, hash); |
187 | memcpy(q, hash + (SHA_HASHSZ - o), o); |
188 | o = 0; |
189 | } |
190 | |
191 | /* --- Step the input buffer --- */ |
192 | |
193 | STEP(d); |
194 | } |
195 | |
196 | /* --- Another pass has been done --- */ |
197 | |
198 | n--; |
199 | } |
200 | |
201 | /* --- Write out subsequent passes --- * |
202 | * |
203 | * The hash output has to be done offline, so this is slightly easier. |
204 | */ |
205 | |
206 | while (n) { |
207 | size_t o = sz; |
208 | |
209 | while (o) { |
210 | sha_ctx h; |
211 | octet hash[SHA_HASHSZ]; |
212 | size_t n; |
213 | octet *pp, *qq; |
214 | |
215 | /* --- Hash the input buffer --- */ |
216 | |
217 | sha_init(&h); |
218 | sha_hash(&h, d->p, d->sz); |
219 | sha_done(&h, hash); |
220 | |
221 | /* --- Work out how much output is wanted --- */ |
222 | |
223 | n = SHA_HASHSZ; |
224 | if (n > o) |
225 | n = o; |
226 | o -= n; |
227 | |
228 | /* --- XOR the data out --- */ |
229 | |
230 | for (pp = hash + (SHA_HASHSZ - n), qq = q + o; |
231 | pp < hash + SHA_HASHSZ; pp++, qq++) |
232 | *qq ^= *pp; |
233 | |
234 | /* --- Step the input buffer --- */ |
235 | |
236 | STEP(d); |
237 | } |
238 | |
239 | /* --- Another pass is done --- */ |
240 | |
241 | n--; |
242 | } |
243 | } |
244 | |
245 | /*----- Generic pseudorandom-number generator interface -------------------*/ |
246 | |
247 | static const grand_ops gops; |
248 | |
249 | typedef struct gctx { |
250 | grand r; |
251 | dsarand d; |
252 | } gctx; |
253 | |
254 | static void gdestroy(grand *r) |
255 | { |
256 | gctx *g = (gctx *)r; |
257 | dsarand_destroy(&g->d); |
258 | DESTROY(g); |
259 | } |
260 | |
261 | static int gmisc(grand *r, unsigned op, ...) |
262 | { |
263 | gctx *g = (gctx *)r; |
264 | va_list ap; |
265 | int rc = 0; |
266 | va_start(ap, op); |
267 | |
268 | switch (op) { |
269 | case GRAND_CHECK: |
270 | switch (va_arg(ap, unsigned)) { |
271 | case GRAND_CHECK: |
272 | case GRAND_SEEDBLOCK: |
273 | case GRAND_SEEDRAND: |
274 | case DSARAND_PASSES: |
275 | rc = 1; |
276 | break; |
277 | default: |
278 | rc = 0; |
279 | break; |
280 | } |
281 | break; |
282 | case GRAND_SEEDBLOCK: { |
283 | const void *p = va_arg(ap, const void *); |
284 | size_t sz = va_arg(ap, size_t); |
285 | dsarand_reseed(&g->d, p, sz); |
286 | } break; |
287 | case GRAND_SEEDRAND: { |
288 | grand *rr = va_arg(ap, grand *); |
289 | rr->ops->fill(rr, g->d.p, g->d.sz); |
290 | } break; |
291 | case DSARAND_PASSES: |
292 | g->d.passes = va_arg(ap, unsigned); |
293 | break; |
294 | default: |
295 | GRAND_BADOP; |
296 | break; |
297 | } |
298 | |
299 | va_end(ap); |
300 | return (rc); |
301 | } |
302 | |
303 | static void gfill(grand *r, void *p, size_t sz) |
304 | { |
305 | gctx *g = (gctx *)r; |
306 | dsarand_fill(&g->d, p, sz); |
307 | } |
308 | |
309 | static const grand_ops gops = { |
310 | "dsarand", |
311 | 0, |
312 | gmisc, gdestroy, |
313 | grand_word, grand_byte, grand_word, grand_range, gfill |
314 | }; |
315 | |
316 | /* --- @dsarand_create@ --- * |
317 | * |
318 | * Arguments: @const void *p@ = pointer to seed buffer |
319 | * @size_t sz@ = size of seed buffer |
320 | * |
321 | * Returns: Pointer to a generic generator. |
322 | * |
323 | * Use: Constructs a generic generator interface over a Catacomb |
324 | * entropy pool generator. |
325 | */ |
326 | |
327 | grand *dsarand_create(const void *p, size_t sz) |
328 | { |
329 | gctx *g = CREATE(gctx); |
330 | g->r.ops = &gops; |
331 | dsarand_init(&g->d, p, sz); |
332 | return (&g->r); |
333 | } |
334 | |
335 | /*----- That's all, folks -------------------------------------------------*/ |