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
        return nums

        for i in range(len(key)):
        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!

  • 2
    $\begingroup$ 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$. $\endgroup$
    – fgrieu
    Commented Jan 27 at 11:13
  • $\begingroup$ @fgrieu Oh,I see! It allows you to calculate future states to evaluate its cryptographic security? $\endgroup$
    – RA35
    Commented Jan 27 at 11:21
  • 1
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Commented Jan 27 at 11:33
  • 1
    $\begingroup$ If you like the learn the math behind, see SHIFT REGISTER SEQUENCES by Solomon Golomb. $\endgroup$
    – kelalaka
    Commented Jan 27 at 16:32


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.