Cryptology ePrint Archive: Report 2015/357

A Group-theory Method to The Cycle Structures of Feedback Shift Registers

Ming Li, Yupeng Jiang and Dongdai Lin

Abstract: In this paper, we consider the cycle structures of feedback shift registers (FSRs). At the beginning, the cycle structures of two special classes of FSRs, pure circulating registers (PCRs) and pure summing registers (PSRs), are studied and it is proved that there are no other FSRs have the same cycle structure of an PCR (or PSR). Then, we regard $n$-stage FSRs as permutations over $2^n$ elements. According to the group theory, two permutations have the same cycle structure if and only if they are conjugate with each other. Since a conjugate of an FSR may no longer an FSR, it is interesting to consider the permutations that always transfer an FSR to an FSR. It is proved that there are exactly two such permutations, the identity mapping and the mapping that map every state to its dual. Furthermore, we prove that they are just the two permutations that transfer any maximum length FSR to an maximum length FSR.

Category / Keywords: secret-key cryptography / stream ciphers

Date: received 21 Apr 2015

Contact author: liming at iie ac cn

Available format(s): PDF | BibTeX Citation

Version: 20150423:125011 (All versions of this report)

Short URL: ia.cr/2015/357

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]