diff options
| -rw-r--r-- | src/lib/math/numbertheory/nistp_redc.cpp | 61 |
1 files changed, 31 insertions, 30 deletions
diff --git a/src/lib/math/numbertheory/nistp_redc.cpp b/src/lib/math/numbertheory/nistp_redc.cpp index d5935584d..caa071668 100644 --- a/src/lib/math/numbertheory/nistp_redc.cpp +++ b/src/lib/math/numbertheory/nistp_redc.cpp @@ -8,6 +8,7 @@ #include <botan/curve_nistp.h> #include <botan/internal/mp_core.h> #include <botan/internal/mp_asmi.h> +#include <botan/internal/ct_utils.h> namespace Botan { @@ -25,6 +26,20 @@ void redc_p521(BigInt& x, secure_vector<word>& ws) const size_t p_top_bits = 521 % BOTAN_MP_WORD_BITS; const size_t p_words = p_full_words + 1; +#if (BOTAN_MP_WORD_BITS == 64) + static const word p521_words[p_words] = { + 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, + 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, + 0x1FF }; +#else + static const word p521_words[p_words] = { + 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, + 0x1FF }; +#endif + if(ws.size() < p_words + 1) ws.resize(p_words + 1); @@ -38,40 +53,26 @@ void redc_p521(BigInt& x, secure_vector<word>& ws) word carry = bigint_add3_nc(x.mutable_data(), x.data(), p_words, ws.data(), p_words); BOTAN_ASSERT_EQUAL(carry, 0, "Final carry in P-521 reduction"); - // Now find the actual carry in bit 522 - const word bit_522_set = x.word_at(p_full_words) >> p_top_bits; + const word top_word = x.word_at(p_full_words); /* - * If bit 522 is set then we overflowed and must reduce. Otherwise, if the - * top bit is set, it is possible we have x == 2**521 - 1 so check for that. + * Check if we need to reduce modulo P + * There are two possible cases: + * - The result overflowed past 521 bits, in which case bit 522 will be set + * - The result is exactly 2**521 - 1 */ - if(bit_522_set) - { -#if (BOTAN_MP_WORD_BITS == 64) - static const word p521_words[p_words] = { - 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, - 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, - 0x1FF }; + const auto bit_522_set = CT::Mask<word>::expand(top_word >> p_top_bits); - bigint_sub2(x.mutable_data(), p_words, p521_words, p_words); -#else - // FIXME use bigint_sub2 - x -= prime_p521(); -#endif - } - else if(x.word_at(p_full_words) >> (p_top_bits - 1)) - { - /* - * Otherwise we must reduce if p is exactly 2^512-1 - */ - - word possibly_521 = MP_WORD_MAX; - for(size_t i = 0; i != p_full_words; ++i) - possibly_521 &= x.word_at(i); - - if(possibly_521 == MP_WORD_MAX) - x.reduce_below(prime_p521(), ws); - } + word and_512 = MP_WORD_MAX; + for(size_t i = 0; i != p_full_words; ++i) + and_512 &= x.word_at(i); + const auto all_512_low_bits_set = CT::Mask<word>::is_equal(and_512, MP_WORD_MAX); + const auto has_p521_top_word = CT::Mask<word>::is_equal(top_word, 0x1FF); + const auto is_p521 = all_512_low_bits_set & has_p521_top_word; + + const auto needs_reduction = is_p521 | bit_522_set; + + bigint_cnd_sub(needs_reduction.value(), x.mutable_data(), p521_words, p_words); } #if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32) |