Linear Cryptanalysis - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 152

6.10 Linear Cryptanalysis Code
The following pieces of Python code can be used to implement linear cryptanalysis. They are currently tuned to
break the EASY1 cipher, although they can be easily adapted to any other ciphers.
All of the code in this chapter relies on the Python code for EASY1 to be already loaded beforehand (from
Chapter 4), that is, the encryption and decryption functions.
First, I define a few extra helper functions in Listing 6-1 . They are used to help us process the ciphertext to
an appropriate level so that we can calculate a linear expression. There are three functions defined: calculating
an inverse (or reverse) S-box given the original definition of the S-box, calculating the reverse P-box given the
original definition of the P-box, and a function to obtain the value of a given bit from a number.
Listing 6-1 A few helper functions for performing linear cryptanalysis on the EASY1 cipher. We assume that
the S-box and P-box functions are already set up, as specified in Chapter 4.
##########################################
# Calculate the reverse S-Box
##########################################
s2 = []
for i in range(0,len(s)):
s2.append(0)
for i in range(0,len(s)):
s2[s[i]] = i
def asbox(x):
return s2[x]
##########################################
# Reverse P-box
##########################################
def apbox(x):
y = 0l
for i in range(len(p)):
if (x & (1l << p[i])) != 0:
y = y ^ (1l << i)
return y
##########################################
# Extract a bit from the argument
##########################################
def grab(x, pos):
return (x >> (pos)) & 1
Next, we need code to generate the known plaintext-ciphertext pairs that that we will use to evaluate the
linear expressions. Listing 6-2 generates the known plaintext-ciphertext pairs for the EASY1 cipher. First, it
defines the simple encryption function using the key (in binary, 0100 1001 0010 0100 1001 0010
0100 1001 0010 ). It then generates 1,800 random plaintexts and stores them, along with the resultant
ciphertexts (after encrypting with the three rounds of the EASY1 cipher).