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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2015/357}},
      url = {https://eprint.iacr.org/2015/357}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.