摘  要： 為了提升密碼算法中非線性布爾函數(shù)實現(xiàn)效率，設(shè)計了串行與電路和以查找表為基礎(chǔ)的并行化低次布爾函數(shù)實現(xiàn)架構(gòu)，分別實現(xiàn)高次與項和低次與項。分析了不同并行化查找表實現(xiàn)密碼算法中低次布爾函數(shù)的效率。結(jié)果表明，結(jié)合香農(nóng)分解定理提出的并行化查找表架構(gòu)處理性能可以達(dá)到1.02 GHz，不僅能夠靈活適配密碼算法中的非線性布爾函數(shù)，而且能夠節(jié)省資源占用。

        關(guān)鍵詞： 非線性布爾函數(shù)；查找表；并行化；適配

        在對稱密碼算法中，非線性布爾函數(shù)起著舉足輕重的作用，其實現(xiàn)效率直接決定密碼算法的處理效率。非線性布爾函數(shù)的實現(xiàn)主要有基本邏輯運算組合實現(xiàn)、可編程的與-異或陣列和查找表3種方式實現(xiàn)。其中基本邏輯運算組合實現(xiàn)主要應(yīng)用于通用處理器中，通過多種基本運算組合，可以實現(xiàn)任意形式的非線性布爾函數(shù)?？删幊膛c-異或陣列^[1-2]采取對陣列進(jìn)行遍歷的方式實現(xiàn)不同的布爾函數(shù)，通過增加陣列的維度以適配更多變量的布爾函數(shù)。查找表^[3-4]采取將真值表預(yù)存的方式實現(xiàn)布爾函數(shù)，通過增加存儲資源來適配更多變量的布爾函數(shù)，也可以將高次布爾函數(shù)分解，通過多級運算的方式實現(xiàn)。

        可編程與-異或陣列和查找表的出現(xiàn)，雖然在一定程度上緩解了非線性布爾函數(shù)實現(xiàn)效率低下的問題，但針對密碼算法中的非線性布爾函數(shù)，以上兩種方式均沒有充分利用密碼算法中非線性布爾函數(shù)的特點，也未充分開發(fā)可編程與-異或陣列和查找表的并行性，導(dǎo)致存儲資源的利用率低，適配能力不足。

        本文通過對密碼算法中的非線性布爾函數(shù)特點進(jìn)行分析，分別針對大與項少和小與項多的特點，設(shè)計了并行化的查找表架構(gòu)，能夠適配最大與項次數(shù)為6的非線性布爾函數(shù)；針對高次與項少的特點，設(shè)計了專門的串行與運算，可以適配任何次數(shù)的與項，能夠有效提升非線性布爾函數(shù)的實現(xiàn)效率。

1 非線性布爾函數(shù)特征分析

1.1 非線性布爾函數(shù)操作特征分析

        分別從非線性布爾函數(shù)的狀態(tài)序列長度、變量個數(shù)、與項最高次數(shù)以及與項個數(shù)等方面對密碼算法中的非線性布爾函數(shù)操作特征進(jìn)行了統(tǒng)計分析和總結(jié)歸納，如表1^[5-7]所示。

        結(jié)合表1和非線性布爾函數(shù)多項式的表示形式，可以得出密碼算法中的非線性布爾函數(shù)具有以下幾個特點：

        (1)狀態(tài)序列長度，即可能出現(xiàn)在非線性布爾函數(shù)中的所有變量個數(shù)，不同算法中差異較大。

        (2)變量個數(shù)。非線性布爾函數(shù)狀態(tài)序列較長，并不是所有變量均參與非線性布爾函數(shù)的運算，如在Grain128算法中，參與運算的變量只有總變量的7.8%左右，但變量位置比較分散。

        (3)與項次數(shù)。參與非線性布爾函數(shù)運算的與項次數(shù)差異較大。

        (4)與項個數(shù)。算法中的非線性布爾函數(shù)中出現(xiàn)的與項種類在變量可能組成的與項種類中所占比例較小。

        (5)與項之間關(guān)系。與項之間均為異或關(guān)系，不同的與項中可能重復(fù)出現(xiàn)相同的變量，與項之間的變量通常具有交叉或包含關(guān)系。

1.2 非線性布爾函數(shù)的分類

        由圖1可知，密碼算法中的非線性布爾函數(shù)具有參與運算的變量占所有變量比例小、變量位置分散、高次與項少、低次與項多的特點。將不同的變量組成的與項進(jìn)行組合可以發(fā)現(xiàn)，整個非線性布爾函數(shù)可以拆分為多個包含較少變量的非線性布爾函數(shù)(少變量布爾函數(shù))，只是變量的表現(xiàn)形式和變量之間的組合不同。若對非線性布爾函數(shù)進(jìn)行拆分，則能夠有效地減少實現(xiàn)介于低次與項和高次與項中間布爾函數(shù)消耗的資源，降低路徑延遲。需要針對少變量布爾函數(shù)的運算進(jìn)行專門的設(shè)計。高次與項較少，需設(shè)計專門的串行與電路實現(xiàn)。

        與-異或陣列實現(xiàn)方式雖然不需要關(guān)心變量的形式，但當(dāng)與項較多時，需要的配置信息量十分龐大，極大地降低了實現(xiàn)的靈活性。查找表實現(xiàn)方式不需要關(guān)心變量的位置，只需要考慮變量的個數(shù)，且配置信息量較小，比較適合實現(xiàn)少變量非線性布爾函數(shù)。只需將多個少變量布爾函數(shù)的結(jié)果相異或，即可實現(xiàn)布爾函數(shù)中所有低次與項計算。但常見的非線性布爾函數(shù)實現(xiàn)方式不能支持多個布爾函數(shù)的同時輸出，造成了資源的浪費和性能的降低?；诖?，為充分開發(fā)設(shè)計的布爾函數(shù)架構(gòu)的并行性，將低次布爾函數(shù)中與項的種類分為兩類，并以此為基礎(chǔ)，研究低次與項的并行化實現(xiàn)架構(gòu)：

         (1)無公共變量

        無公共變量指的是各與項之間不存在公共變量，與項之間相互獨立。如日本的TOYOCRYPT-HS1算法中非線性布爾函數(shù)，包含63個二次與項，與項之間無公共變量。

        (2)有公共變量

        有公共變量指的是各與項之間存在公共變量，且公共變量的個數(shù)差異較大，與項之間的公共變量差異也較大。如Grain80算法中濾波函數(shù)，包含3個二次與項，每兩個與項之間都有一個相同的變量，包含4個三次與項，存在有兩個共有變量的情況。

2 并行化非線性布爾函數(shù)實現(xiàn)架構(gòu)

        結(jié)合密碼算法中非線性布爾函數(shù)中與項的特點，分別針對布爾函數(shù)中不同與項的特點，提出相應(yīng)的布爾函數(shù)實現(xiàn)方式。

2.1 高次與項實現(xiàn) 

        密碼算法中非線性布爾函數(shù)高次與項數(shù)量較少，因此設(shè)計了專門的串行與電路實現(xiàn)，如圖1所示?？梢酝ㄟ^控制序列C中1選擇源序列S相應(yīng)的數(shù)據(jù)，將保留的數(shù)據(jù)進(jìn)行相與，即可得到高次與項的結(jié)果。當(dāng)與項次數(shù)i大于N時，可以將控制序列C中填充為全1，i(mod N)不為0時，最后一組控制序列不需要為全1，按照實際需求進(jìn)行配置。

2.2 低次與項實現(xiàn)

        低次與項的布爾函數(shù)其與項之間的關(guān)系主要包含無公共變量、有公共變量2種，分別對兩類與項的實現(xiàn)進(jìn)行了研究，并在此基礎(chǔ)上提出了改進(jìn)的并行化實現(xiàn)架構(gòu)。

2.2.1 無公共變量類與項實現(xiàn)

        無公共變量類與項中各與項之間無化簡的空間，可以采用傳統(tǒng)的查找表方式實現(xiàn)。由于與項的次數(shù)不固定，因此對查找表實現(xiàn)方式進(jìn)行了并行化設(shè)計，以提高資源的利用率。

        采用單一查找表方式實現(xiàn)變量數(shù)位n的非線性布爾函數(shù)需要的存儲空間為2ⁿ，即可以滿足兩個變量為n-1的布爾函數(shù)所需存儲空間，滿足4個變量數(shù)為n-2的布爾函數(shù)所需存儲空間，依此類推可以滿足2^n-m個變量數(shù)為m的布爾函數(shù)所需存儲空間。結(jié)合密碼算法中布爾函數(shù)的特點，本文以6為例，對布爾函數(shù)的并行化設(shè)計進(jìn)行分析。

        通過分析在2⁶存儲空間上如何實現(xiàn)4變量、5變量、6變量函數(shù)，提出了并行化布爾函數(shù)設(shè)計電路，包含輸入端口和配置端口，通過不同的配置，可以支持4個無公共變量的4變量布爾函數(shù)，2個無公共變量的5 變量布爾函數(shù)，1個6變量的布爾函數(shù)，如圖2所示。可以充分利用電路中的存儲資源，尤其是當(dāng)要實現(xiàn)的布爾函數(shù)具有變量個數(shù)多、與項次數(shù)低的特征時，可以將布爾函數(shù)分別實現(xiàn)，然后將函數(shù)的運算結(jié)果進(jìn)行異或即可。

2.2.2 有公共變量類與項實現(xiàn)

         無公共變量的并行化架構(gòu)靈活性高，實現(xiàn)布爾函數(shù)種類多，但輸入端口數(shù)較多，不利于處理器中集成。密碼算法的布爾函數(shù)中與項存在大量的公共變量，若充分利用公共變量的特點，則能夠有效降低布爾函數(shù)實現(xiàn)中所需的端口。如以6變量布爾函數(shù)為例，支持圖2所具有的功能，公共變量數(shù)為n(n<6)，則輸入端口數(shù)減少為19-3n。

        基于此提出了具有2個公共變量的并行化架構(gòu)，如圖3所示。以具有2個公共變量的6變量布爾函數(shù)的實現(xiàn)為例，可以支持4組具有2個公用變量的4變量布爾函數(shù)，分別為f(a，b，c，d)，f(a，b，g，h)，f(a，b，m，n)，f(a，b，p，q)；支持2組具有2個公用變量的5變量布爾函數(shù)，分別為f(a，b，c，d，e)，f(a，b，m，n，s)；支持一個6變量布爾函數(shù)f(a，b，c，d，e，f)。

2.2.3 改進(jìn)的布爾函數(shù)的實現(xiàn)結(jié)構(gòu)

        具有2個公共變量并行化架構(gòu)能夠有效地減少輸入端口的數(shù)量，但不能減少存儲資源的消耗。若能充分利用密碼算法中非線性布爾函數(shù)具有0、1因子的特點，可以有效地降低實現(xiàn)所需的資源消耗?；诖耍Y(jié)合香農(nóng)分解定理和低次與項具有公共變量的特點，提出了改進(jìn)的具有2個公共變量的并行化架構(gòu)。

        由式(1)可知，當(dāng)一個n變量布爾函數(shù)存在代數(shù)1、0因子時，n變量的布爾函數(shù)可以分解為n-1變量和n-2變量的兩個非線性布爾函數(shù)，從而可將一個n變量布爾函數(shù)所需的2ⁿ比特存儲資源降少到2^n-1+2^n-2比特資源，如圖4所示并行化架構(gòu)，以具有2個公共變量的6變量布爾函數(shù)的實現(xiàn)為例，可以同時支持3組具有2個公用變量的4變量布爾函數(shù)，分別為f(a，b，c，d)，f(a，b，f，g)，f(a，b，m，n)；支持具有一個公用變量的5變量布爾函數(shù)和一個4變量布爾函數(shù)，分別為f(a，b，c，d，e)，f(a，b，m，n)；支持一個具有代數(shù)0、1因子的6變量布爾函數(shù)f(a，b，c，d，e，f)。

        圖4中的非線性布爾函數(shù)實現(xiàn)方式雖然有效降低了輸入端口數(shù)和存儲資源的占用，但其支持的所有布爾函數(shù)均存在公共變量。為了在接口數(shù)量不變的情況下支持更多類型的布爾函數(shù)種類，對圖4進(jìn)行了改進(jìn)，如圖5所示，可以支持支持3組具有2個公用變量的4變量布爾函數(shù)，分別為f(a，b，c，d)，f(a，b，e，f)，f(a，b，g，h)；支持無公用變量的5變量布爾函數(shù)和4變量布爾函數(shù)，分別為f(a，b，c，d，i)，f(e，f，g，h)；支持一個具有代數(shù)0、1因子的6變量布爾函數(shù)f(a，b，c，d，h，i)。

3 函數(shù)適配與性能分析

        為了驗證所設(shè)計架構(gòu)的正確性和高效性，對密碼算法中的非線性布爾函數(shù)進(jìn)行了適配，選取了grain-80算法中的非線性布爾函數(shù)。設(shè)初始的序列已經(jīng)按照布爾函數(shù)的要求將變量進(jìn)行排列：

        如表2所示，可以看出，4種并行化架構(gòu)都能高效地適配密碼算法中的非線性布爾函數(shù)，而密碼算法中的非線性布爾函數(shù)具有代數(shù)0、1因子的特征比較明顯，兩種改進(jìn)的非線性布爾函數(shù)架構(gòu)就可以很好地滿足密碼算法中布爾函數(shù)的需求，最高處理速度可以達(dá)到1.02 GHz，資源占用是其他實現(xiàn)方式的75%。由于其端口數(shù)和存儲資源占用均較小，特別適合集成到專用的密碼處理器中。

        結(jié)果表明，本文設(shè)計的非線性布爾函數(shù)并行化架構(gòu)有效滿足了密碼算法中非線性布爾函數(shù)的特點，不僅可以靈活地適配密碼算法中的非線性布爾函數(shù)，同時具有較高的處理性能。

        通過分析密碼算法中非線性布爾函數(shù)的特點，對布爾函數(shù)中與項進(jìn)行分類；針對不同類別的與項，提出了相應(yīng)的并行化布爾函數(shù)實現(xiàn)架構(gòu)。在此基礎(chǔ)上，結(jié)合香農(nóng)定理，提出了改進(jìn)的并行化非線性布爾函數(shù)實現(xiàn)架構(gòu)，能夠在較少的輸入端口和資源占用情況下靈活適配密碼算法中的非線性布爾函數(shù)。

        下一步需要針對不同應(yīng)用場景下非線性布爾函數(shù)的特點，設(shè)計相應(yīng)的并行化架構(gòu)，提高不同場景下非線性布爾函數(shù)的處理速度。

參考文獻(xiàn)

[1] HUTTON M，Sshilecher J.Improving FPGA performance and area using an adaptive logic module[C].Berlin Heidelberg：J Becker，2004：135-144.

[2] Xu Liqing，Chen Hao.Some results on the algebraic immunity of Boolean functions[J].The Journal of China Universities of Posts and Telecommunications，2011，18(2)：102-105.

[3] KAVUT S，YUCEL M D.9-variable Boolean functions with nonlinearity 242 in the generalized rotation symmetric class[J].Information and Computation, 2010，208(4): 341&ndash;350.

[4] GANGOPADHYAY S，SARKAR S.Telang R.On the lower  bounds of the second order nonlinearities of some Boolean functions[J].Information Science， 2010，180(2)：266-273.

[5] CHASKHKM A V.Local complexity of Boolean functions[J].Discrete Applied Mathematics[J].2004，135(1): 55-64.

[6] COUCEIRO M，MARICHAL J L.Locally monotone Boolean and pseudo-Boolean functions[J].Discrete Applied Mathematics，2012，160(12)：1651-1660.

[7] 徐建博,戴紫彬.面向序列密碼抽取與插入單元可重構(gòu)設(shè)計研究[J].電子技術(shù)應(yīng)用，2011，37(7)：65-67.