# What is a LFSR?

I was reading "serious Cryptography" by Jean-Philippe Aumasson,and when coming to Feedback Shift Registers,I didn't understand what role Polynomials play in the feedback function, does it have to do with polynomial addition,which is simuar to XOR? Also i made a simple FSR,just to understand it better,so I wanted to ask the question:

is this an example for a FSR?:

def feedback(list):
return(((list[-1]+list[-1])^list[-2]|list[-7]&list[0])^(list[-5]|list[-6]&list[-4]^list[-10]^list[-11])&(list[-3]|list[-7]&(~list[-9])^list[-11])|(list[-13]^list[-15]^~list[-4])^list[0]>>1) # the feedback function combines specific bytes from the key stream to generate a new byte

def encrypt_and_decrypt(nums,key):
key = list(key)
if len(key)>=len(nums):#if the key is larger than the plaintext
for i in range(len(key)):#just XOR the key to the plaintext and return the ciphertext
nums[i]^=key[i]
return nums

else:
for i in range(len(key)):
nums[i]^=key[i]
for i in range(len(key),len(nums)):
key.append(feedback(key))# generate new bits from the existing key stream
key = key[1:] # delete the first entry to save memory
nums[i]^=key[-1]# XOR the newly generated key byte to the plaintext byte

return nums



Another question I have is: if this really is an example for a LFSR,what prevents a known plaintext attacker,who knows the first bytes from the plaintext from just XORing that part to the ciphertext,getting the initial key and generating the key stream all over again?

I would thank everyone who answers me,as I am really new to this aspect,ans I'm just beginning to understand it,so thank you for your answers!

• On the first question: see this and this related questions on why polynomials are used. In a nutshell: because it allows to express the evolution of the state of the LFSR using polynomial arithmetic with the terms of the polynomial in a finite field, typically $\mathbb F_2$.
– fgrieu
Commented Jan 27 at 11:13
• @fgrieu Oh,I see! It allows you to calculate future states to evaluate its cryptographic security?
– RA35
Commented Jan 27 at 11:21
• Yes considerations on polynomial arithmetic allows to find future and past states very efficiently. They also allow to reason on LFSR's cryptographic (in)security, and show that an LFSR in isolation is insecure as a PRNG in a known plaintext attack (that's even if it's keystream is never reused and the taps of the LFSR are secret; see Berlekamp-Massey). You are correct that keystream reuse in a stream cipher allows known plaintext attack, and that applies to any PRNG.
– fgrieu
Commented Jan 27 at 11:33
• If you like the learn the math behind, see SHIFT REGISTER SEQUENCES by Solomon Golomb. Commented Jan 27 at 16:32