Optimize P-256 and P-384 reduction

Precompute the multiples of the prime and then subtract directly.

1 files changed, 84 insertions, 29 deletions

diff --git a/src/lib/math/numbertheory/nistp_redc.cpp b/src/lib/math/numbertheory/nistp_redc.cpp
index 29771036d..a2420e975 100644
--- a/src/lib/math/numbertheory/nistp_redc.cpp
+++ b/src/lib/math/numbertheory/nistp_redc.cpp
@@ -1,6 +1,6 @@
 /*
 * NIST prime reductions
-* (C) 2014,2015 Jack Lloyd
+* (C) 2014,2015,2018 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -234,6 +234,10 @@ const BigInt& prime_p256()
 
 void redc_p256(BigInt& x, secure_vector<word>& ws)
    {
+   static const size_t p256_limbs = (BOTAN_MP_WORD_BITS == 32) ? 8 : 4;
+
+   BOTAN_UNUSED(ws);
+
    const uint32_t X8 = get_uint32_t(x, 8);
    const uint32_t X9 = get_uint32_t(x, 9);
    const uint32_t X10 = get_uint32_t(x, 10);
@@ -244,6 +248,7 @@ void redc_p256(BigInt& x, secure_vector<word>& ws)
    const uint32_t X15 = get_uint32_t(x, 15);
 
    x.mask_bits(256);
+   x.shrink_to_fit(p256_limbs + 1);
 
    int64_t S = 0;
 
@@ -342,36 +347,49 @@ void redc_p256(BigInt& x, secure_vector<word>& ws)
    set_uint32_t(x, 7, S);
    S >>= 32;
 
-   S += 5;
-   set_uint32_t(x, 8, S);
-
-   BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow");
-
-#if 0
-   BOTAN_ASSERT(S <= 10, "Expected overflow");
-   static const BigInt P256_mults[11] = {
-      prime_p256(),
-      2*prime_p256(),
-      3*prime_p256(),
-      4*prime_p256(),
-      5*prime_p256(),
-      6*prime_p256(),
-      7*prime_p256(),
-      8*prime_p256(),
-      9*prime_p256(),
-      10*prime_p256(),
-      11*prime_p256()
+   S += 5; // final carry of 6*P-256
+
+   BOTAN_ASSERT(S >= 0 && S <= 10, "Expected overflow");
+
+   /*
+   This is a table of (i*P-256) % 2**256 for i in 1...10
+   */
+   static const word p256_mults[11][p256_limbs] = {
+#if (BOTAN_MP_WORD_BITS == 64)
+      {0xFFFFFFFFFFFFFFFF, 0x00000000FFFFFFFF, 0x0000000000000000, 0xFFFFFFFF00000001},
+      {0xFFFFFFFFFFFFFFFE, 0x00000001FFFFFFFF, 0x0000000000000000, 0xFFFFFFFE00000002},
+      {0xFFFFFFFFFFFFFFFD, 0x00000002FFFFFFFF, 0x0000000000000000, 0xFFFFFFFD00000003},
+      {0xFFFFFFFFFFFFFFFC, 0x00000003FFFFFFFF, 0x0000000000000000, 0xFFFFFFFC00000004},
+      {0xFFFFFFFFFFFFFFFB, 0x00000004FFFFFFFF, 0x0000000000000000, 0xFFFFFFFB00000005},
+      {0xFFFFFFFFFFFFFFFA, 0x00000005FFFFFFFF, 0x0000000000000000, 0xFFFFFFFA00000006},
+      {0xFFFFFFFFFFFFFFF9, 0x00000006FFFFFFFF, 0x0000000000000000, 0xFFFFFFF900000007},
+      {0xFFFFFFFFFFFFFFF8, 0x00000007FFFFFFFF, 0x0000000000000000, 0xFFFFFFF800000008},
+      {0xFFFFFFFFFFFFFFF7, 0x00000008FFFFFFFF, 0x0000000000000000, 0xFFFFFFF700000009},
+      {0xFFFFFFFFFFFFFFF6, 0x00000009FFFFFFFF, 0x0000000000000000, 0xFFFFFFF60000000A},
+      {0xFFFFFFFFFFFFFFF5, 0x0000000AFFFFFFFF, 0x0000000000000000, 0xFFFFFFF50000000B},
+#else
+      {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0xFFFFFFFF},
+      {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001, 0x00000000, 0x00000000, 0x00000002, 0xFFFFFFFE},
+      {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000002, 0x00000000, 0x00000000, 0x00000003, 0xFFFFFFFD},
+      {0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000003, 0x00000000, 0x00000000, 0x00000004, 0xFFFFFFFC},
+      {0xFFFFFFFB, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000004, 0x00000000, 0x00000000, 0x00000005, 0xFFFFFFFB},
+      {0xFFFFFFFA, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000005, 0x00000000, 0x00000000, 0x00000006, 0xFFFFFFFA},
+      {0xFFFFFFF9, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000006, 0x00000000, 0x00000000, 0x00000007, 0xFFFFFFF9},
+      {0xFFFFFFF8, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000007, 0x00000000, 0x00000000, 0x00000008, 0xFFFFFFF8},
+      {0xFFFFFFF7, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000008, 0x00000000, 0x00000000, 0x00000009, 0xFFFFFFF7},
+      {0xFFFFFFF6, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000009, 0x00000000, 0x00000000, 0x0000000A, 0xFFFFFFF6},
+      {0xFFFFFFF5, 0xFFFFFFFF, 0xFFFFFFFF, 0x0000000A, 0x00000000, 0x00000000, 0x0000000B, 0xFFFFFFF5},
+#endif
    };
 
-   x -= P256_mults[S];
+   word borrow = bigint_sub2(x.mutable_data(), x.size(), p256_mults[S], p256_limbs);
 
-   while(x.is_negative())
+   BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow during P-256 reduction");
+
+   if(borrow)
       {
-      x += prime_p256();
+      bigint_add2(x.mutable_data(), x.size() - 1, p256_mults[0], p256_limbs);
       }
-#else
-   x.reduce_below(prime_p256(), ws);
-   #endif
    }
 
 const BigInt& prime_p384()
@@ -382,6 +400,10 @@ const BigInt& prime_p384()
 
 void redc_p384(BigInt& x, secure_vector<word>& ws)
    {
+   BOTAN_UNUSED(ws);
+
+   static const size_t p384_limbs = (BOTAN_MP_WORD_BITS == 32) ? 12 : 6;
+
    const uint32_t X12 = get_uint32_t(x, 12);
    const uint32_t X13 = get_uint32_t(x, 13);
    const uint32_t X14 = get_uint32_t(x, 14);
@@ -396,6 +418,7 @@ void redc_p384(BigInt& x, secure_vector<word>& ws)
    const uint32_t X23 = get_uint32_t(x, 23);
 
    x.mask_bits(384);
+   x.shrink_to_fit(p384_limbs + 1);
 
    int64_t S = 0;
 
@@ -523,10 +546,42 @@ void redc_p384(BigInt& x, secure_vector<word>& ws)
    S -= X22;
    set_uint32_t(x, 11, S);
    S >>= 32;
-   BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow");
-   set_uint32_t(x, 12, S);
 
-   x.reduce_below(prime_p384(), ws);
+   BOTAN_ASSERT(S >= 0 && S <= 4, "Expected overflow in P-384 reduction");
+
+   /*
+   This is a table of (i*P-384) % 2**384 for i in 1...4
+   */
+   static const word p384_mults[5][p384_limbs] = {
+#if (BOTAN_MP_WORD_BITS == 64)
+      {0x00000000FFFFFFFF, 0xFFFFFFFF00000000, 0xFFFFFFFFFFFFFFFE, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF},
+      {0x00000001FFFFFFFE, 0xFFFFFFFE00000000, 0xFFFFFFFFFFFFFFFD, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF},
+      {0x00000002FFFFFFFD, 0xFFFFFFFD00000000, 0xFFFFFFFFFFFFFFFC, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF},
+      {0x00000003FFFFFFFC, 0xFFFFFFFC00000000, 0xFFFFFFFFFFFFFFFB, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF},
+      {0x00000004FFFFFFFB, 0xFFFFFFFB00000000, 0xFFFFFFFFFFFFFFFA, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF},
+
+#else
+      {0xFFFFFFFF, 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF,
+       0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
+      {0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF,
+       0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
+      {0xFFFFFFFD, 0x00000002, 0x00000000, 0xFFFFFFFD, 0xFFFFFFFC, 0xFFFFFFFF,
+       0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
+      {0xFFFFFFFC, 0x00000003, 0x00000000, 0xFFFFFFFC, 0xFFFFFFFB, 0xFFFFFFFF,
+       0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
+      {0xFFFFFFFB, 0x00000004, 0x00000000, 0xFFFFFFFB, 0xFFFFFFFA, 0xFFFFFFFF,
+       0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
+#endif
+   };
+
+   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);
+      }
    }
 
 #endif