Commit | Line | Data |
---|---|---|
e6e0e332 MW |
1 | /* -*-c-*- |
2 | * | |
3 | * $Id: dsarand.c,v 1.1 2000/05/21 11:28:30 mdw Exp $ | |
4 | * | |
5 | * Random number generator for DSA | |
6 | * | |
7 | * (c) 1999 Straylight/Edgeware | |
8 | * (c) 2000 Mark Wooding | |
9 | */ | |
10 | ||
11 | /*----- Licensing notice --------------------------------------------------* | |
12 | * | |
13 | * Copyright (c) 2000 Mark Wooding | |
14 | * All rights reserved. | |
15 | * | |
16 | * Redistribution and use in source and binary forms, with or without | |
17 | * modification, are permitted provided that the following conditions are | |
18 | * met: | |
19 | * | |
20 | * 1. Redistributions of source code must retain the above copyright | |
21 | * notice, this list of conditions and the following disclaimer. | |
22 | * | |
23 | * 2, Redistributions in binary form must reproduce the above copyright | |
24 | * notice, this list of conditions and the following disclaimer in the | |
25 | * documentation and/or other materials provided with the distribution. | |
26 | * | |
27 | * 3. The name of the authors may not be used to endorse or promote | |
28 | * products derived from this software without specific prior written | |
29 | * permission. | |
30 | * | |
31 | * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED | |
32 | * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF | |
33 | * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN | |
34 | * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, | |
35 | * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES | |
36 | * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR | |
37 | * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
38 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | |
39 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN | |
40 | * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | |
41 | * POSSIBILITY OF SUCH DAMAGE. | |
42 | * | |
43 | * Instead of accepting the above terms, you may redistribute and/or modify | |
44 | * this software under the terms of either the GNU General Public License, | |
45 | * or the GNU Library General Public License, published by the Free | |
46 | * Software Foundation; either version 2 of the License, or (at your | |
47 | * option) any later version. | |
48 | */ | |
49 | ||
50 | /*----- Revision history --------------------------------------------------* | |
51 | * | |
52 | * $Log: dsarand.c,v $ | |
53 | * Revision 1.1 2000/05/21 11:28:30 mdw | |
54 | * Initial check-in. | |
55 | * | |
56 | * --- Past lives (Catacomb) --- * | |
57 | * | |
58 | * Revision 1.1 1999/12/22 15:53:12 mdw | |
59 | * Random number generator for finding DSA parameters. | |
60 | * | |
61 | */ | |
62 | ||
63 | /*----- Header files ------------------------------------------------------*/ | |
64 | ||
65 | #include <stdio.h> | |
66 | #include <stdlib.h> | |
67 | #include <string.h> | |
68 | ||
69 | #include "bits.h" | |
70 | #include "dsarand.h" | |
71 | #include "sha.h" | |
72 | ||
73 | /*----- Main code ---------------------------------------------------------*/ | |
74 | ||
75 | /* --- @STEP@ --- * | |
76 | * | |
77 | * Arguments: @dsarand *d@ = pointer to context | |
78 | * | |
79 | * Use: Increments the buffer by one, interpreting it as a big-endian | |
80 | * integer. Carries outside the integer are discarded. | |
81 | */ | |
82 | ||
83 | #define STEP(d) do { \ | |
84 | dsarand *_d = (d); \ | |
85 | octet *_p = _d->p; \ | |
86 | octet *_q = _p + _d->sz; \ | |
87 | unsigned _c = 1; \ | |
88 | while (_c && _q > _p) { \ | |
89 | _c += *--_q; \ | |
90 | *_q = U8(_c); \ | |
91 | _c >>= 8; \ | |
92 | } \ | |
93 | } while (0) | |
94 | ||
95 | /* --- @dsarand_init@ --- * | |
96 | * | |
97 | * Arguments: @dsarand *d@ = pointer to context | |
98 | * @const void *p@ = pointer to seed buffer | |
99 | * @size_t sz@ = size of the buffer | |
100 | * | |
101 | * Returns: --- | |
102 | * | |
103 | * Use: Initializes a DSA random number generator. | |
104 | */ | |
105 | ||
106 | void dsarand_init(dsarand *d, const void *p, size_t sz) | |
107 | { | |
108 | if ((d->p = malloc(sz)) == 0) { | |
109 | fputs("Out of memory in dsarand_init!\n", stderr); | |
110 | exit(EXIT_FAILURE); | |
111 | } | |
112 | d->sz = sz; | |
113 | d->passes = 1; | |
114 | if (p) | |
115 | memcpy(d->p, p, sz); | |
116 | } | |
117 | ||
118 | /* --- @dsarand_reseed@ --- * | |
119 | * | |
120 | * Arguments: @dsarand *d@ = pointer to context | |
121 | * @const void *p@ = pointer to seed buffer | |
122 | * @size_t sz@ = size of the buffer | |
123 | * | |
124 | * Returns: --- | |
125 | * | |
126 | * Use: Initializes a DSA random number generator. | |
127 | */ | |
128 | ||
129 | void dsarand_reseed(dsarand *d, const void *p, size_t sz) | |
130 | { | |
131 | free(d->p); | |
132 | if ((d->p = malloc(sz)) != 0) { | |
133 | fputs("Out of memory in dsarand_init!\n", stderr); | |
134 | exit(EXIT_FAILURE); | |
135 | } | |
136 | d->sz = sz; | |
137 | d->passes = 1; | |
138 | if (p) | |
139 | memcpy(d->p, p, sz); | |
140 | } | |
141 | ||
142 | /* --- @dsarand_destroy@ --- * | |
143 | * | |
144 | * Arguments: @dsarand *d@ = pointer to context | |
145 | * | |
146 | * Returns: --- | |
147 | * | |
148 | * Use: Disposes of a DSA random number generation context. | |
149 | */ | |
150 | ||
151 | void dsarand_destroy(dsarand *d) | |
152 | { | |
153 | free(d->p); | |
154 | } | |
155 | ||
156 | /* --- @dsarand_fill@ --- * | |
157 | * | |
158 | * Arguments: @dsarand *d@ = pointer to context | |
159 | * @void *p@ = pointer to output buffer | |
160 | * @size_t sz@ = size of output buffer | |
161 | * | |
162 | * Returns: --- | |
163 | * | |
164 | * Use: Fills an output buffer with pseudorandom data. | |
165 | * | |
166 | * Let %$p$% be the numerical value of the input buffer, and let | |
167 | * %$b$% be the number of bytes required. Let | |
168 | * %$z = \lceil b / 20 \rceil$% be the number of SHA outputs | |
169 | * required. Then the output of pass %$n$% is | |
170 | * | |
171 | * %$P_n = \sum_{0 \le i < z} 2^{160i} SHA(p + nz + i)$% | |
172 | * %${} \bmod 2^{8b}$% | |
173 | * | |
174 | * and the actual result in the output buffer is the XOR of all | |
175 | * of the output passes. | |
176 | * | |
177 | * The DSA procedure for choosing @q@ involves two passes with | |
178 | * %$z = 1$%; the procedure for choosing @p@ involves one pass | |
179 | * with larger %$z$%. This generalization of the DSA generation | |
180 | * procedure is my own invention but it seems relatively sound. | |
181 | */ | |
182 | ||
183 | void dsarand_fill(dsarand *d, void *p, size_t sz) | |
184 | { | |
185 | octet *q = p; | |
186 | unsigned n = d->passes; | |
187 | ||
188 | /* --- Write out the first pass --- * | |
189 | * | |
190 | * This can write directly to the output buffer, so it's done differently | |
191 | * from the latter passes. | |
192 | */ | |
193 | ||
194 | { | |
195 | size_t o = sz; | |
196 | ||
197 | while (o) { | |
198 | sha_ctx h; | |
199 | ||
200 | /* --- Hash the input buffer --- */ | |
201 | ||
202 | sha_init(&h); | |
203 | sha_hash(&h, d->p, d->sz); | |
204 | ||
205 | /* --- If enough space, extract the hash output directly --- */ | |
206 | ||
207 | if (o >= SHA_HASHSZ) { | |
208 | o -= SHA_HASHSZ; | |
209 | sha_done(&h, q + o); | |
210 | } | |
211 | ||
212 | /* --- Otherwise take the hash result out of line and copy it --- */ | |
213 | ||
214 | else { | |
215 | octet hash[SHA_HASHSZ]; | |
216 | sha_done(&h, hash); | |
217 | memcpy(q, hash + (SHA_HASHSZ - o), o); | |
218 | o = 0; | |
219 | } | |
220 | ||
221 | /* --- Step the input buffer --- */ | |
222 | ||
223 | STEP(d); | |
224 | } | |
225 | ||
226 | /* --- Another pass has been done --- */ | |
227 | ||
228 | n--; | |
229 | } | |
230 | ||
231 | /* --- Write out subsequent passes --- * | |
232 | * | |
233 | * The hash output has to be done offline, so this is slightly easier. | |
234 | */ | |
235 | ||
236 | while (n) { | |
237 | size_t o = sz; | |
238 | ||
239 | while (o) { | |
240 | sha_ctx h; | |
241 | octet hash[SHA_HASHSZ]; | |
242 | size_t n; | |
243 | octet *pp, *qq; | |
244 | ||
245 | /* --- Hash the input buffer --- */ | |
246 | ||
247 | sha_init(&h); | |
248 | sha_hash(&h, d->p, d->sz); | |
249 | sha_done(&h, hash); | |
250 | ||
251 | /* --- Work out how much output is wanted --- */ | |
252 | ||
253 | n = SHA_HASHSZ; | |
254 | if (n > o) | |
255 | n = o; | |
256 | o -= n; | |
257 | ||
258 | /* --- XOR the data out --- */ | |
259 | ||
260 | for (pp = hash + (SHA_HASHSZ - n), qq = q + o; | |
261 | pp < hash + SHA_HASHSZ; pp++, qq++) | |
262 | *qq ^= *pp; | |
263 | ||
264 | /* --- Step the input buffer --- */ | |
265 | ||
266 | STEP(d); | |
267 | } | |
268 | ||
269 | /* --- Another pass is done --- */ | |
270 | ||
271 | n--; | |
272 | } | |
273 | } | |
274 | ||
275 | /*----- That's all, folks -------------------------------------------------*/ |