some helper code for this lab is in this file fivebit.py. here is a summary of the functions included in my code--not all of them are necessarily helpful for this lab:

• encode(s) - encode the characters A-Z and 0-5 in a 5-bit encoding scheme; the result is a list of 0's and 1's
• decode(bits) - give a list of bits (whose length is a multiple of 5), decode it into the appropriate string using our 5-bit scheme; i.e., do the inverse of encode
• onlyalpha(s) - (from lab 3) strips nonalphabetic characters from a string s
• freq_count(s) - (from lab 3) performs a frequency count on the letters in s
• freq_dist(s) - (from lab 3) computes the a frequency distribution of the letters in s

• code - a list of characters defining the 5-bit encoding scheme
• EF - a list of relative frequencies of the English letters

note: for the purposes of this lab, we will work with an n-bit string as a list of 0's and 1's (of type int). this is not the most efficient way to with bit strings, but it is convenient for us to (1) work with general n, and (2) doing arithmetic mod 2. in practice, you would do the latter with bits with bitwise operators

task 1: write a function xor(v,w), which returns the xor (addition mod 2) of 2 strings of the same length. if the strings do not consist of 0s and 1s or are not of the same length, return or print an error. test your code out on a few strings of 0s and 1s of the same length and at least one input of different lengths.

task 2: write a function lfsr(a, seed, N), where a and seed are strings of 0s and 1s of the same length (say n), and N is an integer at least as big as n. this function shoud return a list of length N of 0's and 1's which are the first N bits b[0], b[1], ... , b[N-1] of the lfsr with initial value seed and recurrence b[k] = a[0]b[k-n] + a[1]b[k-n+1] + ... a[n-1]b[k-1] (mod 2). test your function with coefficient lists a = [1,0,0], a = [1,0,1] and a = [1,1,1] with seed = [0,0,1]. what is the period of the resulting sequence in each case?

task 3: write a function printstates(a,seed,N) that prints out the first N states of the register for lfsr(a,seed,*). on each line, print out the state (n-bits where n=len(a) followed by the line number. e.g., printstates([1,1],[0,1],4) should return something like

0 1 | 0
1 1 | 1
1 0 | 2
0 1 | 3

(you may format your printout a bit differently if you prefer). then test this on the cases: (i) a = [1,1,0,0], seed = [1,1,0,0], N = 16, (ii) a = [1,1,0,0], seed = [1,0,1,0], N = 16 and (iii) a = [1,0,1,1,1], seed = [1,0,0,0,0], N = 32. what are the period lengths in each case?

task 4: write a function maxlfsrs(n) that returns a list of the coefficient lists (denote a in the previous task) for the maximal length n-bit lfsrs, i.e., those with period length 2^n-1 for a nonzero seed. determine how many maximal length lfsrs there are on n-bits for n = 2, 3, 4, 5, 6. compare this to the total number of n-bit lfsrs.

task 5: encrypt and decrypt the string text (included in the helper code file) by xoring with the lfsr with parameters a = [1,0,1,1,1], seed = [1,0,0,0,0]. do a frequency analysis of the resulting ciphertext to compare (qualitatively) if the frequency count is closer to a uniform distribution than for a shift or substitution cipher. note: the included functions for frequency counting only count letters, whereas now some of your ciphertext may include digits. you can count the number of times, say '3' occurs in a string s with the command s.count('3'). how do you think the distribution of frequency counts compares to that of a vigenere cipher of appropriate length? what security advantages, if any, does this scheme have over a vigenere cipher? (in particular, think about bits of data for the key (seed) and the period of the lfsr.) are there any apparent disadvantages?

lab 4 homework: complete the above tasks (due fri feb 28)