viff

changeset 1068:33129a6f532a

ByteSub of AES implemented (including bit decomposition).
author Marcel Keller <mkeller@cs.au.dk>
date Mon, 22 Dec 2008 15:38:26 +0100
parents 79c3110de9b5
children 53e67a17c67d
files viff/aes.py
diffstat 1 files changed, 118 insertions(+), 0 deletions(-) [+]
line diff
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/viff/aes.py	Mon Dec 22 15:38:26 2008 +0100
     1.3 @@ -0,0 +1,118 @@
     1.4 +# Copyright 2008 VIFF Development Team.
     1.5 +#
     1.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     1.7 +#
     1.8 +# VIFF is free software: you can redistribute it and/or modify it
     1.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
    1.10 +# published by the Free Software Foundation, either version 3 of the
    1.11 +# License, or (at your option) any later version.
    1.12 +#
    1.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    1.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    1.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    1.16 +# Public License for more details.
    1.17 +#
    1.18 +# You should have received a copy of the GNU Lesser General Public
    1.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    1.20 +
    1.21 +"""MPC implementation of AES (Rijndael)."""
    1.22 +
    1.23 +__docformat__ = "restructuredtext"
    1.24 +
    1.25 +
    1.26 +from viff.field import GF256
    1.27 +from viff.runtime import Share
    1.28 +from viff.matrix import Matrix
    1.29 +
    1.30 +
    1.31 +def bit_decompose(share):
    1.32 +    """Bit decomposition for GF256 shares."""
    1.33 +
    1.34 +    assert isinstance(share, Share) and share.field == GF256, \
    1.35 +        "Parameter must be GF256 share."
    1.36 +
    1.37 +    r_bits = [share.runtime.prss_share_random(GF256, binary=True) \
    1.38 +                  for i in range(8)]
    1.39 +    r = reduce(lambda x,y: x + y, [r_bits[i] * 2 ** i for i in range(8)])
    1.40 +    
    1.41 +    c = share.runtime.open(share + r)
    1.42 +    c_bits = [Share(share.runtime, GF256) for i in range(8)]
    1.43 +    
    1.44 +    def decompose(byte, bits):
    1.45 +        value = byte.value
    1.46 +
    1.47 +        for i in range(8):
    1.48 +            c_bits[i].callback(GF256(value & 1))
    1.49 +            value >>= 1
    1.50 +
    1.51 +    c.addCallback(decompose, c_bits)
    1.52 +
    1.53 +    return [c_bits[i] + r_bits[i] for i in range(8)]
    1.54 +
    1.55 +
    1.56 +class AES:
    1.57 +    def __init__(self, runtime, key_size, block_size=128):
    1.58 +        """Initialize Rijndael.
    1.59 +
    1.60 +        AES(runtime, key_size, block_size), whereas keys ize and block
    1.61 +        size must be given in bits. Block size defaults to 128."""
    1.62 +
    1.63 +        assert key_size in [128, 192, 256], \
    1.64 +            "Key size must be 128, 192 or 256"
    1.65 +        assert block_size in [128, 192, 256], \
    1.66 +            "Block size be 128, 192 or 256"
    1.67 +
    1.68 +        self.n_k = key_size / 32
    1.69 +        self.n_b = block_size / 32
    1.70 +        self.rounds = max(self.n_k, self.n_b) + 6
    1.71 +        self.runtime = runtime
    1.72 +
    1.73 +    def byte_sub(self, state):
    1.74 +        """ByteSub operation of Rijndael.
    1.75 +
    1.76 +        The first argument should be a matrix consisting of elements
    1.77 +        of GF(2^8) or shares thereof with 4 rows and block_size / 32
    1.78 +        elements."""
    1.79 +
    1.80 +        assert len(state) == 4, "State must have 4 rows."
    1.81 +        assert len(state[0]) == self.n_b, "State must have block_size / 32 columns"
    1.82 +
    1.83 +        for h in range(len(state)):
    1.84 +            row = state[h]
    1.85 +            
    1.86 +            for i in range(len(row)):
    1.87 +                byte = row[i]
    1.88 +                bits = bit_decompose(byte)
    1.89 +
    1.90 +                for j in range(len(bits)):
    1.91 +                    bits[j] = 1 - bits[j]
    1.92 +
    1.93 +                while(len(bits) > 1):
    1.94 +                    bits.append(bits.pop() * bits.pop())
    1.95 +
    1.96 +                # b == 1 if byte is 0, b == 0 else
    1.97 +                b = bits[0]
    1.98 +
    1.99 +                r = self.runtime.prss_share_random(GF256)
   1.100 +                c = self.runtime.open((byte + b) * r)
   1.101 +                
   1.102 +                c.addCallback(lambda c: ~c)
   1.103 +                inverted_byte = c * r - b
   1.104 +
   1.105 +                bits = bit_decompose(inverted_byte)
   1.106 +
   1.107 +                A = Matrix([[1,0,0,0,1,1,1,1],
   1.108 +                            [1,1,0,0,0,1,1,1],
   1.109 +                            [1,1,1,0,0,0,1,1],
   1.110 +                            [1,1,1,1,0,0,0,1],
   1.111 +                            [1,1,1,1,1,0,0,0],
   1.112 +                            [0,1,1,1,1,1,0,0],
   1.113 +                            [0,0,1,1,1,1,1,0],
   1.114 +                            [0,0,0,1,1,1,1,1]])
   1.115 +
   1.116 +                # caution: order is lsb first
   1.117 +                vector = A * Matrix(zip(bits)) + Matrix(zip([1,1,0,0,0,1,1,0]))
   1.118 +                bits = zip(*vector.rows)[0]
   1.119 +
   1.120 +                row[i] = reduce(lambda x,y: x + y, 
   1.121 +                                [bits[j] * 2**j for j in range(len(bits))])