Cryptology ePrint Archive: Report 2014/536

On Decomposition of an NFSR into a Cascade Connection of Two Smaller

Tian Tian and Wen-Feng Qi

Abstract: Nonlinear feedback shift registers (NFSRs) are an important type of sequence generators used for building stream ciphers. The shift register used in Grain, one of eSTREAM finalists, is a cascade connection of two NFSRs, which is also known as nonlinear product-feedback shift registers proposed in 1970. This paper provides a series of algorithms to decompose a given NFSR into a cascade connection of two smaller NFSRs. By decomposing an NFSR into a cascade connection of two smaller NFSRs, some properties regarding cycle structure of the original NFSR could be known.

Category / Keywords: secret-key cryptography / stream ciphers, nonlinear feedback shift registers, cascade connection, Grain

Date: received 9 Jul 2014

Contact author: tiantian_d at 126 com

Available format(s): PDF | BibTeX Citation

Version: 20140709:151652 (All versions of this report)

Short URL: ia.cr/2014/536

Discussion forum: Show discussion | Start new discussion