diff options
author | tb <> | 2023-08-03 18:53:56 +0000 |
---|---|---|
committer | tb <> | 2023-08-03 18:53:56 +0000 |
commit | e680fe5b2098d1406fab3bb3994254f026651090 (patch) | |
tree | 3779d2c9bdc12cd8a0d0eb7981bf515d6e27b344 /src/lib/libcrypto/bn | |
parent | 9110c93cd11bc18d800c645352c10a57e2ceea4b (diff) | |
download | openbsd-e680fe5b2098d1406fab3bb3994254f026651090.tar.gz openbsd-e680fe5b2098d1406fab3bb3994254f026651090.tar.bz2 openbsd-e680fe5b2098d1406fab3bb3994254f026651090.zip |
Make the bn_rand_interval() API a bit more ergonomic
Provide bn_rand_in_range() which is a slightly tweaked version of what was
previously called bn_rand_range().
The way bn_rand_range() is called in libcrypto, the lower bound is always
expressible as a word. In fact, most of the time it is 1, the DH code uses
a 2, the MR tests in BPSW use 3 and an exceptinally high number appears in
the Tonelli-Shanks implementation where we use 32. Converting these lower
bounds to BIGNUMs on the call site is annoying so let bn_rand_interval()
do that internally and route that through bn_rand_in_range(). This way we
can avoid using BN_sub_word().
Adjust the bn_isqrt() test to use bn_rand_in_range() since that's the
only caller that uses actual BIGNUMs as lower bounds.
ok jsing
Diffstat (limited to 'src/lib/libcrypto/bn')
-rw-r--r-- | src/lib/libcrypto/bn/bn_bpsw.c | 11 | ||||
-rw-r--r-- | src/lib/libcrypto/bn/bn_local.h | 5 | ||||
-rw-r--r-- | src/lib/libcrypto/bn/bn_mod_sqrt.c | 10 | ||||
-rw-r--r-- | src/lib/libcrypto/bn/bn_rand.c | 37 |
4 files changed, 36 insertions, 27 deletions
diff --git a/src/lib/libcrypto/bn/bn_bpsw.c b/src/lib/libcrypto/bn/bn_bpsw.c index 82a4e87146..14f2800ad3 100644 --- a/src/lib/libcrypto/bn/bn_bpsw.c +++ b/src/lib/libcrypto/bn/bn_bpsw.c | |||
@@ -1,4 +1,4 @@ | |||
1 | /* $OpenBSD: bn_bpsw.c,v 1.10 2023/05/10 21:05:24 tb Exp $ */ | 1 | /* $OpenBSD: bn_bpsw.c,v 1.11 2023/08/03 18:53:55 tb Exp $ */ |
2 | /* | 2 | /* |
3 | * Copyright (c) 2022 Martin Grenouilloux <martin.grenouilloux@lse.epita.fr> | 3 | * Copyright (c) 2022 Martin Grenouilloux <martin.grenouilloux@lse.epita.fr> |
4 | * Copyright (c) 2022 Theo Buehler <tb@openbsd.org> | 4 | * Copyright (c) 2022 Theo Buehler <tb@openbsd.org> |
@@ -385,7 +385,7 @@ bn_miller_rabin(int *is_pseudoprime, const BIGNUM *n, BN_CTX *ctx, | |||
385 | size_t rounds) | 385 | size_t rounds) |
386 | { | 386 | { |
387 | BN_MONT_CTX *mctx = NULL; | 387 | BN_MONT_CTX *mctx = NULL; |
388 | BIGNUM *base, *k, *n_minus_one, *three; | 388 | BIGNUM *base, *k, *n_minus_one; |
389 | size_t i; | 389 | size_t i; |
390 | int s; | 390 | int s; |
391 | int ret = 0; | 391 | int ret = 0; |
@@ -398,8 +398,6 @@ bn_miller_rabin(int *is_pseudoprime, const BIGNUM *n, BN_CTX *ctx, | |||
398 | goto err; | 398 | goto err; |
399 | if ((n_minus_one = BN_CTX_get(ctx)) == NULL) | 399 | if ((n_minus_one = BN_CTX_get(ctx)) == NULL) |
400 | goto err; | 400 | goto err; |
401 | if ((three = BN_CTX_get(ctx)) == NULL) | ||
402 | goto err; | ||
403 | 401 | ||
404 | if (BN_is_word(n, 2) || BN_is_word(n, 3)) { | 402 | if (BN_is_word(n, 2) || BN_is_word(n, 3)) { |
405 | *is_pseudoprime = 1; | 403 | *is_pseudoprime = 1; |
@@ -451,11 +449,8 @@ bn_miller_rabin(int *is_pseudoprime, const BIGNUM *n, BN_CTX *ctx, | |||
451 | * risk of false positives in BPSW. | 449 | * risk of false positives in BPSW. |
452 | */ | 450 | */ |
453 | 451 | ||
454 | if (!BN_set_word(three, 3)) | ||
455 | goto err; | ||
456 | |||
457 | for (i = 0; i < rounds; i++) { | 452 | for (i = 0; i < rounds; i++) { |
458 | if (!bn_rand_interval(base, three, n_minus_one)) | 453 | if (!bn_rand_interval(base, 3, n_minus_one)) |
459 | goto err; | 454 | goto err; |
460 | 455 | ||
461 | if (!bn_fermat(is_pseudoprime, n, n_minus_one, k, s, base, ctx, | 456 | if (!bn_fermat(is_pseudoprime, n, n_minus_one, k, s, base, ctx, |
diff --git a/src/lib/libcrypto/bn/bn_local.h b/src/lib/libcrypto/bn/bn_local.h index 9447ed4f4c..5b7e852d70 100644 --- a/src/lib/libcrypto/bn/bn_local.h +++ b/src/lib/libcrypto/bn/bn_local.h | |||
@@ -1,4 +1,4 @@ | |||
1 | /* $OpenBSD: bn_local.h,v 1.32 2023/08/02 08:44:38 tb Exp $ */ | 1 | /* $OpenBSD: bn_local.h,v 1.33 2023/08/03 18:53:55 tb Exp $ */ |
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | 2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) |
3 | * All rights reserved. | 3 | * All rights reserved. |
4 | * | 4 | * |
@@ -274,7 +274,8 @@ void bn_div_rem_words(BN_ULONG h, BN_ULONG l, BN_ULONG d, BN_ULONG *out_q, | |||
274 | BN_ULONG *out_r); | 274 | BN_ULONG *out_r); |
275 | 275 | ||
276 | int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom); | 276 | int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom); |
277 | int bn_rand_interval(BIGNUM *rnd, const BIGNUM *lower_inc, const BIGNUM *upper_exc); | 277 | int bn_rand_in_range(BIGNUM *rnd, const BIGNUM *lower_inc, const BIGNUM *upper_exc); |
278 | int bn_rand_interval(BIGNUM *rnd, BN_ULONG lower_word, const BIGNUM *upper_exc); | ||
278 | 279 | ||
279 | void BN_init(BIGNUM *); | 280 | void BN_init(BIGNUM *); |
280 | 281 | ||
diff --git a/src/lib/libcrypto/bn/bn_mod_sqrt.c b/src/lib/libcrypto/bn/bn_mod_sqrt.c index bdd5b2cdba..280002cc48 100644 --- a/src/lib/libcrypto/bn/bn_mod_sqrt.c +++ b/src/lib/libcrypto/bn/bn_mod_sqrt.c | |||
@@ -1,4 +1,4 @@ | |||
1 | /* $OpenBSD: bn_mod_sqrt.c,v 1.2 2023/07/08 12:21:58 beck Exp $ */ | 1 | /* $OpenBSD: bn_mod_sqrt.c,v 1.3 2023/08/03 18:53:55 tb Exp $ */ |
2 | 2 | ||
3 | /* | 3 | /* |
4 | * Copyright (c) 2022 Theo Buehler <tb@openbsd.org> | 4 | * Copyright (c) 2022 Theo Buehler <tb@openbsd.org> |
@@ -237,7 +237,7 @@ static int | |||
237 | bn_mod_sqrt_find_sylow_generator(BIGNUM *out_generator, const BIGNUM *p, | 237 | bn_mod_sqrt_find_sylow_generator(BIGNUM *out_generator, const BIGNUM *p, |
238 | const BIGNUM *q, BN_CTX *ctx) | 238 | const BIGNUM *q, BN_CTX *ctx) |
239 | { | 239 | { |
240 | BIGNUM *n, *p_abs, *thirty_two; | 240 | BIGNUM *n, *p_abs; |
241 | int i, is_non_residue; | 241 | int i, is_non_residue; |
242 | int ret = 0; | 242 | int ret = 0; |
243 | 243 | ||
@@ -245,8 +245,6 @@ bn_mod_sqrt_find_sylow_generator(BIGNUM *out_generator, const BIGNUM *p, | |||
245 | 245 | ||
246 | if ((n = BN_CTX_get(ctx)) == NULL) | 246 | if ((n = BN_CTX_get(ctx)) == NULL) |
247 | goto err; | 247 | goto err; |
248 | if ((thirty_two = BN_CTX_get(ctx)) == NULL) | ||
249 | goto err; | ||
250 | if ((p_abs = BN_CTX_get(ctx)) == NULL) | 248 | if ((p_abs = BN_CTX_get(ctx)) == NULL) |
251 | goto err; | 249 | goto err; |
252 | 250 | ||
@@ -259,14 +257,12 @@ bn_mod_sqrt_find_sylow_generator(BIGNUM *out_generator, const BIGNUM *p, | |||
259 | goto found; | 257 | goto found; |
260 | } | 258 | } |
261 | 259 | ||
262 | if (!BN_set_word(thirty_two, 32)) | ||
263 | goto err; | ||
264 | if (!bn_copy(p_abs, p)) | 260 | if (!bn_copy(p_abs, p)) |
265 | goto err; | 261 | goto err; |
266 | BN_set_negative(p_abs, 0); | 262 | BN_set_negative(p_abs, 0); |
267 | 263 | ||
268 | for (i = 0; i < 128; i++) { | 264 | for (i = 0; i < 128; i++) { |
269 | if (!bn_rand_interval(n, thirty_two, p_abs)) | 265 | if (!bn_rand_interval(n, 32, p_abs)) |
270 | goto err; | 266 | goto err; |
271 | if (!bn_mod_sqrt_n_is_non_residue(&is_non_residue, n, p, ctx)) | 267 | if (!bn_mod_sqrt_n_is_non_residue(&is_non_residue, n, p, ctx)) |
272 | goto err; | 268 | goto err; |
diff --git a/src/lib/libcrypto/bn/bn_rand.c b/src/lib/libcrypto/bn/bn_rand.c index f68913473f..a5b163c820 100644 --- a/src/lib/libcrypto/bn/bn_rand.c +++ b/src/lib/libcrypto/bn/bn_rand.c | |||
@@ -1,4 +1,4 @@ | |||
1 | /* $OpenBSD: bn_rand.c,v 1.28 2023/07/08 12:21:58 beck Exp $ */ | 1 | /* $OpenBSD: bn_rand.c,v 1.29 2023/08/03 18:53:55 tb Exp $ */ |
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | 2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) |
3 | * All rights reserved. | 3 | * All rights reserved. |
4 | * | 4 | * |
@@ -284,29 +284,46 @@ BN_rand_range(BIGNUM *r, const BIGNUM *range) | |||
284 | LCRYPTO_ALIAS(BN_rand_range); | 284 | LCRYPTO_ALIAS(BN_rand_range); |
285 | 285 | ||
286 | int | 286 | int |
287 | bn_rand_interval(BIGNUM *rnd, const BIGNUM *lower_inc, const BIGNUM *upper_exc) | 287 | bn_rand_in_range(BIGNUM *rnd, const BIGNUM *lower_inc, const BIGNUM *upper_exc) |
288 | { | 288 | { |
289 | BIGNUM *len = NULL; | 289 | BIGNUM *len; |
290 | int ret = 0; | 290 | int ret = 0; |
291 | 291 | ||
292 | if (BN_cmp(lower_inc, upper_exc) >= 0) | ||
293 | goto err; | ||
294 | |||
295 | if ((len = BN_new()) == NULL) | 292 | if ((len = BN_new()) == NULL) |
296 | goto err; | 293 | goto err; |
297 | |||
298 | if (!BN_sub(len, upper_exc, lower_inc)) | 294 | if (!BN_sub(len, upper_exc, lower_inc)) |
299 | goto err; | 295 | goto err; |
300 | 296 | if (!BN_rand_range(rnd, len)) | |
301 | if (!bn_rand_range(0, rnd, len)) | ||
302 | goto err; | 297 | goto err; |
303 | |||
304 | if (!BN_add(rnd, rnd, lower_inc)) | 298 | if (!BN_add(rnd, rnd, lower_inc)) |
305 | goto err; | 299 | goto err; |
306 | 300 | ||
307 | ret = 1; | 301 | ret = 1; |
302 | |||
308 | err: | 303 | err: |
309 | BN_free(len); | 304 | BN_free(len); |
305 | |||
306 | return ret; | ||
307 | } | ||
308 | |||
309 | int | ||
310 | bn_rand_interval(BIGNUM *rnd, BN_ULONG lower_word, const BIGNUM *upper_exc) | ||
311 | { | ||
312 | BIGNUM *lower_inc = NULL; | ||
313 | int ret = 0; | ||
314 | |||
315 | if ((lower_inc = BN_new()) == NULL) | ||
316 | goto err; | ||
317 | if (!BN_set_word(lower_inc, lower_word)) | ||
318 | goto err; | ||
319 | if (!bn_rand_in_range(rnd, lower_inc, upper_exc)) | ||
320 | goto err; | ||
321 | |||
322 | ret = 1; | ||
323 | |||
324 | err: | ||
325 | BN_free(lower_inc); | ||
326 | |||
310 | return ret; | 327 | return ret; |
311 | } | 328 | } |
312 | 329 | ||