The Journal of the Korea institute of electronic communication sciences (한국전자통신학회논문지)

Korea Institute of Electronic Communication Science (한국전자통신학회)
권호 표지
DOI QR코드

DOI QR Code

Attack using Phase Shifts of Shrunken Sequence

수축수열의 위상이동차 공격법

  • 최언숙 (동명대학교 미디어공학과) ;
  • 조성진 (부경대학교) ;
  • 황윤희 (부경대학교 응용수학과) ;
  • 김한두 (인제대학교 컴퓨터응용과학부, 기초과학연구소)
  • Received : 2010.12.13
  • Accepted : 2011.02.09
  • Published : 2011.02.28
Download PDF
⟨ Previous Next ⟩

Abstract

Pseudo-random sequences with high linear complexity and low correlation function values are widely used in communication and cryptology. In this paper, we study the properties of interleaved sequences generated by shrinking generator. And we give a method for obtaining the shrunken sequence from a partial description of the shrunken sequence by using the phase shifting of PN sequences generated by shrinking generator.

높은 선형복잡도와 낮은 상관관계를 갖는 의사난수열은 통신 및 암호에 널리 사용된다. 본 논문에서는 수숙생성기에 의해 생성된 수축수열을 삽입수열로 해석하여 분석하고 후 위상이동차를 분석하여 수축수열의 일부 정보로부터 수축수열 모두를 알아내는 방법을 제안한다.

Keywords

References

  1. S. M. Jennings, "Multiplexed sequences: Some properties of the minimum polynomial," in Proc. EUROCRYPTO'82 Lecture Notes in Computer Science, vol. 149. New York: Springer_Verlag, 1983.
  2. T. Beth and F. Piper, "The stop-and-go generator" in Advances in Cryptology, Proc. EUROCRYPTO'84. New York: Springer- Verlag, 1985.
  3. D. Coppersmith, H. Krawczyk and Y. Mansour, "The shrinking generator," in; Proc. CRYPTO'93, in: LNCS 773, Springer-Verlag, pp. 22-39, 1994.
  4. A. Fuster-Sabater, P. Caballero-Gil, "Concatenated automata in cryptanalysis of stream ciphers," Proc. of ACRI 2006, LNCS 4173, Springer-Verlag, pp. 611-616, 2006.
  5. A. Fuster-Sabater and D. Guia-Martinez, "Modelling nonlinear sequence generators in terms of linear cellular automata," Applied Mathematical Modelling, 31 pp.226-235. 2007. https://doi.org/10.1016/j.apm.2005.08.013
  6. A. Fuster-Sabater and P. Caballero-Gil, "Synthesis of cryptographic interleaved sequences by means of linear cellular automata," Applied Mathematics Letters 22, pp.1518-1524, 2009. https://doi.org/10.1016/j.aml.2009.03.018
  7. S. A. Tretter, "Properties of PN2 sequences," IEEE Trans. Inform. Theory, vol. IT-20, pp. 295-297, 1974.
  8. F. J. MacWilliams and N. J. A. Sloane, "Pseudo-random sequences and arrays," Proc. IEEE, vol. 64, no. 12, pp. 1715-1729, Dec. 1976. https://doi.org/10.1109/PROC.1976.10411
  9. T. Kasami, "Weight distribution formula for some class of cyclic codes," Coordinated Sci. Lab., Univ. of Illinois, Urbana, Tech. Rep. R-285 (AD632574), 1966.
  10. R. A. Scholtz and L. R. Welch, "GMW sequences," IEEE Trans. Inform. Theory, vol. IT-30, no. 3, pp. 548-553, May 1984.
  11. A. Klapper, A.H. Chan, and M. Goresky, "Cascaded GMW sequences," IEEE Trans. Inform. Theory, vol. 39, no. 1, pp. 177-183, Jan. 1993. https://doi.org/10.1109/18.179353
  12. J. S. No and P. V. Kumar, "A new family of binary pseudo random sequences having optimal periodic correlation properties and large linear span," IEEE Trans. Inform. Theory, vol. 35, no. 2, pp. 371-379, Mar 1989. https://doi.org/10.1109/18.32131
  13. G. Gong, "Theory and applications of q-ary interleaved sequences," IEEE Trans. Inform. Theory 41(2), pp. 400-411, 1995. https://doi.org/10.1109/18.370141
  14. S. J. Cho et al., "Computing phase shifts of maximum-length 90/150 cellular automata," in: Proc. ACRI 2004, in: LNCS 3305, Springer-Verlag, pp.31-39, 2004.
  15. R. Lidi and H. Niederreiter, Finite fields, Encyclopaedia of Mathematics and its Applications, Vol. 20. Reading, MA: Addison-Wesley, 1983.
  16. 조성진, 최언숙, 김한두, 안현주, "수축생성기에 기반한 비선형 수열의 분석," 한국전자통신학회, 5(4), pp. 412-417, 2010.