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

（戰(zhàn)略支援部隊(duì)信息工程大學(xué)密碼工程學(xué)院，鄭州 450001）

0 概述

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

但以上設(shè)計(jì)均只是從某種或者某類算法的角度出發(fā)，并未將對(duì)稱密碼非線性運(yùn)算模塊統(tǒng)一，實(shí)際上兩者本質(zhì)上并無區(qū)別，這樣的異構(gòu)化設(shè)計(jì)必然存在資源浪費(fèi)的問題。此外由于s 盒一般采用并行化處理，這使得s 盒成為密碼處理器中資源消耗最大的模塊，如何降低對(duì)稱密碼非線性運(yùn)算面積開銷是急需解決的問題，因此可以采取一種統(tǒng)一的結(jié)構(gòu)實(shí)現(xiàn)以降低硬件開銷。

本文設(shè)計(jì)一種s 盒非線性布爾函數(shù)模塊（Sbox_Non-linear Boolean Function Module，SNBFM）架構(gòu)，在MBFM 架構(gòu)的基礎(chǔ)上融合部分類型的s 盒，并結(jié)合有限域理論，對(duì)其中能夠優(yōu)化的類AESs 盒進(jìn)行適配，使其對(duì)類AES 的s 盒支持力度更高。

1 可重構(gòu)分析

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

在對(duì)稱密碼中，s 盒和非線性布爾函數(shù)都是作為異構(gòu)的模塊單獨(dú)實(shí)現(xiàn)，其中NBF 在序列密碼的編碼環(huán)節(jié)［15］，即亂源更新，在亂數(shù)生成的過程中均參與運(yùn)算，其通用表達(dá)式包含1，2，…，n次常數(shù)項(xiàng)，公式如下所示：

通過統(tǒng)計(jì)NESSIE 計(jì)劃、CRYPTREC 計(jì)劃和ESTREAM 計(jì)劃，征集序列密碼算法NBF 操作特征，即對(duì)其狀態(tài)序列長度、參與運(yùn)算變量個(gè)數(shù)、項(xiàng)個(gè)數(shù)和次數(shù)進(jìn)行分析，如表1 所示，發(fā)現(xiàn)雖然位寬為12～256 bit，參與運(yùn)算的變量個(gè)數(shù)可能很多，約為12～128 個(gè)，但與項(xiàng)次數(shù)多數(shù)不超過6 次，因此相應(yīng)的NBF 結(jié)構(gòu)均是能實(shí)現(xiàn)最高次數(shù)為6 的變量結(jié)構(gòu)［12-14］。

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

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

1.2 NBFM 結(jié)構(gòu)實(shí)現(xiàn)能力分析

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

表2 NBFM 實(shí)現(xiàn)能力Table 2 NBFM Realization ability

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

圖1 NBFM 結(jié)構(gòu)Fig.1 NBFM structure

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

從表3 可以看出，NBFM 在實(shí)現(xiàn)4-4 和6-4 的s 盒上消耗資源較少，而在實(shí)現(xiàn)8 輸入變量的s 盒上時(shí)需要多個(gè)NBFM 級(jí)聯(lián)才能實(shí)現(xiàn)1 路輸出。NBFM 實(shí)現(xiàn)一個(gè)8-8 的s 盒與8-8 的RAM 如表4 所示?？梢钥闯?，NBFM 在實(shí)現(xiàn)8-8 s 盒上效率很低，性能指標(biāo)也并不如RAM 實(shí)現(xiàn)，但通過對(duì)8-8 的s 盒進(jìn)行進(jìn)一步細(xì)分發(fā)現(xiàn)，8-8 的s 盒中存在求逆和仿射變換構(gòu)造的類AESs 盒，這類s 盒可通過組合邏輯的方法化簡輸出的NBF 表達(dá)式，從而易于NBFM 適配。

表4 8-8 的s 盒適配資源評(píng)估Table 4 8-8 s box adaptation resource evaluation

2 類AESs 盒和非線性布爾函數(shù)可重構(gòu)研究

2.1 類AESs 盒可降解理論分析

在對(duì)文獻(xiàn)［7-8］進(jìn)行分析后發(fā)現(xiàn)，類AES 的s 盒存在2 種分解形式：GF（42）2和GF（（22）2）2。2 種分解形式區(qū)別在于基本模塊規(guī)模的不同，而適合NBFM這種2 輸入LUT 類型實(shí)現(xiàn)的是GF（（22）2）2，因此本文將根據(jù)混合基方法［17］推導(dǎo)s 盒分解后的不同模塊表達(dá)式。

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

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

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

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

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

S2、α乘和α2乘、M2、I2結(jié)果分別用C2、αC、α2C、CD、C-1表示，可得式（6）～式（10）。設(shè)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，結(jié)果分別如式（11）～式（15）所示：

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

2.2 類AESs 盒與NBFM 可重構(gòu)分析

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

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

Sbox_area=3M4+S4+I4+λ+異或，相當(dāng)于用51 個(gè)NBFM 加一部分異或門實(shí)現(xiàn)一個(gè)可分解的8-8 s 盒，這樣效率不如直接實(shí)現(xiàn)，由于M4布爾表達(dá)式是8 入4 出的結(jié)構(gòu)，如果直接采取NBFM 的6 變量模式搭建一個(gè)完備的NBF將導(dǎo)致資源浪費(fèi)，冗余度過高，應(yīng)該針對(duì)M4繼續(xù)分解。

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

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

圖4 M4電路Fig.4 M4 circuit

最后相當(dāng)于 用1 個(gè)NBFM 實(shí)現(xiàn)GF（16）上的乘法。最終的s 盒占用變?yōu)? 個(gè)NBFM 加一部分的異或門，相比將s 盒輸出展開寫成NBF 表達(dá)式的方法節(jié)約了近9 倍的NBFM 資源。

2.3 結(jié)合類AESs 盒的NBFM 結(jié)構(gòu)優(yōu)化分析

由2.1 節(jié)對(duì)塔域分解后的不同模塊表達(dá)式的推導(dǎo)可知，式（11）～式（15）復(fù)雜程度不一，映射到NBFM 上還是采用門級(jí)電路實(shí)現(xiàn)未定，根據(jù)推導(dǎo)出的表達(dá)式復(fù)雜程度，結(jié)合表達(dá)式輸入輸出特征，將各個(gè)模塊分為3 類實(shí)現(xiàn)形式：1）基于異或?qū)崿F(xiàn)平方S4乘和前后的同構(gòu)映射；2）基于NBFM 實(shí)現(xiàn)求逆3）基于改進(jìn)后的SNBFM 實(shí)現(xiàn)和M4乘法。圖5 所示為類AESs 盒適配的電路，可以看到只需用到4 個(gè)NBFM 便可以實(shí)現(xiàn)一個(gè)完整的類AESs 盒。

圖5 s 盒適配后的整體結(jié)構(gòu)Fig.5 Overall structure of s-box after adaptation

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

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

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

圖6 SNBFM 結(jié)構(gòu)Fig.6 SNBFM structure

3 性能評(píng)估

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

表9 電路性能指標(biāo)Table 9 Circuit performance index

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

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

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

表10 電路實(shí)現(xiàn)功能的對(duì)比Table 10 Comparison of circuit realization functions

4 結(jié)束語

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