Changeset View
Changeset View
Standalone View
Standalone View
moduli.c
/* $OpenBSD: moduli.c,v 1.32 2017/12/08 03:45:52 deraadt Exp $ */ | /* $OpenBSD: moduli.c,v 1.36 2019/10/04 03:26:58 dtucker Exp $ */ | ||||
/* | /* | ||||
* Copyright 1994 Phil Karn <karn@qualcomm.com> | * Copyright 1994 Phil Karn <karn@qualcomm.com> | ||||
* Copyright 1996-1998, 2003 William Allen Simpson <wsimpson@greendragon.com> | * Copyright 1996-1998, 2003 William Allen Simpson <wsimpson@greendragon.com> | ||||
* Copyright 2000 Niels Provos <provos@citi.umich.edu> | * Copyright 2000 Niels Provos <provos@citi.umich.edu> | ||||
* All rights reserved. | * All rights reserved. | ||||
* | * | ||||
* Redistribution and use in source and binary forms, with or without | * Redistribution and use in source and binary forms, with or without | ||||
* modification, are permitted provided that the following conditions | * modification, are permitted provided that the following conditions | ||||
▲ Show 20 Lines • Show All 144 Lines • ▼ Show 20 Lines | qfileout(FILE * ofile, u_int32_t otype, u_int32_t otests, u_int32_t otries, | ||||
u_int32_t osize, u_int32_t ogenerator, BIGNUM * omodulus) | u_int32_t osize, u_int32_t ogenerator, BIGNUM * omodulus) | ||||
{ | { | ||||
struct tm *gtm; | struct tm *gtm; | ||||
time_t time_now; | time_t time_now; | ||||
int res; | int res; | ||||
time(&time_now); | time(&time_now); | ||||
gtm = gmtime(&time_now); | gtm = gmtime(&time_now); | ||||
if (gtm == NULL) | |||||
return -1; | |||||
res = fprintf(ofile, "%04d%02d%02d%02d%02d%02d %u %u %u %u %x ", | res = fprintf(ofile, "%04d%02d%02d%02d%02d%02d %u %u %u %u %x ", | ||||
gtm->tm_year + 1900, gtm->tm_mon + 1, gtm->tm_mday, | gtm->tm_year + 1900, gtm->tm_mon + 1, gtm->tm_mday, | ||||
gtm->tm_hour, gtm->tm_min, gtm->tm_sec, | gtm->tm_hour, gtm->tm_min, gtm->tm_sec, | ||||
otype, otests, otries, osize, ogenerator); | otype, otests, otries, osize, ogenerator); | ||||
if (res < 0) | if (res < 0) | ||||
return (-1); | return (-1); | ||||
▲ Show 20 Lines • Show All 278 Lines • ▼ Show 20 Lines | |||||
static void | static void | ||||
write_checkpoint(char *cpfile, u_int32_t lineno) | write_checkpoint(char *cpfile, u_int32_t lineno) | ||||
{ | { | ||||
FILE *fp; | FILE *fp; | ||||
char tmp[PATH_MAX]; | char tmp[PATH_MAX]; | ||||
int r; | int r; | ||||
r = snprintf(tmp, sizeof(tmp), "%s.XXXXXXXXXX", cpfile); | r = snprintf(tmp, sizeof(tmp), "%s.XXXXXXXXXX", cpfile); | ||||
if (r == -1 || r >= PATH_MAX) { | if (r < 0 || r >= PATH_MAX) { | ||||
logit("write_checkpoint: temp pathname too long"); | logit("write_checkpoint: temp pathname too long"); | ||||
return; | return; | ||||
} | } | ||||
if ((r = mkstemp(tmp)) == -1) { | if ((r = mkstemp(tmp)) == -1) { | ||||
logit("mkstemp(%s): %s", tmp, strerror(errno)); | logit("mkstemp(%s): %s", tmp, strerror(errno)); | ||||
return; | return; | ||||
} | } | ||||
if ((fp = fdopen(r, "w")) == NULL) { | if ((fp = fdopen(r, "w")) == NULL) { | ||||
▲ Show 20 Lines • Show All 112 Lines • ▼ Show 20 Lines | |||||
{ | { | ||||
BIGNUM *q, *p, *a; | BIGNUM *q, *p, *a; | ||||
BN_CTX *ctx; | BN_CTX *ctx; | ||||
char *cp, *lp; | char *cp, *lp; | ||||
u_int32_t count_in = 0, count_out = 0, count_possible = 0; | u_int32_t count_in = 0, count_out = 0, count_possible = 0; | ||||
u_int32_t generator_known, in_tests, in_tries, in_type, in_size; | u_int32_t generator_known, in_tests, in_tries, in_type, in_size; | ||||
unsigned long last_processed = 0, end_lineno; | unsigned long last_processed = 0, end_lineno; | ||||
time_t time_start, time_stop; | time_t time_start, time_stop; | ||||
int res; | int res, is_prime; | ||||
if (trials < TRIAL_MINIMUM) { | if (trials < TRIAL_MINIMUM) { | ||||
error("Minimum primality trials is %d", TRIAL_MINIMUM); | error("Minimum primality trials is %d", TRIAL_MINIMUM); | ||||
return (-1); | return (-1); | ||||
} | } | ||||
if (num_lines == 0) | if (num_lines == 0) | ||||
end_lineno = count_lines(in); | end_lineno = count_lines(in); | ||||
▲ Show 20 Lines • Show All 117 Lines • ▼ Show 20 Lines | else | ||||
in_tries = trials; | in_tries = trials; | ||||
/* | /* | ||||
* guess unknown generator | * guess unknown generator | ||||
*/ | */ | ||||
if (generator_known == 0) { | if (generator_known == 0) { | ||||
if (BN_mod_word(p, 24) == 11) | if (BN_mod_word(p, 24) == 11) | ||||
generator_known = 2; | generator_known = 2; | ||||
else if (BN_mod_word(p, 12) == 5) | |||||
generator_known = 3; | |||||
else { | else { | ||||
u_int32_t r = BN_mod_word(p, 10); | u_int32_t r = BN_mod_word(p, 10); | ||||
if (r == 3 || r == 7) | if (r == 3 || r == 7) | ||||
generator_known = 5; | generator_known = 5; | ||||
} | } | ||||
} | } | ||||
/* | /* | ||||
Show All 19 Lines | while (fgets(lp, QLINESIZE + 1, in) != NULL && count_in < end_lineno) { | ||||
/* | /* | ||||
* The (1/4)^N performance bound on Miller-Rabin is | * The (1/4)^N performance bound on Miller-Rabin is | ||||
* extremely pessimistic, so don't spend a lot of time | * extremely pessimistic, so don't spend a lot of time | ||||
* really verifying that q is prime until after we know | * really verifying that q is prime until after we know | ||||
* that p is also prime. A single pass will weed out the | * that p is also prime. A single pass will weed out the | ||||
* vast majority of composite q's. | * vast majority of composite q's. | ||||
*/ | */ | ||||
if (BN_is_prime_ex(q, 1, ctx, NULL) <= 0) { | is_prime = BN_is_prime_ex(q, 1, ctx, NULL); | ||||
if (is_prime < 0) | |||||
fatal("BN_is_prime_ex failed"); | |||||
if (is_prime == 0) { | |||||
debug("%10u: q failed first possible prime test", | debug("%10u: q failed first possible prime test", | ||||
count_in); | count_in); | ||||
continue; | continue; | ||||
} | } | ||||
/* | /* | ||||
* q is possibly prime, so go ahead and really make sure | * q is possibly prime, so go ahead and really make sure | ||||
* that p is prime. If it is, then we can go back and do | * that p is prime. If it is, then we can go back and do | ||||
* the same for q. If p is composite, chances are that | * the same for q. If p is composite, chances are that | ||||
* will show up on the first Rabin-Miller iteration so it | * will show up on the first Rabin-Miller iteration so it | ||||
* doesn't hurt to specify a high iteration count. | * doesn't hurt to specify a high iteration count. | ||||
*/ | */ | ||||
if (!BN_is_prime_ex(p, trials, ctx, NULL)) { | is_prime = BN_is_prime_ex(p, trials, ctx, NULL); | ||||
if (is_prime < 0) | |||||
fatal("BN_is_prime_ex failed"); | |||||
if (is_prime == 0) { | |||||
debug("%10u: p is not prime", count_in); | debug("%10u: p is not prime", count_in); | ||||
continue; | continue; | ||||
} | } | ||||
debug("%10u: p is almost certainly prime", count_in); | debug("%10u: p is almost certainly prime", count_in); | ||||
/* recheck q more rigorously */ | /* recheck q more rigorously */ | ||||
if (!BN_is_prime_ex(q, trials - 1, ctx, NULL)) { | is_prime = BN_is_prime_ex(q, trials - 1, ctx, NULL); | ||||
if (is_prime < 0) | |||||
fatal("BN_is_prime_ex failed"); | |||||
if (is_prime == 0) { | |||||
debug("%10u: q is not prime", count_in); | debug("%10u: q is not prime", count_in); | ||||
continue; | continue; | ||||
} | } | ||||
debug("%10u: q is almost certainly prime", count_in); | debug("%10u: q is almost certainly prime", count_in); | ||||
if (qfileout(out, MODULI_TYPE_SAFE, | if (qfileout(out, MODULI_TYPE_SAFE, | ||||
in_tests | MODULI_TESTS_MILLER_RABIN, | in_tests | MODULI_TESTS_MILLER_RABIN, | ||||
in_tries, in_size, generator_known, p)) { | in_tries, in_size, generator_known, p)) { | ||||
Show All 24 Lines |