Linear feedback shift register

Modern ciphers are classified mainly as stream ciphers and block ciphers. LFSR is a simple method to generate a stream cipher. 

Stream ciphers are generated by adding each bit of plaintext with long generated bits called the keystream. Keystream is made out of a small secret called the seed, which is developed into a very long sequence of bits. 

Stream ciphers are generally based on states, an update function that navigates from one state to another and an output. 

You can read more about LFSR here

Following is the implementation of LFSR in magma with the given specification:

INPUT: 	(P,L,t)  	
         - P is the connection polynomial for the LFSR
			- L is a list for the initial state 
(note that Degree(P) eq #L) 
			- t the length of the keystream that we get 
from the initial state


OUTPUT (Ks,S)		
         - Ks is a List of length t which contains the keystream
			- S is a list of length t+1 which contains 
the states of the LFSR
			  (so S is a list of lists)

function RightLFSR(P, L, t)
	C:= Coefficients(P);
	C:=Reverse(C);

	V:=[];
	L;

	for i in [1..t] do
		V[i]:=L[#L]; // The output value is
                             //the last bit of each stream excluding
                             //the last register value.
		k:=GF(2)!0;
		L1:=L;
		//Shift the register to the right
		for j in [1..#L1]do
			if j+1 in [1..#L] then
				L[j+1] := L1[j];
			end if;
		end for;
		//XOR the values based on the polynomial
		S:=[];
		for j in [1..#L] do
			S[j]:=L1[j]*C[j+1]; // The previous state of
                         // the register before
                          //shifting is taken to find the first bit.
			k:=k+S[j];
		end for;
		L[1]:=k;
		L;
	end for;
return V;
end function;

R<x>:=PolynomialRing(GF(2));
RightLFSR(x^5 + x + 1,[GF(2)!1,0,0,1,0],8);
//Calling the function above
Advertisements