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

doi:10.3778/j.issn.1673-9418.1306027

计算机科学与探索 ›› 2014, Vol. 8 ›› Issue (1): 28-39.DOI: 10.3778/j.issn.1673-9418.1306027

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

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

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

出版日期:2014-01-01 发布日期:2014-01-03

Fast Programming Algorithm to Find Non-Linear Feedback Shift Register

YE Weichen1,2, CHEN Kefei3,4+

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

摘要/Abstract

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

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

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)

叶炜晨，陈克非. 快速寻找非线性反馈移位寄存器的编程算法[J]. 计算机科学与探索, 2014, 8(1): 28-39.

YE Weichen, CHEN Kefei. Fast Programming Algorithm to Find Non-Linear Feedback Shift Register[J]. Journal of Frontiers of Computer Science and Technology, 2014, 8(1): 28-39.

[1]	李秉政，黄高阳，许瑾晨. 面向申威众核处理器的LZMA并行算法设计与优化[J]. 计算机科学与探索, 2020, 14(9): 1501-1509.
[2]	刘徐，肖志勇，甘霖，徐敬蘅，陈宏博. 神威国产处理器应用程序的并行参数自动寻优[J]. 计算机科学与探索, 2020, 14(11): 1838-1848.
[3]	李勇，滕飞，黄齐川，李天瑞. 基于Spark的时间序列并行分解模型[J]. 计算机科学与探索, 2018, 12(7): 1055-1063.
[4]	景翠萍，廖丽，王伟. 面向非结构网格应用并行程序的编程工具[J]. 计算机科学与探索, 2018, 12(2): 252-262.
[5]	韩超，段磊，邓松，王慧锋，唐常杰. 基于Spark的序列数据质量评价[J]. 计算机科学与探索, 2017, 11(6): 897-907.
[6]	王涛，胡双林. 材料科学中的高性能计算[J]. 计算机科学与探索, 2017, 11(2): 185-193.
[7]	郝赫，司雨蒙，韦建文，文敏华，林新华. 天体物理成团研究中的非规则访存优化[J]. 计算机科学与探索, 2017, 11(1): 80-90.
[8]	揭月馨，刘浩. 融合有向图集与并行架构的HEVC去块滤波[J]. 计算机科学与探索, 2016, 10(9): 1221-1228.
[9]	詹杭龙，曹东刚，谢冰. 分布共享环境下支持弹性伸缩的图处理框架[J]. 计算机科学与探索, 2016, 10(7): 901-914.
[10]	赵莲，赵永华，陈尧，赵慰. GPU集群加速近似逆预条件CG并行求解器[J]. 计算机科学与探索, 2015, 9(9): 1084-1092.
[11]	赵慰，赵永华，刘晓辉，何力新. 第一性原理计算软件包在GPU集群上的加速[J]. 计算机科学与探索, 2014, 8(8): 897-905.
[12]	林娟，杜庆良，杨辉，钟一文. 基于粒子群优化算法的并行模拟退火算法[J]. 计算机科学与探索, 2014, 8(7): 886-896.
[13]	韦向远，杨辉华，谢谱模. 基于CUDA的并行布谷鸟搜索算法设计与实现[J]. 计算机科学与探索, 2014, 8(6): 665-673.
[14]	师金钢，郑艳，孙焕良，栾方军. 云环境中海量数据的并行分组密码体制研究[J]. 计算机科学与探索, 2014, 8(2): 161-170.
[15]	吴再龙，张云泉，徐建良，贾海鹏，颜深根，解庆春. 基于OpenCL的Kmeans算法的优化研究[J]. 计算机科学与探索, 2014, 8(10): 1162-1176.

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

Fast Programming Algorithm to Find Non-Linear Feedback Shift Register

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics