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 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 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.
马上, 刘剑锋, 杨泽国, 张艳, 胡剑浩. 基于余数系统与置换多项式的高速长周期伪随机序列生成方法[J]. 电子与信息学报, 2018, 40(1): 42-49.
MA Shang, LIU Jianfeng, YANG Zeguo, ZHANG Yan, HU Jianhao. A Method of Generating High Speed and Long Period Pseudo-random Sequence Based on Residue. JEIT, 2018, 40(1): 42-49.
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.
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.
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.
