隨機(jī)數(shù)在密碼學(xué)中占有重要的地位

設(shè)計(jì)一種超高速全數(shù)字真隨機(jī)數(shù)發(fā)生器，使用嵌入亞穩(wěn)態(tài)環(huán)節(jié)的環(huán)路振蕩器作為隨機(jī)源。對(duì)元胞自動(dòng)機(jī)電路進(jìn)行改良，向其中添加隨機(jī)存儲(chǔ)的特性，并將其作為后處理電路的一部分，提高了數(shù)據(jù)的熵值和偽隨機(jī)性。后級(jí)電路采用異或鏈電路和 DES 加密算法，提高隨機(jī)序列的每比特熵值，改善輸出的統(tǒng)計(jì)特性。該方案具有良好的可移植性，極高的生成速率，偏低的資源使用和自定義擴(kuò)展功能。通過 FPGA 版級(jí)驗(yàn)證，真隨機(jī)數(shù)生成速率可達(dá) 1 Gb/s，具有一定的應(yīng)用價(jià)值。

DOI：10.19339/j.issn.1674-2583.2020.04.006

一種基于隨機(jī)儲(chǔ)存元胞自動(dòng)機(jī)真隨機(jī)發(fā)生器［J］。集成電路應(yīng)用， 2020， 37（04）： 18-21.

True Random Generator Based on Random Storage Cell Automaton

JI Lei， PAN Weiqing， ZHI Yanan

Abstract — In this paper， a ultra-high-speed all-digital true random number generator is designed.The designer uses ring oscillators embedded in a metastable state as a random source. The cellular automaton circuit is improved， and the random storage feature is added to it as a part of the post-processing circuit， which improves the entropy value and pseudo-randomness of the data. The post-stage circuit uses XOR circuit and DES encryption algorithm to increase the entropy value of each bit of the random sequence and improve the statistical characteristics of the output. This solution has good portability， extremely high generation rate， low resource usage， and custom extension functions. Through FPGA-level verification， the true random number generation rate can reach 1 Gb/s， which has certain application value.

Index Terms — TRNG， ring oscillator， metastable state， cellular automata， DES， FPGA.

隨機(jī)數(shù)在密碼學(xué)中占有重要的地位，幾乎所有的密碼算法都要用到一些對(duì)攻擊者來說必須是秘密的數(shù)據(jù)，而其中密鑰必須是隨機(jī)數(shù)。隨著加解密技術(shù)的快速發(fā)展，基于軟件實(shí)現(xiàn)的偽隨機(jī)數(shù)發(fā)生器可能無法滿足安全性的要求，雖然基于物理隨機(jī)源的 TRNG 能保證安全性， 但其產(chǎn)生的真隨機(jī)數(shù)的質(zhì)量不高，生成速率偏慢?？紤]到 5G 時(shí)代的到來，基于區(qū)塊鏈、物聯(lián)網(wǎng)、車聯(lián)網(wǎng)、智慧城市技術(shù)的快速發(fā)展，海量的數(shù)據(jù)需要在信息交互節(jié)點(diǎn)進(jìn)行加密傳輸，這對(duì)真隨機(jī)數(shù)生成的速率有了更高的要求。

本文設(shè)計(jì)了一種超高速真隨機(jī)數(shù)發(fā)生器，其具有可移植性好，生成速率高，實(shí)現(xiàn)成本低廉的特點(diǎn)并具有自我擴(kuò)展特性。實(shí)際測(cè)試中，真隨機(jī)數(shù)生成速率高達(dá) 1 Gb/s，吞吐量/資源高于 1 Mb/LUT，遠(yuǎn)遠(yuǎn)高于常規(guī)真隨機(jī)數(shù)發(fā)生器吞吐量百兆級(jí)別，0.3 Mb/LUT 左右的性能。

1 真隨機(jī)整體設(shè)計(jì)

本文整體架構(gòu)如 所示，框架包括 5 部分：基于亞穩(wěn)態(tài)的環(huán)振器真隨機(jī)源，基于隨機(jī)儲(chǔ)存的元胞自動(dòng)機(jī)電路，異或鏈電路，DES 電路和千兆光口輸出單元。

J.D. Golic 最早提出 Fibonacci 和 Galois 環(huán)形振蕩器電路，但隨機(jī)數(shù)生成速率偏低。2008 年，I.Vasyltsov 等人在 Fibonacci 和 Galois 環(huán)形振蕩器的基礎(chǔ)上引入了亞穩(wěn)態(tài)結(jié)構(gòu)，減少所需熵的積累時(shí)間。文獻(xiàn)中，朱亮亮等人向其中引入控制環(huán)節(jié)，降低發(fā)生器功耗。本文隨機(jī)熵源采用方案。

控制信號(hào)為低電平時(shí)，大環(huán)路斷開，各反相器自成環(huán)路，受到半導(dǎo)體噪聲的影響，他們的輸出會(huì)在亞穩(wěn)態(tài)區(qū)域波動(dòng)。當(dāng)控制信號(hào)為高電平的時(shí)候，各反相器接入大環(huán)路，迅速離開亞穩(wěn)態(tài)區(qū)域，并進(jìn)入穩(wěn)態(tài)區(qū)域，此時(shí)其輸出具有隨機(jī)性。

二進(jìn)制系數(shù) fi 決定環(huán)振器的反饋連接。當(dāng) fi＝1 時(shí)，反饋連接；當(dāng) fi＝0 時(shí)，反饋斷開；反饋多項(xiàng)式可以表示為式。

（1）式中，n 為反相器個(gè)數(shù)。為了確保輸出不會(huì)恒定不變，多項(xiàng)式須滿足式。

必須保證 n 為奇數(shù)，h（x） 不能被 1+x 整除，且 f（x） 可以被 1+x 整除。如果反饋多項(xiàng)式為本原多項(xiàng)式則以上都可以滿足。

本文采用 36 個(gè) 7 階 Fibonacci 震蕩環(huán)，28 個(gè) 7 階 Galois 震蕩環(huán)作為真隨機(jī)源。7 階本原多項(xiàng)式共 18 個(gè)，重復(fù) 3.5 次使用，其輸出作為隨機(jī)儲(chǔ)存元胞自動(dòng)機(jī)電路的選擇輸入端。7 階本原多項(xiàng)式如 所示。

以上輸出的序列具有真隨機(jī)和偽隨機(jī)性，但數(shù)字熵源的統(tǒng)計(jì)特性往往不夠理想，在物理隨機(jī)過程采樣中，會(huì)引入偏差和相關(guān)性，所以需要添加后處理電路提減小偏差和相關(guān)性。

元胞自動(dòng)機(jī)的概念最初被 John von Neumann 和 Ulam 提出，并常用于物理、生物和化學(xué)的建模，也用于生成偽隨機(jī)序列，是常用的后處理算法之一。元胞自動(dòng)機(jī)是元胞的有限陣列，由相同的元胞組成，根據(jù)局部過度功能同步并行發(fā)展，且只能與他們最近的鄰居通信。其可以由四元組（Z，Q，V，f）所定義，其中 Z 代表 d 維的細(xì)胞空間，Q 代表可能元胞可能狀態(tài)組成的集合，V 表示局部規(guī)則使用的鄰域，f 代表本地規(guī)則。初始時(shí)，每個(gè)元胞都有一個(gè)初始狀態(tài)，根據(jù)本地規(guī)則和鄰域聯(lián)系，細(xì)胞狀態(tài)發(fā)生變化。

初級(jí)元胞自動(dòng)機(jī)是一個(gè)基本元胞自動(dòng)機(jī)，一維細(xì)胞空間 Z，元胞狀態(tài) Q＝{0，1}，鄰域 V＝（-1，0，1），本地規(guī)則 f：Q3→Q，Wolfram 在數(shù)學(xué)上證明了它作為高性能隨機(jī)數(shù)發(fā)生器的適用性，可以并行的有效實(shí)現(xiàn)，如式。

最上方三個(gè)方塊表示所有當(dāng)前時(shí)刻 n 可能的鄰域狀態(tài)，下一單元格代表下一時(shí)刻元胞輸出的狀態(tài)。本地規(guī)則被下一時(shí)刻序列的二進(jìn)制值所命名。

2014 年，一種基于儲(chǔ)存的元胞自動(dòng)機(jī)被提出，其中 x，y，z 為包括 0 的正整數(shù)［9］。元胞的下一狀態(tài)的輸出與相鄰元胞和本身的過去狀態(tài)有關(guān)，如式。

最近，一種基于隨機(jī)儲(chǔ)存的元胞自動(dòng)機(jī)被提出，Q＝{0，1}，鄰域 V＝（-1，0，1）。其中，τi是隨機(jī)值，其小于等于元胞儲(chǔ)存的狀態(tài)數(shù) M，元胞的下一狀態(tài)可以隨機(jī)地由當(dāng)前狀態(tài)，以及過去狀態(tài)確定，如式。

本文設(shè)計(jì)一個(gè)基于隨機(jī)儲(chǔ)存的元胞自動(dòng)機(jī)，其元胞儲(chǔ)存狀態(tài)數(shù) M 為 1，本地規(guī)則為 R150，其τi的值由上級(jí)的亞穩(wěn)態(tài)震蕩環(huán)的輸出決定。0 代表τi＝0，輸出當(dāng)前狀態(tài)；1 代表τi＝1，輸出上一狀態(tài)。其元胞單元電路如圖 5 所示。bit_out 為該元胞自動(dòng)隨機(jī)數(shù)的輸出端，連接到異或鏈電路。bit_i_m 為隨機(jī)儲(chǔ)存輸出端，連接與其相鄰的左右兩個(gè)元胞單元。

隨機(jī)儲(chǔ)存的元胞自動(dòng)機(jī)包含 64 個(gè)元胞環(huán)形連接，其相互連接圖如圖 6 所示，其中只有一個(gè) bit_i_m 初始值為 1。系統(tǒng)開始工作后，每個(gè)時(shí)鐘周期生成 64 個(gè) bit_out，每相鄰 8 位進(jìn)行異或壓縮操作，送入下級(jí)異或鏈電路中。

為了減小偏差，使得“0，1”分布均勻，采用異或鏈進(jìn)行處理，對(duì)數(shù)據(jù)進(jìn)行校正，結(jié)構(gòu)如圖 7 所示。本文采用 8 路異或鏈電路，每路由 8 個(gè)觸發(fā)器進(jìn)行異或鏈糾偏，每個(gè)時(shí)鐘周期輸出 8 bit 數(shù)據(jù)，輸出偏執(zhí)非常小。

1940 年代末，香農(nóng)提出了設(shè)計(jì)密碼系統(tǒng)的兩個(gè)基本方法-混淆和擴(kuò)散。擴(kuò)散和混淆可以極大改善輸出序列的統(tǒng)計(jì)特性，提高熵值，彌補(bǔ)統(tǒng)計(jì)缺陷。

設(shè)計(jì)中最后采用 DES 加密算法對(duì)數(shù)據(jù)進(jìn)一步后處理，為 DES 加密算法處理過程。首先對(duì)上級(jí)輸入的 8 bit 序列進(jìn)行數(shù)據(jù)重排，擴(kuò)展到 128 bit，高 64 bit 和低 64 bit 分別作為明文和密鑰輸入，進(jìn)行 IP 初始置換，然后 16 輪迭代變換，最后左右交換后進(jìn)行逆初始置換（IP-1）得到 64 bit密文，作為真隨機(jī)數(shù)輸出序列，16 輪迭代采用 Feistel 密碼結(jié)構(gòu)對(duì)明文和密鑰進(jìn)行混淆和擴(kuò)散。其中置換移位操作可獲得擴(kuò)散，非線性函數(shù) f 操作可獲得混淆。

2 實(shí)驗(yàn)驗(yàn)證

本文設(shè)計(jì)真隨機(jī)發(fā)生器在 FPGA 上進(jìn)行實(shí)驗(yàn)實(shí)現(xiàn)，型號(hào)為 xc7z035ffg676-2。外接輸入時(shí)鐘為 100 MHz，經(jīng)過 PLL 倍頻到 500 MHz 后，最后輸出真隨機(jī)輸出速率高達(dá) 1 Gb/s。實(shí)現(xiàn)過程中沒有使用任何布局布線約束，完全由設(shè)計(jì)軟件自動(dòng)處理。PC 端通過光口接受 126 組數(shù)據(jù)，每組 1 Mbit，使用NIST SP-800-22 隨機(jī)數(shù)測(cè)試套件進(jìn)行隨機(jī)性評(píng)估測(cè)試。測(cè)試規(guī)定當(dāng)測(cè)試通過率都大于 96 %時(shí)，則認(rèn)為通過該項(xiàng)測(cè)試；如果數(shù)據(jù)通過全部 15 項(xiàng)測(cè)試，則認(rèn)為序列是真隨機(jī)的。

為測(cè)試結(jié)果，數(shù)據(jù)完全通過試。

為體現(xiàn)本文所設(shè)計(jì)的真隨機(jī)數(shù)發(fā)生器的性能，本設(shè)計(jì)與國內(nèi)外已經(jīng)公開發(fā)表的真隨機(jī)數(shù)發(fā)生器進(jìn)行比較，其中單個(gè) LUT 資源相當(dāng)于一個(gè) LE 資源；可移植性的判斷是基于實(shí)現(xiàn)時(shí)是否使用特殊器件或手動(dòng)布局布線，如使用則移植性較差，對(duì)比結(jié)果如表 3 所示。在吞吐量方面，本文設(shè)計(jì)的真隨機(jī)數(shù)發(fā)生器遠(yuǎn)超常規(guī)數(shù)字發(fā)生器的百兆級(jí)別。吞吐量/邏輯資源比為 1.107 Mb/LUT，遠(yuǎn)大于常規(guī) 0.3 Mb/LUT，更加節(jié)省資源。移植性方面由于沒有使用特殊器件和物理約束實(shí)現(xiàn)，因此可以快速集成到芯片或 FPGA 當(dāng)中。

由于元胞自動(dòng)機(jī)結(jié)構(gòu)簡(jiǎn)單，易擴(kuò)展的特性，本文對(duì)該設(shè)計(jì)的自我擴(kuò)展性能進(jìn)行了實(shí)驗(yàn)驗(yàn)證，本文將 64 個(gè)元胞自動(dòng)機(jī)裁剪為 32 個(gè)、16 個(gè)，減少硬件資源分別為 143LUT、200LUT，并依次重新實(shí)現(xiàn)設(shè)計(jì)，生成速率分別為 500 Mb/s、250 Mb/s，結(jié)果均能通過 NIST SP800-22 測(cè)試。實(shí)驗(yàn)表明該隨機(jī)數(shù)發(fā)生器具有擴(kuò)展性能，使用者可以根據(jù)自己實(shí)際需求自我進(jìn)行裁剪或擴(kuò)展。

3 結(jié)語

本文介紹了一種新的數(shù)字真隨機(jī)數(shù)發(fā)生器，解決現(xiàn)有真隨機(jī)數(shù)發(fā)生器生成速率，資源消耗，可移植性和擴(kuò)展性無法全面的兼顧的問題。實(shí)際測(cè)試真隨機(jī)數(shù)生成速率可達(dá) 1 Gb/s，吞吐量/資源比為 1.1 Mb/LUT，遠(yuǎn)遠(yuǎn)高于常規(guī)真隨機(jī)發(fā)生器吞吐量的百兆級(jí)別和 0.3 Mb/LUT 的吞吐量/資源比。該方案純具有資源消耗低，吞吐量極高，可移植性好和可擴(kuò)展的特點(diǎn)。便于集成到芯片和 FPGA 中，縮短開發(fā)周期，具有很好的實(shí)際應(yīng)用價(jià)值，可滿足了未來區(qū)塊鏈、物聯(lián)網(wǎng)、車輛網(wǎng)、智慧城市中需要大量真隨機(jī)數(shù)進(jìn)行信息加密的場(chǎng)合。
責(zé)任編輯:pj