OpenCoverage

moduli.c

Absolute File Name:/home/opencoverage/opencoverage/guest-scripts/openssh/src/moduli.c
Source codeSwitch to Preprocessed file
LineSourceCount
1/* $OpenBSD: moduli.c,v 1.32 2017/12/08 03:45:52 deraadt Exp $ */-
2/*-
3 * Copyright 1994 Phil Karn <karn@qualcomm.com>-
4 * Copyright 1996-1998, 2003 William Allen Simpson <wsimpson@greendragon.com>-
5 * Copyright 2000 Niels Provos <provos@citi.umich.edu>-
6 * All rights reserved.-
7 *-
8 * Redistribution and use in source and binary forms, with or without-
9 * modification, are permitted provided that the following conditions-
10 * are met:-
11 * 1. Redistributions of source code must retain the above copyright-
12 * notice, this list of conditions and the following disclaimer.-
13 * 2. Redistributions in binary form must reproduce the above copyright-
14 * notice, this list of conditions and the following disclaimer in the-
15 * documentation and/or other materials provided with the distribution.-
16 *-
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR-
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES-
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.-
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,-
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT-
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,-
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY-
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT-
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF-
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.-
27 */-
28-
29/*-
30 * Two-step process to generate safe primes for DHGEX-
31 *-
32 * Sieve candidates for "safe" primes,-
33 * suitable for use as Diffie-Hellman moduli;-
34 * that is, where q = (p-1)/2 is also prime.-
35 *-
36 * First step: generate candidate primes (memory intensive)-
37 * Second step: test primes' safety (processor intensive)-
38 */-
39-
40#include "includes.h"-
41-
42#ifdef WITH_OPENSSL-
43-
44#include <sys/types.h>-
45-
46#include <openssl/bn.h>-
47#include <openssl/dh.h>-
48-
49#include <errno.h>-
50#include <stdio.h>-
51#include <stdlib.h>-
52#include <string.h>-
53#include <stdarg.h>-
54#include <time.h>-
55#include <unistd.h>-
56#include <limits.h>-
57-
58#include "xmalloc.h"-
59#include "dh.h"-
60#include "log.h"-
61#include "misc.h"-
62-
63#include "openbsd-compat/openssl-compat.h"-
64-
65/*-
66 * File output defines-
67 */-
68-
69/* need line long enough for largest moduli plus headers */-
70#define QLINESIZE (100+8192)-
71-
72/*-
73 * Size: decimal.-
74 * Specifies the number of the most significant bit (0 to M).-
75 * WARNING: internally, usually 1 to N.-
76 */-
77#define QSIZE_MINIMUM (511)-
78-
79/*-
80 * Prime sieving defines-
81 */-
82-
83/* Constant: assuming 8 bit bytes and 32 bit words */-
84#define SHIFT_BIT (3)-
85#define SHIFT_BYTE (2)-
86#define SHIFT_WORD (SHIFT_BIT+SHIFT_BYTE)-
87#define SHIFT_MEGABYTE (20)-
88#define SHIFT_MEGAWORD (SHIFT_MEGABYTE-SHIFT_BYTE)-
89-
90/*-
91 * Using virtual memory can cause thrashing. This should be the largest-
92 * number that is supported without a large amount of disk activity ---
93 * that would increase the run time from hours to days or weeks!-
94 */-
95#define LARGE_MINIMUM (8UL) /* megabytes */-
96-
97/*-
98 * Do not increase this number beyond the unsigned integer bit size.-
99 * Due to a multiple of 4, it must be LESS than 128 (yielding 2**30 bits).-
100 */-
101#define LARGE_MAXIMUM (127UL) /* megabytes */-
102-
103/*-
104 * Constant: when used with 32-bit integers, the largest sieve prime-
105 * has to be less than 2**32.-
106 */-
107#define SMALL_MAXIMUM (0xffffffffUL)-
108-
109/* Constant: can sieve all primes less than 2**32, as 65537**2 > 2**32-1. */-
110#define TINY_NUMBER (1UL<<16)-
111-
112/* Ensure enough bit space for testing 2*q. */-
113#define TEST_MAXIMUM (1UL<<16)-
114#define TEST_MINIMUM (QSIZE_MINIMUM + 1)-
115/* real TEST_MINIMUM (1UL << (SHIFT_WORD - TEST_POWER)) */-
116#define TEST_POWER (3) /* 2**n, n < SHIFT_WORD */-
117-
118/* bit operations on 32-bit words */-
119#define BIT_CLEAR(a,n) ((a)[(n)>>SHIFT_WORD] &= ~(1L << ((n) & 31)))-
120#define BIT_SET(a,n) ((a)[(n)>>SHIFT_WORD] |= (1L << ((n) & 31)))-
121#define BIT_TEST(a,n) ((a)[(n)>>SHIFT_WORD] & (1L << ((n) & 31)))-
122-
123/*-
124 * Prime testing defines-
125 */-
126-
127/* Minimum number of primality tests to perform */-
128#define TRIAL_MINIMUM (4)-
129-
130/*-
131 * Sieving data (XXX - move to struct)-
132 */-
133-
134/* sieve 2**16 */-
135static u_int32_t *TinySieve, tinybits;-
136-
137/* sieve 2**30 in 2**16 parts */-
138static u_int32_t *SmallSieve, smallbits, smallbase;-
139-
140/* sieve relative to the initial value */-
141static u_int32_t *LargeSieve, largewords, largetries, largenumbers;-
142static u_int32_t largebits, largememory; /* megabytes */-
143static BIGNUM *largebase;-
144-
145int gen_candidates(FILE *, u_int32_t, u_int32_t, BIGNUM *);-
146int prime_test(FILE *, FILE *, u_int32_t, u_int32_t, char *, unsigned long,-
147 unsigned long);-
148-
149/*-
150 * print moduli out in consistent form,-
151 */-
152static int-
153qfileout(FILE * ofile, u_int32_t otype, u_int32_t otests, u_int32_t otries,-
154 u_int32_t osize, u_int32_t ogenerator, BIGNUM * omodulus)-
155{-
156 struct tm *gtm;-
157 time_t time_now;-
158 int res;-
159-
160 time(&time_now);-
161 gtm = gmtime(&time_now);-
162-
163 res = fprintf(ofile, "%04d%02d%02d%02d%02d%02d %u %u %u %u %x ",-
164 gtm->tm_year + 1900, gtm->tm_mon + 1, gtm->tm_mday,-
165 gtm->tm_hour, gtm->tm_min, gtm->tm_sec,-
166 otype, otests, otries, osize, ogenerator);-
167-
168 if (res < 0)
res < 0Description
TRUEnever evaluated
FALSEnever evaluated
0
169 return (-1);
never executed: return (-1);
0
170-
171 if (BN_print_fp(ofile, omodulus) < 1)
BN_print_fp(of... omodulus) < 1Description
TRUEnever evaluated
FALSEnever evaluated
0
172 return (-1);
never executed: return (-1);
0
173-
174 res = fprintf(ofile, "\n");-
175 fflush(ofile);-
176-
177 return (res > 0 ? 0 : -1);
never executed: return (res > 0 ? 0 : -1);
res > 0Description
TRUEnever evaluated
FALSEnever evaluated
0
178}-
179-
180-
181/*-
182 ** Sieve p's and q's with small factors-
183 */-
184static void-
185sieve_large(u_int32_t s)-
186{-
187 u_int32_t r, u;-
188-
189 debug3("sieve_large %u", s);-
190 largetries++;-
191 /* r = largebase mod s */-
192 r = BN_mod_word(largebase, s);-
193 if (r == 0)
r == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
194 u = 0; /* s divides into largebase exactly */
never executed: u = 0;
0
195 else-
196 u = s - r; /* largebase+u is first entry divisible by s */
never executed: u = s - r;
0
197-
198 if (u < largebits * 2) {
u < largebits * 2Description
TRUEnever evaluated
FALSEnever evaluated
0
199 /*-
200 * The sieve omits p's and q's divisible by 2, so ensure that-
201 * largebase+u is odd. Then, step through the sieve in-
202 * increments of 2*s-
203 */-
204 if (u & 0x1)
u & 0x1Description
TRUEnever evaluated
FALSEnever evaluated
0
205 u += s; /* Make largebase+u odd, and u even */
never executed: u += s;
0
206-
207 /* Mark all multiples of 2*s */-
208 for (u /= 2; u < largebits; u += s)
u < largebitsDescription
TRUEnever evaluated
FALSEnever evaluated
0
209 BIT_SET(LargeSieve, u);
never executed: ((LargeSieve)[(u)>>((3)+(2))] |= (1L << ((u) & 31)));
0
210 }
never executed: end of block
0
211-
212 /* r = p mod s */-
213 r = (2 * r + 1) % s;-
214 if (r == 0)
r == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
215 u = 0; /* s divides p exactly */
never executed: u = 0;
0
216 else-
217 u = s - r; /* p+u is first entry divisible by s */
never executed: u = s - r;
0
218-
219 if (u < largebits * 4) {
u < largebits * 4Description
TRUEnever evaluated
FALSEnever evaluated
0
220 /*-
221 * The sieve omits p's divisible by 4, so ensure that-
222 * largebase+u is not. Then, step through the sieve in-
223 * increments of 4*s-
224 */-
225 while (u & 0x3) {
u & 0x3Description
TRUEnever evaluated
FALSEnever evaluated
0
226 if (SMALL_MAXIMUM - u < s)
(0xffffffffUL) - u < sDescription
TRUEnever evaluated
FALSEnever evaluated
0
227 return;
never executed: return;
0
228 u += s;-
229 }
never executed: end of block
0
230-
231 /* Mark all multiples of 4*s */-
232 for (u /= 4; u < largebits; u += s)
u < largebitsDescription
TRUEnever evaluated
FALSEnever evaluated
0
233 BIT_SET(LargeSieve, u);
never executed: ((LargeSieve)[(u)>>((3)+(2))] |= (1L << ((u) & 31)));
0
234 }
never executed: end of block
0
235}
never executed: end of block
0
236-
237/*-
238 * list candidates for Sophie-Germain primes (where q = (p-1)/2)-
239 * to standard output.-
240 * The list is checked against small known primes (less than 2**30).-
241 */-
242int-
243gen_candidates(FILE *out, u_int32_t memory, u_int32_t power, BIGNUM *start)-
244{-
245 BIGNUM *q;-
246 u_int32_t j, r, s, t;-
247 u_int32_t smallwords = TINY_NUMBER >> 6;-
248 u_int32_t tinywords = TINY_NUMBER >> 6;-
249 time_t time_start, time_stop;-
250 u_int32_t i;-
251 int ret = 0;-
252-
253 largememory = memory;-
254-
255 if (memory != 0 &&
memory != 0Description
TRUEnever evaluated
FALSEnever evaluated
0
256 (memory < LARGE_MINIMUM || memory > LARGE_MAXIMUM)) {
memory < (8UL)Description
TRUEnever evaluated
FALSEnever evaluated
memory > (127UL)Description
TRUEnever evaluated
FALSEnever evaluated
0
257 error("Invalid memory amount (min %ld, max %ld)",-
258 LARGE_MINIMUM, LARGE_MAXIMUM);-
259 return (-1);
never executed: return (-1);
0
260 }-
261-
262 /*-
263 * Set power to the length in bits of the prime to be generated.-
264 * This is changed to 1 less than the desired safe prime moduli p.-
265 */-
266 if (power > TEST_MAXIMUM) {
power > (1UL<<16)Description
TRUEnever evaluated
FALSEnever evaluated
0
267 error("Too many bits: %u > %lu", power, TEST_MAXIMUM);-
268 return (-1);
never executed: return (-1);
0
269 } else if (power < TEST_MINIMUM) {
power < ((511) + 1)Description
TRUEnever evaluated
FALSEnever evaluated
0
270 error("Too few bits: %u < %u", power, TEST_MINIMUM);-
271 return (-1);
never executed: return (-1);
0
272 }-
273 power--; /* decrement before squaring */-
274-
275 /*-
276 * The density of ordinary primes is on the order of 1/bits, so the-
277 * density of safe primes should be about (1/bits)**2. Set test range-
278 * to something well above bits**2 to be reasonably sure (but not-
279 * guaranteed) of catching at least one safe prime.-
280 */-
281 largewords = ((power * power) >> (SHIFT_WORD - TEST_POWER));-
282-
283 /*-
284 * Need idea of how much memory is available. We don't have to use all-
285 * of it.-
286 */-
287 if (largememory > LARGE_MAXIMUM) {
largememory > (127UL)Description
TRUEnever evaluated
FALSEnever evaluated
0
288 logit("Limited memory: %u MB; limit %lu MB",-
289 largememory, LARGE_MAXIMUM);-
290 largememory = LARGE_MAXIMUM;-
291 }
never executed: end of block
0
292-
293 if (largewords <= (largememory << SHIFT_MEGAWORD)) {
largewords <= ...<< ((20)-(2)))Description
TRUEnever evaluated
FALSEnever evaluated
0
294 logit("Increased memory: %u MB; need %u bytes",-
295 largememory, (largewords << SHIFT_BYTE));-
296 largewords = (largememory << SHIFT_MEGAWORD);-
297 } else if (largememory > 0) {
never executed: end of block
largememory > 0Description
TRUEnever evaluated
FALSEnever evaluated
0
298 logit("Decreased memory: %u MB; want %u bytes",-
299 largememory, (largewords << SHIFT_BYTE));-
300 largewords = (largememory << SHIFT_MEGAWORD);-
301 }
never executed: end of block
0
302-
303 TinySieve = xcalloc(tinywords, sizeof(u_int32_t));-
304 tinybits = tinywords << SHIFT_WORD;-
305-
306 SmallSieve = xcalloc(smallwords, sizeof(u_int32_t));-
307 smallbits = smallwords << SHIFT_WORD;-
308-
309 /*-
310 * dynamically determine available memory-
311 */-
312 while ((LargeSieve = calloc(largewords, sizeof(u_int32_t))) == NULL)
(LargeSieve = ...== ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
313 largewords -= (1L << (SHIFT_MEGAWORD - 2)); /* 1/4 MB chunks */
never executed: largewords -= (1L << (((20)-(2)) - 2));
0
314-
315 largebits = largewords << SHIFT_WORD;-
316 largenumbers = largebits * 2; /* even numbers excluded */-
317-
318 /* validation check: count the number of primes tried */-
319 largetries = 0;-
320 if ((q = BN_new()) == NULL)
(q = BN_new()) == ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
321 fatal("BN_new failed");
never executed: fatal("BN_new failed");
0
322-
323 /*-
324 * Generate random starting point for subprime search, or use-
325 * specified parameter.-
326 */-
327 if ((largebase = BN_new()) == NULL)
(largebase = B...== ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
328 fatal("BN_new failed");
never executed: fatal("BN_new failed");
0
329 if (start == NULL) {
start == ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
330 if (BN_rand(largebase, power, 1, 1) == 0)
BN_rand(largeb...er, 1, 1) == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
331 fatal("BN_rand failed");
never executed: fatal("BN_rand failed");
0
332 } else {
never executed: end of block
0
333 if (BN_copy(largebase, start) == NULL)
BN_copy(largeb...== ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
334 fatal("BN_copy: failed");
never executed: fatal("BN_copy: failed");
0
335 }
never executed: end of block
0
336-
337 /* ensure odd */-
338 if (BN_set_bit(largebase, 0) == 0)
BN_set_bit(largebase, 0) == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
339 fatal("BN_set_bit: failed");
never executed: fatal("BN_set_bit: failed");
0
340-
341 time(&time_start);-
342-
343 logit("%.24s Sieve next %u plus %u-bit", ctime(&time_start),-
344 largenumbers, power);-
345 debug2("start point: 0x%s", BN_bn2hex(largebase));-
346-
347 /*-
348 * TinySieve-
349 */-
350 for (i = 0; i < tinybits; i++) {
i < tinybitsDescription
TRUEnever evaluated
FALSEnever evaluated
0
351 if (BIT_TEST(TinySieve, i))
((TinySieve)[(...< ((i) & 31)))Description
TRUEnever evaluated
FALSEnever evaluated
0
352 continue; /* 2*i+3 is composite */
never executed: continue;
0
353-
354 /* The next tiny prime */-
355 t = 2 * i + 3;-
356-
357 /* Mark all multiples of t */-
358 for (j = i + t; j < tinybits; j += t)
j < tinybitsDescription
TRUEnever evaluated
FALSEnever evaluated
0
359 BIT_SET(TinySieve, j);
never executed: ((TinySieve)[(j)>>((3)+(2))] |= (1L << ((j) & 31)));
0
360-
361 sieve_large(t);-
362 }
never executed: end of block
0
363-
364 /*-
365 * Start the small block search at the next possible prime. To avoid-
366 * fencepost errors, the last pass is skipped.-
367 */-
368 for (smallbase = TINY_NUMBER + 3;-
369 smallbase < (SMALL_MAXIMUM - TINY_NUMBER);
smallbase < ((...) - (1UL<<16))Description
TRUEnever evaluated
FALSEnever evaluated
0
370 smallbase += TINY_NUMBER) {-
371 for (i = 0; i < tinybits; i++) {
i < tinybitsDescription
TRUEnever evaluated
FALSEnever evaluated
0
372 if (BIT_TEST(TinySieve, i))
((TinySieve)[(...< ((i) & 31)))Description
TRUEnever evaluated
FALSEnever evaluated
0
373 continue; /* 2*i+3 is composite */
never executed: continue;
0
374-
375 /* The next tiny prime */-
376 t = 2 * i + 3;-
377 r = smallbase % t;-
378-
379 if (r == 0) {
r == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
380 s = 0; /* t divides into smallbase exactly */-
381 } else {
never executed: end of block
0
382 /* smallbase+s is first entry divisible by t */-
383 s = t - r;-
384 }
never executed: end of block
0
385-
386 /*-
387 * The sieve omits even numbers, so ensure that-
388 * smallbase+s is odd. Then, step through the sieve-
389 * in increments of 2*t-
390 */-
391 if (s & 1)
s & 1Description
TRUEnever evaluated
FALSEnever evaluated
0
392 s += t; /* Make smallbase+s odd, and s even */
never executed: s += t;
0
393-
394 /* Mark all multiples of 2*t */-
395 for (s /= 2; s < smallbits; s += t)
s < smallbitsDescription
TRUEnever evaluated
FALSEnever evaluated
0
396 BIT_SET(SmallSieve, s);
never executed: ((SmallSieve)[(s)>>((3)+(2))] |= (1L << ((s) & 31)));
0
397 }
never executed: end of block
0
398-
399 /*-
400 * SmallSieve-
401 */-
402 for (i = 0; i < smallbits; i++) {
i < smallbitsDescription
TRUEnever evaluated
FALSEnever evaluated
0
403 if (BIT_TEST(SmallSieve, i))
((SmallSieve)[...< ((i) & 31)))Description
TRUEnever evaluated
FALSEnever evaluated
0
404 continue; /* 2*i+smallbase is composite */
never executed: continue;
0
405-
406 /* The next small prime */-
407 sieve_large((2 * i) + smallbase);-
408 }
never executed: end of block
0
409-
410 memset(SmallSieve, 0, smallwords << SHIFT_BYTE);-
411 }
never executed: end of block
0
412-
413 time(&time_stop);-
414-
415 logit("%.24s Sieved with %u small primes in %lld seconds",-
416 ctime(&time_stop), largetries, (long long)(time_stop - time_start));-
417-
418 for (j = r = 0; j < largebits; j++) {
j < largebitsDescription
TRUEnever evaluated
FALSEnever evaluated
0
419 if (BIT_TEST(LargeSieve, j))
((LargeSieve)[...< ((j) & 31)))Description
TRUEnever evaluated
FALSEnever evaluated
0
420 continue; /* Definitely composite, skip */
never executed: continue;
0
421-
422 debug2("test q = largebase+%u", 2 * j);-
423 if (BN_set_word(q, 2 * j) == 0)
BN_set_word(q, 2 * j) == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
424 fatal("BN_set_word failed");
never executed: fatal("BN_set_word failed");
0
425 if (BN_add(q, q, largebase) == 0)
BN_add(q, q, largebase) == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
426 fatal("BN_add failed");
never executed: fatal("BN_add failed");
0
427 if (qfileout(out, MODULI_TYPE_SOPHIE_GERMAIN,
qfileout(out, ... (0), q) == -1Description
TRUEnever evaluated
FALSEnever evaluated
0
428 MODULI_TESTS_SIEVE, largetries,
qfileout(out, ... (0), q) == -1Description
TRUEnever evaluated
FALSEnever evaluated
0
429 (power - 1) /* MSB */, (0), q) == -1) {
qfileout(out, ... (0), q) == -1Description
TRUEnever evaluated
FALSEnever evaluated
0
430 ret = -1;-
431 break;
never executed: break;
0
432 }-
433-
434 r++; /* count q */-
435 }
never executed: end of block
0
436-
437 time(&time_stop);-
438-
439 free(LargeSieve);-
440 free(SmallSieve);-
441 free(TinySieve);-
442-
443 logit("%.24s Found %u candidates", ctime(&time_stop), r);-
444-
445 return (ret);
never executed: return (ret);
0
446}-
447-
448static void-
449write_checkpoint(char *cpfile, u_int32_t lineno)-
450{-
451 FILE *fp;-
452 char tmp[PATH_MAX];-
453 int r;-
454-
455 r = snprintf(tmp, sizeof(tmp), "%s.XXXXXXXXXX", cpfile);-
456 if (r == -1 || r >= PATH_MAX) {
r == -1Description
TRUEnever evaluated
FALSEnever evaluated
r >= 4096Description
TRUEnever evaluated
FALSEnever evaluated
0
457 logit("write_checkpoint: temp pathname too long");-
458 return;
never executed: return;
0
459 }-
460 if ((r = mkstemp(tmp)) == -1) {
(r = mkstemp(tmp)) == -1Description
TRUEnever evaluated
FALSEnever evaluated
0
461 logit("mkstemp(%s): %s", tmp, strerror(errno));-
462 return;
never executed: return;
0
463 }-
464 if ((fp = fdopen(r, "w")) == NULL) {
(fp = fdopen(r...== ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
465 logit("write_checkpoint: fdopen: %s", strerror(errno));-
466 unlink(tmp);-
467 close(r);-
468 return;
never executed: return;
0
469 }-
470 if (fprintf(fp, "%lu\n", (unsigned long)lineno) > 0 && fclose(fp) == 0
fprintf(fp, "%...ng)lineno) > 0Description
TRUEnever evaluated
FALSEnever evaluated
fclose(fp) == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
471 && rename(tmp, cpfile) == 0)
rename(tmp, cpfile) == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
472 debug3("wrote checkpoint line %lu to '%s'",
never executed: debug3("wrote checkpoint line %lu to '%s'", (unsigned long)lineno, cpfile);
0
473 (unsigned long)lineno, cpfile);
never executed: debug3("wrote checkpoint line %lu to '%s'", (unsigned long)lineno, cpfile);
0
474 else-
475 logit("failed to write to checkpoint file '%s': %s", cpfile,
never executed: logit("failed to write to checkpoint file '%s': %s", cpfile, strerror( (*__errno_location ()) ));
0
476 strerror(errno));
never executed: logit("failed to write to checkpoint file '%s': %s", cpfile, strerror( (*__errno_location ()) ));
0
477}-
478-
479static unsigned long-
480read_checkpoint(char *cpfile)-
481{-
482 FILE *fp;-
483 unsigned long lineno = 0;-
484-
485 if ((fp = fopen(cpfile, "r")) == NULL)
(fp = fopen(cp...== ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
486 return 0;
never executed: return 0;
0
487 if (fscanf(fp, "%lu\n", &lineno) < 1)
fscanf(fp, "%l..., &lineno) < 1Description
TRUEnever evaluated
FALSEnever evaluated
0
488 logit("Failed to load checkpoint from '%s'", cpfile);
never executed: logit("Failed to load checkpoint from '%s'", cpfile);
0
489 else-
490 logit("Loaded checkpoint from '%s' line %lu", cpfile, lineno);
never executed: logit("Loaded checkpoint from '%s' line %lu", cpfile, lineno);
0
491 fclose(fp);-
492 return lineno;
never executed: return lineno;
0
493}-
494-
495static unsigned long-
496count_lines(FILE *f)-
497{-
498 unsigned long count = 0;-
499 char lp[QLINESIZE + 1];-
500-
501 if (fseek(f, 0, SEEK_SET) != 0) {
fseek(f, 0, 0 ) != 0Description
TRUEnever evaluated
FALSEnever evaluated
0
502 debug("input file is not seekable");-
503 return ULONG_MAX;
never executed: return (0x7fffffffffffffffL * 2UL + 1UL) ;
0
504 }-
505 while (fgets(lp, QLINESIZE + 1, f) != NULL)
fgets(lp, (100...!= ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
506 count++;
never executed: count++;
0
507 rewind(f);-
508 debug("input file has %lu lines", count);-
509 return count;
never executed: return count;
0
510}-
511-
512static char *-
513fmt_time(time_t seconds)-
514{-
515 int day, hr, min;-
516 static char buf[128];-
517-
518 min = (seconds / 60) % 60;-
519 hr = (seconds / 60 / 60) % 24;-
520 day = seconds / 60 / 60 / 24;-
521 if (day > 0)
day > 0Description
TRUEnever evaluated
FALSEnever evaluated
0
522 snprintf(buf, sizeof buf, "%dd %d:%02d", day, hr, min);
never executed: snprintf(buf, sizeof buf, "%dd %d:%02d", day, hr, min);
0
523 else-
524 snprintf(buf, sizeof buf, "%d:%02d", hr, min);
never executed: snprintf(buf, sizeof buf, "%d:%02d", hr, min);
0
525 return buf;
never executed: return buf;
0
526}-
527-
528static void-
529print_progress(unsigned long start_lineno, unsigned long current_lineno,-
530 unsigned long end_lineno)-
531{-
532 static time_t time_start, time_prev;-
533 time_t time_now, elapsed;-
534 unsigned long num_to_process, processed, remaining, percent, eta;-
535 double time_per_line;-
536 char *eta_str;-
537-
538 time_now = monotime();-
539 if (time_start == 0) {
time_start == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
540 time_start = time_prev = time_now;-
541 return;
never executed: return;
0
542 }-
543 /* print progress after 1m then once per 5m */-
544 if (time_now - time_prev < 5 * 60)
time_now - time_prev < 5 * 60Description
TRUEnever evaluated
FALSEnever evaluated
0
545 return;
never executed: return;
0
546 time_prev = time_now;-
547 elapsed = time_now - time_start;-
548 processed = current_lineno - start_lineno;-
549 remaining = end_lineno - current_lineno;-
550 num_to_process = end_lineno - start_lineno;-
551 time_per_line = (double)elapsed / processed;-
552 /* if we don't know how many we're processing just report count+time */-
553 time(&time_now);-
554 if (end_lineno == ULONG_MAX) {
end_lineno == ...L * 2UL + 1UL)Description
TRUEnever evaluated
FALSEnever evaluated
0
555 logit("%.24s processed %lu in %s", ctime(&time_now),-
556 processed, fmt_time(elapsed));-
557 return;
never executed: return;
0
558 }-
559 percent = 100 * processed / num_to_process;-
560 eta = time_per_line * remaining;-
561 eta_str = xstrdup(fmt_time(eta));-
562 logit("%.24s processed %lu of %lu (%lu%%) in %s, ETA %s",-
563 ctime(&time_now), processed, num_to_process, percent,-
564 fmt_time(elapsed), eta_str);-
565 free(eta_str);-
566}
never executed: end of block
0
567-
568/*-
569 * perform a Miller-Rabin primality test-
570 * on the list of candidates-
571 * (checking both q and p)-
572 * The result is a list of so-call "safe" primes-
573 */-
574int-
575prime_test(FILE *in, FILE *out, u_int32_t trials, u_int32_t generator_wanted,-
576 char *checkpoint_file, unsigned long start_lineno, unsigned long num_lines)-
577{-
578 BIGNUM *q, *p, *a;-
579 BN_CTX *ctx;-
580 char *cp, *lp;-
581 u_int32_t count_in = 0, count_out = 0, count_possible = 0;-
582 u_int32_t generator_known, in_tests, in_tries, in_type, in_size;-
583 unsigned long last_processed = 0, end_lineno;-
584 time_t time_start, time_stop;-
585 int res;-
586-
587 if (trials < TRIAL_MINIMUM) {
trials < (4)Description
TRUEnever evaluated
FALSEnever evaluated
0
588 error("Minimum primality trials is %d", TRIAL_MINIMUM);-
589 return (-1);
never executed: return (-1);
0
590 }-
591-
592 if (num_lines == 0)
num_lines == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
593 end_lineno = count_lines(in);
never executed: end_lineno = count_lines(in);
0
594 else-
595 end_lineno = start_lineno + num_lines;
never executed: end_lineno = start_lineno + num_lines;
0
596-
597 time(&time_start);-
598-
599 if ((p = BN_new()) == NULL)
(p = BN_new()) == ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
600 fatal("BN_new failed");
never executed: fatal("BN_new failed");
0
601 if ((q = BN_new()) == NULL)
(q = BN_new()) == ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
602 fatal("BN_new failed");
never executed: fatal("BN_new failed");
0
603 if ((ctx = BN_CTX_new()) == NULL)
(ctx = BN_CTX_...== ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
604 fatal("BN_CTX_new failed");
never executed: fatal("BN_CTX_new failed");
0
605-
606 debug2("%.24s Final %u Miller-Rabin trials (%x generator)",-
607 ctime(&time_start), trials, generator_wanted);-
608-
609 if (checkpoint_file != NULL)
checkpoint_file != ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
610 last_processed = read_checkpoint(checkpoint_file);
never executed: last_processed = read_checkpoint(checkpoint_file);
0
611 last_processed = start_lineno = MAXIMUM(last_processed, start_lineno);
((last_process...start_lineno))Description
TRUEnever evaluated
FALSEnever evaluated
0
612 if (end_lineno == ULONG_MAX)
end_lineno == ...L * 2UL + 1UL)Description
TRUEnever evaluated
FALSEnever evaluated
0
613 debug("process from line %lu from pipe", last_processed);
never executed: debug("process from line %lu from pipe", last_processed);
0
614 else-
615 debug("process from line %lu to line %lu", last_processed,
never executed: debug("process from line %lu to line %lu", last_processed, end_lineno);
0
616 end_lineno);
never executed: debug("process from line %lu to line %lu", last_processed, end_lineno);
0
617-
618 res = 0;-
619 lp = xmalloc(QLINESIZE + 1);-
620 while (fgets(lp, QLINESIZE + 1, in) != NULL && count_in < end_lineno) {
fgets(lp, (100...!= ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
count_in < end_linenoDescription
TRUEnever evaluated
FALSEnever evaluated
0
621 count_in++;-
622 if (count_in <= last_processed) {
count_in <= last_processedDescription
TRUEnever evaluated
FALSEnever evaluated
0
623 debug3("skipping line %u, before checkpoint or "-
624 "specified start line", count_in);-
625 continue;
never executed: continue;
0
626 }-
627 if (checkpoint_file != NULL)
checkpoint_file != ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
628 write_checkpoint(checkpoint_file, count_in);
never executed: write_checkpoint(checkpoint_file, count_in);
0
629 print_progress(start_lineno, count_in, end_lineno);-
630 if (strlen(lp) < 14 || *lp == '!' || *lp == '#') {
strlen(lp) < 14Description
TRUEnever evaluated
FALSEnever evaluated
*lp == '!'Description
TRUEnever evaluated
FALSEnever evaluated
*lp == '#'Description
TRUEnever evaluated
FALSEnever evaluated
0
631 debug2("%10u: comment or short line", count_in);-
632 continue;
never executed: continue;
0
633 }-
634-
635 /* XXX - fragile parser */-
636 /* time */-
637 cp = &lp[14]; /* (skip) */-
638-
639 /* type */-
640 in_type = strtoul(cp, &cp, 10);-
641-
642 /* tests */-
643 in_tests = strtoul(cp, &cp, 10);-
644-
645 if (in_tests & MODULI_TESTS_COMPOSITE) {
in_tests & (0x01)Description
TRUEnever evaluated
FALSEnever evaluated
0
646 debug2("%10u: known composite", count_in);-
647 continue;
never executed: continue;
0
648 }-
649-
650 /* tries */-
651 in_tries = strtoul(cp, &cp, 10);-
652-
653 /* size (most significant bit) */-
654 in_size = strtoul(cp, &cp, 10);-
655-
656 /* generator (hex) */-
657 generator_known = strtoul(cp, &cp, 16);-
658-
659 /* Skip white space */-
660 cp += strspn(cp, " ");-
661-
662 /* modulus (hex) */-
663 switch (in_type) {-
664 case MODULI_TYPE_SOPHIE_GERMAIN:
never executed: case (4):
0
665 debug2("%10u: (%u) Sophie-Germain", count_in, in_type);-
666 a = q;-
667 if (BN_hex2bn(&a, cp) == 0)
BN_hex2bn(&a, cp) == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
668 fatal("BN_hex2bn failed");
never executed: fatal("BN_hex2bn failed");
0
669 /* p = 2*q + 1 */-
670 if (BN_lshift(p, q, 1) == 0)
BN_lshift(p, q, 1) == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
671 fatal("BN_lshift failed");
never executed: fatal("BN_lshift failed");
0
672 if (BN_add_word(p, 1) == 0)
BN_add_word(p, 1) == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
673 fatal("BN_add_word failed");
never executed: fatal("BN_add_word failed");
0
674 in_size += 1;-
675 generator_known = 0;-
676 break;
never executed: break;
0
677 case MODULI_TYPE_UNSTRUCTURED:
never executed: case (1):
0
678 case MODULI_TYPE_SAFE:
never executed: case (2):
0
679 case MODULI_TYPE_SCHNORR:
never executed: case (3):
0
680 case MODULI_TYPE_STRONG:
never executed: case (5):
0
681 case MODULI_TYPE_UNKNOWN:
never executed: case (0):
0
682 debug2("%10u: (%u)", count_in, in_type);-
683 a = p;-
684 if (BN_hex2bn(&a, cp) == 0)
BN_hex2bn(&a, cp) == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
685 fatal("BN_hex2bn failed");
never executed: fatal("BN_hex2bn failed");
0
686 /* q = (p-1) / 2 */-
687 if (BN_rshift(q, p, 1) == 0)
BN_rshift(q, p, 1) == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
688 fatal("BN_rshift failed");
never executed: fatal("BN_rshift failed");
0
689 break;
never executed: break;
0
690 default:
never executed: default:
0
691 debug2("Unknown prime type");-
692 break;
never executed: break;
0
693 }-
694-
695 /*-
696 * due to earlier inconsistencies in interpretation, check-
697 * the proposed bit size.-
698 */-
699 if ((u_int32_t)BN_num_bits(p) != (in_size + 1)) {
(u_int32_t)BN_... (in_size + 1)Description
TRUEnever evaluated
FALSEnever evaluated
0
700 debug2("%10u: bit size %u mismatch", count_in, in_size);-
701 continue;
never executed: continue;
0
702 }-
703 if (in_size < QSIZE_MINIMUM) {
in_size < (511)Description
TRUEnever evaluated
FALSEnever evaluated
0
704 debug2("%10u: bit size %u too short", count_in, in_size);-
705 continue;
never executed: continue;
0
706 }-
707-
708 if (in_tests & MODULI_TESTS_MILLER_RABIN)
in_tests & (0x04)Description
TRUEnever evaluated
FALSEnever evaluated
0
709 in_tries += trials;
never executed: in_tries += trials;
0
710 else-
711 in_tries = trials;
never executed: in_tries = trials;
0
712-
713 /*-
714 * guess unknown generator-
715 */-
716 if (generator_known == 0) {
generator_known == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
717 if (BN_mod_word(p, 24) == 11)
BN_mod_word(p, 24) == 11Description
TRUEnever evaluated
FALSEnever evaluated
0
718 generator_known = 2;
never executed: generator_known = 2;
0
719 else if (BN_mod_word(p, 12) == 5)
BN_mod_word(p, 12) == 5Description
TRUEnever evaluated
FALSEnever evaluated
0
720 generator_known = 3;
never executed: generator_known = 3;
0
721 else {-
722 u_int32_t r = BN_mod_word(p, 10);-
723-
724 if (r == 3 || r == 7)
r == 3Description
TRUEnever evaluated
FALSEnever evaluated
r == 7Description
TRUEnever evaluated
FALSEnever evaluated
0
725 generator_known = 5;
never executed: generator_known = 5;
0
726 }
never executed: end of block
0
727 }-
728 /*-
729 * skip tests when desired generator doesn't match-
730 */-
731 if (generator_wanted > 0 &&
generator_wanted > 0Description
TRUEnever evaluated
FALSEnever evaluated
0
732 generator_wanted != generator_known) {
generator_want...enerator_knownDescription
TRUEnever evaluated
FALSEnever evaluated
0
733 debug2("%10u: generator %d != %d",-
734 count_in, generator_known, generator_wanted);-
735 continue;
never executed: continue;
0
736 }-
737-
738 /*-
739 * Primes with no known generator are useless for DH, so-
740 * skip those.-
741 */-
742 if (generator_known == 0) {
generator_known == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
743 debug2("%10u: no known generator", count_in);-
744 continue;
never executed: continue;
0
745 }-
746-
747 count_possible++;-
748-
749 /*-
750 * The (1/4)^N performance bound on Miller-Rabin is-
751 * extremely pessimistic, so don't spend a lot of time-
752 * really verifying that q is prime until after we know-
753 * that p is also prime. A single pass will weed out the-
754 * vast majority of composite q's.-
755 */-
756 if (BN_is_prime_ex(q, 1, ctx, NULL) <= 0) {
BN_is_prime_ex...id *)0) ) <= 0Description
TRUEnever evaluated
FALSEnever evaluated
0
757 debug("%10u: q failed first possible prime test",-
758 count_in);-
759 continue;
never executed: continue;
0
760 }-
761-
762 /*-
763 * q is possibly prime, so go ahead and really make sure-
764 * that p is prime. If it is, then we can go back and do-
765 * the same for q. If p is composite, chances are that-
766 * will show up on the first Rabin-Miller iteration so it-
767 * doesn't hurt to specify a high iteration count.-
768 */-
769 if (!BN_is_prime_ex(p, trials, ctx, NULL)) {
!BN_is_prime_e... ((void *)0) )Description
TRUEnever evaluated
FALSEnever evaluated
0
770 debug("%10u: p is not prime", count_in);-
771 continue;
never executed: continue;
0
772 }-
773 debug("%10u: p is almost certainly prime", count_in);-
774-
775 /* recheck q more rigorously */-
776 if (!BN_is_prime_ex(q, trials - 1, ctx, NULL)) {
!BN_is_prime_e... ((void *)0) )Description
TRUEnever evaluated
FALSEnever evaluated
0
777 debug("%10u: q is not prime", count_in);-
778 continue;
never executed: continue;
0
779 }-
780 debug("%10u: q is almost certainly prime", count_in);-
781-
782 if (qfileout(out, MODULI_TYPE_SAFE,
qfileout(out, ...ator_known, p)Description
TRUEnever evaluated
FALSEnever evaluated
0
783 in_tests | MODULI_TESTS_MILLER_RABIN,
qfileout(out, ...ator_known, p)Description
TRUEnever evaluated
FALSEnever evaluated
0
784 in_tries, in_size, generator_known, p)) {
qfileout(out, ...ator_known, p)Description
TRUEnever evaluated
FALSEnever evaluated
0
785 res = -1;-
786 break;
never executed: break;
0
787 }-
788-
789 count_out++;-
790 }
never executed: end of block
0
791-
792 time(&time_stop);-
793 free(lp);-
794 BN_free(p);-
795 BN_free(q);-
796 BN_CTX_free(ctx);-
797-
798 if (checkpoint_file != NULL)
checkpoint_file != ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
799 unlink(checkpoint_file);
never executed: unlink(checkpoint_file);
0
800-
801 logit("%.24s Found %u safe primes of %u candidates in %ld seconds",-
802 ctime(&time_stop), count_out, count_possible,-
803 (long) (time_stop - time_start));-
804-
805 return (res);
never executed: return (res);
0
806}-
807-
808#endif /* WITH_OPENSSL */-
Source codeSwitch to Preprocessed file
Generated by Squish Coco 4.2.2