兩類非線性密碼組件可重構研究與電路設計

連宜新，陳 韜，李 偉，南龍梅

（戰略支援部隊信息工程大學密碼工程學院，鄭州 450001）

0 概述

對稱密碼在網絡和通信領域應用廣泛，其按照加密方式的不同可進一步分為序列密碼算法和分組密碼算法［1］。在基于比特級操作［2］的序列密碼算法中，非線性布爾函數成為其核心部件，在亂源更新和亂數生成過程中都參與運算，而s 盒是分組密碼唯一的非線性部件，為算法提供了非線性性和安全性，兩者本質上都是非線性布爾函數，但在密碼芯片實際處理中卻存在不同的實現方式。在s 盒實現方面，由于s 盒構造方式的不同，國內外研究分為通用和專用s 盒的實現加速，在通用領域［3-5］均采用時序部件8-8的RAM 搭建可重構運算單元，可不同程度地并行實現常規類型的s 盒，區別在于文獻［5］在電路的基礎上增加了旁系電路，通過門控技術降低了s 盒功耗。而文獻［6］將s 盒作為非線性布爾函數，利用與或陣列的形式搭建可重構s 盒電路。在專用領域，s 盒的實現主要針對基于塔域求逆和仿射變換設計s 盒的算法，如AES、Camellia、SMS4 等。文獻［7-8］根據有限域上域的擴張理論，采用組合邏輯的方式優化單算法AESs 盒。文獻［9］提出的復合域求逆運算模型針對有限域求逆的s 盒，其本質上仍然是域的擴張理論，文獻［10］將AES、Camellia、SMS4 等s 盒電路采用GF（16）上的運算搭建進而重構，其核心的求逆電路相同，區別只是在于求逆電路輸入前和輸出后的轉換矩陣。在針對序列密碼的非線性布爾函數（NBF）實現方面，單算法設計如文獻［11］采取直接實現的方法，而面向密碼處理的NBF 設計結構具有通用性，其可重構設計借鑒了FPGA 思想。文獻［12-14］在統計序列密碼NBF 運算特征，即參與運算變量個數與項次數基礎上采用LUT 搭建實現，其結構的區別在于LUT 選取的粒度和規模不同。

但以上設計均只是從某種或者某類算法的角度出發，并未將對稱密碼非線性運算模塊統一，實際上兩者本質上并無區別，這樣的異構化設計必然存在資源浪費的問題。此外由于s 盒一般采用并行化處理，這使得s 盒成為密碼處理器中資源消耗最大的模塊，如何降低對稱密碼非線性運算面積開銷是急需解決的問題，因此可以采取一種統一的結構實現以降低硬件開銷。

本文設計一種s 盒非線性布爾函數模塊（Sbox_Non-linear Boolean Function Module，SNBFM）架構，在MBFM 架構的基礎上融合部分類型的s 盒，并結合有限域理論，對其中能夠優化的類AESs 盒進行適配，使其對類AES 的s 盒支持力度更高。

1 可重構分析

1.1 兩類非線性密碼組件操作特征分析

在對稱密碼中，s 盒和非線性布爾函數都是作為異構的模塊單獨實現，其中NBF 在序列密碼的編碼環節［15］，即亂源更新，在亂數生成的過程中均參與運算，其通用表達式包含1，2，…，n次常數項，公式如下所示：

通過統計NESSIE 計劃、CRYPTREC 計劃和ESTREAM 計劃，征集序列密碼算法NBF 操作特征，即對其狀態序列長度、參與運算變量個數、項個數和次數進行分析，如表1 所示，發現雖然位寬為12～256 bit，參與運算的變量個數可能很多，約為12～128 個，但與項次數多數不超過6 次，因此相應的NBF 結構均是能實現最高次數為6 的變量結構［12-14］。

表1 NBF 操作特征Table 1 NBF operational characteristics

s 盒設計方法主要包括隨機選取測試和利用數學方法產生2 種［16］，并且需要滿足一定的設計準則，而硬件設計人員在s 盒實現上關注的是s 盒的操作特征，即輸入和輸出變量數。本文對AES 計劃、NESSIE 計劃以及其他商用分組密碼算法的s 盒進行特征分析，發現s 盒的種類大多集中在4-4、6-4、8-4、8-8、8-32 上，同時s 盒具有一定的并行性。

1.2 NBFM 結構實現能力分析

在文獻［13］所列出的4 種NBFM 結構中，其中的一種共享2 輸入NBFM 結構如圖1 所示，NBFM 是一個10 入4 出的結構，這類含共享變量的結構充分考慮了NBFM 操作特征，減少了端口數目，易于在處理器中集成，整體結構可以分為LUT 存儲和NBFM組合邏輯兩部分。適配8-8 s 盒的NBFM 如圖2 所示。NBFM 實現能力如表2 所示，其中輸出端用0、1、2、3 代替。將s 盒映射到NBFM 是將s 盒輸出的每一路都看作輸入的非線性布爾函數，然后根據輸入變量的多少確定NBFM 變量模式，可以看到，NBFM對于4 輸入、5 輸入、6 輸入的s 盒能夠分別支持4 路、2 路和1 路輸出，較好地支持了4-4、6-4 類型的s 盒。但由于NBFM 缺少8 變量模式，因此只能通過級聯實現8 變量NBFM，圖2 所示為8-8 s 盒輸出任意一路在NBFM 中的適配，而各類s 盒在NBFM 中適配資源消耗如表3 所示。

表2 NBFM 實現能力Table 2 NBFM Realization ability

表3 不同類型s 盒資源消耗Table 3 Resource consumption of different types of s box

圖1 NBFM 結構Fig.1 NBFM structure

圖2 適配8-8 s 盒的NBFMFig.2 NBFM of adaptation 8-8 s box

從表3 可以看出，NBFM 在實現4-4 和6-4 的s 盒上消耗資源較少，而在實現8 輸入變量的s 盒上時需要多個NBFM 級聯才能實現1 路輸出。NBFM 實現一個8-8 的s 盒與8-8 的RAM 如表4 所示。可以看出，NBFM 在實現8-8 s 盒上效率很低，性能指標也并不如RAM 實現，但通過對8-8 的s 盒進行進一步細分發現，8-8 的s 盒中存在求逆和仿射變換構造的類AESs 盒，這類s 盒可通過組合邏輯的方法化簡輸出的NBF 表達式，從而易于NBFM 適配。

表4 8-8 的s 盒適配資源評估Table 4 8-8 s box adaptation resource evaluation

2 類AESs 盒和非線性布爾函數可重構研究

2.1 類AESs 盒可降解理論分析

在對文獻［7-8］進行分析后發現，類AES 的s 盒存在2 種分解形式：GF（42）2和GF（（22）2）2。2 種分解形式區別在于基本模塊規模的不同，而適合NBFM這種2 輸入LUT 類型實現的是GF（（22）2）2，因此本文將根據混合基方法［17］推導s 盒分解后的不同模塊表達式。

文獻［17］采用混合基實現AESs 盒的塔域分解，具體采用的基和不可約多項式如表5 所示，其中，α是e(x)=0 的一個根，β是f(x)=0 的一個根，γ是g(x)=0 的一個根。為方便計算，記λ=α2β。塔域分解后的AESs 盒電路如圖3 所示，可以看到s 盒的求逆部分由乘和求逆等5 類模塊組成，δ、Aδ-1+C是復合仿射變換后的同構映射矩陣，規模為8 行8 列，負責對求逆的輸入和輸出進行轉換。與文獻［17］s 盒采用GF（16）上的模塊用GF（4）模塊組合實現、GF（4）上模塊再用GF（2）上的運算組合實現的兩級模塊化設計方法不同，由于各個模塊具體適配到NBFM 上時，適配的對象LUT_n表示一個n輸入的NBF，最終的適配對象應該是一個個的NBF，因此只能推導出各個模塊的NBF 表達式，而文獻［17］的兩級模塊搭建方法無法深入比特級表達式，因此無法適配各個模塊。下文將依次推導出求逆所包含的5 個模塊的布爾表達式。

表5 不可約多項式和基的選取Table 5 Selection of irreducible polynomials and bases

圖3 塔域分解后的AES s 盒電路Fig.3 AES s box circuit after tower domain decomposition

s 盒的求逆部分包含平方S4、乘法M4、乘法常數乘法乘、求逆等5 類模塊，涉及到的運算均在GF（16）上，其中S4、M4以多項式基輸入和輸出，乘和以多項式基輸入、正規基輸出。設GF（16）上元素A、B用多項式基表示：A=a0⊕a1β，B=b0⊕b1β，a0b0是低2 位，a1b1是高2 位，a0b0a1b1∈(0，1，2，3)。

S4、M4乘和求逆結果用A2、AB、AB_ptn、λA、A-1表示，則可得式（1）～式（5）。由于最后要推導出各個模塊的布爾表達式，而a0b0a1b1是GF（4）并非GF（2）上元素，因此需要繼續分解。可以看到，式（1）～式（5）用到的基本運算包含GF（4）上的平方S2、兩類常數乘法α乘和α2乘、乘 法M2和求逆I2等4 類。GF（4）上元素用正規基表示可以簡化求逆和平方的計算，設C=c0⊕c1α，D=d0⊕d1α，其中，c0d0是低位，c1d1是高位，c0d0c1d1∈(0，1)。

S2、α乘和α2乘、M2、I2結果分別用C2、αC、α2C、CD、C-1表示，可得式（6）～式（10）。設GF（16）上元素AB的比特形式為A={A3，A2，A1，A0}，B={B3，B2，B1，B0}，將式（6）和式（7）代入式（1）得S4，將式（7）和式（8）代入式（2）得乘，將式（6）、式（7）、式（9）和式（10）代入式（3）得，將式（7）和式（9）代入式（4）和式（5）得和M4，結果分別如式（11）～式（15）所示：

將AESs 盒求逆表達式推導完成后，由于涉及到的是類AESs 盒，因此還需要從原理上證明此類s 盒適合重構。文獻［10］對AES、Camellia、SMS4等類AESs 盒做了可重構電路，其求逆統一在塔域GF（42）2上實現，區別僅在復合了仿射變換后的前后同構映射矩陣上，但并未說明其理論基礎。文獻［18］根據包含相同個數元素的域是同構的原理，證明了GF（256）上s 盒S和基于有限域擴張理論求出來的逆s 盒T存在線性變換A1、B1，使得S=B1（T（A（x）），并進一步證明有2 040 個這樣的轉換對使得s 盒原域和塔域的乘法逆s 盒保持線性變換。A1、B1即為轉換矩陣，在采用統一基類型和不可約多項式的前提下類AESs 盒乘法逆T相同，這樣即從原理上證明了此類s 盒存在統一的結構，為可重構電路設計奠定了理論基礎。

2.2 類AESs 盒與NBFM 可重構分析

將塔域分解后的s 盒和NBFM 結構重構，即將s盒適配到NBFM 結構中，將s 盒分解到GF（16）上的各個運算，考慮各模塊輸入輸出情況，如乘法M4是8 入4 出的結構，采用NBFM 的6 輸入模式后，需要消耗16 個NBFM，具體各模塊資源消耗如表6 所示，其中，異或包括求逆的2 個GF（16）上運算以及2 個轉換矩陣，1 個異或門面積≈個2_LUT。

表6 各模塊資源消耗Table 6 Resource consumption of each module

Sbox_area=3M4+S4+I4+λ+異或，相當于用51 個NBFM 加一部分異或門實現一個可分解的8-8 s 盒，這樣效率不如直接實現，由于M4布爾表達式是8 入4 出的結構，如果直接采取NBFM 的6 變量模式搭建一個完備的NBF將導致資源浪費，冗余度過高，應該針對M4繼續分解。

將GF（16）上的乘法繼續分解到GF（4）上，用到3個M2乘法、1 個α 乘以及部分異或門資源，電路如圖4 所示。涉及到的各模塊資源損耗如表7 所示，其中，M2電路只考慮LUT 資源的情況下消耗4 個2 輸入LUT，相當于1/4 個NBFM。

表7 M4資源消耗Table 7 M4 resource consumption

圖4 M4電路Fig.4 M4 circuit

最后相當于 用1 個NBFM 實現GF（16）上的乘法。最終的s 盒占用變為6 個NBFM 加一部分的異或門，相比將s 盒輸出展開寫成NBF 表達式的方法節約了近9 倍的NBFM 資源。

2.3 結合類AESs 盒的NBFM 結構優化分析

由2.1 節對塔域分解后的不同模塊表達式的推導可知，式（11）～式（15）復雜程度不一，映射到NBFM 上還是采用門級電路實現未定，根據推導出的表達式復雜程度，結合表達式輸入輸出特征，將各個模塊分為3 類實現形式：1）基于異或實現平方S4乘和前后的同構映射；2）基于NBFM 實現求逆3）基于改進后的SNBFM 實現和M4乘法。圖5 所示為類AESs 盒適配的電路，可以看到只需用到4 個NBFM 便可以實現一個完整的類AESs 盒。

圖5 s 盒適配后的整體結構Fig.5 Overall structure of s-box after adaptation

基本模塊平方S4乘根據式（11）、式（12）結果只有少數的1 次項，如果采用能實現從1 次項到4 次項且變量任意組合的NBFM 的4 變量模式，將造成極大的資源浪費，考慮到s 盒實現的并行性，用較少的NBFM實現是需要考慮的性能指標，基于此，平方S4和求逆采用異或實現，這樣只需要用到6 個2 輸入異或門便可實現S4模塊，需要7個2輸入異或門便可實現乘模塊。此外，同構映射矩陣也采用異或門實現，異或門的數量=矩陣中1 的數量減1，由于前后的同構映射矩陣不屬于求逆部分，類AESs 盒的差別即在于此，因此設置成可配置類型，共需要128 bit 配置信息和126 個異或門，配置信息為1 時輸入位取反，為0 時輸入位不變。下面給出AESs盒輸入轉換y=和輸出轉換y=的轉換矩陣，其中x、y均按小端排列。

表8 電路端口映射Table 8 circuit port mapping

表8 電路端口映射Table 8 circuit port mapping

圖6 SNBFM 結構Fig.6 SNBFM structure

3 性能評估

在保證NBFM 原有NBF 功能前提下，采用verilog實現各個改進的NBFM 模塊，最后按照類AESs 盒電路的組織形式對改進后的NBFM進行級聯實現s盒功能。功能驗證通過后在CMOS 65 nm 工藝庫下對該電路進行綜合，與塔域直接實現的s 盒電路和NBFM 電路進行對比分析后的結果如表9 所示。

表9 電路性能指標Table 9 Circuit performance index

RAM 是一個時序部件，雖然延遲最小但規模過大，而文獻［13］的NBFM 結構在適配s 盒時將s 盒作為NBF 適配，這種方法雖然適合通用8-8 的s 盒，但由于NBM 最多只能支持6 變量模式，因此NBFM 個數消耗過多以致占用資源最多。這種NBF 適配的方法適合6 變量、4 變量輸入的s 盒，但并不適合8-8 的通用s 盒。文獻［17］所選用的塔域分解是一種用組合邏輯的方法實現AESs 盒，其目的是為了降低面積開銷，但是這種組合邏輯的方法在單個算法s 盒性能表現上并不是最優的。文獻［19］將各模塊的表達式推導出以后，采用CSE 算法將其中的各模塊表達式含有的公共項消除進一步減少了s 盒面積和延遲。本文驗證了類AESs 盒電路差異僅在轉換矩陣上，實現了類AESs 盒和NBF 的可重構，由于可重構的結構是要實現兩類非線性運算，但NBFM 的結構并不適合對類AESs 盒直接實現，需要對NBFM 進行改進，這使得NBFM 的電路資源并非完全參與s 盒的運算，采用CSE 算法也會造成一定的冗余度。也因此，本文采用類似的塔域分解的方法，相比文獻［19］增加了1 倍多面積。

但實際上面積不是唯一的指標，由于牽扯到復雜的NBF 適配，NBFM 的個數是多個級聯在一起，因此在保證充分復用前提下用最少的NBFM 個數來實現s 盒。本文采用的方法相當于在4 個改進后的NBM 電路加一部分異或陣列，可以看到在4 個NBFM 基礎上增加1 632-362×4=184 μm2實現了一個類AES 的8-8 的s 盒，相當于只用22.7%的s 盒電路面積實現了一個類AES 的s 盒，而電路延遲基本不變。

在電路實現功能上，如表10 所示，由于塔域分解定理只針對部分s 盒，因此并不能實現通用的8-8 s 盒的實現。

表10 電路實現功能的對比Table 10 Comparison of circuit realization functions

4 結束語

本文實現了類AESs 盒和NBFM 的可重構電路，并基于塔域分解理論，提出一種新的SNBFM 結構。采用混合基方法將AES 類s 盒電路分解為GF（16）上的各種運算模塊，并推導出這些模塊的位級表達式。實驗結果表明，改進后的整體結構只用到4 個NBFM加上原s 盒的22.7%面積實現一個完整的類AESs盒，而延遲基本不變，并保證了已有NBF 功能。但類AESs 盒相比通用s 盒種類較少，使得該結構的用途受到限制，下一步將研究運用更少的資源實現通用s盒和NBF 的可重構，并通過擴展指令的方式加速密碼運算［20］。