Nowadays, I spend most of my time studying on Nonlinear Feedback Shift Registers (NFSRs). Especially the ones with Maximum period.
A feedback shift register is a device that shifts its contents into adjacent positions within the register and fills the position on the other end with a new value generated by the feedback function. If the feedback function is linear, everything is easy! :)But when you start to work on nonlinear feedback functions, things start to get a little bit harder.
There are some important unsolved problems and conjectures related to the selection of feedback function of a NFSR. There is no efficient method that finds feedback function with maximum period and also, given a feedback function it is hard to predict the period.
If you want to learn more about NFSRs, you can start with the following papers and books.
- H. Fredricksen. A survey of full length nonlinear shift register cyclealgorithms. Siam Review, 24(2):195–221, 1982
- S. W. Golomb. Shift Register Sequences. Aegean Park Press, LagunaHills, CA, USA, 1981
- A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook ofapplied cryptography. CRC Press, Boca Raton, Florida, 1996.
If you want to discuss anything about NFSRs, please feel free :)
17 comments:
Very useful! Thanks, Meltem. I'm also interested in NFSRs. I knew about Golomb's book, but i didn't know about Fredricksen paper. I'll check it. Cheers!
hello and thanks for the information
so could you tell me wath is the maximum period of 128 nfsr i mean the taps like in grain-128 where we use nfsr for the key so if you prove that there is maximum period in nfsr it will be good to improve grain
me question what is the maximum period of nfsr 128 bit .
thanks
Hi.
The maximum period of the sequence generated by a 128 bit NFSR is 2^{128}, they are called de Bruijn sequences.
The NFSR used in Grain is probably not maximum length, at least currently we don't know a way to prove that it is maximum lenght. But using a maximum length NFSR might not improve the security of Grain, because the NFSR is fed with the output of another LFSR, which affects the period of the NFSR. Is it clear ?
thanks alot
I'm totally new to linear and nonlinear pseudo random sequences and their generators, so can you please in few sentences explain me what is the difference between LFSR and NLFSR. How can I, when I first see the scheme of the generator tell if it is LFSR or NLFSR?
Feedback shift registers have a feedback polynomial, if the feedback polynomial is linear, register is called Linear Feedback Shift Register. if the feedback polynomial is nonlinear then it is called a Nonlinear feedback shift register.
Thank you for your response, however, in order to ask you more precisely my question here are two pictures of generators.
http://img202.imageshack.us/img202/1576/image1rr.jpg
http://img440.imageshack.us/img440/2244/image2zjt.jpg
In the book that I read it says that on the first picture (image1) is LFSR, and on the second one is NLFSR. My question is how do I know it's a NLFSR, because I don't see any negation or what does it need to have on it self, this generator in order to call it NLFSR. I know it has got something to do with gf(2), but can you please explain me what. Or is it a mistake in the book?
Thank you in advance for a response it will be of much help to me!
Based on the images, I believe both of them are linear feed back shift registers. I see that they only use the XOR operation. If it had an AND operation (multiplication modulo 2) it would be nonlinear.
In Grain it is possible that after the Key scheduling the LFSR becomes all zero. In such a case, the NFSR would run on its own. In such an event, since it is clear that the NFSR feedback function does not produce a full length DeBruijn Sequence, it is possible that one possible NFSR state may produce a sequence of small period..... Since the lower bound of the period of a random FSR is 2^(n/2) is it possible to find a state with period 2^40?
Yes, the observation is true and it was previously used on a paper.I dont remember the title right now.
Actually, nowadays, I am working on how to find a short cycles for Grain.
As far as I know, if the feedback function is random, then the expected cycle is 2^{n/2}. But if the feedback is 1-1 (as in the case of Grain), the expected cycle length is 2^{n-1}.
If you want to discuss further, send me an email meltemsturan AT gmail.com
Dear Meltem
I am using an LFSR of length 17 over Galois field. I am using a function in feedback, Should this qualify as NLFSR? kindly reply asap.
thnx
That should still be considered as an LFSR, you are not limited to GF(2) in the definition of an LFSR.
what about the feedback function that i am using in feedback. I want to add here that i am using an s-box inside that feedback function. shud it now qualify as an nlfsr?
If you are using a nonlinear sbox inside the feedback function, then it qualifies as an NLFSR. You can also check the linear complexity of the output, after you are done.
thanks. the last confusion is about non linear s-box.. i m not very sure about it. the s-box i m using is exctly the same used in SOBER t16 & t32 but I am not sure whether its linear or non-linear, though i have feeling that its non linear. The s-box is a combination of SKIPjack and ISRC and is used in the NLF part of the cipher.
If you are using the Sober s-box, then it is definitely nonlinear.
thanks ma'am a lot and sry fr troubling u again and again. Although u have very clearly stated it as non linear, I just want to reconfirm it once again, before i continue with my work. I am using an LFSR of length 17 over GF(2) and am providing feedabck via a feedback function that uses an S-box same as used in Sober-t16. Should I call this LFSR as NLFSR or I need to make any further modification for non linearity. thnx again
Post a Comment