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

code in Listing 6-4 to the end of the above algorithm. In the code, we define a simple function to print out its
argument binary. We then print out the key derived from the linear cryptanalysis code, and also show the actual
relevant subkey.

Listing 6-4 Python code for printing out the results of the previous linear cryptanalysis of EASY1. Note that
the rjust function takes the string it is applied to and pads it up to the given length (the first argument) by in-
serting the pad character (the second argument) on the left until it is the correct length.

# Prints out its argument in binary
def binary(x):
if x != 0:
y = binary(x >> 1) + str(x 1)

if y == "":
return "0"
else :
return y
else :
return ""

print "guess:",
print (binary(maxk >> koffset)).rjust(6,
print maxk >> koffset,
print " deviation: ",
print maxdev/float(len(plaintext))

print "real: ",
print (binary((apbox(key) >> koffset) 0x3f)).rjust(6,

print (apbox(key) >> koffset) 0x3f)

6.11 Summary
In this chapter, we explored a powerful technique for deriving keys in many ciphers. This technique is the first
attack against DES to operate in less time than an exhaustive search. The downside is that a large number of
known plaintext-ciphertext pairs must be collected, and that because the attack is probabilistic, it isn't guaran-
teed to work for every key.
Nearly every attack we cover in the rest of the topic will have a similar structure to linear cryptanalysis:
We typically generate some kind of expression for each individual cryptographic element (such as an S-box)
and build the expression to encompass rounds and eventually the entire cipher. The nature of these expressions
changes depending on the attack, although several are based on linear expressions. As such, understanding the
basic linear cryptanalytic attack is extremely helpful in comprehending the attacks of the next chapter.