summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn
diff options
context:
space:
mode:
authortb <>2023-08-03 18:53:56 +0000
committertb <>2023-08-03 18:53:56 +0000
commite680fe5b2098d1406fab3bb3994254f026651090 (patch)
tree3779d2c9bdc12cd8a0d0eb7981bf515d6e27b344 /src/lib/libcrypto/bn
parent9110c93cd11bc18d800c645352c10a57e2ceea4b (diff)
downloadopenbsd-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.c11
-rw-r--r--src/lib/libcrypto/bn/bn_local.h5
-rw-r--r--src/lib/libcrypto/bn/bn_mod_sqrt.c10
-rw-r--r--src/lib/libcrypto/bn/bn_rand.c37
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
276int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom); 276int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom);
277int bn_rand_interval(BIGNUM *rnd, const BIGNUM *lower_inc, const BIGNUM *upper_exc); 277int bn_rand_in_range(BIGNUM *rnd, const BIGNUM *lower_inc, const BIGNUM *upper_exc);
278int bn_rand_interval(BIGNUM *rnd, BN_ULONG lower_word, const BIGNUM *upper_exc);
278 279
279void BN_init(BIGNUM *); 280void 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
237bn_mod_sqrt_find_sylow_generator(BIGNUM *out_generator, const BIGNUM *p, 237bn_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)
284LCRYPTO_ALIAS(BN_rand_range); 284LCRYPTO_ALIAS(BN_rand_range);
285 285
286int 286int
287bn_rand_interval(BIGNUM *rnd, const BIGNUM *lower_inc, const BIGNUM *upper_exc) 287bn_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
309int
310bn_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