基于量子元胞自動機(jī)的真隨機(jī)數(shù)發(fā)生器設(shè)計(jì)

秦亞辰, 解光軍

(合肥工業(yè)大學(xué) 電子科學(xué)與應(yīng)用物理學(xué)院,安徽 合肥 230601)

隨著微納電子器件技術(shù)的蓬勃發(fā)展,在后摩爾定律時(shí)代,尋找晶體管電路的理想替代者,一直是熱門的研究問題。文獻(xiàn)[1]提出了鋁量子點(diǎn)元胞自動機(jī)模型,此后關(guān)于量子元胞自動機(jī)(quantum-dot cellular automata,QCA)電路的設(shè)計(jì)和研究成果層出不窮?；趽穸噙壿媅2-4]為基礎(chǔ)邏輯的QCA電路可以實(shí)現(xiàn)類似于經(jīng)典電路中的“與”“或”功能,輔以其獨(dú)特的時(shí)鐘循環(huán)機(jī)制[5]加以分割時(shí)序,亦可構(gòu)建時(shí)序邏輯單元,時(shí)鐘同時(shí)也為QCA電路提供能量,QCA時(shí)鐘和傳輸線原理如圖1所示。

圖1 QCA時(shí)鐘和傳輸線原理

隨機(jī)數(shù)發(fā)生器(random number generator,RNG)模塊在信息安全領(lǐng)域具有極其重要的應(yīng)用價(jià)值,從經(jīng)典的分組密碼加密算法來看,不管是基于Feistel函數(shù)輪迭代的DES加密算法還是基于SP函數(shù)的AES算法,其密鑰組成部分的選擇尤為重要,要保證每輪通過移位置換操作生成的子密鑰與明文進(jìn)行異或運(yùn)算后生成的密文不易被攻擊者破解,對初始密鑰的隨機(jī)性具有較高的要求。相比較而言,序列密碼加密算法更加傾向于逐位(bit)操作,其理論和技術(shù)已經(jīng)十分成熟,且更容易硬件實(shí)現(xiàn)。

序列密碼加密算法是簡單的對合運(yùn)算,屬于對稱密碼的范疇,收發(fā)雙方使用同一套密鑰進(jìn)行加密解密操作,加密解密過程即為簡單的模二加運(yùn)算,因此它對產(chǎn)生密鑰的隨機(jī)性具有很高的要求,可以說RNG每次產(chǎn)生密鑰序列的隨機(jī)性直接關(guān)系著加密的安全性。

在密碼學(xué)領(lǐng)域,自同步序列密碼加密解密過程常用的隨機(jī)數(shù)發(fā)生器為線性反饋移位寄存器,linear feedback shift register,LFSR)[6],在GF(2n)有限域上選取適當(dāng)?shù)谋驹囗?xiàng)式作為反饋函數(shù),產(chǎn)生的M序列最大周期T=2n-1,當(dāng)T足夠大時(shí)(遠(yuǎn)大于每次采樣的密鑰流的位數(shù)K),則可以認(rèn)為生成的序列是隨機(jī)的。

類似于LFSR的偽隨機(jī)數(shù)發(fā)生器(pseudo-random number generator,PRNG)實(shí)現(xiàn)方案有很多種,PRNG生成的密鑰流完全取決于“種子”序列和加密算法,理想的PRNG需要保證其算法的優(yōu)異性能,使得生成序列在頻率測試中保證“0”“1”出現(xiàn)的概率接近50%,同時(shí)要盡可能確保每次更換的“種子”序列隨機(jī)。否則在長期的信道攻擊下很可能被黑客掌握足夠的數(shù)據(jù),破解加密算法的規(guī)律。

相比較而言,真隨機(jī)數(shù)發(fā)生器(ture random number generator,TRNG)則可以避免上述問題,達(dá)到香農(nóng)提出的“一次一密”無條件安全的效果,自然界中有許多物理過程的演化規(guī)律是天然的隨機(jī)源,如放射性衰變的脈沖周期和晶體管的熱噪聲等。

本文基于QCA元胞在傳導(dǎo)極化過程中存在的不確定性因素作為隨機(jī)源,設(shè)計(jì)TRNG電路,并對生成的序列進(jìn)行隨機(jī)性測試。

1 相關(guān)工作

1.1 QCA交叉耦合結(jié)構(gòu)

交叉耦合結(jié)構(gòu)[7-8]是QCATRNG設(shè)計(jì)的重要組成單元之一,如圖2所示。文獻(xiàn)[7]利用2個(gè)XNOR門和2個(gè)循環(huán)延遲結(jié)構(gòu)設(shè)計(jì)1-bit的交叉耦合電路,該電路有一位的輸入和輸出,當(dāng)輸入CLK=0時(shí),輸出結(jié)果Qn=Qn-1,保持穩(wěn)定狀態(tài);當(dāng)CLK的狀態(tài)從0→1時(shí),由于QCA傳輸線環(huán)路信號的時(shí)鐘延遲特性,導(dǎo)致接下來的每一個(gè)時(shí)鐘周期Qn的值出現(xiàn)振蕩,這種環(huán)路振蕩的現(xiàn)象是將來每一位產(chǎn)生隨機(jī)序列的根源。

圖2 文獻(xiàn)[7-8]提出的交叉耦合結(jié)構(gòu)

只要將每一級輸入不確定性的異步時(shí)鐘信號CLKi作為“觸發(fā)源”,在下一個(gè)時(shí)鐘周期輸出的Qi的值保持和反轉(zhuǎn)的概率就各為50%,即可以實(shí)現(xiàn)生成真隨機(jī)數(shù)的效果。文獻(xiàn)[8]提出了基于交叉耦合結(jié)構(gòu)的改進(jìn)型電路。

所謂驅(qū)動下一級的不確定性異步時(shí)鐘信號就需要交叉導(dǎo)向(cross-oriented)結(jié)構(gòu)[7-8]來產(chǎn)生。

1.2 QCA交叉導(dǎo)向結(jié)構(gòu)

新型的交叉耦合單元結(jié)構(gòu)的原理圖、版圖及仿真結(jié)果如圖3所示,交叉導(dǎo)向結(jié)構(gòu)的2個(gè)輸入端為A、B,其對中心元胞C的影響決定了輸出端OUT被賦予的邏輯值。

根據(jù)靜電累積原理[9]可以證明,當(dāng)A?B=0時(shí),C的狀態(tài)穩(wěn)定;當(dāng)A?B=1時(shí),輸入端對中心元胞作用的總能量ET大致相等而抵消,因此元胞最終的輸出狀態(tài)不確定,即可以誘導(dǎo)中心元胞的亞穩(wěn)態(tài)來作為驅(qū)動下一級交叉耦合結(jié)構(gòu)的異步時(shí)鐘,這是QCA元胞自帶的物理屬性。文獻(xiàn)[7-8]以及本文提出的交叉導(dǎo)向結(jié)構(gòu)的性能對比見表1所列。

表1 幾種交叉耦合結(jié)構(gòu)的性能參數(shù)對比

2 新型的TRNG電路設(shè)計(jì)

2.1 新型單元結(jié)構(gòu)的設(shè)計(jì)與分析

基于1.1節(jié)對1-bit交叉耦合結(jié)構(gòu)的分析可以得出:當(dāng)CLK=0時(shí),電路的輸出OUT處于鎖存狀態(tài);當(dāng)CLK=1時(shí),在高電平脈沖到來的下一個(gè)時(shí)鐘周期,信號被反轉(zhuǎn),此后一直振蕩,直到低電平信號到來的下一個(gè)時(shí)鐘周期截止。根據(jù)此原理,可以直接利用現(xiàn)有的QCA2-input異或門[10]結(jié)構(gòu),輔以合適的延遲線路,實(shí)現(xiàn)交叉耦合結(jié)構(gòu)原有的輸出邏輯關(guān)系,即

Ot+1=CLK⊕Ot

(1)

其中:Ot+1為t+1時(shí)的OUT;CLK為CLK;Ot為t時(shí)的OUT。

2.2 TRNG電路的原理

在完成對交叉耦合結(jié)構(gòu)的設(shè)計(jì)之后,再利用1.2節(jié)中提到的交叉導(dǎo)向結(jié)構(gòu)便可以實(shí)現(xiàn)位拓展的功能,構(gòu)建n-bit(n=2k,k∈Z+)TRNG電路,QCA雙8-bit TRNG電路如圖4所示。這里n為偶數(shù),是為了使設(shè)計(jì)的電路更加對稱工整。該TRNG電路在一個(gè)時(shí)鐘周期循環(huán)內(nèi)可以一次性產(chǎn)生2組不同的k-bit真隨機(jī)數(shù)密鑰,這2組密鑰之間相互獨(dú)立存在。電路唯一的輸入即為CLK,當(dāng)設(shè)備工作時(shí),CLK可以人為設(shè)置一組0/1序列作為“種子”輸入。

圖4 QCA雙8-bit TRNG電路

不同于PRNG電路,此時(shí)CLK作為種子輸入的作用被弱化到僅僅具有開關(guān)的意義,每次啟動設(shè)備時(shí),由于QCA循環(huán)延遲電路自身的物理屬性,賦予初始值的“抽頭序列”會隨著元胞傳遞極化值而瞬態(tài)響應(yīng),最終建立起穩(wěn)定的狀態(tài)被隨機(jī)分配為“0”“1”的輸出,與圖2所示的2種結(jié)構(gòu)相比較,新型的交叉耦合結(jié)構(gòu)電路被簡化了。延遲、功耗、所消耗的元胞數(shù)目和電路面積都進(jìn)一步減小。顯然,利用新的單元結(jié)構(gòu)的位拓展設(shè)計(jì)n-bit TRNG電路將獲得更加優(yōu)化的量子成本。因此該TRNG電路每次啟動的初始值是一個(gè)k-bit的真隨機(jī)數(shù),再加上交叉導(dǎo)向結(jié)構(gòu)對每一級電路異步時(shí)鐘信號(CLKi)的隨機(jī)性誘導(dǎo),便可以保證每一級輸出“0”“1”的概率相等。

QCA雙8-bit TRNG隨機(jī)一次測試的仿真結(jié)果如圖5所示。

圖5 QCA雙8-bitTRNG隨機(jī)一次測試的仿真結(jié)果

設(shè)存在一個(gè)2k-bit(k∈Z+)的該類TRNG電路,在設(shè)定輸出隨機(jī)序列的選擇方法上,首先假設(shè)OUT[O1,O2,O3,…,O2k-1,O2k]為目標(biāo)的隨機(jī)序列,其中OUT可以表示為GF(22k)有限域上的一個(gè)特征多項(xiàng)式。

由交叉導(dǎo)向結(jié)構(gòu)提供的異步時(shí)鐘信號CLKi(0≤i≤k),輸出值為0或1的概率各為50%,盡管如此,驅(qū)動第i級交叉耦合結(jié)構(gòu)的輸出值卻只有保持或者反轉(zhuǎn)2種方式,即

00→00/11,01→01/10,10→10/01,11→00/11。

假設(shè)在任意時(shí)刻采樣到了一組OUT的值,其中00、01、10、11的個(gè)數(shù)分別為a、b、c、d。根據(jù)馬爾可夫矩陣可以推導(dǎo)出以下關(guān)系:

(2)

經(jīng)過p(p≥1)次輪迭代之后,輸出序列OUTp中2個(gè)連續(xù)位上00、01、10、11共4種狀態(tài)分別對應(yīng)的個(gè)數(shù)即為等式右邊行向量的每個(gè)元素。此時(shí)OUTp取值的可能性共有:

(3)

設(shè)a+d=m,b+c=k-m。根據(jù)Γ函數(shù)對(3)式分母進(jìn)行展開,則有:

(4)

根據(jù)上述推導(dǎo)過程可以得知,按照文獻(xiàn)[7-8]中的輸出設(shè)置,OUT[O1,O2,O3,…,O2k-1,O2k]一次理論上最大只能產(chǎn)生2k種可能的真隨機(jī)數(shù),其電路使用的量子成本并非最優(yōu)化,因?yàn)榇嬖?k個(gè)輸出位,相當(dāng)于每次設(shè)備開始工作時(shí),所以其隨機(jī)的初始狀態(tài)OUT決定了輸出在一個(gè)固定的循環(huán)中演化,而這樣的初始狀態(tài)也存在2k種。

對現(xiàn)有的TRNG電路輸出設(shè)置進(jìn)行改進(jìn),取OUT1[O1,O3, …,O2k-1]和OUT2[O2,O4, …,O2k]2組相互獨(dú)立的k-bit輸出序列作為最終的輸出值,通過分析可以得出,2組序列中任意一位每次在異步時(shí)鐘信號的誘導(dǎo)下,輸出0/1的概率皆為5%,服從概率空間I上嚴(yán)格的均勻分布。且2組序列對應(yīng)的初始狀態(tài)皆隨機(jī)且相互獨(dú)立?，F(xiàn)引入自信息量[11]和無條件熵[12]的概念,即

I(xi)=-lbp(xi)

(5)

(6)

其中,xi為概率空間上任一元素。自信息量在密鑰序列發(fā)出之前可以表示信源的不確定度。

(7)

當(dāng)且僅當(dāng)Pi=1/n時(shí)H(X)取極大值。本文提出的輸出位改進(jìn)模型對應(yīng)如下運(yùn)算關(guān)系:

(8)

(9)

當(dāng)且僅當(dāng)p=1-p時(shí),無條件熵取極大值1。此時(shí)p=0.5。因此在QCATRNG電路中,按照上述方法輸出OUT的值,理論上可以使系統(tǒng)輸出獲得最大的不確定度。

3 電路性能的測試與仿真

n-bit(n=2k,k∈Z+)TRNG電路一個(gè)時(shí)鐘周期內(nèi)能夠產(chǎn)生2組相互獨(dú)立的k-bit的隨機(jī)序列,在實(shí)際應(yīng)用的過程中結(jié)合QCA并/串結(jié)構(gòu)[13]或是移位寄存器組來實(shí)現(xiàn)密鑰流的輸出,因?yàn)楝F(xiàn)有的工藝水平以及仿真軟件功能的限制,所以只能對生成的結(jié)果進(jìn)行局部的隨機(jī)性測試。測試對象為雙8-bit TRNG電路(圖4),設(shè)置16個(gè)時(shí)鐘周期循環(huán),取其中任意一組輸出矢量OUT1,經(jīng)過并/串轉(zhuǎn)換之后生成16 byte的密鑰流(圖5)。

根據(jù)上述仿真結(jié)果,取OUT1作為被測數(shù)據(jù),測試手段為美國國家標(biāo)準(zhǔn)技術(shù)研究院(National Institute of Standards and Technology,NIST)提供的幾種指標(biāo)[14]。

NIST隨機(jī)性測試標(biāo)準(zhǔn)見表2所列。

表2 NIST隨機(jī)性測試標(biāo)準(zhǔn)

經(jīng)過局部的隨機(jī)性測試,產(chǎn)生的16 byte密鑰流對應(yīng)的測量參數(shù)Pvalue≥0.01,證明生成的序列具有隨機(jī)性。測試過程中涉及到的重要函數(shù)為誤差函數(shù)(erfc)、非完全伽馬函數(shù)(igamc),其數(shù)據(jù)處理和計(jì)算結(jié)果由matlab函數(shù)庫提供支持。

4 結(jié) 論

本文結(jié)合QCA自身的物理性質(zhì),對原有的交叉耦合結(jié)構(gòu)進(jìn)行了深入的分析,利用其輸出特性,在原有的基礎(chǔ)上進(jìn)行了邏輯綜合優(yōu)化[15],設(shè)計(jì)了一種新型的QCA TRNG單元結(jié)構(gòu),該結(jié)構(gòu)具有元胞面積小、低延遲的特性,且便于進(jìn)行位拓展的操作。雙8-bit TRNG電路基于簡化的單元結(jié)構(gòu)和交叉導(dǎo)向結(jié)構(gòu)共同實(shí)現(xiàn)。對輸出位的設(shè)置相比較之前的工作來看,通過數(shù)學(xué)推導(dǎo)證明了選取奇數(shù)位和偶數(shù)位獨(dú)立輸出可以使系統(tǒng)獲得最大的不確定度。

目前相關(guān)的工作仍然存在一些問題尚待解決。QCATRNG電路是采用并行輸出方式的,即一個(gè)時(shí)鐘周期產(chǎn)生k-bit的輸出序列,這就需要利用并串技術(shù)把生成的一組輸出矢量轉(zhuǎn)化為密鑰流同明文進(jìn)行逐位加密,這一過程必然會增加通信電路整體的時(shí)序冗余,但是并行的輸出結(jié)果如果應(yīng)用于分組密碼加密系統(tǒng),那么可以省去輪密鑰生成算法中置換、移位等線性操作,相當(dāng)于每一輪的加密都使用了獨(dú)立的密鑰,這就讓分組密碼機(jī)制中除了S-box之外,又增加了另一個(gè)非線性因素,對加密的安全性有著本質(zhì)的提升,而且在每一輪加密的過程中,RNG的電路結(jié)構(gòu)和輸入的“種子”(即CLK)都不需要做任何的變化,這在經(jīng)典電路中是難以想象的,如達(dá)到同樣的效果必須要耗費(fèi)巨大的硬件成本。另外,真隨機(jī)數(shù)也存在天然的缺陷,因?yàn)閭坞S機(jī)數(shù)是由特定算法生成的,所以其0/1分布相對均勻,對應(yīng)的塊內(nèi)頻率測試的值更加合理,而真隨機(jī)數(shù)的本質(zhì)是因?yàn)槲锢磉^程的演變而量化的結(jié)果,所以其存在0/1集中分布的概率是很大的,如果直接應(yīng)用于加密操作,很可能會導(dǎo)致部分子塊內(nèi)的密文信息泄露,那么后續(xù)的工作會考慮到在并行輸出的后端再加上一級具有混淆功能的P-box,至于變換矩陣的算法,設(shè)想依照QCA物理模型對應(yīng)的“熵源”交叉耦合結(jié)構(gòu)和交叉導(dǎo)向結(jié)構(gòu)內(nèi)在的演化規(guī)律同溫度、元胞距離等參數(shù)的關(guān)系,再根據(jù)本文設(shè)計(jì)的TRNG輸出結(jié)果進(jìn)行大量的數(shù)據(jù)測試和統(tǒng)計(jì),最終利用QCA的可逆邏輯門[16-17]電路,實(shí)現(xiàn)對P-box的最優(yōu)化的設(shè)計(jì)。