From e82fd1b4574c8908b2c3bb68e1237f057a981820 Mon Sep 17 00:00:00 2001 From: Matt Caswell Date: Tue, 31 May 2016 11:28:14 +0100 Subject: [PATCH] Fix BN_mod_word bug On systems where we do not have BN_ULLONG (e.g. typically 64 bit systems) then BN_mod_word() can return incorrect results if the supplied modulus is too big. RT#4501 Reviewed-by: Andy Polyakov (cherry picked from commit 37258dadaa9e36db4b96a3aa54aa6c67136160cc) --- crypto/bn/bn_word.c | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) diff --git a/crypto/bn/bn_word.c b/crypto/bn/bn_word.c index b031a60b5b..9b5f9cb98c 100644 --- a/crypto/bn/bn_word.c +++ b/crypto/bn/bn_word.c @@ -72,10 +72,32 @@ BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w) if (w == 0) return (BN_ULONG)-1; +#ifndef BN_LLONG + /* + * If |w| is too long and we don't have BN_ULLONG then we need to fall + * back to using BN_div_word + */ + if (w > ((BN_ULONG)1 << BN_BITS4)) { + BIGNUM *tmp = BN_dup(a); + if (tmp == NULL) + return (BN_ULONG)-1; + + ret = BN_div_word(tmp, w); + BN_free(tmp); + + return ret; + } +#endif + bn_check_top(a); w &= BN_MASK2; for (i = a->top - 1; i >= 0; i--) { #ifndef BN_LLONG + /* + * We can assume here that | w <= ((BN_ULONG)1 << BN_BITS4) | and so + * | ret < ((BN_ULONG)1 << BN_BITS4) | and therefore the shifts here are + * safe and will not overflow + */ ret = ((ret << BN_BITS4) | ((a->d[i] >> BN_BITS4) & BN_MASK2l)) % w; ret = ((ret << BN_BITS4) | (a->d[i] & BN_MASK2l)) % w; #else -- 2.25.1