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

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

RSA implementation in Python

This Python script below implements the basic RSA encryption and decryption operations without any concern about padding or character encoding. Nevertheless, it has all the primitive machinery needed to encrypt and decrypt messages using the RSA public-key algorithm. The getprime() function is in charge of generating primes of the required size and, for this purpose, uses a probabilistic algorithm, the Miller-Rabin primality test. The inv() function, which calculates modular multiplicative inverses, gets a helping hand from the Extended Euclidean algorithm xgcd() function. The genRSA() function is pretty straightforward: it generates the standard public-key small exponent, 3 or 65537 (hex 10001), depending on the size of modulus (a small public exponent speeds up both the encryption and signature verification operations).

#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: RSA implementation in Python 3
#
# Date: 2012-01-30
#
# License: Attribution-NonCommercial-ShareAlike 3.0 Unported
#          (CC BY-NC-SA 3.0)
#===========================================================
from random import randrange, getrandbits
from itertools import repeat
from functools import reduce

def getPrime(n):
    """Get a n-bit pseudo-random prime"""
    def isProbablePrime(n, t = 7):
        """Miller-Rabin primality test"""
        def isComposite(a):
            """Check if n is composite"""
            if pow(a, d, n) == 1:
                return False
            for i in range(s):
                if pow(a, 2 ** i * d, n) == n - 1:
                    return False
            return True
    
        assert n > 0
        if n < 3:
            return [False, False, True][n]
        elif not n & 1:
            return False
        else:
            s, d = 0, n - 1
            while not d & 1:
                s += 1
                d >>= 1
        for _ in repeat(None, t):
            if isComposite(randrange(2, n)):
                return False
        return True    
    
    p = getrandbits(n)
    while not isProbablePrime(p):
        p = getrandbits(n)
    return p

def inv(p, q):
    """Multiplicative inverse"""
    def xgcd(x, y):
        """Extended Euclidean Algorithm"""
        s1, s0 = 0, 1
        t1, t0 = 1, 0
        while y:
            q = x // y
            x, y = y, x % y
            s1, s0 = s0 - q * s1, s1
            t1, t0 = t0 - q * t1, t1
        return x, s0, t0      

    s, t = xgcd(p, q)[0:2]
    assert s == 1
    if t < 0:
        t += q
    return t

def genRSA(p, q):
    """Generate public and private keys"""
    phi, mod = (p - 1) * (q - 1), p * q
    if mod < 65537:
        return (3, inv(3, phi), mod)
    else:
        return (65537, inv(65537, phi), mod)    

def text2Int(text):
    """Convert a text string into an integer"""
    return reduce(lambda x, y : (x << 8) + y, map(ord, text))

def int2Text(number, size):
    """Convert an integer into a text string"""
    text = "".join([chr((number >> j) & 0xff)
                    for j in reversed(range(0, size << 3, 8))])
    return text.lstrip("\x00")

def int2List(number, size):
    """Convert an integer into a list of small integers"""
    return [(number >> j) & 0xff
            for j in reversed(range(0, size << 3, 8))]

def list2Int(listInt):
    """Convert a list of small integers into an integer"""
    return reduce(lambda x, y : (x << 8) + y, listInt)

def modSize(mod):
    """Return length (in bytes) of modulus"""
    modSize = len("{:02x}".format(mod)) // 2
    return modSize

def encrypt(ptext, pk, mod):
    """Encrypt message with public key"""
    size = modSize(mod)
    output = []
    while ptext:
        nbytes = min(len(ptext), size - 1)
        aux1 = text2Int(ptext[:nbytes])
        assert aux1 < mod
        aux2 = pow(aux1, pk, mod)
        output += int2List(aux2, size + 2)
        ptext = ptext[size:]
    return output

def decrypt(ctext, sk, p, q):
    """Decrypt message with private key
    using the Chinese Remainder Theorem"""
    mod = p * q
    size = modSize(mod)
    output = ""
    while ctext:
        aux3 = list2Int(ctext[:size + 2])
        assert aux3 < mod
        m1 = pow(aux3, sk % (p - 1), p)
        m2 = pow(aux3, sk % (q - 1), q)
        h = (inv(q, p) * (m1 - m2)) % p
        aux4 = m2 + h * q
        output += int2Text(aux4, size)
        ctext = ctext[size + 2:]
    return output

if __name__ == "__main__":

    from math import log10
    from time import time

    def printHexList(intList):
        """Print ciphertext in hex"""
        for index, elem in enumerate(intList):
            if index % 32 == 0:
                print()            
            print("{:02x}".format(elem), end = "")
        print()

    def printLargeInteger(number):
        """Print long primes in a formatted way"""
        string = "{:02x}".format(number)
        for j in range(len(string)):
            if j % 64 == 0:
                print()
            print(string[j], end = "")
        print()

    def testCase(p, q, msg, nTimes = 1):
        """Execute test case: generate keys, encrypt message and
           decrypt resulting ciphertext"""
        print("Key size: {:0d} bits".format(round(log10(p * q) / log10(2))))
        print("Prime #1:", end = "")
        printLargeInteger(p)
        print("Prime #2:", end = "")
        printLargeInteger(q)
        print("Plaintext:", msg)
        pk, sk, mod = genRSA(p, q)
        ctext = encrypt(msg, pk, mod)
        print("Ciphertext:", end = "")
        printHexList(ctext)
        ptext = decrypt(ctext, sk, p, q)
        print("Recovered plaintext:", ptext, "\n")

    # First test: RSA-129 (see http://en.wikipedia.org/wiki/RSA_numbers#RSA-129)
    p1 = 3490529510847650949147849619903898133417764638493387843990820577
    p2 = 32769132993266709549961988190834461413177642967992942539798288533
    testCase(p1, p2, "The Magic Words are Squeamish Ossifrage", 1000)
  
    # Second test: random primes (key size: 512 to 4096 bits)
    for n in [256, 512, 1024, 2048]:    
        t1 = time()
        p5 = getPrime(n)
        t2 = time()
        print("Elapsed time for {:0d}-bit prime ".format(n), end = "")
        print("generation: {:0.3f} s".format(round(t2 - t1, 3)))
        t3 = time()
        p6 = getPrime(n)
        t4 = time()
        print("Elapsed time for {:0d}-bit prime ".format(n), end = "")
        print("generation: {:0.3f} s".format(round(t4 - t3, 3)))
        testCase(p5, p6, "It's all greek to me")

The first test uses the famous 425-bit key pair belonging to RSA-129, a challenge published in Martin Gardner’s column in Scientific American back in 1977. RSA-129 owes its name to the 129-digit number that expresses the product of two (unknown at the time) primes.

RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429 35706935245733897830597123563958705058989075147599290026879543541

This challenge, posed by the inventors of the RSA algorithm (Rivest, Shamir & Adleman), was solved only in 1994. The decrypted plaintext was the phrase “The Magic Words are Squeamish Ossifrage”. The second test was done with pairs of randomly generated primes. Their key sizes (as a matter of fact, the size of the modulus) are 512, 1024 and 2048 bits (the key size most used in SSL certificates is 1024 bits). The output of this Python script is shown below.

Key size: 425 bits
Prime #1:
87c296ed480f9ab17885decd31197d617779c0dac70c3234996e1
Prime #2:
4fa84812157119acc8ecca98c404b2e5ee24ce18f60ea818091895
Plaintext: The Magic Words are Squeamish Ossifrage
Ciphertext:
000100d00ec048028f8de9998bfcdb271ad5d34ab70a3990ebdfdd30a32ae15e
1ae01ccda1945493cc02be7d739ded0c56d8cd9c996ee8
Recovered plaintext: The Magic Words are Squeamish Ossifrage 

Elapsed time for 256-bit prime generation: 0.108 s
Elapsed time for 256-bit prime generation: 0.018 s
Key size: 511 bits
Prime #1:
7a29e838f6afe351c24b0dfee0b12d32e092c6ec129382b75b224f749e9785c9
Prime #2:
caffe728fa460b4f009a7647bdbb0763868206942a4ced79aefd36a6b05f539b
Plaintext: It's all greek to me
Ciphertext:
00005741fdf3f6f20fc16524c9a1c80f62e7a293aaff5238f319692e4c469443
10d2272ed76d6a9a884372c2eae03e2d3b8c10df04353d459659a3f8c3e63be3
2c6d
Recovered plaintext: It's all greek to me 

Elapsed time for 512-bit prime generation: 0.162 s
Elapsed time for 512-bit prime generation: 0.576 s
Key size: 1015 bits
Prime #1:
37f8ab0bbdeca6af2a8a8874844472add93745cb98a6224175c6528c1e3c2f26
5ef0fcba9c6044ecd3c98aa22981e1f75f8779ba5f72fa33ab4da89d4abfc357
Prime #2:
2aabce36a668c2f8e161521238d2be8541d286e612b6572e4c1531f8218dfe0e
08de2e177b02c2ab1a76056eca13920e2847bfdffffdb6b2b9fe874849c3637
Plaintext: It's all greek to me
Ciphertext:
00006d1c01974161e2c4710ec423076bbab8107cf31d2d2ecfd6127ca6dc142e
aa7f37d93281222684227892c82575ef93491ffa802003efac9085e3e8076000
63780dd7ea03b1418e7cdb17dec38b533913d2e11f37de1f364dd96e559add5b
a205c367ed6d7270e1ab02da80522264238e3cb93aff81e53eeec7910d5013c8
a4
Recovered plaintext: It's all greek to me 

Elapsed time for 1024-bit prime generation: 7.189 s
Elapsed time for 1024-bit prime generation: 8.921 s
Key size: 2047 bits
Prime #1:
7843d991e4fa29466f4e0fa385f0b8612db5d51c0f09f0fca801339155cd1ca2
fde3b810569de371e99e8d1e3d127a9b4d7f07944d64c7d9da973252b73dd1ed
847183c1a855b65817411cfea22c05b58764d5bb016770feef93d6cb5e6274e3
fce2c5fb251bb41a8ba879cd5a2d6755c591e921c6aa08327ef6b6e8f1cf1a1b
Prime #2:
e751af1ed509106fdd814d52778da0cf6998b768bafd16a10ec91c4becf05856
9e96007661d4525cb0b40b20247aa879657c4550d3d58a74ab23666b504febaf
5de5b40f3cc7b8c766e5d426fa37d9832b91fef718e4f117984168a2eeb087bc
8ad09364d9f57c6534d5332eb78eacf9f5cdaa12f95aee44de0d1df475ec52ff
Plaintext: It's all greek to me
Ciphertext:
000056ce1bab323cc03876dc786cdc9f53e406a4e321a2e8233ed648f93d0026
3b9504faa72bfbf2d97b166f320344596bb2634addd2766ef9e4816841a76b95
ba3c5b899bd559222162d5580924ef073ba7118023710cebc901a20f51603acb
5a797e84ea7cf853d3b2031f3263879d3afb3d05bd74f15219b877753b3182ef
a93cdfc015db601b8fd93540e1e50d1b9676e152769268039484cdd821f9291b
93f408d1e8c851fb79b143a80d7ef03629f3c11c81f8188a35076df9a88df1ba
5da77de10857a9c7238122f3818c4011a6cbe4e702c8b481789edca59ab74606
3608ca5c98f6126ddec1a3eb972021b9297c7d4d2c38f50f8105745eb3110977
f76a
Recovered plaintext: It's all greek to me

I will comment on code details in another post.

AES implementation in Python

After implementing DES, the next obvious challenge was AES. I was expecting AES code to be simpler to write than DES’ because AES was designed to be implemented in hardware or software, while DES design was geared towards hardware. This time, however, I decided to write an object-oriented API supporting the three different key sizes AES inherited from Rijndael (128-, 192- and 256-bit). In addition, besides the ECB (Electronic Code Book) basic operation mode, this implementation also supports CBC (Cipher Block Chaining) mode.

#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: AES implementation in Python 3
# (sundAES)
#
# Date: 2013-06-02 (version 1.1)
#       2012-01-16 (version 1.0)
#
# License: Attribution-NonCommercial-ShareAlike 3.0 Unported
# (CC BY-NC-SA 3.0)
#===========================================================
import sys
from itertools import repeat
from functools import reduce
from copy import copy

__all__ = ["setKey","encrypt","decrypt"]

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

def mult(p1,p2):
"""Multiply two polynomials in GF(2^8)/x^8+x^4+x^3+x+1"""
p = 0
while p2:
if p2&0x01:
p ^= p1
p1 <<= 1
if p1&0x100:
p1 ^= 0x1b
p2 >>= 1
return p&0xff

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

@memoize
def x2(y):
"""Multiplication by 2"""
return mult(2,y)

@memoize
def x3(y):
"""Multiplication by 3"""
return mult(3,y)

@memoize
def x9(y):
"""Multiplication by 9"""
return mult(9,y)

@memoize
def x11(y):
"""Multiplication by 11"""
return mult(11,y)

@memoize
def x13(y):
"""Multiplication by 13"""
return mult(13,y)

@memoize
def x14(y):
"""Multiplication by 14"""
return mult(14,y)

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

# Instance variables
wordSize = None
w = [None]*60 # Round subkeys list
keyDefined = None # Key definition flag
numberOfRounds = None
cipherMode = None
padding = None # Padding scheme
ivEncrypt = None # Initialization
ivDecrypt = None # vectors

def __init__(self,mode,padding = "NoPadding"):
"""Create a new instance of an AES object"""
try:
assert mode in AES.cipherModeTable
except AssertionError:
print("Cipher mode not supported:",mode)
sys.exit("ValueError")
self.cipherMode = mode
try:
assert padding in AES.paddingTable
except AssertionError:
print("Padding scheme not supported:",padding)
sys.exit(ValueError)
self.padding = padding
self.keyDefined = False

def intToList(self,number):
"""Convert an 16-byte number into a 16-element list"""
return [(number>>i)&0xff for i in reversed(range(0,128,8))]

def intToList2(self,number):
"""Converts an integer into one (or more) 16-element list"""
lst = []
while number:
lst.append(number&0xff)
number >>= 8
m = len(lst)%16
if m == 0 and len(lst) != 0:
return lst[::-1]
else:
return list(bytes(16-m)) + lst[::-1]

def listToInt(self,lst):
"""Convert a list into a number"""
return reduce(lambda x,y:(x<<8)+y,lst)

def wordToState(self,wordList):
"""Convert list of 4 words into a 16-element state list"""
return [(wordList[i]>>j)&0xff
for j in reversed(range(0,32,8)) for i in range(4)]

def listToState(self,list):
"""Convert a 16-element list into a 16-element state list"""
return [list[i+j] for j in range(4) for i in range(0,16,4)]

stateToList = listToState # this function is an involution

def subBytes(self,state):
"""SubBytes transformation"""
return [AES.sBox[e] for e in state]

def invSubBytes(self,state):
"""Inverse SubBytes transformation"""
return [AES.invSBox[e] for e in state]

def shiftRows(self,s):
"""ShiftRows transformation"""
return s[:4]+s[5:8]+s[4:5]+s[10:12]+s[8:10]+s[15:]+s[12:15]

def invShiftRows(self,s):
"""Inverse ShiftRows transformation"""
return s[:4]+s[7:8]+s[4:7]+s[10:12]+s[8:10]+s[13:]+s[12:13]

def mixColumns(self,s):
"""MixColumns transformation"""
return [x2(s[i])^x3(s[i+4])^ s[i+8] ^ s[i+12] for i in range(4)]+ \
[ s[i] ^x2(s[i+4])^x3(s[i+8])^ s[i+12] for i in range(4)]+ \
[ s[i] ^ s[i+4] ^x2(s[i+8])^x3(s[i+12]) for i in range(4)]+ \
[x3(s[i])^ s[i+4] ^ s[i+8] ^x2(s[i+12]) for i in range(4)]

def invMixColumns(self,s):
"""Inverse MixColumns transformation"""
return [x14(s[i])^x11(s[i+4])^x13(s[i+8])^ x9(s[i+12]) for i in range(4)]+ \
[ x9(s[i])^x14(s[i+4])^x11(s[i+8])^x13(s[i+12]) for i in range(4)]+ \
[x13(s[i])^ x9(s[i+4])^x14(s[i+8])^x11(s[i+12]) for i in range(4)]+ \
[x11(s[i])^x13(s[i+4])^ x9(s[i+8])^x14(s[i+12]) for i in range(4)]

def addRoundKey (self,subkey,state):
"""AddRoundKey transformation"""
return [i^j for i,j in zip(subkey,state)]

xorLists = addRoundKey

def rotWord(self,number):
"""Rotate subkey left"""
return (((number&0xff000000)>>24) +
((number&0xff0000)<<8) +
((number&0xff00)<<8) +
((number&0xff)<<8))

def subWord(self,key):
"""Substitute subkeys bytes using S-box"""
return ((AES.sBox[(key>>24)&0xff]<<24) +
(AES.sBox[(key>>16)&0xff]<<16) +
(AES.sBox[(key>>8)&0xff]<<8) +
AES.sBox[key&0xff])

def setKey(self,keySize,key,iv = None):
"""KeyExpansion transformation"""
rcon = (0x00,0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80,0x1B,0x36)
try:
assert keySize in AES.keySizeTable
except AssertionError:
print("Key size identifier not valid")
sys.exit("ValueError")
try:
assert isinstance(key,int)
except AssertionError:
print("Invalid key")
sys.exit("ValueError")
klen = len("{:02x}".format(key))//2
try:
assert klen <= AES.keySizeTable[keySize]
except AssertionError:
print("Key size mismatch")
sys.exit("ValueError")
try:
assert ((self.cipherMode == "MODE_CBC" and isinstance(iv,int)) or
self.cipherMode == "MODE_ECB")
except AssertionError:
print("IV is mandatory for CBC mode")
sys.exit(ValueError)

if self.cipherMode == "MODE_CBC":
temp = self.intToList(iv)
self.ivEncrypt = copy(temp)
self.ivDecrypt = copy(temp)
nr = AES.numberOfRoundsTable[keySize]
self.numberOfRounds = nr
self.wordSize = AES.wordSizeTable[keySize]
if nr == 10:
nk = 4
keyList = self.intToList(key)
elif nr == 12:
nk = 6
keyList = self.intToList(key>>64) + \
(self.intToList(key&int("ff"*32,16)))[8:]
else:
nk = 8
keyList = self.intToList(key>>128) + \
self.intToList(key&int("ff"*64,16))
for index in range(nk):
self.w[index] = (keyList[4*index]<<24) + \
(keyList[4*index+1]<<16) + \
(keyList[4*index+2]<<8) +\
keyList[4*index+3]
for index in range(nk,self.wordSize):
temp = self.w[index - 1]
if index % nk == 0:
temp = (self.subWord(self.rotWord(temp)) ^
rcon[index//nk]<<24)
elif self.numberOfRounds == 14 and index%nk == 4:
temp = self.subWord(temp)
self.w[index] = self.w[index-nk]^temp
self.keyDefined = True
return

def getKey(self,operation):
"""Return next round subkey for encryption or decryption"""
if operation == "encryption":
for i in range(0,self.wordSize,4):
yield self.wordToState(self.w[i:i+4])
else: # operation = "decryption":
for i in reversed(range(0,self.wordSize,4)):
yield self.wordToState(self.w[i:i+4])

def encryptBlock(self,plaintextBlock):
"""Encrypt a 16-byte block with key already defined"""
key = self.getKey("encryption")
state = self.listToState(plaintextBlock)
state = self.addRoundKey(next(key),state)
for _ in repeat(None,self.numberOfRounds - 1):
state = self.subBytes(state)
state = self.shiftRows(state)
state = self.mixColumns(state)
state = self.addRoundKey(next(key),state)
state = self.subBytes(state)
state = self.shiftRows(state)
state = self.addRoundKey(next(key),state)
return self.stateToList(state)

def decryptBlock(self,ciphertextBlock):
"""Decrypt a 16-byte block with key already defined"""
key = self.getKey("decryption")
state = self.listToState(ciphertextBlock)
state = self.addRoundKey(next(key),state)
for _ in repeat(None,self.numberOfRounds - 1):
state = self.invShiftRows(state)
state = self.invSubBytes(state)
state = self.addRoundKey(next(key),state)
state = self.invMixColumns(state)
state = self.invShiftRows(state)
state = self.invSubBytes(state)
state = self.addRoundKey(next(key),state)
return self.stateToList(state)

def padData(self,data):
"""Add PKCS7 padding to plaintext (or just add bytes to fill a block)"""
paddingLength = 16-(len(data)%16)
if self.padding == "NoPadding":
paddingLength %= 16
if type(data) is bytes:
return data+bytes(list([paddingLength]*paddingLength))
else:
return [ord(s) for s in data]+[paddingLength]*paddingLength

def unpadData(self,byteList):
"""Remove PKCS7 padding (if present) from plaintext"""
if self.padding == "PKCS7Padding":
return "".join(chr(e) for e in byteList[:-byteList[-1]])
else:
return "".join(chr(e) for e in byteList)

def encrypt(self,input):
"""Encrypt plaintext passed as a string or as an integer"""
try:
assert self.keyDefined
except AssertionError:
print("Key not defined")
sys.exit("ValueError")

if type(input) is int:
inList = self.intToList2(input)
else:
inList = self.padData(input)
outList = []
if self.cipherMode == "MODE_CBC":
outBlock = self.ivEncrypt
for i in range(0,len(inList),16):
auxList = self.xorLists(outBlock,inList[i:i+16])
outBlock = self.encryptBlock(auxList)
outList += outBlock
self.ivEncrypt = outBlock
else:
for i in range(0,len(inList),16):
outList += self.encryptBlock(inList[i:i+16])
if type(input) is int:
return self.listToInt(outList)
else:
return outList

def decrypt(self,input):
"""Decrypt ciphertext passed as a string or as an integer"""
try:
assert self.keyDefined
except AssertionError:
print("Key not defined")
sys.exit("ValueError")
if type(input) is int:
inList = self.intToList2(input)
else:
inList = input
outList = []
if self.cipherMode == "MODE_CBC":
oldInBlock = self.ivDecrypt
for i in range(0,len(inList),16):
newInBlock = inList[i:i+16]
auxList = self.decryptBlock(newInBlock)
outList += self.xorLists(oldInBlock,auxList)
oldInBlock = newInBlock
self.ivDecrypt = oldInBlock
else:
for i in range(0,len(inList),16):
outList += self.decryptBlock(inList[i:i+16])
if type(input) is int:
return self.listToInt(outList)
else:
return self.unpadData(outList)

The code below informally verify the correctness of the implementation with the help of the test vectors described in NIST document SP800-38A, Recommendation for Block Cipher Modes of Operation – Methods and Techniques:

import pyAES

def intToList(number):
    """Convert a 16-byte number into a 16-element list"""
    return [(number >> 120) & 0xff, (number >> 112) & 0xff,
            (number >> 104) & 0xff, (number >> 96)  & 0xff,
            (number >> 88)  & 0xff, (number >> 80)  & 0xff,
            (number >> 72)  & 0xff, (number >> 64)  & 0xff,
            (number >> 56)  & 0xff, (number >> 48)  & 0xff,
            (number >> 40)  & 0xff, (number >> 32)  & 0xff,
            (number >> 24)  & 0xff, (number >> 16)  & 0xff,
            (number >> 8)   & 0xff,  number & 0xff]

def intToText(hexNumber):
    """Convert a 16-byte number into a 16 char text string"""
    return "".join(chr(e) for e in intToList(hexNumber))

def checkTestVector1(mode, keySize, key, plaintext, ciphertext, iv = None):
    """Check test vectors for single block encryption and decryption"""
    success = True
    obj = pyAES.AES(mode)
    obj.setKey(keySize, key, iv)
    for i, (p, c) in enumerate(zip(plaintext, ciphertext)):
        p_text = intToText(p)
        c_text = intToList(c)
        code = "{0:3s}-{1:3s}".format(mode[5:], keySize[5:])
        try:
            assert obj.encrypt(p_text) == c_text
        except AssertionError:
            print(code, "encryption #{:d} failed".format(i))
            success = False
        try:
            assert obj.decrypt(c_text) == p_text
        except AssertionError:
            print(code, "decryption #{:d} failed".format(i))
            success = False
    if success:
        print(code, "encryption/decryption ok")
    return success

def checkTestVector2(mode, keySize, plaintext, key1, key2, iv1 = None, iv2 = None):
    obj1 = pyAES.AES(mode, "PKCS5Padding")
    obj1.setKey(keySize, key1, iv1)
    obj2 = pyAES.AES(mode, "PKCS5Padding")
    obj2.setKey(keySize, key2, iv2)
    ciphertext1 = obj1.encrypt(plaintext)
    ciphertext2 = obj2.encrypt(plaintext)
    plaintext1 = obj1.decrypt(ciphertext1)
    plaintext2 = obj2.decrypt(ciphertext2)
    code = "{0:3s}-{1:3s}".format(mode[5:], keySize[5:])
    try:
        assert plaintext1 == plaintext and plaintext2 == plaintext
    except AssertionError:
        print("Multi-block", code, "encryption/decryption failed")
        return False
    print("Multi-block", code, "encryption/decryption ok")
    return True

#===========================================================================

# Test vectors from NIST SP800-38A sections F.1.1 and F.1.2
def ECB_128_NOPAD():
    key = 0x2b7e151628aed2a6abf7158809cf4f3c
    plaintext =  [0x6bc1bee22e409f96e93d7e117393172a,
                  0xae2d8a571e03ac9c9eb76fac45af8e51,
                  0x30c81c46a35ce411e5fbc1191a0a52ef,
                  0xf69f2445df4f9b17ad2b417be66c3710]
    ciphertext = [0x3ad77bb40d7a3660a89ecaf32466ef97,
                  0xf5d3d58503b9699de785895a96fdbaaf,
                  0x43b1cd7f598ece23881b00e3ed030688,
                  0x7b0c785e27e8ad3f8223207104725dd4]
    return checkTestVector1("MODE_ECB", "SIZE_128", key, plaintext, ciphertext)

# Test vectors from NIST SP800-38A sections F.1.3 and F.1.4
def ECB_192_NOPAD():
    key = 0x8e73b0f7da0e6452c810f32b809079e562f8ead2522c6b7b
    plaintext =  [0x6bc1bee22e409f96e93d7e117393172a,
                  0xae2d8a571e03ac9c9eb76fac45af8e51,
                  0x30c81c46a35ce411e5fbc1191a0a52ef,
                  0xf69f2445df4f9b17ad2b417be66c3710]
    ciphertext = [0xbd334f1d6e45f25ff712a214571fa5cc,
                  0x974104846d0ad3ad7734ecb3ecee4eef,
                  0xef7afd2270e2e60adce0ba2face6444e,
                  0x9a4b41ba738d6c72fb16691603c18e0e]
    return checkTestVector1("MODE_ECB", "SIZE_192", key, plaintext, ciphertext)

# Test vectors from NIST SP800-38A sections F.1.5 and F.1.6
def ECB_256_NOPAD():
    key = 0x603deb1015ca71be2b73aef0857d77811f352c073b6108d72d9810a30914dff4
    plaintext =  [0x6bc1bee22e409f96e93d7e117393172a,
                  0xae2d8a571e03ac9c9eb76fac45af8e51,
                  0x30c81c46a35ce411e5fbc1191a0a52ef,
                  0xf69f2445df4f9b17ad2b417be66c3710]
    ciphertext = [0xf3eed1bdb5d2a03c064b5a7e3db181f8,
                  0x591ccb10d410ed26dc5ba74a31362870,
                  0xb6ed21b99ca6f4f9f153e7b1beafed1d,
                  0x23304b7a39f9f3ff067d8d8f9e24ecc7]
    return checkTestVector1("MODE_ECB", "SIZE_256", key, plaintext, ciphertext)

# Test vectors from NIST SP800-38A sections F.2.1 and F.2.2
def CBC_128_NOPAD():
    key = 0x2b7e151628aed2a6abf7158809cf4f3c
    iv = 0x000102030405060708090a0b0c0d0e0f
    plaintext =  [0x6bc1bee22e409f96e93d7e117393172a,
                   0xae2d8a571e03ac9c9eb76fac45af8e51,
                   0x30c81c46a35ce411e5fbc1191a0a52ef,
                   0xf69f2445df4f9b17ad2b417be66c3710]
    ciphertext = [0x7649abac8119b246cee98e9b12e9197d,
                  0x5086cb9b507219ee95db113a917678b2,
                  0x73bed6b8e3c1743b7116e69e22229516,
                  0x3ff1caa1681fac09120eca307586e1a7]
    return checkTestVector1("MODE_CBC", "SIZE_128", key, plaintext, ciphertext, iv)

# Test vectors from NIST SP800-38A sections F.2.3 and F.2.4
def CBC_192_NOPAD():
    key = 0x8e73b0f7da0e6452c810f32b809079e562f8ead2522c6b7b
    iv = 0x000102030405060708090a0b0c0d0e0f
    plaintext =  [0x6bc1bee22e409f96e93d7e117393172a,
                  0xae2d8a571e03ac9c9eb76fac45af8e51,
                  0x30c81c46a35ce411e5fbc1191a0a52ef,
                  0xf69f2445df4f9b17ad2b417be66c3710]
    ciphertext = [0x4f021db243bc633d7178183a9fa071e8,
                  0xb4d9ada9ad7dedf4e5e738763f69145a,
                  0x571b242012fb7ae07fa9baac3df102e0,
                  0x08b0e27988598881d920a9e64f5615cd]
    return checkTestVector1("MODE_CBC", "SIZE_192", key, plaintext, ciphertext, iv)

# Test vectors from NIST SP800-38A sections F.2.5 and F.2.6
def CBC_256_NOPAD():
    key = 0x603deb1015ca71be2b73aef0857d77811f352c073b6108d72d9810a30914dff4
    iv = 0x000102030405060708090a0b0c0d0e0f
    plaintext=  [0x6bc1bee22e409f96e93d7e117393172a,
                 0xae2d8a571e03ac9c9eb76fac45af8e51,
                 0x30c81c46a35ce411e5fbc1191a0a52ef,
                 0xf69f2445df4f9b17ad2b417be66c3710]
    ciphertext = [0xf58c4c04d6e5f1ba779eabfb5f7bfbd6,
                  0x9cfc4e967edb808d679f777bc6702c7d,
                  0x39f23369a9d9bacfa530e26304231461,
                  0xb2eb05e2c39be9fcda6c19078c6a9d1b]
    return checkTestVector1("MODE_CBC", "SIZE_256", key, plaintext, ciphertext, iv)

#===========================================================================

# Two multi-block encryptions in ECB mode with 128-bit key
def ECB_128_PKCS5():
    plaintext = "The quick brown fox jumps over the lazy dog"
    key1 = 0x000102030405060708090a0b0c0d0e0f
    key2 = 0xffeeddccbbaa99887766554433221100
    return checkTestVector2("MODE_ECB", "SIZE_128", plaintext, key1, key2)

# Two multi-block encryptions in ECB mode with 192-bit key
def ECB_192_PKCS5():
    plaintext = "The quick brown fox jumps over the lazy dog"
    key1 = 0x000102030405060708090a0b0c0d0e0f1011121314151617
    key2 = 0x1716151413121110ffeeddccbbaa99887766554433221100
    return checkTestVector2("MODE_ECB", "SIZE_192", plaintext, key1, key2)

# Two multi-block encryptions in ECB mode with 256-bit key
def ECB_256_PKCS5():
    plaintext = "The quick brown fox jumps over the lazy dog"
    key1 = 0x000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f
    key2 = 0x1f1e1d1c1b1a19181716151413121110ffeeddccbbaa99887766554433221100
    return checkTestVector2("MODE_ECB", "SIZE_256", plaintext, key1, key2)

# Two multi-block encryptions in CBC mode with 128-bit key
def CBC_128_PKCS5():
    plaintext = "The quick brown fox jumps over the lazy dog"
    key1 = 0x000102030405060708090a0b0c0d0e0f
    key2 = 0xffeeddccbbaa99887766554433221100
    iv1 = 0x0123cdef456789ab0123cdef456789ab
    iv2 = 0xab0123cdef456789ab0123cdef456789
    return checkTestVector2("MODE_CBC", "SIZE_128", plaintext, key1, key2, iv1, iv2)

# Two multi-block encryptions in CBC mode with 192-bit key
def CBC_192_PKCS5():
    plaintext = "The quick brown fox jumps over the lazy dog"
    key1 = 0x000102030405060708090a0b0c0d0e0f1011121314151617
    key2 = 0x1716151413121110ffeeddccbbaa99887766554433221100
    iv1 = 0x0123cdef456789ab0123cdef456789ab
    iv2 = 0xab0123cdef456789ab0123cdef456789
    return checkTestVector2("MODE_CBC", "SIZE_192", plaintext, key1, key2, iv1, iv2)

# Two multi-block encryptions in CBC mode with 256-bit key
def CBC_256_PKCS5():
    plaintext = "The quick brown fox jumps over the lazy dog"
    key1 = 0x000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f
    key2 = 0x1f1e1d1c1b1a19181716151413121110ffeeddccbbaa99887766554433221100
    iv1 = 0x0123cdef456789ab0123cdef456789ab
    iv2 = 0xab0123cdef456789ab0123cdef456789
    return checkTestVector2("MODE_CBC", "SIZE_256", plaintext, key1, key2, iv1, iv2)

def main():
    # Perform vector tests
    testSuccess = True
    for pad in ["NOPAD", "PKCS5"]:
        for mode in ["ECB", "CBC"]:
            for size in ["128", "192", "256"]:
                testVector = mode + "_" + size + "_" + pad + "()"
                testSuccess = testSuccess & eval(testVector)
    if testSuccess:
        print("All tests passed!")

if __name__ == '__main__':
    main()

DES implementation in Python

After coding RC4, I thought it was time to face a more difficult challenge: DES (Data Encryption Standard). Although it has been replaced by AES (Advanced Encryption Standard) more than a decade ago, it still has some appeal to me because it was the first symmetric algorithm I learned (and also because its creation, 40 years ago, was surrounded by mystery). Before fighting the monster, I faced a lighter opponent, S-DES (Simplified DES), to get used to the awkward bit manipulation DES take advantage of. Since S-DES is just a toy cryptographic algorithm, it isn’t worthwhile to spend much time and space writing about it. For this reason, without further ado, this is the DES Python code I wrote:

#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: DES implementation in Python 3
#
# Note: only single DES in ECB mode (with PKCS5 padding)
#       is supported
#
# License: Attribution-NonCommercial-ShareAlike 3.0 Unported
#          (CC BY-NC-SA 3.0)
#===========================================================

subKeyList = 16*[[None]*8]

IPtable = (58, 50, 42, 34, 26, 18, 10, 2,
           60, 52, 44, 36, 28, 20, 12, 4,
           62, 54, 46, 38, 30, 22, 14, 6,
           64, 56, 48, 40, 32, 24, 16, 8,
           57, 49, 41, 33, 25, 17,  9, 1,
           59, 51, 43, 35, 27, 19, 11, 3,
           61, 53, 45, 37, 29, 21, 13, 5,
           63, 55, 47, 39, 31, 23, 15, 7)

EPtable = (32,  1,  2,  3,  4,  5,
            4,  5,  6,  7,  8,  9,
            8,  9, 10, 11, 12, 13,
           12, 13, 14, 15, 16, 17,
           16, 17, 18, 19, 20, 21,
           20, 21, 22, 23, 24, 25,
           24, 25, 26, 27, 28, 29,
           28, 29, 30, 31, 32,  1)

PFtable = (16,  7, 20, 21, 29, 12, 28, 17,
            1, 15, 23, 26,  5, 18, 31, 10,
            2,  8, 24, 14, 32, 27,  3,  9,
           19, 13, 30,  6, 22, 11,  4, 25)

FPtable = (40, 8, 48, 16, 56, 24, 64, 32,
           39, 7, 47, 15, 55, 23, 63, 31,
           38, 6, 46, 14, 54, 22, 62, 30,
           37, 5, 45, 13, 53, 21, 61, 29,
           36, 4, 44, 12, 52, 20, 60, 28,
           35, 3, 43, 11, 51, 19, 59, 27,
           34, 2, 42, 10, 50, 18, 58, 26,
           33, 1, 41,  9, 49, 17, 57, 25)

sBox = 8*[64*[0]]

sBox[0] = (14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7,
            0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8,
            4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0,
           15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13)

sBox[1] = (15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10,
            3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5,
            0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15,
           13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9)

sBox[2] = (10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8,
           13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1,
           13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7,
            1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12)

sBox[3] = ( 7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15,
           13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9,
           10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4,
            3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14)

sBox[4] = ( 2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9,
           14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6,
            4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14,
           11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3)

sBox[5] = (12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11,
           10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8,
            9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6,
            4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13)

sBox[6] = ( 4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1,
           13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6,
            1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2,
            6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12)

sBox[7] = (13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7,
            1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2,
            7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8,
            2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11)

def bit2Byte(bitList):
    """Convert bit list into a byte list"""
    return [int("".join(map(str,bitList[i*8:i*8+8])),2) for i in range(len(bitList)//8)]

def byte2Bit(byteList):
    """Convert byte list into a bit list"""
    return [(byteList[i//8]>>(7-(i%8)))&0x01 for i in range(8*len(byteList))]

def permBitList(inputBitList,permTable):
    """Permute input bit list according to input permutation table"""
    return [inputBitList[e - 1] for e in permTable]

def permByteList(inByteList,permTable):
    """Permute input byte list according to input permutation table"""
    outByteList = (len(permTable)>>3)*[0]
    for index,elem in enumerate(permTable):
        i = index%8
        e = (elem-1)%8
        if i>=e:
            outByteList[index>>3] |= \
                (inByteList[(elem-1)>>3]&(128>>e))>>(i-e)
        else:
            outByteList[index>>3] |= \
                (inByteList[(elem-1)>>3]&(128>>e))<<(e-i)
    return outByteList

def getIndex(inBitList):
    """Permute bits to properly index the S-boxes"""
    return (inBitList[0]<<5)+(inBitList[1]<<3)+ \
           (inBitList[2]<<2)+(inBitList[3]<<1)+ \
           (inBitList[4]<<0)+(inBitList[5]<<4)

def padData(string):
    """Add PKCS5 padding to plaintext"""
    padLength = 8-(len(string)%8)
    return [ord(s) for s in string]+padLength*[padLength]

def unpadData(byteList):
    """Remove PKCS5 padding from plaintext"""
    return "".join(chr(e) for e in byteList[:-byteList[-1]])

def setKey(keyByteList):
    """Generate all sixteen round subkeys"""
    PC1table = (57, 49, 41, 33, 25, 17,  9,
                 1, 58, 50, 42, 34, 26, 18,
                10,  2, 59, 51, 43, 35, 27,
                19, 11,  3, 60, 52, 44, 36,
                63, 55, 47, 39, 31, 23, 15,
                 7, 62, 54, 46, 38, 30, 22,
                14,  6, 61, 53, 45, 37, 29,
                21, 13,  5, 28, 20, 12,  4)

    PC2table= (14, 17, 11, 24,  1,  5,  3, 28,
               15,  6, 21, 10, 23, 19, 12,  4,
               26,  8, 16,  7, 27, 20, 13,  2,
               41, 52, 31, 37, 47, 55, 30, 40,
               51, 45, 33, 48, 44, 49, 39, 56,
               34, 53, 46, 42, 50, 36, 29, 32)

    def leftShift(inKeyBitList,round):
        """Perform one (or two) circular left shift(s) on key"""
        LStable = (1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1)

        outKeyBitList = 56*[0]
        if LStable[round] == 2:
            outKeyBitList[:26] = inKeyBitList[2:28]
            outKeyBitList[26] = inKeyBitList[0]
            outKeyBitList[27] = inKeyBitList[1]
            outKeyBitList[28:54] = inKeyBitList[30:]
            outKeyBitList[54] = inKeyBitList[28]
            outKeyBitList[55] = inKeyBitList[29]
        else:
            outKeyBitList[:27] = inKeyBitList[1:28]
            outKeyBitList[27] = inKeyBitList[0]
            outKeyBitList[28:55] = inKeyBitList[29:]
            outKeyBitList[55] = inKeyBitList[28]
        return outKeyBitList

    permKeyBitList = permBitList(byte2Bit(keyByteList),PC1table)
    for round in range(16):
        auxBitList = leftShift(permKeyBitList,round)
        subKeyList[round] = bit2Byte(permBitList(auxBitList,PC2table))
        permKeyBitList = auxBitList

def encryptBlock(inputBlock):
    """Encrypt an 8-byte block with already defined key"""
    inputData = permByteList(inputBlock,IPtable)
    leftPart,rightPart = inputData[:4],inputData[4:]
    for round in range(16):
        expRightPart = permByteList(rightPart,EPtable)
        key = subKeyList[round]
        indexList = byte2Bit([i^j for i,j in zip(key,expRightPart)])
        sBoxOutput = 4*[0]
        for nBox in range(4):
            nBox12 = 12*nBox
            leftIndex = getIndex(indexList[nBox12:nBox12+6])
            rightIndex = getIndex(indexList[nBox12+6:nBox12+12])
            sBoxOutput[nBox] = (sBox[nBox<<1][leftIndex]<<4)+ \
                                sBox[(nBox<<1)+1][rightIndex]
        aux = permByteList(sBoxOutput,PFtable)
        newRightPart = [i^j for i,j in zip(aux,leftPart)]
        leftPart = rightPart
        rightPart = newRightPart
    return permByteList(rightPart+leftPart,FPtable)

def decryptBlock(inputBlock):
    """Decrypt an 8-byte block with already defined key"""
    inputData = permByteList(inputBlock,IPtable)
    leftPart,rightPart = inputData[:4],inputData[4:]
    for round in range(16):
        expRightPart = permByteList(rightPart,EPtable)
        key = subKeyList[15-round]
        indexList = byte2Bit([i^j for i,j in zip(key,expRightPart)])
        sBoxOutput = 4*[0]
        for nBox in range(4):
            nBox12 = 12*nBox
            leftIndex = getIndex(indexList[nBox12:nBox12+6])
            rightIndex = getIndex(indexList[nBox12+6:nBox12+12])
            sBoxOutput[nBox] = (sBox[nBox*2][leftIndex]<<4)+ \
                                sBox[nBox*2+1][rightIndex]
        aux = permByteList(sBoxOutput,PFtable)
        newRightPart = [i^j for i,j in zip(aux,leftPart)]
        leftPart = rightPart
        rightPart = newRightPart
    return permByteList(rightPart+leftPart,FPtable)

def encrypt(key, inString):
    """Encrypt plaintext with given key"""
    setKey(key)
    inByteList,outByteList = padData(inString),[]
    for i in range(0,len(inByteList),8):
        outByteList += encryptBlock(inByteList[i:i+8])
    return outByteList

def decrypt(key, inByteList):
    """Decrypt ciphertext with given key"""
    setKey(key)
    outByteList = []
    for i in range(0,len(inByteList),8):
        outByteList += decryptBlock(inByteList[i:i+8])
    return unpadData(outByteList)

To verify this DES implementation, I also wrote a separate Python module (shown below) containing an interesting algorithm proposed by Ron Rivest a long time ago (1985) in the paper Testing Implementation of DES. I also added a simple multi-block test.

import sys
from pyDES import setKey, encryptBlock, decryptBlock, encrypt, decrypt

def sanityCheck1():
    """Tests single-block DES encryption & decryption
       using algorithm proposed by Ronald Rivest
       (http://people.csail.mit.edu/rivest/Destest.txt)"""
    x0 =  [0x94, 0x74, 0xb8, 0xe8, 0xc7, 0x3b, 0xca, 0x7d]
    x16 = [0x1b, 0x1a, 0x2d, 0xdb, 0x4c, 0x64, 0x24, 0x38]
    x = x0
    for i in range(16):
        setKey(x)
        if i % 2 == 0:
            x = encryptBlock(x) # if i is even, x[i+1] = E(x[i], x[i)
        else:
            x = decryptBlock(x) # if i is odd, x[i+1] = D(x[i], x[i)
    try:
        assert x == x16
    except AssertionError:
        return False
    return True

def sanityCheck2():
    """Tests multi-block DES encryption and decryption"""
    try:
        key = [0x0f, 0x15, 0x71, 0xc9, 0x47, 0xd9, 0xe8, 0x59]
        plaintext = "The quick brown fox jumps over the lazy dog"
        ciphertext = encrypt(key, plaintext)
        assert decrypt(key, ciphertext) == plaintext
    except AssertionError:
        return False
    return True

def main():
    if sanityCheck1() and sanityCheck2():
        print("All DES tests ok!")
    else:
        sys.exit(1)
    sys.exit()

if __name__ == '__main__':
    main()

RC4 implementation in Python

I started learning Python two months ago. To get the most out of the process, I decided to combine it with another interest of mine, cryptography, by trying to implement a very simple symmetric algorithm, RC4. Here is the code:

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

# Global variables
state = [None] * 256
p = q = None

def setKey(key):
    """RC4 Key Scheduling Algorithm (KSA)"""
    global p, q, state
    state = [n for n in range(256)]
    p = q = j = 0
    for i in range(256):
        if len(key) > 0:
            j = (j + state[i] + key[i % len(key)]) % 256
        else:
            j = (j + state[i]) % 256
        state[i], state[j] = state[j], state[i]

def byteGenerator():
    """RC4 Pseudo-Random Generation Algorithm (PRGA)"""
    global p, q, state
    p = (p + 1) % 256
    q = (q + state[p]) % 256
    state[p], state[q] = state[q], state[p]
    return state[(state[p] + state[q]) % 256]

def encrypt(inputString):
    """Encrypt input string returning a byte list"""
    return [ord(p) ^ byteGenerator() for p in inputString]

def decrypt(inputByteList):
    """Decrypt input byte list returning a string"""
    return "".join([chr(c ^ byteGenerator()) for c in inputByteList])

To informally verify the correctness of this implementation, I wrote a separate Python module that uses Wikipedia’s RC4 test vectors for this purpose:

import sys
import pyRC4

def main():
    """Verify the correctness of RC4 implementation using Wikipedia
       test vectors"""

    def intToList(inputNumber):
        """Convert a number into a byte list"""
        inputString = "{:02x}".format(inputNumber)
        return [int(inputString[i:i + 2], 16) for i in range(0, len(inputString), 2)]

    def string_to_list(inputString):
        """Convert a string into a byte list"""
        return [ord(c) for c in inputString]

    def test(key, plaintext, ciphertext, testNumber):
        success = True
        pyRC4.setKey(string_to_list(key))
        try:
            assert pyRC4.encrypt(plaintext) == intToList(ciphertext)
            print("RC4 encryption test #{:d} ok!".format(testNumber))
        except AssertionError:
            print("RC4 encryption test #{:d} failed".format(testNumber))
            success = False
        pyRC4.setKey(string_to_list(key))
        try:
            assert pyRC4.decrypt(intToList(ciphertext)) == plaintext
            print("RC4 decryption test #{:d} ok!".format(testNumber))
        except AssertionError:
            print("RC4 decryption test #{:d} failed".format(testNumber))
            success = False
        return success

    # Test vectors definition section
    numberOfTests = 3
    testVectorList = [{}] * numberOfTests

    # Wikipedia test vector #1
    testVectorList[0] = dict(key = "Key",
                             plaintext = "Plaintext",
                             ciphertext = 0xBBF316E8D940AF0AD3,
                             testNumber = 1)

    # Wikipedia test vector #2
    testVectorList[1] = dict(key = "Wiki",
                             plaintext = "pedia",
                             ciphertext = 0x1021BF0420,
                             testNumber = 2)

    # Wikipedia test vector #3
    testVectorList[2] = dict(key = "Secret",
                             plaintext = "Attack at dawn",
                             ciphertext = 0x45A01F645FC35B383552544B9BF5,
                             testNumber = 3)

    # Testing section
    testSuccess = True
    for p in range(numberOfTests):
        testSuccess &= test(**testVectorList[p])
    if testSuccess:
        print("All RC4 tests succeeded!")
    else:
        print("At least one RC4 test failed")
        sys.exit(1)
    sys.exit()

if __name__ == '__main__':
    main()