diff options
author | Jack Lloyd <[email protected]> | 2018-03-01 10:13:47 -0500 |
---|---|---|
committer | Jack Lloyd <[email protected]> | 2018-03-01 10:13:47 -0500 |
commit | 0b15b2da77565e6219b4fd342e5ca6831472d871 (patch) | |
tree | 22c7c37b300e23e568ba8c9241307c8fed1303f3 | |
parent | 2674d453be668537fcf5cc1ea634659b1aefda9b (diff) |
Correct error in P-521 reduction
Introduced in c95b3967bf421, we failed to reduce if the result
was exactly 2**521 - 1
OSS-Fuzz 6635
-rw-r--r-- | src/lib/math/numbertheory/nistp_redc.cpp | 31 |
1 files changed, 25 insertions, 6 deletions
diff --git a/src/lib/math/numbertheory/nistp_redc.cpp b/src/lib/math/numbertheory/nistp_redc.cpp index 9d2e430d0..94a8d2872 100644 --- a/src/lib/math/numbertheory/nistp_redc.cpp +++ b/src/lib/math/numbertheory/nistp_redc.cpp @@ -40,24 +40,43 @@ void redc_p521(BigInt& x, secure_vector<word>& ws) // Word-level carry will be zero word carry = bigint_add3_nc(x.mutable_data(), x.data(), p_words, ws.data(), p_words); - BOTAN_ASSERT_EQUAL(carry, 0, "Final final carry in P-521 reduction"); + BOTAN_ASSERT_EQUAL(carry, 0, "Final carry in P-521 reduction"); // Now find the actual carry in bit 522 const uint8_t bit_522_set = x.word_at(p_full_words) >> (p_top_bits); +#if (BOTAN_MP_WORD_BITS == 64) + static const word p521_words[9] = { + 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, + 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, + 0x1FF }; +#endif + + /* + * 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. + */ if(bit_522_set) { #if (BOTAN_MP_WORD_BITS == 64) - static const word p521_words[9] = { - 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, - 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, - 0x1FF }; - bigint_sub2(x.mutable_data(), x.size(), p521_words, 9); #else 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); + } } #if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32) |