changeset 1576:d2e456c89f9f

aes: Online masked exponentiation.
author Marcel Keller <m.keller@bristol.ac.uk>
date Thu, 29 Mar 2012 10:56:14 +0100
parents cfb8e1485006
children 49ddac9bf0fa
files viff/aes.py
diffstat 1 files changed, 19 insertions(+), 1 deletions(-) [+]
line wrap: on
line diff
--- a/viff/aes.py	Wed Dec 15 13:00:00 2010 +0100
+++ b/viff/aes.py	Thu Mar 29 10:56:14 2012 +0100
@@ -115,6 +115,8 @@
                 self.invert = self.invert_by_exponentiation_with_least_rounds
             elif use_exponentiation == "masked":
                 self.invert = self.invert_by_masked_exponentiation
+            elif use_exponentiation == "masked_online":
+                self.invert = self.invert_by_masked_exponentiation_online
             else:
                 self.invert = self.invert_by_exponentiation
         else:
@@ -127,7 +129,8 @@
                                "shortest_sequential_chain",
                                "shortest_chain_with_least_rounds",
                                "chain_with_least_rounds",
-                               "masked"]
+                               "masked",
+                               "masked_online"]
 
     def invert_by_masking(self, byte):
         bits = bit_decompose(byte)
@@ -179,6 +182,21 @@
         return self.runtime.schedule_callback(
             masked_byte, add_and_multiply, random_powers, prep)
 
+    # constants for efficient computation of x^2, x^4, x^8 etc.
+    powers_of_two = [[GF256(2**j)**(2**i) for j in range(8)] for i in range(8)]
+
+    def invert_by_masked_exponentiation_online(self, byte):
+        bits = bit_decompose(byte)
+        byte_powers = []
+
+        for i in range(1,8):
+            byte_powers.append(self.runtime.lin_comb(AES.powers_of_two[i], bits))
+
+        while len(byte_powers) > 1:
+            byte_powers.append(byte_powers.pop(0) * byte_powers.pop(0))
+
+        return byte_powers[0]
+
     def invert_by_exponentiation(self, byte):
         byte_2 = byte * byte
         byte_3 = byte_2 * byte