| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Design and Properties of a New Pseudorandom Generator Based on a Filtered FCSR Automaton
November 2005 (vol. 54 no. 11)
pp. 1374-1383
Feedback with carry shift registers (FCSR) was introduced by Goresky and Klapper in 1993. It is similar to the classical linear feedback shift registers (LFSR) used in many pseudorandom generators. The main difference is that the elementary additions are not additions modulo 2 but with propagation of carries. The main problem for the use of an FCSR automaton is the fact that the generated sequences are predictable. In order to remove this weakness of FCSR-based generators, we propose filtering the state of the FCSR with a linear function. This method is efficient since the FCSR structure is not related to a linear property. This paper presents an extensive study of FCSR automata, a security analysis of our generator (concerning linear and 2-adic cryptanalysis, algebraic attack, correlation attack, etc.), and a practical example of parameters in order to design this generator. An important point concerning this generator is the fact that it is simple and efficient, both in hardware and software implementation.
[1] F. Arnault, T.P. Berger, and A. Necer, “A New Class of Stream Ciphers Combining LFSR and FCSR Architectures,” Proc. INDOCRYPT '02, A. Menezez and P. Sarkar, eds., pp. 22-33, Dec. 2002.
[2] F. Arnault, T.P. Berger, and A. Necer, “Feedback with Carry Shift Registers Synthesis with the Euclidean Algorithm,” IEEE Trans. Information Theory, vol. 50, no. 5, pp. 910-917, May 2004.
[3] W. Bosma and J. Canon, Handbook of Magma Functions, Dept. of Math., Univ. of Sydney, Nov. 1994, http://www.maths.usyd. edu.au:8000/umagma /.
[4] C. Carlet, “On Cryptographic Complexity of Boolean Functions, Finite Fields with Applications to Coding Theory, Cryptography and Related Areas,” Proc. Sixth Conf. Finite Fields with Applications to Coding Theory, pp. 53-96, 2002.
[5] D. Coppersmith, H Krawczyk, and Y. Mansour, “The Shrinking Generator,” Advances in Cryptology, Proc. CRYPTO '93, pp. 22-39, 1994.
[6] N. Courtois and W. Meier, “Algebraic Attack on Stream Ciphers with Linear Feedback,” Proc. EUROCRYPT '03, E. Biham, ed., pp. 345-359, 2003.
[7] J.C. Faugère, “A New Efficient Algorithm for Computing Gröbner Bases without Reduction to Zero ($F_5$ ),” Proc. Int'l Symp. Symbolic and Algebraic Computation (ISSAC '02,), pp. 75-83, 2002.
[8] M. Goresky and A. Klapper, “Arithmetic Crosscorrelation of Feedback with Carry Shift Register Sequences,” IEEE Trans. Information Theory, vol. 43, pp. 1342-1345, 1997.
[9] M. Goresky and A. Klapper, “Fibonacci and Galois Representation of Feedback with Carry Shift Registers,” IEEE Trans. Information Theory, vol. 48, pp. 2826-2836, 2002.
[10] S.-J. Kim, K. Umeno, and A. Hasegawa, “Corrections of the NIST Statistical Test Suite for Randomness,” Cryptology ePrint Archive: Report 2004/018, http://eprint.iacr.org/2004018, 2004.
[11] A. Klapper and M. Goresky, “2-adic Shift Registers,” Proc. Cambridge Security Workshop, Fast Software Encryption '93, R. Anderson, ed., pp. 174-178, 1993.
[12] A. Klapper and M. Goresky, “Cryptanalysis Based on 2-adic Rational Approximation,” Proc. CRYPTO '95, D. Coppersmith, ed., pp. 262-274, 1995.
[13] A. Klapper and M. Goresky, “Feedback Shift Registers, 2-adic Span, and Combiners with Memory,” J. Cryptology, vol. 10, pp. 11-147, 1997.
[14] A. Klapper and J. Xu, “Register Synthesis for Algebraic Feedback Shift Registers Based on Non-Primes,” Designs, Codes, and Cryptography, vol. 31, pp. 227-25, 2004.
[15] N. Koblitz, $p$ -adic Numbers, $p$ -adic Analysis and Zeta-Functions. Springer-Verlag, 1997.
[16] F.J. Macwilliams and N.J.A. Sloane, The Theory of Error Correcting Codes. North-Holland, 1986.
[17] J.L. Massey, “Shift Register Synthesis and BCH Decoding,” IEEE Trans. Information Theory, vol. 15, pp. 122-127, 1969.
[18] U.M. Maurer, “New Approaches of the Design of Self-Synchronizing Stream Ciphers,” Advances in Cryptology, Proc. EUROCRYPT '91, D.W. Davies, ed., pp. 458-471, 1991.
[19] J.W. Meier and O. Staffelbach, “Correlation Properties of Combiners with Memory in Stream Ciphers,” J. Cryptology, vol. 5, no. 1, pp. 67-86, 1992.
[20] NIST, A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications, http://csrc.nist.govrng/, 2001.
[21] R.A. Rueppel, “Correlation Immunity and the Summation Generator,” Advances in Cryptology, Proc. CRYPTO '85, H.C. Williams, ed., pp. 260-272, 1985.
[22] R.A. Rueppel, “Linear Complexity of Random Sequences,” Advances in Cryptology, Proc. EUROCRYPT '85, F. Pichler, ed., pp. 167-188, 1985.
[23] T. Siegenthaler, “Correlation-Immunity of Nonlinear Combining Functions for Cryptographic Applications,” IEEE Trans. Information Theory, vol. 30, pp. 776-780, 1984.
[24] T. Siegenthaler, “Cryptanalysts Representation of Nonlinear Filtered ML-Sequences,” Advances in Cryptology, Proc. EUROCRYPT '85, F. Pichler, ed. , pp. 103-110, 1985.
Index Terms:
Index Terms- Pseudorandom generator, shift register, 2-adic numbers, periodic sequences, secret key cryptography.
Citation:
Fran?ois Arnault, Thierry P. Berger, "Design and Properties of a New Pseudorandom Generator Based on a Filtered FCSR Automaton," IEEE Transactions on Computers, vol. 54, no. 11, pp. 1374-1383, Nov. 2005, doi:10.1109/TC.2005.181
