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

doi:10.11999/JEIT170421

Abstract
Figure/Table
References (17)
Related Citation (15)

Download: PDF (277 KB)
Export: BibTeX | EndNote (RIS)

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 2¹⁰⁰. Meanwhile, this method has large space to select polynomials. For example, 10905 permutation polynomials can be used when q≡2(mod)3 and q≤503 . 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 2⁹⁰, 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.

Key words： Pseudo-random sequence Residue Number System (RNS) Permutation polynomial High speed Long period Field Programmable Gate Array (FPGA)

Received: 08 May 2017 Published: 01 November 2017

PACS:

TN918.2

Fund:The National Natural Science Foundation of China (61571083)

Corresponding Authors: MA Shang E-mail: mashang@uestc.edu.cn

	Service

	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	MA Shang
	LIU Jianfeng
	YANG Zeguo
	ZHANG Yan
	HU Jianhao

Cite this article:

MA Shang,LIU Jianfeng,YANG Zeguo等. A Method of Generating High Speed and Long Period Pseudo-random Sequence Based on Residue[J]. JEIT, 2018, 40(1): 42-49.

URL:

http://jeit.ie.ac.cn/EN/10.11999/JEIT170421 OR http://jeit.ie.ac.cn/EN/Y2018/V40/I1/42

[1]	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.
[2]	PEINADO A, MUNILLA J, and FÚSTERSABATER 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.
[3]	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.
[4]	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.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	CHESTER D B and MICHAELS A J. Digital generation of a chaotic numerical sequence[P]. Harris Corporation, Pub.US, No.20080263119A1.
[12]	MICHAELS A J. A maximal entropy digital chaotic circuit[C]. IEEE International Symposium on Circuits and Systems, Rio de Janeiro, 2011: 717-720.
[13]	胡剑浩, 马上. 余数系统原理与在高速数字信号处理中的应用[M]. 北京: 科学出版社, 2012: 80-100.
[14]	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.
[15]	孙琦, 万大庆. 置换多项式及其应用[M]. 哈尔滨: 哈尔滨工业大学出版社, 2012: 150-180.
[16]	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.
[17]	许栋, 崔小欣, 王田, 等. 基于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.