流密碼非線性布爾函數(shù)可重構(gòu)運(yùn)算單元設(shè)計(jì)方法RA-NLBF

張宗仁，戴紫彬，劉燕江，張曉磊

流密碼非線性布爾函數(shù)可重構(gòu)運(yùn)算單元設(shè)計(jì)方法RA-NLBF

張宗仁1，2，戴紫彬1*，劉燕江1，張曉磊1

（1.解放軍信息工程大學(xué)，鄭州 450001； 2.31642部隊(duì)，云南 臨滄 677000）（ ? 通信作者電子郵箱daizb2004@126.com）

分組密碼中的S盒（多輸出）以及流密碼中的反饋函數(shù)都需要特殊的布爾函數(shù)來保證密碼算法的安全性。為解決現(xiàn)有流密碼算法中非線性布爾函數(shù)（NLBF）可重構(gòu)硬件運(yùn)算單元資源占用過大、時(shí)鐘頻率低等問題，提出一種高效的基于與非錐（AIC）的NLBF可重構(gòu)運(yùn)算單元設(shè)計(jì)方法（RA-NLBF）。以密碼學(xué)理論為基礎(chǔ)，在著重分析多種流密碼算法的NLBF特性，提取了涵蓋與項(xiàng)次數(shù)、與項(xiàng)個數(shù)、輸入端口數(shù)等NLBF函數(shù)特征的基礎(chǔ)上，提出基于“混合極性Reed-Muller（MPRM）”和“傳統(tǒng)布爾邏輯（TB）”雙邏輯混合形式的NLBF化簡方法，NLBF的與項(xiàng)數(shù)量減少29%，形成了適用于AIC的NLBF表達(dá)式；根據(jù)化簡后的表達(dá)中與項(xiàng)個數(shù)、與項(xiàng)次數(shù)分布等特征，設(shè)計(jì)了可重構(gòu)AIC單元和互聯(lián)網(wǎng)絡(luò)，形成可滿足現(xiàn)有公開流密碼算法中的NLBF運(yùn)算的可重構(gòu)單元?；贑MOS 180 nm工藝對提出的RA-NLBF進(jìn)行邏輯綜合驗(yàn)證，結(jié)果顯示該方法的面積為12 949.67 μm2，時(shí)鐘頻率達(dá)到505 MHz，與現(xiàn)有相同功能的單元可重構(gòu)序列密碼邏輯單元（RSCLU）相比，面積減少了59.7%，時(shí)鐘頻率提高了37.3%。

流密碼；可重構(gòu)實(shí)現(xiàn)；非線性布爾函數(shù)；與非錐；混合極性RM

0 引言

基于非線性反饋移位寄存器的流密碼正在成為現(xiàn)代流密碼的主流設(shè)計(jì)。運(yùn)算速度快、硬件占用空間小和功耗低的特性使此類密碼更適合需要安全通信的資源受限應(yīng)用。為了滿足流密碼算法安全特性并提高流密碼算法中布爾函數(shù)的平衡性、高代數(shù)次數(shù)、高非線性、相關(guān)免疫性等，設(shè)計(jì)者選擇目前公認(rèn)的各方面性質(zhì)較為平衡的非線性布爾函數(shù)（Non-Linear Boolean Function， NLBF）作為流密碼的構(gòu)建塊［1］。目前，NLBF的硬件實(shí)現(xiàn)包括通用實(shí)現(xiàn)和專用實(shí)現(xiàn)兩種方式。隨著可重構(gòu)邏輯陣列器件的興起和不斷發(fā)展，NLBF的通用實(shí)現(xiàn)方式正成為一個重要的研究方向。

通用實(shí)現(xiàn)方式主要集中在現(xiàn)場可編程陣列（Field-Programmable Gate Array， FPGA）和粗粒度可重構(gòu)陣列（Coarse-Grained Reconfigurable Array， CGRA），目前學(xué)術(shù)界普遍利用FPGA的查找表（Look Up Table， LUT）、選擇器（MUX）和寄存器等器件來實(shí)現(xiàn)各種布爾函數(shù)。文獻(xiàn)［2］中提出了一種基于“AND-LUT”混合的NLBF實(shí)現(xiàn)方法，其中與陣列用于實(shí)現(xiàn)高扇入邏輯電路，LUT用于實(shí)現(xiàn)低扇入邏輯結(jié)構(gòu)，相較于其他基于FPGA中LUT級聯(lián)的結(jié)構(gòu)，資源面積減少了46%；但未針對密碼算法中的NLBF運(yùn)算進(jìn)行優(yōu)化，資源利用率低。文獻(xiàn)［3］中利用布爾代數(shù)理論將NLBF進(jìn)行分解運(yùn)算，將高效布爾運(yùn)算分解成低次，采用流水線技術(shù)使各級實(shí)現(xiàn)不同的函數(shù)功能；但消耗的資源會隨著變量增加呈指數(shù)級增長。文獻(xiàn)［4］中提出了一種面向?qū)ΨQ密碼處理的可重構(gòu)結(jié)構(gòu)，整體結(jié)構(gòu)每行通過靈活的樹形互連，降低了互連復(fù)雜度，減少了面積，可完成大部分分組密碼和少部分流密碼的功能，具有較低的功耗及較高的面積利用率；但處理單元對NLBF適用性不強(qiáng)。文獻(xiàn)［5］中以提高資源利用率為目標(biāo)，以變量頻次為約束改進(jìn)適配算法，并設(shè)計(jì)單元互聯(lián)結(jié)構(gòu)，將資源利用率提高到91%以上；但該算法以LUT數(shù)量為利用率的計(jì)算數(shù)據(jù)，資源占用仍然較大。文獻(xiàn)［6］中分別設(shè)計(jì)了NLBF的線性和非線性部分，其中非線性部分的高次項(xiàng)采用與-異或陣列，低次項(xiàng)部分采用共享兩輸入端口的LUT級聯(lián)結(jié)構(gòu)實(shí)現(xiàn)；雖然架構(gòu)可以滿足現(xiàn)有公開密碼算法的NLBF，但高次項(xiàng)部分占用資源過大，同時(shí)低次項(xiàng)的共享端口給軟件映射增加了難度。文獻(xiàn)［7］在文獻(xiàn)［5］研究的基礎(chǔ)上，增加部分電路以實(shí)現(xiàn)多種S盒的功能，在功能上進(jìn)行了擴(kuò)展，提高了資源利用率；但增加了部分電路，在延遲上也沒有改進(jìn)?？偟膩碚f，現(xiàn)有研究均是基于LUT設(shè)計(jì)的NLBF可重構(gòu)運(yùn)算單元，然而LUT的高靈活性是以面積、延遲和功耗為代價(jià)的，密碼領(lǐng)域的邏輯函數(shù)結(jié)構(gòu)差別大、數(shù)量少，對于大位寬的復(fù)雜NLBF，由于LUT單元面積與輸入端口數(shù)目呈指數(shù)增長關(guān)系，利用大尺寸LUT單元實(shí)現(xiàn)時(shí)資源占用較大，而利用小尺寸LUT單元實(shí)現(xiàn)時(shí)級聯(lián)復(fù)雜，延遲增加；對于簡單的NLBF，可重構(gòu)單元資源冗余過大，利用率低。

本文首先從流密碼的NLBF設(shè)計(jì)原則入手，總結(jié)NLBF特性，針對NLBF輸入端口多、分布廣和存在極高與項(xiàng)次數(shù)特點(diǎn)，利用新興的與非錐（And-Inverter Cone， AIC）［8］結(jié)構(gòu)的大位寬輸入和多輸出特性實(shí)現(xiàn)NLBF，針對性地簡化NLBF表達(dá)式，提出了一種基于AIC的NLBF的可重構(gòu)運(yùn)算單元設(shè)計(jì)方法RA-NLBF（Reconfigurable operation unit AIC-based for Non-Linear Boolean Function），可以有效降低資源占用問題，避免了復(fù)雜的互聯(lián)關(guān)系，并降低了電路延遲。本文設(shè)計(jì)的可重構(gòu)運(yùn)算單元可以兼容現(xiàn)有流密碼算法的所有NLBF，并且資源占用小，時(shí)鐘頻率明顯提高。

1 流密碼中NLBF特性及實(shí)現(xiàn)方式分析

1.1　NLBF特性分析

流密碼（序列密碼）因加解密原理簡單，算法迅速快捷，在保密通信中扮演著不可替代的角色。布爾函數(shù)作為流密碼非線性組合部分的重要部件，它的密碼學(xué)性質(zhì)直接關(guān)系到整個流密碼系統(tǒng)的安全性。密碼學(xué)指標(biāo)［9］主要為：平衡性準(zhǔn)則、代數(shù)次數(shù)（線性復(fù)雜度）、非線性度、相關(guān)免疫（彈性）和代數(shù)免疫度。

但諸多安全性指標(biāo)很難同時(shí)兼顧，彼此制約，指標(biāo)之間本身就是矛盾的關(guān)系。例如：

為了更直觀地分析流密碼中NLBF的特性，本文提取近幾年新設(shè)計(jì)的輕量級流密碼和傳統(tǒng)經(jīng)典流密碼中的NLBF，對與項(xiàng)次數(shù)分布和端口數(shù)目等特征進(jìn)行統(tǒng)計(jì)分析，如表1所示。其中：1次項(xiàng)占比約30.6%，1次項(xiàng)是函數(shù)平衡性的保證；2次與項(xiàng)占比約34.2%，大部分兩兩之間無公共變量，這是高非線性度的特征要求；3次與項(xiàng)和4次與項(xiàng)總占比約31.8%，這是為了兼顧高非線性同時(shí)提高代數(shù)次數(shù)；高于4次項(xiàng)部分僅占3.4%，僅存在于部分算法中，這是高代數(shù)次數(shù)與高相關(guān)免疫性、高非線性之間的中和結(jié)果。根據(jù)各個安全指標(biāo)的定義可知，變元個數(shù)越大，各種安全特性呈線性（指數(shù)）變化。流密碼中NLBF輸入端口數(shù)目分布集中于［13，18］，占比約44.9%，其中超過24個輸入端口的仍占比約14.3%，13個輸入端口以上占73.5%，增加輸入端口數(shù)目可以盡可能兼顧幾種設(shè)計(jì)原則，從而提高安全性。

表1　流密碼NLBF與項(xiàng)次數(shù)、輸入端口頻率分布

根據(jù)NLBF的設(shè)計(jì)原則和表1統(tǒng)計(jì)結(jié)果，總結(jié)流密碼中NLBF具有以下特點(diǎn)：

1）高次與項(xiàng)（4次以上）僅占比約3.4%，僅有個別NLBF涉及高次與項(xiàng)，高于7次與項(xiàng)的僅有Toyocrypt-hs1算法。

2）低次與項(xiàng)占比約96.6%，但很多算法中低次與項(xiàng)之間關(guān)系交叉相關(guān)，或完全無關(guān)。

3）端口數(shù)13以上占比約73.5%，分布范圍也比較大，即NLBF位寬較大，特別是在輕量級流密碼中得到越來越多使用。

1.2　基于LUT結(jié)構(gòu)的NLBF實(shí)現(xiàn)方式分析

表2　密碼算法中的NLBF任意4變量組合形式

2 基于AIC的NLBF實(shí)現(xiàn)設(shè)計(jì)分析

2.1　AIC原理

2012年，瑞士洛桑理工大學(xué)Parandeh博士等受到用于電路映射工具的基本映射單元AIG（And-Inverter Graphs）［10］的啟發(fā)，提出了一種更貼近電路邏輯表達(dá)式的通用邏輯單元與非錐（AIC）結(jié)構(gòu)，這種深度約束型邏輯結(jié)構(gòu)在提高可重構(gòu)陣列性能、面積和功耗等指標(biāo)上展現(xiàn)出了可觀的潛力。

圖1　三級AIC結(jié)構(gòu)

2.2　AIC的結(jié)構(gòu)特點(diǎn)分析

近年來，黃志洪［11］對AIC中間節(jié)點(diǎn)進(jìn)行定制化改進(jìn)，大幅改善了AIC結(jié)構(gòu)由于配置信息不同而可能造成的延遲毛刺并降低了延遲；在大量不同類型邏輯電路測試后，對輸入端和輸出端的交叉開關(guān)（Crossbar）進(jìn)行優(yōu)化設(shè)計(jì)［12］，與基于LUT相比，基于AIC的FPGA全局面積減少了10%，延遲降低了30%［13］。

從1.1節(jié)可知，73.5%的流密碼算法中NLBF的輸入變量在13個以上，使用尺寸為13的LUT顯然資源浪費(fèi)極大，若采用多級互聯(lián)方式，會造成資源浪費(fèi)和延遲增加。即使某些架構(gòu)可以共享LUT的輸入端口，但由于流密碼算法中高非線性度的要求，需要盡可能避免公共變量的與項(xiàng)，因此可以共享的端口也極有限，節(jié)省資源有限。相較于LUT結(jié)構(gòu)，由于AIC結(jié)構(gòu)的多輸入多輸出的特點(diǎn)，一個4-AIC可以滿足16個2次以下的與項(xiàng)，或8個4次以下的與項(xiàng)，與項(xiàng)之間相互獨(dú)立。由1.1節(jié)可知，2次以下的與項(xiàng)占流密碼與項(xiàng)總數(shù)的64.8%，4次以下與項(xiàng)占流密碼與項(xiàng)總數(shù)的96.6%。因此，對于流密碼算法中NLBF，AIC結(jié)構(gòu)作為硬件實(shí)現(xiàn)電路有顯著的優(yōu)勢。

3 流密碼中NLBF化簡

3.1　基于AIC結(jié)構(gòu)實(shí)現(xiàn)布爾函數(shù)的特點(diǎn)分析

一個任意的2變量布爾函數(shù)有10種表達(dá)形式（除了常數(shù)項(xiàng)和1變量形式外），由第2章可知，AIC結(jié)構(gòu)的一個節(jié)點(diǎn)可以實(shí)現(xiàn)8種2輸入邏輯，不能實(shí)現(xiàn)的2種分別是異或、同或。一個異或（同或）邏輯若采用多節(jié)點(diǎn)級聯(lián)方式，需要3個節(jié)點(diǎn)，其中一條支路的輸入和另一條支路完全相同，則一條支路端口被重復(fù)占用，整體AIC的輸入變量減少。對一個4?AIC，表達(dá)式第一級運(yùn)算出現(xiàn)異或，則占用3個節(jié)點(diǎn)、2級電路，輸入變量最多14個；第二級出現(xiàn)，則占用7個節(jié)點(diǎn)、3級電路，輸入變量最多12個；第三級出現(xiàn)異或，則占用全部4-AIC節(jié)點(diǎn)15個，輸入變量最多8個。由此可見，AIC結(jié)構(gòu)不適合異或運(yùn)算的實(shí)現(xiàn)，因此在多個AIC級聯(lián)時(shí)，將異或邏輯拆解，避免在同一個AIC單元中實(shí)現(xiàn)異或。

AIC結(jié)構(gòu)另一個顯著特點(diǎn)是輸入和輸出可以根據(jù)需要取反。在代數(shù)理論中，多種布爾邏輯通過輸入或輸出取反，或輸入變量位置變換后具有相同的函數(shù)結(jié)構(gòu)，即與項(xiàng)個數(shù)和次數(shù)完全相同，則稱這些邏輯函數(shù)NPN（Negation-Permutation-Negation）等價(jià)。通過NPN等價(jià)分類，可以大幅減少函數(shù)的類別，利用相同的電路結(jié)構(gòu)實(shí)現(xiàn)更多的邏輯功能。在函數(shù)化簡時(shí)，應(yīng)充分利用此特性，用最簡的NPN等價(jià)類表達(dá)式，取代同一等價(jià)類中復(fù)雜的表達(dá)式。

3.2　NLBF化簡

根據(jù)3.1節(jié)分析結(jié)果，本文提出一種“混合極性RM（Mixed Polarity Reed-Muller， MPRM）”［14］和“傳統(tǒng)布爾（Traditional Boolean function， TB）邏輯”雙邏輯混合化簡NLBF表達(dá)式的方法，以減少與項(xiàng)，并將異或運(yùn)算剝離到其他電路中實(shí)現(xiàn)。

表3　與、的關(guān)系

AIC結(jié)構(gòu)中的輸入取反操作，對應(yīng)MPRM邏輯的極性配置。輸出取反操作可以將“與”邏輯和“或”邏輯進(jìn)行互換。在布爾運(yùn)算中一個高次的與項(xiàng)無法通過低次與項(xiàng)異或得到，因此，本文針對密碼算法布爾函數(shù)特性和AIC結(jié)構(gòu)特點(diǎn)，提出兩種情況下的消除與項(xiàng)的方法。

1）利用極性轉(zhuǎn)化消除低次與項(xiàng)。

根據(jù)異或運(yùn)算的性質(zhì)，式（3）是兩種轉(zhuǎn)化情況：第一種，利用異或結(jié)合律對不同的變量取反以消除低次與項(xiàng)；第二種，同一個函數(shù)中變量既可以存在原相也可以存在反相，以達(dá)到減少與項(xiàng)的目的。在AIC結(jié)構(gòu)中通過配置輸入取反和輸出取反即可實(shí)現(xiàn)。

2）利用AIC多輸出功能復(fù)用相同與項(xiàng)。

例如Toyocrypt-hs1算法中有63次與項(xiàng)、17次與項(xiàng)以及4次與項(xiàng)。

經(jīng)過分析，17次與項(xiàng)包含于63次與項(xiàng)中，4次與項(xiàng)包含于63次與項(xiàng)中。如式（5）所示，用極性轉(zhuǎn)化的方法只能消除一個17次與項(xiàng)或一個4次與項(xiàng)。若將4次與項(xiàng)的輸出直接復(fù)用，則可以消除2個與項(xiàng)只用一個63次與項(xiàng)的電路實(shí)現(xiàn)函數(shù)。

經(jīng)過化簡后，與項(xiàng)個數(shù)得到明顯優(yōu)化，3次項(xiàng)減少66.5%，總項(xiàng)數(shù)減少28.1%，Toyocrypt-hs1算法減少一個4次和一個17次與項(xiàng)，資源占用得到較大優(yōu)化。1次與項(xiàng)和2次與項(xiàng)在AIC結(jié)構(gòu)中均要使用一個可編程2輸入與節(jié)點(diǎn)，消耗同等的資源，與化簡前相比，1次與項(xiàng)和2次與項(xiàng)總數(shù)量減少26.6%。在AIC結(jié)構(gòu)中，3次與項(xiàng)和4次與項(xiàng)占用資源相同且大概是2次與項(xiàng)的3倍，5次與項(xiàng)和6次與項(xiàng)占用資源相同且大概是2次與項(xiàng)的7倍，一個63次與項(xiàng)資源占用大概是2次與項(xiàng)的63倍?；喓罂傮w資源占用至少降低29%。

圖2　NLBF化簡前后結(jié)果比較

4 NLBF的可重構(gòu)單元設(shè)計(jì)

4.1　可重構(gòu)運(yùn)算單元總體架構(gòu)

NLBF可重構(gòu)運(yùn)算單元如圖3所示，主要分為三大部分：AIC運(yùn)算（AIC operation）、異或陣列（Xor array）和配置存儲單元（Configuration Reg unit）。其中AIC運(yùn)算單元以基于AIC設(shè)計(jì)改進(jìn)型AIC-g作為基本構(gòu)件，采用3個Part組合，共20個2?AIC-g、6個3-AIC-g和1個6-AIC-g（此部分在下一節(jié)詳細(xì)分析）。AIC運(yùn)算部分單個Part為64 bit輸入（共計(jì)192 bit輸入），此單元可以實(shí)現(xiàn)最多64次與項(xiàng)，最多48個4次與項(xiàng)和最多96個2次與項(xiàng)的函數(shù)，生成4 bit輸出。

圖3　RA-NLBF總體布局

4.2　AIC結(jié)構(gòu)的功能定制設(shè)計(jì)和級聯(lián)結(jié)構(gòu)分析

對化簡后的NLBF中與項(xiàng)次數(shù)和異或操作進(jìn)行分析：

1）與項(xiàng)次數(shù)大部分不高于4次，有極個別大于8次，但只出現(xiàn)在了一個算法中，且可以化簡合并成一個與項(xiàng)；與項(xiàng)最后一級不需要取反。

2）大部分異或運(yùn)算出現(xiàn)在第一級、第二級、第三級，極個別函數(shù)中，異或運(yùn)算出現(xiàn)在四級以上（目前僅有Toyocrypt-hs1中存在）。

由于AIC結(jié)構(gòu)對異或運(yùn)算支持能力差，將AIC-g的輸出直接送入異或陣列中，通過配置信息選擇需要的與項(xiàng)結(jié)果，避免在AIC-g中計(jì)算異或。如表4，對32種NLBF進(jìn)行適配，本文中一個3-AIC-g可以轉(zhuǎn)變?yōu)?個2-AIC-g，一個6?AIC?g可以轉(zhuǎn)變?yōu)?6個2-AIC-g，表中以一個2-AIC-g為基本單位。由表4中2-AIC-g占用情況分析可得，最多需要48個，最少需要2個，大部分算法在16個以下。

表4　常用流密碼算法［15］NLBF的資源占用

注：Z表示鐘控函數(shù)，F(xiàn)表示反饋函數(shù)，M表示密鑰生成函數(shù)，V表示初始化，S表示輸出函數(shù)。

通過以上分析，如圖4，將10個2-AIC-g與3個3-AIC-g并行為一組，選擇所需AIC輸出進(jìn)入異或陣列生成1 bit輸出（Part-A），另一組相同單元（Part-B）可生成第2 bit輸出。如圖5，為滿足極少數(shù)高次項(xiàng)需求，增加一個6-AIC-g單元，所有輸出經(jīng)過選擇后進(jìn)入異或陣列生成1 bit輸出（Part-C）。單個Part可以實(shí)現(xiàn)大部分算法的NLBF，3個Part輸出異或，生成一個新的1 bit輸出，可實(shí)現(xiàn)某些較復(fù)雜的NLBF。

5 NLBF映射與實(shí)驗(yàn)結(jié)果分析

Achterbahn加密和解密通過將二進(jìn)制偽隨機(jī)序列（稱為密鑰流）分別按位添加到明文字符串或密文字符串實(shí)現(xiàn)。Achterbahn-80的密鑰流生成器部署了11個原始二進(jìn)制非線性反饋移位寄存器，Achterbahn-128的密鑰流生成器部署了13個原始非線性反饋移位寄存器，并包含Achterbahn-80的密鑰流生成器作為子結(jié)構(gòu)。Achterbahn的NLBF目前也被許多輕量級流密碼采用，如Lizard。算法中密鑰生成函數(shù)直接采用了Achterbahn算法中的A10函數(shù)。如表5，本文對Achterbahn-A10算法的化簡過程進(jìn)行演示。

圖4　Part-A（Part-B）的級聯(lián)結(jié)構(gòu)

圖5　Part-C的級聯(lián)結(jié)構(gòu)

表5　Achterbahn-80/128-A10適配結(jié)果

根據(jù)圖3可知，最長關(guān)鍵路徑經(jīng)過Patr?C部分由［3］輸出，設(shè)定均選用2輸入1輸出的MUX、NAND、XOR標(biāo)準(zhǔn)單元，則?AIC?g延遲計(jì)算公式為：

在CMOS 180 nm工藝下進(jìn)行邏輯綜合，各項(xiàng)性能指標(biāo)如表6所示?？傃訒r(shí)為1.98 ns，總面積為12 949.67 μm2，等效兩輸入與非門約為0.129萬門，此時(shí)的時(shí)鐘頻率為505 MHz。

表6　可重構(gòu)單元的面積和延遲

在CMOS 180 nm工藝下，將性能與以往設(shè)計(jì)進(jìn)行對比，如表7所示，2003年提出的RNF［16］架構(gòu)主要是對寄存器并行化的設(shè)計(jì)，對資源面積和時(shí)鐘頻率未做優(yōu)化，它的延遲與本文相當(dāng)，面積卻增加205倍；2009年提出的RPNF［17］對NLBF進(jìn)行了簡單優(yōu)化，等效門數(shù)為1.31萬門，延遲為6.01 ns；2013年提出的TNF［18］對NLBF表達(dá)式進(jìn)行處理，將線性與非線性分開設(shè)計(jì)，但在優(yōu)化時(shí)只對線性部分進(jìn)行優(yōu)化，事實(shí)上非線性部分占用資源更大，運(yùn)算寬度可以達(dá)到256 bit，等效門數(shù)0.44萬門，延遲為5.24 ns；2016年提出的可重構(gòu)序列密碼邏輯單元（Reconfigurable Logic Unit for Sequence Cryptographic， RSCLU）［5］以提高NLBF資源利用率為目的，提取函數(shù)的高頻變量作為共享LUT輸入，有效降低了可重構(gòu)單元的資源占用，但資源利用率以LUT為基本單元，未考慮LUT單元自身的資源冗余問題。2019的文獻(xiàn)［6］的方法僅在一定程度上改善了外部互聯(lián)，但面積占用和延遲都不理想。2022年發(fā)表的SNBFM［7］對S盒的實(shí)現(xiàn)進(jìn)行了改進(jìn)，并用65 nm工藝節(jié)點(diǎn)實(shí)現(xiàn)，增加了電路，延長了關(guān)鍵路徑，理論上面積和延遲都要比RSCLU大。與RSCLU相比，文本方法面積占用減少59.7%，延遲降低37.3%，專用性更強(qiáng)，資源利用較充分。

表7　不同方法的性能對比

6 結(jié)語

本文提出的基于AIC結(jié)構(gòu)的可重構(gòu)NLBF運(yùn)算單元設(shè)計(jì)方法RA-NLBF，使用較少的資源，獲得明顯的時(shí)鐘頻率提升。本文針對現(xiàn)有算法進(jìn)行分析，因此結(jié)構(gòu)的通用性可能受影響；但從理論上也進(jìn)行了定性分析，設(shè)計(jì)方法可推廣，適用于對未來新出現(xiàn)的NLBF可重構(gòu)單元設(shè)計(jì)。未來還將在映射算法和外部互聯(lián)結(jié)構(gòu)作進(jìn)一步研究。

[1] CRAMA Y， HAMMER P L. Boolean Functions： Theory， Algorithms， and Applications［M］. Cambridge： Cambridge University Press， 2011： 564-607.

[2] CHEN L G， LAI J M， TONG J R. An AND-LUT based hybrid FPGA architecture［J］. Chinese Journal of Semiconductors， 2007， 28（3）：398-403.

[3] SARKAR P， MAITRA S. Efficient implementation of "large" stream cipher systems［C］// Proceedings of the 2001 International Workshop on Cryptographic Hardware and Embedded Systems， LNCS 2162. Berlin： Springer， 2001： 319-332.

[4] WANG B， LIU L. A flexible and energy-efficient reconfigurable architecture for symmetric cipher processing［C］// Proceedings of the 2015 IEEE International Symposium on Circuits and Systems. Piscataway： IEEE， 2015： 1182-1185.

[5] 戴紫彬，王周闖，李偉，等.可重構(gòu)非線性布爾函數(shù)利用率模型研究與硬件設(shè)計(jì)［J］. 電子與信息學(xué)報(bào)， 2017， 39（5）： 1226-1232.（DAI Z B， WANG Z C， LI W， et al. Hardware implementation and utilization model research for reconfigurable non-linear Boolean function［J］. Journal of Electronics and Information Technology， 2017， 39（5）： 1226-1232.）

[6] SU Y， SHEN J， WANG W. Reconfigurable design and implementation of nonlinear Boolean function for cloud computing security platform［J］. International Journal of Information and Computer Security， 2019， 11（2）：145-159.

[7] 連宜新，陳韜，李偉，等. 兩類非線性密碼組件可重構(gòu)研究與電路設(shè)計(jì)［J］. 計(jì)算機(jī)工程， 2022， 48（2）：156-163， 172.（LIAN Y X， CHEN T， LI W， et al. Reconfigurable research and circuit design of two types of nonlinear cryptographic components［J］. Computer Engineering， 2022， 48（2）：156-163， 172.）

[8] PARANDEH-AFSHAR H， BENBIHI H， NOVO D， et al. Rethinking FPGAs： elude the flexibility excess of LUTs with and-inverter cones［C］// Proceedings of the 2012 ACM/SIGDA International Symposium on Field Programmable Gate Arrays. New York， ACM， 2012：119-128.

[9] 葛徽. 流密碼中密碼函數(shù)的設(shè)計(jì)與分析［D］. 西安：西安電子科技大學(xué)， 2021：11-23.（GE H. Analysis and design of cryptographic functions for stream ciphers［D］. Xi’an： Xidian University， 2021： 11-23.）

[10] MISHCHENKO A， CHATTERJEE S， BRAYTON R. DAG-aware AIG rewriting： a fresh look at combinational logic synthesis［C］// Proceedings of the 43rd ACM/IEEE Design Automation Conference. New York： ACM， 2006： 532-535.

[11] 黃志洪.現(xiàn)場可編程門陣列（FPGA）異質(zhì)邏輯與存儲互連結(jié)構(gòu)研究［D］.北京：中國科學(xué)院大學(xué)，2016：75-91.（HUANG Z H. Research on heterogeneous logic and storage interconnection structure of Field Programmable Gate Array （FPGA）［D］. Beijing： University of Chinese Academy of Sciences， 2016： 75-91.）

[12] 黃志洪，李威，楊立群，等.一種基于與非錐簇架構(gòu)FPGA輸入交叉互連設(shè)計(jì)優(yōu)化方法［J］.電子與信息學(xué)報(bào)，2016，38（9）： 2397-2404.（HUANG Z H， LI W， YANG L Q， et al. An input crossbar optimization method for and-inverter cone based FPGA［J］. Journal of Electronics and Information Technology， 2016， 38（9）： 2397-2404.）

[13] RAI S， NATH P， RUPANI A， et al. A survey of FPGA logic cell designs in the light of emerging technologies［J］. IEEE Access， 2021， 9： 91564-91574.

[14] 李輝. 混合極性Reed-Muller邏輯電路功耗和面積優(yōu)化［D］. 寧波：寧波大學(xué)， 2011：41-45.（LI H. Power and area optimization of mixed polarity Reed-Muller logic circuits［D］. Ningbo： Ningbo University， 2011：41-45.）

[15] 趙石磊，劉玲，黃海，等. 流密碼算法、架構(gòu)與硬件實(shí)現(xiàn)研究［J］. 密碼學(xué)報(bào)， 2021， 8（6）： 1039-1057.（ZHAO S L， LIU L， HUANG H， et al. Algorithm， architecture and hardware implementation of stream cipher［J］. Journal of Cryptologic Research， 2021， 8（6）： 1039-1057.）

[16] 秦曉懿，王瀚晟，曾烈光.線性和非線性寄存器系統(tǒng)的并行化技術(shù)［J］. 電子學(xué)報(bào)，2003，31（3）：406-410. （QIN X Y， WANG H S， ZENG L G. Parallelization techniques for linear and non-linear register systems［J］. Acta Electronica Sinica， 2003， 31（3）： 406-410.）

[17] 李偉.面向序列密碼的反饋移位寄存器可重構(gòu)并行化設(shè)計(jì)技術(shù)研究［D］.鄭州：解放軍信息工程大學(xué)，2009：34-35.（LI W. Research on technology of reconfigurable parallel feedback shift register targeted at stream cipher［D］. Zhengzhou： PLA Information Engineering University， 2009： 34-35.）

[18] 陳韜，楊萱，戴紫彬，等.面向序列密碼的非線性反饋移位寄存器可重構(gòu)并行化設(shè)計(jì)［J］.上海交通大學(xué)學(xué)報(bào)，2013，47（1）：28-32. （CHEN T， YANG X， DAI Z B， et al. Design of a reconfigurable parallel nonlinear feedback shift register structure targeted at stream cipher［J］. Journal of Shanghai Jiao Tong University， 2013， 47（1）： 28-32.）

RA-NLBF： design method of reconfigurable operation unit for stream cipher non-linear Boolean function

ZHANG Zongren1，2， DAI Zibin1*， LIU Yanjiang1， ZHANG Xiaolei1

（1，450001，；231642，677000，）

Both the S-box （multiple outputs） in block ciphers and the feedback function in stream ciphers require special Boolean functions to ensure the security of the cipher algorithm. To solve the problems of excessive resource consumption of reconfigurable hardware operation units and low clock frequency caused by Non-Linear Boolean Function （NLBF） in the existing algorithms of stream cipher， a high-efficiency AIC（And-Inverter Cone）-based design scheme for NLBF reconfigurable operation units was proposed， namely RA-NLBF. Based on the theories of cryptography， after analyzing the NLBF characteristics of various stream cipher algorithms and extracting the function features of NLBF including the times of AND terms， the number of AND terms， and the number of input ports， an NLBF simplification method based on the dual-logic hybrid form of “Mixed Polarity Reed-Muller （MPRM）” and “Traditional Boolean function （TB）” was proposed， which reduced the number of NLBF AND terms by 29% and formed an NLBF expression suitable for the AIC. Based on the simplified expression characteristics， such as the distribution of the number of AND terms and the times of AND terms， reconfigurable AIC units and interconnection networks were designed to form the reconfigurable units that can satisfy the NLBF operation in the existing public stream cipher algorithms. The proposed RA-NLBF was verified by logic synthesis based on CMOS 180 nm technology， and the results show that the area of RA-NLBF is 12 949.67 μm2， and the clock frequency reaches 505 MHz， which is a 59.7% reduction in area and a 37.3% increase in clock frequency compared with Reconfigurable Logic Unit for Sequence Cryptographic （RSCLU）， an existing method with the same function.

stream cipher; reconfigurable implementation; Non-Linear Boolean Function (NLBF); And-Inverter Cone (AIC); Mixed Polarity Reed-Muller (MPRM)

1001-9081（2023）11-3527-07

10.11772/j.issn.1001-9081.2022111690

2022?11?15；

2023?03?07；

“核高基”國家科技重大專項(xiàng)（2018ZX01027101?004）。

張宗仁（1994—），男，湖北襄陽人，碩士研究生，主要研究方向：安全專用芯片設(shè)計(jì)、可重構(gòu)計(jì)算； 戴紫彬（1966—），男，河南西峽人，教授，博士生導(dǎo)師，博士，主要研究方向：信息安全、體系結(jié)構(gòu)； 劉燕江（1990—），男，河南南陽人，博士，主要研究方向：安全專用芯片設(shè)計(jì)、側(cè)信道攻擊； 張曉磊（1992—），男，河北青縣人，碩士研究生，主要研究方向：安全專用芯片設(shè)計(jì)。

TP309.7； TN492

A

2023?03?20。

This work is partially supported by National Science and Technology Major Project （2018ZX01027101-004）.

ZHANG Zongren， born in 1994， M. S. candidate. His research interests include special security chip design， reconfigurable computing.

DAI Zibin， born in 1966， Ph. D.， professor. His research interests include information security， architecture.

LIU Yanjiang， born in 1990， Ph. D. His research interests include special security chip design， side-channel attacks.

ZHANG Xiaolei， born in 1992， M. S. candidate. His research interests include special security chip design.