diff options
author | Jack Lloyd <jack@randombit.net> | 2018-06-14 21:05:37 -0400 |
---|---|---|
committer | Jack Lloyd <jack@randombit.net> | 2018-06-14 21:05:37 -0400 |
commit | bee4746c1107876583f152295f34a03cc6f6d025 (patch) | |
tree | f79e13d870836669d0b0efed4ae3580d697677ab /src/lib/math/mp | |
parent | 33d325d5107852890e490dab70b9990af22d7098 (diff) |
Make Karatsuba multiply completely const time
Diffstat (limited to 'src/lib/math/mp')
-rw-r--r-- | src/lib/math/mp/mp_core.cpp | 31 | ||||
-rw-r--r-- | src/lib/math/mp/mp_core.h | 13 | ||||
-rw-r--r-- | src/lib/math/mp/mp_karat.cpp | 20 |
3 files changed, 45 insertions, 19 deletions
diff --git a/src/lib/math/mp/mp_core.cpp b/src/lib/math/mp/mp_core.cpp index b1add33a4..9f2999929 100644 --- a/src/lib/math/mp/mp_core.cpp +++ b/src/lib/math/mp/mp_core.cpp @@ -211,18 +211,35 @@ void bigint_sub2_rev(word x[], const word y[], size_t y_size) BOTAN_ASSERT(!borrow, "y must be greater than x"); } -int32_t bigint_sub_abs(word z[], const word x[], const word y[], size_t sz) +word bigint_sub_abs(word z[], + const word x[], const word y[], size_t N, + word ws[]) { - word borrow = bigint_sub3(z, x, sz, y, sz); + // Subtract in both direction then conditional copy out the result - CT::unpoison(borrow); - if(borrow) + word* ws0 = ws; + word* ws1 = ws + N; + + word borrow0 = 0; + word borrow1 = 0; + + const size_t blocks = N - (N % 8); + + for(size_t i = 0; i != blocks; i += 8) { - bigint_sub3(z, y, sz, x, sz); - return -1; + borrow0 = word8_sub3(ws0 + i, x + i, y + i, borrow0); + borrow1 = word8_sub3(ws1 + i, y + i, x + i, borrow1); } - return 1; + for(size_t i = blocks; i != N; ++i) + { + ws0[i] = word_sub(x[i], y[i], &borrow0); + ws1[i] = word_sub(y[i], x[i], &borrow1); + } + + word mask = CT::conditional_copy_mem(borrow1, z, ws0, ws1, N); + + return CT::select<word>(mask, 0, 1); } /* diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h index 4ae28f7bb..9d8ad84db 100644 --- a/src/lib/math/mp/mp_core.h +++ b/src/lib/math/mp/mp_core.h @@ -100,9 +100,16 @@ word bigint_sub3(word z[], * Otherwise compute z = y - x * No borrow is possible since the result is always >= 0 * -* Returns 1 if x >= y or -1 if x < y -*/ -int32_t bigint_sub_abs(word z[], const word x[], const word y[], size_t size); +* Returns 1 if x >= y or 0 if x < y +* @param z output array of at least N words +* @param x input array of N words +* @param y input array of N words +* @param N length of x and y +* @param ws array of at least 2*N words +*/ +word bigint_sub_abs(word z[], + const word x[], const word y[], size_t N, + word ws[]); /* * Shift Operations diff --git a/src/lib/math/mp/mp_karat.cpp b/src/lib/math/mp/mp_karat.cpp index 03a37ed8d..27ae349ef 100644 --- a/src/lib/math/mp/mp_karat.cpp +++ b/src/lib/math/mp/mp_karat.cpp @@ -1,6 +1,6 @@ /* * Multiplication and Squaring -* (C) 1999-2010 Jack Lloyd +* (C) 1999-2010,2018 Jack Lloyd * 2016 Matthias Gierlings * * Botan is released under the Simplified BSD License (see license.txt) @@ -8,6 +8,7 @@ #include <botan/internal/mp_core.h> #include <botan/internal/mp_asmi.h> +#include <botan/internal/ct_utils.h> #include <botan/mem_ops.h> #include <botan/exceptn.h> @@ -120,11 +121,10 @@ void karatsuba_mul(word z[], const word x[], const word y[], size_t N, */ // First compute (X_lo - X_hi)*(Y_hi - Y_lo) - const int32_t cmp0 = bigint_sub_abs(z0, x0, x1, N2); - const int32_t cmp1 = bigint_sub_abs(z1, y1, y0, N2); + const word cmp0 = bigint_sub_abs(z0, x0, x1, N2, workspace); + const word cmp1 = bigint_sub_abs(z1, y1, y0, N2, workspace); karatsuba_mul(ws0, z0, z1, N2, ws1); - const bool is_negative = cmp0 != cmp1; // Compute X_lo * Y_lo karatsuba_mul(z0, x0, y0, N2, ws1); @@ -138,10 +138,12 @@ void karatsuba_mul(word z[], const word x[], const word y[], size_t N, z_carry += bigint_add2_nc(z + N + N2, N2, &ws_carry, 1); bigint_add2_nc(z + N + N2, N2, &z_carry, 1); - if(is_negative) - bigint_sub2(z + N2, 2*N-N2, ws0, N); - else - bigint_add2_nc(z + N2, 2*N-N2, ws0, N); + clear_mem(workspace + N, N2); + + const word is_negative = CT::expand_mask<word>(cmp0 != cmp1); + + bigint_cnd_sub(is_negative, z + N2, workspace, 2*N-N2); + bigint_cnd_add(~is_negative, z + N2, workspace, 2*N-N2); } /* @@ -178,7 +180,7 @@ void karatsuba_sqr(word z[], const word x[], size_t N, word workspace[]) clear_mem(workspace, 2*N); // See comment in karatsuba_mul - bigint_sub_abs(z0, x0, x1, N2); + bigint_sub_abs(z0, x0, x1, N2, workspace); karatsuba_sqr(ws0, z0, N2, ws1); karatsuba_sqr(z0, x0, N2, ws1); |