In the modern world of secure communication, there is ever growing need for faster transfer of data. One way to accomplish this task is by trading negligible space in a communication device with the time requirement for an implementation. In this article, Feedback Shift Registers (FSRs) which forms one of the most important primitives in any of the stream cipher designs is studied from this viewpoint. Two of the major operations in FSR are calculating the feedback and then shifting the contents of register. It has been proven mathematically that in the classical definition of FSR, be it in Galois or Fibonacci mode, clocking can be replaced by a procedure which outputs the same feedback without actually having to shift register’s contents. It has been shown experimentally that the shifting operation which is the dominant time consuming step can be reformulated. With this trick shifting process can be completely avoided helping in reduction of running time although it might increase space complexity linearly which is a small cost with respect to the time consumption. The main result of article is the reformulation of notion of FSRs and then how this reformulation helps in efficient implementation of FSRs on any device.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Reformulation of Feedback Shift Register from Practical Viewpoint

  • Prasanna R. Mishra,
  • Nupur Gupta,
  • Navneet Gaba

摘要

In the modern world of secure communication, there is ever growing need for faster transfer of data. One way to accomplish this task is by trading negligible space in a communication device with the time requirement for an implementation. In this article, Feedback Shift Registers (FSRs) which forms one of the most important primitives in any of the stream cipher designs is studied from this viewpoint. Two of the major operations in FSR are calculating the feedback and then shifting the contents of register. It has been proven mathematically that in the classical definition of FSR, be it in Galois or Fibonacci mode, clocking can be replaced by a procedure which outputs the same feedback without actually having to shift register’s contents. It has been shown experimentally that the shifting operation which is the dominant time consuming step can be reformulated. With this trick shifting process can be completely avoided helping in reduction of running time although it might increase space complexity linearly which is a small cost with respect to the time consumption. The main result of article is the reformulation of notion of FSRs and then how this reformulation helps in efficient implementation of FSRs on any device.