viff

changeset 1083:e530dfcb40cd

Implemented inversion by exponentiation in AES ByteSub.
author Marcel Keller <mkeller@cs.au.dk>
date Thu, 15 Jan 2009 18:30:46 +0100
parents c1b3ced5bf05
children b4d9b373bbab
files viff/aes.py viff/test/test_aes.py
diffstat 2 files changed, 63 insertions(+), 34 deletions(-) [+]
line diff
     1.1 --- a/viff/aes.py	Wed Jan 14 18:33:33 2009 +0100
     1.2 +++ b/viff/aes.py	Thu Jan 15 18:30:46 2009 +0100
     1.3 @@ -51,7 +51,8 @@
     1.4  
     1.5  
     1.6  class AES:
     1.7 -    def __init__(self, runtime, key_size, block_size=128):
     1.8 +    def __init__(self, runtime, key_size, block_size=128, 
     1.9 +                 use_exponentiation=False):
    1.10          """Initialize Rijndael.
    1.11  
    1.12          AES(runtime, key_size, block_size), whereas key size and block
    1.13 @@ -66,6 +67,7 @@
    1.14          self.n_b = block_size / 32
    1.15          self.rounds = max(self.n_k, self.n_b) + 6
    1.16          self.runtime = runtime
    1.17 +        self.use_exponentiation = use_exponentiation
    1.18  
    1.19      # matrix for byte_sub
    1.20      A = Matrix([[1,0,0,0,1,1,1,1],
    1.21 @@ -83,39 +85,58 @@
    1.22          The first argument should be a matrix consisting of elements
    1.23          of GF(2^8)."""
    1.24  
    1.25 +        def invert_by_masking(byte):
    1.26 +            bits = bit_decompose(byte)
    1.27 +
    1.28 +            for j in range(len(bits)):
    1.29 +                bits[j] = 1 - bits[j]
    1.30 +
    1.31 +            while(len(bits) > 1):
    1.32 +                bits.append(bits.pop() * bits.pop())
    1.33 +
    1.34 +            # b == 1 if byte is 0, b == 0 else
    1.35 +            b = bits[0]
    1.36 +
    1.37 +            r = Share(self.runtime, GF256)
    1.38 +            c = Share(self.runtime, GF256)
    1.39 +
    1.40 +            def get_masked_byte(c_opened, r_related, c, r, byte):
    1.41 +                if (c_opened == 0):
    1.42 +                    r_trial = self.runtime.prss_share_random(GF256)
    1.43 +                    c_trial = self.runtime.open((byte + b) * r_trial)
    1.44 +                    c_trial.addCallback(get_masked_byte, r_trial,
    1.45 +                                        c, r, byte)
    1.46 +                else:
    1.47 +                    r_related.addCallback(r.callback)
    1.48 +                    c.callback(~c_opened)
    1.49 +
    1.50 +            get_masked_byte(0, None, c, r, byte)
    1.51 +            return c * r - b
    1.52 +
    1.53 +        def invert_by_exponentiation(byte):
    1.54 +            byte_2 = byte * byte
    1.55 +            byte_3 = byte_2 * byte
    1.56 +            byte_6 = byte_3 * byte_3
    1.57 +            byte_12 = byte_6 * byte_6
    1.58 +            byte_15 = byte_12 * byte_3
    1.59 +            byte_30 = byte_15 * byte_15
    1.60 +            byte_60 = byte_30 * byte_30
    1.61 +            byte_63 = byte_60 * byte_3
    1.62 +            byte_126 = byte_63 * byte_63
    1.63 +            byte_252 = byte_126 * byte_126
    1.64 +            byte_254 = byte_252 * byte_2
    1.65 +            return byte_254
    1.66 +
    1.67 +        if (self.use_exponentiation):
    1.68 +            invert = invert_by_exponentiation
    1.69 +        else:
    1.70 +            invert = invert_by_masking
    1.71 +
    1.72          for h in range(len(state)):
    1.73              row = state[h]
    1.74              
    1.75              for i in range(len(row)):
    1.76 -                byte = row[i]
    1.77 -                bits = bit_decompose(byte)
    1.78 -
    1.79 -                for j in range(len(bits)):
    1.80 -                    bits[j] = 1 - bits[j]
    1.81 -
    1.82 -                while(len(bits) > 1):
    1.83 -                    bits.append(bits.pop() * bits.pop())
    1.84 -
    1.85 -                # b == 1 if byte is 0, b == 0 else
    1.86 -                b = bits[0]
    1.87 -
    1.88 -                r = Share(self.runtime, GF256)
    1.89 -                c = Share(self.runtime, GF256)
    1.90 -
    1.91 -                def get_masked_byte(c_opened, r_related, c, r, byte):
    1.92 -                    if (c_opened == 0):
    1.93 -                        r_trial = self.runtime.prss_share_random(GF256)
    1.94 -                        c_trial = self.runtime.open((byte + b) * r_trial)
    1.95 -                        c_trial.addCallback(get_masked_byte, r_trial,
    1.96 -                                            c, r, byte)
    1.97 -                    else:
    1.98 -                        r_related.addCallback(r.callback)
    1.99 -                        c.callback(~c_opened)
   1.100 -
   1.101 -                get_masked_byte(0, None, c, r, byte)
   1.102 -                inverted_byte = c * r - b
   1.103 -
   1.104 -                bits = bit_decompose(inverted_byte)
   1.105 +                bits = bit_decompose(invert(row[i]))
   1.106  
   1.107                  # caution: order is lsb first
   1.108                  vector = AES.A * Matrix(zip(bits)) + Matrix(zip([1,1,0,0,0,1,1,0]))
     2.1 --- a/viff/test/test_aes.py	Wed Jan 14 18:33:33 2009 +0100
     2.2 +++ b/viff/test/test_aes.py	Thu Jan 15 18:30:46 2009 +0100
     2.3 @@ -69,9 +69,7 @@
     2.4  
     2.5          return gather_shares(opened_results)
     2.6  
     2.7 -    @protocol
     2.8 -    def test_byte_sub(self, runtime):
     2.9 -        aes = AES(runtime, 128)
    2.10 +    def _test_byte_sub(self, runtime, aes):
    2.11          results = []
    2.12          expected_results = []
    2.13  
    2.14 @@ -81,13 +79,23 @@
    2.15  
    2.16              for j in range(4):
    2.17                  b = 60 * i + j
    2.18 -                results[i].append(Share(runtime, GF256, b))
    2.19 +                results[i].append(Share(runtime, GF256, GF256(b)))
    2.20                  expected_results[i].append(S[b])
    2.21  
    2.22          aes.byte_sub(results)
    2.23          self.verify(runtime, results, expected_results)
    2.24  
    2.25      @protocol
    2.26 +    def test_byte_sub_with_masking(self, runtime):
    2.27 +        self._test_byte_sub(runtime, AES(runtime, 128, 
    2.28 +                                         use_exponentiation=False))
    2.29 +
    2.30 +    @protocol
    2.31 +    def test_byte_sub_with_exponentiation(self, runtime):
    2.32 +        self._test_byte_sub(runtime, AES(runtime, 128, 
    2.33 +                                         use_exponentiation=True))
    2.34 +
    2.35 +    @protocol
    2.36      def test_key_expansion(self, runtime):
    2.37          aes = AES(runtime, 256)
    2.38          key = []