# load plaintext-ciphertext pair list
#ptctlist=load('ptctlist.txt')
f=open('ptctlist.txt','r')
ptctlist=eval(f.readline())
# function that sums the bits in state L selected by the 1-bits in list M
def sumstate(L,M): return sum([(L[i]&M[i]) for i in range(16)],0)
# function to test linear relation given plaintext PT, ciphertext CT, guess for roundkey K5
# and the linear relation specified by PTM (over the bits of PT) and R4M (over the bits of the input of round 4)
# Using K5 it decrypts the final round key-mixing and the last substitutions of CT to obtain the input of round 4
# (we can ignore K4 here as showed in class: it only affects the sign of the bias)
# it returns the sum of the selected bits PTM of PT and of the selected bits R4M of the round 4 input
def testlinrel(PT,CT,K5,PTM,R4M): return ((sumstate(PTM,PT)+sumstate(R4M,substbitsinv(xor(CT,K5)))+1)%2)
# the plaintext mask and round 4 input mask for the linear relation covered in class
ptmask=[0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0]
r4mask=[0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1]
# function to test the above linear relation for given plaintext,ciphertext pair and guess for K5
def testsub(PTCT,K5): return testlinrel(int2state(PTCT[0]), int2state(PTCT[1]), K5, ptmask, r4mask)
# function to test guess for K5 over entire plaintext-ciphertext pair list and return |bias|=|#(testsub=1) - 4096|
def test(K5): return abs(sum([testsub(ptctlist[i],K5) for i in range(len(ptctlist))],0)-(len(ptctlist)//2))
# function that maps an 8-bit integer to a guess for K5 over bits 5,6,7,8 and 13,14,15,16
def int2K5sub(i): return word2bits(0)+word2bits(i//16)+word2bits(0)+word2bits(i%16)
# try all possible guesses for K5: result is list of [bias,k5guess]-pairs
result=[[test(int2K5sub(i)),i] for i in range(256)]
# sort result on bias
result.sort()
# take the k5guess with highest bias (result[-1] returns the last element)
k5guess=int2K5sub(result[-1][1])