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

Ming Li; Yupeng Jiang; Dongdai Lin

Paper 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.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: stream ciphers
Contact author(s): liming @ iie ac cn
History: 2015-04-23: received
Short URL: https://ia.cr/2015/357
License: CC BY

BibTeX

@misc{cryptoeprint:2015/357,
      author = {Ming Li and Yupeng Jiang and Dongdai Lin},
      title = {A Group-theory Method to The Cycle Structures of Feedback Shift Registers},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/357},
      year = {2015},
      url = {https://eprint.iacr.org/2015/357}
}