diff options
author | jsing <> | 2023-03-07 06:19:44 +0000 |
---|---|---|
committer | jsing <> | 2023-03-07 06:19:44 +0000 |
commit | 4320ee92fb55c991eec4cdc78f60c762533babb7 (patch) | |
tree | 6a167a9b374a6e5a6fc9fb06d04f4cff22727f76 /src/lib | |
parent | 9d27b98c03802e34828891a1a14e03f9ff09e110 (diff) | |
download | openbsd-4320ee92fb55c991eec4cdc78f60c762533babb7.tar.gz openbsd-4320ee92fb55c991eec4cdc78f60c762533babb7.tar.bz2 openbsd-4320ee92fb55c991eec4cdc78f60c762533babb7.zip |
Implement bn_montgomery_multiply()
Provide a constant-time-style Montgomery multiplication implementation.
Use this in place of the assembly bn_mul_mont() on platforms that either
do not have an assembly implementation or have not compiled it in.
Also use this as the fallback version for bn_mul_mont(), rather than
falling back to a non-constant time implementation.
ok beck@ tb@
Diffstat (limited to 'src/lib')
-rw-r--r-- | src/lib/libcrypto/bn/bn_mont.c | 89 |
1 files changed, 86 insertions, 3 deletions
diff --git a/src/lib/libcrypto/bn/bn_mont.c b/src/lib/libcrypto/bn/bn_mont.c index d2ca4404f9..e92ceae5f4 100644 --- a/src/lib/libcrypto/bn/bn_mont.c +++ b/src/lib/libcrypto/bn/bn_mont.c | |||
@@ -1,4 +1,4 @@ | |||
1 | /* $OpenBSD: bn_mont.c,v 1.49 2023/03/07 06:15:09 jsing Exp $ */ | 1 | /* $OpenBSD: bn_mont.c,v 1.50 2023/03/07 06:19:44 jsing 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 | * |
@@ -336,12 +336,95 @@ bn_mod_mul_montgomery_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, | |||
336 | return ret; | 336 | return ret; |
337 | } | 337 | } |
338 | 338 | ||
339 | /* | ||
340 | * bn_montgomery_multiply_words() computes r = aR * bR * R^-1 = abR for the | ||
341 | * given word arrays. The caller must ensure that rp, ap, bp and np are all | ||
342 | * n_len words in length, while tp must be n_len * 2 + 2 words in length. | ||
343 | */ | ||
344 | void | ||
345 | bn_montgomery_multiply_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp, | ||
346 | const BN_ULONG *np, BN_ULONG *tp, BN_ULONG n0, int n_len) | ||
347 | { | ||
348 | BN_ULONG carry, mask; | ||
349 | int i; | ||
350 | |||
351 | for (i = 0; i < n_len * 2 + 2; i++) | ||
352 | tp[i] = 0; | ||
353 | |||
354 | for (i = 0; i < n_len; i++) { | ||
355 | carry = bn_mul_add_words(tp, ap, n_len, bp[i]); | ||
356 | bn_addw(tp[n_len], carry, &tp[n_len + 1], &tp[n_len]); | ||
357 | |||
358 | carry = bn_mul_add_words(tp, np, n_len, tp[0] * n0); | ||
359 | bn_addw(tp[n_len], carry, &carry, &tp[n_len]); | ||
360 | bn_addw(tp[n_len + 1], carry, &carry, &tp[n_len + 1]); | ||
361 | |||
362 | tp++; | ||
363 | } | ||
364 | |||
365 | /* | ||
366 | * The output is now in the range of [0, 2N). Attempt to reduce once by | ||
367 | * subtracting the modulus. If the reduction was necessary then the | ||
368 | * result is already in r, otherwise copy the value prior to reduction | ||
369 | * from tp. | ||
370 | */ | ||
371 | mask = bn_ct_ne_zero(tp[n_len]) - bn_sub_words(rp, tp, np, n_len); | ||
372 | |||
373 | for (i = 0; i < n_len; i++) { | ||
374 | *rp = (*rp & ~mask) | (*tp & mask); | ||
375 | rp++; | ||
376 | tp++; | ||
377 | } | ||
378 | } | ||
379 | |||
380 | /* | ||
381 | * bn_montgomery_multiply() computes r = aR * bR * R^-1 = abR for the given | ||
382 | * BIGNUMs. The caller must ensure that the modulus is two or more words in | ||
383 | * length and that a and b have the same number of words as the modulus. | ||
384 | */ | ||
385 | int | ||
386 | bn_montgomery_multiply(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, | ||
387 | BN_MONT_CTX *mctx, BN_CTX *ctx) | ||
388 | { | ||
389 | BIGNUM *t; | ||
390 | int ret = 0; | ||
391 | |||
392 | BN_CTX_start(ctx); | ||
393 | |||
394 | if (mctx->N.top <= 1 || a->top != mctx->N.top || b->top != mctx->N.top) | ||
395 | goto err; | ||
396 | if (!bn_wexpand(r, mctx->N.top)) | ||
397 | goto err; | ||
398 | |||
399 | if ((t = BN_CTX_get(ctx)) == NULL) | ||
400 | goto err; | ||
401 | if (!bn_wexpand(t, mctx->N.top * 2 + 2)) | ||
402 | goto err; | ||
403 | |||
404 | bn_montgomery_multiply_words(r->d, a->d, b->d, mctx->N.d, t->d, | ||
405 | mctx->n0[0], mctx->N.top); | ||
406 | |||
407 | r->top = mctx->N.top; | ||
408 | bn_correct_top(r); | ||
409 | |||
410 | BN_set_negative(r, a->neg ^ b->neg); | ||
411 | |||
412 | ret = 1; | ||
413 | err: | ||
414 | BN_CTX_end(ctx); | ||
415 | |||
416 | return ret; | ||
417 | } | ||
418 | |||
339 | #ifndef OPENSSL_BN_ASM_MONT | 419 | #ifndef OPENSSL_BN_ASM_MONT |
340 | int | 420 | int |
341 | bn_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, | 421 | bn_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
342 | BN_MONT_CTX *mctx, BN_CTX *ctx) | 422 | BN_MONT_CTX *mctx, BN_CTX *ctx) |
343 | { | 423 | { |
344 | return bn_mod_mul_montgomery_simple(r, a, b, mctx, ctx); | 424 | if (mctx->N.top <= 1 || a->top != mctx->N.top || b->top != mctx->N.top) |
425 | return bn_mod_mul_montgomery_simple(r, a, b, mctx, ctx); | ||
426 | |||
427 | return bn_montgomery_multiply(r, a, b, mctx, ctx); | ||
345 | } | 428 | } |
346 | #else | 429 | #else |
347 | 430 | ||
@@ -360,7 +443,7 @@ bn_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, | |||
360 | * another implementation. | 443 | * another implementation. |
361 | */ | 444 | */ |
362 | if (!bn_mul_mont(r->d, a->d, b->d, mctx->N.d, mctx->n0, mctx->N.top)) | 445 | if (!bn_mul_mont(r->d, a->d, b->d, mctx->N.d, mctx->n0, mctx->N.top)) |
363 | return bn_mod_mul_montgomery_simple(r, a, b, mctx, ctx); | 446 | return bn_montgomery_multiply(r, a, b, mctx, ctx); |
364 | 447 | ||
365 | r->top = mctx->N.top; | 448 | r->top = mctx->N.top; |
366 | bn_correct_top(r); | 449 | bn_correct_top(r); |