summaryrefslogtreecommitdiff
path: root/src/lib
diff options
context:
space:
mode:
authorjsing <>2023-03-07 06:19:44 +0000
committerjsing <>2023-03-07 06:19:44 +0000
commit4320ee92fb55c991eec4cdc78f60c762533babb7 (patch)
tree6a167a9b374a6e5a6fc9fb06d04f4cff22727f76 /src/lib
parent9d27b98c03802e34828891a1a14e03f9ff09e110 (diff)
downloadopenbsd-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.c89
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 */
344void
345bn_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 */
385int
386bn_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
340int 420int
341bn_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 421bn_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);