aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math/mp
diff options
context:
space:
mode:
authorJack Lloyd <jack@randombit.net>2018-06-14 21:05:37 -0400
committerJack Lloyd <jack@randombit.net>2018-06-14 21:05:37 -0400
commitbee4746c1107876583f152295f34a03cc6f6d025 (patch)
treef79e13d870836669d0b0efed4ae3580d697677ab /src/lib/math/mp
parent33d325d5107852890e490dab70b9990af22d7098 (diff)
Make Karatsuba multiply completely const time
Diffstat (limited to 'src/lib/math/mp')
-rw-r--r--src/lib/math/mp/mp_core.cpp31
-rw-r--r--src/lib/math/mp/mp_core.h13
-rw-r--r--src/lib/math/mp/mp_karat.cpp20
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);