基于余数系统与置换多项式的高速长周期伪随机序列生成方法

马上; 刘剑锋; 杨泽国; 张艳; 胡剑浩

doi:10.11999/JEIT170421

基于余数系统与置换多项式的高速长周期伪随机序列生成方法

doi: 10.11999/JEIT170421

基金项目:

国家自然科学基金面上项目(61571083)

计量
- 文章访问数: 1394
- HTML全文浏览量: 148
- PDF下载量: 169
- 被引次数: 0
出版历程
- 收稿日期: 2017-05-08
- 修回日期: 2017-09-19
- 刊出日期: 2018-01-19

A Method of Generating High Speed and Long Period Pseudo-random Sequence Based on Residue

Funds:

The National Natural Science Foundation of China (61571083)

摘要

摘要: 低复杂度长周期数字伪随机序列在现代加密、通信等系统中具有广泛的应用。该文提出一种基于余数系统和有限域置换多项式的伪随机序列生成方法。该方法基于中国剩余定理将多个互质的小周期有限域随机序列进行单射扩展生成长周期数字伪随机序列，置换多项式的迭代计算在多个并行的小动态范围有限域上进行，从而降低了硬件实现中迭代环路的计算位宽，提高了生成速率。该文还给出构建长周期伪随机序列的置换多项式参数选择方法和中国剩余定理优化方法，在现有技术平台下可轻易实现2100以上的序列周期。同时，该方法具有极大的迭代多项式选择自由度，例如仅在q2(mod)3且q503的有限域上满足要求的置换多项式就有10905种。硬件实现结构简单，基于Xilinx XC7Z020芯片实现290的随机序列仅需20个18 kbit的BRAM和少量逻辑资源，无需乘法器，生成速率可达449.236 Mbps。基于NIST的测试表明序列具有良好的随机特性。
- 伪随机序列 /
- 余数系统 /
- 置换多项式 /
- 高速 /
- 长周期 /
- 现场可编程逻辑门阵列
Abstract: Low complexity and long period pseudo-random sequence is widely used in data encryption and communication systems. A method of generating pseudo-random sequence based on Residue Number System (RNS) and permutation polynomials over finite fields is proposed. This method extends several short period sequences into a long period digital pseudo-random sequence based on Chinese Remainder Theorem (CRT). Several short period sequences are generated by corresponding permutation polynomials over small finite fields parallelly, thereby reducing the bit width in hardware implementation and increased the generation speed. In order to generate long period sequences, a method to find the permutation polynomial and the the optimazition procedure for CRT are also proposed in this paper. Based on most of current hardware platforms, the proposed method can easily generate the pseudo-random sequence with period over 2100. Meanwhile, this method has large space to select polynomials. For example, 10905 permutation polynomials can be used whenq2(mod)3 and q503 . Based no Xilinx XC7Z020, it only costs 20 18 kbit BRAMs and a small amount of other resources (no multiplier) to generate a pseudo-random sequence whose period over 290, and the generation rate is over 449.236 Mbps. The results of NIST test show that the sequence has good random property and encryption performance.
- Pseudo-random sequence /
- Residue Number System (RNS) /
- Permutation polynomial /
- High speed /
- Long period /
- Field Programmable Gate Array (FPGA)

HTML全文

参考文献(18)

PEINADO A, MUNILLA J, and FSTERSABATER A. Optimal modes of operation of pseudorandom sequence generators based on DLFSRs[J]. Logical Journal of IGPL, 2016, 24(6): 933-943. doi: 10.1093/jigpal/jzw050.

NAWKHARE Rahul, TRIPATHI Amit, and POKLE Praveen. DS-SS communication system using pseudo chaotic sequences generator[C]. International Conference on Communication Systems and Network Technologies, Gwalior, 2013: 78-82.

De Figueiredo F A P, MATHILDE F S, CARDOSO F A C M, et al. Efficient FPGA-based implementation of a CAZAC sequence generator for 3GPP LTE[C]. International Conference on Reconfigurable Computing and Fpgas, Cancun, 2014: 1-6.

MANDAL K and GONG G. Feedback reconstruction and implementations of pseudorandom number generators from composited De Bruijn sequences[J]. IEEE Transactions on Computers, 2016, 65(9): 2725-2738. doi: 10.1109/TC.2015. 2506557.

SWAMI D S and SARMA K K. A logistic map based PN sequence generator for direct-sequence spread-spectrum modulation system[C]. International Conference on Signal Processing and Integrated Networks, Noida, 2014: 780-784.

ZHOU Y, HUA Z, PUN C M, et al. Cascade Chaotic System With Applications[J]. IEEE Transactions on Cybernetics, 2015, 45(9): 2001-2012. doi: 10.1109/TCYB.2014.2363168.

TALEB F. A new chaos based image encryption scheme using chaotic logistic maps[C]. International Conference on Multimedia Computing and Systems, Marrakech, 2014: 1222-1228.

SHUNSUKE Araki, HIDEYUKI Muraoka, TAKERU Miyazaki, et al. A design guide of renewal of a parameter of the Logistic map over integers on pseudorandom number generator[C]. International Symposium on Information Theory and Its Applications (ISITA), Monterey, 2016: 781-785.

CORINTO F, KRULIKOVSKYI O V, and HALIUK S D. Memristor-based chaotic circuit for pseudo-random sequence generators[C]. Mediterranean Electrotechnical Conference, Lemesos, 2016: 18-20. doi: 10.1109/MELCON.2016.7495319.

OLIVER N, CORNELLES Soriano M, SUKOW D W, et al. Fast random bit generation using a chaotic laser: Approaching the information theoretic limit[J]. Journal of Quantum Electronics IEEE, 2013, 49(11): 910-918. doi: 10.1109/JQE.2013.2280917.

CHESTER D B and MICHAELS A J. Digital generation of a chaotic numerical sequence[P]. Harris Corporation, Pub.US, No.20080263119A1.

MICHAELS A J. A maximal entropy digital chaotic circuit[C]. IEEE International Symposium on Circuits and Systems, Rio de Janeiro, 2011: 717-720.

胡剑浩, 马上. 余数系统原理与在高速数字信号处理中的应用[M]. 北京: 科学出版社, 2012: 80-100.

KHACHATRIAN G and KYUREGHYAN M. A new public key encryption system based on permutation polynomials[C]. IEEE International Conference on Cloud Engineering, Boston, 2014: 540-543.

孙琦, 万大庆. 置换多项式及其应用[M]. 哈尔滨: 哈尔滨工业大学出版社, 2012: 150-180.

BASSHAM Iii L E, RUKHIN A L, SOTO J, et al. SP 800-22 Rev. 1a. A statistical test suite for random and pseudorandom number generators for cryptographic applications[J]. Nist Special Publication, 2010.

许栋, 崔小欣, 王田, 等. 基于Logistic映射的混沌随机数发生器研究[J]. 微电子学与计算机, 2016(2): 1-6.

XU Dong, CUI Xiaoxin, WANG Tian, et al. Research on chaotic random bit generator based on Logistic map[J]. Microelectronics Computer, 2016(2): 1-6.

施引文献

资源附件(0)

访问统计