Journal of Frontiers of Computer Science and Technology ›› 2014, Vol. 8 ›› Issue (1): 28-39.DOI: 10.3778/j.issn.1673-9418.1306027

Previous Articles     Next Articles

Fast Programming Algorithm to Find Non-Linear Feedback Shift Register

YE Weichen1,2, CHEN Kefei3,4+   

  1. 1. Cryptography and Information Security Laboratory, Shanghai Jiao Tong University, Shanghai 200240, China
    2. Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
    3. Faculty of Science, Hangzhou Normal University, Hangzhou 310036, China
    4. Science and Technology on Communication Security Laboratory, Chengdu 610041, China
  • Online:2014-01-01 Published:2014-01-03

快速寻找非线性反馈移位寄存器的编程算法

叶炜晨1,2,陈克非3,4+   

  1. 1. 上海交通大学 密码学与信息安全实验室,上海 200240
    2. 上海交通大学 计算机科学与工程系,上海 200240
    3. 杭州师范大学 理学院,杭州 310036
    4. 保密通信重点实验室,成都 610041

Abstract: Non-linear feedback shift register (NLFSR) is a common device to generate pseudo-random sequences in stream cipher. However, there is still no effective mathematical algorithm to find NLFSRs for a given period or output sequence. This paper provides a quick method to find NLFSRs. This method is a programming algorithm based on compute unified device architecture (CUDA) and parallel computing, and can quickly find NLFSRs for the given period or output sequence. This method has very good performance on both simple and complex NLFSRs. With this new method, people can easily get a large amount of experimental data about NLFSRs. It will be a great help for the future research on the mathematical algorithm to find NLFSRs.

Key words: parallel computing, pseudo-random sequence, compute unified device architecture (CUDA), non-linear feedback shift register (NLFSR)

摘要: 在流密码中,非线性反馈移位寄存器(non-linear feedback shift register,NLFSR)是一种常用的安全性较高的伪随机序列生成器。目前仍然没有一种普遍有效的数学算法,能够根据给定的序列或者序列周期,直接推导出NLFSR。提出了一种快速寻找NLFSR的编程算法。该算法基于统一计算架构(compute unified device architecture,CUDA)和并行计算来实现,计算速度快,尤其适用于处理高次数的复杂NLFSR。并且该算法可以快速大规模地计算出NLFSR,为未来研究寻找NLFSR的数学算法提供了大量的实验数据。

关键词: 并行计算, 伪随机序列, 统一计算架构(CUDA), 非线性反馈移位寄存器(NLFSR)