Use async in ElGamal encryption and Nyberg-Rueppel verification

3 files changed, 39 insertions, 10 deletions

diff --git a/src/math/numbertheory/powm_fw.cpp b/src/math/numbertheory/powm_fw.cpp
index b764ee7aa..e4272f20d 100644
--- a/src/math/numbertheory/powm_fw.cpp
+++ b/src/math/numbertheory/powm_fw.cpp
@@ -77,17 +77,40 @@ BigInt Fixed_Window_Exponentiator::execute() const
    {
    const u32bit exp_nibbles = (exp.bits() + window_bits - 1) / window_bits;
 
-   BigInt x = 1;
-   for(u32bit j = exp_nibbles; j > 0; --j)
+   if(exp_nibbles == 0)
+      return 1;
+
+   BigInt x1 = 1;
+
+   for(u32bit j = 0; j != exp_nibbles / 2; ++j)
+      {
+      for(u32bit k = 0; k != window_bits; ++k)
+         x1 = reducer.square(x1);
+
+      u32bit nibble = exp.get_substring(window_bits*(exp_nibbles-1-j),
+                                        window_bits);
+
+      if(nibble)
+         x1 = reducer.multiply(x1, g[nibble-1]);
+      }
+
+   for(u32bit k = 0; k != window_bits; ++k)
+      x1 = reducer.square(x1);
+   BigInt x2 = 1;
+
+   for(u32bit j = exp_nibbles / 2; j != exp_nibbles; ++j)
       {
       for(u32bit k = 0; k != window_bits; ++k)
-         x = reducer.square(x);
+         x2 = reducer.square(x2);
+
+      u32bit nibble = exp.get_substring(window_bits*(exp_nibbles-1-j),
+                                        window_bits);
 
-      u32bit nibble = exp.get_substring(window_bits*(j-1), window_bits);
       if(nibble)
-         x = reducer.multiply(x, g[nibble-1]);
+         x2 = reducer.multiply(x2, g[nibble-1]);
       }
-   return x;
+
+   return reducer.multiply(x1, x2);
    }
 
 /*
diff --git a/src/pubkey/elgamal/elg_op.cpp b/src/pubkey/elgamal/elg_op.cpp
index 1e476ab7a..db828a300 100644
--- a/src/pubkey/elgamal/elg_op.cpp
+++ b/src/pubkey/elgamal/elg_op.cpp
@@ -1,11 +1,12 @@
 /*
 * ElGamal Operations
-* (C) 1999-2007 Jack Lloyd
+* (C) 1999-2009 Jack Lloyd
 *
 * Distributed under the terms of the Botan license
 */
 
 #include <botan/elg_op.h>
+#include <botan/async.h>
 
 namespace Botan {
 
@@ -33,8 +34,9 @@ SecureVector<byte> Default_ELG_Op::encrypt(const byte in[], u32bit length,
    if(m >= p)
       throw Invalid_Argument("Default_ELG_Op::encrypt: Input is too large");
 
-   BigInt a = powermod_g_p(k);
+   auto future_a = std_async([&]() { return powermod_g_p(k); });
    BigInt b = mod_p.multiply(m, powermod_y_p(k));
+   BigInt a = future_a.get();
 
    SecureVector<byte> output(2*p.bytes());
    a.binary_encode(output + (p.bytes() - a.bytes()));
diff --git a/src/pubkey/nr/nr_op.cpp b/src/pubkey/nr/nr_op.cpp
index b5efa3d37..49aa9fc00 100644
--- a/src/pubkey/nr/nr_op.cpp
+++ b/src/pubkey/nr/nr_op.cpp
@@ -1,11 +1,12 @@
 /*
 * NR Operations
-* (C) 1999-2007 Jack Lloyd
+* (C) 1999-2009 Jack Lloyd
 *
 * Distributed under the terms of the Botan license
 */
 
 #include <botan/nr_op.h>
+#include <botan/async.h>
 
 namespace Botan {
 
@@ -37,7 +38,10 @@ SecureVector<byte> Default_NR_Op::verify(const byte in[], u32bit length) const
    if(c.is_zero() || c >= q || d >= q)
       throw Invalid_Argument("Default_NR_Op::verify: Invalid signature");
 
-   BigInt i = mod_p.multiply(powermod_g_p(d), powermod_y_p(c));
+   auto future_y_c = std_async([&]() { return powermod_y_p(c); });
+   BigInt g_d = powermod_g_p(d);
+
+   BigInt i = mod_p.multiply(g_d, future_y_c.get());
    return BigInt::encode(mod_q.reduce(c - i));
    }