About JHAF

Infosec consultant, jazz music fan, amateur chess player... (not necessarily in this order)

The Traveling Rook

Posted on July 11, 2017 by JHAF

Rook paths

A rook is placed in the corner of a standard (8 x 8) chessboard. Every minute, it makes a legal move, where each move has the same probability of being chosen. What is the expected number of minutes for the rook to reach the opposite corner?

This puzzle was proposed at the HMMT November 2015 competition (Theme round, problem #8). HMMT is the Harvard-MIT Mathematics Tournament, one of the largest and most prestigious high school competitions in the world. Each event gathers close to 1,000 students from around the globe, including top scorers at both U.S. and international math olympiads.

The minimum number of moves (and minutes) for the rook, being at one corner, to get to the opposite one is just 2 (two); the probability that this happens is 1/7 * 1/14 + 1/7 * 1/14 = 1/49 (almost 2%). On the other hand, the set (or more exactly, the tree) of possible “journeys” for the rook, which account for the remaining 98%, is infinite; each journey takes more (or much more) than two minutes. What would be the expected number of minutes for the rook to get to its final destination: ten, twenty, fifty? One hundred maybe?

Simulation

One obvious solution is to simulate a “reasonable” number (say 1 million times) of random rook journeys, each one starting at the same corner square and ending on the opposite one. The C program below took roughly 1.3 seconds on my PC to print the average journey duration: 70.022925 minutes.

#include <time.h>
#include <stdlib.h>
#include <stdio.h>

typedef struct {
int x;
int y;
} square;

square rookMove (square sq) {
int newCoord = (rand() % 8) + 1;
if (rand() % 2) {
while (newCoord == sq.x)
newCoord = (rand() % 8) + 1;
sq.x = newCoord;
} else {
while (newCoord == sq.y)
newCoord = (rand() % 8) + 1;
sq.y = newCoord;
}
return sq;
}

float rookJourneys (int trials) {
int moves = 0;
for (int i = 0; i < trials; i++) {
square sq = {1, 1};
while (sq.x != 8 || sq.y != 8) {
sq = rookMove(sq);
moves++;
}
}
return (float) moves / (float) trials;
}

void main () {
srand(time(NULL));
printf("%.6f\n", rookJourneys(1000000));
}

Markov chain

We can also attack this problem treating the sequence of rook moves as a discrete-time Markov chain.

A Markov chain (or process) can be described by a set of states, $S = \{s_1, s_2, . . . , s_n\}$ and a probabilities matrix, $M =\{p_{ij}\}, 1 \leq i,j \leq n$ . The process starts in one of these states and moves successively from one state to another. Each move is called a step. If the chain is currently in state $s_i$ , then it moves to state $s_j$ at the next step with a probability denoted by $p_{ij}$ , and this probability does not depend upon which states the chain was in before the current state (we say that a Markov chain has limited memory, as any future state depends on the past m states).

The probabilities $p_{ij}$ are called transition probabilities. The process can remain in the state it is in, and this occurs with probability $p_{ii}$ . An initial probability distribution, defined on S, specifies the starting state. Usually, this is done by specifying a particular state as the starting state.

Let’s now see the what are the particular characteristics of our newly discovered Markov chain. One can associate a unique state to each of the 64 squares the rook can eventually go. The rook initial square — which coordinates are (1, 1) — is the starting state for all sequences. It’s also easy to see that all transition probabilities of the form $p_{ii}$ are zero (with one exception; see below) since the rook has to make a move every minute (it cannot stay in the same square). As any transition probability depends only on the starting and destination states, this Markov chain has order (or memory) $m=1$ .

Our Markov chain has another interesting property: it has an absorbing state — with coordinates (8,8) — a state it is impossible to leave, meaning that $p_{ii} = 1$ $\land$ $p_{ij} = 0$ , $i \neq j$ for the absorbing state $s_i$ (those two conditions can be expressed more concisely, using Kronecker’s delta, as $p_{ij} = \delta_{ij}$ ). All other states are transient.

The Magma script (see box below) calculates the expected number of minutes taken by the rook to get to the final square starting on any other square. It follows the very clear and interesting explanation about absorbing Markov chains found in “Introduction to Probability“, Gristead & Snell (see chap. 11, section 11.2, pp. 416-419).

/**
* Square (i, j) on the board (1 <= i,j <= 8) is unequivocally
* represented by state (i, j) = 8 * (i - 1) + (j - 1) + 1.
* Note that 1 <= state (i, j) <= 64.
*/
function state (i, j)
return 8 * (i - 1) + (j - 1) + 1;
end function;
/**
* This function returns a SeqEnum containing the coordinates
* (row/column) associated with the input state (1 <= i,j <= 8).
*/
function unstate (n)
return [(n - 1) mod 8 + 1, (n - 1) div 8 + 1];
end function;
/**
* Entry Q[u, v] on the transition probability matrix below
* denotes the probability of a transition from transient
* state u to transient state v.
*/
Q := ZeroMatrix (RealField (), 63, 63);
for i, j, k in [1 .. 8] do
// make sure the absorbing state (8, 8) is excluded
if i + j ne 16 and i + k ne 16 and j + k ne 16 then
if k ne j then
// probability to move on the same row: 1/2
// probability to move to a square on that row: 1/7
Q [state (i, j)][state (i, k)] := (1 / 2) * (1 / 7);
end if;
if k ne i then
// probability to move on the same column: 1/2
// probability to move to a square on that column: 1/7
Q [state (i, j)][state (k, j)] := (1 / 2) * (1 / 7);
end if;
end if;
end for;
/**
* N is the 'fundamental matrix' for P, the transition probability
* matrix for all allowed states, either transient or absorbing.
*/
I := IdentityMatrix (RealField (), 63);
N := (I - Q) ^ -1;
c := Matrix (RealField (), 63, 1, [1.0 : k in [1 .. 63]]);
t := N * c;
printf "Starting square\t Expected time to reach destination\n";
for n in [1 .. 63] do
printf "    (%o, %o)\t t = %o\n",
unstate(n)[1], unstate(n)[2], t[n][1];
end for;

In simple terms, this script evaluates the expression below for each one of the 63 possible starting squares:

$E_{ij} = \displaystyle\sum_{\substack{all \, paths\\ starting \, on\\ square \, (i,j)}}^{} probability \, [path] \, \times \, time \, (path)$

Magma is a commercial software package designed for computations in algebra, number theory, algebraic geometry and algebraic combinatorics. The mentioned script was executed using Magma Calculator, a web interface that provides free access to the Magma software under certain run time and script size restrictions.

After just 0.3 seconds, we have the desired results (see box below). It seems that the expected times could probably be integers (63 and 70), something we haven’t been able to notice during the simulation session.

Using the same tool, it’s also easy to evaluate the probability that the rook takes, say, 500 minutes, to reach the destination square starting from the square (1, 1). All that is needed is to execute the command ((Q^500)*c [state(1, 1)], which gives 0.066% as the answer.

Starting square  Expected time to reach destination
(1, 1)       t = 70.0000000000000000000000000016
(2, 1)       t = 70.0000000000000000000000000030
(3, 1)       t = 70.0000000000000000000000000030
(4, 1)       t = 70.0000000000000000000000000027
(5, 1)       t = 70.0000000000000000000000000025
(6, 1)       t = 70.0000000000000000000000000030
(7, 1)       t = 70.0000000000000000000000000024
(8, 1)       t = 63.0000000000000000000000000025
(1, 2)       t = 70.0000000000000000000000000023
(2, 2)       t = 70.0000000000000000000000000019
...                         ...
(6, 7)       t = 70.0000000000000000000000000025
(7, 7)       t = 70.0000000000000000000000000021
(8, 7)       t = 63.0000000000000000000000000017
(1, 8)       t = 63.0000000000000000000000000018
(2, 8)       t = 63.0000000000000000000000000026
(3, 8)       t = 63.0000000000000000000000000022
(4, 8)       t = 63.0000000000000000000000000023
(5, 8)       t = 63.0000000000000000000000000023
(6, 8)       t = 63.0000000000000000000000000027
(7, 8)       t = 63.0000000000000000000000000023

Conditional probabilities

One can further improve the Markovian approach used by looking at the pattern showed in the previous results. Considering the minimum number of moves taken by the rook to get to the destination square, one can divide the chessboard squares into just three types, thus greatly reducing the size of the transition probabilities matrix from 64×64 to only 3×3.

For the sake of notation, we call a type n square any one from which the rook must take at least n move(s), or second(s), to get to the target square. This way, the chessboard can be partitioned into 1 (one) destination square (type 0), 14 (fourteen) “edge” squares (type 1) and 49 (forty-nine) remaining squares (type 2). For all type 1 squares, the expected time is close to 63 minutes while for every type 2 one the expected time is a little bit longer, around 70 minutes.

Chessboard zones

A much simpler transition probability matrix can then be defined taking into account only five transitions: $type \, 2 \rightarrow type \, 2$ , $type \, 2 \rightarrow type \, 1$ , $type \, 1 \rightarrow type \, 2$ , $type \, 1 \rightarrow type \, 1$ and $type \, 1 \rightarrow type \,0$ . For convenience, we can denote the associated transition probability $p \, [type \, i \rightarrow type \, j]$ as $p_{ij}$ .

Let the expected number of minutes it will take the rook to reach the destination square from any $type \, 1$ square be $\bold{E_1}$ . Let the expected number of minutes it will take the rook to get to the same destination square from any $type \, 2$ square be $\bold{E_2}$ . Now we can write the following two linear equations relating $\bold{E_1}$ and $\bold{E_2}$ :

$\bold{E_1} = p_{10} \, . \, 1 + p_{11} \, . \, (\bold{E_1} + 1) + p_{12} \, . \, (\bold{E_2} + 1)$ and

$\bold{E_2} = p_{21} \, . \, (\bold{E_1} + 1) + p_{22} \, . \, (\bold{E_2} + 1)$

The transition probabilites are easy to calculate:

$p_{10} = 1/14$ , $p_{11} = 6/14$ , $p_{12} = 7/14$ , $p_{21} = 12/14$ , $p_{22} = 2/14$

(of course, $\displaystyle\sum_{j=0}^{2} p_{1j} = \displaystyle\sum_{j=1}^{2} p_{2j} = 1$ ).

We can now solve the equation system, which gives the solution $\bold{E_1}$ = 63 minutes and $\bold{E_2}$ = 70 minutes (our goal).

This approach not only is simple but also powerful since it definitely shows that the expected time is an integer. It can also be easily extended to chessboards of other sizes, e.g. 10×10 or 15×15.

Who’s (really) the best chess player?

Posted on September 20, 2014 by JHAF

You’ve just made it into the finals of a chess tournament. Although your opponent is “stronger” than you, you are trying to think of some strategy to beat him on the board.

There will be 2 (two) matches, and if they both result in a tie, a third match will be played to decide the winner, who will take home a $1,000 prize. If the play-off also ends in a draw, you’ll share the prize with your opponent.

The scoring system is the one used in chess tournaments since the middle of the 19th century: players who scored a win in a game are awarded 1 (one) point, while those scoring draws are given a 0.5 (half-point) each. Losing a game, as you might expect, is worth 0 (zero) point.

You know, from previous games against the same opponent, that you can choose between two different strategies: “play fearlessly”, in which you win 45% and lose 55% of the time, or “play defensively”, in which you draw 90% and lose 10% of the time (but selecting this alternative you’ll have no chance to win). Note that both strategies have the same expected value since 0.45 x 1.0 = 0.9 x 0.5.

If you play optimally, what are your chances of beating your opponent (and winning the $1,000 prize)?

The decision tree below shows all possible sequence of events that result in your winning the tournament. To keep the diagram simple, all remaining, non-winning sequences were omitted. Obviously this decision tree applies equally well to any other zero-sum game besides chess that can also result in a draw (e.g. checkers).

Tournament finals decision tree

It is really surprising that the probability of you, the “weaker” player, winning the finals is around 0.537 (or 0.536625 to be exact), which is greater than 0.5. Each strategy, analyzed separately, confirms that, on the average, your opponent will win more games than you. Yet the odds of grabbing the $1,000 are in your favor! How come?

N-ary m-sequence generator in Python

Posted on February 15, 2014 by JHAF

Maximum length sequences (or m-sequences) are bit sequences generated using maximal LFSRs (Linear Feedback Shift Registers) and are so called because they are periodic and reproduce every binary sequence that can be represented by the shift registers (i.e., for length-m registers they produce a sequence of length $2^{m}-1$ ). Although originally defined for binary sequences, the concept of m-sequence can be extended to sequences over $GF(n), n>2$ .

Despite being deterministically generated, m-sequences have nice statistical properties, which resemble those of white noise (they are spectrally flat, with the exception of a near-zero constant term). For this reason, m-sequences are often referred to as pseudo random noise code (PN code). Unfortunately though, unpredictability is not among those properties (see below).

The configuration of the feedback taps in a binary LFSR can be expressed in finite field arithmetic as a polynomial in $GF(2^{n})$ . The LFSR is maximal-length if and only if the corresponding feedback polynomial is primitive. The linear complexity (LC) of a given periodic sequence is the number of cells in the shortest LFSR that can generate that sequence. The correlation between two sequences is the complex inner product of the first sequence with a shifted version of the second sequence. It is called an autocorrelation if the two sequences are the same or a cross-correlation if they are distinct. Particularly interesting for spread spectrum application are sequences (not necessarily m-sequences) that exhibit low autocorrelation and low cross-correlation (the ideal correlation function would then be the Kronecker’s delta).

Apart from spread spectrum communications, m-sequences are used in a variety of areas including digital watermarking and cryptography. As m-sequences are derived from linear recurrence relations — which lead to fairly easy cryptanalysis — they must be processed by nonlinear functions in order to be used in cryptographic applications. A good example is Trivium, a 80-bit stream cipher that consists of three shift registers of different lengths.

#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: N-ary sequence generator in Python
#
# Version: 1
#
# Date: 2014-02-14
#
# License: Attribution-NonCommercial-ShareAlike 3.0 Unported
#          (CC BY-NC-SA 3.0)
#===========================================================

from functools import reduce
from fractions import Fraction
from cmath import rect,pi

def flatList(s,q):
    """Converts (list of) polynomials into (list of) elements
       of finite field mapped as integers.
         s: list of polynomials
         q: order of finite field"""
    if type(s[0]) is int:
        return s
    elif type(s[0]) is list:
        return [reduce(lambda i,j:(i*q)+j,e) for e in s]
    else:
        raise TypeError

def printListOfNumbers(S,L,*X):
    """Print list of numbers according to their particular
       format (integer, float or complex)"""
    print(S+" [",end="")
    for i,e in enumerate(L):
        if type(e) is complex:
            print("{:5.3f}{:+5.3f}i".format(e.real,e.imag),end="")
        elif type(e) is float:
            print("{:5.3f}".format(e),end="")
        elif type(e) is int:
            print("{:d}".format(e),end="")
        elif type(e) is Fraction:
            print("{:s}".format(e),end="")
        else:
            raise TypeError
        if i<len(L)-1:
            print(", ",end="")
    print("]",*X)

def xac(s,q=None,d=None,n=None):
    """Evaluates the complex auto-correlation of a periodic
       sequence with increasing delays within the period.
       Input length must correspond to a full period.
         s: q-ary periodic sequence
         q: order of finite field
         d: maximum denominator allowed in fractions
         n: number of decimal places in floating point numbers"""
    return xcc(s,s,q,d,n)
    
def xcc(s1,s2,q=None,d=None,n=None):
    """Evaluates the complex cross-correlation between two
       equally periodic q-ary sequences with increasing delays
       within the period. Input length must correspond to a full
       period.
         s: q-ary periodic sequence
         q: order of finite field
         d: maximum denominator allowed in fractions
         n: number of decimal places in floating point numbers"""
    
    def cc(s1,s2):
        """Evaluates the complex correlation between two equally
           periodic numerical sequences.        
             s1,s2: q-ary periodic sequences"""      
        assert type(s1[0]) == type(s2[0])
        if type(s1[0]) is list:
            s3 = [[(j-i)%q for i,j in zip(u,v)] for u,v in zip(s1,s2)]
            s4 = [reduce(lambda x,y:(x*q)+y,e) for e in s3]
            z = sum(rect(1,2*pi*i/q) for i in s4)/len(s1)
        elif type(s1[0]) is int:
            z = sum(rect(1,2*pi*(j-i)/q) for i,j in zip(s1,s2))/len(s1)
        else:
            raise TypeError
        zr,zi = round(z.real,n),round(z.imag,n)
        if abs(zi%1)<10**-n:
            if abs(zr-round(zr))<10**-n:
                return int(zr)
            elif Fraction(z.real).limit_denominator().denominator<=d:
                return Fraction(z.real).limit_denominator()
            else:
                return zr
        else:
            return complex(zr,zi)

    q = 2 if q is None else q
    d = 30 if d is None else d
    n = 3 if n is None else n
    assert len(s1) == len(s2)
    return [cc(s1,s2[i:]+s2[:i]) for i in range(len(s1))]

def LFSR(P,S,M,N,K):
    """Outputs K-ary sequence with N elements. Each element is
       derived from M successive values of the LFSR sequence
       generated by polynomial P and initial state S. Polynomial
       P is represented by a list of coefficients in decreasing
       power order."""
    def LFSR2():
        """Generates linear K-ary sequence according to polynomial
           P and initial state S. If P is primitive, sequence length
           is exactly one period."""
        seq,st = [S[-1]],S
        for j in range(K**len(S)-2):
            st0 = sum([i*j for i,j in zip(st,P[1:])])%K
            st = [st0]+st[:-1]
            seq += [st[-1]]
        return seq

    assert len(P) > 1 and len(P)-1 == len(S)
    s = LFSR2()
    L = len(s)
    assert M <= L
    return [s[i%L] if M == 1 else (s[i%L:]+s[:i%L])[:M] for i in range(N)] 

if __name__ == "__main__":
       
    # Binary sequence over GF(2) generated by the LFSR
    # defined by non primitive polynomial x⁴+x³+x+1.
    # This is not a m-sequence since its period is 6
    # (<15 = 2⁴-1)
    s01 = LFSR([1,1,0,1,1],[0,0,0,1],1,15,2)
    print("s01 =",s01,"\n")

s01 = [1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0]

    # Sequence over GF(2⁴) derived from sequence "s01".
    # The polynomial elements were also mapped to integers
    # in Z16, in order to show the period. 
    s04 = LFSR([1,1,0,1,1],[0,0,0,1],4,15,2)
    print("s04 =",s04,"\n")
    print("s04 =",flatList(s04,2),"\n")

s04 = [[1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 1, 1],
       [1, 1, 1, 0], [1, 1, 0, 0], [1, 0, 0, 0], [0, 0, 0, 1],
       [0, 0, 1, 1], [0, 1, 1, 1], [1, 1, 1, 0], [1, 1, 0, 0],
       [1, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0]]

s04 = [8, 1, 3, 7, 14, 12, 8, 1, 3, 7, 14, 12, 9, 2, 4]

    # m-sequence over GF(2) generated by the LFSR defined
    # by the primitive polynomial x⁴+x+1. Its period is
    # equal to 2⁴-1=15
    s11 = LFSR([1,1,0,0,1],[0,0,0,1],1,15,2)
    print("s11 =",s11,"\n")

s11 = [1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0]

    # Autocorrelation of m-sequence "s11". This function
    # is two-valued and has the same period as sequence
    # "s11"
    printListOfNumbers("ac(s11) =",xac(s11),"\n")

ac(s11) = [1, -1/15, -1/15, -1/15, -1/15, -1/15, -1/15, -1/15,
           -1/15, -1/15, -1/15, -1/15, -1/15, -1/15, -1/15]

    # Sequence over GF(2²) derived from m-sequence "s11"
    s12 = LFSR([1,0,0,1,1],[0,0,0,1],2,15,2)
    print("s12 =",s12,"\n")

s12 = [[1, 0], [0, 0], [0, 0], [0, 1], [1, 0], [0, 0], [0, 1],
       [1, 1], [1, 0], [0, 1], [1, 0], [0, 1], [1, 1], [1, 1], [1, 1]]

    
    # Autocorrelation of sequence "s12"
    printListOfNumbers("ac(s12) =",xac(s12,4),"\n")

ac(s12) = [1, 7/15, 7/15, 7/15, 7/15, 7/15, 7/15, 7/15, 7/15,
           7/15, 7/15, 7/15, 7/15, 7/15, 7/15]

    # Sequence over GF(2³) derived from m-sequence "s11"
    s13 = LFSR([1,0,0,1,1],[0,0,0,1],3,15,2)
    print("s13 =",s13,"\n")

s13 = [[1, 0, 0], [0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0],
       [0, 0, 1], [0, 1, 1], [1, 1, 0], [1, 0, 1], [0, 1, 0],
       [1, 0, 1], [0, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 0]]

    # Autocorrelation of sequence "s13"
    printListOfNumbers("ac(s13) =",xac(s13,8,d=1000),"\n")

ac(s13) = [1, 0.844, 0.844, 0.844, 0.844, 0.844, 0.844, 0.844,
           0.844, 0.844, 0.844, 0.844, 0.844, 0.844, 0.844]

    # Sequence over GF(2⁴) derived from the m-sequence "s11"
    s14 = LFSR([1,0,0,1,1],[0,0,0,1],4,15,2)
    print("s14 =",s14,"\n")

s14 = [[1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0],
       [1, 0, 0, 1], [0, 0, 1, 1], [0, 1, 1, 0], [1, 1, 0, 1],
       [1, 0, 1, 0], [0, 1, 0, 1], [1, 0, 1, 1], [0, 1, 1, 1],
       [1, 1, 1, 1], [1, 1, 1, 0], [1, 1, 0, 0]]

    # Autocorrelation of sequence "s14" 
    printListOfNumbers("ac(s14) =",xac(s14,16,d=1000),"\n")

ac(s14) = [1, 0.959, 0.959, 0.959, 0.959, 0.959, 0.959, 0.959,
           0.959, 0.959, 0.959, 0.959, 0.959, 0.959, 0.959]

    # Binary sequence over GF(2) generated by the LFSR
    # defined by the primitive polynomial (x⁴+x³+1).
    # This is also a m-sequence with period equal to
    # 15 = 2⁴-1
    s21 = LFSR([1,0,0,1,1],[0,0,0,1],1,15,2)
    print("s21 =",s21,"\n")

s21 = [1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]

    # Autocorrelation of sequence "s21"       
    printListOfNumbers("ac(s21) =",xac(s21),"\n")

ac(s21) = [1, -1/15, -1/15, -1/15, -1/15, -1/15, -1/15,
           -1/15, -1/15, -1/15, -1/15, -1/15, -1/15, -1/15, -1/15]

    # Cross-correlation between m-sequences "s11" and "s21".
    # This function is four-valued and has the same period
    # as sequences "s11" and "s21"
    printListOfNumbers("cc(s11,s21) =",xcc(s11,s21),"\n")

cc(s11,s21) = [-1/15, 1/5, -1/15, 7/15, 1/5, -1/3, -1/15,
               1/5, 7/15, -1/3, 1/5, -1/3, -1/3, -1/15, -1/15]

    # m-sequence over GF(3) generated by the LFSR defined
    # by the primitive polynomial x²+2x+1. Its period is
    # equal to 3²-1=8 
    s31 = LFSR([1,2,1],[1,0],1,8,3)
    print("s31 =",s31,"\n")

s31 = [0, 1, 2, 2, 0, 2, 1, 1]

    # Autocorrelation of sequence "s31"
    printListOfNumbers("ac(s31) =",xac(s31,3),"\n")

ac(s31) = [1, -1/8, -1/8, -1/8, -1/8, -1/8, -1/8, -1/8]

    # Sequence over GF(3²) derived from m-sequence "s31"
    s32 = LFSR([1,2,1],[1,0],2,8,3)
    print("s32 =",s32,"\n")

s32 = [[0, 1], [1, 2], [2, 2], [2, 0], [0, 2], [2, 1], [1, 1], [1, 0]]

    # Autocorrelation of sequence "s32"
    printListOfNumbers("ac(s32) =",xac(s32,3),"\n")

ac(s32) = [1, -1/8, -1/8, -1/8, -1/8, -1/8, -1/8, -1/8]

    # Sequence over GF(3³) derived from m-sequence "s31"
    s33 = LFSR([1,2,1],[1,0],3,8,3)
    print("s33 =",s33,"\n")

s33 = [[0, 1, 2], [1, 2, 2], [2, 2, 0], [2, 0, 2],
       [0, 2, 1], [2, 1, 1], [1, 1, 0], [1, 0, 1]]

    # Autocorrelation of sequence "s33"
    printListOfNumbers("ac(s33) =",xac(s33,3),"\n")

ac(s33) = [1, -1/8, -1/8, -1/8, -1/8, -1/8, -1/8, -1/8]

    # m-sequence over GF(3) generated by the LFSR defined
    # by the primitive polynomial x³+x²+2. Its period is
    # equal to 3³-1=26 
    s41 = LFSR([1,1,0,2],[1,0,0],1,26,3)
    print("s41 =",s41,"\n")

s41 = [0, 0, 1, 1, 1, 0, 2, 1, 1, 2, 1, 0, 1, 0, 0, 2, 2, 2, 0, 1,
       2, 2, 1, 2, 0, 2]

    # Autocorrelation of m-sequence "s41". This function is
    # two-valued and has the same period as sequence "s41"    
    printListOfNumbers("ac(s41) =",xac(s41,3),"\n")

ac(s41) = [1, -1/26, -1/26, -1/26, -1/26, -1/26, -1/26, -1/26, -1/26, 
           -1/26, -1/26, -1/26, -1/26, -1/26, -1/26, -1/26, -1/26, -1/26,
           -1/26, -1/26, -1/26, -1/26, -1/26, -1/26, -1/26, -1/26]

    # Sequence over GF(3²) derived from m-sequence "s41"
    s42 = LFSR([1,1,0,2],[1,0,0],2,26,3)
    print("s42 =",s42,"\n")

s42 = [[0, 0], [0, 1], [1, 1], [1, 1], [1, 0], [0, 2],
       [2, 1], [1, 1], [1, 2], [2, 1], [1, 0], [0, 1],
       [1, 0], [0, 0], [0, 2], [2, 2], [2, 2], [2, 0],
       [0, 1], [1, 2], [2, 2], [2, 1], [1, 2], [2, 0],
       [0, 2], [2, 0]]

    # Autocorrelation of sequence "s42"
    printListOfNumbers("ac(s42) =",xac(s42,9),"\n")

ac(s42) = [1, 0.701, 0.701, 0.701, 0.701, 0.701, 0.701,
           0.701, 0.701, 0.701, 0.701, 0.701, 0.701, 0.838,
           0.701, 0.701, 0.701, 0.701, 0.701, 0.701, 0.701,
           0.701, 0.701, 0.701, 0.701, 0.701]

    # Sequence over GF(3³) derived from m-sequence "s31"
    s43 = LFSR([1,1,0,2],[1,0,0],3,26,3)
    print("s43 =",s43,"\n")

s43 = [[0, 0, 1], [0, 1, 1], [1, 1, 1], [1, 1, 0],
       [1, 0, 2], [0, 2, 1], [2, 1, 1], [1, 1, 2],
       [1, 2, 1], [2, 1, 0], [1, 0, 1], [0, 1, 0],
       [1, 0, 0], [0, 0, 2], [0, 2, 2], [2, 2, 2],
       [2, 2, 0], [2, 0, 1], [0, 1, 2], [1, 2, 2],
       [2, 2, 1], [2, 1, 2], [1, 2, 0], [2, 0, 2],
       [0, 2, 0], [2, 0, 0]]

    # Autocorrelation of sequence "s43"
    printListOfNumbers("ac(s43) =",xac(s43,27),"\n")

ac(s43) = [1, 0.963, 0.963, 0.963, 0.963, 0.963, 0.963,
           0.963, 0.963, 0.963, 0.963, 0.963, 0.963, 0.981,
           0.963, 0.963, 0.963, 0.963, 0.963, 0.963, 0.963,
           0.963, 0.963, 0.963, 0.963, 0.963]

    # Sequence over Z20 with ideal autocorrelation function
    # (Kronecker's delta)
    s51 = [t**2%20 for t in range(10)]
    print("s51 =",s51,"\n")

s51 = [0, 1, 4, 9, 16, 5, 16, 9, 4, 1]

    # Autocorrelation of sequence "s51"  
    printListOfNumbers("xac(s51) =",xac(s51,20),"\n")

xac(s51) = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

    # Sequence over Z7 with ideal autocorrelation function
    # (Kronecker's delta)
    s61 = [(t*(t+1)//2)%7 for t in range(7)]
    print("s61 =",s61,"\n")

s61 = [0, 1, 3, 6, 3, 1, 0]

    # Autocorrelation of sequence "s61"  
    printListOfNumbers("xac(s61) =",xac(s61,7),"\n")

xac(s61) = [1, 0, 0, 0, 0, 0, 0]

HMAC-SHA-256 implementation in Python 3

Posted on June 11, 2013 by JHAF

A hash-based message authentication code (HMAC) is an algorithm for generating a message authentication code (MAC), which can be used to verify both the integrity and the authentication of a given message. Although both constructs, HMAC and MAC, are based on a cryptographic hash function (such as SHA-1, Whirlpool or RIPEMD-160), the former requires a key (shared between the sender and the receiver of the message) while the latter doesn’t. The HMAC concept was proposed by Bellare, Canetti, and Krawczyk in 1996 and is described in RFC 2104.

As seen from its name, HMAC-SHA-256 uses as its engine the SHA-256 cryptographic hash function, which produces message digests of 256 bits in length. Like the other members of the SHA-2 family (and also MD-5 and SHA-1), SHA-256 is an iterative hash function (based on the Merkle–Damgård scheme) that works by breaking up the input message into blocks of a fixed size (512 bits for SHA-256) and iterating over them with a compression function.

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

from functools import reduce
from math import log,ceil

def intToList2(number,length):
    """Convert a number into a byte list
       with specified length"""
    return [(number >> i) & 0xff
            for i in reversed(range(0,length*8,8))]

def intToList(number):
    """Converts an integer of any length into an integer list"""
    L1 = log(number,256)
    L2 = ceil(L1)
    if L1 == L2:
        L2 += 1
    return [(number&(0xff<<8*i))>>8*i for i in reversed(range(L2))] 

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

def bitList32ToList4(lst):
    """Convert a 32-bit list into a 4-byte list"""
    def bitListToInt(lst):
        return reduce(lambda x,y:(x<<1)+y,lst)    
    
    lst2 = []
    for i in range(0,len(lst),8):
        lst2.append(bitListToInt(lst[i:i+8]))
    return list([0]*(4-len(lst2)))+lst2

def list4ToBitList32(lst):
    """Convert a 4-byte list into a 32-bit list"""
    def intToBitList2(number,length):
        """Convert an integer into a bit list
        with specified length"""
        return [(number>>n) & 1
                for n in reversed(range(length))]    
    
    lst2 = []
    for e in lst:
        lst2 += intToBitList2(e,8)
    return list([0]*(32-len(lst2)))+lst2

def add32(p,q,r=None,s=None,t=None):
    """Add up to five 32-bit numbers"""
    mask32 = (1<<32)-1
    p2,q2 = listToInt(p), listToInt(q)
    if t is None:
        if s is None:
            if r is None:
                return intToList2((p2+q2)&mask32,4)
            else:
                r2 = listToInt(r)
                return intToList2((p2+q2+r2)&mask32,4)
        else:
            r2,s2 = listToInt(r),listToInt(s)
            return intToList2((p2+q2+r2+s2)&mask32,4)
    else:
        r2,s2,t2 = listToInt(r),listToInt(s),listToInt(t)
        return intToList2((p2+q2+r2+s2+t2)&mask32,4)

def xor(x,y,z=None):
    """Evaluate the XOR on two or three operands"""
    if z is None:
        return list(i^j for i,j in zip(x,y))
    else:
        return list(i^j^k for i,j,k in zip(x,y,z))
   
def sha256(m):
    """Return the SHA-256 digest of input"""
    def padding(m):
        """Pad message according to SHA-256 rules"""
        def bitListToList(lst):
            """Convert a bit list into a byte list"""
            lst2 = [0]*((8-len(lst)%8)%8)+lst
            return [reduce(lambda x,y:(x<<1)+y,lst2[i*8:i*8+8])
                    for i in range(len(lst2)//8)]
    
        def intToBitList(number):
            """Convert an integer into a bit list"""
            return list(map(int,list(bin(number)[2:])))
    
        if type(m) is int:
            m1 = intToBitList(m)
            L = len(m1)
            k = (447-L)%512
            return bitListToList(m1+[1]+list([0]*k))+intToList2(L,8)
        else:
            m1 = m
            if type(m) is str:
                m1 = list(map(ord,m))
            if not(type(m) is list):
                raise TypeError
            L = len(m1)*8
            k = (447-L)%512
            return m1+bitListToList([1]+list([0]*k))+intToList2(L,8)    
    
    def compress(m):
        """Evaluates SHA-256 compression function to input"""
        def Ch(x,y,z):
            return list([(i&j)^((i^0xff)&k) for i,j,k in zip(x,y,z)])
        
        def Maj(x,y,z):
            return list([(i&j)^(i&k)^(j&k) for i,j,k in zip(x,y,z)])              
        
        def rotRight(p,n):
            """Rotate 32-bit word right by n bits"""
            p2 = list4ToBitList32(p)
            return bitList32ToList4(p2[-n:]+p2[:-n])
        
        def shiftRight(p,n):
            """Shift 32-bit right by n bits"""
            p2 = list4ToBitList32(p)
            return bitList32ToList4(list(bytes(n))+p2[:-n])
        
        def Sigma0(p):
            """SHA-256 function"""
            return xor(rotRight(p,2),rotRight(p,13),rotRight(p,22))
        
        def Sigma1(p):
            """SHA-256 function"""
            return xor(rotRight(p,6),rotRight(p,11),rotRight(p,25))
        
        def sigma0(p):
            """SHA-256 function"""
            return xor(rotRight(p,7),rotRight(p,18),shiftRight(p,3))
        
        def sigma1(p):
            """SHA-256 function"""
            return xor(rotRight(p,17),rotRight(p,19),shiftRight(p,10))            
        
        nonlocal H
        [a,b,c,d,e,f,g,h] = H
        K = [0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
             0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
             0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
             0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
             0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
             0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
             0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
             0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
             0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
             0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
             0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
             0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
             0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
             0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
             0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
             0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2]    
        W = [None]*64
        for t in range(16):
            W[t] = m[t*4:t*4+4]
        for t in range(16,64):
            W[t] = add32(sigma1(W[t-2]),W[t-7],sigma0(W[t-15]),W[t-16])
        for t in range(64):
            T1 = add32(h,Sigma1(e),Ch(e,f,g),intToList2(K[t],4),W[t])
            T2 = add32(Sigma0(a),Maj(a,b,c))
            h = g; g = f; f = e; e = add32(d,T1)
            d = c; c = b; b = a; a = add32(T1,T2)
        H = [add32(x,y) for x,y in zip([a,b,c,d,e,f,g,h],H)]
        
    H0 = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
         0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19]
    H = list(map(lambda x:intToList2(x,4),H0))
    mp = padding(m)
    for i in range(0,len(mp),64):
        compress(mp[i:i+64])
    return listToInt([s2 for s1 in H for s2 in s1])

def hmac_sha256(k,m):
    """Return the HMAC-SHA-256 of the input
       HMAC(k,m)=SHA-256((k⊕opad)∥SHA-256((k⊕ipad)∥m))"""
    opad = list([0x5c]*64); ipad = list([0x36]*64)
    if type(k) is int:
        k1 = intToList(k)
        L = len(k1)
        if L > 64:
            K = intToList2(sha256(k),32)+list([0]*32)
        else:
            K = k1+list([0]*(64-L))  
    else:
        k1 = list(map(ord,k))      
        L = len(k1)
        if L > 64:
            K = intToList(sha256(k1))
        else:
            K = k1+list([0]*(64-L))
    if type(m) is int:
        M = intToList(m)
    else:
        M = list(map(ord,m))
    arg1 = xor(K,opad)
    arg2 = xor(K,ipad)
    return sha256(arg1+intToList(sha256(arg2+M)))

if __name__ == '__main__':

    # Wikipedia's test case #1
    assert hmac_sha256("","") == 0xb613679a0814d9ec772f95d778c35fc5ff1697c493715653c6c712144292c5ad
    
    # Wikipedia's test case #2
    assert hmac_sha256("key", "The quick brown fox jumps over the lazy dog") == \
           0xf7bc83f430538424b13298e6aa6fb143ef4d59a14946175997479dbc2d1a3cd8
    
    # RFC 4231 - Identifiers and Test Vectors for HMAC-SHA-224, HMAC-SHA-256,
    # HMAC-SHA-384, and HMAC-SHA-512
    
    # RFC 4231 Test case 1
    Key1 = 0x0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b
    Data1 = 0x4869205468657265
    HMAC1 = 0xb0344c61d8db38535ca8afceaf0bf12b881dc200c9833da726e9376c2e32cff7    
    assert hmac_sha256(Key1,Data1) == HMAC1      

    # RFC 4231 Test case 2
    Key2 = 0x4a656665
    Data2 = 0x7768617420646f2079612077616e7420666f72206e6f7468696e673f
    HMAC2 = 0x5bdcc146bf60754e6a042426089575c75a003f089d2739839dec58b964ec3843
    assert hmac_sha256(Key2,Data2) == HMAC2
    
    # RFC 4231 Test case 3    
    Key3 = 0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
    Data3 = 0xdddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
    HMAC3 = 0x773ea91e36800e46854db8ebd09181a72959098b3ef8c122d9635514ced565fe
    assert hmac_sha256(Key3,Data3) == HMAC3

    # RFC 4231 Test case 4
    Key4 = 0x0102030405060708090a0b0c0d0e0f10111213141516171819
    Data4 = 0xcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcd
    HMAC4 = 0x82558a389a443c0ea4cc819899f2083a85f0faa3e578f8077a2e3ff46729665b
    assert hmac_sha256(Key4,Data4) == HMAC4

    # RFC 4231 Test case 5
    Key5 = 0x0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c
    Data5 = 0x546573742057697468205472756e636174696f6e 
    HMAC5 = 0xa3b6167473100ee06e0c796c2955552b
    assert hmac_sha256(Key5,Data5)>>128 == HMAC5

    # RFC 4231 Test case 6
    Key6 = 0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
    Data6 = 0x54657374205573696e67204c6172676572205468616e20426c6f636b2d53697a65204b6579202d2048617368204b6579204669727374
    HMAC6 = 0x60e431591ee0b67f0d8a26aacbf5b77f8e0bc6213728c5140546040f0ee37f54
    assert hmac_sha256(Key6,Data6) == HMAC6

    # RFC 4231 Test case 7    
    Key7 = 0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
    Data7 = 0x5468697320697320612074657374207573696e672061206c6172676572207468616e20626c6f636b2d73697a65206b657920616e642061206c6172676572207468616e20626c6f636b2d73697a6520646174612e20546865206b6579206e6565647320746f20626520686173686564206265666f7265206265696e6720757365642062792074686520484d414320616c676f726974686d2e
    HMAC7 = 0x9b09ffa71b942fcb27635fbcd5b0e944bfdc63644f0713938a7f51535c3a35e2
    assert hmac_sha256(Key7,Data7) == HMAC7

    print("Ok!")

Validation of an AES-CFB implementation in Python 3

Posted on June 7, 2013 by JHAF

A symmetric block cipher such as AES (or Triple DES) operates on blocks of fixed size (128 bits for AES and 64 bits for TDES). It is possible, however, to convert a block cipher into a stream cipher using one of the three following modes: cipher feedback (CFB), output feedback (OFB), and counter (CTR). A stream cipher eliminates the need to pad a message to be an integral number of blocks and, for this reason, can operate in real time, making it the natural choice for encrypting streaming data (e.g. voice).

The Python code shown below implements the encryption and decryption operations for CFB-8 and CFB-128 modes. These functions rely on the “basic” AES mode (ECB) services provided by sundAES, an AES implementation in Python presented in a previous blog.

#!/usr/bin/python3

import sys
from functools import reduce
import sundAES

# Auxiliary functions

def xor(x,y):
    """Returns the xor between two lists"""
    return bytes(i^j for i,j in zip(x,y))

def bytesToInt(b):
    """Converts a bytes string into an integer"""
    return listToInt(list(b))

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

def intToList(number):
    """Converts an integer into an integer list"""
    if number == 0:
        return [0]
    lst = []
    while number:
        lst += [number&0xff]
        number >>= 8
    return lst[::-1]

def intToBytes(number):
    """Converts an integer into a bytes list"""
    return bytes(intToList(number))

def intToList2(number,length=None):
    """Converts an integer into an integer list with
       16, 24 or 32 elements"""
    lst = []
    while number:
        lst.append(number&0xff)
        number >>= 8
    L = len(lst)
    if length:
        pZero = length-L
        assert pZero >= 0
    else:
        if L <= 16:
            pZero = 16-L
        elif L <= 24:
            pZero = 24-L
        elif L <= 32:
            pZero = 32-L
        else:
            raise ValueError
    return list(bytes(pZero)) + lst[::-1]

def intToBytes2(number,length=None):
    """Converts an integer into a bytes list with
       16, 24 or 32 elements"""
    return bytes(intToList2(number,length))

# Real crypto stuff starts here...

def encryptCFB8(keysize,key,iv,input):
    """Encrypts single bytes of input block (CFB8 mode)"""
    inputBuffer = intToBytes2(iv)
    if type(input) is int:
        ptext = intToBytes(input)
    else:
        ptext = bytes(map(ord,input))
    obj = sundAES.AES("MODE_ECB")
    obj.setKey(keysize,key,iv)    
    ctext = bytes()
    for i in range(0,len(ptext),1):
        AESoutput = obj.encrypt(inputBuffer)
        cbyte = bytes([AESoutput[0] ^ ptext[i]])
        inputBuffer = inputBuffer[1:] + cbyte
        ctext += cbyte
    if type(input) is int:
        ctext = bytesToInt(ctext)
    else:
        ctext = list(ctext)
    return ctext

def decryptCFB8(keysize,key,iv,input):
    """Decrypts single bytes of input block (CFB8 mode)"""
    inputBuffer = intToBytes2(iv)
    if type(input) is int:
        ctext = intToBytes(input)
    else:
        ctext = bytes(map(ord,input))
    obj = sundAES.AES("MODE_ECB")
    obj.setKey(keysize,key,iv) 
    ptext = bytes()
    for i in range(0,len(ctext),1):
        AESoutput = obj.encrypt(inputBuffer)
        pbyte = bytes([AESoutput[0] ^ ctext[i]])
        inputBuffer = inputBuffer[1:] + bytes(ctext[i])
        ptext += pbyte
    if type(input) is int:
        ptext = bytesToInt(ptext)
    else:
        ptext = "".join(chr(e) for e in ptext)
    return ptext

# ... and goes on here

def encryptCFB128(keysize,key,iv,input):
    """Encrypts a 16-byte input block (CFB128 mode)"""
    inputBuffer = intToBytes2(iv)
    if type(input) is int:
        ptext = intToList2(input)
    else:
        ptext = list(map(ord,input))
        L = 16-len(ptext)
        ptext = list(bytes(L)) + ptext
    obj = sundAES.AES("MODE_ECB")
    obj.setKey(keysize,key,iv)    
    ctext = bytes()
    L3 = len(ptext)
    for i in range(0,L3,16):
        AESoutput = obj.encrypt(inputBuffer)
        inputBuffer = xor(AESoutput,ptext[i:min(L3,i+16)])
        ctext += bytes(inputBuffer)
    if type(input) is int:
        ctext = bytesToInt(ctext)
    else:
        ctext = list(ctext)
    return ctext

def decryptCFB128(keysize,key,iv,input):
    """Decrypts a 16-byte input block (CFB128 mode)"""
    inputBuffer = intToBytes2(iv)
    if type(input) is int:
        ctext = intToList2(input)
    else:
        ctext = list(map(ord,input))
        L = 16-len(ctext)
        ctext = list(bytes(L)) + ctext
    obj = sundAES.AES("MODE_ECB")
    obj.setKey(keysize,key,iv) 
    ptext = bytes()
    L3 = len(ctext)
    for i in range(0,L3,16):
        AESoutput = obj.encrypt(inputBuffer)
        inputBuffer = ctext[i:min(L3,i+16)]
        ptextBlock = xor(AESoutput,inputBuffer)
        ptext += ptextBlock
    if type(input) is int:
        ptext = bytesToInt(ptext)
    else:
        ptext = "".join(chr(e) for e in ptext)
    return ptext

CFB8 encrypts (or decrypts) a single byte while CFB128 operates on a 16-byte block. Like the other stream modes (OFB and CTR), and differently from Electronic codebook (ECB) and Cipher block chaining (CBC) “block modes”, CFB dispenses padding and uses only the ECB encryption operation. This latter feature is very convenient for AES, since AES encryption and decryption operations are somewhat different.

The US National Institute of Standards and Technology (NIST) defines four types of Known Answer Test (KAT): GFSbox, KeySbox, Variable Key and Variable Text. The contents of file CFB8GFSbox128.rsp (see below) describe the GFSbox encryption and decryption tests cases for CFB8 using 128-bits AES keys.

# CAVS 11.1
# Config info for aes_values
# AESVS GFSbox test data for CFB8
# State : Encrypt and Decrypt
# Key Length : 128
# Generated on Fri Apr 22 15:11:46 2011

[ENCRYPT]

COUNT = 0
KEY = 00000000000000000000000000000000
IV = f34481ec3cc627bacd5dc3fb08f273e6
PLAINTEXT = 00
CIPHERTEXT = 03

... 5 test cases omitted

[DECRYPT]

COUNT = 0
KEY = 00000000000000000000000000000000
IV = f34481ec3cc627bacd5dc3fb08f273e6
CIPHERTEXT = 03
PLAINTEXT = 00

... 5 test cases omitted

As a second example, the contents of file CFB128VarKey192.rsp file that follow describe the Variable Key encryption and decryption tests cases for the CFB128 mode using 192-bits AES keys.

# CAVS 11.1
# Config info for aes_values
# AESVS VarKey test data for CFB128
# State : Encrypt and Decrypt
# Key Length : 192
# Generated on Fri Apr 22 15:11:55 2011

[ENCRYPT]

COUNT = 0
KEY = 800000000000000000000000000000000000000000000000
IV = 00000000000000000000000000000000
PLAINTEXT = 00000000000000000000000000000000
CIPHERTEXT = de885dc87f5a92594082d02cc1e1b42c

... 190 test cases omitted

[DECRYPT]

COUNT = 0
KEY = 800000000000000000000000000000000000000000000000
IV = 00000000000000000000000000000000
CIPHERTEXT = de885dc87f5a92594082d02cc1e1b42c
PLAINTEXT = 00000000000000000000000000000000

... 190 test cases omitted

Next is presented the Python program that extracts data from the files contained in the KAT_AES directory which names start with “CFB8” or “CFB128”, then builds the test cases and finally executes them.

#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: Validation of AES-CFB8 and AES-CFB128
#              implementations in Python
#
# Date: 2013-06-05
#
# License: Attribution-NonCommercial-ShareAlike 3.0 Unported
#          (CC BY-NC-SA 3.0)
#===========================================================

import os,sys,re
from functools import reduce
from glob import glob
import AES_CFB

# Global counters
noFilesTested = noFilesSkipped = 0
counterOK = counterNOK = 0

class AEStester:
    def buildTestCases(self,filename):
        """Build test cases described in a given file"""
        global noFilesTested,noFilesSkipped
        
        self.basename = os.path.basename(filename)
        if self.basename.startswith('CFB'):
            if self.basename.startswith('CFB8'):
                self.mode = "MODE_CFB8"
                result = re.search("CFB8(\D{6,})\d{3}",self.basename)
                self.typeTest = result.group(1)                
            elif self.basename.startswith('CFB128'):
                self.mode = "MODE_CFB128"
                result = re.search("CFB128(\D{6,})\d{3}",self.basename)
                self.typeTest = result.group(1)                
            else: # CFB1 files not considered
                noFilesSkipped += 1
                return
        else: # not CFB files
            noFilesSkipped += 1
            return
    
        noFilesTested += 1
        digits = re.search("(\d{3})\.",self.basename)
        self.keysize = 'SIZE_' + digits.group(1)
        self.iv = None
        for line in open(filename):
            line = line.strip()
            if (line == "") or line.startswith('#'):
                continue
            elif line == '[ENCRYPT]':
                self.operation = 'encrypt'
                continue
            elif line == '[DECRYPT]':
                self.operation = 'decrypt'
                continue
            param,_,value = line.split(' ',2)
            if param == "COUNT":
                self.count = int(value)
                continue
            else:           
                self.__setattr__(param.lower(),int(value,16))
                if (self.operation == 'encrypt') and (param == "CIPHERTEXT") or \
                   (self.operation == 'decrypt' and param == "PLAINTEXT"):
                    self.runTestCase()
    
    def runTestCase(self):
        """Execute test case and report result"""
        global counterOK,counterNOK      
        
        def printTestCase(result):
            print("Type={0:s} Mode={1:s} Keysize={2:s} Function={3:s} Count={4:03d} {5:s}"\
                  .format(self.typeTest,self.mode[5:],\
                          self.keysize[5:],self.operation.upper(),\
                          self.count,result))              
        if self.operation == 'encrypt':
            if self.mode == "MODE_CFB8":
                CIPHERTEXT = AES_CFB5.encryptCFB8(self.keysize,self.key,self.iv,self.plaintext)
            else:
                CIPHERTEXT = AES_CFB5.encryptCFB128(self.keysize,self.key,self.iv,self.plaintext)
            try:
                assert self.ciphertext == CIPHERTEXT
                counterOK += 1
                printTestCase("OK")   
            except AssertionError:
                counterNOK +=1
                print(self.basename,end=" ")
                printTestCase("failed")
                print("Expected ciphertext={0:0x}".format(self.ciphertext))
                print("Returned ciphertext={0:0x}".format(CIPHERTEXT))
        else:
            if self.mode == "MODE_CFB8":
                PLAINTEXT = AES_CFB5.decryptCFB8(self.keysize,self.key,self.iv,self.ciphertext)
            else:
                PLAINTEXT = AES_CFB5.decryptCFB128(self.keysize,self.key,self.iv,self.ciphertext)
            try:
                assert self.plaintext == PLAINTEXT
                counterOK += 1
                printTestCase("OK")
            except AssertionError:
                counterNOK +=1
                print(self.basename,end=" ")
                printTestCase("failed")
                print("Expected plaintext={0:0x}".format(self.plaintext))
                print("Returned plaintext={0:0x}".format(PLAINTEXT))

if __name__ == '__main__': 
    path = os.path.dirname(__file__)
    files = sys.argv[1:]
    if not files:
        files = glob(os.path.join(path,'KAT_AES','*.rsp'))
        files.sort()
    for file in files:
        AEStester().buildTestCases(file)
    print("Files tested={0:d}".format(noFilesTested))
    print("Files skipped={0:d}".format(noFilesSkipped))
    print("Test cases OK={0:d}".format(counterOK))
    print("Test cases NOK={0:d}".format(counterNOK))

This program, when executed without arguments, will generate the following report:

Type=GFSbox Mode=CFB128 Keysize=128 Function=ENCRYPT Count=000 OK
Type=GFSbox Mode=CFB128 Keysize=128 Function=ENCRYPT Count=001 OK
Type=GFSbox Mode=CFB128 Keysize=128 Function=ENCRYPT Count=002 OK
Type=GFSbox Mode=CFB128 Keysize=128 Function=ENCRYPT Count=003 OK
Type=GFSbox Mode=CFB128 Keysize=128 Function=ENCRYPT Count=004 OK

... 4,146 test cases omitted

Type=VarTxt Mode=CFB8 Keysize=256 Function=DECRYPT Count=123 OK
Type=VarTxt Mode=CFB8 Keysize=256 Function=DECRYPT Count=124 OK
Type=VarTxt Mode=CFB8 Keysize=256 Function=DECRYPT Count=125 OK
Type=VarTxt Mode=CFB8 Keysize=256 Function=DECRYPT Count=126 OK
Type=VarTxt Mode=CFB8 Keysize=256 Function=DECRYPT Count=127 OK
Files tested=24
Files skipped=48
Test cases OK=4156
Test cases NOK=0

Validation of an AES implementation in Python 3

Posted on June 3, 2013 by JHAF

The Cryptographic Algorithm Validation Program (CAVP) defines validation testing for cryptographic algorithms approved by the US National Institute of Standards and Technology (NIST). All of the tests under CAVP, established by NIST and its Canadian counterpart (CSEC) in 1995, are handled by accredited third-party laboratories.

To assist prospective vendors in checking their implementations, NIST provides electronic versions of the vectors for the Known Answer Test (KAT) for the three NIST-approved symmetric cryptographic algorithms: AES, Triple-DES, and Skipjack. Also available are sample values for the Monte Carlo (MCT) test and the Multiblock Message (MMT) test for the same algorithms, thus completing the set of tests a cryptographic implementation (dubbed “Implementation Under Test”) will face during a formal validation. A detailed account of the procedures involved in validating AES implementations can be found in the NIST document The Advanced Encryption Standard Algorithm Validation Suite (AESAVS).

The NIST KAT validation suite for AES contains 72 files describing test vectors for different AES modes of operation: ECB (Electronic Codebook), CBC (Cipher Block Chaining), CFB (Cipher Feedback) and OFB (Output Feedback). Besides this partition, there are also separated tests for AES encryption and decryption, exemplified by the abridged contents of the file ECBKeySbox128.rsp (see below).

# CAVS 11.1
# Config info for aes_values
# AESVS KeySbox test data for ECB
# State : Encrypt and Decrypt
# Key Length : 128
# Generated on Fri Apr 22 15:11:26 2011

[ENCRYPT]

COUNT = 0
KEY = 10a58869d74be5a374cf867cfb473859
PLAINTEXT = 00000000000000000000000000000000
CIPHERTEXT = 6d251e6944b051e04eaa6fb4dbf78465

COUNT = 1
KEY = caea65cdbb75e9169ecd22ebe6e54675
PLAINTEXT = 00000000000000000000000000000000
CIPHERTEXT = 6e29201190152df4ee058139def610bb

... (18 test cases omitted)

[DECRYPT]

COUNT = 0
KEY = 10a58869d74be5a374cf867cfb473859
CIPHERTEXT = 6d251e6944b051e04eaa6fb4dbf78465
PLAINTEXT = 00000000000000000000000000000000

COUNT = 1
KEY = caea65cdbb75e9169ecd22ebe6e54675
CIPHERTEXT = 6e29201190152df4ee058139def610bb
PLAINTEXT = 00000000000000000000000000000000

... (18 test cases omitted)

These vectors can be used to informally verify the correctness of an AES implementation, such as the one presented below, which successfully passed all 4,156 KAT tests involving ECB and CBC modes. This Python code differs from the one already presented in a previous blog only with respect to the input/output types accepted: if the input plaintext (ciphertext) is of integer type, so will be the correspondent ciphertext (plaintext) output. This feature simplifies validation testing, since the integer plaintexts and ciphertexts usually employed in those scenarios can be deal with directly without any type conversion.

#!/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 Python program below extracts data from the files contained in the KAT_AES directory, then builds the test cases and finally executes them. Only the files applicable to ECB and CBC operation modes (the modes supported by this AES implementation) are considered.

#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: Validation of an AES implementation in Python
#
# Date: 2013-06-02
#
# License: Attribution-NonCommercial-ShareAlike 3.0 Unported
#          (CC BY-NC-SA 3.0)
#===========================================================

import os,sys,re
from functools import reduce
from glob import glob
import sundAES

# Global counters
noFilesTested = noFilesSkipped = 0
counterOK = counterNOK = 0

class AEStester:
    """"""
    def buildTestCases(self,filename):
        """Build test cases described in a given file"""
        global noFilesTested,noFilesSkipped

        self.basename = os.path.basename(filename)
        if self.basename.startswith('ECB'):
            self.mode = "MODE_ECB"
            noFilesTested += 1
        elif self.basename.startswith('CBC'):
            self.mode = "MODE_CBC"
            noFilesTested += 1
        else:
            noFilesSkipped += 1
            return

        digits = re.search("\d{3}",self.basename)
        self.keysize = 'SIZE_' + digits.group()
        result = re.search("CFB\d*(\D{6,})\d{3}",self.basename)
        if result != None:
            self.typeTest = result.group(1)
        self.typeTest = re.search("\w{3}(\D{6,})\d{3}",self.basename).group(1)
        self.iv = None
        for line in open(filename):
            line = line.strip()
            if (line == "") or line.startswith('#'):
                continue
            elif line == '[ENCRYPT]':
                self.operation = 'encrypt'
                continue
            elif line == '[DECRYPT]':
                self.operation = 'decrypt'
                continue
            param,_,value = line.split(' ',2)
            if param == "COUNT":
                self.count = int(value)
                continue
            else:
                self.__setattr__(param.lower(),int(value,16))
                if (self.operation == 'encrypt') and (param == "CIPHERTEXT") or \
                   (self.operation == 'decrypt' and param == "PLAINTEXT"):
                    self.runTestCase()

    def runTestCase(self):
        """Execute test case and report result"""
        global counterOK,counterNOK

        def printTestCase(result):
            print("Type={0:s} Mode={1:s} Keysize={2:s} Function={3:s} Count={4:03d} {5:s}"\
                  .format(self.typeTest,self.mode[5:],\
                          self.keysize[5:],self.operation.upper(),\
                          self.count,result))

        obj = sundAES3.AES(self.mode)
        obj.setKey(self.keysize,self.key,self.iv)
        if self.operation == 'encrypt':
            CIPHERTEXT = obj.encrypt(self.plaintext)
            try:
                assert self.ciphertext == CIPHERTEXT
                counterOK += 1
                printTestCase("OK")
            except AssertionError:
                counterNOK +=1
                print(self.basename)
                printTestCase("failed")
                print("Expected ciphertext={0:0x}".format(self.ciphertext))
                print("Returned ciphertext={0:0x}".format(CIPHERTEXT))
        else:
            PLAINTEXT = obj.decrypt(self.ciphertext)
            try:
                assert self.plaintext == PLAINTEXT
                counterOK += 1
                printTestCase("OK")
            except AssertionError:
                counterNOK +=1
                print(self.basename)
                printTestCase("failed")
                print("Expected plaintext={0:0x}".format(self.plaintext))
                print("Returned plaintext={0:0x}".format(PLAINTEXT))

# Main program
path = os.path.dirname(__file__)
files = sys.argv[1:]
if not files:
    files = glob(os.path.join(path,'KAT_AES','*.rsp'))
    files.sort()
for file in files:
    AEStester().buildTestCases(file)
print("Files tested={0:d}".format(noFilesTested))
print("Files skipped={0:d}".format(noFilesSkipped))
print("Test cases OK={0:d}".format(counterOK))
print("Test cases NOK={0:d}".format(counterNOK))

Executed without arguments, this program will apply all ECB and CBC tests described in the files against the AES implementation, producing the following output:

Type=GFSbox Mode=CBC Keysize=128 Function=ENCRYPT Count=000 OK
Type=GFSbox Mode=CBC Keysize=128 Function=ENCRYPT Count=001 OK
Type=GFSbox Mode=CBC Keysize=128 Function=ENCRYPT Count=002 OK
Type=GFSbox Mode=CBC Keysize=128 Function=ENCRYPT Count=003 OK
Type=GFSbox Mode=CBC Keysize=128 Function=ENCRYPT Count=004 OK

... (4,147 lines omitted)

Type=VarTxt Mode=ECB Keysize=256 Function=DECRYPT Count=124 OK
Type=VarTxt Mode=ECB Keysize=256 Function=DECRYPT Count=125 OK
Type=VarTxt Mode=ECB Keysize=256 Function=DECRYPT Count=126 OK
Type=VarTxt Mode=ECB Keysize=256 Function=DECRYPT Count=127 OK
Files tested=24
Files skipped=48
Test cases OK=4156
Test cases NOK=0

If, however, this program is run with one or more files in the KAT_AES directory as argument(s), it will instead build and execute the tests contained in the indicated file(s).

AES-GCM implementation in Python 3

Posted on May 31, 2013 by JHAF

Galois/Counter Mode (GCM) is a mode of operation for symmetric key cryptographic block ciphers that provides authenticated encryption.

Proposed by David McGrew and John Viega in 2005, GCM is suited for high-speed secure computing and communication. Acknowledging this fact, the US National Institute of Standards and Technology (NIST) standardized GCM and its companion algorithm, Galois Message Authentication Code (GMAC), in 2007. The latter is an authentication-only variant of GCM which can be used as an incremental message authentication code (MAC). AES-GCM (the Advanced Encryption Algorithm operating in Galois/Counter Mode) has also been included in NSA Suite B Cryptography.

GCM’s confidentiality service is based on a variation of the Counter mode (CTR) while its authenticity assurance relies on a universal hash function defined over the binary Galois field $GF(2^{128})/x^{128}+x^7+x^2+x+1$ .

GCM is defined for block ciphers with block sizes of 128, 192, and 256 bits (AES uses 128-bit blocks). Both GCM and GMAC can accept initialization vectors (IVs) of arbitrary length (AES and other symmetric ciphers, on the other hand, require IVs to be of the same size as the cipher’s block size).

Its interesting to note that Intel high-end CPUs support a special instruction, PCLMULQDQ, that computes the 128-bit product (the carry-less multiplication) of two 64-bit operands. This instruction can be used as a building block to perform the carry-less multiplication of two 128-bit operands required by GCM. The other step in GCM is reduction modulo the irreducible polynomial $x^{128}+x^7+x^2+x+1$ , an operation that takes advantage of the PSRLD, PSLLD and PSHUFD instructions. Together with Intel’s Advanced Encryption Standard Instructions (AES-NI), these instructions allow GCM to offer authenticated encryption services at very high rates without using hardware-based solutions (e.g. FPGAs or ASICs). According to Intel, “an AES-GCM implementation based on the AES-NI and PCLMULQDQ instructions delivered a 400% throughput performance gain when compared to a non-AES-NI enabled software solution on the same platform.”

The Python code below implements AES-GCM using the AES implementation already presented and supports the three key sizes used by AES (128, 192 and 256 bits). All eighteen test cases proposed by McGrew & Viega were used to validate this implementation. Please note that this code is not of production quality.

#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: AES-GCM (Galois Counter/Mode) implementation
#              in Python 3
#
# Date: 2013-05-30
#
# License: Attribution-NonCommercial-ShareAlike 3.0 Unported
#          (CC BY-NC-SA 3.0)
#================================================================

import pyAES
from functools import reduce

def xor(x,y):
    """Returns the exclusive or (xor) between two vectors"""
    return bytes(i^j for i,j in zip(x,y))

def intToList(number,listSize):
    """Convert a number into a byte list""" 
    return [(number >> i) & 0xff
            for i in reversed(range(0,listSize*8,8))]

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

def GHASH (hkey,aad,ctext):
    """GCM's GHASH function"""
    def xorMultH (p,q):
        """Multiply (p^q) by hash key"""
        def multGF2(x,y):
            """Multiply two polynomials in GF(2^m)/g(w)
               g(w) = w^128 + w^7 + w^2 + w + 1
               (operands and result bits reflected)"""      
            (x,y) = map(lambda z:listToInt(list(z)),(x,y))
            z = 0
            while y & ((1<<128)-1):
                if y & (1<<127):
                    z ^= x
                y <<= 1
                if x & 1:
                    x = (x>>1)^(0xe1<<120)
                else:
                    x >>= 1
            return bytes(intToList(z,16))

        return bytes(multGF2(hkey,xor(p,q)))
    
    def gLen(s):
        """Evaluate length of input in bits and returns
           it in the LSB bytes of a 64-bit string"""
        return bytes(intToList(len(s)*8,8))  
  
    x = bytes(16)    
    aadP = aad + bytes((16-len(aad)%16)%16)
    ctextP = ctext + bytes((16-len(ctext)%16)%16)
    for i in range(0,len(aadP),16):
        x = xorMultH(x,aadP[i:i+16])
    for i in range(0,len(ctextP),16):
        x = xorMultH(x,ctextP[i:i+16])
    return xorMultH(x,gLen(aad) + gLen(ctext))

def GCM_crypt(keysize,key,iv,input,aad):
    """GCM's Authenticated Encryption/Decryption Operations"""
    def incr(m):
        """Increment the LSB 32 bits of input counter"""
        n = list(m)
        n12 = bytes(n[:12])
        ctr = listToInt(n[12:])
        if ctr == (1<<32)-1:
            return n12 + bytes(4)
        else:
            return n12 + bytes(intToList(ctr+1,4))
       
    obj = pyAES.AES('MODE_ECB')
    obj.setKey(keysize,key)    
    h = bytes(obj.encrypt(bytes(16)))
    output = bytes()
    L = len(input)
    if len(iv) == 12:
        y0 = bytes(iv) + bytes(b'\x00\x00\x00\x01')
    else:
        y0 = bytes(GHASH(h,bytes(),iv))
    y = y0
    for i in range(0,len(input),16):
        y = incr(y)
        ctextBlock = xor(bytes(obj.encrypt(y)),
                         input[i:min(i+16,L)])
        output += bytes(ctextBlock)
    g = obj.encrypt(y0)
    tag = xor(GHASH(h,aad,output),g)
    return output,tag,g,h
 
def GCM_encrypt(keysize,key,iv,ptext,aad):
    """GCM's Authenticated Encryption Operation"""
    (ctext,tag,g,h) = GCM_crypt(keysize,key,iv,ptext,aad)
    return ctext,xor(GHASH(h,aad,ctext),g)

def GCM_decrypt(keysize,key,iv,ctext,aad,tag):
    """GCM's Authenticated Decryption Operation"""
    (ptext,_,g,h) = GCM_crypt(keysize,key,iv,ctext,aad)
    if tag == xor(GHASH(h,aad,ctext),g):
        return True,ptext
    else:
        return False,None

######################## Testing section ########################

if __name__ == '__main__':

    def printHex(s):
        """Prints a bytes string in hex format"""
        print('{0:#0x}'.format(bytesToInt(s)))
    
    def bytesToInt(b):
        """Converts a bytes string into an integer"""
        return listToInt(list(b))
    
    def listToInt(list):
        """Convert a byte list into a number""" 
        return reduce(lambda x,y:(x<<8)+y,list)
    
    def checkTestVector(id,keysize,key,ptext,aad,iv,ctext,tag):
        def intToBytes(n):
            """Converts an integer into a bytes string"""
            lst = []
            while n:
                lst.append(n&0xff)
                n >>= 8
            return bytes(reversed(lst))

        def convertType(v):
            """Convert input variable type to bytes"""
            if type(v) is int:
                return intToBytes(v)
            elif type(v) is bytes:
                return v
            else:
                return bytes(v,'ISO-8859-1')

        def printOutputs():
            """Prints expected/evaluated tags and
                      expected/evaluated ciphertexts"""
            print("Tag expected:  ", end="")
            printHex(tag)
            print("Tag evaluated: ", end="")
            printHex(TAG)
            print("Ciphertext expected:  ", end="")
            printHex(ctext)
            print("Ciphertext evaluated: ", end="")
            printHex(CTEXT)            
          
        (ptext,aad,iv,ctext,tag) = map(convertType,(ptext,aad,iv,ctext,tag))
        (CTEXT,TAG) = GCM_encrypt(keysize,key,iv,ptext,aad)
        (SUCCESS,PTEXT) = GCM_decrypt(keysize,key,iv,CTEXT,aad,TAG)
    
        try:
            assert SUCCESS & (CTEXT == ctext) & (TAG == tag)
            print("Test case {0:0d} succeeded".format(id))
        except AssertionError:
            print("Test case {0:0d} failed".format(id))
            printOutputs()           
    
    # Test cases extracted from
    # "The Galois/Counter Mode of Operation(GCM)", McGrew & Viega, 2005 (http://goo.gl/DWJPK)
    
    # Some useful constants
    emptyString = bytes() # zero length bit string
    nullBitString128 = bytes(16) # 128-bit null string 
    nullBitString96 = bytes(12) # 96-bit null IV
    
    # Test Case #1
    testcase1 = {'id':1,'keysize':"SIZE_128",'key':0x0,'ptext':emptyString,
                 'aad':emptyString,'iv':nullBitString96,'ctext':emptyString,
                 'tag':0x58e2fccefa7e3061367f1d57a4e7455a}
    
    # Test Case #2
    testcase2 = {'id':2,'keysize':"SIZE_128",'key':0x0,'ptext':nullBitString128,
                 'aad':emptyString,'iv':nullBitString96,'ctext':0x0388dace60b6a392f328c2b971b2fe78,
                 'tag':0xab6e47d42cec13bdf53a67b21257bddf}
    
    # Test Case #3
    testcase3 = {'id':3,'keysize':"SIZE_128",'key':0xfeffe9928665731c6d6a8f9467308308,
                 'ptext':0xd9313225f88406e5a55909c5aff5269a86a7a9531534f7da2e4c303d8a318a721c3c0c95956809532fcf0e2449a6b525b16aedf5aa0de657ba637b391aafd255,
                 'aad':emptyString,'iv':0xcafebabefacedbaddecaf888,
                 'ctext':0x42831ec2217774244b7221b784d0d49ce3aa212f2c02a4e035c17e2329aca12e21d514b25466931c7d8f6a5aac84aa051ba30b396a0aac973d58e091473f5985,
                 'tag':0x4d5c2af327cd64a62cf35abd2ba6fab4}
    
    ## Test Case #4
    testcase4 = {'id':4,'keysize':"SIZE_128",'key':0xfeffe9928665731c6d6a8f9467308308,
                 'ptext':0xd9313225f88406e5a55909c5aff5269a86a7a9531534f7da2e4c303d8a318a721c3c0c95956809532fcf0e2449a6b525b16aedf5aa0de657ba637b39,
                 'aad':0xfeedfacedeadbeeffeedfacedeadbeefabaddad2,'iv':0xcafebabefacedbaddecaf888,
                 'ctext':0x42831ec2217774244b7221b784d0d49ce3aa212f2c02a4e035c17e2329aca12e21d514b25466931c7d8f6a5aac84aa051ba30b396a0aac973d58e091,
                 'tag':0x5bc94fbc3221a5db94fae95ae7121a47}

    ## Test Case #5
    testcase5 = {'id':5,'keysize':"SIZE_128",'key':0xfeffe9928665731c6d6a8f9467308308,
                 'ptext':0xd9313225f88406e5a55909c5aff5269a86a7a9531534f7da2e4c303d8a318a721c3c0c95956809532fcf0e2449a6b525b16aedf5aa0de657ba637b39,
                 'aad':0xfeedfacedeadbeeffeedfacedeadbeefabaddad2,'iv':0xcafebabefacedbad,
                 'ctext':0x61353b4c2806934a777ff51fa22a4755699b2a714fcdc6f83766e5f97b6c742373806900e49f24b22b097544d4896b424989b5e1ebac0f07c23f4598,
                 'tag':0x3612d2e79e3b0785561be14aaca2fccb}

    ## Test Case #6
    testcase6 = {'id':6,'keysize':"SIZE_128",'key':0xfeffe9928665731c6d6a8f9467308308,
                 'ptext':0xd9313225f88406e5a55909c5aff5269a86a7a9531534f7da2e4c303d8a318a721c3c0c95956809532fcf0e2449a6b525b16aedf5aa0de657ba637b39,
                 'aad':0xfeedfacedeadbeeffeedfacedeadbeefabaddad2,
                 'iv':0x09313225df88406e555909c5aff5269aa6a7a9538534f7da1e4c303d2a318a728c3c0c95156809539fcf0e2429a6b525416aedbf5a0de6a57a637b39b,
                 'ctext':0x8ce24998625615b603a033aca13fb894be9112a5c3a211a8ba262a3cca7e2ca701e4a9a4fba43c90ccdcb281d48c7c6fd62875d2aca417034c34aee5,
                 'tag':0x619cc5aefffe0bfa462af43c1699d050}
        
    ## Test Case #7
    testcase7 = {'id':7,'keysize':"SIZE_192",'key':0x0,'ptext':emptyString,
                 'aad':emptyString,'iv':nullBitString96,'ctext':emptyString,
                 'tag':0xcd33b28ac773f74ba00ed1f312572435}
   
    ## Test Case #8
    testcase8 = {'id':8,'keysize':"SIZE_192",'key':0x0,'ptext':nullBitString128,
                 'aad':emptyString,'iv':nullBitString96,
                 'ctext':0x98e7247c07f0fe411c267e4384b0f600,
                 'tag':0x2ff58d80033927ab8ef4d4587514f0fb}

    ## Test Case #9
    testcase9 = {'id':9,'keysize':"SIZE_192",'key':0xfeffe9928665731c6d6a8f9467308308feffe9928665731c,
                 'ptext':0xd9313225f88406e5a55909c5aff5269a86a7a9531534f7da2e4c303d8a318a721c3c0c95956809532fcf0e2449a6b525b16aedf5aa0de657ba637b391aafd255,
                 'aad':emptyString,'iv':0xcafebabefacedbaddecaf888,
                 'ctext':0x3980ca0b3c00e841eb06fac4872a2757859e1ceaa6efd984628593b40ca1e19c7d773d00c144c525ac619d18c84a3f4718e2448b2fe324d9ccda2710acade256,
                 'tag':0x9924a7c8587336bfb118024db8674a14}
                   
    ## Test Case #10
    testcase10 = {'id':10,'keysize':"SIZE_192",'key':0xfeffe9928665731c6d6a8f9467308308feffe9928665731c,
                  'ptext':0xd9313225f88406e5a55909c5aff5269a86a7a9531534f7da2e4c303d8a318a721c3c0c95956809532fcf0e2449a6b525b16aedf5aa0de657ba637b39,
                  'aad':0xfeedfacedeadbeeffeedfacedeadbeefabaddad2,'iv':0xcafebabefacedbaddecaf888,
                  'ctext':0x3980ca0b3c00e841eb06fac4872a2757859e1ceaa6efd984628593b40ca1e19c7d773d00c144c525ac619d18c84a3f4718e2448b2fe324d9ccda2710,
                  'tag':0x2519498e80f1478f37ba55bd6d27618c}
                                    
    ## Test Case #11
    testcase11 = {'id':11,'keysize':"SIZE_192",'key':0xfeffe9928665731c6d6a8f9467308308feffe9928665731c,
                  'ptext':0xd9313225f88406e5a55909c5aff5269a86a7a9531534f7da2e4c303d8a318a721c3c0c95956809532fcf0e2449a6b525b16aedf5aa0de657ba637b39,
                  'aad':0xfeedfacedeadbeeffeedfacedeadbeefabaddad2,'iv':0xcafebabefacedbad,
                  'ctext':0x0f10f599ae14a154ed24b36e25324db8c566632ef2bbb34f8347280fc4507057fddc29df9a471f75c66541d4d4dad1c9e93a19a58e8b473fa0f062f7,
                  'tag':0x65dcc57fcf623a24094fcca40d3533f8}
                                                    
    ## Test Case #12
    testcase12 = {'id':12,'keysize':"SIZE_192",'key':0xfeffe9928665731c6d6a8f9467308308feffe9928665731c,
                  'ptext':0xd9313225f88406e5a55909c5aff5269a86a7a9531534f7da2e4c303d8a318a721c3c0c95956809532fcf0e2449a6b525b16aedf5aa0de657ba637b39,
                  'aad':0xfeedfacedeadbeeffeedfacedeadbeefabaddad2,
                  'iv':0x9313225df88406e555909c5aff5269aa6a7a9538534f7da1e4c303d2a318a728c3c0c95156809539fcf0e2429a6b525416aedbf5a0de6a57a637b39b,
                  'ctext':0xd27e88681ce3243c4830165a8fdcf9ff1de9a1d8e6b447ef6ef7b79828666e4581e79012af34ddd9e2f037589b292db3e67c036745fa22e7e9b7373b,
                  'tag':0xdcf566ff291c25bbb8568fc3d376a6d9}

    ## Test Case #13
    testcase13 = {'id':13,'keysize':"SIZE_256",'key':0x0,'ptext':emptyString,
                  'aad':emptyString,'iv':nullBitString96,'ctext':emptyString,
                  'tag':0x530f8afbc74536b9a963b4f1c4cb738b}

    ## Test Case #14
    testcase14 = {'id':14,'keysize':"SIZE_256",'key':0x0,'ptext':nullBitString128,
                   'aad':emptyString,'iv':nullBitString96,'ctext':0xcea7403d4d606b6e074ec5d3baf39d18,
                   'tag':0xd0d1c8a799996bf0265b98b5d48ab919}             

    ## Test Case #15
    testcase15 = {'id':15,'keysize':"SIZE_256",'key':0xfeffe9928665731c6d6a8f9467308308feffe9928665731c6d6a8f9467308308,
                  'ptext':0xd9313225f88406e5a55909c5aff5269a86a7a9531534f7da2e4c303d8a318a721c3c0c95956809532fcf0e2449a6b525b16aedf5aa0de657ba637b391aafd255,
                  'aad':emptyString,'iv':0xcafebabefacedbaddecaf888,
                  'ctext':0x522dc1f099567d07f47f37a32a84427d643a8cdcbfe5c0c97598a2bd2555d1aa8cb08e48590dbb3da7b08b1056828838c5f61e6393ba7a0abcc9f662898015ad,
                  'tag':0xb094dac5d93471bdec1a502270e3cc6c}

    ## Test Case #16
    testcase16 = {'id':16,'keysize':"SIZE_256",'key':0xfeffe9928665731c6d6a8f9467308308feffe9928665731c6d6a8f9467308308,
                  'ptext':0xd9313225f88406e5a55909c5aff5269a86a7a9531534f7da2e4c303d8a318a721c3c0c95956809532fcf0e2449a6b525b16aedf5aa0de657ba637b39,
                  'aad':0xfeedfacedeadbeeffeedfacedeadbeefabaddad2,'iv':0xcafebabefacedbaddecaf888,
                  'ctext':0x522dc1f099567d07f47f37a32a84427d643a8cdcbfe5c0c97598a2bd2555d1aa8cb08e48590dbb3da7b08b1056828838c5f61e6393ba7a0abcc9f662,
                  'tag':0x76fc6ece0f4e1768cddf8853bb2d551b}

    ## Test Case #17
    testcase17 = {'id':17,'keysize':"SIZE_256",'key':0xfeffe9928665731c6d6a8f9467308308feffe9928665731c6d6a8f9467308308,
                  'ptext':0xd9313225f88406e5a55909c5aff5269a86a7a9531534f7da2e4c303d8a318a721c3c0c95956809532fcf0e2449a6b525b16aedf5aa0de657ba637b39,
                  'aad':0xfeedfacedeadbeeffeedfacedeadbeefabaddad2,'iv':0xcafebabefacedbad,
                  'ctext':0xc3762df1ca787d32ae47c13bf19844cbaf1ae14d0b976afac52ff7d79bba9de0feb582d33934a4f0954cc2363bc73f7862ac430e64abe499f47c9b1f,
                  'tag':0x3a337dbf46a792c45e454913fe2ea8f2} 

    ## Test Case #18
    testcase18 = {'id':18,'keysize':"SIZE_256",'key':0xfeffe9928665731c6d6a8f9467308308feffe9928665731c6d6a8f9467308308,
                  'ptext':0xd9313225f88406e5a55909c5aff5269a86a7a9531534f7da2e4c303d8a318a721c3c0c95956809532fcf0e2449a6b525b16aedf5aa0de657ba637b39,
                  'aad':0xfeedfacedeadbeeffeedfacedeadbeefabaddad2,
                  'iv':0x9313225df88406e555909c5aff5269aa6a7a9538534f7da1e4c303d2a318a728c3c0c95156809539fcf0e2429a6b525416aedbf5a0de6a57a637b39b,
                  'ctext':0x5a8def2f0c9e53f1f75d7853659e2a20eeb2b22aafde6419a058ab4f6f746bf40fc0c3b780f244452da3ebf1c5d82cdea2418997200ef82e44ae7e3f,
                  'tag':0xa44a8266ee1c8eb0c8b5d4cf5ae9f19a}
                  
    for i in range(1,19):    
        checkTestVector(**(eval("testcase" + str(i))))

Fast Fourier Transform in Haskell

Posted on March 28, 2013 by JHAF

The Discrete Fourier Transform (DFT) converts a finite list of equally-spaced samples of a function into the list of coefficients of a finite combination of complex sinusoids, ordered by their frequencies, that has those same sample values.

The DFT is used to perform Fourier analysis in different applications like digital signal processing, polynomial multiplication, partial differential equations solving, large integers multiplication etc. It has also been used in statistical tests of random and pseudorandom number generators for cryptographic applications (see NIST Special Publication 800-22).

The Haskell function dft (shown below) evaluates the DFT for any number of points. Since the vectors $[e^{2{\pi}kn/N} | n = 0,1..N-1]$ constitute an orthogonal basis over the set of N-dimensional complex vectors, the inverse DFT can be calculated by the same algorithm using the complex conjugate vectors (see function idft). In order to make the forward and the inverse transforms unitary, a normalization factor equal to $\sqrt{1/N}$ is used in both functions.

-------------------------------------------------------------
--
-- Author: Joao H de A Franco (jhafranco@acm.org)
--
-- Description: DFT implementation in Haskell
--
-- Date: 2013-Mar-28
--
-- License: Attribution-NonCommercial-ShareAlike 3.0 Unported
--          (CC BY-NC-SA 3.0)
--
-------------------------------------------------------------
module Aux.DFT (dft,idft) where
import Data.Complex (Complex((:+)))

dft, idft :: [Complex Float] -> [Complex Float]
dft = dft' 1
idft = dft' (-1)
           
dft' :: Float -> [Complex Float] -> [Complex Float]
dft' e x = let t = length x
               y = 1 / fromIntegral t
               dft'' k = let w = fromIntegral k * 2 * e * pi * y
                         in (sqrt y :+ 0) *
                             sum (zipWith (\n z -> z * exp (0 :+ n * w)) [0..] x)                         
           in map dft'' [0..t-1]

The DFT can be seen as a linear transformation where an real-valued N-tuple is multiplied by an N x N matrix returning a complex-valued N-tuple. This matrix operation takes N² scalar multiplications, which makes it very expensive to deal with large data sets.

Fast Fourier Transform is the generic name given to algorithms that compute the DFT (or its inverse) faster than O(N²). The most commonly used FFT algorithm is due to Cooley & Tukey (1965), a “divide and conquer” procedure that recursively breaks down a DFT of any composite size N = N1 * N2 into many smaller DFTs of sizes N1 and N2. The Cooley-Tukey and other FFTs schemes reduce the algorithm complexity from O(N²) to O(N log N).

The advent of FFT algorithms has revolutionized the use of the Discrete Fourier Transform, making it possible to use it on a variety of areas: applied mechanics, biomedical engineering, communications, electromagnetics, finance, instrumentation, numerical methods, radar, signal processing, sonics and acoustics etc.

It’s interesting to note, however, that the general idea behind the FFT algorithms was invented by Carl Friedrich Gauss (“The Prince of Mathematicians”) around 1805, when he was calculating the orbit of an asteroid. Amazing!

The Cooley–Tukey algorithm is usually employed to recursively divide a N-point transform into two N/2-point transforms and for this reason it is limited to cases where N is a power of two. The Haskell code below implements this technique, called decimation-in-time radix-2 (fft implements the forward transform and ifft the inverse one).

-------------------------------------------------------------
--
-- Author: Joao H de A Franco (jhafranco@acm.org)
--
-- Description: FFT implementation in Haskell
--
-- Date: 2013-Mar-28
--
-- License: Attribution-NonCommercial-ShareAlike 3.0 Unported
--          (CC BY-NC-SA 3.0)
--
-------------------------------------------------------------
module Aux.FFT (fft,ifft) where
import Data.Complex(Complex((:+)))

fft, ifft :: [Complex Float] -> [Complex Float]
fft = fft' 1
ifft = fft' (-1)

fft' :: Float -> [Complex Float] -> [Complex Float]
fft' e xs = if pow2 (length xs) 
            then let z = sqrt (1 / fromIntegral (length xs))
                  in map ((z :+ 0) *) $ fft'' e xs
            else error "Number of points is not a power of 2"
            where pow2 n
                     | n == 1 || n == 2 = True
                     | otherwise = n `mod` 2 == 0 && pow2 (n `div` 2)

fft'' :: Float -> [Complex Float] -> [Complex Float]
fft'' _ [] = []
fft'' _ [x] = [x]
fft'' e xs = fft'' e (evens xs) <+> t (fft'' e (odds xs))
  where (<+>) r s = zipWith (+) (r ++ r) (s ++ map negate s)
        evens [] = []
        evens [u] = [u]
        evens (v:_:vs) = v:evens vs
        odds = evens . drop 1
        n = 2 * pi / fromIntegral (length xs)
        t = zipWith (\k z -> z * exp (0 :+ k * n * e)) ([0..] :: [Float])

Besides classic references on this subject such as Brigham’s and Bracewell’s books, I recommend the excellent lectures on The Fourier Transforms and Its Applications (EE261) by Prof. Brad Osgood from Stanford University. As a matter of fact, I’ve watched only lectures 20 to 22, as they cover DFT and the basics of FFT algorithms, but most probably the remaining lectures should be equally good. Extensive course materials (syllabus, handouts, past exams, exercises & solutions) are available.

The box below shows some simple tests to check the correctness of the above implementations.

-------------------------------------------------------------
--
-- Author: Joao H de A Franco (jhafranco@acm.org)
--
-- Description: Test module for FFT implementation in Haskell
--
-- Date: 2013-Mar-28
--
-- License: Attribution-NonCommercial-ShareAlike 3.0 Unported
--          (CC BY-NC-SA 3.0)
--
-------------------------------------------------------------
module Main where
import Data.Complex (Complex((:+)),realPart,imagPart)
import Aux.DFT (dft,idft)
import Aux.FFT (fft,ifft)

main :: IO ()
main = print (if test1 && test2 && test3 then "ok" else "nok")

-- 7-point DFT (prime number) compared to Mathematica's evaluation
test1 :: Bool
test1 = let mathematica1 = [3.40168 :+ 0, (-0.566947) :+ 0.564962,
                            (-0.566947) :+ (-1.41899), (-0.566947) :+ 0.645967,
                            (-0.566947) :+ (-0.645967), (-0.566947) :+ 1.41899,
                            (-0.566947) :+ (-0.564962)]
        in map (roundComplex 3 0.001) (dft [0,1,2,3,0,1,2]) == 
           map (roundComplex 3 0.001) mathematica1

-- 8-point FFT (power of 2) compared to Mathematica's evaluation
test2 :: Bool
test2 = let mathematica2 = [4.24264 :+ 0, 0 :+ 0,
                            (-1.41421) :+ (-1.41421), 0 :+ 0, 
                            (-1.41421) :+ 0, 0 :+ 0,
                            (-1.41421) :+ 1.41421, 0 :+ 0]
        in map (roundComplex 3 0.001) (fft [0,1,2,3,0,1,2,3]) == 
           map (roundComplex 3 0.001) mathematica2

-- 512-point DFT compared to FFT
test3 :: Bool
test3 = let list = take 512 $ cycle ([0,1,2,3] :: [Complex Float])
            z1 = map (roundComplex 2 0.001) $ dft list
            z2 = map (roundComplex 2 0.001) $ fft list
         in z1 == z2

-- 128-point time-shifted impulse forward & inverse DFT (auto-test)
test4 :: Bool
test4 = all (==True) t4
        where t4 = do
              n <- [0..127]
              let x = impulse n 128 :: [Complex Float]
              return $ map (roundComplex 3 0.001) (idft (dft x)) == x

-- 1024-point time-shifted impulse forward & inverse FFT (auto-test)         
test5 :: Bool
test5 = all (==True) t5
        where t4 = do
              n <- [0..1023]
              let x = impulse n 1024 :: [Complex Float]
              return $ map (roundComplex 3 0.001) (ifft (fft x)) == x

-- Discrete Dirac delta generator
impulse :: Num a => Int -> Int -> [a]
impulse n m = replicate n 0 ++ 1:replicate (m - n - 1) 0

-- Rounding function
roundComplex :: Int -> Float -> Complex Float -> Complex Float
roundComplex n e x = let zeroFloat e' f = if abs f < e' then 0 else f
                         trim = roundFloat n . zeroFloat e
                         roundFloat m y = fromIntegral (round $ y * 10 ^ m :: Int) / 10 ^^ m
                     in trim (realPart x) :+ trim (imagPart x)

You can run the above FFT script to evaluate the forward and inverse FFT for a small data set using the facilities provided by Codepad.org, an online compiler/interpreter for Haskell and other languages.

A quick benchmark shows the speed-up achieved by the radix-2 FFT over the classic DFT: 18 ms vs. 2.5 s for 4,096 points (two orders of magnitude!). FFTW, a C subroutine library for computing the DFT in one or more dimensions, is much faster, as it takes only 0.7 ms for processing 4,096 points on the same Linux system.

RC4 coded in Haskell

Posted on February 22, 2013 by JHAF

After using Python in some small projects, my attention turned to a much more attractive language, Haskell. Haskell is a functional programming language with non-strict (“lazy”) semantics and strong static typing. It is relatively new (1990) and surprisingly well-defined, despite being created by a committee. The most popular Haskell compiler & interpreter, GHC (the Glasgow Haskell Compiler), is open-source software, available for Windows, Mac and Linux platforms.

The language is named after Haskell Brooks Curry, whose work in mathematical logic serves as a foundation for functional languages. Haskell and other functional languages are based on the lambda calculus which, according to the Church–Turing thesis, is as powerful as the Turing machine (that serves as a paradigm for imperative languages like C, C++, Java and others) for expressing computable functions.

Learning how to program in Haskell has been a rewarding experience for me. At some point, it reminded myself of a famous quote by Benjamin Whorf, “language shapes the way we think and determines what we can think about.” I will comment on my learning experience in Haskell in another post. For the moment, I would like to comment about the RC4 cryptographic algorithm and its implementation in Haskell. RC4 is a remarkably simple algorithm (already coded in Python in another post), and thus the obvious choice as the first cryptographic algorithm to be coded in a new programming language.

As the next box shows [1], it is possible to code the RC4 algorithm in less than ten lines of Haskell. The resulting code, although totally functional (no pun intended), definitely does not meet software quality standards, but does really show Haskell conciseness.

module Crypto.RC4 where
import Data.Char;import Data.Array
prga=prga' 0 0 where prga' i j s=let{i'=succ i`mod`256;j'=(s!i'+j)`mod`256;
s' = swap i' j' s;t = s'!((s!i'+s!j') `mod` 256)} in chr t : prga' i' j' s'
ksa k = ksa' 0 0 $ array (0,255) [(i,i)|i<-[0..255]] where {ksa' 256 _ s=s;
ksa' i j s = let {i'= i `mod` length k; j' = (j+s!i+ord(k!!i')) `mod` 256}
in ksa' (succ i) j' (swap j' i s)}
swap i j s = if i /= j then s // [(i, s ! j), (j, s ! i)] else s

The RC4 stream cipher algorithm

RC4, a variable key-size stream cipher with byte-oriented operations, is the most widely used stream cipher algorithm. It was designed by Ronald Rivest in 1987 for RSA Data Security (now RSA Security, a division of EMC²). RC4, also known as ARC4 [2], was kept as a trade secret until 1994, when it was posted anonymously to the cypherpunks mailing list.

RC4 creates a finite-state machine that uses a state array of 256 bytes. Initially, this array is set to the identity permutation (see pseudo-code below). The next step is performed by the Key Scheduling Algorithm (KSA), which traverses the state array swapping its elements based on the key, which size can be defined anywhere in the range of 40 to 2,048 bits [3]. As soon as KSA finishes its job, the key can be discarded since its contribution has been incorporated into the state array.

The state array is then ready for the Pseudo-Random Generation Algorithm (PRGA) to generate the stream cipher that will be xor’d with the plaintext (encryption) or with the ciphertext (decryption). Every time a byte is produced, the state array is permuted once more [4].

############ RC4 pseudo-code (extracted from Wikipedia) ############

# RC4 array state initialization
for i from 0 to 255
    S[i] := i
endfor

# Key Scheduling Algorithm (KSA)
j := 0
for i from 0 to 255
    j := (j + S[i] + key[i mod keylength]) mod 256
    swap values of S[i] and S[j]
endfor

# Pseudo-Random Generation Algorithm (PRGA)
i := 0
j := 0
while GeneratingOutput:
    i := (i + 1) mod 256
    j := (j + S[i]) mod 256
    swap values of S[i] and S[j]
    K := S[(S[i] + S[j]) mod 256]
    output K
endwhile

RC4 implementation in Haskell

In the expanded version (see box below), the following aspects were changed:

An extra module, Data.Bits, was imported to support the xor operation required by the encrypt function, absent in the first program, since it is not related to the RC4 algorithm itself (its task is just to combine the keystream generated by any stream cipher with the cleartext or ciphertext digits).
Only external objects (functions, types, data and value constructors) effectively used were imported from modules Data.Char, Data.Array and Data.Bits.
All top-level functions declared were assigned type signatures (those lines containing the double-colon operator). Although the Haskell compiler can (most of time) infer types automatically, it is strongly recommended to state them explicitly to assist the compiler in generating a more efficient code and to provide a better documentation.
Curly braces and semi-colons were substituted for indentation to structure code (unlike Python, indentation is not compulsory in Haskell).
A short descriptive comment was added to the four top-level functions (encrypt, prga, ksa and swap).

-------------------------------------------------------------
--
-- Author: Joao H de A Franco (jhafranco@acm.org)
--
-- Description: RC4 implementation in Haskell
--
-- Date: 2013-Feb-22
--
-- License: Attribution-NonCommercial-ShareAlike 3.0 Unported
--          (CC BY-NC-SA 3.0)
--
-------------------------------------------------------------
module Crypto.RC4 (encrypt) where
import Data.Array (Array, array, (//), (!))
import Data.Char (chr, ord)
import Data.Bits (xor)

type ArrayRC4 = Array Int Int
type Index = Int
type Key = String
type Stream = String

-- Encrypt (or decrypt) using RC4 keystream
encrypt :: Key -> String -> String
encrypt k c = map chr $ zipWith xor (map ord (stream k)) (map ord c)
              where stream = prga . ksa

-- Pseudo-random generation algorithm (PRGA)                             
prga :: ArrayRC4 -> Stream
prga = prga' 0 0
  where prga' i j s = let i' = succ i `mod` 256
                          j' = (s ! i' + j) `mod` 256
                          s' = swap i' j' s
                          t = s' ! ((s ! i' + s ! j') `mod` 256)
                       in chr t : prga' i' j' s'

-- Key Scheduling Algorithm (KSA)
ksa :: Key -> ArrayRC4
ksa k = ksa' 0 0 $ array (0,255) [(i,i) | <- [0..255]]
  where ksa' 256 _ s = s
        ksa' i j s = let i' = i `mod` length k
                         j' = (j + s ! i + ord (k !! i')) `mod` 256
                     in ksa' (succ i) j' (swap j' i s)

-- Swap the values of S[i] and S[j]
swap :: Index -> Index -> ArrayRC4 -> ArrayRC4
swap i j s = if i /= j then s // [(i, s ! j), (j, s ! i)] else s

Let’s go over the code. Initially, the state array is created and set to the identity permutation, which is done by the expression (listed inside ksa body)

array (0,255) [(i,i) | i<- [0..255]]

which creates a value of the type ArrayRC4 (which is a synonym for Array Int Int) with the help of the array function imported from the Data.Array module. This function requires two parameters: the array bounds and the array contents. The array bounds (the lowest and highest indices in the array) are expressed as the Haskell tuple (0,255), while its contents are specified by a list of tuples of the form (index, value): [(0,0),(1,1),(2,2)...(255,255)], that can be expressed much more concisely as a list comprehension: [(i,i)|<-[0..255]].

Being Haskell a strong static typed language, every expression to be computed must have a well defined type during compilation time. Since indices and elements change places in both functions, ksa and prga, their types must be exactly the same, Int in this case. Although we haven’t explicitly declared the type of the array state, the Haskell compiler will infer it from the type declarations ksa :: Key -> ArrayRC4 (which states that the function ksa produces an output of type ArrayRC4) and ksa' 256 _ s = s (which requires that ksa' last parameter to be of type ArrayRC4).

The swap function

-- Swap values of S[i] and S[j]
swap :: Index -> Index -> ArrayRC4 -> ArrayRC4
swap i j s = if i /= j then s // [(i, s ! j), (j, s ! i)] else s

The swap function accepts two indices (of type Index, a synonym for Int) and the state array (of type ArrayRC4) as inputs and produces a new, updated state array after swapping the contents of the two specified array elements. Arrays of type Data.Array.Array (the only array type supported by Haskell 98) are, like any other pure functional data structures, immutables, so once created they cannot be changed, only queried. In order to do its job, swap uses the incremental array update infix operator, //, imported from the Data.Array module. For example, an array a with an element i updated to value v is written a//[(i,v)].

This array update is not very efficient (both in terms of time and memory), as a new copy of the array must be carried out before any changes can be applied. On the other hand, those arrays can be used in pure functional code [6]. The second operator imported from the Data.Array module is the array subscripting infix operator ! (as an example, the expression a!i returns the value at index i of an array a).

The ksa function

-- Key Scheduling Algorithm (KSA)
ksa :: Key -> ArrayRC4
ksa k = ksa' 0 0 $ array (0,255) [(i,i) | <- [0..255]]
  where ksa' 256 _ s = s
        ksa' i j s = let i' = i `mod` length k
                         j' = (j + s ! i + ord (k !! i')) `mod` 256
                     in ksa' (succ i) j' (swap j' i s)

The ksa function accepts a key (of type Key, a synonym for String) as input and outputs the state array (of type ArrayRC4). Since there is no “loop” construction in Haskell, recursion is used instead. The ksa function just set the initial parameters for an auxiliary, recursive function, ksa', that does the hard work, visiting every single element of the array state. Its parameters are i (first index and counter), j (second index) and s (the state array). The stop condition (otherwise the recursion will never stop) is met, via Haskell’s pattern match, when i is equal to 256.

Two additional comments:

List subscripting is done by the infix operator !!, made available by the Prelude module (a standard module imported by default into all Haskell modules).
If a function (or constructor) takes two or more arguments, like mod, it can be used in infix form by enclosing its name in backtick characters (`mod`).

The prga function

-- Pseudo-random generation algorithm (PRGA)                         
prga :: ArrayRC4 -> Stream
prga = prga' 0 0
  where prga' i j s = let i' = succ i `mod` 256
                          j' = (s ! i' + j) `mod` 256
                          s' = swap i' j' s
                          t = chr $ s' ! ((s ! i' + s ! j') `mod` 256)
                       in t : prga' i' j' s'

The prga function accepts the initialized state array (of type ArrayRC4) as input and outputs the keystream (of type Stream, a synonym for String), represented in Haskell by a list of characters of (potentially) infinite length. This is no problem for non-strict languages like Haskell, Miranda and Clean. In particular, Haskell, and also Miranda, adopt the approach known as “lazy evaluation” (or “call-by-need”): an expression is evaluated only when its value is required.

The encrypt function

-- Encrypt (or decrypt) using RC4 keystream
encrypt :: Key -> String -> String
encrypt k c = map chr $ zipWith xor (map ord (stream k)) (map ord c)
              where stream k' = prga (ksa k')

The encrypt function defines the encryption/decryption service interface: it accepts the key (of type Key) and the plaintext/ciphertext (of type String) and returns the ciphertext/plaintext (also of type String). It is interesting to examine how the expression below is evaluated.

-- zipWith xor (map ord (stream k)) (map ord c)

The zipWith function (exported by the Prelude module) accepts a binary function and two lists and produces a third list which elements are calculated applying the function to the elements occurring at the same position in both lists (in this particular case, the binary function is xor, and the three lists are of type [Int]). If the first two lists are of different length, the longer one is truncated to make them of the same size.

The first list, the keystream (represented as a list of integers), has potentially infinite length, while the second one, the cleartext/ciphertext (also represented as a list of integers), has finite length. Haskell’s lazy evaluation of this expression will demand from the prga function a keystream exactly as long as that of the cleartext or ciphertext being encrypted (decrypted).

The Main module

Since RC4 is a proprietary algorithm, there are no official test suite for validating RC4 implementations [5]. A quick check can be performed, however, using the unofficial test vectors available at Wikipedia.

The program below executes the three tests described at Wikipedia and a fourth that checks whether the encrypt function is an involution (a function that it is own inverse) testing a single point of its domain. The keys and plaintext shown in the code are ASCII while the keystream and ciphertext are in hexadecimal.

-------------------------------------------------------------
--
-- Author: Joao H de A Franco (jhafranco@acm.org)
--
-- Description: Test module for RC4 implementation in Haskell
--
-- Date: 2013-Feb-22
--
-- License: Attribution-NonCommercial-ShareAlike 3.0 Unported
--          (CC BY-NC-SA 3.0)
--
-------------------------------------------------------------
module Main where
import Crypto.RC4 (encrypt)
import Numeric (showHex)
import Data.Char (ord)

-- The first threee test-vectors are from Wikipedia
-- (http://en.wikipedia.org/wiki/RC4#Test_vectors)
main :: IO ()
main = do
-- Test #1 ----------------------------------------
  let t1 = encrypt "Key" "Plaintext"
  check (convert t1 == "bbf316e8d940af0ad3") 1
-- Test #2 ----------------------------------------
  let t2 = encrypt "Wiki" "pedia"
  check (convert t2 == "1021bf0420") 2
-- Test #3 ----------------------------------------
  let t3 = encrypt "Secret" "Attack at dawn"
  check (convert t3 == "45a01f645fc35b383552544b9bf5") 3
-- Test #4 ----------------------------------------
  let t4 = encrypt "bla-bla-bla" "Do you want to know a secret?"
  let t4' = encrypt "bla-bla-bla" t4
  check (t4' == "Do you want to know a secret?") 4

check :: Bool -> Int -> IO ()
check f t = putStrLn $ "Test " ++ show t ++ if f then ": ok" else ": nok"

convert :: String -> String
convert = concatMap (showHex' . ord)
          where showHex' x = let y = showHex x ""
                              in if length y == 1 then '0' : y else y

Comments

The main function (in the Main module) can be evaluated using GHCi (GHC’s interactive environment), in which Haskell expressions can be interactively evaluated and programs can be interpreted. The output is shown below:

GHCi, version 7.4.2: http://www.haskell.org/ghc/
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package array-0.4.0.0 ... linking ... done.
[2 of 2] Compiling Main (/home/jhaf/workspace/RC4a/src/Main.hs, interpreted)
Ok, modules loaded: Main, Crypto.RC4
*Main> main
Test 1: ok
Test 2: ok
Test 3: ok
Test 4: ok

Note 1 – You will see no syntax highlighting in all boxes showing Haskell code because it is not a programming language supported by WordPress.com. Although Haskell is not particularly popular — it is in position #33 in the TIOBE Programming Community Index — other languages ranked worse than Haskell in the TIOBE index (Scala, Erlang, F#, Clojure, VB and Powershell) are indeed supported by WordPress.com.

Note 2 – The name RC4 is a trademark of RSA Security. For this reason, RC4 is often referred to as ARCFOUR or ARC4 (alleged RC4) to avoid trademark problems. RSA Security has never officially released the algorithm.

Note 3 – Until 2000, when the U.S. government relaxed export regulations on cryptography, only encryption software with keys up to 40 bits could be exported by U.S. companies. While this lower limit is just a convention, the upper one is real: if the key is greater than 2,048 bits (which happens to be 8 x 256), the excess bytes will be just dropped by the KSA.

Note 4 – An interesting RC4 tutorial with animation is available at Marc Loiseau’s blog).

Note 5 – Haskell libraries with other, more complex, implementations of arrays – but which have far more features – are available, some of which are mutable and/or strict.

Note 6 – As RSA was the sole primary vendor of cryptographic kits that include implementations of RC4, which was not an approved algorithm for use by the U.S. government, there was no (strong) demand for a test suite for validating RC4 implementations.

Four chess problems

Posted on March 19, 2012 by JHAF

More than stating the importance of time, material sacrifices in chess combinations are tangible proofs of the superiority of mind over matter. Your task, dear reader, is to find out the solution of each of the following chess problems. The first two are composed problems and the other two were extracted from (unknown) real games.

Problem 1 – White to play and mate in two.
V. Melnichenko (1958)

Problem 2 – White to play and mate in two.
S. Loyd (1877)

Problem 3 – White to play and mate in three.

Problem 4 – White to play and mate in three.

Solutions: P1: 1.Bh5 / P2: 1.Qa1 / P3: 1.Ng6 hg6 2.Nd5 ed5 3.Qe5# / P4: 1.Qa6 ba6 2.Nb5 Ka8 3.Rg8#

João H de A Franco

"What's mind? No matter. What's matter? Never mind." (Bertrand Russell)

Author Archives: JHAF