# load plaintext-ciphertext pair list1#ptctlist=load('ptctlist.txt')2f=open('ptctlist.txt','r')3ptctlist=eval(f.readline())45# function that sums the bits in state L selected by the 1-bits in list M6def sumstate(L,M): return sum([(L[i]&M[i]) for i in range(16)],0)7# function to test linear relation given plaintext PT, ciphertext CT, guess for roundkey K58# and the linear relation specified by PTM (over the bits of PT) and R4M (over the bits of the input of round 4)9# Using K5 it decrypts the final round key-mixing and the last substitutions of CT to obtain the input of round 410# (we can ignore K4 here as showed in class: it only affects the sign of the bias)11# it returns the sum of the selected bits PTM of PT and of the selected bits R4M of the round 4 input12def testlinrel(PT,CT,K5,PTM,R4M): return ((sumstate(PTM,PT)+sumstate(R4M,substbitsinv(xor(CT,K5)))+1)%2)1314# the plaintext mask and round 4 input mask for the linear relation covered in class15ptmask=[0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0]16r4mask=[0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1]1718# function to test the above linear relation for given plaintext,ciphertext pair and guess for K519def testsub(PTCT,K5,PTM,R4M): return testlinrel(int2state(PTCT[0]), int2state(PTCT[1]), K5, PTM, R4M)2021# function to test guess for K5 over entire plaintext-ciphertext pair list and return |bias|=|#(testsub=1) - 4096|22def test(K5,PTM,R4M): return abs(sum([testsub(ptctlist[i],K5,PTM,R4M) for i in range(len(ptctlist))],0)-(len(ptctlist)//2))2324# function that maps an 8-bit integer to a guess for K5 over bits 5,6,7,8 and 13,14,15,1625def int2K5sub(i): return word2bits(0)+word2bits(i//16)+word2bits(0)+word2bits(i%16)2627# try all possible guesses for K5: result is list of [bias,k5guess]-pairs28result=[[test(int2K5sub(i),ptmask,r4mask),i] for i in range(256)]2930# sort result on bias31result.sort()3233# take the k5guess with highest bias (result[-1] returns the last element)34k5guess=int2K5sub(result[-1][1])3536# another linear approximation attack: this assumes 8 bits of K5 are known: [**** 1100 **** 1000]37def int2K5sub2(i): return word2bits(i//16)+[1,1,0,0]+word2bits(i%16)+[1,0,0,0]38result2=[[test(int2K5sub2(i),[0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0],[0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0]),i] for i in range(256)]39result2.sort()40k5guess2=int2K5sub2(result2[-1][1])4142# and another linear approximation attack43def int2K5sub3(i): return word2bits(i%16)+[1,1,0,0]+word2bits(0)+[1,0,0,0]44result3=[[test(int2K5sub3(i)),i] for i in range(16)]45result3.sort()46k5guess3=int2K5sub3(result3[-1][1])474849