Commit | Line | Data |
---|---|---|
e6e0e332 MW |
1 | /* -*-c-*- |
2 | * | |
05dfc037 | 3 | * $Id$ |
e6e0e332 MW |
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 | |
6b2d9d76 | 34 | * NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, |
e6e0e332 MW |
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 $ | |
6b2d9d76 MW |
53 | * Revision 1.2 2000/07/02 15:21:20 mdw |
54 | * Fix licence text. | |
55 | * | |
e6e0e332 MW |
56 | * Revision 1.1 2000/05/21 11:28:30 mdw |
57 | * Initial check-in. | |
58 | * | |
59 | * --- Past lives (Catacomb) --- * | |
60 | * | |
61 | * Revision 1.1 1999/12/22 15:53:12 mdw | |
62 | * Random number generator for finding DSA parameters. | |
63 | * | |
64 | */ | |
65 | ||
66 | /*----- Header files ------------------------------------------------------*/ | |
67 | ||
68 | #include <stdio.h> | |
69 | #include <stdlib.h> | |
70 | #include <string.h> | |
71 | ||
72 | #include "bits.h" | |
73 | #include "dsarand.h" | |
74 | #include "sha.h" | |
75 | ||
76 | /*----- Main code ---------------------------------------------------------*/ | |
77 | ||
78 | /* --- @STEP@ --- * | |
79 | * | |
80 | * Arguments: @dsarand *d@ = pointer to context | |
81 | * | |
82 | * Use: Increments the buffer by one, interpreting it as a big-endian | |
83 | * integer. Carries outside the integer are discarded. | |
84 | */ | |
85 | ||
86 | #define STEP(d) do { \ | |
87 | dsarand *_d = (d); \ | |
88 | octet *_p = _d->p; \ | |
89 | octet *_q = _p + _d->sz; \ | |
90 | unsigned _c = 1; \ | |
91 | while (_c && _q > _p) { \ | |
92 | _c += *--_q; \ | |
93 | *_q = U8(_c); \ | |
94 | _c >>= 8; \ | |
95 | } \ | |
96 | } while (0) | |
97 | ||
98 | /* --- @dsarand_init@ --- * | |
99 | * | |
100 | * Arguments: @dsarand *d@ = pointer to context | |
101 | * @const void *p@ = pointer to seed buffer | |
102 | * @size_t sz@ = size of the buffer | |
103 | * | |
104 | * Returns: --- | |
105 | * | |
106 | * Use: Initializes a DSA random number generator. | |
107 | */ | |
108 | ||
109 | void dsarand_init(dsarand *d, const void *p, size_t sz) | |
110 | { | |
111 | if ((d->p = malloc(sz)) == 0) { | |
112 | fputs("Out of memory in dsarand_init!\n", stderr); | |
113 | exit(EXIT_FAILURE); | |
114 | } | |
115 | d->sz = sz; | |
116 | d->passes = 1; | |
117 | if (p) | |
118 | memcpy(d->p, p, sz); | |
119 | } | |
120 | ||
121 | /* --- @dsarand_reseed@ --- * | |
122 | * | |
123 | * Arguments: @dsarand *d@ = pointer to context | |
124 | * @const void *p@ = pointer to seed buffer | |
125 | * @size_t sz@ = size of the buffer | |
126 | * | |
127 | * Returns: --- | |
128 | * | |
129 | * Use: Initializes a DSA random number generator. | |
130 | */ | |
131 | ||
132 | void dsarand_reseed(dsarand *d, const void *p, size_t sz) | |
133 | { | |
134 | free(d->p); | |
135 | if ((d->p = malloc(sz)) != 0) { | |
136 | fputs("Out of memory in dsarand_init!\n", stderr); | |
137 | exit(EXIT_FAILURE); | |
138 | } | |
139 | d->sz = sz; | |
140 | d->passes = 1; | |
141 | if (p) | |
142 | memcpy(d->p, p, sz); | |
143 | } | |
144 | ||
145 | /* --- @dsarand_destroy@ --- * | |
146 | * | |
147 | * Arguments: @dsarand *d@ = pointer to context | |
148 | * | |
149 | * Returns: --- | |
150 | * | |
151 | * Use: Disposes of a DSA random number generation context. | |
152 | */ | |
153 | ||
154 | void dsarand_destroy(dsarand *d) | |
155 | { | |
156 | free(d->p); | |
157 | } | |
158 | ||
159 | /* --- @dsarand_fill@ --- * | |
160 | * | |
161 | * Arguments: @dsarand *d@ = pointer to context | |
162 | * @void *p@ = pointer to output buffer | |
163 | * @size_t sz@ = size of output buffer | |
164 | * | |
165 | * Returns: --- | |
166 | * | |
167 | * Use: Fills an output buffer with pseudorandom data. | |
168 | * | |
169 | * Let %$p$% be the numerical value of the input buffer, and let | |
170 | * %$b$% be the number of bytes required. Let | |
171 | * %$z = \lceil b / 20 \rceil$% be the number of SHA outputs | |
172 | * required. Then the output of pass %$n$% is | |
173 | * | |
174 | * %$P_n = \sum_{0 \le i < z} 2^{160i} SHA(p + nz + i)$% | |
175 | * %${} \bmod 2^{8b}$% | |
176 | * | |
177 | * and the actual result in the output buffer is the XOR of all | |
178 | * of the output passes. | |
179 | * | |
180 | * The DSA procedure for choosing @q@ involves two passes with | |
181 | * %$z = 1$%; the procedure for choosing @p@ involves one pass | |
182 | * with larger %$z$%. This generalization of the DSA generation | |
183 | * procedure is my own invention but it seems relatively sound. | |
184 | */ | |
185 | ||
186 | void dsarand_fill(dsarand *d, void *p, size_t sz) | |
187 | { | |
188 | octet *q = p; | |
189 | unsigned n = d->passes; | |
190 | ||
191 | /* --- Write out the first pass --- * | |
192 | * | |
193 | * This can write directly to the output buffer, so it's done differently | |
194 | * from the latter passes. | |
195 | */ | |
196 | ||
197 | { | |
198 | size_t o = sz; | |
199 | ||
200 | while (o) { | |
201 | sha_ctx h; | |
202 | ||
203 | /* --- Hash the input buffer --- */ | |
204 | ||
205 | sha_init(&h); | |
206 | sha_hash(&h, d->p, d->sz); | |
207 | ||
208 | /* --- If enough space, extract the hash output directly --- */ | |
209 | ||
210 | if (o >= SHA_HASHSZ) { | |
211 | o -= SHA_HASHSZ; | |
212 | sha_done(&h, q + o); | |
213 | } | |
214 | ||
215 | /* --- Otherwise take the hash result out of line and copy it --- */ | |
216 | ||
217 | else { | |
218 | octet hash[SHA_HASHSZ]; | |
219 | sha_done(&h, hash); | |
220 | memcpy(q, hash + (SHA_HASHSZ - o), o); | |
221 | o = 0; | |
222 | } | |
223 | ||
224 | /* --- Step the input buffer --- */ | |
225 | ||
226 | STEP(d); | |
227 | } | |
228 | ||
229 | /* --- Another pass has been done --- */ | |
230 | ||
231 | n--; | |
232 | } | |
233 | ||
234 | /* --- Write out subsequent passes --- * | |
235 | * | |
236 | * The hash output has to be done offline, so this is slightly easier. | |
237 | */ | |
238 | ||
239 | while (n) { | |
240 | size_t o = sz; | |
241 | ||
242 | while (o) { | |
243 | sha_ctx h; | |
244 | octet hash[SHA_HASHSZ]; | |
245 | size_t n; | |
246 | octet *pp, *qq; | |
247 | ||
248 | /* --- Hash the input buffer --- */ | |
249 | ||
250 | sha_init(&h); | |
251 | sha_hash(&h, d->p, d->sz); | |
252 | sha_done(&h, hash); | |
253 | ||
254 | /* --- Work out how much output is wanted --- */ | |
255 | ||
256 | n = SHA_HASHSZ; | |
257 | if (n > o) | |
258 | n = o; | |
259 | o -= n; | |
260 | ||
261 | /* --- XOR the data out --- */ | |
262 | ||
263 | for (pp = hash + (SHA_HASHSZ - n), qq = q + o; | |
264 | pp < hash + SHA_HASHSZ; pp++, qq++) | |
265 | *qq ^= *pp; | |
266 | ||
267 | /* --- Step the input buffer --- */ | |
268 | ||
269 | STEP(d); | |
270 | } | |
271 | ||
272 | /* --- Another pass is done --- */ | |
273 | ||
274 | n--; | |
275 | } | |
276 | } | |
277 | ||
278 | /*----- That's all, folks -------------------------------------------------*/ |