Abstract
Feedback with Carry Shift Registers (FCSRs) are primitives that are used in multiple areas like cryptography or generation of pseudorandom sequences. In both cases, we do not want that an attacker can easily guess the content of the register. This requires a high entropy of the inner state. We consider the case of a binary FCSR in Galois representation. In this article, we show that we already lose after one iteration a lot of entropy. The entropy reduces until the moment where the FCSR reaches a periodic behavior. We present an algorithm which computes the final entropy of an FCSR and which also allows us to show that the entropy never decreases under the size of the main register.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Arnault, F., Berger, T.P.: Design and properties of a new pseudorandom generator based on a filtered FCSR automaton. IEEE Transactions on Computers 54(11), 1374–1383 (2005)
Arnault, F., Berger, T.P.: F-FCSR: Design of a New Class of Stream Ciphers. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 83–97. Springer, Heidelberg (2005)
Arnault, F., Berger, T.P., Lauradoux, C.: F-FCSR. eSTREAM, ECRYPT Stream Cipher Project, Report 2005/008 (2005), http://www.ecrypt.eu.org/stream
Arnault, F., Berger, T.P., Lauradoux, C.: Update on F-FCSR stream cipher. In: SASC, State of the Art of Stream Ciphers Workshop, Leuven, Belgium, February 2006. ECRYPT Network of Excellence in Cryptology, pp. 267–277 (2006)
Arnault, F., Berger, T.P., Minier, M.: Some results on FCSR automata with applications to the security of FCSR-based pseudorandom generators. IEEE Transactions on Information Theory 54(2), 836–840 (2008)
Couture, R., L’Ecuyer, P.: On the lattice structure of certain linear congruential sequences related to AWC/SWB generators. Math. Comput. 62(206), 799–808 (1994)
Goresky, M., Klapper, A.: Fibonacci and galois representations of feedback-with-carry shift registers. IEEE Transactions on Information Theory 48(11), 2826–2836 (2002)
Klapper, A., Goresky, M.: 2-adic shift registers. In: Anderson, R. (ed.) FSE 1993. LNCS, vol. 809, pp. 174–178. Springer, Heidelberg (1994)
Klapper, A., Goresky, M.: Feedback shift registers, 2-adic span, and combiners with memory. J. Cryptology 10(2), 111–147 (1997)
Marsaglia, G., Zaman, A.: A new class of random number generators. Annals of Appl. Prob. 1(3), 462–480 (1991)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Röck, A. (2008). Entropy of the Internal State of an FCSR in Galois Representation. In: Nyberg, K. (eds) Fast Software Encryption. FSE 2008. Lecture Notes in Computer Science, vol 5086. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-71039-4_22
Download citation
DOI: https://doi.org/10.1007/978-3-540-71039-4_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-71038-7
Online ISBN: 978-3-540-71039-4
eBook Packages: Computer ScienceComputer Science (R0)