文獻標識碼： A
文章編號： 0258-7998(2014)07-0061-04
摘 要： 為了提升密碼算法中非線性布爾函數實現效率，設計了串行與電路和以查找表為基礎的并行化低次布爾函數實現架構，分別實現高次與項和低次與項。分析了不同并行化查找表實現密碼算法中低次布爾函數的效率。結果表明，結合香農分解定理提出的并行化查找表架構處理性能可以達到1.02 GHz，不僅能夠靈活適配密碼算法中的非線性布爾函數，而且能夠節省資源占用。
關鍵詞： 非線性布爾函數；查找表；并行化；適配
在對稱密碼算法中，非線性布爾函數起著舉足輕重的作用，其實現效率直接決定密碼算法的處理效率。非線性布爾函數的實現主要有基本邏輯運算組合實現、可編程的與-異或陣列和查找表3種方式實現。其中基本邏輯運算組合實現主要應用于通用處理器中，通過多種基本運算組合，可以實現任意形式的非線性布爾函數。可編程與-異或陣列[1-2]采取對陣列進行遍歷的方式實現不同的布爾函數，通過增加陣列的維度以適配更多變量的布爾函數。查找表[3-4]采取將真值表預存的方式實現布爾函數，通過增加存儲資源來適配更多變量的布爾函數，也可以將高次布爾函數分解，通過多級運算的方式實現。
可編程與-異或陣列和查找表的出現，雖然在一定程度上緩解了非線性布爾函數實現效率低下的問題，但針對密碼算法中的非線性布爾函數，以上兩種方式均沒有充分利用密碼算法中非線性布爾函數的特點，也未充分開發可編程與-異或陣列和查找表的并行性，導致存儲資源的利用率低，適配能力不足。
本文通過對密碼算法中的非線性布爾函數特點進行分析，分別針對大與項少和小與項多的特點，設計了并行化的查找表架構，能夠適配最大與項次數為6的非線性布爾函數；針對高次與項少的特點，設計了專門的串行與運算，可以適配任何次數的與項，能夠有效提升非線性布爾函數的實現效率。
1 非線性布爾函數特征分析
1.1 非線性布爾函數操作特征分析
分別從非線性布爾函數的狀態序列長度、變量個數、與項最高次數以及與項個數等方面對密碼算法中的非線性布爾函數操作特征進行了統計分析和總結歸納，如表1[5-7]所示。
結合表1和非線性布爾函數多項式的表示形式，可以得出密碼算法中的非線性布爾函數具有以下幾個特點：
(1)狀態序列長度，即可能出現在非線性布爾函數中的所有變量個數，不同算法中差異較大。
(2)變量個數。非線性布爾函數狀態序列較長，并不是所有變量均參與非線性布爾函數的運算，如在Grain128算法中，參與運算的變量只有總變量的7.8%左右，但變量位置比較分散。
(3)與項次數。參與非線性布爾函數運算的與項次數差異較大。
(4)與項個數。算法中的非線性布爾函數中出現的與項種類在變量可能組成的與項種類中所占比例較小。
(5)與項之間關系。與項之間均為異或關系，不同的與項中可能重復出現相同的變量，與項之間的變量通常具有交叉或包含關系。
1.2 非線性布爾函數的分類
由圖1可知，密碼算法中的非線性布爾函數具有參與運算的變量占所有變量比例小、變量位置分散、高次與項少、低次與項多的特點。將不同的變量組成的與項進行組合可以發現，整個非線性布爾函數可以拆分為多個包含較少變量的非線性布爾函數(少變量布爾函數)，只是變量的表現形式和變量之間的組合不同。若對非線性布爾函數進行拆分，則能夠有效地減少實現介于低次與項和高次與項中間布爾函數消耗的資源，降低路徑延遲。需要針對少變量布爾函數的運算進行專門的設計。高次與項較少，需設計專門的串行與電路實現。
與-異或陣列實現方式雖然不需要關心變量的形式，但當與項較多時，需要的配置信息量十分龐大，極大地降低了實現的靈活性。查找表實現方式不需要關心變量的位置，只需要考慮變量的個數，且配置信息量較小，比較適合實現少變量非線性布爾函數。只需將多個少變量布爾函數的結果相異或，即可實現布爾函數中所有低次與項計算。但常見的非線性布爾函數實現方式不能支持多個布爾函數的同時輸出，造成了資源的浪費和性能的降低。基于此，為充分開發設計的布爾函數架構的并行性，將低次布爾函數中與項的種類分為兩類，并以此為基礎，研究低次與項的并行化實現架構：
(1)無公共變量
無公共變量指的是各與項之間不存在公共變量，與項之間相互獨立。如日本的TOYOCRYPT-HS1算法中非線性布爾函數，包含63個二次與項，與項之間無公共變量。
(2)有公共變量
有公共變量指的是各與項之間存在公共變量，且公共變量的個數差異較大，與項之間的公共變量差異也較大。如Grain80算法中濾波函數，包含3個二次與項，每兩個與項之間都有一個相同的變量，包含4個三次與項，存在有兩個共有變量的情況。
2 并行化非線性布爾函數實現架構
結合密碼算法中非線性布爾函數中與項的特點，分別針對布爾函數中不同與項的特點，提出相應的布爾函數實現方式。
2.1 高次與項實現
密碼算法中非線性布爾函數高次與項數量較少，因此設計了專門的串行與電路實現，如圖1所示。可以通過控制序列C中1選擇源序列S相應的數據，將保留的數據進行相與，即可得到高次與項的結果。當與項次數i大于N時，可以將控制序列C中填充為全1，i(mod N)不為0時，最后一組控制序列不需要為全1，按照實際需求進行配置。
2.2 低次與項實現
低次與項的布爾函數其與項之間的關系主要包含無公共變量、有公共變量2種，分別對兩類與項的實現進行了研究，并在此基礎上提出了改進的并行化實現架構。
2.2.1 無公共變量類與項實現
無公共變量類與項中各與項之間無化簡的空間，可以采用傳統的查找表方式實現。由于與項的次數不固定，因此對查找表實現方式進行了并行化設計，以提高資源的利用率。
采用單一查找表方式實現變量數位n的非線性布爾函數需要的存儲空間為2n，即可以滿足兩個變量為n-1的布爾函數所需存儲空間，滿足4個變量數為n-2的布爾函數所需存儲空間，依此類推可以滿足2n-m個變量數為m的布爾函數所需存儲空間。結合密碼算法中布爾函數的特點，本文以6為例，對布爾函數的并行化設計進行分析。
通過分析在26存儲空間上如何實現4變量、5變量、6變量函數，提出了并行化布爾函數設計電路，包含輸入端口和配置端口，通過不同的配置，可以支持4個無公共變量的4變量布爾函數，2個無公共變量的5 變量布爾函數，1個6變量的布爾函數，如圖2所示。可以充分利用電路中的存儲資源，尤其是當要實現的布爾函數具有變量個數多、與項次數低的特征時，可以將布爾函數分別實現，然后將函數的運算結果進行異或即可。
2.2.2 有公共變量類與項實現
無公共變量的并行化架構靈活性高，實現布爾函數種類多，但輸入端口數較多，不利于處理器中集成。密碼算法的布爾函數中與項存在大量的公共變量，若充分利用公共變量的特點，則能夠有效降低布爾函數實現中所需的端口。如以6變量布爾函數為例，支持圖2所具有的功能，公共變量數為n(n<6)，則輸入端口數減少為19-3n。
基于此提出了具有2個公共變量的并行化架構，如圖3所示。以具有2個公共變量的6變量布爾函數的實現為例，可以支持4組具有2個公用變量的4變量布爾函數，分別為f(a，b，c，d)，f(a，b，g，h)，f(a，b，m，n)，f(a，b，p，q)；支持2組具有2個公用變量的5變量布爾函數，分別為f(a，b，c，d，e)，f(a，b，m，n，s)；支持一個6變量布爾函數f(a，b，c，d，e，f)。
2.2.3 改進的布爾函數的實現結構
具有2個公共變量并行化架構能夠有效地減少輸入端口的數量，但不能減少存儲資源的消耗。若能充分利用密碼算法中非線性布爾函數具有0、1因子的特點，可以有效地降低實現所需的資源消耗。基于此，結合香農分解定理和低次與項具有公共變量的特點，提出了改進的具有2個公共變量的并行化架構。
由式(1)可知，當一個n變量布爾函數存在代數1、0因子時，n變量的布爾函數可以分解為n-1變量和n-2變量的兩個非線性布爾函數，從而可將一個n變量布爾函數所需的2n比特存儲資源降少到2n-1+2n-2比特資源，如圖4所示并行化架構，以具有2個公共變量的6變量布爾函數的實現為例，可以同時支持3組具有2個公用變量的4變量布爾函數，分別為f(a，b，c，d)，f(a，b，f，g)，f(a，b，m，n)；支持具有一個公用變量的5變量布爾函數和一個4變量布爾函數，分別為f(a，b，c，d，e)，f(a，b，m，n)；支持一個具有代數0、1因子的6變量布爾函數f(a，b，c，d，e，f)。
圖4中的非線性布爾函數實現方式雖然有效降低了輸入端口數和存儲資源的占用，但其支持的所有布爾函數均存在公共變量。為了在接口數量不變的情況下支持更多類型的布爾函數種類，對圖4進行了改進，如圖5所示，可以支持支持3組具有2個公用變量的4變量布爾函數，分別為f(a，b，c，d)，f(a，b，e，f)，f(a，b，g，h)；支持無公用變量的5變量布爾函數和4變量布爾函數，分別為f(a，b，c，d，i)，f(e，f，g，h)；支持一個具有代數0、1因子的6變量布爾函數f(a，b，c，d，h，i)。
3 函數適配與性能分析
為了驗證所設計架構的正確性和高效性，對密碼算法中的非線性布爾函數進行了適配，選取了grain-80算法中的非線性布爾函數。設初始的序列已經按照布爾函數的要求將變量進行排列：
如表2所示，可以看出，4種并行化架構都能高效地適配密碼算法中的非線性布爾函數，而密碼算法中的非線性布爾函數具有代數0、1因子的特征比較明顯，兩種改進的非線性布爾函數架構就可以很好地滿足密碼算法中布爾函數的需求，最高處理速度可以達到1.02 GHz，資源占用是其他實現方式的75%。由于其端口數和存儲資源占用均較小，特別適合集成到專用的密碼處理器中。
結果表明，本文設計的非線性布爾函數并行化架構有效滿足了密碼算法中非線性布爾函數的特點，不僅可以靈活地適配密碼算法中的非線性布爾函數，同時具有較高的處理性能。
通過分析密碼算法中非線性布爾函數的特點，對布爾函數中與項進行分類；針對不同類別的與項，提出了相應的并行化布爾函數實現架構。在此基礎上，結合香農定理，提出了改進的并行化非線性布爾函數實現架構，能夠在較少的輸入端口和資源占用情況下靈活適配密碼算法中的非線性布爾函數。
下一步需要針對不同應用場景下非線性布爾函數的特點，設計相應的并行化架構，提高不同場景下非線性布爾函數的處理速度。
參考文獻
[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–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] 徐建博,戴紫彬.面向序列密碼抽取與插入單元可重構設計研究[J].電子技術應用，2011，37(7)：65-67.