Deleted Added
sdiff udiff text old ( 126274 ) new ( 137015 )
full compact
moduli.c (126274) moduli.c (137015)
1/* $OpenBSD: moduli.c,v 1.5 2003/12/22 09:16:57 djm Exp $ */
1/* $OpenBSD: moduli.c,v 1.9 2004/07/11 17:48:47 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

--- 23 unchanged lines hidden (view full) ---

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"
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

--- 23 unchanged lines hidden (view full) ---

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#include "moduli.h"
42#include "xmalloc.h"
43#include "log.h"
44
45#include <openssl/bn.h>
46
47/*
48 * File output defines
49 */
50
51/* need line long enough for largest moduli plus headers */
41#include "xmalloc.h"
42#include "log.h"
43
44#include <openssl/bn.h>
45
46/*
47 * File output defines
48 */
49
50/* need line long enough for largest moduli plus headers */
52#define QLINESIZE (100+8192)
51#define QLINESIZE (100+8192)
53
54/* Type: decimal.
55 * Specifies the internal structure of the prime modulus.
56 */
52
53/* Type: decimal.
54 * Specifies the internal structure of the prime modulus.
55 */
57#define QTYPE_UNKNOWN (0)
58#define QTYPE_UNSTRUCTURED (1)
59#define QTYPE_SAFE (2)
60#define QTYPE_SCHNOOR (3)
61#define QTYPE_SOPHIE_GERMAINE (4)
62#define QTYPE_STRONG (5)
56#define QTYPE_UNKNOWN (0)
57#define QTYPE_UNSTRUCTURED (1)
58#define QTYPE_SAFE (2)
59#define QTYPE_SCHNOOR (3)
60#define QTYPE_SOPHIE_GERMAIN (4)
61#define QTYPE_STRONG (5)
63
64/* Tests: decimal (bit field).
65 * Specifies the methods used in checking for primality.
66 * Usually, more than one test is used.
67 */
62
63/* Tests: decimal (bit field).
64 * Specifies the methods used in checking for primality.
65 * Usually, more than one test is used.
66 */
68#define QTEST_UNTESTED (0x00)
69#define QTEST_COMPOSITE (0x01)
70#define QTEST_SIEVE (0x02)
71#define QTEST_MILLER_RABIN (0x04)
72#define QTEST_JACOBI (0x08)
73#define QTEST_ELLIPTIC (0x10)
67#define QTEST_UNTESTED (0x00)
68#define QTEST_COMPOSITE (0x01)
69#define QTEST_SIEVE (0x02)
70#define QTEST_MILLER_RABIN (0x04)
71#define QTEST_JACOBI (0x08)
72#define QTEST_ELLIPTIC (0x10)
74
75/*
76 * Size: decimal.
77 * Specifies the number of the most significant bit (0 to M).
78 * WARNING: internally, usually 1 to N.
79 */
73
74/*
75 * Size: decimal.
76 * Specifies the number of the most significant bit (0 to M).
77 * WARNING: internally, usually 1 to N.
78 */
80#define QSIZE_MINIMUM (511)
79#define QSIZE_MINIMUM (511)
81
82/*
83 * Prime sieving defines
84 */
85
86/* Constant: assuming 8 bit bytes and 32 bit words */
80
81/*
82 * Prime sieving defines
83 */
84
85/* Constant: assuming 8 bit bytes and 32 bit words */
87#define SHIFT_BIT (3)
88#define SHIFT_BYTE (2)
89#define SHIFT_WORD (SHIFT_BIT+SHIFT_BYTE)
90#define SHIFT_MEGABYTE (20)
91#define SHIFT_MEGAWORD (SHIFT_MEGABYTE-SHIFT_BYTE)
86#define SHIFT_BIT (3)
87#define SHIFT_BYTE (2)
88#define SHIFT_WORD (SHIFT_BIT+SHIFT_BYTE)
89#define SHIFT_MEGABYTE (20)
90#define SHIFT_MEGAWORD (SHIFT_MEGABYTE-SHIFT_BYTE)
92
93/*
91
92/*
93 * Using virtual memory can cause thrashing. This should be the largest
94 * number that is supported without a large amount of disk activity --
95 * that would increase the run time from hours to days or weeks!
96 */
97#define LARGE_MINIMUM (8UL) /* megabytes */
98
99/*
100 * Do not increase this number beyond the unsigned integer bit size.
101 * Due to a multiple of 4, it must be LESS than 128 (yielding 2**30 bits).
102 */
103#define LARGE_MAXIMUM (127UL) /* megabytes */
104
105/*
94 * Constant: when used with 32-bit integers, the largest sieve prime
95 * has to be less than 2**32.
96 */
106 * Constant: when used with 32-bit integers, the largest sieve prime
107 * has to be less than 2**32.
108 */
97#define SMALL_MAXIMUM (0xffffffffUL)
109#define SMALL_MAXIMUM (0xffffffffUL)
98
99/* Constant: can sieve all primes less than 2**32, as 65537**2 > 2**32-1. */
110
111/* Constant: can sieve all primes less than 2**32, as 65537**2 > 2**32-1. */
100#define TINY_NUMBER (1UL<<16)
112#define TINY_NUMBER (1UL<<16)
101
102/* Ensure enough bit space for testing 2*q. */
103#define TEST_MAXIMUM (1UL<<16)
104#define TEST_MINIMUM (QSIZE_MINIMUM + 1)
105/* real TEST_MINIMUM (1UL << (SHIFT_WORD - TEST_POWER)) */
106#define TEST_POWER (3) /* 2**n, n < SHIFT_WORD */
107
108/* bit operations on 32-bit words */
109#define BIT_CLEAR(a,n) ((a)[(n)>>SHIFT_WORD] &= ~(1L << ((n) & 31)))
110#define BIT_SET(a,n) ((a)[(n)>>SHIFT_WORD] |= (1L << ((n) & 31)))
111#define BIT_TEST(a,n) ((a)[(n)>>SHIFT_WORD] & (1L << ((n) & 31)))
112
113/*
114 * Prime testing defines
115 */
116
113
114/* Ensure enough bit space for testing 2*q. */
115#define TEST_MAXIMUM (1UL<<16)
116#define TEST_MINIMUM (QSIZE_MINIMUM + 1)
117/* real TEST_MINIMUM (1UL << (SHIFT_WORD - TEST_POWER)) */
118#define TEST_POWER (3) /* 2**n, n < SHIFT_WORD */
119
120/* bit operations on 32-bit words */
121#define BIT_CLEAR(a,n) ((a)[(n)>>SHIFT_WORD] &= ~(1L << ((n) & 31)))
122#define BIT_SET(a,n) ((a)[(n)>>SHIFT_WORD] |= (1L << ((n) & 31)))
123#define BIT_TEST(a,n) ((a)[(n)>>SHIFT_WORD] & (1L << ((n) & 31)))
124
125/*
126 * Prime testing defines
127 */
128
129/* Minimum number of primality tests to perform */
130#define TRIAL_MINIMUM (4)
131
117/*
118 * Sieving data (XXX - move to struct)
119 */
120
121/* sieve 2**16 */
122static u_int32_t *TinySieve, tinybits;
123
124/* sieve 2**30 in 2**16 parts */
125static u_int32_t *SmallSieve, smallbits, smallbase;
126
127/* sieve relative to the initial value */
128static u_int32_t *LargeSieve, largewords, largetries, largenumbers;
129static u_int32_t largebits, largememory; /* megabytes */
130static BIGNUM *largebase;
131
132/*
133 * Sieving data (XXX - move to struct)
134 */
135
136/* sieve 2**16 */
137static u_int32_t *TinySieve, tinybits;
138
139/* sieve 2**30 in 2**16 parts */
140static u_int32_t *SmallSieve, smallbits, smallbase;
141
142/* sieve relative to the initial value */
143static u_int32_t *LargeSieve, largewords, largetries, largenumbers;
144static u_int32_t largebits, largememory; /* megabytes */
145static BIGNUM *largebase;
146
147int gen_candidates(FILE *, int, int, BIGNUM *);
148int prime_test(FILE *, FILE *, u_int32_t, u_int32_t);
132
133/*
134 * print moduli out in consistent form,
135 */
136static int
137qfileout(FILE * ofile, u_int32_t otype, u_int32_t otests, u_int32_t otries,
138 u_int32_t osize, u_int32_t ogenerator, BIGNUM * omodulus)
139{

--- 74 unchanged lines hidden (view full) ---

214
215 /* Mark all multiples of 4*s */
216 for (u /= 4; u < largebits; u += s)
217 BIT_SET(LargeSieve, u);
218 }
219}
220
221/*
149
150/*
151 * print moduli out in consistent form,
152 */
153static int
154qfileout(FILE * ofile, u_int32_t otype, u_int32_t otests, u_int32_t otries,
155 u_int32_t osize, u_int32_t ogenerator, BIGNUM * omodulus)
156{

--- 74 unchanged lines hidden (view full) ---

231
232 /* Mark all multiples of 4*s */
233 for (u /= 4; u < largebits; u += s)
234 BIT_SET(LargeSieve, u);
235 }
236}
237
238/*
222 * list candidates for Sophie-Germaine primes (where q = (p-1)/2)
239 * list candidates for Sophie-Germain primes (where q = (p-1)/2)
223 * to standard output.
224 * The list is checked against small known primes (less than 2**30).
225 */
226int
227gen_candidates(FILE *out, int memory, int power, BIGNUM *start)
228{
229 BIGNUM *q;
230 u_int32_t j, r, s, t;
231 u_int32_t smallwords = TINY_NUMBER >> 6;
232 u_int32_t tinywords = TINY_NUMBER >> 6;
233 time_t time_start, time_stop;
234 int i, ret = 0;
235
236 largememory = memory;
237
240 * to standard output.
241 * The list is checked against small known primes (less than 2**30).
242 */
243int
244gen_candidates(FILE *out, int memory, int power, BIGNUM *start)
245{
246 BIGNUM *q;
247 u_int32_t j, r, s, t;
248 u_int32_t smallwords = TINY_NUMBER >> 6;
249 u_int32_t tinywords = TINY_NUMBER >> 6;
250 time_t time_start, time_stop;
251 int i, ret = 0;
252
253 largememory = memory;
254
255 if (memory != 0 &&
256 (memory < LARGE_MINIMUM || memory > LARGE_MAXIMUM)) {
257 error("Invalid memory amount (min %ld, max %ld)",
258 LARGE_MINIMUM, LARGE_MAXIMUM);
259 return (-1);
260 }
261
238 /*
239 * Set power to the length in bits of the prime to be generated.
240 * This is changed to 1 less than the desired safe prime moduli p.
241 */
242 if (power > TEST_MAXIMUM) {
243 error("Too many bits: %u > %lu", power, TEST_MAXIMUM);
244 return (-1);
245 } else if (power < TEST_MINIMUM) {

--- 152 unchanged lines hidden (view full) ---

398
399 for (j = r = 0; j < largebits; j++) {
400 if (BIT_TEST(LargeSieve, j))
401 continue; /* Definitely composite, skip */
402
403 debug2("test q = largebase+%u", 2 * j);
404 BN_set_word(q, 2 * j);
405 BN_add(q, q, largebase);
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) {
267 error("Too many bits: %u > %lu", power, TEST_MAXIMUM);
268 return (-1);
269 } else if (power < TEST_MINIMUM) {

--- 152 unchanged lines hidden (view full) ---

422
423 for (j = r = 0; j < largebits; j++) {
424 if (BIT_TEST(LargeSieve, j))
425 continue; /* Definitely composite, skip */
426
427 debug2("test q = largebase+%u", 2 * j);
428 BN_set_word(q, 2 * j);
429 BN_add(q, q, largebase);
406 if (qfileout(out, QTYPE_SOPHIE_GERMAINE, QTEST_SIEVE,
430 if (qfileout(out, QTYPE_SOPHIE_GERMAIN, QTEST_SIEVE,
407 largetries, (power - 1) /* MSB */, (0), q) == -1) {
408 ret = -1;
409 break;
410 }
411
412 r++; /* count q */
413 }
414

--- 10 unchanged lines hidden (view full) ---

425
426/*
427 * perform a Miller-Rabin primality test
428 * on the list of candidates
429 * (checking both q and p)
430 * The result is a list of so-call "safe" primes
431 */
432int
431 largetries, (power - 1) /* MSB */, (0), q) == -1) {
432 ret = -1;
433 break;
434 }
435
436 r++; /* count q */
437 }
438

--- 10 unchanged lines hidden (view full) ---

449
450/*
451 * perform a Miller-Rabin primality test
452 * on the list of candidates
453 * (checking both q and p)
454 * The result is a list of so-call "safe" primes
455 */
456int
433prime_test(FILE *in, FILE *out, u_int32_t trials,
434 u_int32_t generator_wanted)
457prime_test(FILE *in, FILE *out, u_int32_t trials, u_int32_t generator_wanted)
435{
436 BIGNUM *q, *p, *a;
437 BN_CTX *ctx;
438 char *cp, *lp;
439 u_int32_t count_in = 0, count_out = 0, count_possible = 0;
440 u_int32_t generator_known, in_tests, in_tries, in_type, in_size;
441 time_t time_start, time_stop;
442 int res;
443
458{
459 BIGNUM *q, *p, *a;
460 BN_CTX *ctx;
461 char *cp, *lp;
462 u_int32_t count_in = 0, count_out = 0, count_possible = 0;
463 u_int32_t generator_known, in_tests, in_tries, in_type, in_size;
464 time_t time_start, time_stop;
465 int res;
466
467 if (trials < TRIAL_MINIMUM) {
468 error("Minimum primality trials is %d", TRIAL_MINIMUM);
469 return (-1);
470 }
471
444 time(&time_start);
445
446 p = BN_new();
447 q = BN_new();
448 ctx = BN_CTX_new();
449
450 debug2("%.24s Final %u Miller-Rabin trials (%x generator)",
451 ctime(&time_start), trials, generator_wanted);

--- 33 unchanged lines hidden (view full) ---

485 /* generator (hex) */
486 generator_known = strtoul(cp, &cp, 16);
487
488 /* Skip white space */
489 cp += strspn(cp, " ");
490
491 /* modulus (hex) */
492 switch (in_type) {
472 time(&time_start);
473
474 p = BN_new();
475 q = BN_new();
476 ctx = BN_CTX_new();
477
478 debug2("%.24s Final %u Miller-Rabin trials (%x generator)",
479 ctime(&time_start), trials, generator_wanted);

--- 33 unchanged lines hidden (view full) ---

513 /* generator (hex) */
514 generator_known = strtoul(cp, &cp, 16);
515
516 /* Skip white space */
517 cp += strspn(cp, " ");
518
519 /* modulus (hex) */
520 switch (in_type) {
493 case QTYPE_SOPHIE_GERMAINE:
494 debug2("%10u: (%u) Sophie-Germaine", count_in, in_type);
521 case QTYPE_SOPHIE_GERMAIN:
522 debug2("%10u: (%u) Sophie-Germain", count_in, in_type);
495 a = q;
496 BN_hex2bn(&a, cp);
497 /* p = 2*q + 1 */
498 BN_lshift(p, q, 1);
499 BN_add_word(p, 1);
500 in_size += 1;
501 generator_known = 0;
502 break;

--- 124 unchanged lines hidden --- 		523 a = q;
524 BN_hex2bn(&a, cp);
525 /* p = 2*q + 1 */
526 BN_lshift(p, q, 1);
527 BN_add_word(p, 1);
528 in_size += 1;
529 generator_known = 0;
530 break;

--- 124 unchanged lines hidden ---