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.

2 files changed, 127 insertions, 41 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]),
diff --git a/src/testvectors.rs b/src/testvectors.rs
index e5449e7..212033a 100644
--- a/src/testvectors.rs
+++ b/src/testvectors.rs
@@ -116,7 +116,7 @@ pub const EXTRACT_VECTORS: &[(&str, &str)] = &[
 ];
 
 #[rustfmt::skip]
-pub const E_VECTORS: &[(&str, i32, i32, &str, &str)] = &[
+pub const E_VECTORS: &[(&str, i32, u32, &str, &str)] = &[
    // (K,j,i,a,b)  ==>  E_K^{j,i}(a) = b.
    ("8b30294cd9e405cdf087eec59d303877731e9511c16f7f674947084db0b65e98a157edacb60adad2c0cfa4821dfdd9b5", -1, 0, "18f3907664ec81cc5a25dc4ebce0846b", "078aed532a57973a7a47ed362f7e32dc"),
    ("e46ad908beabc8d183fb404a8c8b31b5eb1cfc9e82f27652512eb9e014c1b58efaf8fa69a12915a19a26f7657f7335d6", -1, 0, "2e2828a8a9f8c7c62898a52e092abcc0", "c592a0d157e598c64f8a3be838c8eb39"),
@@ -1724,4 +1724,3 @@ pub const ENCRYPT_VECTORS: &[(&str, &str, &[&str], u32, &str, &str)] = encrypt_v
   ("efdb03bb9763e29931eb251d5f65bcbc3cae9c059fcbdbbe0f13ed3c1fd7d5208fa4adca0bac429f6b450b8f12ea3e7c", "679c8290af6f720410a491f9e009ef9d", ["bfacb884297f0f51ad07", "", "e4270a9f6ef17abc12557126f85244"], 0, "465abed627709c9406b08dd4a790129f6bfec1578d7dd77e0f33b041e7ea0c44e133e77446c5eca59609670bdffaf39f1e4c70c7ec7fc4959577ef5af315248664d662868196c9b573be7197c1e1906ba389da1ace5424f3509be72285383f515d71363a78a0cd966b6c4319449a25c1a4dc4ad279b37098fa46c2294ee3f0f5529cf629aa997f690c50ac8cda1333af1b10e78b13a3eef7eec01d31e7c9924114bf420a30db292adb3b2dc0e07e249d8f01abab97d766288eb23463bfd8e16b054ed4168b0ae46e2dc849718533f15ce8aa9608a0f4427c43c2cc808e116271cc0ea85a50906942875e1f307ac74b9ffbd784411e13faddc677bf78f0636a94da5e23d048ee48bab7383be9306f889103dcf05a61642faab5c5347dd8263e63b9ef471c827daab6b6a74903135c128890be40e70d4a007edbf75d954263cbb2c9e676199e03f195cb2f514528217aeed8614d91128fc5ee6ad96e0029400580c604195ebfb076a359c64f8293bc4e652f71e3e8dac705649cf54fe6935a824eaa6190c89b66e76a2c140cbb9929684a39b812412bf7f496e309c58437d3d4b9cb8ceb8830d951499cae379d73b9f928c7c5dcd6c9e910acf603664192f05e3ce3754f1e13214a8e464a1a628ad3c3b389a522bcef3a52124f831be86413b41be1e193e5543feb82cda0abdf24f8d7326b34290a31fb969a19b55078803799", "4149f7c1f7f12f04bb6e0c5b017c20264ffaf19062ccbdd703ae82a44de8097134f5d9e4b76c7335f673c76b6ca0e5d8df22bf772f66a41608272a1210251a84888c47acd8bc7986fadf397c30eb505e08c60005d16d5cd55771e18545ec70725ae561a442a134f2f99c3efb4ff1d3289c7f03ed9bf355e41770203faa3203bd20645532cb76b04f3c3098278037fadb076a8089580f00f690c344cc108ad26a3fa912c75a34a756c7f5a713f9197ee66e3a5a816809f91b61ad538b297dfc0a9a3b44b13afe96e71516a982c7e7e5f2265b88be9cd27d5157e0c4f0ba4bc8070cd3e77a696b318037b8b45645edb514cb258028cf87562c6a38ad7c362a4794ca118e59e54e92f6bdfefc29f0be0e7c5cf55cb269629b483522b7dbfaa8e93c31eb8bc9151090545f270d53499ee8b30d25a2f1baad1e9780d7fbfe4a322b4b7a5736dac143565a7f15095470bc5ff53306422972f52ef716a4e6bfb87f550cff4bee2b22b98472e9d7fb53e6c33e31ede6a7a376f771d96c1f1563035c8ec40f557008e340cbc79576f1efb9d49012302c22673074636bd897ce92ba61abef0e8b856a820db4fab33bedea2556a255f1d51bb29079cd42d2273d27a9fe2e6fac0bf75ba543fb9e5b201235ef62b4c97a68de2d4e477fe9738f11b42f2b43787d8c260d9104f20fb7bdda1fa0658feb4c49fc44eaf7b04c0e008169a3bfbd"),
   ("157f71b2ba780938d047460a008dd99fc32fa16d56f218fa6be39815cc61fb85761545fbd397fc7fa5190e2ed5ef0a50", "2d6ccec9e86cba006da248752c3c18da", ["7970f888f169c7fd84f0", "", "cdc3233ccb573dfa7b02a26a0b2ebc"], 16, "a271b3ddb4555c6b15c161d1bb1947712994850df7da4a04ca65c37fa0f11deb04923f1bcd570f52781aed4536e32e907dc5c7ab0954a46a8c5185efb5d2206a6368942640f615daf94e56f148e9e4ca7974e76f4cc5303a8968f0154f601af2f9cdbbd85306f2129a8fdedddd7b2b022a0035ccf4c9d5352fa12ff4444ea30ca96c54d918574e0978a0f61327ab76e007934455f94ac3aa5bc3b0364d89ac3ff81a6e62e827f52fb24e84191a2a8a0bf2d6746a025dc30e76cc921308e9b2166c27c96d7c97f16c177a35481ae2636eddbb6e93d7bf51fe9e5753c213b220be32004d163c3354d01fe340a6dc183cd8e7d826984cd64891479179bd7a2441bf65695dc46ea5bada2d0bbc888e9ae4c526a5b51149647a01ea643b621065b2b9862ff45bf295ee2f70ef2d911911b0cd4766ca211d2bf7c2bbe6276947bd0e24c0acbc41c101795cf854210cc06e7998c142134cae075ffdd78607cfa1a87f741bd3fedab40757b864d0c4e165c12b513428c49fd525df0f38033042dce2072ea14d4075ccbaeca917c0009dd945759e25a6fefe6e69fb3c0d3e473529ee153eee984710ba92fda16b7313e36b88a29565d32ce324ef361eea4098c62d1b2079a59f0ff4ccbeafe92cce29115d6891a649a16192b671e2d62cddddeea99de93ef29f2c5ee1db2fc0d3665eb65069e485830d1bc4a93787d38a02faf280f997", "f7e405296797d59ad6825b8eeb2ee3e32d9548d8a9efde671b301262bd891092249c86fa31c79d2f9cac18a8afc6ea7f2df32110cd04fdf0c8fab457268f98c527cc6f73e9aec17eba39749c8b2224c081f31a4f3b27aa5b91bb5afed8c2d52f3d6961f8c3542afb7805fec2d4af8c455e1d492447292e1114e44d3baf627e8413ef728974bb6c672df3e42062905ace9ba884c6bac1ba7f01b398d0380cbe6f267a371ff94c3d400299f4cc96440d1ebe9f80ea6c792a77317a9bb87a41906380712e75177690d1055e892e18330e566ecc4e7b7ddb9d169d1bba9a9be7c544ef7d06bf4cb06ae4fd44636cd8443ce044a50b3922687e1302c1d0e167236590f02b55c2bdc10f80917dda22bc86137ac708617aa6d4bd7913746f3c3c300b8914c7bb4d5e8fc9b345b1be3530139f96ea5372fa04168370cc0fc0f4b3f584842933d2965bf85ec469072b91e9433cc9278c7c80bedde9e1deae85691583f97ec0a4954258954837e79593a84718e6a22011dd1d75691f30e834936e97096134a44d17751c1138b011d28ea3dc827e8b59912d21ecbedd5929ab1b1cfe3d8dab310c6a3752f5684c2220ca0c159038547dd3acc386ebee3fa1876eda2cf942f40cc6b9530403d9ea3fe70c34d0cde2cad3f1ad273e076c3051ddf33e6ed081319900cabac461c8402122689f4a31b79714d750985df875a0eaf6c7b10a7ea9bc8f713a555302249271bf3b6afa738f"),
 ];
-