S 盒和P 置換安全性指標(biāo)評(píng)估方法的研究與比較*

劉繼榮 王 克 曹宇軒

1.北京電子科技學(xué)院，北京市 100070

2.浙江省密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室，杭州師范大學(xué)，杭州市 311121

1 引言

自第三次科技革命以來(lái)，計(jì)算機(jī)和互聯(lián)網(wǎng)極大地改變了人類(lèi)的生活方式，信息傳播呈指數(shù)爆炸式的增長(zhǎng)，同時(shí)信息安全問(wèn)題也日益嚴(yán)峻。 比如，個(gè)人數(shù)據(jù)的泄露會(huì)導(dǎo)致不法分子進(jìn)行電信詐騙；國(guó)家機(jī)密的泄露會(huì)導(dǎo)致社會(huì)穩(wěn)定、經(jīng)濟(jì)發(fā)展、國(guó)家安全受到嚴(yán)重威脅。 在這樣的背景下，保護(hù)信息安全已然刻不容緩。 密碼學(xué)是保護(hù)數(shù)據(jù)和通信安全的重要技術(shù)，是信息安全的基石［1］。

分組密碼是密碼學(xué)的重要組成部分，具有速度快、易于標(biāo)準(zhǔn)化和便于軟件實(shí)現(xiàn)等特點(diǎn)，主要應(yīng)用于數(shù)據(jù)的加解密處理［2］。 分組密碼最常用的兩 種 結(jié) 構(gòu) 為： Feistel 結(jié) 構(gòu) 和SP 結(jié) 構(gòu)［3］。Feistel 結(jié)構(gòu)有好的對(duì)稱性，其重要代表為數(shù)據(jù)加密標(biāo)準(zhǔn)DES（Data Encryption Standard）；SP 結(jié)構(gòu)可看成Feistel 結(jié)構(gòu)的推廣，其代表為高級(jí)數(shù)據(jù)加密標(biāo)準(zhǔn)AES（Advanced Encryption Standard）。分組密碼的安全性設(shè)計(jì)原則包含混淆原則和擴(kuò)散原則兩個(gè)方面。 特別地，SP 結(jié)構(gòu)中的S 是指混淆層，一般由若干個(gè)S 盒并置而成，它們是非線性部件，主要起混淆的作用，同時(shí)也是密碼算法安全性的重要保障；P 是指P 置換，一般由一個(gè)置換或一個(gè)可逆變換構(gòu)成，主要起擴(kuò)散作用，大多數(shù)情況下采用線性變換，也稱作P 置換。作為分組算法的核心部件，S 盒和P 置換在算法的設(shè)計(jì)與分析中扮演重要的角色。

S 盒是分組密碼中重要的非線性部件，很大程度上影響著整個(gè)密碼算法的安全性。 它首次出現(xiàn)在Lucifer 密碼［4］中，隨后因DES 密碼［5］的使用而廣為流行。 S 盒是密碼算法能夠抵抗差分分析和線性分析等攻擊的重要保障。 特別地，DES 密碼因?yàn)镾 盒的不平衡性遭到了差分分析和線性分析，AES 密碼［6］因?yàn)镾 盒存在代數(shù)表達(dá)式項(xiàng)數(shù)少的弱點(diǎn)招致代數(shù)攻擊。 S 盒的密碼指標(biāo)主要有差分均勻度［7］、非線性度［8］、代數(shù)次數(shù)與代數(shù)項(xiàng)數(shù)［9］、擴(kuò)散性［10］、嚴(yán)格雪崩性［11］、代數(shù)免疫度［12］，主要用來(lái)評(píng)估抵抗差分分析、線性分析、代數(shù)攻擊的能力。

P 置換的作用是擴(kuò)散，是分組密碼中重要的線性組件。 P 置換作為迭代型分組密碼的一個(gè)很重要的部件，它的設(shè)計(jì)不但影響分組密碼算法的安全性，而且影響分組密碼在軟硬件中的實(shí)現(xiàn)效率。 性能良好的P 置換可以有效地抵抗一些著名的密碼攻擊，如差分分析［13］和線性分析［14］。 P 置換的安全性能主要由分支數(shù)［15，16］來(lái)衡量，P 置換的分支數(shù)越小，分組密碼越容易遭受差分分析、線性分析以及一些未知分析方法的攻擊。

本文對(duì)分組密碼算法關(guān)鍵部件S 盒和P 置換進(jìn)行評(píng)估與設(shè)計(jì)，主要貢獻(xiàn)如下：

（1）針對(duì)S 盒與P 置換的安全指標(biāo)，包括S盒的差分均勻度、非線性度、代數(shù)次數(shù)、代數(shù)項(xiàng)數(shù)、雪崩特性、擴(kuò)散特性、代數(shù)免疫度、代數(shù)項(xiàng)數(shù)、不動(dòng)點(diǎn)個(gè)數(shù)以及P 置換的矩陣分支數(shù)，提出P置換新的指標(biāo)評(píng)估算法，匯總這些安全指標(biāo)的評(píng)估方法，比較各評(píng)估方法的優(yōu)缺點(diǎn)、可用性、實(shí)現(xiàn)難度。

（2）基于S 盒和P 置換的安全指標(biāo)評(píng)估方法，選擇其中有效的評(píng)估方法，對(duì)重要分組密碼算法中S 盒和P 置換進(jìn)行評(píng)估。 參考AES 算法的設(shè)計(jì)原理，結(jié)合當(dāng)前流行的超輕量級(jí)分組密碼算法PRESENT［17］，并運(yùn)用現(xiàn)代分組密碼設(shè)計(jì)中的技巧，篩選出現(xiàn)行標(biāo)準(zhǔn)下效率和安全性最優(yōu)的S 盒與P 置換的設(shè)計(jì)方案。

2 預(yù)備知識(shí)

下面給出關(guān)于S 盒和P 置換的相關(guān)知識(shí)。

2.1 S 盒

其中x＝（x1，…，xn）∈Fn2，對(duì)每一個(gè)1 ≤i≤m，fi∈βn（n元布爾函數(shù)全體）稱為S 盒的輸出函數(shù)。

2.2 P 置換

分組密碼的P 置換都可以表示為有限域上的線性變換操作，接下來(lái)我們需要對(duì)線性變換進(jìn)行具體分析，本節(jié)給出分支數(shù)的定義。

分支數(shù)的概念是由J.Deamen 最先提出的［15，16］。 分支數(shù)能夠表示在連續(xù)兩輪的差分或者線性特征中最小的活躍S 盒數(shù)量。

定義1［18］：令θ： （F2m）n→ （F2m）nx→θ（x）＝y(tǒng)是一個(gè)變換，x＝（x1，…，xn）∈（F2m）n；則θ的分支數(shù)計(jì)算方法如公式（1-1）所示：

公式（1-1）中ωb（x） 是非零xi（1 ≤i≤m）的數(shù)量，被稱作x 的漢明重量。

定義2［18］：線性變換θ的差分分支數(shù)計(jì)算方法如公式（1-2）所示：

由數(shù)學(xué)知識(shí)可知，任意的線性變換θ一般能夠用矩陣M來(lái)實(shí)現(xiàn)，θt表示θ的轉(zhuǎn)置，于是θt能夠用Mt刻畫(huà)出來(lái)。

定義3［18］：線性變換θ的線性分支數(shù)計(jì)算方法如公式（1-3）所示：

P 置換的擴(kuò)散性能可以通過(guò)分支數(shù)來(lái)衡量，分支數(shù)越大，擴(kuò)散性能越好。 所以，在構(gòu)造P 置換時(shí)要求分支數(shù)盡量達(dá)到最大。 當(dāng)進(jìn)行差分攻擊時(shí)，第一步是構(gòu)造差分路徑，在一條差分路徑中，如果S 盒的輸入存在差分，那么稱該S 盒為活躍的，分支數(shù)就是最小活躍S 盒的個(gè)數(shù)。 一個(gè)線性變換的差分（線性）分支數(shù)越大，那么在進(jìn)行差分（線性）攻擊時(shí)要選擇的明文數(shù)量就越多。 所以說(shuō)，分支數(shù)是構(gòu)造P 置換的關(guān)鍵性準(zhǔn)則之一。

對(duì)于任意輸入x，肯定滿足ωb（θ（x）） ≤n，于是當(dāng)取漢明重量等于1 的輸入時(shí)，分支數(shù)能夠達(dá)到的最大值為n＋1。 分支數(shù)為n＋1 時(shí)，P 置換的擴(kuò)散性能是最優(yōu)的，該P(yáng) 置換被稱為最優(yōu)P置換。

定義4［15］：將線性分支數(shù)和差分分支數(shù)同時(shí)達(dá)到最大值n＋1 的變換稱作最優(yōu)擴(kuò)散變換，其對(duì)應(yīng)的矩陣稱作最優(yōu)擴(kuò)散矩陣，簡(jiǎn)稱作MDS 矩陣。

3 對(duì)S 盒評(píng)估方法的比較

分組密碼算法的安全性依賴于關(guān)鍵組件的安全性。 因此對(duì)分組密碼的關(guān)鍵組件進(jìn)行安全性評(píng)估是分組密碼算法安全性評(píng)估中必不可少的一部分。 本節(jié)研究了分組密碼的S 盒，P 置換兩個(gè)關(guān)鍵組件的安全性評(píng)估指標(biāo)，并匯總了當(dāng)前的一些安全性評(píng)估方法，同時(shí)對(duì)與這些方法進(jìn)行比對(duì)分析。

在關(guān)鍵組件的評(píng)估方面，S 盒的安全性很大程度上決定了整個(gè)密碼算法的安全性，因此我們對(duì)S 盒的安全性進(jìn)行相關(guān)性質(zhì)的評(píng)估。

3.1 S 盒的安全性評(píng)估

如何全面準(zhǔn)確的衡量S 盒的安全性是分組密碼研究中的一大難題，目前的研究主要集中在S 盒布爾函數(shù)方面的密碼特性，這些特性包括正交性、嚴(yán)格雪崩準(zhǔn)則（SAC）、差分均勻度、代數(shù)次數(shù)、代數(shù)正規(guī)型與代數(shù)項(xiàng)數(shù)，非線性度和不動(dòng)點(diǎn)個(gè)數(shù)等等。 當(dāng)然，分析S 盒的密碼強(qiáng)度，還得結(jié)合現(xiàn)有的對(duì)分組密碼的攻擊方法進(jìn)行分析。 我們查閱、比較了大量國(guó)內(nèi)外關(guān)于S 盒研究的論文，得出主流的對(duì)S 盒的攻擊方法有線性分析、差分分析、代數(shù)分析等。 這些攻擊方法給我們?cè)u(píng)價(jià)S 盒的安全性提供了一種新思路。 以下給出了國(guó)內(nèi)外論文、研究資料中計(jì)算S 盒布爾函數(shù)常規(guī)指標(biāo)的方法，我們將對(duì)比其中的S 盒線性度計(jì)算和差分均勻度計(jì)算方法，取其精華，將其思想納入到S 盒安全性能測(cè)試軟件的設(shè)計(jì)之中。

3.1.1 S 盒的非線性度

線性分析是一種高效的主要針對(duì)分組密碼或者流密碼的分析技術(shù)。 線性攻擊是一種利用明文、密文和子密鑰之間高概率發(fā)生的線性關(guān)系進(jìn)行攻擊的方式。 這是一種已知明文攻擊，即攻擊者在攻擊前可以知道一定量的明文以及對(duì)應(yīng)的密文，但其無(wú)法按照意愿去選擇明文和相應(yīng)的密文。

對(duì)于線性分析來(lái)說(shuō)，直接影響S 盒抗線性分析能力的指標(biāo)是線性度與非線性度；從密碼學(xué)角度來(lái)看，希望所選用的布爾函數(shù)f（x） 的非線性度越大越好。

定義5［19］：對(duì)任意n×m的S 盒S（x），稱

為S（x） 的非線性度，稱

為S（x） 的線性度。

其中，函數(shù)（a） 函數(shù)的計(jì)算方法如下：

該函數(shù)表示的是Sb的線性度。

Lin（S） 這個(gè)函數(shù)的值越小，表明S 盒抵抗線性分析的能力越強(qiáng)。

關(guān)于計(jì)算S 盒的線性度的方法有非線性度輪廓測(cè)試［20］和Walsh 譜計(jì)算［21］，這兩種方法的比較如表1：

方法 時(shí)間復(fù)雜度實(shí)現(xiàn)難度 優(yōu)點(diǎn) 缺點(diǎn)［20］ 22n＋m＋1 較難 可靠性高 代碼冗長(zhǎng)、空間資源消耗大［21］ 22n＋m＋1 簡(jiǎn)單 輕量化 空間資源消耗最大

方法比較：如表1 所示，對(duì)兩種非線性度測(cè)試算法進(jìn)行比較。 方法［20］的計(jì)算復(fù)雜度為22n＋m＋1次，與方法［21］大致相同；方法［21］的計(jì)算邏輯比方法［20］更簡(jiǎn)單，實(shí)現(xiàn)上更容易，考慮到保證軟件輕量化的目的，不考慮使用方法［20］來(lái)計(jì)算S 盒的線性度。 所以我們選擇方法［21］作為我們的軟件的計(jì)算非線性度算法。

3.1.2 S 盒的差分均勻度

差分分析最早出現(xiàn)于20 世紀(jì)90 年代。 差分分析的主要思路是考察輸入的差分是如何影響對(duì)應(yīng)的輸出差分。 通過(guò)尋找高概率的差分特征來(lái)發(fā)現(xiàn)算法的非隨機(jī)行為，從而進(jìn)一步地恢復(fù)出密鑰。 和線性分析類(lèi)似，差分分析也有衡量標(biāo)準(zhǔn)，差分均勻度。

Diff（S）的值與差分對(duì)出現(xiàn)的最大概率有關(guān)。 一個(gè)S 盒的Diff（S）越小，表示這個(gè)S 盒的抗差分攻擊能力越強(qiáng)。

關(guān)于計(jì)算S 盒的差分均勻度的方法有快速檢測(cè)方法［24］和文獻(xiàn)［25］中的方法，這兩種方法的比較如表2：

方法比較：如表2 所示，對(duì)兩種差分均勻度測(cè)試算法進(jìn)行比較。 兩個(gè)方法時(shí)間復(fù)雜度都是22n，空間復(fù)雜度相同，從實(shí)現(xiàn)難度分析也相差不大；但方法［25］用在輕量級(jí)S 盒上有更好的效率，代碼編寫(xiě)難度更小，所以我們選擇方法［25］。

方法 時(shí)間復(fù)雜度實(shí)現(xiàn)難度 優(yōu)點(diǎn) 缺點(diǎn)［24］ 22n 較難 原理簡(jiǎn)單 代碼冗長(zhǎng)無(wú)創(chuàng)新性［25］ 22n 簡(jiǎn)單 輕量化效率更優(yōu) 大規(guī)模S 盒開(kāi)銷(xiāo)大

3.1.3 S 盒的雪崩特性

雪崩效應(yīng)是指當(dāng)輸入發(fā)生最微小的改變時(shí)，也會(huì)導(dǎo)致輸出的不可區(qū)分性改變（輸出中每個(gè)二進(jìn)制位有50%的概率發(fā)生反轉(zhuǎn)）。 對(duì)于S 盒的設(shè)計(jì)者而言，他們推崇S 盒具有較嚴(yán)格的雪崩特性，并將其作為主要研究方向。 有了良好的雪崩效應(yīng)，分析者或攻擊者就很難從輸入推測(cè)其輸出，大大增加了算法的破解難度。

定義7［26］：函數(shù)f：GF（28） →GF（2）， 若對(duì)任意一位輸入比特取補(bǔ)，其輸出比特有50%的概率取補(bǔ)，則稱該函數(shù)滿足嚴(yán)格雪崩準(zhǔn)則SAC（Strict Avalanche Criterion）。 對(duì)于嚴(yán)格雪崩準(zhǔn)則平均距離的計(jì)算，有如下方法：

設(shè)多輸出布爾函數(shù)

當(dāng)l＝0 時(shí)，F(xiàn)（x） 滿足嚴(yán)格雪崩準(zhǔn)則。 當(dāng)F（x） 不滿足嚴(yán)格雪崩準(zhǔn)則時(shí)，l越小F（x） 越接近嚴(yán)格雪崩準(zhǔn)則。

關(guān)于計(jì)算S 盒雪崩特性的方法有通過(guò)測(cè)試它獨(dú)立矩陣和距離矩陣的辦法［27］和［28］中的方法，這兩種方法的比較如表3：

方法 時(shí)間復(fù)雜度實(shí)現(xiàn)難度 優(yōu)點(diǎn) 缺點(diǎn)［27］ 22n＋m 較難 實(shí)現(xiàn)原理簡(jiǎn)單 代碼表示復(fù)雜［28］ 22n＋m 簡(jiǎn)單 思路清晰、代碼易編寫(xiě) 沒(méi)有效率優(yōu)化

方法比較：如表3 所示，對(duì)兩種雪崩特性測(cè)試算法進(jìn)行比較。 兩種方法的時(shí)間復(fù)雜度相差無(wú)幾，不過(guò)方法［27］的代數(shù)形式復(fù)雜，在代碼中表達(dá)比較困難；方法［28］思路清晰、實(shí)現(xiàn)較簡(jiǎn)單，所以我們選擇方法［28］作為軟件計(jì)算嚴(yán)格雪崩準(zhǔn)則平均距離的方法。

3.1.4 S 盒的代數(shù)正規(guī)型和項(xiàng)數(shù)

布爾函數(shù)是研究密碼算法和密碼技術(shù)的重要工具。 S 盒可以看作一個(gè)布爾函數(shù)，我們?cè)谶@里給出了幾種代數(shù)正規(guī)型的計(jì)算方法。

關(guān)于計(jì)算S 盒的代數(shù)正規(guī)型和項(xiàng)數(shù)的方法有定義法、利用解方程軟件［21］和真值表［21］，這三種方法的比較如表4：

方法 空間復(fù)雜度實(shí)現(xiàn)難度 優(yōu)點(diǎn) 缺點(diǎn)定義法 22n 中等 代碼簡(jiǎn)短 效率低解方程 22n 簡(jiǎn)單 效率高輕量化 準(zhǔn)確性較低真值表22n 簡(jiǎn)單 表達(dá)形式直觀 需要大空間

方法比較：如表4 所示，對(duì)三種代數(shù)項(xiàng)數(shù)測(cè)試算法進(jìn)行比較。 三種方法在計(jì)算復(fù)雜度上是大體相同的，真值表法更直觀但需要開(kāi)辟較多空間，所以不考慮這種方法。 解方程法和定義法相比，實(shí)現(xiàn)起來(lái)更容易，代碼數(shù)量更少，所以我們選擇解方程法作為軟件計(jì)算代數(shù)正規(guī)型的算法。

3.1.5 S 盒的代數(shù)次數(shù)

S 盒的代數(shù)次數(shù)用于衡量S 盒的代數(shù)非線性程度，代數(shù)次數(shù)的大小一定程度上反映了S 盒的線性復(fù)雜度，相關(guān)研究表明，S 盒的線性復(fù)雜度越高，越難用線性表達(dá)式逼近，越能夠抵抗線性分析。

關(guān)于計(jì)算S 盒的代數(shù)次數(shù)方法有定義法、由布爾函數(shù)f（x） 的ANF 向量計(jì)算代數(shù)次數(shù)［20］和［21］中的算法，這三種方法的比較如表5：

方法 空間復(fù)雜度實(shí)現(xiàn)難度 優(yōu)點(diǎn) 缺點(diǎn)定義法 22n 中等 代碼簡(jiǎn)潔 輸入?yún)?shù)多［20］ 22n 簡(jiǎn)單 實(shí)現(xiàn)簡(jiǎn)單代碼簡(jiǎn)潔 測(cè)試范圍?。?1］ 2n＋1 較難 實(shí)現(xiàn)效率高 代碼設(shè)計(jì)難度大

方法比較：如表5 所示，對(duì)三種代數(shù)次數(shù)測(cè)試算法進(jìn)行比較。 定義法的計(jì)算復(fù)雜度是22n和方法［20］相近，方法［21］的計(jì)算復(fù)雜度無(wú)法確定，但其涉及化簡(jiǎn)、合并同類(lèi)項(xiàng)操作，比較適用于手算，軟件實(shí)現(xiàn)較困難。 方法［20］只需輸入ANF 的向量，實(shí)現(xiàn)簡(jiǎn)單，而且ANF 會(huì)用于分析S盒布爾函數(shù)的其他密碼特性，所以我們選擇方法［20］作為軟件的計(jì)算代數(shù)次數(shù)的算法。

4 對(duì)P 置換評(píng)估方法的比較

P 置換是分組密碼中最為重要的線性組件。對(duì)于SP 網(wǎng)絡(luò)型分組密碼和輪函數(shù)采用SP 網(wǎng)絡(luò)的Feistel 網(wǎng)絡(luò)型分組密碼，P 置換的分支數(shù)和活躍S 盒的個(gè)數(shù)有很大關(guān)系，分支數(shù)越大，活躍S盒的數(shù)目也越大。

P 置換的分支數(shù)對(duì)算法整體抗差分及線性攻擊等的強(qiáng)度有重要影響。 一方面，使用分支數(shù)較高的線性層可以在較小的輪數(shù)內(nèi)達(dá)到較高的抗差分和攻擊強(qiáng)度，從而降低算法的整體延遲。另一方面，分支數(shù)較高的線性層其實(shí)現(xiàn)代價(jià)也更大。 因此，設(shè)計(jì)者往往會(huì)進(jìn)行各種參數(shù)的權(quán)衡。例如，近些年來(lái)，在一些輕量級(jí)分組密碼算法的設(shè)計(jì) 中，P 置 換 往 往 不 使 用MDS 矩 陣， 如PRINCE［29］和MIDORI［30］使用的擴(kuò)散函數(shù)分支數(shù)為4（最大值為5），而像PRESENT［31］使用的是分支數(shù)僅為2 的比特拉線，并通過(guò)非線性層和線性層的配合達(dá)到更好的擴(kuò)散效果。

4.1 評(píng)估指標(biāo)

（1）分支數(shù)

令θ：（F2m）n→（F2m）nx→θ（x）＝y(tǒng)是一個(gè)變換，x＝（x1，…，xn） ∈（F2m）n；則θ的分支數(shù)計(jì)算方法如公式（1-1）［6］所示：

（2）P 置換的差分分支數(shù)和線性分支數(shù)

要想求P 置換的差分分支數(shù)和線性分支數(shù)，必須要得到P 置換的差分形式和線性形式［6］，有以下定理。

其中［z］ 表示Z 的向量或矩陣，［z］t表示Z的轉(zhuǎn)置向量或矩陣。

其中，ΔaI，Γai表示輸入差分和輸入掩碼，ΔbI，Γbi表示輸出差分和輸出掩碼。

4.2 評(píng)估方法及實(shí)現(xiàn)

我們下面進(jìn)行計(jì)算差分分支數(shù)的實(shí)現(xiàn)，線性分支數(shù)的方法類(lèi)似（不同的是P 為P 置換的轉(zhuǎn)置矩陣或向量），其中方法2 與方法3 是我們所設(shè)計(jì)的評(píng)估算法。

方法1：

算法的基本思想：如果根據(jù)定義窮盡輸入值的話，數(shù)據(jù)復(fù)雜度太高，比如Camellia 密碼，有264個(gè)可能的輸入，所以為減少計(jì)算量，對(duì)輸入按漢明重量從小到大計(jì)算。

分支數(shù)測(cè)試：

輸入：

m：P 置換輸入差分ΔX的向量形式（ΔX1，…，ΔXm） 的維數(shù)。

n：P 置換輸入差分ΔX的向量形式（ΔX1，…，ΔXm） 中ΔXi（1 ≤i≤m） 的比特?cái)?shù)。

P：P 置換。

輸出：

Pd：差分分支數(shù)。

測(cè)試過(guò)程：

設(shè)輸入為ΔX＝（ΔX1，…，ΔXm） ∈（Fn2）m，將輸入值按漢明重量（即非零ΔXi（1 ≤i≤m）的個(gè)數(shù)）從小到大依次計(jì)算其輸出值的漢明重量，并求出輸入值和輸出值的漢明重量之和，如果對(duì)漢明重量小于i 的輸入計(jì)算得到其所有輸入值和輸出值的漢明重量之和的最小值為n，而這時(shí)i ＞n- 1，則停止搜索，差分分支數(shù)即為n。

方法2：

設(shè)L 是一個(gè)［n，k］ -線性碼，校驗(yàn)矩陣為H，那么L 的極小距離為d 當(dāng)且僅當(dāng)H 中存在d列線性相關(guān)，但任意d- 1 列都線性無(wú)關(guān)。 所以在設(shè)計(jì)算法時(shí)，構(gòu)造校驗(yàn)矩陣［MI］， 設(shè)待測(cè)的分支數(shù)為br，則檢驗(yàn)是否任意br- 1 列都線性無(wú)關(guān)，若是，則檢驗(yàn)是否存在br 列線性相關(guān)。 在檢驗(yàn)時(shí)，使用高斯消去法變換矩陣，通過(guò)計(jì)算秩判斷是否線性相關(guān)。

分支數(shù)測(cè)試

輸入：

m：P 置換輸入差分ΔX的向量形式（ΔX1，…，ΔXm） 的維數(shù)。

n：P 置換輸入差分ΔX的向量形式（ΔX1，…，ΔXm） 的矩陣。

輸出：

Pd：差分分支數(shù)。

測(cè)試過(guò)程：

如算法一所示，該程序是修改后的測(cè)試多元域上的dim 維矩陣分支數(shù)的程序，使用的是有關(guān)分支數(shù)和線性碼方面的知識(shí)，并且使用高斯消去法計(jì)算矩陣的線性相關(guān)性。

算法一.二元域矩陣分支數(shù)的確定1：function BBN（M，dimension）2： InuM←inverse matrix of M 3： miniweight←2·dimension 4： while wb（x） ＜miniweight／2 do 5： weight←wb（x） ＋wb（M·x）6： if weight≤miniweight then 7： miniweight←weight 8： end if 9： weight←wb（x） ＋wb（InvM·x）10： if weight≤miniweight then 11： updata x in the increasing order by Hamming weight 12： return miniweight 13： end function

方法3：利用公式B（θ）＝minx≠0（ωb（x）＋ωb（θ（x）））， 這里，ωb（x） 就是非零元素的個(gè)數(shù)，即X 的漢明重量。θ（x） 就是P 置換的輸出差分。 通過(guò)測(cè)試X 的漢明重量和線性變換的系數(shù)矩陣來(lái)確定分支數(shù)的大小。

分支數(shù)測(cè)試

輸入：

m：P 置換輸入差分ΔX的向量形式（ΔX1，…，ΔXm） 的維數(shù)。

n：P 置換輸入差分ΔX的向量形式（ΔX1，…，ΔXm） 的矩陣。

輸出：

Pd：差分分支數(shù)。

測(cè)試過(guò)程：

設(shè)計(jì)算法主要是逆推法。 首先定義最小距離為2n，通過(guò)驗(yàn)證m個(gè)列向量是否線性相關(guān)，在此基礎(chǔ)上不斷把最小距離進(jìn)行縮小。 而判斷是否線性相關(guān)，因?yàn)槭窃诙蛩酝ㄟ^(guò)異或運(yùn)算結(jié)果是否為0 進(jìn)行判斷。 若是，則將定義的最小距離2n替換為m，最大分支數(shù)就是m。

如算法二所示，以ARIA 型擴(kuò)散結(jié)構(gòu)為例計(jì)算分支數(shù)。

算法二.伽羅瓦域矩陣分支數(shù)的確定1： function BBN（n，BinaryMatrix［MAX］ ［MAX］，Branch-Num）2： while a ＜sum（n） do 3： c←a 4： while I ←n - 1 ≥0 do 5： if c←0 then 6： B←c%2 c←c／ ＝2 7： compute the weight of the generatrion part 8： if weight＜minweight then 9： miniweight ←weight 10： end while 11： return miniweight 12： end function

4.3 評(píng)估方法的對(duì)比分析

差分分支數(shù)的實(shí)現(xiàn)有以下三種，方法1［33］、方法2 和方法3，線性分支數(shù)也是類(lèi)似，這三種方法的對(duì)比如下表：

方法比較：如表6 所示，對(duì)三種P 置換分支數(shù)測(cè)試算法進(jìn)行比較。 方法1 是對(duì)輸入按漢明重量從小到大計(jì)算，通過(guò)篩選找到分支數(shù)，并且需要測(cè)試三個(gè)量（漢明重量、向量的維數(shù)和比特?cái)?shù)）。 方法2 是驗(yàn)證列向量是否線性相關(guān)，在此基礎(chǔ)上不斷把最小距離進(jìn)行縮小，并且需要測(cè)試兩個(gè)量（二元域上矩陣維數(shù)、矩陣的元素）。 方法3 使用的是有關(guān)分支數(shù)和線性碼方面的知識(shí)，利用高斯消去法計(jì)算矩陣的線性相關(guān)性，并且需要兩個(gè)量（多元域上矩陣維數(shù)、矩陣的元素）。因此，方法二和方法三在測(cè)試范圍、進(jìn)程內(nèi)存、CPU 占比等方面都表現(xiàn)優(yōu)異，我們采用算法二和算法三相結(jié)合的方式來(lái)進(jìn)行P 置換分支數(shù)的測(cè)試。

測(cè)試算法 原理 測(cè)試需求 內(nèi)存消耗CPU 運(yùn)行時(shí)間方法1 正推法 漢明重量、維數(shù)和比特?cái)?shù) 16MB 367.587ms方法2 逆推法 矩陣的維數(shù)矩陣的元素 14MB 350.423ms方法3 線性碼 矩陣的維數(shù)矩陣的元素 15MB 350.423ms

5 對(duì)S 盒的評(píng)估和比較

基于前面S 盒安全指標(biāo)的評(píng)估方法，本節(jié)選擇其中有效的方法對(duì)當(dāng)下重要的分組密碼算法中S 盒進(jìn)行評(píng)估，并在此基礎(chǔ)上篩選出現(xiàn)行標(biāo)準(zhǔn)下適于軟硬件實(shí)現(xiàn)的安全輕量最優(yōu)S 盒設(shè)計(jì)方案。

首先我們描述我們采用的評(píng)估算法，然后我們針對(duì)當(dāng)下重要的分組密碼算法中S 盒進(jìn)行評(píng)估。

5.1 采用的S 盒評(píng)估方法

S 盒的代數(shù)性質(zhì)和代數(shù)結(jié)構(gòu)很大程度上決定了整個(gè)密碼算法的安全強(qiáng)度。 關(guān)于S 盒的代數(shù)性質(zhì)研究較多，目前最常見(jiàn)的S 盒度量指標(biāo)列舉如下：非線性度、差分均勻性、平衡性、擴(kuò)散性和可逆性、代數(shù)次數(shù)及項(xiàng)數(shù)分布、正交性、相關(guān)免疫性。 對(duì)于代數(shù)性質(zhì)較好的S 盒，為了抵抗線性分析，一般都會(huì)具有較高的非線性度；為了抵抗差分分析，需要較大的差分均勻性；為了抵抗代數(shù)攻擊和立方攻擊，需要較高的代數(shù)次數(shù)，并且不同的代數(shù)次數(shù)的項(xiàng)數(shù)分布較均勻。

我們對(duì)現(xiàn)有主流分組密碼中的S 盒就非線性度、雪崩效應(yīng)以及擴(kuò)散特性等性質(zhì)做了分析與研究。 綜合比對(duì)多個(gè)S 盒設(shè)計(jì)方案，詳細(xì)研究這些S 盒的差分均勻度、非線性度、不動(dòng)點(diǎn)個(gè)數(shù)、代數(shù)次數(shù)、代數(shù)項(xiàng)數(shù)、代數(shù)免疫度、雪崩效應(yīng)以及擴(kuò)散特性等性質(zhì)，并與現(xiàn)有的主流分組密碼匯總的S 盒各項(xiàng)性能指標(biāo)進(jìn)行對(duì)比。

5.2 S 盒評(píng)估的結(jié)果

我們搜集了多種密碼算法的S 盒代數(shù)表達(dá)式、代數(shù)性質(zhì)的比較分析，將AES 算法、SEED 算法、Camellia 算法、SMS4 算法、Blowfish 算法、Serpent 算法和Twofish 算法S 盒的代數(shù)性質(zhì)各項(xiàng)數(shù)據(jù)指標(biāo)的計(jì)算結(jié)果列于下表7 所示。

算法 AES SEED Camellia SMS4 S 盒 S S1 S2 S1 S2 S3 S4 S次數(shù) 254 254 254 254 254 254 254 254項(xiàng)數(shù) 9 255 255 254 253 254 255 255差分矩陣 4 4 4 4 4 4 4 4線性矩陣 16 16 16 16 16 16 16 16差分均勻 4 5 5 3 3 3 3 4非線性度 112 112 112 112 112 112 112 112雪崩準(zhǔn)則 滿足 滿足 滿足 滿足 滿足 滿足 滿足 滿足算法 Blowfish Serpent S 盒 S1 S2 S3 S4 S1 S2 S3 S4次數(shù) 254 254 254 254 32 32 32 32項(xiàng)數(shù) 256 256 256 256 4 4 4 4差分矩陣 4 4 4 4 4 4 4 4線性矩陣 4 4 4 4 16 16 16 16差分均勻 8 8 8 8 4 4 4 4非線性度 106 106 106 106 112 112 112 112雪崩準(zhǔn)則 滿足 滿足 滿足 滿足 滿足 滿足 滿足 滿足算法 Serpent Twofish S 盒 S5 S6 S7 S8 S1 S2 S3 S4次數(shù) 32 32 32 32 254 254 254 254項(xiàng)數(shù) 4 4 4 4 256 256 256 256差分矩陣 4 4 4 4 4 4 4 4線性矩陣 16 16 16 16 4 4 4 4差分均勻 4 4 4 4 8 8 8 8非線性度 112 112 112 112 116 116 116 116雪崩準(zhǔn)則 滿足 滿足 滿足 滿足 滿足 滿足 滿足 滿足

7 種算法S 盒的差分矩陣的最大值均為4，且最大值在每一行每一列（首行首列除外）中出現(xiàn)且僅出現(xiàn)1 次。 因此，可以初步認(rèn)為AES 算法、 SEED 算 法、 Camellia 算 法、 SMS4 算 法、Blowfish 算法、Serpent 算法和Twofish 算法S 盒的差分特性是相當(dāng)?shù)摹?此外，其中5 種算法S 盒的線性矩陣中最大絕對(duì)值均為16，且最大值在每一行每一列（首行首列除外）中出現(xiàn)且僅出現(xiàn)5 次。 剩余2 種算法S 盒的線性矩陣中最大絕對(duì)值均為4，且最大值在每一行每一列（首行首列除外）中出現(xiàn)且僅出現(xiàn)1 次。 通過(guò)上述分析比較，7 種算法在抵抗差分分析的能力是相當(dāng)?shù)?，但抵抗線性分析的能力上AES 算法、SEED算法、Camellia 算法、SMS4 算法和Serpent 算法要優(yōu)于Blowfish 算法和Twofish 算法。

5.3 對(duì)S 盒設(shè)計(jì)方法的比較

在資源受限的環(huán)境中，4-bit S 盒則更受青睞。 因此，本文的目標(biāo)是從已有的S 盒設(shè)計(jì)方案中篩選出能抵抗傳統(tǒng)密碼分析最優(yōu)的4-bit S盒。 對(duì)于4×4 的S 盒，如果它是滿足置換性質(zhì)，并且它的非線性度和差分均勻度都等于4，則這個(gè)S 盒是密碼學(xué)性質(zhì)最優(yōu)的S 盒。 本節(jié)借助前文第3 節(jié)的評(píng)估方法，最終得出文獻(xiàn)［34］輕量級(jí)S 盒的設(shè)計(jì)方案安全性和效率是相對(duì)最優(yōu)。

代數(shù)次數(shù)差分均勻度非線性度是否最優(yōu)最低深度S 盒個(gè)數(shù) 來(lái)源3 4 4 是 2 32 文獻(xiàn)［34］3 6 4 否 3 24 文獻(xiàn)［35］3 4 6否38Serpent 3 4 8否316PRESENT

如表8 的對(duì)比結(jié)果可知，同樣在文獻(xiàn)［35］中作為輕量級(jí)算法的S 盒，雖然在非線性度與文獻(xiàn)［34］的S 盒持平，但差分均勻度度卻沒(méi)有達(dá)到密碼學(xué)性質(zhì)最優(yōu)。 除此之外，文獻(xiàn)［34］的設(shè)計(jì)方案還可以快速地生成更多的最優(yōu)S 盒，并且設(shè)計(jì)的S 盒組合邏輯電路最低深度為2，在實(shí)現(xiàn)效率方面是優(yōu)于文獻(xiàn)［35］的S 盒。 除此之外，對(duì)比Serpent 算法、PRESENT 算法這些經(jīng)典算法，他們的迭代循環(huán)周期沒(méi)有達(dá)到最大，甚至還存在不動(dòng)點(diǎn)，差分均勻度、擴(kuò)散特性也還可以做得更好，因此我們選取的設(shè)計(jì)方案在輕量級(jí)密碼學(xué)性質(zhì)以及S 盒數(shù)量等方面都有明顯的優(yōu)勢(shì)。當(dāng)然，文獻(xiàn)［34］S 盒的設(shè)計(jì)方案將在下面進(jìn)行簡(jiǎn)要介紹。

本節(jié)所選取的文獻(xiàn)［34］設(shè)計(jì)方案是通過(guò)三次布爾函數(shù)中的變量進(jìn)行循環(huán)移位來(lái)構(gòu)造S 盒。 給定一個(gè)布爾函數(shù)f，其對(duì)應(yīng)的4×4 的S 盒如下所示。

另外就S 盒的設(shè)計(jì)我們給出一個(gè)定義和一個(gè)定理。

設(shè)f是一個(gè)三次的布爾函數(shù)，限定函數(shù)所含三次項(xiàng)、二次項(xiàng)的個(gè)數(shù)。 觀察f的函數(shù)表達(dá)式可知，表達(dá)式中有1 個(gè)三次項(xiàng)，6 個(gè)二次項(xiàng)和4 個(gè)一次項(xiàng)，有10（a1～a10）個(gè)系數(shù)，4 個(gè)變量（x，y，z，w）。 從1024 個(gè)f中搜索平衡的三次布爾函數(shù)，通過(guò)編程實(shí)現(xiàn)，能找到400 個(gè)平衡的f。 所謂平衡是指在16 個(gè)變量（0000，0001…，1110，1111）中有8 個(gè)變量的函數(shù)值為1，8 個(gè)變量的函數(shù)值為0。 從搜索出來(lái)的平衡的三次布爾函數(shù)中任取一個(gè)，對(duì)其變量進(jìn)行左移1 位、左移2 位、左移3 位，得到函數(shù)f1、f2、f3。

將f、f1、f2、f3進(jìn)行組合即（f、f1、f2、f3），然后對(duì)x、y、z、w進(jìn)行0000 到1111 遍歷，計(jì)算出此時(shí)的f、f1、f2、f3的值，找到置換即（x、y、z、w） →（f、f1、f2、f3）。 此時(shí)的置換剛好滿足定義1 和定理1，就是所構(gòu)建的S 盒。 該方法能夠找到這樣置換的個(gè)數(shù)是64。

將該設(shè)計(jì)方案所構(gòu)造的64 個(gè)S 盒的差分分布表分別計(jì)算出來(lái)，并統(tǒng)計(jì)它們的差分均勻度，統(tǒng)計(jì)結(jié)果如表9 所示，可知該方法所構(gòu)造的64個(gè)S 盒中差分均勻度為4 的有32 個(gè)，剩下的S盒均是差分均勻度為6。 由此看來(lái)，利用該方法構(gòu)造的S 盒有一半達(dá)到了密碼性質(zhì)最優(yōu)時(shí)的差分均勻度的要求。

代數(shù)次數(shù) 差分均勻度 非線性度 線性度 S 盒 是否最優(yōu) 是否平衡 個(gè)數(shù)3 4 4 8 S3、S4、S7、S8、S11、S12、S15、S16、S19、S20、S23、S24、S27、S28、S31、S32、S35、S36、S39、S40、S43、S44、S47、S48、S51、S52、S55、S56、S59、S60、S63、S64是是 32 212 無(wú) 否 否0 3 6 3 4 4 8 S1、S2、S9、S10、S13、S14、S29、S30、S41、S42、S53、S54、S57、S58、S61、S62否否 16 3 6 2 12 S5、S6、S17、S18、S21、S22、S25、S26、S33、S34、S37、S38、S45、S46、S49、S50否否16

在上述構(gòu)造的64 個(gè)S 盒中，有32 個(gè)S 盒的非線性度和差分均勻度都等于4，這些S 盒的密碼性質(zhì)最優(yōu)。 因此，利用文獻(xiàn)［34］設(shè)計(jì)方案構(gòu)造的64 個(gè)S 盒中有一半的S 盒密碼性質(zhì)最優(yōu)，這些S 盒是安全可用的。 另外該方案是利用代數(shù)次數(shù)為3 的布爾函數(shù)來(lái)構(gòu)造S 盒，所以同時(shí)兼顧了S 盒高代數(shù)次數(shù)的要求。

6 對(duì)P 置換的評(píng)估和比較

列線性相關(guān)，但任意d - 1 列都線性無(wú)關(guān)。 所以在設(shè)計(jì)算法時(shí)，構(gòu)造校驗(yàn)矩陣［MI］， 設(shè)待測(cè)的分支數(shù)為br，則檢驗(yàn)是否任意br -1 列都線性無(wú)關(guān)，若是，則檢驗(yàn)是否存在br 列線性相關(guān)。 在檢驗(yàn)時(shí)，使用高斯消去法變換矩陣，先將矩陣A 與單位矩陣I 進(jìn)行連接形成一個(gè)新的增廣矩陣，再通過(guò)計(jì)算秩判斷是否線性相關(guān)。

基于前面P 置換的評(píng)估，本節(jié)選擇其中有效的方法對(duì)當(dāng)下重要分組密碼算法中的P 置換進(jìn)行評(píng)估，并在此基礎(chǔ)上篩選出輕量級(jí)P 置換的設(shè)計(jì)方案。

首先我們描述采用算法二和算法三相結(jié)合的方式，然后我們針對(duì)當(dāng)下重要的分組密碼算法中P 置換進(jìn)行評(píng)估。

6.1 采用的P 置換評(píng)估方法

本文使用有關(guān)分支數(shù)和線性碼方面的知識(shí)來(lái)測(cè)試多元域上的矩陣分支數(shù)，并且使用高斯消去法計(jì)算矩陣的線性相關(guān)性，也就是前文4.2 節(jié)所提到的P 置換分支數(shù)測(cè)試算法2。

主要使用的算法原理為：

設(shè)L 是一個(gè)［n，k］ -線性碼，校驗(yàn)矩陣為H，那么L 的極小距離為d 當(dāng)且僅當(dāng)H 中存在d

6.2 P 置換評(píng)估的結(jié)果

我們通過(guò)搜索二元域上所有的4×4 可逆矩陣，利用分支數(shù)的概念從20000 個(gè)候選矩陣中進(jìn)行篩選，搜索出二元有限域上的MDS 矩陣的數(shù)量為零，找到了24 個(gè)almost-MDS 矩陣，見(jiàn)下表10 所示。

并且通過(guò)對(duì)almost-MDS 矩陣進(jìn)行了研究分析，發(fā)現(xiàn)almost-MDS 矩陣不僅實(shí)現(xiàn)代價(jià)小，而且能夠提供可證的安全性，見(jiàn)如下表11 所示：

almost-MDS 矩陣能夠在安全性和效率之間進(jìn)行最佳權(quán)衡。 almost-MDS 矩陣雖然具有次優(yōu)分支數(shù)，但是它們比MDS 矩陣需要更少的區(qū)域，更短的運(yùn)行時(shí)間，與MDS 矩陣相比，它們?cè)谲浻布?shí)現(xiàn)方面效率更高，在almost-MDS 矩陣的實(shí)現(xiàn)過(guò)程中，它們只需要一個(gè)簡(jiǎn)單的異或操作，就可以大大減少軟件和硬件資源的消耗。 許多分組密碼算法將almost-MDS 矩陣作為P 置換使用， 如 ARIA［38］、 Camellia［39］、 FIDES［40］、Midori［41］、PRIDE［42］、PRINCE［43］等等，表11 列舉了采用almost-MDS 矩陣構(gòu)造P 置換的一些密碼算法。

非對(duì)稱矩陣 對(duì)稱矩陣■ ■■■11 01 11 10 10 01 11 11 1 1 0 1 0 1 1 1■ ■■■■ ■■■1 1 1 1 0 1 1 0■ ■■■■ ■■■11 01 10 11 10 01 11 11 0 1 1 1 1 1 1 0■ ■■■■ ■■■1 1 1 1 1 0 0 1■ ■■■■ ■■■11 01 11 10 11 11 01 10 0 1 1 1 1 1 0 1■ ■■■■ ■■■0 1 1 0 1 1 1 1■ ■■■■ ■■■11 01 10 11 11 10 01 11 1 1 0 1 1 0 1 1■ ■■■■ ■■■0 1 1 1 1 1 1 0■ ■■■■ ■■■10 11 01 11 11 10 11 01 1 0 1 1 1 1 1 0■ ■■■■ ■■■1 1 0 1 0 1 1 1■ ■■■■ ■■■10 11 01 11 11 11 10 01 1 1 1 0 1 0 1 1■ ■■■■ ■■■1 0 0 1 1 1 1 1■ ■■■■ ■■■11 10 01 11 01 11 10 11 1 1 0 1 1 0 1 1■ ■■■■ ■■■1 0 1 1 1 1 1 0■ ■■■■ ■■■11 11 01 10 01 10 11 11 1 0 0 1 1 1 1 1■ ■■■■ ■■■1 1 1 1 1 0 0 1■ ■■■■ ■■■10 11 11 01 01 11 11 10 1 1 1 0 0 1 1 1■ ■■■■ ■■■1 1 1 0 0 1 1 1■ ■■■■ ■■■10 11 11 01 01 10 11 11 1 0 1 1 1 1 0 1■ ■■■■ ■■■1 1 1 1 0 1 1 0■ ■■■■ ■■■11 10 11 01 0 1 1 1 1 1 0 1■ ■■■■ ■■■11 11 10 01 0 1 1 0 1 1 1 1■ ■■■■ ■■■01 11 11 10 1 0 1 1 1 1 0 1■ ■■■■ ■■■01 11 10 11 1 1 1 0 1 0 1 1■ ■■■

6.3 對(duì)P 置換設(shè)計(jì)方法的比較

近些年隨著物聯(lián)網(wǎng)等普適計(jì)算的發(fā)展，計(jì)算能力有限的微型設(shè)備被廣泛應(yīng)用，這對(duì)硬件提出了新的要求。 許多傳統(tǒng)密碼算法效率較低，因此如何構(gòu)造一個(gè)適用于輕量級(jí)密碼算法的P 置換受到了廣泛關(guān)注。 因此本節(jié)在前文第四節(jié)的基礎(chǔ)上，給出我們篩選的輕量級(jí)P 置換設(shè)計(jì)方案［44］。

密碼算法 矩陣維數(shù) 對(duì)合性 分支數(shù)MIBS 8否5 Midori 4是4 FIDES 4是4方案［44］的P 置換 8 是 7

上述密碼算法的P 置換都是作用在F42上，由表12 可以看出，本節(jié)選取的設(shè)計(jì)方案所構(gòu)造的P 置換分支數(shù)要高于MIBS 算法、Midori 算法、FIDES 算法的P 置換，因?yàn)榭紤]到分支數(shù)較高的P 置換可以在較小的輪數(shù)內(nèi)達(dá)到較高的抗差分和攻擊強(qiáng)度，從而降低算法的整體延遲。 因此方案［44］設(shè)計(jì)構(gòu)造的P 置換擴(kuò)散效果相對(duì)較優(yōu)。 除此之外，該方案所構(gòu)造的對(duì)合矩陣可以提供更高級(jí)別的擴(kuò)散，增強(qiáng)密碼的安全性，同時(shí)處理方式也非常高效，因此它可以在保證安全性的前提下，提高加密效率。 綜上，可以得出方案［44］的P 置換在擴(kuò)散效果和實(shí)現(xiàn)效率上都有著明顯的優(yōu)勢(shì)。 下面對(duì)文獻(xiàn)［44］S 盒的設(shè)計(jì)方案進(jìn)行簡(jiǎn)要介紹。

該方案設(shè)計(jì)的P 置換主要是基于密碼結(jié)構(gòu)構(gòu)造P 置換，基于Feistel 結(jié)構(gòu)構(gòu)造的P 置換逆變換和其本身具有相同的結(jié)構(gòu)，只需簡(jiǎn)單地按順序反向使用輪函數(shù)即可實(shí)現(xiàn)逆變換。 這種結(jié)構(gòu)使P 置換和它的逆變換擁有相同的異或數(shù)，特別地，對(duì)合的P 置換可以使用相同的代碼和電路實(shí)現(xiàn)加密和解密，大大節(jié)省了軟硬件資源，當(dāng)輪函數(shù)是對(duì)稱的時(shí)候，矩陣M 為對(duì)合矩陣，如［P1，P2，P1］ 和 ［P1，P2，P2，P1］。 并 且 由 于Feistel 結(jié)構(gòu)簡(jiǎn)單，它實(shí)際上是利用小矩陣構(gòu)造大矩陣，如果采用簡(jiǎn)單的輪函數(shù)，將會(huì)構(gòu)造出十分容易實(shí)現(xiàn)的P 置換。 為了構(gòu)造出既安全又高效的P 置換，限定采用三輪Feistel 結(jié)構(gòu)，并且只搜索對(duì)合P 置換。 圖1 給出了三輪Feistel 結(jié)構(gòu)構(gòu)造的P 置換，矩陣M ＝［P1，P2，P3］， 逆矩陣為M-1＝［P3，P2，P1］，

圖1 三輪Feistel 結(jié)構(gòu)構(gòu)造的P 置換

對(duì)合P 置換要求輪函數(shù)P1和P3相同。 下面給出作用在（Fm2）2n上的基于三輪Feistel 結(jié)構(gòu)構(gòu)造的輕量級(jí)對(duì)合P 置換。

因此在（F42）8上構(gòu)造對(duì)合P 置換，當(dāng)n＝4，m＝4 時(shí)，窮搜了3 項(xiàng)及以下循環(huán)移位和異或運(yùn)算的線性變換作為輪函數(shù)的三輪Feistel 的所有可逆P 置換，沒(méi)有找到MDS 矩陣，得到最好的作用在（F42）8上的對(duì)合P 置換分支數(shù)為7，共找到1248 個(gè)這樣的對(duì)合P 置換，并且每一個(gè)輪函數(shù)均為3 項(xiàng)（k＝3）。 表13 給出了部分分支數(shù)為7 的對(duì)合P 置換L（X）。

S1 S2｛0，4，9｝ ｛0，3，7｝｛0，4，9｝ ｛0，10，15｝｛1，5，9｝ ｛0，7，11｝｛1，5，9｝ ｛1，2，14｝｛2，6，13｝ ｛1，8，11｝｛2，6，13｝ ｛2，9，15｝｛5，9，13｝ ｛0，1，4｝｛5，9，13｝ ｛0，2，14｝｛6，10，14｝ ｛0，1，5｝｛6，10，14｝ ｛0，3，7｝

綜上所述，F(xiàn)eistel 結(jié)構(gòu)因其軟硬件實(shí)現(xiàn)效率高，加解密一致，加解密速度快等優(yōu)點(diǎn)受到廣大研究者的青睞。 本方案主要是基于三輪Feistel結(jié)構(gòu)構(gòu)造輕量級(jí)P 置換，輪函數(shù)采用基于循環(huán)移位和異或的線性變換，構(gòu)造出了一系列作用在（F42）8上分支數(shù)為7 的對(duì)合P 置換，一方面，對(duì)合性質(zhì)使P 置換的加密和解密操作在硬件上可以使用相同的電路，在軟件上可以使用相同的代碼，并且輪函數(shù)采用基于循環(huán)移位和異或運(yùn)算的線性變換。 不管是移位運(yùn)算還是循環(huán)移位運(yùn)算，通過(guò)軟件實(shí)現(xiàn)所需的CPU 周期數(shù)均很低，大大提高了軟件實(shí)現(xiàn)效率；另一方面，對(duì)于作用在8個(gè)4-bit S 盒上的P 置換，分支數(shù)為7 的P 置換已經(jīng)可以提供較好的擴(kuò)散效果，并且分支數(shù)為7的P 置換是安全性和效率方面的權(quán)衡。

7 結(jié)束語(yǔ)

本文針對(duì)分組密碼中S 盒和P 置換兩個(gè)關(guān)鍵組件的評(píng)估與比較展開(kāi)研究，將已有的評(píng)估算法在S 盒的代數(shù)次數(shù)、差分均勻度、非線性度、雪崩特性等方面以及P 置換矩陣分支數(shù)進(jìn)行總結(jié)比較。 特別地，本文針對(duì)P 置換提出新的評(píng)估算法。 在此基礎(chǔ)上，我們采用其中有效的評(píng)估方法對(duì)多種S 盒和P 置換方案進(jìn)行評(píng)估，進(jìn)而篩選出密碼性質(zhì)最優(yōu)的S 盒與P 置換設(shè)計(jì)方案。

S 盒設(shè)計(jì)方案利用對(duì)三次布爾函數(shù)中的變量進(jìn)行循環(huán)移位來(lái)構(gòu)造4×4 的S 盒，設(shè)計(jì)了輕量級(jí)分組密碼的混淆層。 然后通過(guò)求解所構(gòu)造的S 盒的差分均勻度與非線性度，來(lái)衡量它們抵抗差分分析和線性分析的能力。 通過(guò)求解可知，32 個(gè)S 盒的非線性度與差分均勻度都為4，因此它們是密碼性質(zhì)最優(yōu)的S 盒，這些S 盒是安全有效的。

P 置換設(shè)計(jì)方案是基于三輪Feistel 結(jié)構(gòu)構(gòu)造輕量級(jí)P 置換，輪函數(shù)采用基于循環(huán)移位和異或的線性變換，構(gòu)造出了一系列作用在（F42）8上分支數(shù)為7 的對(duì)合P 置換。 在本文綜述的4比特最優(yōu)S 盒以及輕量級(jí)P 置換都能夠達(dá)到一些算法的安全需求，因此二者構(gòu)造方法都具有可行性和適用性。