基于余數(shù)系統(tǒng)與置換多項(xiàng)式的高速長周期偽隨機(jī)序列生成方法
doi: 10.11999/JEIT170421
基金項(xiàng)目:
國家自然科學(xué)基金面上項(xiàng)目(61571083)
A Method of Generating High Speed and Long Period Pseudo-random Sequence Based on Residue
Funds:
The National Natural Science Foundation of China (61571083)
-
摘要: 低復(fù)雜度長周期數(shù)字偽隨機(jī)序列在現(xiàn)代加密、通信等系統(tǒng)中具有廣泛的應(yīng)用。該文提出一種基于余數(shù)系統(tǒng)和有限域置換多項(xiàng)式的偽隨機(jī)序列生成方法。該方法基于中國剩余定理將多個(gè)互質(zhì)的小周期有限域隨機(jī)序列進(jìn)行單射擴(kuò)展生成長周期數(shù)字偽隨機(jī)序列，置換多項(xiàng)式的迭代計(jì)算在多個(gè)并行的小動(dòng)態(tài)范圍有限域上進(jìn)行，從而降低了硬件實(shí)現(xiàn)中迭代環(huán)路的計(jì)算位寬，提高了生成速率。該文還給出構(gòu)建長周期偽隨機(jī)序列的置換多項(xiàng)式參數(shù)選擇方法和中國剩余定理優(yōu)化方法，在現(xiàn)有技術(shù)平臺(tái)下可輕易實(shí)現(xiàn)2100以上的序列周期。同時(shí)，該方法具有極大的迭代多項(xiàng)式選擇自由度，例如僅在q2(mod)3且q503的有限域上滿足要求的置換多項(xiàng)式就有10905種。硬件實(shí)現(xiàn)結(jié)構(gòu)簡單，基于Xilinx XC7Z020芯片實(shí)現(xiàn)290的隨機(jī)序列僅需20個(gè)18 kbit的BRAM和少量邏輯資源，無需乘法器，生成速率可達(dá)449.236 Mbps?；贜IST的測試表明序列具有良好的隨機(jī)特性。
-
關(guān)鍵詞:
- 偽隨機(jī)序列 /
- 余數(shù)系統(tǒng) /
- 置換多項(xiàng)式 /
- 高速 /
- 長周期 /
- 現(xiàn)場可編程邏輯門陣列
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. -
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. 胡劍浩, 馬上. 余數(shù)系統(tǒng)原理與在高速數(shù)字信號(hào)處理中的應(yīng)用[M]. 北京: 科學(xué)出版社, 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. 孫琦, 萬大慶. 置換多項(xiàng)式及其應(yīng)用[M]. 哈爾濱: 哈爾濱工業(yè)大學(xué)出版社, 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ī)數(shù)發(fā)生器研究[J]. 微電子學(xué)與計(jì)算機(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. -
計(jì)量
- 文章訪問數(shù): 1433
- HTML全文瀏覽量: 161
- PDF下載量: 169
- 被引次數(shù): 0
下載:
