Monthly Archives: February 2012

My favorite quotes (II)

Posted on by
Reply

“If Java had true garbage collection, most programs would delete themselves upon execution.”
Robert Sewell

“If debugging is the process of removing bugs, then programming must be the process of putting them in.”
Edsger W. Dijkstra

“Programming can be fun, so can cryptography; however they should not be combined.”
Kreitzberg and Shneiderman

“Science is what we understand well enough to explain to a computer. Art is everything else we do.”
Donald Knuth

“In C++ it’s harder to shoot yourself in the foot, but when you do, you blow off your whole leg.”
Bjarne Stroustrup

“Software is getting slower more rapidly than hardware becomes faster.”
Niklaus Wirth

“A computer once beat me at chess, but it was no match for me at kick boxing.”
Emo Philips

“A refund for defective software might be nice, except it would bankrupt the entire software industry in the first year.”
Andrew Tanenbaum

“Quantum mechanic Seth Lloyd says the universe is one giant, hackable computer. Let’s hope it’s not running Windows.”
Kevin Kelly

“Any sufficiently advanced technology is indistinguishable from magic.”
Arthur Clarke

“Any sufficiently advanced bug is indistinguishable from a feature.”
Rich Kulawiec

“From a programmer’s point of view, the user is a peripheral that types when you issue a read request.”
Peter Williams

“The teaching of BASIC should be rated as a criminal offence: it mutilates the mind beyond recovery.”
Edsger Dijkstra

“Real Programmers always confuse Christmas and Halloween because Oct31 == Dec25.”
Andrew Rutherford

“When your work speaks for itself, don’t interrupt.”
Henry Kaiser

“Real men don’t use backups. They post their stuff on a public ftp server and let the rest of the world make copies.”
Linus Torvalds

“Premature optimization is the root of all evil.”
Donald Knuth

“GOTO is a four letter word.”
Edsger Dijkstra

“unzip; strip; touch; finger; mount; fsck; more; yes; unmount; sleep”
anonymous

“If it wasn’t for C, we’d be writing programs in BASI, PASAL, and OBOL.”
anonymous

“SQL, Lisp, and Haskell are the only programming languages that I’ve seen where one spends more time thinking than typing.”
Philip Greenspun

“There are two ways of constructing a software design: one way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies.”
Tony Hoare

“If you don’t want to be replaced by a computer, don’t act like one.”
Arno Penzias

“God exists since mathematics is consistent, and the Devil exists since we cannot prove it.”
André Weil

“Machines should work. People should think.”
Richard Hamming

“Good judgement comes from experience, and experience comes from bad judgement.”
Fred Brooks

“The limits of my language mean the limits of my world.”
Ludwig Wittgenstein

RTFM
Linpack Users’ Guide

Multiplication over the binary finite field GF(2^m)

Posted on by
Reply

The multGF2() function shown in the Python script below implements the element (polynomial) multiplication over a binary finite field GF(2^{m}). The second function, setGF2(), sets the three constants needed for its colleague to perform its multiplication task: "mask1" and "mask2" (used in “and” operations) and "polyred", a polynomial constant used in the polynomial reduction of the product. These constants are defined from the parameters passed to setGF2(): "degree" (the extension degree of the binary field GF(2^{m})) and "irPoly" (the irreducible polynomial used for the product reduction). The version of multGF2() in the post AES implementation in Python, dubbed “mult()“, was configured specifically for the AES binary finite field used in the MixColumns operation, GF(2^{8})/x^{8} + x^{4} + x^{3} + x + 1.

#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: Binary finite field multiplication in Python 3
#
# Date: 2012-02-16
#
# License: Attribution-NonCommercial-ShareAlike 3.0 Unported
#          (CC BY-NC-SA 3.0)
#===========================================================
from functools import reduce

# constants used in the multGF2 function
mask1 = mask2 = polyred = None

def setGF2(degree, irPoly):
    """Define parameters of binary finite field GF(2^m)/g(x)
       - degree: extension degree of binary field
       - irPoly: coefficients of irreducible polynomial g(x)
    """
    global mask1, mask2, polyred
    mask1 = mask2 = 1 << degree
    mask2 -= 1
    if sum(irPoly) <= len(irPoly):
        polyred = reduce(lambda x, y: (x << 1) + y, irPoly[1:])    
    else:
        polyred = poly2Int(irPoly[1:]) 
        
def multGF2(p1, p2):
    """Multiply two polynomials in GF(2^m)/g(x)"""
    p = 0
    while p2:
        if p2 & 1:
            p ^= p1
        p1 <<= 1
        if p1 & mask1:
            p1 ^= polyred
        p2 >>= 1
    return p & mask2

#=============================================================================
#                        Auxiliary formatting functions
#=============================================================================
def int2Poly(bInt):
    """Convert a "big" integer into a "high-degree" polynomial"""
    exp = 0
    poly = []
    while bInt:
        if bInt & 1:
            poly.append(exp)
        exp += 1
        bInt >>= 1
    return poly[::-1]

def poly2Int(hdPoly):
    """Convert a "high-degree" polynomial into a "big" integer"""
    bigInt = 0
    for exp in hdPoly:
        bigInt += 1 << exp
    return bigInt

def i2P(sInt):
    """Convert a "small" integer into a "low-degree" polynomial"""
    return [(sInt >> i) & 1 for i in reversed(range(sInt.bit_length()))]

def p2I(ldPoly):
    """Convert a "low-degree" polynomial into a "small" integer"""
    return reduce(lambda x, y: (x << 1) + y, ldPoly)

def ldMultGF2(p1, p2):
    """Multiply two "low-degree" polynomials in GF(2^n)/g(x)"""
    return multGF2(p2I(p1), p2I(p2))

def hdMultGF2(p1, p2):
    """Multiply two "high-degree" polynomials in GF(2^n)/g(x)"""
    return multGF2(poly2Int(p1), poly2Int(p2))

if __name__ == "__main__":
  
    # Define binary field GF(2^3)/x^3 + x + 1
    setGF2(3, [1, 0, 1, 1])
    
    # Alternative way to define GF(2^3)/x^3 + x + 1
    setGF2(3, i2P(0b1011))    
    
    # Check if (x + 1)(x^2 + 1) == x^2
    assert ldMultGF2([1, 1], [1, 0, 1]) == p2I([1, 0, 0])

    # Check if (x^2 + x + 1)(x^2 + 1) == x^2 + x
    assert ldMultGF2([1, 1, 1], [1, 0, 1]) == p2I([1, 1, 0])
    
    # Define binary field GF(2^8)/x^8 + x^4 + x^3 + x + 1
    setGF2(8, [1, 0, 0, 0, 1, 1, 0, 1, 1])
    
    # Alternative way to define GF(2^8)/x^8 + x^4 + x^3 + x + 1
    setGF2(8, i2P(0b100011011))
    
    # Check if (x)(x^7 + x^2 + x + 1) == x^4 + x^2 + 1
    assert ldMultGF2([1, 0], [1, 0, 0, 0, 0, 1, 1, 1]) == p2I([1, 0, 1, 0, 1])
    
    # Check if (x + 1)(x^6 + x^5 + x^3 + x^2 + x) == x^7 + x^5 + x^4 + x
    assert ldMultGF2([1, 1], [1, 1, 0, 1, 1, 1, 0]) == p2I([1, 0, 1, 1, 0, 0, 1, 0])

    # Define binary field GF(2^571)/x^571 + x^10 + x^5 + x^2 + x
    setGF2(571, [571, 10, 5, 2, 1])

    # Calculate the product of two polynomials in GF(2^571)/x^571 + x^10 + x^5 + x^2 + x,
    # x^518 + x^447 + x^320 + x^209 + x^119 + x + 1 and x^287 + x^145 + x^82 + + x^44
    print(int2Poly(hdMultGF2([518, 447, 320, 209, 119, 1, 0], [287, 145, 82, 44])))

The output of the above script is:

[562, 529, 496, 491, 465, 406, 402, 364, 354, 291, 288, 287, 264, 253, 244,
239, 235, 201, 173, 168, 165, 164, 163, 146, 145, 102, 97, 94, 93, 83, 82,
46, 45, 44, 41, 39, 38, 37, 34, 30, 26, 23, 22]

This means that the product of the polynomials x^{518} + x^{447} + x^{320} + x^{209} + x^{119} + x + 1 and x^{287} + x^{145} + x^{82} + x^{44} is:

x^562 + x^529 + x^496 + x^491 + x^465 + x^406 + x^402 + x^364 + x^354 +
x^291 + x^288 + x^287 + x^264 + x^253 + x^244 + x^239 + x^236 + x^235 +
x^201 + x^173 + x^168 + x^165 + x^164 + x^163 + x^146 + x^145 + x^102 +
x^97 + x^94 + x^93 + x^83 + x^82 + x^46 + x^45 + x^44 + x^41 + x^39 +
x^38 + x^37 + x^34 + x^30 + x^26 + x^23 + x^22

An elegant algorithm for calculating Hamming distance

Posted on by
5

Generally speaking, the Hamming distance between two strings of the same length is the number of positions in which the corresponding symbols are different. This metric, proposed by Richard W. Hamming in his seminal paper “Error Detecting and Error Correcting Codes”, Bell System Technical Journal 26(2):147-160 (1950), also expresses the least number of (intended or unintended) substitutions needed to change one string to another.

Besides being used in computer- and communications-related fields such as information theory, coding theory, and cryptography, the Hamming distance concept has also found its way into genomics for the comparison of genomic sequences. Its importance can also be judged by the fact that modern microprocessors have a specific instruction (POPCNT, “population count”) for counting the number of bits set to 1.

Assuming two bit strings of equal length, x and y, the “obvious” algorithm to calculate the Hamming distance between them is to count the number of “1” bits in the result of the expression “x xor y”, as shown in the following Python code:

def hamming1(x,y):
    """Calculate the Hamming distance between two bit strings"""
    assert len(x) == len(y)
    count,z = 0,int(x,2)^int(y,2)
    while z:
        if z&1:
            count += 1
        z >>= 1
    return count

While searching the web the other day, I have come across a very elegant algorithm for the same purpose, which can be coded in Python as follows:

def hamming2(x,y):
    """Calculate the Hamming distance between two bit strings"""
    assert len(x) == len(y)
    count,z = 0,int(x,2)^int(y,2)
    while z:
        count += 1
        z &= z-1 # magic!
    return count

Apart from being 50% faster than the first one, its simplicity is awesome! After being counted, the lowest-order nonzero bit is cleared like magic! When I started a new search later, this time looking for the algorithm’s authorship, I finally learned that it was proposed by Peter Wegner in 1960 (“A technique for counting ones in a binary computer“, Communications of the ACM 3 (5): 322).

Where did I find this information? The answer was, talking again about “obvious” things, in the very same Wikipedia’s entry for “Hamming distance“! This little gem has been there for at least a year (according to the entry’s history), just waiting to be discovered! Quoting Antoine de Saint Exupéry, “You know you have achieved perfection in design, not when you have nothing more to add, but when you have nothing more to take away.”

Simplified AES implementation in Python

Posted on by
Reply

Simplified AES, created by Edward Schaefer and two of his students at Santa Clara University in 2003, is described in the paper “A Simplified AES Algorithm and Its Linear and Differential Cryptoanalyses”, Cryptologia, Vol. XXVII (2), pages 148-177. Like Simplified DES, its purpose is educational, since its key and block size are very small (16-bit and 8-bit, respectively). Nonetheless, due to its simplicity, it is possible for students to encrypt or decrypt a block doing all operations by hand, making it easier for them to understand the structure and operation of its elder brother, AES.

#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: Simplified AES implementation in Python 3
#
# Date: 2012-02-11
#
# License: Attribution-NonCommercial-ShareAlike 3.0 Unported
#          (CC BY-NC-SA 3.0)
#===========================================================
import sys

# S-Box
sBox  = [0x9, 0x4, 0xa, 0xb, 0xd, 0x1, 0x8, 0x5,
         0x6, 0x2, 0x0, 0x3, 0xc, 0xe, 0xf, 0x7]

# Inverse S-Box
sBoxI = [0xa, 0x5, 0x9, 0xb, 0x1, 0x7, 0x8, 0xf,
         0x6, 0x0, 0x2, 0x3, 0xc, 0x4, 0xd, 0xe]

# Round keys: K0 = w0 + w1; K1 = w2 + w3; K2 = w4 + w5
w = [None] * 6

def mult(p1, p2):
    """Multiply two polynomials in GF(2^4)/x^4 + x + 1"""
    p = 0
    while p2:
        if p2 & 0b1:
            p ^= p1
        p1 <<= 1
        if p1 & 0b10000:
            p1 ^= 0b11
        p2 >>= 1
    return p & 0b1111

def intToVec(n):
    """Convert a 2-byte integer into a 4-element vector"""
    return [n >> 12, (n >> 4) & 0xf, (n >> 8) & 0xf,  n & 0xf]            

def vecToInt(m):
    """Convert a 4-element vector into 2-byte integer"""
    return (m[0] << 12) + (m[2] << 8) + (m[1] << 4) + m[3]

def addKey(s1, s2):
    """Add two keys in GF(2^4)"""   
    return [i ^ j for i, j in zip(s1, s2)]
    
def sub4NibList(sbox, s):
    """Nibble substitution function"""
    return [sbox[e] for e in s]
    
def shiftRow(s):
    """ShiftRow function"""
    return [s[0], s[1], s[3], s[2]]

def keyExp(key):
    """Generate the three round keys"""
    def sub2Nib(b):
        """Swap each nibble and substitute it using sBox"""
        return sBox[b >> 4] + (sBox[b & 0x0f] << 4)

    Rcon1, Rcon2 = 0b10000000, 0b00110000
    w[0] = (key & 0xff00) >> 8
    w[1] = key & 0x00ff
    w[2] = w[0] ^ Rcon1 ^ sub2Nib(w[1])
    w[3] = w[2] ^ w[1]
    w[4] = w[2] ^ Rcon2 ^ sub2Nib(w[3])
    w[5] = w[4] ^ w[3]

def encrypt(ptext):
    """Encrypt plaintext block"""
    def mixCol(s):
        return [s[0] ^ mult(4, s[2]), s[1] ^ mult(4, s[3]),
                s[2] ^ mult(4, s[0]), s[3] ^ mult(4, s[1])]    
    
    state = intToVec(((w[0] << 8) + w[1]) ^ ptext)
    state = mixCol(shiftRow(sub4NibList(sBox, state)))
    state = addKey(intToVec((w[2] << 8) + w[3]), state)
    state = shiftRow(sub4NibList(sBox, state))
    return vecToInt(addKey(intToVec((w[4] << 8) + w[5]), state))
    
def decrypt(ctext):
    """Decrypt ciphertext block"""
    def iMixCol(s):
        return [mult(9, s[0]) ^ mult(2, s[2]), mult(9, s[1]) ^ mult(2, s[3]),
                mult(9, s[2]) ^ mult(2, s[0]), mult(9, s[3]) ^ mult(2, s[1])]
    
    state = intToVec(((w[4] << 8) + w[5]) ^ ctext)
    state = sub4NibList(sBoxI, shiftRow(state))
    state = iMixCol(addKey(intToVec((w[2] << 8) + w[3]), state))
    state = sub4NibList(sBoxI, shiftRow(state))
    return vecToInt(addKey(intToVec((w[0] << 8) + w[1]), state))

if __name__ == '__main__':
    # Test vectors from "Simplified AES" (Steven Gordon)
    # (http://hw.siit.net/files/001283.pdf)
    
    plaintext = 0b1101011100101000
    key = 0b0100101011110101
    ciphertext = 0b0010010011101100
    keyExp(key)
    try:
        assert encrypt(plaintext) == ciphertext
    except AssertionError:
        print("Encryption error")
        print(encrypt(plaintext), ciphertext)
        sys.exit(1)
    try:
        assert decrypt(ciphertext) == plaintext
    except AssertionError:
        print("Decryption error")
        print(decrypt(ciphertext), plaintext)
        sys.exit(1)
    print("Test ok!")
    sys.exit()

Simplified DES implementation in Python

Posted on by
Reply

Simplified DES (SDES) is a cryptographic algorithm developed by Edward Schaefer in 1986 with educational purposes and published in “A simplified data encryption algorithm”, Cryptologia, 20(1):77–84. Simplified DES is considered a “toy” crypto algorithm since it uses a very short key (10-bits). Messages encrypted with SDES can be broken by brute force in a tiny fraction of a second, after only 512 trials on average. Nevertheless, it helps students grasp some features of its strong brother, the Data Encryption Standard (DES), without the complexities of a real world algorithm. SDES accepts an 8-bit block as input (plaintext) and produces an 8-bit block (ciphertext) in just 2 rounds. Compare these numbers with those of DES: 64-bit block, 56-bits key, 16 rounds. As mentioned in a previous post, DES implementation in Python, implementing SDES in Python was my warm-up session before coding DES.

#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: Simplified DES implementation in Python 3
#
# Date: 2012-02-10
#
# License: Attribution-NonCommercial-ShareAlike 3.0 Unported
#          (CC BY-NC-SA 3.0)
#===========================================================
from sys import exit
from time import time

KeyLength = 10
SubKeyLength = 8
DataLength = 8
FLength = 4

# Tables for initial and final permutations (b1, b2, b3, ... b8)
IPtable = (2, 6, 3, 1, 4, 8, 5, 7)
FPtable = (4, 1, 3, 5, 7, 2, 8, 6)

# Tables for subkey generation (k1, k2, k3, ... k10)
P10table = (3, 5, 2, 7, 4, 10, 1, 9, 8, 6)
P8table = (6, 3, 7, 4, 8, 5, 10, 9)

# Tables for the fk function
EPtable = (4, 1, 2, 3, 2, 3, 4, 1)
S0table = (1, 0, 3, 2, 3, 2, 1, 0, 0, 2, 1, 3, 3, 1, 3, 2)
S1table = (0, 1, 2, 3, 2, 0, 1, 3, 3, 0, 1, 0, 2, 1, 0, 3)
P4table = (2, 4, 3, 1)

def perm(inputByte, permTable):
    """Permute input byte according to permutation table"""
    outputByte = 0
    for index, elem in enumerate(permTable):
        if index >= elem:
            outputByte |= (inputByte & (128 >> (elem - 1))) >> (index - (elem - 1))
        else:
            outputByte |= (inputByte & (128 >> (elem - 1))) << ((elem - 1) - index)
    return outputByte

def ip(inputByte):
    """Perform the initial permutation on data"""
    return perm(inputByte, IPtable)

def fp(inputByte):
    """Perform the final permutation on data"""
    return perm(inputByte, FPtable)

def swapNibbles(inputByte):
    """Swap the two nibbles of data"""
    return (inputByte << 4 | inputByte >> 4) & 0xff

def keyGen(key):
    """Generate the two required subkeys"""
    def leftShift(keyBitList):
        """Perform a circular left shift on the first and second five bits"""
        shiftedKey = [None] * KeyLength
        shiftedKey[0:9] = keyBitList[1:10]
        shiftedKey[4] = keyBitList[0]
        shiftedKey[9] = keyBitList[5]
        return shiftedKey

    # Converts input key (integer) into a list of binary digits
    keyList = [(key & 1 << i) >> i for i in reversed(range(KeyLength))]
    permKeyList = [None] * KeyLength
    for index, elem in enumerate(P10table):
        permKeyList[index] = keyList[elem - 1]
    shiftedOnceKey = leftShift(permKeyList)
    shiftedTwiceKey = leftShift(leftShift(shiftedOnceKey))
    subKey1 = subKey2 = 0
    for index, elem in enumerate(P8table):
        subKey1 += (128 >> index) * shiftedOnceKey[elem - 1]
        subKey2 += (128 >> index) * shiftedTwiceKey[elem - 1]
    return (subKey1, subKey2)

def fk(subKey, inputData):
    """Apply Feistel function on data with given subkey"""
    def F(sKey, rightNibble):
        aux = sKey ^ perm(swapNibbles(rightNibble), EPtable)
        index1 = ((aux & 0x80) >> 4) + ((aux & 0x40) >> 5) + \
                 ((aux & 0x20) >> 5) + ((aux & 0x10) >> 2)
        index2 = ((aux & 0x08) >> 0) + ((aux & 0x04) >> 1) + \
                 ((aux & 0x02) >> 1) + ((aux & 0x01) << 2)
        sboxOutputs = swapNibbles((S0table[index1] << 2) + S1table[index2])
        return perm(sboxOutputs, P4table)

    leftNibble, rightNibble = inputData & 0xf0, inputData & 0x0f
    return (leftNibble ^ F(subKey, rightNibble)) | rightNibble

def encrypt(key, plaintext):
    """Encrypt plaintext with given key"""
    data = fk(keyGen(key)[0], ip(plaintext))
    return fp(fk(keyGen(key)[1], swapNibbles(data)))

def decrypt(key, ciphertext):
    """Decrypt ciphertext with given key"""
    data = fk(keyGen(key)[1], ip(ciphertext))
    return fp(fk(keyGen(key)[0], swapNibbles(data)))  

if __name__ == '__main__':
    # Test vectors described in "Simplified DES (SDES)"
    # (http://www2.kinneret.ac.il/mjmay/ise328/328-Assignment1-SDES.pdf)

    try:
        assert encrypt(0b0000000000, 0b10101010) == 0b00010001
    except AssertionError:
        print("Error on encrypt:")
        print("Output: ", encrypt(0b0000000000, 0b10101010), "Expected: ", 0b00010001)
        exit(1)
    try:
        assert encrypt(0b1110001110, 0b10101010) == 0b11001010
    except AssertionError:
        print("Error on encrypt:")
        print("Output: ", encrypt(0b1110001110, 0b10101010), "Expected: ", 0b11001010)
        exit(1)
    try:
        assert encrypt(0b1110001110, 0b01010101) == 0b01110000
    except AssertionError:
        print("Error on encrypt:")
        print("Output: ", encrypt(0b1110001110, 0b01010101), "Expected: ", 0b01110000)
        exit(1)
    try:
        assert encrypt(0b1111111111, 0b10101010) == 0b00000100
    except AssertionError:
        print("Error on encrypt:")
        print("Output: ", encrypt(0b1111111111, 0b10101010), "Expected: ", 0b00000100)
        exit(1)

    t1 = time()
    for i in range(1000):
        encrypt(0b1110001110, 0b10101010)
    t2 = time()
    print("Elapsed time for 1,000 encryptions: {:0.3f}s".format(t2 - t1))
    exit()

Generating Permutations From Factoradic Numbers

Posted on by
Reply

This is the title of an interesting tutorial by Prof. Joel Guilherme S. Filho. It describes how to generate permutations of a set of n elements from a given decimal index based on its representation as a “factoradic number”, i.e. a number represented in the mixed base [(n-1)!, (n-2)!, … , 2!, 1!, 0!].

Thanks to the list manipulation facilities and the support for arbitrary long integers provided by the Python programming language, it’s easy to write a short script (shown below) that generates permutations even for large indexes. Please read his tutorial for additional details.

#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: Generating Permutations From Factoradic Numbers
#
# Date: 2012-02-06
#
# License: Attribution-NonCommercial-ShareAlike 3.0 Unported
#          (CC BY-NC-SA 3.0)
#=============================================================
from sys import argv
from math import factorial

N = int(argv[1])

n = 0
while N > factorial(n):
    n += 1

S = [i for i in range(n)]
Factoradic, Permutation = [None] * n, [None] * n

v, s = N, S[:]
for i in range(n):
    r, v = divmod(v, factorial(n - i - 1))
    Factoradic[i], Permutation[i] = r, s.pop(r)

print("For N = {:d}\n".format(N))
print("n = {:d}\n".format(n))
print("Permutation[0] = {:s}\n".format(S))
print("Factoradic[N] = {:s}\n".format(Factoradic))
print("Permutation[N] = {:s}\n".format(Permutation))

Executing this script with 51 as the command-line argument, we get the output below:

For N = 51

n = 5

Perm[0] = [0, 1, 2, 3, 4]

Factoradic[N] = [2, 0, 1, 1, 0]

Permutation[N] = [2, 0, 3, 4, 1]

Trying now a big number like the Mersenne number \small 2^{607} - 1 (which happens to be the Mersenne prime # 14), we get the following results:

For N = 53113799281676709868958820655246862732959311772703192319944413 ... 29486246501015346579337652707239409519978766587351943831270835393219031728127

n = 113

Permutation[0] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112]

Factoradic[N] = [2, 77, 30, 88, 71, 102, 97, 70, 4, 12, 75, 71, 27, 9, 91, 43, 75, 58, 30, 73, 10, 11, 68, 33, 77, 79, 50, 80, 41, 77, 48, 5, 32, 78, 25, 74, 0, 9, 49, 3, 43, 14, 6, 20, 2, 6, 61, 14, 29, 7, 37, 41, 5, 15, 30, 54, 26, 0, 41, 19, 29, 50, 6, 6, 2, 25, 6, 8, 44, 10, 26, 13, 16, 0, 14, 4, 5, 24, 24, 30, 22, 6, 6, 29, 10, 24, 12, 23, 3, 20, 15, 20, 16, 11, 12, 7, 2, 15, 10, 5, 5, 8, 6, 7, 2, 0, 0, 1, 0, 1, 0, 1, 0]

Permutation[N] = [2, 78, 31, 91, 73, 107, 102, 72, 5, 14, 82, 77, 30, 11, 104, 49, 87, 65, 36, 88, 13, 16, 84, 42, 98, 101, 61, 106, 52, 103, 60, 7, 43, 111, 34, 108, 0, 17, 69, 6, 63, 24, 12, 35, 4, 18, 99, 28, 53, 20, 67, 75, 15, 37, 58, 105, 54, 1, 85, 45, 64, 110, 22, 23, 9, 62, 26, 32, 112, 39, 74, 46, 51, 3, 50, 25, 29, 83, 86, 96, 80, 38, 40, 109, 55, 94, 59, 95, 21, 92, 76, 97, 81, 66, 70, 47, 19, 100, 71, 44, 48, 79, 57, 89, 27, 8, 10, 41, 33, 68, 56, 93, 90]

My favorite quotes (I)

Posted on by
Reply

“My hands tell me what I am thinking.”
Pablo Picasso

“A distributed system is one in which the failure of a computer you didn’t even know existed can render your own computer unusable.”
Leslie Lamport

“You know you have achieved perfection in design, not when you have nothing more to add, but when you have nothing more to take away.”
Antoine de Saint Exupéry

“Never trust a computer you can’t lift.”
(anonymous)

“Language shapes the way we think and determines what we can think about.”
Benjamin Whorf

“To err is human. To blame it on a computer is even more.”
(anonymous)

“Experience is what you get when you didn’t get what you wanted.”
(anonymous)

“Prediction is difficult, especially of the future.”
Niels Bohr

“A script is what you hand to the actors. A program is what you hand to the audience.”
Larry Wall

“Whatever you do will be insignificant, but it is very important that you do it.”
Mahatma Gandhi

“I think there is a world market for maybe five computers.”
Thomas J Watson

“There is no reason anyone would want a computer in their home.”
Ken Olsen

“640 kb ought to be enough for anybody.”
Bill Gates

“Research is what I’m doing when I don’t know what I’m doing.”
Wernher von Braun

“The truth is more important than the facts.”
Frank Lloyd Wright

“Not everything that can be counted counts, and not everything that counts can be counted.”
Albert Einstein

“In God we trust. All others we monitor.”
NSA

“Cryptology is about communication in the presence of adversaries.”
Ron Rivest

“If you would wish another to keep your secret, first keep it yourself.”
Hippolytus

“Software is like sex: it’s better when it’s free.”
Linus Torvalds

“The nice thing about standards is that there are so many to choose from.”
Andrew Tannenbaum

“The best way to predict the future is to invent it.”
Alan Kay

“My name is dump, core dump.”
(anonymous)

“All generalizations are false, including this one.”
Mark Twain

“If builders built houses the way programmers built programs, the first woodpecker to come along would destroy civilization.”
Gerald Weinberg

“The wise man doesn’t give the right answers, he poses the right questions.”
Claude Levi-Strauss

“When you trade freedom for security you get neither.”
Thomas Jefferson

“Why are you ruining my beautiful mathematics by choosing a lousy password?”
Bruce Schneier

“In theory there is no difference between theory and practice. In practice there is.”
(anonymous)

“She sells C shells by the seashore.”
(anonymous)

“It isn’t a bug. It’s a feature.”
Microsoft

“What you see is all you get.”
Brian Kernighan

“Seek simplicity, but distrust it.”
Alfred North Whitehead

“To be or not to be is true.”
George Boole

“Form follows function.”
Louis Sullivan

“Programs must be written for people to read, and only incidentally for machines to execute.”
Abelson and Sussman

“I have made this letter longer because I have not had the time to make it shorter.”
Blaise Pascal

“The use of COBOL cripples the mind; its teaching should, therefore, be regarded as a criminal offence.”
Edsger Dijkstra

“What’s mind? No matter. What’s matter? Never mind.”
Bertrand Russell

Ella Fitzgerald with the Tommy Flanagan Trio

Posted on by
1

Ella Fitzgerald (1917-1996) is considered beyond a shadow of doubt one of the American greatest jazz singers of all times. During her long artistic career (almost 60 years), Lady Ella’s had played with jazz giants such as singer and trumpeter Louis Armstrong, bandleaders Count Basie and Duke Ellington and guitarist Joe Pass. Her perfect diction, phrasing and intonation and her incredible voice range (which spanned over three octaves!) made the First Lady of Song famous worldwide.

The songs of this album were recorded live at the 1977 Montreux Jazz Festival with the Tommy Flanagan Trio (Tommy Flanagan-piano, Keter Betts-bass and Bobby Durham-drums). Fitzgerald’s outstanding vocal abilities matched perfectly with TFT’s superb jazz support. After all, it was not the first time they had met: they had been playing together since 1965.

Their presentation opened with Too Close for Comfort. In the sequence, Montreux’s audience was presented with jazz classics (I Ain’t Got Nothing But the Blues and Come Rain or Come Shine) along with other not so known songs (My Man, Ordinary Fool, I Let a Song Go Out of My Heart). Tom Jobim’s One Note Samba offered an excellent opportunity for Fitzgerald to show her famous scat singing (it should be noted that Jobim himself has written the English lyrics for One Note Samba). Finally, You Are The Sunshine of My Life closed the show.

It was a brilliant jazz evening for the Swiss audience, as we can tell by the final applause. Except for those happy few who had the opportunity to attend the presentation, the only thing that remains for the vast majority that could not do the same is to buy the CD. Recommended!

CLEFIA implementation in Python (improved version)

Posted on by
Reply

As commented in my last post, CLEFIA implementation in Python, the performance figures for key setup and block encryption of my first coding attempt were poor when compared to those of AES.

Nevertheless, in order to establish a fair comparison between the two implementations, I included in CLEFIA’s code the same optimization technique used in AES, memoization, for speeding up the multiplication in the binary finite field GF(2^8). For this purpose, the generic multiplication function used in the first version was replaced by five memoized functions, x2(), x4(), x6(), x8() and x10(), thanks to the fact that there are only five different constants (besides the multiplicative identity of the field, 1) in the matrices m0 and m1.

The payback of this small effort was remarkable: the new code is 7 times(!) faster than the old, as the time required for the 128-bit key setup plus block encryption (in ECB mode) went down from 3.8 ms to 0.5 ms. A similar reduction was observed for 192- and 256-bit keys: from 5.2ms to 0.7 ms and 5.7 ms to 0.77 ms. All numbers were observed in a Core i7-2600K @ 3.5 GHz desktop running 64-bit Windows 7. The Python interpreter used was ActivePython-3.2.2.3-win64-x64.

#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: CLEFIA implementation in Python 3
#
# Date: 2012-02-03
#
# License: Attribution-NonCommercial-ShareAlike 3.0 Unported
#          (CC BY-NC-SA 3.0)
#===========================================================
import sys
from time import time

# Key sizes supported
ksTable = {"SIZE_128": 16,
           "SIZE_192": 24,
           "SIZE_256": 32}

# Number of rounds related to key size
nrTable = {"SIZE_128": 18,
           "SIZE_192": 22,
           "SIZE_256": 26}

# Number of round keys related to key size
nrkTable = {"SIZE_128": 36,
            "SIZE_192": 44,
            "SIZE_256": 52}

# Number of rounds
nr = None

# Number of round keys effectively used
nrk = None

# Number of whitening keys
nwk = 4

# Round keys vector
rk = [None] * 2 * nrTable[max(nrTable)]

# Whitening keys
wk = [None] * 4

# First S-Box
s0 = [0x57, 0x49, 0xd1, 0xc6, 0x2f, 0x33, 0x74, 0xfb,
      0x95, 0x6d, 0x82, 0xea, 0x0e, 0xb0, 0xa8, 0x1c,
      0x28, 0xd0, 0x4b, 0x92, 0x5c, 0xee, 0x85, 0xb1,
      0xc4, 0x0a, 0x76, 0x3d, 0x63, 0xf9, 0x17, 0xaf,
      0xbf, 0xa1, 0x19, 0x65, 0xf7, 0x7a, 0x32, 0x20,
      0x06, 0xce, 0xe4, 0x83, 0x9d, 0x5b, 0x4c, 0xd8,
      0x42, 0x5d, 0x2e, 0xe8, 0xd4, 0x9b, 0x0f, 0x13,
      0x3c, 0x89, 0x67, 0xc0, 0x71, 0xaa, 0xb6, 0xf5,
      0xa4, 0xbe, 0xfd, 0x8c, 0x12, 0x00, 0x97, 0xda,
      0x78, 0xe1, 0xcf, 0x6b, 0x39, 0x43, 0x55, 0x26,
      0x30, 0x98, 0xcc, 0xdd, 0xeb, 0x54, 0xb3, 0x8f,
      0x4e, 0x16, 0xfa, 0x22, 0xa5, 0x77, 0x09, 0x61,
      0xd6, 0x2a, 0x53, 0x37, 0x45, 0xc1, 0x6c, 0xae,
      0xef, 0x70, 0x08, 0x99, 0x8b, 0x1d, 0xf2, 0xb4,
      0xe9, 0xc7, 0x9f, 0x4a, 0x31, 0x25, 0xfe, 0x7c,
      0xd3, 0xa2, 0xbd, 0x56, 0x14, 0x88, 0x60, 0x0b,
      0xcd, 0xe2, 0x34, 0x50, 0x9e, 0xdc, 0x11, 0x05,
      0x2b, 0xb7, 0xa9, 0x48, 0xff, 0x66, 0x8a, 0x73,
      0x03, 0x75, 0x86, 0xf1, 0x6a, 0xa7, 0x40, 0xc2,
      0xb9, 0x2c, 0xdb, 0x1f, 0x58, 0x94, 0x3e, 0xed,
      0xfc, 0x1b, 0xa0, 0x04, 0xb8, 0x8d, 0xe6, 0x59,
      0x62, 0x93, 0x35, 0x7e, 0xca, 0x21, 0xdf, 0x47,
      0x15, 0xf3, 0xba, 0x7f, 0xa6, 0x69, 0xc8, 0x4d,
      0x87, 0x3b, 0x9c, 0x01, 0xe0, 0xde, 0x24, 0x52,
      0x7b, 0x0c, 0x68, 0x1e, 0x80, 0xb2, 0x5a, 0xe7,
      0xad, 0xd5, 0x23, 0xf4, 0x46, 0x3f, 0x91, 0xc9,
      0x6e, 0x84, 0x72, 0xbb, 0x0d, 0x18, 0xd9, 0x96,
      0xf0, 0x5f, 0x41, 0xac, 0x27, 0xc5, 0xe3, 0x3a,
      0x81, 0x6f, 0x07, 0xa3, 0x79, 0xf6, 0x2d, 0x38,
      0x1a, 0x44, 0x5e, 0xb5, 0xd2, 0xec, 0xcb, 0x90,
      0x9a, 0x36, 0xe5, 0x29, 0xc3, 0x4f, 0xab, 0x64,
      0x51, 0xf8, 0x10, 0xd7, 0xbc, 0x02, 0x7d, 0x8e]

# Second S-Box
s1 = [0x6c, 0xda, 0xc3, 0xe9, 0x4e, 0x9d, 0x0a, 0x3d,
      0xb8, 0x36, 0xb4, 0x38, 0x13, 0x34, 0x0c, 0xd9,
      0xbf, 0x74, 0x94, 0x8f, 0xb7, 0x9c, 0xe5, 0xdc,
      0x9e, 0x07, 0x49, 0x4f, 0x98, 0x2c, 0xb0, 0x93,
      0x12, 0xeb, 0xcd, 0xb3, 0x92, 0xe7, 0x41, 0x60,
      0xe3, 0x21, 0x27, 0x3b, 0xe6, 0x19, 0xd2, 0x0e,
      0x91, 0x11, 0xc7, 0x3f, 0x2a, 0x8e, 0xa1, 0xbc,
      0x2b, 0xc8, 0xc5, 0x0f, 0x5b, 0xf3, 0x87, 0x8b,
      0xfb, 0xf5, 0xde, 0x20, 0xc6, 0xa7, 0x84, 0xce,
      0xd8, 0x65, 0x51, 0xc9, 0xa4, 0xef, 0x43, 0x53,
      0x25, 0x5d, 0x9b, 0x31, 0xe8, 0x3e, 0x0d, 0xd7,
      0x80, 0xff, 0x69, 0x8a, 0xba, 0x0b, 0x73, 0x5c,
      0x6e, 0x54, 0x15, 0x62, 0xf6, 0x35, 0x30, 0x52,
      0xa3, 0x16, 0xd3, 0x28, 0x32, 0xfa, 0xaa, 0x5e,
      0xcf, 0xea, 0xed, 0x78, 0x33, 0x58, 0x09, 0x7b,
      0x63, 0xc0, 0xc1, 0x46, 0x1e, 0xdf, 0xa9, 0x99,
      0x55, 0x04, 0xc4, 0x86, 0x39, 0x77, 0x82, 0xec,
      0x40, 0x18, 0x90, 0x97, 0x59, 0xdd, 0x83, 0x1f,
      0x9a, 0x37, 0x06, 0x24, 0x64, 0x7c, 0xa5, 0x56,
      0x48, 0x08, 0x85, 0xd0, 0x61, 0x26, 0xca, 0x6f,
      0x7e, 0x6a, 0xb6, 0x71, 0xa0, 0x70, 0x05, 0xd1,
      0x45, 0x8c, 0x23, 0x1c, 0xf0, 0xee, 0x89, 0xad,
      0x7a, 0x4b, 0xc2, 0x2f, 0xdb, 0x5a, 0x4d, 0x76,
      0x67, 0x17, 0x2d, 0xf4, 0xcb, 0xb1, 0x4a, 0xa8,
      0xb5, 0x22, 0x47, 0x3a, 0xd5, 0x10, 0x4c, 0x72,
      0xcc, 0x00, 0xf9, 0xe0, 0xfd, 0xe2, 0xfe, 0xae,
      0xf8, 0x5f, 0xab, 0xf1, 0x1b, 0x42, 0x81, 0xd6,
      0xbe, 0x44, 0x29, 0xa6, 0x57, 0xb9, 0xaf, 0xf2,
      0xd4, 0x75, 0x66, 0xbb, 0x68, 0x9f, 0x50, 0x02,
      0x01, 0x3c, 0x7f, 0x8d, 0x1a, 0x88, 0xbd, 0xac,
      0xf7, 0xe4, 0x79, 0x96, 0xa2, 0xfc, 0x6d, 0xb2,
      0x6b, 0x03, 0xe1, 0x2e, 0x7d, 0x14, 0x95, 0x1d]

m0 = [0x01, 0x02, 0x04, 0x06, 0x02, 0x01, 0x06, 0x04,
      0x04, 0x06, 0x01, 0x02, 0x06, 0x04, 0x02, 0x01]

m1 = [0x01, 0x08, 0x02, 0x0a, 0x08, 0x01, 0x0a, 0x02,
      0x02, 0x0a, 0x01, 0x08, 0x0a, 0x02, 0x08, 0x01]

con128 = [0xf56b7aeb, 0x994a8a42, 0x96a4bd75, 0xfa854521,
          0x735b768a, 0x1f7abac4, 0xd5bc3b45, 0xb99d5d62,
          0x52d73592, 0x3ef636e5, 0xc57a1ac9, 0xa95b9b72,
          0x5ab42554, 0x369555ed, 0x1553ba9a, 0x7972b2a2,
          0xe6b85d4d, 0x8a995951, 0x4b550696, 0x2774b4fc,
          0xc9bb034b, 0xa59a5a7e, 0x88cc81a5, 0xe4ed2d3f,
          0x7c6f68e2, 0x104e8ecb, 0xd2263471, 0xbe07c765,
          0x511a3208, 0x3d3bfbe6, 0x1084b134, 0x7ca565a7,
          0x304bf0aa, 0x5c6aaa87, 0xf4347855, 0x9815d543,
          0x4213141a, 0x2e32f2f5, 0xcd180a0d, 0xa139f97a,
          0x5e852d36, 0x32a464e9, 0xc353169b, 0xaf72b274,
          0x8db88b4d, 0xe199593a, 0x7ed56d96, 0x12f434c9,
          0xd37b36cb, 0xbf5a9a64, 0x85ac9b65, 0xe98d4d32,
          0x7adf6582, 0x16fe3ecd, 0xd17e32c1, 0xbd5f9f66,
          0x50b63150, 0x3c9757e7, 0x1052b098, 0x7c73b3a7]

con192 = [0xc6d61d91, 0xaaf73771, 0x5b6226f8, 0x374383ec,
          0x15b8bb4c, 0x799959a2, 0x32d5f596, 0x5ef43485,
          0xf57b7acb, 0x995a9a42, 0x96acbd65, 0xfa8d4d21,
          0x735f7682, 0x1f7ebec4, 0xd5be3b41, 0xb99f5f62,
          0x52d63590, 0x3ef737e5, 0x1162b2f8, 0x7d4383a6,
          0x30b8f14c, 0x5c995987, 0x2055d096, 0x4c74b497,
          0xfc3b684b, 0x901ada4b, 0x920cb425, 0xfe2ded25,
          0x710f7222, 0x1d2eeec6, 0xd4963911, 0xb8b77763,
          0x524234b8, 0x3e63a3e5, 0x1128b26c, 0x7d09c9a6,
          0x309df106, 0x5cbc7c87, 0xf45f7883, 0x987ebe43,
          0x963ebc41, 0xfa1fdf21, 0x73167610, 0x1f37f7c4,
          0x01829338, 0x6da363b6, 0x38c8e1ac, 0x54e9298f,
          0x246dd8e6, 0x484c8c93, 0xfe276c73, 0x9206c649,
          0x9302b639, 0xff23e324, 0x7188732c, 0x1da969c6,
          0x00cd91a6, 0x6cec2cb7, 0xec7748d3, 0x8056965b,
          0x9a2aa469, 0xf60bcb2d, 0x751c7a04, 0x193dfdc2,
          0x02879532, 0x6ea666b5, 0xed524a99, 0x8173b35a,
          0x4ea00d7c, 0x228141f9, 0x1f59ae8e, 0x7378b8a8,
          0xe3bd5747, 0x8f9c5c54, 0x9dcfaba3, 0xf1ee2e2a,
          0xa2f6d5d1, 0xced71715, 0x697242d8, 0x055393de,
          0x0cb0895c, 0x609151bb, 0x3e51ec9e, 0x5270b089]

con256 = [0x0221947e, 0x6e00c0b5, 0xed014a3f, 0x8120e05a,
          0x9a91a51f, 0xf6b0702d, 0xa159d28f, 0xcd78b816,
          0xbcbde947, 0xd09c5c0b, 0xb24ff4a3, 0xde6eae05,
          0xb536fa51, 0xd917d702, 0x62925518, 0x0eb373d5,
          0x094082bc, 0x6561a1be, 0x3ca9e96e, 0x5088488b,
          0xf24574b7, 0x9e64a445, 0x9533ba5b, 0xf912d222,
          0xa688dd2d, 0xcaa96911, 0x6b4d46a6, 0x076cacdc,
          0xd9b72353, 0xb596566e, 0x80ca91a9, 0xeceb2b37,
          0x786c60e4, 0x144d8dcf, 0x043f9842, 0x681edeb3,
          0xee0e4c21, 0x822fef59, 0x4f0e0e20, 0x232feff8,
          0x1f8eaf20, 0x73af6fa8, 0x37ceffa0, 0x5bef2f80,
          0x23eed7e0, 0x4fcf0f94, 0x29fec3c0, 0x45df1f9e,
          0x2cf6c9d0, 0x40d7179b, 0x2e72ccd8, 0x42539399,
          0x2f30ce5c, 0x4311d198, 0x2f91cf1e, 0x43b07098,
          0xfbd9678f, 0x97f8384c, 0x91fdb3c7, 0xfddc1c26,
          0xa4efd9e3, 0xc8ce0e13, 0xbe66ecf1, 0xd2478709,
          0x673a5e48, 0x0b1bdbd0, 0x0b948714, 0x67b575bc,
          0x3dc3ebba, 0x51e2228a, 0xf2f075dd, 0x9ed11145,
          0x417112de, 0x2d5090f6, 0xcca9096f, 0xa088487b,
          0x8a4584b7, 0xe664a43d, 0xa933c25b, 0xc512d21e,
          0xb888e12d, 0xd4a9690f, 0x644d58a6, 0x086cacd3,
          0xde372c53, 0xb216d669, 0x830a9629, 0xef2beb34,
          0x798c6324, 0x15ad6dce, 0x04cf99a2, 0x68ee2eb3]

def _8To32(x32):
    """Convert a 4-byte list to a 32-bit integer"""
    return (((((x32[0] << 8) + x32[1]) << 8) + x32[2]) << 8) + x32[3]    

def _32To8(x32):
    """Convert a 32-bit integer to a 4-byte list"""
    return [(x32 >> 8 * i) & 0xff for i in reversed(range(4))]

def _32To128(x32):
    """Convert a 32-bit 4-element list to a 128-bit integer"""
    return (((((x32[0] << 32) + x32[1]) << 32) + x32[2]) << 32) + x32[3]

def _128To32(x128):
    """Convert a 128-bit integer to a 32-bit 4-element list"""
    return [(x128 >> 32 * i) & 0xffffffff for i in reversed(range(4))]

def _192To32(x192):
    """Convert a 192-bit integer to a 32-bit 6-element list"""
    return [(x192 >> 32 * i) & 0xffffffff for i in reversed(range(6))]

def _256To32(x256):
    """Convert a 256-bit integer to a 32-bit 8-element list"""
    return [(x256 >> 32 * i) & 0xffffffff for i in reversed(range(8))]

def sigma(x128):
    """The double-swap function sigma (used in key scheduling)"""
    return [(x128[0] << 7) & 0xffffff80  | (x128[1] >> 25),
            (x128[1] << 7) & 0xffffff80  | (x128[3] & 0x7f),
            (x128[0] & 0xfe000000)       | (x128[2] >> 7),
            (x128[2] << 25) & 0xfe000000 | (x128[3] >> 7)]

def memoize(f):
    """Memoization function"""
    memo = {}
    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper

def mult(p1, p2):
    """Multiply two polynomials in GF(2^8)
       (the irreducible polynomial used in this
       field is x^8 + x^4 + x^3 + x^2 + 1)"""
    p = 0
    while p2:
        if p2 & 0b1:
            p ^= p1
        p1 <<= 1
        if p1 & 0x100:
            p1 ^= 0b11101
        p2 >>= 1
    return p & 0xff

# Auxiliary one-parameter functions defined for memoization
# (to speed up multiplication in GF(2^8))

@memoize    
def x2(y):
    """Multiply by 2 in GF(2^8)"""
    return mult(2, y)

@memoize
def x4(y):
    """Multiply by 4 in GF(2^8)"""    
    return mult(4, y)

@memoize
def x6(y):
    """Multiply by 6 in GF(2^8)"""        
    return mult(6, y)

@memoize
def x8(y):
    """Multiply by 8 in GF(2^8)"""    
    return mult(8, y)

@memoize
def x10(y):
    """Multiply by 10 in GF(2^8)"""    
    return mult(10, y)

def multm0(t32):
    """Multiply the matrix m0 by a 4-element transposed vector in GF(2^8)"""
    return [   t32[0]  ^ x2(t32[1]) ^ x4(t32[2]) ^ x6(t32[3]),
            x2(t32[0]) ^    t32[1]  ^ x6(t32[2]) ^ x4(t32[3]),
            x4(t32[0]) ^ x6(t32[1]) ^    t32[2]  ^ x2(t32[3]),
            x6(t32[0]) ^ x4(t32[1]) ^ x2(t32[2]) ^    t32[3]]    
    
def multm1(t32):
    """Multiply the matrix m1 by a 4-element transposed vector in GF(2^8)"""
    return [    t32[0]  ^  x8(t32[1]) ^  x2(t32[2]) ^ x10(t32[3]),
             x8(t32[0]) ^     t32[1]  ^ x10(t32[2]) ^  x2(t32[3]),
             x2(t32[0]) ^ x10(t32[1]) ^     t32[2]  ^  x8(t32[3]),
            x10(t32[0]) ^ x2(t32[1])  ^  x8(t32[2]) ^     t32[3]]      

def f0(rk, x32):
    """F0 function"""
    t8 = _32To8(rk ^ x32)
    t8 = [s0[t8[0]], s1[t8[1]], s0[t8[2]], s1[t8[3]]]
    return _8To32(multm0(t8))

def f1(rk, x32):
    """F1 function"""
    t8 = _32To8(rk ^ x32)
    t8 = s1[t8[0]], s0[t8[1]], s1[t8[2]], s0[t8[3]]
    return _8To32(multm1(t8))

def gfn4(x32, n):
    """4-branch Generalized Feistel Network function"""
    t32 = x32[:]
    for i in range(0, n << 1, 2):
        t32[1] ^= f0(rk[i], t32[0])
        t32[3] ^= f1(rk[i + 1], t32[2])
        t32 = t32[1:] + t32[:1]
    return t32[3:] + t32[:3]

def gfn4i(x32, n):
    """4-branch Generalized Feistel Network inverse function"""
    t32 = x32[:]
    for i in reversed(range(0, n << 1, 2)):
        t32[1] ^= f0(rk[i], t32[0])
        t32[3] ^= f1(rk[i + 1], t32[2])
        t32 = t32[3:] + t32[:3]
    return t32[1:] + t32[:1]

def gfn8(x32, n):
    """8-branch Generalized Feistel Network function"""
    t32 = x32[:]
    for i in range(0, n << 2, 4):
        t32[1] ^= f0(rk[i], t32[0])
        t32[3] ^= f1(rk[i + 1], t32[2])
        t32[5] ^= f0(rk[i + 2], t32[4])
        t32[7] ^= f1(rk[i + 3], t32[6])     
        t32 = t32[1:] + t32[:1]
    return t32[7:] + t32[:7]

def setKey128(k128):
    """Generate round/whitening keys from a 128-bit key"""
    k32 = _128To32(k128)
    for i in range(len(con128) - nrk):
        rk[i] = con128[i]
    l = gfn4(k32, 12)
    for i in range(nwk):
        wk[i] = k32[i]
    for i in range(0, nrk, 4):
        t32 = [r ^ s for r, s in zip(l, con128[i + 24:i + 28])]
        l = sigma(l)
        if i & 0b100:
            rk[i:i + 4] = [r ^ s for r, s in zip(t32, k32)]
        else:
            rk[i:i + 4] = t32

def setKey192(k192):
    """Generate round/whitening keys from a 192-bit key"""
    k32 = _192To32(k192)
    kl = k32[:4]
    kr = k32[4:6] + [k32[0] ^ 0xffffffff] + [k32[1] ^ 0xffffffff]
    for i in range(len(con192) - nrk):
        rk[i] = con192[i]        
    l = gfn8(kl + kr, 10)
    ll, lr = l[:4], l[4:]
    kk = [r ^ s for r, s in zip(kl, kr)]
    for i in range(nwk):
        wk[i] = kk[i]
    for i in range(0, nrk, 4):
        if i & 0b1100 < 8:
            t32 = [r ^ s for r, s in zip(ll, con192[i + 40:i + 44])]
            ll = sigma(ll)
            if i & 0b100:
                t32 = [r ^ s for r, s in zip(t32, kr)]
        else:
            t32 = [r ^ s for r, s in zip(lr, con192[i + 40:i + 44])]
            lr = sigma(lr)
            if i & 0b100:
                t32 = [r ^ s for r, s in zip(t32, kl)]            
        rk[i:i + 4] = t32     

def setKey256(k256):
    """Generate round/whitening keys from a 256-bit key"""
    k32 = _256To32(k256)
    kl, kr = k32[:4], k32[4:]
    for i in range(len(con256) - nrk):
        rk[i] = con256[i]    
    l = gfn8(kl + kr, 10)
    ll, lr = l[:4], l[4:]
    kk = [r ^ s for r, s in zip(kl, kr)]    
    for i in range(nwk):
        wk[i] = kk[i]
    for i in range(0, nrk, 4):
        if i & 0b1100 < 8:
            t32 = [r ^ s for r, s in zip(ll, con256[i + 40:i + 44])]
            ll = sigma(ll)
            if i & 0b100:
                t32 = [r ^ s for r, s in zip(t32, kr)]
        else:
            t32 = [r ^ s for r, s in zip(lr, con256[i + 40:i + 44])]
            lr = sigma(lr)
            if i & 0b100:
                t32 = [r ^ s for r, s in zip(t32, kl)]                
        rk[i:i + 4] = t32

def setKey(key, keySize):
    """Generate round/whitening keys from the given key"""
    global nr, nrk
    try:
        assert keySize in ksTable
    except AssertionError:
        print("Key size identifier not valid")
        sys.exit("ValueError")
    try:
        assert isinstance(key, int)
    except AssertionError:
        print("Invalid key")
        sys.exit("ValueError")
    try:
        assert key.bit_length() // 8 <= ksTable[keySize]
    except AssertionError:
        print("Key size mismatch")
        sys.exit("ValueError")
    nr = nrTable[keySize]
    nrk = nrkTable[keySize]
    if keySize == "SIZE_128":
        setKey128(key)
    elif keySize == "SIZE_192":
        setKey192(key)
    elif keySize == "SIZE_256":
        setKey256(key)
    else:
        sys.exit("Invalid key size identifier")

def encrypt(ptext):
    """Encrypt a block"""
    t32 = _128To32(ptext)
    t32[1] ^= wk[0]
    t32[3] ^= wk[1]
    t32 = gfn4(t32, nr)
    t32[1] ^= wk[2]
    t32[3] ^= wk[3]
    return _32To128(t32)

def decrypt(ctext):
    """Decrypt a block"""
    t32 = _128To32(ctext)
    t32[1] ^= wk[2]
    t32[3] ^= wk[3]
    t32 = gfn4i(t32, nr)
    t32[1] ^= wk[0]
    t32[3] ^= wk[1]
    return _32To128(t32)

if __name__ == "__main__":

    def checkTestVector(key, keySize, plaintext, ciphertext, nIter = 1000):
        testSuccess = True
        setKey(key, keySize)
        ks = ksTable[keySize] * 8
        ctext = encrypt(plaintext)
        ptext = decrypt(ctext)
        try:
            assert ctext == ciphertext
        except AssertionError:
            print("Error in encryption")
            print("Resulting ciphertext: {:02x}".format(ctext))
            print("Expected ciphertext: {:02x}".format(ciphertext))
            testSuccess = False
        try:
            assert ptext == plaintext
        except AssertionError:
            print("Error in decryption:")
            print("Recovered plaintext: {:02x}".format(ptext))
            print("Expected plaintext: {:02x}".format(plaintext))
            testSuccess = False         
        if not testSuccess:
            return False
        t1 = time()        
        for i in range(nIter):
            setKey(key, keySize)
            ctext = encrypt(plaintext)
        t2 = time()
        avg_elapsed_time = (t2 - t1) * 1000 / nIter        
        print("{:3d}-bit key test ok!".format(ksTable[keySize] * 8))
        print("Average elapsed time for 16-byte block ", end="")
        print("ECB-{0:3d} encryption: {1:0.3f}ms".format(ks, avg_elapsed_time))
        t3 = time()   
        for i in range(nIter):
            setKey(key, keySize)
            ptext = decrypt(ctext)
        t4 = time()
        avg_elapsed_time = (t4 - t3) * 1000 / nIter        
        print("{:3d}-bit key test ok!".format(ksTable[keySize] * 8))
        print("Average elapsed time for 16-byte block ", end="")
        print("ECB-{0:3d} decryption: {1:0.3f}ms".format(ks, avg_elapsed_time))        
        return True

    # The test vectors below are described in document "The 128-bit Blockcipher
    # CLEFIA Algorithm Specification" rev.1, June 1, 2007, Sony Corporation.

    ptext = 0x000102030405060708090a0b0c0d0e0f

    # Test vector for 128-bit key
    key1 = 0xffeeddccbbaa99887766554433221100
    ctext1 = 0xde2bf2fd9b74aacdf1298555459494fd

    # Test vector for 192-bit key
    key2 = 0xffeeddccbbaa99887766554433221100f0e0d0c0b0a09080
    ctext2 = 0xe2482f649f028dc480dda184fde181ad

    # Test vector for 256-bit key
    key3 = 0xffeeddccbbaa99887766554433221100f0e0d0c0b0a090807060504030201000
    ctext3 = 0xa1397814289de80c10da46d1fa48b38a

    try:
        assert checkTestVector(key1, "SIZE_128", ptext, ctext1) and \
               checkTestVector(key2, "SIZE_192", ptext, ctext2) and \
               checkTestVector(key3, "SIZE_256", ptext, ctext3)
    except AssertionError:
        print("At least one test failed")
        sys.exit(1)
    print("All tests passed!")
    sys.exit()

CLEFIA implementation in Python

Posted on by
Reply

As Wikipedia puts it, “CLEFIA is a new block cipher algorithm developed by Sony. Its name is derived from the French word clef, meaning “key”. The block size is 128 bits and the key size can be 128 bit, 192 bit or 256 bit [exactly like NIST’s Advanced Encryption Standard (AES)]. It is intended to be used in DRM systems.”

CLEFIA has just been standardized in ISO/IEC 29192 (Information technology – Security techniques – Lightweight cryptography – Part 2: Block ciphers). The rationale for “lightweight cryptography” is described in the short paper “Lightweight Cryptography for the Internet of Things” (Katagi & Moriai). CLEFIA’s architecture is presented in RFC 6114.

According to Sony, “when implemented in hardware [CLEFIA] achieves the world’s highest hardware gate efficiency. When implemented in software it can realize high speed performance on a wide variety of processors.” My AES Python implementation is, however, an order of magnitude faster than CLEFIA’s (see below) with respect to key setup & single block encryption. I think, though, that there is room for some improvement, as this version of CLEFIA is the very first.

#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: CLEFIA implementation in Python 3
#
# Date: 2012-02-02
#
# License: Attribution-NonCommercial-ShareAlike 3.0 Unported
#          (CC BY-NC-SA 3.0)
#===========================================================
import sys
from time import time

# Key size supported
ksTable = {"SIZE_128": 16,
           "SIZE_192": 24,
           "SIZE_256": 32}

# Number of rounds related to key size
nrTable = {"SIZE_128": 18,
           "SIZE_192": 22,
           "SIZE_256": 26}

# Number of round keys related to key size
nrkTable = {"SIZE_128": 36,
            "SIZE_192": 44,
            "SIZE_256": 52}

# Number of rounds
nr = None

# Number of round keys effectively used
nrk = None

# Number of whitening keys
nwk = 4

# Round keys vector
rk = [None] * 2 * nrTable[max(nrTable)]

# Whitening keys
wk = [None] * 4

# First S-Box
s0 = [0x57, 0x49, 0xd1, 0xc6, 0x2f, 0x33, 0x74, 0xfb,
      0x95, 0x6d, 0x82, 0xea, 0x0e, 0xb0, 0xa8, 0x1c,
      0x28, 0xd0, 0x4b, 0x92, 0x5c, 0xee, 0x85, 0xb1,
      0xc4, 0x0a, 0x76, 0x3d, 0x63, 0xf9, 0x17, 0xaf,
      0xbf, 0xa1, 0x19, 0x65, 0xf7, 0x7a, 0x32, 0x20,
      0x06, 0xce, 0xe4, 0x83, 0x9d, 0x5b, 0x4c, 0xd8,
      0x42, 0x5d, 0x2e, 0xe8, 0xd4, 0x9b, 0x0f, 0x13,
      0x3c, 0x89, 0x67, 0xc0, 0x71, 0xaa, 0xb6, 0xf5,
      0xa4, 0xbe, 0xfd, 0x8c, 0x12, 0x00, 0x97, 0xda,
      0x78, 0xe1, 0xcf, 0x6b, 0x39, 0x43, 0x55, 0x26,
      0x30, 0x98, 0xcc, 0xdd, 0xeb, 0x54, 0xb3, 0x8f,
      0x4e, 0x16, 0xfa, 0x22, 0xa5, 0x77, 0x09, 0x61,
      0xd6, 0x2a, 0x53, 0x37, 0x45, 0xc1, 0x6c, 0xae,
      0xef, 0x70, 0x08, 0x99, 0x8b, 0x1d, 0xf2, 0xb4,
      0xe9, 0xc7, 0x9f, 0x4a, 0x31, 0x25, 0xfe, 0x7c,
      0xd3, 0xa2, 0xbd, 0x56, 0x14, 0x88, 0x60, 0x0b,
      0xcd, 0xe2, 0x34, 0x50, 0x9e, 0xdc, 0x11, 0x05,
      0x2b, 0xb7, 0xa9, 0x48, 0xff, 0x66, 0x8a, 0x73,
      0x03, 0x75, 0x86, 0xf1, 0x6a, 0xa7, 0x40, 0xc2,
      0xb9, 0x2c, 0xdb, 0x1f, 0x58, 0x94, 0x3e, 0xed,
      0xfc, 0x1b, 0xa0, 0x04, 0xb8, 0x8d, 0xe6, 0x59,
      0x62, 0x93, 0x35, 0x7e, 0xca, 0x21, 0xdf, 0x47,
      0x15, 0xf3, 0xba, 0x7f, 0xa6, 0x69, 0xc8, 0x4d,
      0x87, 0x3b, 0x9c, 0x01, 0xe0, 0xde, 0x24, 0x52,
      0x7b, 0x0c, 0x68, 0x1e, 0x80, 0xb2, 0x5a, 0xe7,
      0xad, 0xd5, 0x23, 0xf4, 0x46, 0x3f, 0x91, 0xc9,
      0x6e, 0x84, 0x72, 0xbb, 0x0d, 0x18, 0xd9, 0x96,
      0xf0, 0x5f, 0x41, 0xac, 0x27, 0xc5, 0xe3, 0x3a,
      0x81, 0x6f, 0x07, 0xa3, 0x79, 0xf6, 0x2d, 0x38,
      0x1a, 0x44, 0x5e, 0xb5, 0xd2, 0xec, 0xcb, 0x90,
      0x9a, 0x36, 0xe5, 0x29, 0xc3, 0x4f, 0xab, 0x64,
      0x51, 0xf8, 0x10, 0xd7, 0xbc, 0x02, 0x7d, 0x8e]

# Second S-Box
s1 = [0x6c, 0xda, 0xc3, 0xe9, 0x4e, 0x9d, 0x0a, 0x3d,
      0xb8, 0x36, 0xb4, 0x38, 0x13, 0x34, 0x0c, 0xd9,
      0xbf, 0x74, 0x94, 0x8f, 0xb7, 0x9c, 0xe5, 0xdc,
      0x9e, 0x07, 0x49, 0x4f, 0x98, 0x2c, 0xb0, 0x93,
      0x12, 0xeb, 0xcd, 0xb3, 0x92, 0xe7, 0x41, 0x60,
      0xe3, 0x21, 0x27, 0x3b, 0xe6, 0x19, 0xd2, 0x0e,
      0x91, 0x11, 0xc7, 0x3f, 0x2a, 0x8e, 0xa1, 0xbc,
      0x2b, 0xc8, 0xc5, 0x0f, 0x5b, 0xf3, 0x87, 0x8b,
      0xfb, 0xf5, 0xde, 0x20, 0xc6, 0xa7, 0x84, 0xce,
      0xd8, 0x65, 0x51, 0xc9, 0xa4, 0xef, 0x43, 0x53,
      0x25, 0x5d, 0x9b, 0x31, 0xe8, 0x3e, 0x0d, 0xd7,
      0x80, 0xff, 0x69, 0x8a, 0xba, 0x0b, 0x73, 0x5c,
      0x6e, 0x54, 0x15, 0x62, 0xf6, 0x35, 0x30, 0x52,
      0xa3, 0x16, 0xd3, 0x28, 0x32, 0xfa, 0xaa, 0x5e,
      0xcf, 0xea, 0xed, 0x78, 0x33, 0x58, 0x09, 0x7b,
      0x63, 0xc0, 0xc1, 0x46, 0x1e, 0xdf, 0xa9, 0x99,
      0x55, 0x04, 0xc4, 0x86, 0x39, 0x77, 0x82, 0xec,
      0x40, 0x18, 0x90, 0x97, 0x59, 0xdd, 0x83, 0x1f,
      0x9a, 0x37, 0x06, 0x24, 0x64, 0x7c, 0xa5, 0x56,
      0x48, 0x08, 0x85, 0xd0, 0x61, 0x26, 0xca, 0x6f,
      0x7e, 0x6a, 0xb6, 0x71, 0xa0, 0x70, 0x05, 0xd1,
      0x45, 0x8c, 0x23, 0x1c, 0xf0, 0xee, 0x89, 0xad,
      0x7a, 0x4b, 0xc2, 0x2f, 0xdb, 0x5a, 0x4d, 0x76,
      0x67, 0x17, 0x2d, 0xf4, 0xcb, 0xb1, 0x4a, 0xa8,
      0xb5, 0x22, 0x47, 0x3a, 0xd5, 0x10, 0x4c, 0x72,
      0xcc, 0x00, 0xf9, 0xe0, 0xfd, 0xe2, 0xfe, 0xae,
      0xf8, 0x5f, 0xab, 0xf1, 0x1b, 0x42, 0x81, 0xd6,
      0xbe, 0x44, 0x29, 0xa6, 0x57, 0xb9, 0xaf, 0xf2,
      0xd4, 0x75, 0x66, 0xbb, 0x68, 0x9f, 0x50, 0x02,
      0x01, 0x3c, 0x7f, 0x8d, 0x1a, 0x88, 0xbd, 0xac,
      0xf7, 0xe4, 0x79, 0x96, 0xa2, 0xfc, 0x6d, 0xb2,
      0x6b, 0x03, 0xe1, 0x2e, 0x7d, 0x14, 0x95, 0x1d]

m0 = [0x01, 0x02, 0x04, 0x06, 0x02, 0x01, 0x06, 0x04,
      0x04, 0x06, 0x01, 0x02, 0x06, 0x04, 0x02, 0x01]

m1 = [0x01, 0x08, 0x02, 0x0a, 0x08, 0x01, 0x0a, 0x02,
      0x02, 0x0a, 0x01, 0x08, 0x0a, 0x02, 0x08, 0x01]

con128 = [0xf56b7aeb, 0x994a8a42, 0x96a4bd75, 0xfa854521,
          0x735b768a, 0x1f7abac4, 0xd5bc3b45, 0xb99d5d62,
          0x52d73592, 0x3ef636e5, 0xc57a1ac9, 0xa95b9b72,
          0x5ab42554, 0x369555ed, 0x1553ba9a, 0x7972b2a2,
          0xe6b85d4d, 0x8a995951, 0x4b550696, 0x2774b4fc,
          0xc9bb034b, 0xa59a5a7e, 0x88cc81a5, 0xe4ed2d3f,
          0x7c6f68e2, 0x104e8ecb, 0xd2263471, 0xbe07c765,
          0x511a3208, 0x3d3bfbe6, 0x1084b134, 0x7ca565a7,
          0x304bf0aa, 0x5c6aaa87, 0xf4347855, 0x9815d543,
          0x4213141a, 0x2e32f2f5, 0xcd180a0d, 0xa139f97a,
          0x5e852d36, 0x32a464e9, 0xc353169b, 0xaf72b274,
          0x8db88b4d, 0xe199593a, 0x7ed56d96, 0x12f434c9,
          0xd37b36cb, 0xbf5a9a64, 0x85ac9b65, 0xe98d4d32,
          0x7adf6582, 0x16fe3ecd, 0xd17e32c1, 0xbd5f9f66,
          0x50b63150, 0x3c9757e7, 0x1052b098, 0x7c73b3a7]

con192 = [0xc6d61d91, 0xaaf73771, 0x5b6226f8, 0x374383ec,
          0x15b8bb4c, 0x799959a2, 0x32d5f596, 0x5ef43485,
          0xf57b7acb, 0x995a9a42, 0x96acbd65, 0xfa8d4d21,
          0x735f7682, 0x1f7ebec4, 0xd5be3b41, 0xb99f5f62,
          0x52d63590, 0x3ef737e5, 0x1162b2f8, 0x7d4383a6,
          0x30b8f14c, 0x5c995987, 0x2055d096, 0x4c74b497,
          0xfc3b684b, 0x901ada4b, 0x920cb425, 0xfe2ded25,
          0x710f7222, 0x1d2eeec6, 0xd4963911, 0xb8b77763,
          0x524234b8, 0x3e63a3e5, 0x1128b26c, 0x7d09c9a6,
          0x309df106, 0x5cbc7c87, 0xf45f7883, 0x987ebe43,
          0x963ebc41, 0xfa1fdf21, 0x73167610, 0x1f37f7c4,
          0x01829338, 0x6da363b6, 0x38c8e1ac, 0x54e9298f,
          0x246dd8e6, 0x484c8c93, 0xfe276c73, 0x9206c649,
          0x9302b639, 0xff23e324, 0x7188732c, 0x1da969c6,
          0x00cd91a6, 0x6cec2cb7, 0xec7748d3, 0x8056965b,
          0x9a2aa469, 0xf60bcb2d, 0x751c7a04, 0x193dfdc2,
          0x02879532, 0x6ea666b5, 0xed524a99, 0x8173b35a,
          0x4ea00d7c, 0x228141f9, 0x1f59ae8e, 0x7378b8a8,
          0xe3bd5747, 0x8f9c5c54, 0x9dcfaba3, 0xf1ee2e2a,
          0xa2f6d5d1, 0xced71715, 0x697242d8, 0x055393de,
          0x0cb0895c, 0x609151bb, 0x3e51ec9e, 0x5270b089]

con256 = [0x0221947e, 0x6e00c0b5, 0xed014a3f, 0x8120e05a,
          0x9a91a51f, 0xf6b0702d, 0xa159d28f, 0xcd78b816,
          0xbcbde947, 0xd09c5c0b, 0xb24ff4a3, 0xde6eae05,
          0xb536fa51, 0xd917d702, 0x62925518, 0x0eb373d5,
          0x094082bc, 0x6561a1be, 0x3ca9e96e, 0x5088488b,
          0xf24574b7, 0x9e64a445, 0x9533ba5b, 0xf912d222,
          0xa688dd2d, 0xcaa96911, 0x6b4d46a6, 0x076cacdc,
          0xd9b72353, 0xb596566e, 0x80ca91a9, 0xeceb2b37,
          0x786c60e4, 0x144d8dcf, 0x043f9842, 0x681edeb3,
          0xee0e4c21, 0x822fef59, 0x4f0e0e20, 0x232feff8,
          0x1f8eaf20, 0x73af6fa8, 0x37ceffa0, 0x5bef2f80,
          0x23eed7e0, 0x4fcf0f94, 0x29fec3c0, 0x45df1f9e,
          0x2cf6c9d0, 0x40d7179b, 0x2e72ccd8, 0x42539399,
          0x2f30ce5c, 0x4311d198, 0x2f91cf1e, 0x43b07098,
          0xfbd9678f, 0x97f8384c, 0x91fdb3c7, 0xfddc1c26,
          0xa4efd9e3, 0xc8ce0e13, 0xbe66ecf1, 0xd2478709,
          0x673a5e48, 0x0b1bdbd0, 0x0b948714, 0x67b575bc,
          0x3dc3ebba, 0x51e2228a, 0xf2f075dd, 0x9ed11145,
          0x417112de, 0x2d5090f6, 0xcca9096f, 0xa088487b,
          0x8a4584b7, 0xe664a43d, 0xa933c25b, 0xc512d21e,
          0xb888e12d, 0xd4a9690f, 0x644d58a6, 0x086cacd3,
          0xde372c53, 0xb216d669, 0x830a9629, 0xef2beb34,
          0x798c6324, 0x15ad6dce, 0x04cf99a2, 0x68ee2eb3]

def _8To32(x32):
    return ((x32[0] * 256 + x32[1]) * 256 + x32[2]) * 256 + x32[3]    

def _32To8(x32):
    return [(x32 >> 8 * i) & 0xff for i in reversed(range(4))]

def _32To128(x32):
    return ((x32[0] * 256 ** 4 + x32[1]) * 256 ** 4 + x32[2]) * 256 ** 4 + x32[3]

def _128To32(x128):
    return [(x128 >> 32 * i) & 0xffffffff for i in reversed(range(4))]

def _192To32(x192):
    return [(x192 >> 32 * i) & 0xffffffff for i in reversed(range(6))]

def _256To32(x256):
    return [(x256 >> 32 * i) & 0xffffffff for i in reversed(range(8))]

def sigma(x128):
    return [(x128[0] << 7) & 0xffffff80  | (x128[1] >> 25),
            (x128[1] << 7) & 0xffffff80  | (x128[3] & 0x7f),
            (x128[0] & 0xfe000000)       | (x128[2] >> 7),
            (x128[2] << 25) & 0xfe000000 | (x128[3] >> 7)]

def mMult(m, t):
    """Multiply a 4x4 matrix by a transposed 1x4 vector in GF(2^8)"""

    def mult(p1, p2):
        """Multiply two polynomials in GF(2^8)"""
        p = 0
        while p2:
            if p2 & 1: p ^= p1
            p1 <<= 1
            if p1 & 256: p1 ^= 0x1d
            p2 >>= 1
        return p & 255    

    s = [0] * 4
    for i in range(4):
        for j in range(4):
            s[i] ^= mult(m[4 * i + j], t[j])
    return s

def f0(rk, x32):
    """F0 function"""
    t8 = _32To8(rk ^ x32)
    return _8To32(mMult(m0, [s0[t8[0]], s1[t8[1]], s0[t8[2]], s1[t8[3]]]))

def f1(rk, x32):
    """F1 function"""
    t8 = _32To8(rk ^ x32)
    return _8To32(mMult(m1, [s1[t8[0]], s0[t8[1]], s1[t8[2]], s0[t8[3]]]))

def gfn4(x32, n):
    """4-branch Generalized Feistel Network function"""
    t32 = x32[:]
    for i in range(n):
        t32[1] ^= f0(rk[2 * i], t32[0])
        t32[3] ^= f1(rk[2 * i + 1], t32[2])
        t32 = t32[1:] + t32[:1]
    return t32[3:] + t32[:3]

def gfn4i(x32, n):
    """4-branch Generalized Feistel Network inverse function"""
    t32 = x32[:]
    for i in reversed(range(n)):
        t32[1] ^= f0(rk[2 * i], t32[0])
        t32[3] ^= f1(rk[2 * i + 1], t32[2])
        t32 = t32[3:] + t32[:3]
    return t32[1:] + t32[:1]

def gfn8(x32, n):
    """8-branch Generalized Feistel Network function"""
    t32 = x32[:]
    for i in range(n):
        t32[1] ^= f0(rk[4 * i], t32[0])
        t32[3] ^= f1(rk[4 * i + 1], t32[2])
        t32[5] ^= f0(rk[4 * i + 2], t32[4])
        t32[7] ^= f1(rk[4 * i + 3], t32[6])     
        t32 = t32[1:] + t32[:1]
    return t32[7:] + t32[:7]

def setKey128(k128):
    """Generate round/whitening keys from 128-bit key"""
    k32 = _128To32(k128)
    for i in range(len(con128) - nrk):
        rk[i] = con128[i]
    l = gfn4(k32, 12)
    for i in range(nwk):
        wk[i] = k32[i]
    for i in range(nrk // 4):
        t32 = [r ^ s for r, s in zip(l, con128[4 * i + 24: 4 * i + 28])]
        l = sigma(l)
        if i % 2:
            t32 = [r ^ s for r, s in zip(t32, k32)]
        rk[4 * i:4 * i + 4] = t32

def setKey192(k192):
    """Generate round/whitening keys from 192-bit key"""
    k32 = _192To32(k192)
    kl = k32[:4]
    kr = k32[4:6] + [k32[0] ^ 0xffffffff] + [k32[1] ^ 0xffffffff]
    for i in range(len(con192) - nrk):
        rk[i] = con192[i]        
    l = gfn8(kl + kr, 10)
    ll, lr = l[:4], l[4:]
    kk = [r ^ s for r, s in zip(kl, kr)]
    for i in range(nwk):
        wk[i] = kk[i]
    for i in range(nrk // 4):
        if i % 4 == 0 or i % 4 == 1:
            t32 = [r ^ s for r, s in zip(ll, con192[4 * i + 40: 4 * i + 44])]
            ll = sigma(ll)
            if i % 2:
                t32 = [r ^ s for r, s in zip(t32, kr)]
        else:
            t32 = [r ^ s for r, s in zip(lr, con192[4 * i + 40: 4 * i + 44])]
            lr = sigma(lr)
            if i % 2:
                t32 = [r ^ s for r, s in zip(t32, kl)]                
        rk[4 * i:4 * i + 4] = t32     

def setKey256(k256):
    """Generate round/whitening keys from 256-bit key"""
    k32 = _256To32(k256)
    kl = k32[:4]
    kr = k32[4:]
    for i in range(len(con256) - nrk):
        rk[i] = con256[i]    
    l = gfn8(kl + kr, 10)
    ll, lr = l[:4], l[4:]
    kk = [r ^ s for r, s in zip(kl, kr)]    
    for i in range(nwk):
        wk[i] = kk[i]
    for i in range(nrk // 4):
        if i % 4 == 0 or i % 4 == 1:
            t32 = [r ^ s for r, s in zip(ll, con256[4 * i + 40: 4 * i + 44])]
            ll = sigma(ll)
            if i % 2:
                t32 = [r ^ s for r, s in zip(t32, kr)]
        else:
            t32 = [r ^ s for r, s in zip(lr, con256[4 * i + 40: 4 * i + 44])]
            lr = sigma(lr)
            if i % 2:
                t32 = [r ^ s for r, s in zip(t32, kl)]                
        rk[4 * i:4 * i + 4] = t32

def setKey(key, keySize):
    """Generate round/whitening keys"""
    global nr, nrk
    try:
        assert keySize in ksTable
    except AssertionError:
        print("Key size identifier not valid")
        sys.exit("ValueError")
    try:
        assert isinstance(key, int)
    except AssertionError:
        print("Invalid key")
        sys.exit("ValueError")
    try:
        assert key.bit_length() // 8 <= ksTable[keySize]
    except AssertionError:
        print("Key size mismatch")
        sys.exit("ValueError")
    nr = nrTable[keySize]
    nrk = nrkTable[keySize]
    if keySize == "SIZE_128":
        setKey128(key)
    elif keySize == "SIZE_192":
        setKey192(key)
    elif keySize == "SIZE_256":
        setKey256(key)
    else:
        sys.exit("Invalid key size identifier")

def enc(ptext):
    t32 = _128To32(ptext)
    t32[1] ^= wk[0]
    t32[3] ^= wk[1]
    t32 = gfn4(t32, nr)
    t32[1] ^= wk[2]
    t32[3] ^= wk[3]
    return _32To128(t32)

def dec(ctext):
    t32 = _128To32(ctext)
    t32[1] ^= wk[2]
    t32[3] ^= wk[3]
    t32 = gfn4i(t32, nr)
    t32[1] ^= wk[0]
    t32[3] ^= wk[1]
    return _32To128(t32)

if __name__ == "__main__":
    
    def checkTestVector(key, keySize, plaintext, ciphertext, nIter = 1000):
        testSuccess = True
        setKey(key, keySize)
        ks = ksTable[keySize] * 8
        try:
            assert  enc(plaintext) == ciphertext
        except AssertionError:
            print("Error in encryption")
            print("Resulted ciphertext: {:s}".format(ctext))
            print("Expected ciphertext: {:s}".format(ciphertext))
            testSuccess = False
        try:
            assert dec(enc(plaintext)) == plaintext
        except AssertionError:
            print("Error in decryption:")
            print("Recovered plaintext: {:s}".format(ptext))
            print("Expected plaintext: {:s}".format(plaintext))
            testSuccess = False         
        if not testSuccess:
            return False
        t1 = time()        
        for i in range(nIter):
            setKey(key, keySize)
            ctext = enc(plaintext)
        t2 = time()
        avg_elapsed_time = (t2 - t1) * 1000 / nIter        
        print("{:3d}-bit key test ok!".format(ksTable[keySize] * 8))
        print("Average elapsed time for 16-byte block ", end="")
        print("ECB-{0:3d} encryption: {1:0.3f}ms".format(ks, avg_elapsed_time))
        t3 = time()   
        for i in range(nIter):
            setKey(key, keySize)
            ptext = dec(ctext)
        t4 = time()
        avg_elapsed_time = (t4 - t3) * 1000 / nIter        
        print("{:3d}-bit key test ok!".format(ksTable[keySize] * 8))
        print("Average elapsed time for 16-byte block ", end="")
        print("ECB-{0:3d} decryption: {1:0.3f}ms".format(ks, avg_elapsed_time))        
        return True
    
    # The test vectors below are described in document "The 128-bit Blockcipher
    # CLEFIA Algorithm Specification" rev.1, June 1, 2007, Sony Corporation.

    ptext = 0x000102030405060708090a0b0c0d0e0f
    
    # Test vector for 128-bit key
    key1 = 0xffeeddccbbaa99887766554433221100
    ctext1 = 0xde2bf2fd9b74aacdf1298555459494fd
    
    # Test vector for 192-bit key
    key2 = 0xffeeddccbbaa99887766554433221100f0e0d0c0b0a09080
    ctext2 = 0xe2482f649f028dc480dda184fde181ad
    
    # Test vector for 256-bit key
    key3 = 0xffeeddccbbaa99887766554433221100f0e0d0c0b0a090807060504030201000
    ctext3 = 0xa1397814289de80c10da46d1fa48b38a
    
    try:
        assert checkTestVector(key1, "SIZE_128", ptext, ctext1) and \
               checkTestVector(key2, "SIZE_192", ptext, ctext2) and \
               checkTestVector(key3, "SIZE_256", ptext, ctext3)
    except AssertionError:
        print("At least one test failed")
        sys.exit(1)
    print("All tests passed!")
    sys.exit()