speed up computation of successive e values

This vastly speeds up the encipher/decipher functions, as we no longer
keep computing key_i * (1 << exponent) over and over again.

1 files changed, 126 insertions, 39 deletions

diff --git a/src/lib.rs b/src/lib.rs
index 23ca0ff..08f0570 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -328,9 +328,10 @@ fn encipher_aez_core(key: &Key, tweaks: Tweak, message: &[u8]) -> Vec<u8> {
     let mut ws = Vec::new();
     let mut xs = Vec::new();
 
-    for (i, (mi, mi_)) in block_pairs.iter().enumerate() {
-        let i = (i + 1) as i32;
-        let w = *mi ^ e(1, i, key, *mi_);
+    let mut e1_eval = E::new(1, 0, key);
+    for (mi, mi_) in block_pairs.iter() {
+        e1_eval.advance();
+        let w = *mi ^ e1_eval.eval(*mi_);
         let x = *mi_ ^ e(0, 0, key, w);
         ws.push(w);
         xs.push(x);
@@ -358,13 +359,16 @@ fn encipher_aez_core(key: &Key, tweaks: Tweak, message: &[u8]) -> Vec<u8> {
 
     let mut cipher_pairs = Vec::new();
     let mut y = Block::NULL;
-    for (i, (wi, xi)) in ws.iter().zip(xs.iter()).enumerate() {
-        let i = (i + 1) as i32;
-        let s_ = e(2, i, key, s);
+    let mut e2_eval = E::new(2, 0, key);
+    let mut e1_eval = E::new(1, 0, key);
+    for (wi, xi) in ws.iter().zip(xs.iter()) {
+        e2_eval.advance();
+        e1_eval.advance();
+        let s_ = e2_eval.eval(s);
         let yi = *wi ^ s_;
         let zi = *xi ^ s_;
         let ci_ = yi ^ e(0, 0, key, zi);
-        let ci = zi ^ e(1, i, key, ci_);
+        let ci = zi ^ e1_eval.eval(ci_);
 
         cipher_pairs.push((ci, ci_));
         y = y ^ yi;
@@ -470,9 +474,10 @@ fn decipher_aez_core(key: &Key, tweaks: Tweak, cipher: &[u8]) -> Vec<u8> {
     let mut ws = Vec::new();
     let mut ys = Vec::new();
 
-    for (i, (ci, ci_)) in block_pairs.iter().enumerate() {
-        let i = (i + 1) as i32;
-        let w = *ci ^ e(1, i, key, *ci_);
+    let mut e1_eval = E::new(1, 0, key);
+    for (ci, ci_) in block_pairs.iter() {
+        e1_eval.advance();
+        let w = *ci ^ e1_eval.eval(*ci_);
         let y = *ci_ ^ e(0, 0, key, w);
         ws.push(w);
         ys.push(y);
@@ -500,13 +505,16 @@ fn decipher_aez_core(key: &Key, tweaks: Tweak, cipher: &[u8]) -> Vec<u8> {
 
     let mut plain_pairs = Vec::new();
     let mut x = Block::NULL;
-    for (i, (wi, yi)) in ws.iter().zip(ys.iter()).enumerate() {
-        let i = (i + 1) as i32;
-        let s_ = e(2, i, key, s);
+    let mut e2_eval = E::new(2, 0, key);
+    let mut e1_eval = E::new(1, 0, key);
+    for (wi, yi) in ws.iter().zip(ys.iter()) {
+        e2_eval.advance();
+        e1_eval.advance();
+        let s_ = e2_eval.eval(s);
         let xi = *wi ^ s_;
         let zi = *yi ^ s_;
         let mi_ = xi ^ e(0, 0, key, zi);
-        let mi = zi ^ e(1, i, key, mi_);
+        let mi = zi ^ e1_eval.eval(mi_);
 
         plain_pairs.push((mi, mi_));
         x = x ^ xi;
@@ -637,34 +645,113 @@ fn aez_prf(key: &Key, tweaks: Tweak, tau: u32) -> Vec<u8> {
     result
 }
 
-fn e(j: i32, i: i32, key: &Key, block: Block) -> Block {
-    let (key_i, key_j, key_l) = split_key(key);
-    if j == -1 {
-        let k = [
-            &Block::NULL,
-            &key_i,
-            &key_j,
-            &key_l,
-            &key_i,
-            &key_j,
-            &key_l,
-            &key_i,
-            &key_j,
-            &key_l,
-            &key_i,
-        ];
-        let delta = key_l * i.try_into().expect("i was negative");
-        aes10(&k, &(block ^ delta))
-    } else {
-        let k = [&Block::NULL, &key_j, &key_i, &key_l, &Block::NULL];
-        let j: u32 = j.try_into().expect("j was negative");
-        let i: u32 = i.try_into().expect("i was negative");
-        let exponent = if i % 8 == 0 { i / 8 } else { i / 8 + 1 };
-        let delta = (key_j * j) ^ key_i.exp(exponent) ^ (key_l * (i % 8));
-        aes4(&k, &(block ^ delta))
+/// Represents a computation of E_K^{j,i}.
+///
+/// As we usually need multiple values with a fixed j and ascending i, this struct saves the
+/// temporary values and makes it much faster to compute E_K^{j, i+1}, E_K^{j, i+2}, ...
+#[derive(Clone, Debug)]
+struct E {
+    key_i: Block,
+    key_j: Block,
+    key_l: Block,
+    state: Estate,
+}
+
+#[derive(Clone, Debug)]
+enum Estate {
+    Neg {
+        i: u32,
+    },
+    Pos {
+        i: u32,
+        kj_t_j: Block,
+        ki_p_i: Block,
+    },
+}
+
+impl E {
+    /// Create a new "suspended" computation of E_K^{j,i}.
+    fn new(j: i32, i: u32, key: &Key) -> Self {
+        let (key_i, key_j, key_l) = split_key(key);
+        let state = if j == -1 {
+            Estate::Neg { i }
+        } else {
+            let j: u32 = j.try_into().expect("j was negative");
+            let exponent = if i % 8 == 0 { i / 8 } else { i / 8 + 1 };
+            Estate::Pos {
+                i,
+                kj_t_j: key_j * j,
+                ki_p_i: key_i.exp(exponent),
+            }
+        };
+        E {
+            key_i,
+            key_j,
+            key_l,
+            state,
+        }
+    }
+
+    /// Complete this computation to evaluate E_K^{j,i}(block).
+    fn eval(&self, block: Block) -> Block {
+        match self.state {
+            Estate::Neg { i } => {
+                let k = [
+                    &Block::NULL,
+                    &self.key_i,
+                    &self.key_j,
+                    &self.key_l,
+                    &self.key_i,
+                    &self.key_j,
+                    &self.key_l,
+                    &self.key_i,
+                    &self.key_j,
+                    &self.key_l,
+                    &self.key_i,
+                ];
+                let delta = self.key_l * i;
+                aes10(&k, &(block ^ delta))
+            }
+            Estate::Pos { i, kj_t_j, ki_p_i } => {
+                let k = [
+                    &Block::NULL,
+                    &self.key_j,
+                    &self.key_i,
+                    &self.key_l,
+                    &Block::NULL,
+                ];
+                let delta = kj_t_j ^ ki_p_i ^ (self.key_l * (i % 8));
+                aes4(&k, &(block ^ delta))
+            }
+        }
+    }
+
+    /// Advance this computation by going from i to i+1.
+    ///
+    /// Afterwards, this computation will represent E_K^{j, i+1}
+    fn advance(&mut self) {
+        self.state = match self.state {
+            Estate::Neg { i } => Estate::Neg { i: i + 1 },
+            Estate::Pos { i, kj_t_j, ki_p_i } => {
+                // We need to advance ki_p_i if exponent = old_exponent + 1
+                // This happens exactly when the old exponent was just a multiple of 8, because the
+                // next exponent is then not a multiple anymore and will be rounded *up*.
+                let ki_p_i = if i % 8 == 0 { ki_p_i * 2 } else { ki_p_i };
+                Estate::Pos {
+                    i: i + 1,
+                    kj_t_j,
+                    ki_p_i,
+                }
+            }
+        }
     }
 }
 
+/// Shorthand to get E_K^{j,i}(block)
+fn e(j: i32, i: u32, key: &Key, block: Block) -> Block {
+    E::new(j, i, key).eval(block)
+}
+
 fn split_key(key: &Key) -> (Block, Block, Block) {
     (
         Block::from_slice(&key[..16]),