diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/lib/math/mp/mp_core.h | 59 | ||||
| -rw-r--r-- | src/lib/math/numbertheory/nistp_redc.cpp | 58 |
2 files changed, 58 insertions, 59 deletions
diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h index 5244261d7..40ff5fadd 100644 --- a/src/lib/math/mp/mp_core.h +++ b/src/lib/math/mp/mp_core.h @@ -40,17 +40,16 @@ inline void bigint_cnd_swap(word cnd, word x[], word y[], size_t size) } } -/* -* If cond > 0 adds x[0:size] and y[0:size] and returns carry -* Runs in constant time -*/ -inline word bigint_cnd_add(word cnd, word x[], const word y[], size_t size) +inline word bigint_cnd_add(word cnd, word x[], word x_size, + const word y[], size_t y_size) { + BOTAN_ASSERT(x_size >= y_size, "Expected sizes"); + const word mask = CT::expand_mask(cnd); word carry = 0; - const size_t blocks = size - (size % 8); + const size_t blocks = y_size - (y_size % 8); word z[8] = { 0 }; for(size_t i = 0; i != blocks; i += 8) @@ -61,26 +60,45 @@ inline word bigint_cnd_add(word cnd, word x[], const word y[], size_t size) x[i+j] = CT::select(mask, z[j], x[i+j]); } - for(size_t i = blocks; i != size; ++i) + for(size_t i = blocks; i != y_size; ++i) { z[0] = word_add(x[i], y[i], &carry); x[i] = CT::select(mask, z[0], x[i]); } + for(size_t i = y_size; i != x_size; ++i) + { + z[0] = word_add(x[i], 0, &carry); + x[i] = CT::select(mask, z[0], x[i]); + } + return carry & mask; } /* +* If cond > 0 adds x[0:size] and y[0:size] and returns carry +* Runs in constant time +*/ +inline word bigint_cnd_add(word cnd, word x[], const word y[], size_t size) + { + return bigint_cnd_add(cnd, x, size, y, size); + } + +/* * If cond > 0 subtracts x[0:size] and y[0:size] and returns borrow * Runs in constant time */ -inline word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size) +inline word bigint_cnd_sub(word cnd, + word x[], size_t x_size, + const word y[], size_t y_size) { + BOTAN_ASSERT(x_size >= y_size, "Expected sizes"); + const word mask = CT::expand_mask(cnd); word carry = 0; - const size_t blocks = size - (size % 8); + const size_t blocks = y_size - (y_size % 8); word z[8] = { 0 }; for(size_t i = 0; i != blocks; i += 8) @@ -91,16 +109,32 @@ inline word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size) x[i+j] = CT::select(mask, z[j], x[i+j]); } - for(size_t i = blocks; i != size; ++i) + for(size_t i = blocks; i != y_size; ++i) { z[0] = word_sub(x[i], y[i], &carry); x[i] = CT::select(mask, z[0], x[i]); } + for(size_t i = y_size; i != x_size; ++i) + { + z[0] = word_sub(x[i], 0, &carry); + x[i] = CT::select(mask, z[0], x[i]); + } + return carry & mask; } /* +* If cond > 0 adds x[0:size] and y[0:size] and returns carry +* Runs in constant time +*/ +inline word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size) + { + return bigint_cnd_sub(cnd, x, size, y, size); + } + + +/* * Equivalent to * bigint_cnd_add( mask, x, y, size); * bigint_cnd_sub(~mask, x, y, size); @@ -478,7 +512,10 @@ void bigint_monty_redc(word z[], size_t ws_size); /** -* Compare x and y returning early +* Compare x and y +* Return -1 if x < y +* Return 0 if x == y +* Return 1 if x > y */ inline int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size) diff --git a/src/lib/math/numbertheory/nistp_redc.cpp b/src/lib/math/numbertheory/nistp_redc.cpp index 5ad4515b4..a005e1abb 100644 --- a/src/lib/math/numbertheory/nistp_redc.cpp +++ b/src/lib/math/numbertheory/nistp_redc.cpp @@ -194,19 +194,9 @@ void redc_p192(BigInt& x, secure_vector<word>& ws) #endif }; - if(S == 0 && x.word_at(p192_limbs-1) < p192_mults[0][p192_limbs-1]) - { - return; - } - word borrow = bigint_sub2(x.mutable_data(), x.size(), p192_mults[S], p192_limbs); - - BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow during P-192 reduction"); - - if(borrow) - { - bigint_add2(x.mutable_data(), x.size() - 1, p192_mults[0], p192_limbs); - } + BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1); + bigint_cnd_add(borrow, x.mutable_data(), x.size(), p192_mults[0], p192_limbs); } const BigInt& prime_p224() @@ -303,19 +293,9 @@ void redc_p224(BigInt& x, secure_vector<word>& ws) }; - if(S == 0 && x.word_at(p224_limbs-1) < p224_mults[0][p224_limbs-1]) - { - return; - } - word borrow = bigint_sub2(x.mutable_data(), x.size(), p224_mults[S], p224_limbs); - - BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow during P-224 reduction"); - - if(borrow) - { - bigint_add2(x.mutable_data(), x.size() - 1, p224_mults[0], p224_limbs); - } + BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1); + bigint_cnd_add(borrow, x.mutable_data(), x.size(), p224_mults[0], p224_limbs); } const BigInt& prime_p256() @@ -405,7 +385,7 @@ void redc_p256(BigInt& x, secure_vector<word>& ws) S += 5; // the top digits of 6*P-256 - BOTAN_ASSERT(S >= 0 && S <= 10, "Expected overflow"); + BOTAN_DEBUG_ASSERT(S >= 0 && S <= 10); /* This is a table of (i*P-256) % 2**256 for i in 1...10 @@ -438,19 +418,11 @@ void redc_p256(BigInt& x, secure_vector<word>& ws) #endif }; - if(S == 0 && x.word_at(p256_limbs-1) < p256_mults[0][p256_limbs-1]) - { - return; - } + CT::unpoison(S); word borrow = bigint_sub2(x.mutable_data(), x.size(), p256_mults[S], p256_limbs); - - BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow during P-256 reduction"); - - if(borrow) - { - bigint_add2(x.mutable_data(), x.size() - 1, p256_mults[0], p256_limbs); - } + BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1); + bigint_cnd_add(borrow, x.mutable_data(), x.size(), p256_mults[0], p256_limbs); } const BigInt& prime_p384() @@ -598,19 +570,9 @@ void redc_p384(BigInt& x, secure_vector<word>& ws) #endif }; - if(S == 0 && x.word_at(p384_limbs-1) < p384_mults[0][p384_limbs-1]) - { - return; - } - word borrow = bigint_sub2(x.mutable_data(), x.size(), p384_mults[S], p384_limbs); - - BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow during P-384 reduction"); - - if(borrow) - { - bigint_add2(x.mutable_data(), x.size() - 1, p384_mults[0], p384_limbs); - } + BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1); + bigint_cnd_add(borrow, x.mutable_data(), x.size(), p384_mults[0], p384_limbs); } #endif |