基于密碼結構的擴散層構造

李鵬飛

（1. 中國科學院信息工程研究所信息安全國家重點實驗室，北京 100093；2. 中國科學院大學網絡空間安全學院，北京 100049）

基于密碼結構的擴散層構造

李鵬飛1,2

（1. 中國科學院信息工程研究所信息安全國家重點實驗室，北京 100093；2. 中國科學院大學網絡空間安全學院，北京 100049）

以分組密碼擴散層為研究對象，根據輕量級分組密碼的特點，基于2種密碼結構構造輕量級擴散層，分別是基于Feistel結構構造面向軟件實現的擴散層和基于LFSR構造面向硬件實現的擴散層。利用三輪Feistel結構，輪函數采用基于循環移位和異或的線性變換，構造出作用在8個4 bit和8 bit S盒上分支數為7的輕量級對合擴散層。基于LFSR構造出作用在4個4 bit和8 bit S盒上的次最優擴散層和作用在8個4 bit和8 bit S盒上分支數為7的擴散層。另外，利用LFSR構造出了6、7、8維MDBL矩陣以及16、18、32維分支數分別為7、7、12的大維數二進制矩陣。研究結果在分組密碼的設計方面具有較高的應用價值。

分組密碼；擴散層；Feistel結構；反饋移位寄存器；MDBL矩陣

1 引言

隨著物聯網（IoT，Internet of things）技術的快速發展，射頻識別（RFID，radio frequency identification）標簽、無線傳感器網絡（WSN，wireless sensor network）、個人數字助理（PDA，personal digital assistant）終端等微型嵌入式設備越來越發達，它們廣泛應用于人們生活的方方面面，將任何物品與互聯網連接起來，實現物與物、物與人、物與網絡的信息交互，達到萬物的智能化識別、定位、跟蹤、監控和管理。然而，由于這些微型嵌入式設備只有有限的計算能力、通信能力、存儲空間和能量來源，消耗更多軟硬件資源、運行速度較差的傳統密碼算法（如DES[1]、AES[2]、SM4[3]等）已很難適用，給安全帶來了極大的挑戰，為了保障用戶的數據和隱私安全，輕量級密碼學應運而生，輕量級是相對于普通密碼提供的安全保護級別和實現所需資源而言的，旨在安全性、面積功耗、時延速度等多個方面實現較好的折中。近幾年，隨著物聯網的安全問題逐漸成為重要的研究課題，研究者相繼提出了許多輕量級密碼算法，包括輕量級分組密碼、Hash函數、認證加密算法（如HIGHT[4]、PRESENT[5]、CLEFIA[6]、LED[7]、LBlock[8]、PRINCE[9]、SIMON和SPECK[10]、Zorro[11]、SIMECK[12]、PHOTON[13]、PRIMATEs[14]）等，這些算法的典型特點是：在嚴格規定的硬件資源條件下，能夠達到一定的安全級別。

分組密碼因其加解密速度快，便于軟硬件實現和易于標準化等特點，成為輕量級密碼學研究的重點，受到了學者的廣泛關注。擴散層作為分組密碼的一個重要部件，它的設計不但影響分組密碼算法的安全性，而且影響分組密碼在軟硬件中的實現效率。一方面，擴散層為分組密碼提供主要的擴散性，在抵抗差分分析和線性分析中扮演著重要的角色；另一方面，實現相同的安全性指標時，精心選擇的擴散層可以顯著提升分組密碼算法在軟硬件中的實現效率。目前，擴散層不僅是分組密碼算法的必備部件，也在其他對稱密碼體制（如Hash函數、認證加密算法）中有廣泛應用。擴散層的安全性能主要由文獻[2]中提出的分支數的概念衡量，它是度量連續兩輪差分和線性特征中活躍S盒數目下界的一個重要指標，利用它可以有效地計算差分特征概率和線性逼近概率的上界，估計密碼算法的安全性。擴散層的分支數越小，分組密碼越容易遭受差分分析、線性分析以及一些未知分析方法的攻擊；反之，分支數越大，擴散層的擴散效果越好、安全性越好，因此，分組密碼設計者面臨的一大挑戰是如何設計分支數大、軟硬件實現代價低的擴散層，特別是在資源極端受限的物聯網環境下。近幾年，分組密碼設計與改進的重點以及有所創新的地方主要集中在擴散層，有很多研究成果。

MDS（maximum distance separable）矩陣可以保證分支數達到最大，擴散性能達到最優，從而可以最大限度地保證密碼算法在差分和線性分析下的安全性。許多密碼算法都將 MDS矩陣作為擴散層使用，分組密碼如 SHARK[15]、Rijndeal[2]、Twofish[16,17]、Square[18]、Anubis[19]、Khazad[20]、FOX[21]、CLEFIA、LED等，流密碼如MUGI[22]，Hash函數如Maelstrom[23]，Gr?stl[24]，WHIRLPOOL[25]和PHOTON輕量級Hash函數族[13]等。盡管這么多算法的擴散層都采用 MDS矩陣，但不可否認，MDS矩陣在提供最優擴散性的同時，也使算法的效率有所降低，它們通常需要較長的執行時間，消耗更多的軟硬件資源，例如，硬件實現AES所需的最少電路門數為2 400等效門數[26]（GE，gate equivalents），其中僅列混淆部分就需要263 GE。關于MDS矩陣的研究也有很多[27～39]，這些MDS矩陣主要面向硬件實現，所需的異或個數極少，但沒有過多地考慮軟件實現效率。

分組密碼算法設計中還經常采用 MDBL（maximum distance binary linear）矩陣作為擴散層使用，如ARIA[40]、Camellia[41]、E2[42]、MIBS[43]、Midori[44]、FIDES[45]、Minalpher[46]等密碼算法中的擴散層都是使用MDBL矩陣，MDBL矩陣是二進制矩陣中具有最大分支數的矩陣[47]，它們相對MDS矩陣而言具有較高的軟硬件實現效率，實現過程只需要異或操作，大大降低了軟硬件資源消耗。表1給出了一些采用MDBL矩陣作為擴散層使用的密碼算法。

相對于MDS矩陣，關于MDBL矩陣的研究比較少[48,49]，Kang等[50]證明了可逆8 × 8二進制矩陣的分支數小于等于5，即具有分支數5的8× 8二進制矩陣是最優的。Kwon等[40]證明了可逆16× 16二進制矩陣的最大分支數為 8，同時構造了許多分支數為8的16× 16對合二進制矩陣，并且使用一些數學方法找到了矩陣乘積的形式，使二進制矩陣在8 bit和32 bit處理器上軟件的實現效率大大提高。

表1 一些采用MDBL矩陣作為擴散層的密碼算法

Kanda等[51]通過搜索所有候選矩陣找到10 080個具有分支數5的8× 8二進制矩陣，這些矩陣的漢明重量均為44，其中，4個列（行）向量的漢明重量為6，另外4個列（行）向量的漢明重量為5，這些結果對E2和Camellia算法擴散層的設計具有一定的指導意義。

文獻[52]提出了一種統一化的方法構造所有具有最大分支數5的8×8二進制矩陣，并且總結了它們的特征，發現這些矩陣的漢明重量集中在33～44。文獻[53,54]采用組合小矩陣的方式構造大維數的二進制矩陣（16× 16或32 × 32矩陣）。文獻[55]基于4× 4的 Hadamard矩陣和循環矩陣構造帶有一個固定點并且分支數為7的16× 16二進制矩陣。

關于MDBL矩陣的研究，研究者很少提及二進制矩陣的軟硬件實現，Dehnavi等[56]提出一種特殊類型（按位異或）的線性變換，這些線性變換可以表示成具有最大分支數的二進制矩陣的形式，可以有效地在軟硬件上實現。

Feistel和線性反饋移位寄存器（LFSR，linear feedback shift register）是2種重要的密碼結構。Feistel結構不僅廣泛應用于對稱密碼算法（如DES、LBlock、SIMON和SIMECK）中，而且也被用來構造密碼算法的關鍵部件——S盒和擴散層，如CRYPTON算法[57]、ZUC[58]、CS-Cipher[59]均采用三輪Feistel結構構造S盒，MISTY[60]算法也使用三輪Feistel結構構造它的非線性部分FI，文獻[61]對三輪Feistel結構構造的S盒做了進一步研究，文獻[62]使用三輪Feistel結構和MISTY結構構造輕量級S盒。同時，文獻[63]研究了利用Feistel結構構造最優二進制矩陣，其輪函數采用比特置換。

對稱密碼中的流密碼廣泛應用于信息加密、分布式計算、碼分多址（CDMA，code division multiple access）系統等領域。流密碼技術的核心是構造性能優良的密鑰流，線性反饋移位寄存器是一種基本的密鑰流生成器，由于采用邏輯運算，具有原理簡單、計算速度快、便于硬件實現等優點，成為構造密鑰流生成器的重要部件之一[64]。正是由于LFSR的諸多優點，有學者將LFSR應用于分組密碼擴散層的構造上，文獻[7,16,29,30]設計的迭代型擴散層中就用到了LFSR。

本文結合Feistel和LFSR這2種密碼結構的優勢，將其用來構造分組密碼的擴散層，首先研究了基于Feistel結構構造輕量級擴散層，輪函數采用基于循環移位和異或的線性變換，利用三輪Feistel結構構造出了作用在8個4 bit和8 bit S盒上的分支數為 7的輕量級對合擴散層；接著研究了基于LFSR構造輕量級擴散層，使用LFSR構造出了作用在n個m比特S盒上（ n= 4,8;m= 4,8）的輕量級擴散層和6、7、8維MDBL矩陣以及分支數分別為7、7、12的16、18、32維二進制矩陣。

2 預備知識

本節給出分支數的定義和 Feistel結構以及LFSR的基礎知識。

2.1 分支數

也稱為擴散層θ的分支數，其中 wt(x)表示 x中非零分量的個數。

由定義1可知，擴散層的分支數 β≤ n+1。

定義2 將分支數達到最大(n + 1)時的擴散層稱為最優擴散層，對應的矩陣稱為MDS矩陣，其中，

定義3 將分支數達到次最大n時的擴散層稱為次最優擴散層，對應的矩陣稱為次MDS矩陣，其中，

2.2 Feistel結構

Feistel結構[65]廣泛應用于對稱密碼算法中，許多分組密碼算法都采用Feistel結構，其中最著名的是由IBM公司在20世紀70年代設計的DES算法。圖1給出了Feistel密碼結構的加解密過程。加密算法的輸入是長度為2wbit的明文分組和用戶密鑰K，明文分組被分為等長（w bit）的兩部分： LE0和 RE0，這兩部分數據經過n輪迭代后組合成密文分組，第i輪迭代的輸入 LEi?1和 REi?1來自于上一輪迭代的輸出，第i輪迭代的輪密鑰Ki是由用戶密鑰K推導出來的，一般地， Ki不同于K，并且 Ki之間也互不相同。

Feistel密碼結構代替操作作用在數據的左半部分，整個結構通過將輪函數F作用于數據的右半部分后，與左半部分數據進行異或完成。Feistel結構每輪迭代都有相同的輪變換，但每輪的輪密鑰 Ki不同，也就是說，輪函數F是w bit長的右半分組數據以及y bit長的輪密鑰函數，第i輪輪函數的輸出為w bit長的值輪函數操作后，與左半部分數據異或得到第 i+1輪右半部分數據 REi，第 i+1輪的左半部分數據 LEi是第 i輪的右半部分數據。在最后一輪迭代之后有一個交換，用以抵消在最后一輪迭代中的左右部分數據的交換。

Feistel密碼結構的解密過程本質上和加密過程一致，其規則如下：將密文作為算法的輸入，但逆序使用輪密鑰 Ki，也就是說，第一輪使用Kn，第二輪使用 Kn?1，直到最后一輪使用 K1。基于以上特點，Feistel結構只需實現一個算法便可以完成加密和解密操作，大大簡化了硬件實現的電路和軟件實現的代碼量。

2.3 LFSR

反饋移位寄存器由兩部分組成：移位寄存器和反饋函數，移位寄存器是一個比特序列，它的長度用比特表示，若移位寄存器的長度為n bit，則稱為n級移位寄存器。圖2給出了二元域 GF(2)上的n級反饋移位寄存器，其中，n個寄存器從右至左依次稱為第1,2,… ,n級。為反饋函數，它是 n個變量的布爾函數n級反饋移位寄存器的工作原理是：當一個時鐘脈沖到來時，第i級寄存器的內容傳送給第 i?1級寄存器第1級寄存器的內容為反饋移位寄存器的輸出。反饋函數的值傳送給第n級寄存器，可以看出，第 n級寄存器的值是根據其他寄存器的值計算得到的。反饋移位寄存器的輸出序列（稱為反饋移位寄存器序列）為

定義5 如果一個n級反饋移位寄存器的反饋函數是線性函數

則稱該反饋移位寄存器為線性反饋移位寄存器，輸出序列稱為線性反饋移位寄存器序列，記為LFSR序列。LFSR只有一種運算：異或運算，系數不全為0，若c0≠ 0,則稱LFSR為非退化的，若 c0= 0,則稱為退化的 LFSR。圖 3給出了n級LFSR的結構圖。

圖1 Feistel密碼結構加解密過程

圖2 反饋移位寄存器基本結構

圖3 n級LFSR結構

n級 LFSR可以由它的狀態轉移矩陣唯一表示，n級LFSR矩陣可以由狀態轉移矩陣的n次方計算得到，n級LFSR的狀態轉移矩陣如下。

其中， βn?1βn?2βn?3βn?4βn?5βn?6…β0為i的二進制表示，即 (i)2=βn?1βn?2βn?3βn?4βn?5βn?6…β0。

3 基于Feistel結構構造擴散層

本節使用三輪Feistel結構構造分組密碼的擴散層，并且主要集中在對合擴散層的構造上。假設其中（m是S盒的比特長度，n是S盒的個數），基于Feistel結構的擴散層如圖4所示，這類擴散層可以由矩陣表示為

圖4 r輪Feistel結構構造的擴散層

圖5 三輪Feistel結構構造的擴散層

基于 Feistel結構構造輕量級擴散層的特點如下。一方面，基于Feistel結構構造的擴散層逆變換和其本身具有相同的結構，只需簡單地按順序反向使用輪函數即可實現逆變換。這種結構使擴散層和它的逆變換擁有相同的異或數，特別地，對合的擴散層可以使用相同的代碼和電路實現加密和解密，大大節省了軟硬件資源，當輪函數是對稱的時候，矩陣 M為對合矩陣，如和另一方面，Feistel結構簡單，它實際上是利用小矩陣構造大矩陣，如果采用簡單的輪函數，將會構造出十分容易實現的擴散層。為了構造出既安全又高效的擴散層，限定采用三輪Feistel結構，并且只搜索對合擴散層。圖 5給出了三輪 Feistel結構構造的擴散層，矩陣逆矩陣為對合擴散層要求輪函數 P1和 P3相同。下面給出作用在上的基于三輪 Feistel結構構造的輕量級對合擴散層。

本節研究使用循環移位和異或線性變換作為三輪Feistel的輪函數構造輕量級對合擴散層。基于 (Fm)n上的循環移位和異或運算的線性變換

2構造作用在上的擴散層即輪變換為基于循環移位和異或運算的線性變換：共含有k項，并且0 ≤ bj≤為了節省軟硬件實現開銷，利用3項及以下的基于循環移位和異或運算的線性變換構造分組密碼的擴散層，即1 ≤ k≤ 3,并且只考慮對合擴散層。由于實際密碼算法中8個4 bit和8 bit的S盒比較常見，所以這里令 n=4;對合擴散層矩陣為為簡便起見，令輪變換為

表2上構造分支數為7的對合擴散層L(X)

表2上構造分支數為7的對合擴散層L(X)

S1S2{ 0 , 4 , 9 } { 0 , 3 , 7 } { 0 , 4 , 9 } { 0 , 1 0 , 1 5 } { 1 , 5 , 9 } { 0 , 7 , 1 1 } { 1 , 5 , 9 } { 1 , 2 , 1 4 } { 2 , 6 , 1 3 } { 1 , 8 , 1 1 } { 2 , 6 , 1 3 } { 2 , 9 , 1 5 } { 5 , 9 , 1 3 } { 0 , 1 , 4 } { 5 , 9 , 1 3 } { 0 , 2 , 1 4 } { 6 , 1 0 , 1 4 } { 0 , 1 , 5 } { 6 , 1 0 , 1 4 } { 0 , 3 , 7 }

當n=4,m=8時，搜索了部分三輪Feistel結構構造的可逆擴散層，并且輪函數采用3項及以下的循環移位和異或運算的線性變換，沒有找到MDS矩陣，找到部分作用在上的分支數為7的對合擴散層，表3給出了部分分支數為7的對合擴散層 L(X )的例子。

表3上構造分支數為7的對合擴散層L(X)

表3上構造分支數為7的對合擴散層L(X)

S1S2{ 6 , 1 4 , 2 2 } { 6 , 1 4 , 2 3 } { 6 , 1 4 , 2 2 } { 6 , 1 4 , 2 5 } { 6 , 1 4 , 2 2 } { 6 , 1 4 , 2 7 } { 6 , 1 4 , 2 3 } { 8 , 1 3 , 2 8 } { 6 , 1 4 , 2 3 } { 8 , 1 3 , 3 0 } { 6 , 2 1 , 2 9 } { 6 , 1 3 , 2 9 } { 6 , 2 1 , 2 9 } { 6 , 1 3 , 3 1 } { 6 , 2 1 , 2 9 } { 6 , 1 4 , 1 7 } { 6 , 2 2 , 3 0 } { 6 , 1 4 , 1 5 } { 6 , 2 2 , 3 0 } { 2 3 , 2 4 , 3 1 } { 6 , 2 2 , 3 0 } { 2 3 , 2 5 , 3 1 }

4 基于LFSR構造擴散層

表4 利用LFSR構造出上的次最優擴散層

表4 利用LFSR構造出上的次最優擴散層

L F S R維數 L F S R狀態轉移矩陣的最后一列值i 1 6 3 2 9 6 6、3 2 9 7 0、3 2 9 7 8、3 2 9 9 0、3 2 9 9 4、3 3 0 0 3、3 3 0 1 1、3 3 0 3 2、3 3 0 3 3 1 6 3 3 0 3 7、3 3 0 3 9、3 3 0 4 0、3 3 0 4 1、3 3 0 4 2、3 3 0 4 6、3 3 0 4 7、3 3 0 5 1、3 3 0 5 2 1 6 3 3 0 6 1、3 3 0 7 2、3 3 0 7 3、3 3 0 7 5、3 3 0 7 9、3 3 0 8 0、3 3 0 8 2、3 3 0 9 3、3 3 0 9 7 1 6 3 3 0 9 8、3 3 1 0 6、3 3 1 1 4、3 3 1 3 1、3 3 1 3 9、3 3 1 4 5、3 3 1 6 1、3 3 1 6 5、3 3 1 6 7

表5 利用LFSR構造出上的次最優擴散層

表5 利用LFSR構造出上的次最優擴散層

LFSR維數 LFSR狀態轉移矩陣的最后一列值i 32 2147520533、2147520538、2147520547、2147520551、2147520562 32 2147520565、2147520571、2147520574、2147520578、2147520587 32 2147520590、2147520593、2147520598、2147520599、2147520619 32 2147520630、2147520631、2147520634、2147520642、2147520650

表6 利用LFSR構造出上分支數為7的擴散層

表6 利用LFSR構造出上分支數為7的擴散層

L F S R維數 L F S R狀態轉移矩陣的最后一列值i 3 2 2 1 4 8 6 1 8 2 7 9、2 1 4 9 4 5 9 4 6 9、2 1 4 9 6 6 9 1 7 9、2 1 4 9 7 1 7 0 6 9、2 1 5 0 0 3 8 1 6 4 3 2 2 1 5 0 1 6 5 4 7 5、2 1 5 0 1 9 5 6 2 1、2 1 5 0 9 6 2 8 3 5、2 1 5 1 0 4 5 2 6 5、2 1 5 1 1 2 8 2 8 1 3 2 2 1 5 1 4 4 6 9 5 3、2 1 5 1 5 3 6 5 5 8、2 1 5 1 6 5 0 8 3 6、2 1 5 1 8 0 3 1 4 9、2 1 5 1 8 4 9 1 4 7 3 2 2 1 5 1 8 7 1 3 7 0、2 1 5 1 9 3 6 2 0 4、2 1 5 2 0 3 4 1 9 3、2 1 5 2 0 3 6 5 7 7、2 1 5 2 0 5 4 3 5 6

表7 利用LFSR構造出上分支數為7的擴散層

表7 利用LFSR構造出上分支數為7的擴散層

LFSR維數 LFSR狀態轉移矩陣的最后一列值i 64 9296019069125191687、9300522668752562183、9300523218508376071 64 9300523218508376199、9300523218508376215、9300523218508376727 64 9300523218541931159、9300525417565186711、9300525417565187735 64 9300525417565253271、9300525692443160215、9309532891697901207 64 9311784691511586455、9311925428999941783、9311960613372030615 64 9311960613908901527、9311961713420529303、9311966111467040407

4.2 構造二進制矩陣

二進制矩陣因為具有結構簡單、實現過程只需要異或操作等優點，被廣泛應用于分組密碼算法中，MDBL矩陣是二進制矩陣中具有最大分支數的矩陣，很多密碼算法，如ARIA、Camellia、E2、MIBS、Midori、FIDES、Minalpher等的擴散層都使用MDBL矩陣。本節討論了基于n維LFSR構造作用在上n × n大小的二進制矩陣 Mn，這里m是S盒的比特長度，n是S盒的個數。

表8 n維LFSR矩陣最大分支數和MDBL矩陣的分支數 βmdbl

表8 n維LFSR矩陣最大分支數和MDBL矩陣的分支數 βmdbl

nmaxβlfsrβ nmaxmdblβ βmdbllfsr 4 3 4 5 3 4 6 4 4 7 4 4 8 5 5 9 5 6 10 5 6 12 7 8 14 6 8 16 7 8 18 7 8 32 12 12*

表 9統計了當矩陣維數為6,7,8時，利用 n維LFSR構造出的MDBL矩陣。表9中的為n維LFSR的狀態轉移矩陣，的n次方表示對應的MDBL矩陣 Mn，即

表9 當n=6,7,8時，利用LFSR構造出的MDBL矩陣

表10 利用16維LFSR構造出的分支數為7的二進制矩陣

表11給出了部分利用18維LFSR構造出的分支數為7的二進制矩陣，表中i表示18維LFSR狀態轉移矩陣的最后一列值。

表11 利用18維LFSR構造出的分支數為7的二進制矩陣

表12給出了部分利用32維LFSR構造出的分支數為11的二進制矩陣，表中i表示32維LFSR狀態轉移矩陣的最后一列值。

表12 利用32維LFSR構造出的分支數為11的二進制矩陣

5 結束語

擴散層作為分組密碼的一個重要部件，在密碼算法中扮演著重要角色，近幾年，很多研究者都將目光轉移到該問題上，產生了一系列的研究成果[27～56]。然而，目前的結果主要是面向硬件實現的，很少針對軟件實現設計擴散層。本文首先介紹擴散層的研究現狀，接著基于兩大密碼結構構造擴散層，分別是基于Feistel結構構造面向軟件實現的擴散層和基于LFSR構造面向硬件實現的擴散層。

Feistel結構因其軟硬件實現效率高，加解密一致，加解密速度快等優點受到廣大研究者的青睞，Feistel結構不僅廣泛應用于分組密碼算法的整體設計中，而且也用來構造分組密碼的主要部件S盒和擴散層。本文基于三輪Feistel結構構造輕量級擴散層，輪函數采用基于循環移位和異或的線性變換，構造出了一系列作用在和上分支數為 7的對合擴散層，一方面，對合性質使擴散層的加密和解密操作在硬件上可以使用相同的電路，在軟件上可以使用相同的代碼，并且輪函數采用基于循環移位和異或運算的線性變換，在支持循環移位指令的處理器中，循環移位運算通常可以通過一條指令實現，而在不支持循環移位的處理器中，通常只需要將該指令分解成3條指令：邏輯左移1次、邏輯右移1次、兩者異或[67]。不管是移位運算還是循環移位運算，軟件實現所需的CPU周期數均很低，大大提高了軟件實現效率；另一方面，對于作用在8個4 bit或8 bit S盒上的擴散層，分支數為7的擴散層已經可以提供較好的擴散效果，并且分支數為7的擴散層是安全性和效率方面的權衡。

LFSR因其具有原理簡單、計算速度快、便于硬件實現等優點，通常被用來構造密鑰流生成器，而且也被用來構造分組密碼的擴散層[7,13,14,29,30]，基于 LFSR構造的擴散層具有很高的硬件實現效率，擴散層只需實現LFSR且能在不需要額外邏輯控制電路的情形下重用已有的存儲，大大降低了硬件消耗。本文基于LFSR構造出作用在和上的次最優擴散層，這些次最優擴散層應用于軟硬件要求極其苛刻的環境下，可以使密碼算法軟硬件消耗極度降低。利用LFSR也構造出了作用在和上分支數為7的擴散層。另外，二進制矩陣相對于MDS矩陣（實現過程需要異或、查表和xtime操作[68]）而言，實現過程只需要異或操作，具有較高的軟硬件實現效率，非常適合輕量級密碼的設計，本文利用n維LFSR構造了作用在上n × n大小的二進制矩陣，列出了維二進制矩陣的分支數，并給出了采用LFSR構造的6、7、8維MDBL矩陣的具體構造，以及分支數分別為7、7、12的16、18、32維二進制矩陣的具體構造。本文構造的擴散層在輕量級密碼的設計方面具有較高的應用價值。

[1] SCHNEIER B, SCHNEIER B. Data encryption standard (DES)[C]// Advances in Cryptology — EUROCRYPT’ 85. 1985:3-5.

[2] DAEMEN J, RIJMEN V. The design of Rijndael: AES, the advanced encryption standard[M]. Berlin: Springer,2002.

[3] 無線局域網產品中使用的 SMS4算法[EB/OL]. http://www. oscca.gov.cn/UpFile/200621016423197990.pdf. SMS4 algorithm used in wireless LAN products[EB/OL]. http://www. oscca.gov.cn/UpFile/200621016423197990.pdf.

[4] HONG D, SUNG J, HONG S, et al. HIGHT: a new block cipher suitable for low-resource device[C]//Cryptographic Hardware and Embedded Systems. 2006: 46-59.

[5] BOGDANOV A, KNUDSEN L R, LEANDER G, et al. PRESENT: an ultra-lightweight block cipher[C]//Cryptographic Hardware and Embedded Systems .2007:450-466.

[6] SHIRAI T, SHIBUTANI K, AKISHITA T, et al. The 128 bit blockcipher CLEFIA[C]//The 14th International Conference on Fast Software Encryption. 2007:181-195.

[7] GUO J, PEYRIN T, POSCHMANN A, et al. The LED block cipher[C]//Cryptographic Hardware and Embedded Systems. 2011: 326-341.

[8] WU W, ZHANG L. LBlock: a lightweight block cipher[C]//Applied Cryptography and Network Security. 2011: 327-344.

[9] BORGHOFF J, CANTEAUT A, GüNEYSU T, et al. PRINCE—a low-latency block cipher for pervasive computing applications[C]// The International Conference on the Theory and Application of Cryptology and Information Security. 2012: 208-225.

[10] RAY B, DOUGLAS S, JASON S. The simon and speck families of lightweight block ciphers[R]. 2013.

[11] GéRARD B, GROSSO V, NAYA-PLASENCIA M, et al. Block ciphers that are easier to mask: How far can we go?[C]// International Workshop on Cryptographic Hardware and Embedded Systems. 2013: 383-399.

[12] YANG G, ZHU B, SUDER V, et al. The simeck family of lightweight block ciphers[C]//The International Workshop on Cryptographic Hardware and Embedded Systems. 2015: 307-329.

[13] GUO J, PEYRIN T, POSCHMANN A. The photon family of lightweight Hash functions[C]//Advances in Cryptology Conference. 2011:222-239.

[14] ANDREEVA E, BILGIN B, BOGDANOV A, et al. Submission to the CAESAR competition[EB/OL].http://competitions.cr.yp.to/ round1/ primatesv1.pdf.

[15] RIJMEN V, DAEMEN J. The cipher shark[C]//Fast Software Encryption. 1996:99-112.

[16] SCHNEIER B, KELSEY J, WHITING D, et al. Twofish: a 128 bit block cipher[C]//The 1st AES Candidate Conference on National Institute for Standards and Technology. 1998.

[17] SCHNEIER B, KELSEY J, WHITING D, et al. The twofish encryption algorithm[M]. New York:John Wiley & Sons. 1999.

[18] DAEMEN J, KNUDSEN L R, RIJMEN V. The block cipher square[C]//The 4th Fast Software Encryption Workshop. 1997: 149-165.

[19] BARRETO P, RIJMEN V. The anubis block cipher[EB/OL]. http://www.larc.usp.br/～pbarreto/AnubisPage.html.

[20] BARRETO P, RIJMEN V. The khazad legacy-level block cipher[C]//Primitive Submitted to NESSIE. 2000.

[21] JUNOD P, VAUDENAY S. FOX: a new family of block ciphers[C]//Selected Areas in Cryptography. 2004:114-119.

[22] DAI W, FURUYA S, YOSHIDA H, et al. A new keystream generator MUGI[M]//Fast Software Encryption. Berlin: Springer, 2002:37-45.

[23] FILHO G D, BARRETO P, RIJMEN V. The maelstrom-0 Hash function[C]//The 6th Brazilian Symposium on Information and Computer Systems Security. 2006.

[24] GAURAVARAM P, KNUDSEN L R, MATUSIEWICZ K, et al. Gr?stl a SHA-3 candidate[EB/OL]. http://www.groestl.info.

[25] BARRETO P S L M, RIJMEN V. The Whirlpool hashing function[EB/OL].http://read.pudn.com/downloads67/sourcecode/disk/2 40939/Whirlpool.pdf.

[26] MORADI A, POSCHMANN A, LING S, et al. Pushing the limits: a very compact and a threshold implementation of AES[C]//Advances in Cryptology – EUROCRYPT .2011.

[27] 崔霆, 金晨輝. 對合 Cauchy-Hadamard型 MDS矩陣的構造[J].電子與信息學報, 2010, 32(2):500-503.

CUI T, JIN C H. Construction of involution cauchy-hadamard type MDS matrices[J]. Journal of Electronics & Information Technology, 2010, 32(2): 500-503.

[28] SAJADIEH M, DAKHILALIAN M, MALA H, et al. On construction of involutory MDS matrices from Vandermonde Matrices in GF [J]. Designs, Codes and Cryptography, 2012, 64(3):287-308.

[29] SAJADIEH M, DAKHILALIAN M, MALA H, et al. Recursive diffusion layers for block ciphers and Hash functions[C]//The International Conference on Fast Software Encryption. 2012:385-401.

[30] WU S, WANG M, WU W. Recursive diffusion layers for (lightweight)block ciphers and Hash functions[C]//Selected Areas in Cryptography. 2012:355-371.

[31] AUGOT D, FINIASZ M. Exhaustive search for small dimension recursive MDS diffusion layers for block ciphers and Hash functions[C]//IEEE International Symposium on Information Theory Proceedings.2013:1551-1555.

[32] BERGER T P. Construction of recursive MDS diffusion layers from Gabidulin codes[C]//INDOCRYPT. 2013:274-285.

[33] AUGOT D, FINIASZ M. Direct construction of recursive MDS diffusion layers using shortened BCH codes[C]// Fast Software Encryption.2014:3-17.

[34] KHOO K, PEYRIN T, POSCHMANN A Y, et al. FOAM: searching for hardware-optimal SPN structures and components with a fair comparison[C]//Cryptographic Hardware and Embedded System. 2014:433-450.

[35] SIM S M, KHOO K, OGGIER F, et al. Lightweight MDS involution matrices[C]//Fast Software Encryption. 2015:471-493.

[36] NAKAHARA J, ABRAHO L. A new involutory MDS matrix for the AES[J]. International Journal of Network Security, 2009, 9(2): 109-116.

[37] GUPTA K C, RAY I G. On constructions of circulant MDS matrices for lightweight cryptography[C]// Information Security Practice and Experience. 2014:564-576.

[38] LIU M, SIM S M. Lightweight MDS generalized circulant matric-es[C]// Fast Software Encryption. 2016.

[39] LI Y, WANG M. On the construction of lightweight circulant involutory MDS matrices[C]// Fast Software Encryption. 2016.

[40] KWON D, KIM J, PARK S, et al. New block cipher: ARIA[C]// ICISC. 2003:432-445.

[41] AOKI K, ICHIKAWA T, KANDA M, et al. Camellia: a 128 bit block cipher suitable for multiple platforms design and analysis[C]//Selected Areas in Cryptography. 2000:39-56.

[42] KANDA M, MORIAI S, AOKI K, et al. E2—a new 128 bit block cipher[J]. Ieice Transactions on Fundamentals of Electronics Communications & Computer Sciences, 2000, 83(1):48-59.

[43] IZADI M, SADEGHIYAN B, SADEGHIAN S S, et al. MIBS: a new lightweight block cipher[C]//The International Conference on Cryptology and Network Security.2009:334-348.

[44] BANIK S, BOGDANOV A, ISOBE T, et al. Midori: a block cipher for low energy[C]//The International Conference on the Theory and Application of Cryptology and Information Security. 2014: 411-436.

[45] BILGIN B, BOGDANOV A, KNE?EVI? M, et al. Fides: lightweight authenticated cipher with side-channel resistance for constrained hardware[C]//The International Workshop on Cryptographic Hardware and Embedded Systems. 2013: 142-158.

[46] SASAKI Y, TODO Y, AOKI K, et al. Minalpher v1[C]//Submission to the CAESAR Competition. 2014.

[47] KWON D, SUNG S H, SONG J H, et al. Design of block ciphers and coding theory[J]. Trends in Mathematics, 2005, 8(1): 13-20.

[48] KOO B W, JANG H S, SONG J H. Constructing and cryptanalysis of a 16×16 binary matrix as a diffusion layer[C]//The International Workshop on Information Security Applications. 2003:489-503.

[49] KOO B W, JANG H S, SONG J H. On constructing of a 32×32 binary matrix as a diffusion layer for a 256-bit block cipher[C]// Information Security and Cryptology (ICISC). 2006:51-64.

[50] KANG J S, HONG S, LEE S, et al. Practical and provable security against differential and linear cryptanalysis for substitution permutation networks[J]. ETRI Journal, 2001, 23(4): 158-167.

[51] KANDA M, TAKASHIMA Y, MATSUMOTO T, et al. A strategy for constructing fast round functions with practical security against differential and linear cryptanalysis[C]//Selected Areas in Cryptography. 1998: 264-279.

[52] GAO Y, GUO G. Unified approach to construct 8×8 binary matrices with branch number 5[C]// The 1st Acis International Symposium on Cryptography, and Network Security, Data Mining and Knowledge Discovery, E-Commerce and ITS Applications, and Embedded Systems. 2010:413-416.

[53] ASLAN B, SAKALLI M. Algebraic construction of cryptographically good binary linear transformations[J]. Security and Communication Networks, 2014, 7(1):53-63.

[54] SAKALL M T, ASLAN B. On the algebraic construction of cryptographically good 32×32 binary linear transformations[J]. Journal of Computational & Applied Mathematics, 2014, 259: 485-494.

[55] SAKALL S M T, ASLAN B. Algebraic construction of 16×16 binary matrices of branch number 7 with one fixed point[EB/OL]. http://www.singacom.uva.es/～edgar/cactc2012/trabajos/CACT2012_ Sakalli.pdf.

[56] DEHNAVI S M, RISHAKANI A M, SHAMSABAD M R M. Bitwise linear mappings with good cryptographic properties and efficient implementation[J]. Antiquity, 2015, 75.

[57] LIM C H. CRYPTON: a new 128-bit block cipher[J]. Nist Aes Proposal, 1998.

[58] ETSI/SAGE TS 35.222-2011, Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3; Document 2: ZUC Specification[S].

[59] STERN J, VAUDENAY S. CS-Cipher[J]. Lecture Notes in Computer Science, 1998, 1372:189-205.

[60] MATSUI M. New block encryption algorithm MISTY[C]//The International Workshop on Fast Software Encryption. 1997:54-68.

[61] LI Y, WANG M. Constructing s-boxes for lightweight cryptography with feistel structure[C]//Cryptographic Hardware and Embedded Systems.2014:127-146.

[62] CANTEAUT A, DUVAL S, LEURENT G. Construction of lightweight s-boxes using feistel and misty structures[C]//The International Conference on Selected Areas in Cryptography. 2015: 373-393.

[63] GUO Z, WU W, GAO S. Constructing lightweight optimal diffusion primitives with feistel structure[C]//The International Conference on Selected Areas in Cryptography. 2015: 352-372.

[64] 張雪鋒, 范九倫. 基于線性反饋移位寄存器和混沌系統的偽隨機序列生成方法[J]. 物理學報, 2010, 59(4):2289-2297.

ZHANG X F, FAN J L. Pseudo-random sequence generating method based on LFSR and chaotic system[J]. Acta Physica Sinica, 2010, 59(4):2289-2297.

[65] STALLINGS W. Cryptography and network security: principles and practice, fifth edition[M]. Pearson Education, 2011.

[66] TODO Y, AOKI K. Wide trail design strategy for binary mixcolumns[M]. Applied Cryptography and Network Security. 2016.

[67] 公麗麗. 分組密碼的軟件實現評估方法研究及RECTANGLE在X86平臺的軟件實現測評[D]. 北京: 中國科學院大學, 2015.

GONG L L. A study of software implementation of block cipher and software implementation of RECTANGLE on X86 platforms[D]. Beijing: The University of Chinese Academy of Sciences, 2015.

[68] NAKAHARA J,ABRAH?O E. A new involutory MDS matrix for the AES[J].International Journal of Network Security, 2009, 9(2): 109-116.

Construction of diffusion layers based on cipher structures

LI Peng-fei1,2

(1. The State Key Lab of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China; 2. School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China)

Taked diffusion layers of block cipher algorithms as the research object, lightweight diffusion layers were constructed by two cipher structures based on the characteristics of diffusion layers of lightweight block cipher algorithms, which were the construction of software-oriented diffusion layers based on Feistel structure and the construction of hardware-oriented diffusion layers based on LFSR. Lightweight involution diffusion layers with branch numbers 7 over eight 4-bit and 8-bit S-boxes were constructed by 3-round Feistel structure and the round functions adopt linear transformations with rotation and XORs. Some suboptimal diffusion layers over four 4 bit and 8 bit S-boxes and diffusion layers with branch numbers 7 over eight 4 bit and 8 bit S boxes based on LFSR were constructed. In addition, 6, 7, 8 dimension MDBL matrices and many 16, 18, 32 dimension binary matrices with big dimension and branch numbers 7, 7, 12 based on LFSR were constructed. The experimental results have high practical significance in realm of the design of block cipher algorithms.

block cipher, diffusion layer, Feistel structure, linear feedback shift register, MDBL matrix

The National Natural Science Foundation of China (No.61379142)

TP393

A

10.11959/j.issn.2096-109x.2017.00170

2017-04-07；

2017-05-20。通信作者：李鵬飛，lipengfei@iie.ac.cn

國家自然科學基金資助項目（No.61379142）

李鵬飛（1991-），男，陜西渭南人，中國科學院信息工程研究所碩士生，主要研究方向為密碼學。