Simplified DES implementation in Python

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

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)

“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

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)

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

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()

Math poetry: prime numbers and Nemo

“How many computing operations have been performed by all machines across all of world history?” … To put it roughly, right around the turn of the century (2000 AD), about one mole — that is, the Avogadro number 6 \times 10^{23} of chemistry, call it 10^{24} — is the total operation count for all machines for all of history. In spite of the usual mystery and awe that surrounds the notion of industrial and government super-computing, it is the huge collection of personal computers that allows this 10^{24}, this mole. The relevance is that a task such as trial dividing an integer N \simeq 10^{50} directly for prime factors is hopeless in the sense that one would essentially have to replicate the machine effort of all time. To convey an idea of scale, a typical instance of the deepest factoring or primality-proving runs of the modern era involves perhaps 10^{16} to 10^{18} machine operations. Similarly, a full-length graphically rendered synthetic movie of today—for example, the 2003 Pixar/Disney movie Finding Nemo—involves operation counts in the 10^{18} range. It is amusing that for this kind of Herculean machine effort one may either obtain a single answer (a factor, maybe even a single “prime/composite” decision bit) or create a full-length animated feature whose character is as culturally separate from a one-bit answer as can be. It is interesting that a computational task of say 10^{18} operations is about one ten-millionth of the overall historical computing effort by all Earth-bound machinery.

[excerpt from Crandall & Pomerance, “Prime Numbers – A Computational Perspective”, 2nd edition, Springer (2005), p. 5]