aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math/mp
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/math/mp')
-rw-r--r--src/lib/math/mp/mp_core.cpp19
-rw-r--r--src/lib/math/mp/mp_core.h13
-rw-r--r--src/lib/math/mp/mp_karat.cpp68
3 files changed, 55 insertions, 45 deletions
diff --git a/src/lib/math/mp/mp_core.cpp b/src/lib/math/mp/mp_core.cpp
index 52ad3a4d4..b1add33a4 100644
--- a/src/lib/math/mp/mp_core.cpp
+++ b/src/lib/math/mp/mp_core.cpp
@@ -157,8 +157,7 @@ word bigint_add3_nc(word z[], const word x[], size_t x_size,
*/
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
{
- if(bigint_add2_nc(x, x_size, y, y_size))
- x[x_size] += 1;
+ x[x_size] += bigint_add2_nc(x, x_size, y, y_size);
}
/*
@@ -212,6 +211,20 @@ 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 borrow = bigint_sub3(z, x, sz, y, sz);
+
+ CT::unpoison(borrow);
+ if(borrow)
+ {
+ bigint_sub3(z, y, sz, x, sz);
+ return -1;
+ }
+
+ return 1;
+ }
+
/*
* Three Operand Subtraction
*/
@@ -396,7 +409,7 @@ void bigint_shr2(word y[], const word x[], size_t x_size,
* Compare two MP integers
*/
int32_t bigint_cmp(const word x[], size_t x_size,
- const word y[], size_t y_size)
+ const word y[], size_t y_size)
{
if(x_size < y_size) { return (-bigint_cmp(y, y_size, x, x_size)); }
diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h
index a2c39bafa..1fae33987 100644
--- a/src/lib/math/mp/mp_core.h
+++ b/src/lib/math/mp/mp_core.h
@@ -95,6 +95,15 @@ word bigint_sub3(word z[],
const word x[], size_t x_size,
const word y[], size_t y_size);
+/**
+* Return abs(x-y), ie if x >= y, then compute z = x - y
+* 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);
+
/*
* Shift Operations
*/
@@ -134,10 +143,10 @@ void bigint_monty_redc(word z[],
size_t ws_size);
/**
-* Compare x and y
+* Compare x and y returning early
*/
int32_t bigint_cmp(const word x[], size_t x_size,
- const word y[], size_t y_size);
+ const word y[], size_t y_size);
/**
* Compute ((n1<<bits) + n0) / d
diff --git a/src/lib/math/mp/mp_karat.cpp b/src/lib/math/mp/mp_karat.cpp
index 7322b1c4b..220bd8f9e 100644
--- a/src/lib/math/mp/mp_karat.cpp
+++ b/src/lib/math/mp/mp_karat.cpp
@@ -101,8 +101,8 @@ void karatsuba_mul(word z[], const word x[], const word y[], size_t N,
word* z0 = z;
word* z1 = z + N;
- const int32_t cmp0 = bigint_cmp(x0, N2, x1, N2);
- const int32_t cmp1 = bigint_cmp(y1, N2, y0, N2);
+ word* ws0 = workspace;
+ word* ws1 = workspace + N;
clear_mem(workspace, 2*N);
@@ -115,34 +115,29 @@ void karatsuba_mul(word z[], const word x[], const word y[], size_t N,
* subtractions and recursively multiply to avoid the timing channel.
*/
- //if(cmp0 && cmp1)
- {
- if(cmp0 > 0)
- bigint_sub3(z0, x0, N2, x1, N2);
- else
- bigint_sub3(z0, x1, N2, x0, N2);
+ // 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);
- if(cmp1 > 0)
- bigint_sub3(z1, y1, N2, y0, N2);
- else
- bigint_sub3(z1, y0, N2, y1, N2);
+ karatsuba_mul(ws0, z0, z1, N2, ws1);
+ const bool is_negative = cmp0 != cmp1;
- karatsuba_mul(workspace, z0, z1, N2, workspace+N);
- }
+ // Compute X_lo * Y_lo
+ karatsuba_mul(z0, x0, y0, N2, ws1);
- karatsuba_mul(z0, x0, y0, N2, workspace+N);
- karatsuba_mul(z1, x1, y1, N2, workspace+N);
+ // Compute X_hi * Y_hi
+ karatsuba_mul(z1, x1, y1, N2, ws1);
- const word ws_carry = bigint_add3_nc(workspace + N, z0, N, z1, N);
- word z_carry = bigint_add2_nc(z + N2, N, workspace + N, N);
+ const word ws_carry = bigint_add3_nc(ws1, z0, N, z1, N);
+ word z_carry = bigint_add2_nc(z + N2, N, ws1, N);
z_carry += bigint_add2_nc(z + N + N2, N2, &ws_carry, 1);
bigint_add2_nc(z + N + N2, N2, &z_carry, 1);
- if((cmp0 == cmp1) || (cmp0 == 0) || (cmp1 == 0))
- bigint_add2(z + N2, 2*N-N2, workspace, N);
+ if(is_negative)
+ bigint_sub2(z + N2, 2*N-N2, ws0, N);
else
- bigint_sub2(z + N2, 2*N-N2, workspace, N);
+ bigint_add2_nc(z + N2, 2*N-N2, ws0, N);
}
/*
@@ -169,37 +164,30 @@ void karatsuba_sqr(word z[], const word x[], size_t N, word workspace[])
word* z0 = z;
word* z1 = z + N;
- const int32_t cmp = bigint_cmp(x0, N2, x1, N2);
+ word* ws0 = workspace;
+ word* ws1 = workspace + N;
clear_mem(workspace, 2*N);
// See comment in karatsuba_mul
+ bigint_sub_abs(z0, x0, x1, N2);
+ karatsuba_sqr(ws0, z0, N2, ws1);
- //if(cmp)
- {
- if(cmp > 0)
- bigint_sub3(z0, x0, N2, x1, N2);
- else
- bigint_sub3(z0, x1, N2, x0, N2);
-
- karatsuba_sqr(workspace, z0, N2, workspace+N);
- }
-
- karatsuba_sqr(z0, x0, N2, workspace+N);
- karatsuba_sqr(z1, x1, N2, workspace+N);
+ karatsuba_sqr(z0, x0, N2, ws1);
+ karatsuba_sqr(z1, x1, N2, ws1);
- const word ws_carry = bigint_add3_nc(workspace + N, z0, N, z1, N);
- word z_carry = bigint_add2_nc(z + N2, N, workspace + N, N);
+ const word ws_carry = bigint_add3_nc(ws1, z0, N, z1, N);
+ word z_carry = bigint_add2_nc(z + N2, N, ws1, N);
z_carry += bigint_add2_nc(z + N + N2, N2, &ws_carry, 1);
bigint_add2_nc(z + N + N2, N2, &z_carry, 1);
/*
- * This is only actually required if cmp is != 0, however
- * if cmp==0 then workspace[0:N] == 0 and avoiding the jump
- * hides a timing channel.
+ * This is only actually required if cmp (result of bigint_sub_abs) is != 0,
+ * however if cmp==0 then ws0[0:N] == 0 and avoiding the jump hides a
+ * timing channel.
*/
- bigint_sub2(z + N2, 2*N-N2, workspace, N);
+ bigint_sub2(z + N2, 2*N-N2, ws0, N);
}
/*
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-02 19:00:59 +0000