http://hg.viff.dk/viff/rev/950815ab873f
changeset: 1154:950815ab873f
user: Martin Geisler <[email protected]>
date: Fri Mar 27 15:44:01 2009 +0100
summary: Merged.
diffstat:
19 files changed, 458 insertions(+), 204 deletions(-)
apps/aes.py | 4
apps/beginner.py | 114 +++++++++++++++++
apps/benchmark.py | 6
apps/generate-config-files.py | 9 -
apps/multiply.py | 7 -
doc/authors.txt | 2
doc/bibliography.txt | 2
doc/index.txt | 1
doc/install.txt | 38 +++--
doc/todo.txt | 50 +++++++
setup.py | 30 ++--
viff/aes.py | 17 +-
viff/config.py | 5
viff/field.py | 44 ++++++
viff/passive.py | 28 ++++
viff/runtime.py | 6
viff/test/rijndael.py | 272 +++++++++++++++++++----------------------
viff/test/test_util.py | 17 +-
viff/util.py | 10 +
diffs (truncated from 987 to 800 lines):
diff -r 99a8a7c9cce5 -r 950815ab873f apps/aes.py
--- a/apps/aes.py Fri Mar 27 15:33:52 2009 +0100
+++ b/apps/aes.py Fri Mar 27 15:44:01 2009 +0100
@@ -20,7 +20,6 @@
# This example shows how to use multi-party AES encryption.
-import sys
import time
from optparse import OptionParser
@@ -30,7 +29,7 @@
from viff.runtime import Runtime, create_runtime, gather_shares
from viff.config import load_config
-from viff.aes import bit_decompose,AES
+from viff.aes import AES
parser = OptionParser(usage="Usage: %prog [options] config_file")
@@ -89,7 +88,6 @@
for i in range(24):
inputter = i % 3 + 1
-
if (inputter == id):
key.append(rt.input([inputter], GF256, ord("b")))
else:
diff -r 99a8a7c9cce5 -r 950815ab873f apps/beginner.py
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/apps/beginner.py Fri Mar 27 15:44:01 2009 +0100
@@ -0,0 +1,114 @@
+#!/usr/bin/python
+
+# Copyright 2009 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
+
+# This file contains a simpel example of a VIFF program, which illustrates
+# the basic features of VIFF. How to input values from the command line,
+# from individual players in the program, add, multiply, and output values
+# to all or some of the players.
+
+# Inorder to run the program follow the three steps:
+#
+# Generate player configurations in the viff/apps directory using:
+# python generate-config-files.py localhost:4001 localhost:4002
localhost:4003
+#
+# Generate ssl certificates in the viff/apps directory using:
+# python generate-certificates.py
+#
+# Run the program using three different shells using the command:
+# python beginner.py player-x.ini 79
+# where x is replaced by the player number
+
+# Some useful imports.
+import sys
+
+from twisted.internet import reactor
+
+from viff.field import GF
+from viff.runtime import create_runtime
+from viff.config import load_config
+from viff.util import dprint, find_prime
+
+# Load the configuration from the player configuration files.
+id, players = load_config(sys.argv[1])
+
+# Initialize the field we do arithmetic over.
+Zp = GF(find_prime(2**64))
+
+# Read input from the commandline.
+input = int(sys.argv[2])
+
+print "I am player %d and will input %s" % (id, input)
+
+
+def protocol(runtime):
+ print "-" * 64
+ print "Program started"
+ print
+
+ # Each of the players [1, 2, 3] shares his input -- resulting in
+ # three shares. The a share is the input from P1, b is from P2,
+ # and c is from P3.
+ a, b, c = runtime.input([1, 2, 3], Zp, input)
+
+ # It is possible to make the players do different things by
+ # branching on the players ID. In this case only P1 inputs a
+ # number. The other two players must still participate in order to
+ # get the hold of their share.
+ if runtime.id == 1:
+ s1 = runtime.input([1], Zp, 42)
+ else:
+ s1 = runtime.input([1], Zp, None)
+
+ # Secure arithmetic works like normal.
+ a = b + c
+ b = c * s1
+
+ # Outputting shares convert them from secret shared form into
+ # cleartext. By default every player receives the cleartext.
+ a = runtime.output(a)
+ b = runtime.output(b)
+ c = runtime.output(c)
+ # Output s1 to player 2. The other players will receive None.
+ s1 = runtime.output(s1, [2])
+
+ dprint("### Output a to all: %s ###", a)
+ dprint("### Output b to all: %s ###", b)
+ dprint("### Output c to all: %s ###", c)
+
+ # We only print the value of s1 for player 2,
+ # since only player 2 has the value of s1.
+ if runtime.id == 2:
+ dprint("### opened s1: %s ###", s1)
+
+ # We wait for the evaluation of deferred a, b, c.
+ runtime.wait_for(a, b, c)
+
+def errorHandler(failure):
+ print "Error: %s" % failure
+
+
+# Create a runtime
+pre_runtime = create_runtime(id, players, 1)
+pre_runtime.addCallback(protocol)
+# This error handler will enable debugging by capturing
+# any exceptions and print them on Standard Out.
+pre_runtime.addErrback(errorHandler)
+
+print "#### Starting reactor ###"
+reactor.run()
diff -r 99a8a7c9cce5 -r 950815ab873f apps/benchmark.py
--- a/apps/benchmark.py Fri Mar 27 15:33:52 2009 +0100
+++ b/apps/benchmark.py Fri Mar 27 15:44:01 2009 +0100
@@ -140,9 +140,11 @@
if options.fake:
print "Using fake field elements"
- GF = FakeGF
+ Field = FakeGF
+else:
+ Field = GF
-Zp = GF(find_prime(options.modulus))
+Zp = Field(find_prime(options.modulus))
print "Using field elements (%d bit modulus)" % log(Zp.modulus, 2)
count = options.count
diff -r 99a8a7c9cce5 -r 950815ab873f apps/generate-config-files.py
--- a/apps/generate-config-files.py Fri Mar 27 15:33:52 2009 +0100
+++ b/apps/generate-config-files.py Fri Mar 27 15:44:01 2009 +0100
@@ -65,12 +65,15 @@
help="be quiet")
parser.add_option("-n", "--players", dest="n", type="int",
help="number of players")
+parser.add_option("-k", "--keysize", type="int",
+ help="Specify the key-size")
parser.add_option("-t", "--threshold", dest="t", type="int",
help="threshold (it must hold that t < n/2)")
parser.add_option("--skip-prss", action="store_true",
help="do not generate PRSS keys")
-parser.set_defaults(verbose=True, n=3, t=1, prefix='player', skip_prss=False)
+parser.set_defaults(verbose=True, n=3, t=1, prefix='player', skip_prss=False,
+ keysize=1024)
(options, args) = parser.parse_args()
@@ -78,8 +81,8 @@
parser.error("must supply a hostname:port argument for each player")
addresses = [arg.split(':', 1) for arg in args]
-configs = generate_configs(options.n, options.t, addresses, options.prefix,
- options.skip_prss)
+configs = generate_configs(options.n, options.t, options.keysize, addresses,
+ options.prefix, options.skip_prss)
for config in configs.itervalues():
config.write()
diff -r 99a8a7c9cce5 -r 950815ab873f apps/multiply.py
--- a/apps/multiply.py Fri Mar 27 15:33:52 2009 +0100
+++ b/apps/multiply.py Fri Mar 27 15:44:01 2009 +0100
@@ -1,6 +1,6 @@
#!/usr/bin/python
-# Copyright 2008 VIFF Development Team.
+# Copyright 2008, 2009 VIFF Development Team.
#
# This file is part of VIFF, the Virtual Ideal Functionality Framework.
#
@@ -24,10 +24,13 @@
from viff.runtime import create_runtime, Runtime
from viff.config import load_config
-parser = OptionParser()
+parser = OptionParser("%prog config input")
Runtime.add_options(parser)
(options, args) = parser.parse_args()
+if len(args) != 2:
+ parser.error("please supply a config file and an integer")
+
Zp = GF(1031)
id, players = load_config(args[0])
diff -r 99a8a7c9cce5 -r 950815ab873f doc/authors.txt
--- a/doc/authors.txt Fri Mar 27 15:33:52 2009 +0100
+++ b/doc/authors.txt Fri Mar 27 15:44:01 2009 +0100
@@ -13,6 +13,8 @@
* Jakob Illeborg Pagter
* Sigurd Meldgaard
* Marcel Keller <[email protected]>
+* Tord Reistad
+* Ivan Damgård
If you have been forgotten, then please checkout `the repository`_,
add yourself to the list and `send us a patch`_!
diff -r 99a8a7c9cce5 -r 950815ab873f doc/bibliography.txt
--- a/doc/bibliography.txt Fri Mar 27 15:33:52 2009 +0100
+++ b/doc/bibliography.txt Fri Mar 27 15:44:01 2009 +0100
@@ -74,7 +74,7 @@
.. [Toft05] Tomas Toft, *Secure Integer Computation with Applications
in Economics*, PhD Progress Report, July 2005, PDF__.
- .. __: http://www.daimi.au.dk/~tomas/publications/progress.pdf
+ .. __: http://www.daimi.au.dk/~ttoft/publications/progress.pdf
.. [Yao82] Andrew Chi-Chih Yao, *Protocols for Secure Computations*,
FOCS 1982, 160-164.
diff -r 99a8a7c9cce5 -r 950815ab873f doc/index.txt
--- a/doc/index.txt Fri Mar 27 15:33:52 2009 +0100
+++ b/doc/index.txt Fri Mar 27 15:44:01 2009 +0100
@@ -32,6 +32,7 @@
install
implementation
background
+ todo
coding-style
development
unit-testing
diff -r 99a8a7c9cce5 -r 950815ab873f doc/install.txt
--- a/doc/install.txt Fri Mar 27 15:33:52 2009 +0100
+++ b/doc/install.txt Fri Mar 27 15:44:01 2009 +0100
@@ -73,27 +73,39 @@
Python-installation which comes with Mac OS X is not entirely
up-to-date).
-2) Download and Install Twisted_ from source. Notice again that Mac OS
- X comes with a pre-installed version of Twisted, but this is not
- the full Twisted installation. After installation change your
- ``PYTHONPATH`` (in your ``~/.bash_profile``) to::
+2) Download and Install Twisted_ from source. There is an installer
+ for Mac OS X 10.5 which can be used if you use Mac OS X
+ 10.5. Notice again that Mac OS X comes with a pre-installed version
+ of Twisted, but this is not the full Twisted installation. After
+ installation change your ``PYTHONPATH`` (in your
+ ``~/.bash_profile``) to::
- PATH="/Library/Python/2.5/site-packages:${PATH}"
+ export PYTHONPATH="/Library/Python/2.5/site-packages:${PYTHONPATH}"
+ export PYTHONPATH=$PYTHONPATH:$HOME/opt/lib/python
3) Optionally: download PyOpenSSL_ and tell us if it works!
-4) Download and install GMPY_ following the instructions in
+4) Download and install GMP_. You can preferably use the Macports or
+ Fink package utilities. If you download the other dependencies from
+ either Macports or Fink, they might depend on Python 2.4 which is
+ not preferable, you should use Python 2.5, unless you have good
+ reasons not to.
+
+5) Download and install GMPY_ following the instructions in
``gmpy-1.02.macosx.README.txt`` (under Downloads).
-5) Install VIFF from source (see below). If you prefer you can just
- install it in site-packages, it makes no difference. For
- developers, it is perhaps a better solution in to create a symbolic
- link from the site-packages directory to the VIFF Python files
- (``viff/viff/``), as otherwise you need to re-install VIFF each time
- the project is modified.
+6) Install VIFF from source (see below). If you prefer you can just
+ install it in site-packages, it makes no difference.
-6) Proceed to `testing`_.
+ For developers, either add VIFF to the PYTHONPATH::
+ export PYTHONPATH=$PYTHONPATH:$HOME/path-to-viff/viff
+
+ or create a symbolic link from the site-packages directory to the
+ VIFF Python files (``viff/viff/``), as otherwise you need to
+ re-install VIFF each time the project is modified.
+
+7) Proceed to `testing`_.
GNU/Linux
---------
diff -r 99a8a7c9cce5 -r 950815ab873f doc/todo.txt
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/todo.txt Fri Mar 27 15:44:01 2009 +0100
@@ -0,0 +1,50 @@
+
+Planned Work on VIFF
+====================
+
+This document collects the bigger pieces of work we plan to do on
+VIFF --- pieces too big for the bug tracker.
+
+
+Active Security
+---------------
+
+The protocol implemented in :mod:`viff.active` is (believed to be)
+secure against active adversaries, but only as long as they don't
+actually try to cheat! In other words, the players will crash in bad
+ways if malformed data is received or too few shares are received.
+
+The following points should be addressed:
+
+* Error correction. The honest players must tolerate being sent wrong
+ shares or no shares at all from the corrupt players.
+
+ This is related to Issue4_, Issue29_, and Issue70_.
+
+ .. _Issue4: http://tracker.viff.dk/issue4
+ .. _Issue29: http://tracker.viff.dk/issue29
+ .. _Issue70: http://tracker.viff.dk/issue70
+
+* Byzantine agreement. After the preprocessing phase a Byzantime
+ agreement protocol should be run in order to determine if all honest
+ players are ready to continue.
+
+ At the moment an honest players simply aborts the protocol if it
+ detects any form of cheating --- the "idea" being that this will
+ make the other honest players crash too, thereby effectively halting
+ the protocol.
+
+Self Trust
+----------
+
+Implement an (actively) secure protocol with threshold ``t = n-1``
+based on the "triples approach" of Claudio Orlandi and Jesper Buus
+Nielsen. There will soon be a paper describing the protocol.
+
+Covert Adversaries
+------------------
+
+Implement an actively secure protocol for a covert adversary and
+threshold ``t < n/2``. The goal is to have almost the same complexity
+as for the passive case. Martin Geisler is working on a paper
+describing a solution.
diff -r 99a8a7c9cce5 -r 950815ab873f setup.py
--- a/setup.py Fri Mar 27 15:33:52 2009 +0100
+++ b/setup.py Fri Mar 27 15:44:01 2009 +0100
@@ -4,7 +4,7 @@
# For a local install into ~/opt, use: python setup.py --home=~/opt
# For more options, use: python setup.py --help
-# Copyright 2007, 2008 VIFF Development Team.
+# Copyright 2007, 2008, 2009 VIFF Development Team.
#
# This file is part of VIFF, the Virtual Ideal Functionality Framework.
#
@@ -33,22 +33,22 @@
class hg_sdist(sdist):
def get_file_list(self):
try:
- # Attempt the import here so that users can run the other
- # Distutils commands without needing Mercurial.
- from mercurial import hg
- except ImportError:
from distutils.errors import DistutilsModuleError
- raise DistutilsModuleError("could not import mercurial")
+ import subprocess
+ p = subprocess.Popen(['hg', 'manifest'], stdout=subprocess.PIPE)
+ exitcode = p.wait()
+ if exitcode != 0:
+ raise DistutilsModuleError("Mercurial exited with non-zero "
+ "exit code: %d" % exitcode)
+ files = p.stdout.read().strip().split('\n')
- repo = hg.repository(None)
- changeset = repo.changectx(None)
- files = changeset.manifest().keys()
-
- # Add the files *before* the normal manifest magic is done.
- # That allows the manifest template to exclude some files
- # tracked by hg and to include others.
- self.filelist.extend(files)
- sdist.get_file_list(self)
+ # Add the files *before* the normal manifest magic is
+ # done. That allows the manifest template to exclude some
+ # files tracked by hg and to include others.
+ self.filelist.extend(files)
+ sdist.get_file_list(self)
+ except OSError, e:
+ raise DistutilsModuleError("could not execute Mercurial: %s" % e)
setup(name='viff',
version=viff.__version__,
diff -r 99a8a7c9cce5 -r 950815ab873f viff/aes.py
--- a/viff/aes.py Fri Mar 27 15:33:52 2009 +0100
+++ b/viff/aes.py Fri Mar 27 15:44:01 2009 +0100
@@ -58,14 +58,17 @@
class AES:
- """AES instantiation:
+ """AES instantiation.
- >>> aes = AES(runtime, 192)
- >>> cleartext = [Share(runtime, GF256, GF256(0)) for i in range(128/8)]
- >>> key = [runtime.prss_share_random(GF256) for i in range(192/8)]
- >>> ciphertext = aes.encrypt("abcdefghijklmnop", key)
- >>> ciphertext = aes.encrypt(cleartext, "keykeykeykeykeykeykeykey")
- >>> ciphertext = aes.encrypt(cleartext, key)
+ This class is used together with a :class:`viff.runtime.Runtime`
+ object::
+
+ aes = AES(runtime, 192)
+ cleartext = [Share(runtime, GF256, GF256(0)) for i in range(128/8)]
+ key = [runtime.prss_share_random(GF256) for i in range(192/8)]
+ ciphertext = aes.encrypt("abcdefghijklmnop", key)
+ ciphertext = aes.encrypt(cleartext, "keykeykeykeykeykeykeykey")
+ ciphertext = aes.encrypt(cleartext, key)
In every case *ciphertext* will be a list of shares over GF256.
"""
diff -r 99a8a7c9cce5 -r 950815ab873f viff/config.py
--- a/viff/config.py Fri Mar 27 15:33:52 2009 +0100
+++ b/viff/config.py Fri Mar 27 15:44:01 2009 +0100
@@ -158,7 +158,7 @@
return owner_id, players
-def generate_configs(n, t, addresses=None, prefix=None, skip_prss=False):
+def generate_configs(n, t, keysize=1024, addresses=None, prefix=None,
skip_prss=False):
"""Generate player configurations.
Generates *n* configuration objects with a threshold of *t*. The
@@ -194,8 +194,7 @@
"""Convert a dealer ID to a string."""
return "Dealer " + str(dealer)
- # TODO: remove hard-coded key size.
- key_pairs = dict([(p, paillier.generate_keys(1024)) for p in players])
+ key_pairs = dict([(p, paillier.generate_keys(keysize)) for p in players])
configs = {}
for p in players:
diff -r 99a8a7c9cce5 -r 950815ab873f viff/field.py
--- a/viff/field.py Fri Mar 27 15:33:52 2009 +0100
+++ b/viff/field.py Fri Mar 27 15:44:01 2009 +0100
@@ -32,6 +32,7 @@
>>> x = Zp(10)
>>> y = Zp(15)
+>>> z = Zp(1)
Addition and subtraction (with modulo reduction):
@@ -40,6 +41,15 @@
>>> x - y
{14}
+Bitwise xor for field elements:
+
+>>> z ^ z
+{0}
+>>> z ^ 0
+{1}
+>>> 1 ^ z
+{0}
+
Exponentiation:
>>> x**3
@@ -69,6 +79,7 @@
from gmpy import mpz
+from math import log, ceil
class FieldElement(object):
@@ -84,6 +95,25 @@
__long__ = __int__
+ def split(self):
+ """Splits self into bit array LSB first.
+
+ >>> Zp = GF(29)
+ >>> Zp(3).split()
+ [{1}, {1}, {0}, {0}, {0}]
+ >>> Zp(28).split()
+ [{0}, {0}, {1}, {1}, {1}]
+ >>> GF256(8).split()
+ [[0], [0], [0], [1], [0], [0], [0], [0]]
+ """
+ length = int(ceil(log(self.modulus,2)))
+ result = [0] * length
+ temp = self.value
+ for i in range(length):
+ result[i] = self.field(temp % 2)
+ temp = temp // 2
+ return result
+
#: Inversion table.
#:
#: Maps a value *x* to *x^-1*. See `_generate_tables`.
@@ -377,6 +407,20 @@
"""Subtraction (reflected argument version)."""
return GFElement(other - self.value)
+ def __xor__(self, other):
+ """Xor for bitvalues."""
+ if not isinstance(other, (GFElement, int, long)):
+ return NotImplemented
+ try:
+ assert self.field is other.field, "Fields must be identical"
+ return GFElement(self.value ^ other.value)
+ except AttributeError:
+ return GFElement(self.value ^ other)
+
+ def __rxor__(self, other):
+ """Xor for bitvalues (reflected argument version)."""
+ return GFElement(other ^ self.value)
+
def __mul__(self, other):
"""Multiplication."""
if not isinstance(other, (GFElement, int, long)):
diff -r 99a8a7c9cce5 -r 950815ab873f viff/passive.py
--- a/viff/passive.py Fri Mar 27 15:33:52 2009 +0100
+++ b/viff/passive.py Fri Mar 27 15:44:01 2009 +0100
@@ -214,7 +214,7 @@
def pow(self, share, exponent):
"""Exponentation of a share to an integer by square-and-multiply."""
- assert isinstance(exponent, int), "Exponent must be an integer"
+ assert isinstance(exponent, (int, long)), "Exponent must be an integer"
assert exponent >= 0, "Exponent must be non-negative"
if exponent == 0:
@@ -464,6 +464,32 @@
unless there is only one inputter in which case the
share is returned directly.
+ In code it is used like this::
+
+ a, b, c = runtime.shamir_share([1, 2, 3], Zp, x)
+
+ where ``Zp`` is a field and ``x`` is a Python integer holding
+ the input of each player (three inputs in total).
+
+ If only a subset of the players provide input it looks like
+ this::
+
+ if runtime.id == 1:
+ a = runtime.shamir_share([1], Zp, x)
+ else:
+ a = runtime.shamir_share([1], Zp)
+
+ Instead of branching when calling :meth:`shamir_share`, one
+ can give ``None`` as input::
+
+ if runtime.id == 1:
+ x = int(raw_input("Input x: "))
+ else:
+ x = None
+ a = runtime.shamir_share([1], Zp, x)
+
+ which might be practical in some cases.
+
Communication cost: n elements transmitted.
"""
assert number is None or self.id in inputters
diff -r 99a8a7c9cce5 -r 950815ab873f viff/runtime.py
--- a/viff/runtime.py Fri Mar 27 15:33:52 2009 +0100
+++ b/viff/runtime.py Fri Mar 27 15:44:01 2009 +0100
@@ -514,11 +514,11 @@
All connections are closed and the runtime cannot be used
again after this has been called.
"""
- print "Synchronizing shutdown... ",
+ print "Synchronizing shutdown...",
def close_connections(_):
print "done."
- print "Closing connections... ",
+ print "Closing connections...",
results = [maybeDeferred(self.port.stopListening)]
for protocol in self.protocols.itervalues():
results.append(protocol.lost_connection)
@@ -527,7 +527,7 @@
def stop_reactor(_):
print "done."
- print "Stopping reactor... ",
+ print "Stopping reactor...",
reactor.stop()
print "done."
diff -r 99a8a7c9cce5 -r 950815ab873f viff/test/rijndael.py
--- a/viff/test/rijndael.py Fri Mar 27 15:33:52 2009 +0100
+++ b/viff/test/rijndael.py Fri Mar 27 15:44:01 2009 +0100
@@ -36,109 +36,6 @@
# [keysize][block_size]
num_rounds = {16: {16: 10, 24: 12, 32: 14}, 24: {16: 12, 24: 12, 32: 14}, 32:
{16: 14, 24: 14, 32: 14}}
-A = [[1, 1, 1, 1, 1, 0, 0, 0],
- [0, 1, 1, 1, 1, 1, 0, 0],
- [0, 0, 1, 1, 1, 1, 1, 0],
- [0, 0, 0, 1, 1, 1, 1, 1],
- [1, 0, 0, 0, 1, 1, 1, 1],
- [1, 1, 0, 0, 0, 1, 1, 1],
- [1, 1, 1, 0, 0, 0, 1, 1],
- [1, 1, 1, 1, 0, 0, 0, 1]]
-
-# produce log and alog tables, needed for multiplying in the
-# field GF(2^m) (generator = 3)
-alog = [1]
-for i in xrange(255):
- j = (alog[-1] << 1) ^ alog[-1]
- if j & 0x100 != 0:
- j ^= 0x11B
- alog.append(j)
-
-log = [0] * 256
-for i in xrange(1, 255):
- log[alog[i]] = i
-
-# multiply two elements of GF(2^m)
-def mul(a, b):
- if a == 0 or b == 0:
- return 0
- return alog[(log[a & 0xFF] + log[b & 0xFF]) % 255]
-
-# substitution box based on F^{-1}(x)
-box = [[0] * 8 for i in xrange(256)]
-box[1][7] = 1
-for i in xrange(2, 256):
- j = alog[255 - log[i]]
- for t in xrange(8):
- box[i][t] = (j >> (7 - t)) & 0x01
-
-B = [0, 1, 1, 0, 0, 0, 1, 1]
-
-# affine transform: box[i] <- B + A*box[i]
-cox = [[0] * 8 for i in xrange(256)]
-for i in xrange(256):
- for t in xrange(8):
- cox[i][t] = B[t]
- for j in xrange(8):
- cox[i][t] ^= A[t][j] * box[i][j]
-
-# S-boxes and inverse S-boxes
-S = [0] * 256
-Si = [0] * 256
-for i in xrange(256):
- S[i] = cox[i][0] << 7
- for t in xrange(1, 8):
- S[i] ^= cox[i][t] << (7-t)
- Si[S[i] & 0xFF] = i
-
-# T-boxes
-G = [[2, 1, 1, 3],
- [3, 2, 1, 1],
- [1, 3, 2, 1],
- [1, 1, 3, 2]]
-
-AA = [[0] * 8 for i in xrange(4)]
-
-for i in xrange(4):
- for j in xrange(4):
- AA[i][j] = G[i][j]
- AA[i][i+4] = 1
-
-for i in xrange(4):
- pivot = AA[i][i]
- if pivot == 0:
- t = i + 1
- while AA[t][i] == 0 and t < 4:
- t += 1
- assert t != 4, 'G matrix must be invertible'
- for j in xrange(8):
- AA[i][j], AA[t][j] = AA[t][j], AA[i][j]
- pivot = AA[i][i]
- for j in xrange(8):
- if AA[i][j] != 0:
- AA[i][j] = alog[(255 + log[AA[i][j] & 0xFF] - log[pivot & 0xFF]) %
255]
- for t in xrange(4):
- if i != t:
- for j in xrange(i+1, 8):
- AA[t][j] ^= mul(AA[i][j], AA[t][i])
- AA[t][i] = 0
-
-iG = [[0] * 4 for i in xrange(4)]
-
-for i in xrange(4):
- for j in xrange(4):
- iG[i][j] = AA[i][j + 4]
-
-def mul4(a, bs):
- if a == 0:
- return 0
- r = 0
- for b in bs:
- r <<= 8
- if b != 0:
- r = r | mul(a, b)
- return r
-
T1 = []
T2 = []
T3 = []
@@ -152,48 +49,141 @@
U3 = []
U4 = []
-for t in xrange(256):
- s = S[t]
- T1.append(mul4(s, G[0]))
- T2.append(mul4(s, G[1]))
- T3.append(mul4(s, G[2]))
- T4.append(mul4(s, G[3]))
+S = [0] * 256
+Si = [0] * 256
- s = Si[t]
- T5.append(mul4(s, iG[0]))
- T6.append(mul4(s, iG[1]))
- T7.append(mul4(s, iG[2]))
- T8.append(mul4(s, iG[3]))
+rcon = [1]
- U1.append(mul4(t, iG[0]))
- U2.append(mul4(t, iG[1]))
- U3.append(mul4(t, iG[2]))
- U4.append(mul4(t, iG[3]))
+def initialize():
+ """Called once at module import to initialize constants defined above."""
-# round constants
-rcon = [1]
-r = 1
-for t in xrange(1, 30):
- r = mul(2, r)
- rcon.append(r)
+ A = [[1, 1, 1, 1, 1, 0, 0, 0],
+ [0, 1, 1, 1, 1, 1, 0, 0],
+ [0, 0, 1, 1, 1, 1, 1, 0],
+ [0, 0, 0, 1, 1, 1, 1, 1],
+ [1, 0, 0, 0, 1, 1, 1, 1],
+ [1, 1, 0, 0, 0, 1, 1, 1],
+ [1, 1, 1, 0, 0, 0, 1, 1],
+ [1, 1, 1, 1, 0, 0, 0, 1]]
-del A
-del AA
-del pivot
-del B
-del G
-del box
-del log
-del alog
-del i
-del j
-del r
-del s
-del t
-del mul
-del mul4
-del cox
-del iG
+ # produce log and alog tables, needed for multiplying in the
+ # field GF(2^m) (generator = 3)
+ alog = [1]
+ for i in xrange(255):
+ j = (alog[-1] << 1) ^ alog[-1]
+ if j & 0x100 != 0:
+ j ^= 0x11B
+ alog.append(j)
+
+ log = [0] * 256
+ for i in xrange(1, 255):
_______________________________________________
viff-commits mailing list
[email protected]
http://lists.viff.dk/listinfo.cgi/viff-commits-viff.dk
