一種新的面向硬件輕量級near-MDS矩陣的構造算法*

張怡帆,任炯炯,陳少真

1.解放軍信息工程大學,鄭州450001

2.數學工程與先進計算國家重點實驗室,鄭州450001

1 引言

線性擴散層是對稱密碼的一個重要組件,它為對稱密碼算法提供了內部獨立性.對于對稱密碼算法來說,其線性擴散層是設計時需要重點考慮的關鍵部件.我們用分支數來衡量一個擴散層的安全性,分支數較大的擴散層能更好地抵抗差分和線性攻擊.在資源受限的環境下,不僅需要考慮安全性,而且要關注輕量級密碼算法擴散層的硬件效率.隨著輕量級密碼的快速發展[1–4],如何構造分支數較大,硬件效率高的輕量級擴散層引起人們的重視.

分支數達到最大的矩陣稱作MDS矩陣,能實現最好的擴散效果,因此許多MDS矩陣如遞歸MDS矩陣和對合MDS矩陣的構造方法被提出[5–16].許多算法諸如AES 等的線性擴散層采用MDS矩陣以期達到最好的擴散性,但MDS矩陣中的每一個元素均為非零,因此在硬件應用時耗能較大,效率較低.在資源受限的今天,算法實現起來較為困難.隨著物聯網技術等普適計算的發展,對硬件提出了新的安全需求,輕量級密碼的研究領域越來越受重視.輕量級密碼算法對安全性的要求相較來說有所降低,而如何在保證安全性的前提下提高效率受到了廣泛關注.

2008年,Choy[17]和Khoo[9]將差分分支數達到次優的矩陣定義為almost-MDS矩陣,由于兩篇文章中的almost-MDS矩陣對應不同文獻給出的線性碼定義,因此將差分與線性分支數均達到次優的矩陣稱為near-MDS矩陣.與MDS矩陣相比,near-MDS矩陣的分支數僅次于MDS矩陣,安全性也僅次于MDS矩陣,但其具有實現代價小的優勢.在對安全性的要求降低,實現代價要求提高的資源受限環境下,用near-MDS矩陣作為擴散層是一個很好的選擇.實際上,一些用near-MDS矩陣構造的擴散層在硬件應用上的表現優于MDS矩陣或者迭代MDS矩陣.近來,near-MDS矩陣已經被許多輕量級分組密碼采用,包括PRINCE[18]、FIDES[19]、PRIDE[20]、Midori[21]和MANTIS[22]等.Near-MDS矩陣被廣泛應用在低消耗低延遲的輕量級分組密碼的設計中,因此研究此類矩陣具有一定的密碼學價值和現實意義.

有限域F2m中的每個元素都可以表示成F2上的m×m矩陣,所以F2m上的MDS矩陣實際上對應著F2上的一個分塊矩陣,每一塊都是m×m大小,需要注意的是,并不是F2上的每一個矩陣都可以代表有限域F2m內的一個元素,這取決于它的最小多項式是否為不可約的.Li[23]利用有限域F2m內的元素作為擴散矩陣的元素,在F24上構造出10 個XORs 最少的4×4 near-MDS矩陣.但是有限域F2m內的元素乘法問題[5]只是上線性變換的一種特殊形式,在上還存在著許多不能用有限域F2m中的元素乘法表示的線性變換[10],上的線性變換空間可以表示為F2上的m×m矩陣.因此,若只考慮在有限域F2m中構造MDS矩陣有可能會導致丟失一些較好的構造結果,在上的線性變換空間中,有可能構造出新的符合要求的輕量級near-MDS矩陣.在之前的構造方法中,用來構造矩陣的元素滿足成對交換,或者假定滿足成對交換[24,25],但該假定條件也可能會導致丟失較好的構造結果,所以本文中,沒有假定用來構造near-MDS矩陣的上的線性變換是成對交換的.

在對稱密碼算法中,最常用的是4 比特S盒和8 比特S盒,最常用擴散矩陣的維度是4.當矩陣維度較大時,計算復雜度會變得非常復雜,因此將重點放在利用和上的線性變換來構造4×4 near-MDS矩陣上.本文利用直接將F2上的m×m矩陣作為擴散矩陣元素的方法,利用循環矩陣、對合矩陣的性質給出了循環對合矩陣元素間滿足的性質引理,利用引理給出算法搜索的約束條件,并借助Matlab 構造出4×4 循環對合near-MDS矩陣,在m=4時可以找到48 個滿足條件XORs 最少的4×4 循環對合near-MDS矩陣,m=8時,依據文獻[9,14,26]中提到的子域構造方法,可直接得到異或操作數最少的8×8 循環對合near-MDS矩陣,較之前結果找到了更多的XORs 最少的循環對合near-MDS矩陣,且計算復雜度較小,在Windows 10 系統、i5-6200U CPU 處理器、4 G 內存的機器條件下僅需要大概6 分鐘.

本文結構安排如下:第2 節給出了本文所涉及的符號表示及相關基礎知識; 第3 節給出對near-MDS矩陣內元素的一個基本限制條件以及對合循環near-MDS矩陣的構造方法,并給出了自動搜索算法以及結果; 第4 節給出了一個簡短的總結.附錄中記錄了本文所有的搜索結果.

2 基礎知識

2.1 符號表示

XORs:異或操作次數;

Bd(L):矩陣L的差分分支數;

Bl(L):矩陣L的線性分支數;

#A:A·x所需的異或操作次數;

ω(A[i]):矩陣A中第i行非零元素的個數.

2.2 相關基礎知識

本節介紹一些相關的基礎概念和定義.

2.2.1 分支數

對x,y∈,若映射A:→滿足A(x+y)=A(x)+A(y),則稱為線性映射.在F2上固定的一組基,則上的一個線性映射可以表示為F2上的一個m×m矩陣,我們用A來表示,滿足A(x)=A·x,其中x=(x1,··· ,xm)∈,在本文中代表一個列向量.一個線性映射是上的一個置換當且僅當它的矩陣表示是非奇異的.GL(m,S)代表所有m×m的非奇異矩陣,矩陣中元素屬于S,S是一個元素集.

每個線性擴散層都是一個線性映射,可以用如下矩陣表示:

其中Li,j是F2上的m×m矩陣,對X=(x1,··· ,xn)∈L(X)=其中對于X=(x1,···,xn)∈中非零元素的個數定義為重量,用

定義1矩陣L是上的n×n矩陣,L的差分分支數定義為

L的線性分支數定義為

分支數可以用線性碼的最小距離來表示.

定理1[27]假設矩陣L是上的n×n矩陣,C是上的一個[2n,n]線性碼,它的生成矩陣是(In|LT),其中In是一個n維單位矩陣.則矩陣L的差分分支數等價于線性碼C的最小距離,即Bd(L)=d(C).此外,Bl(L)=d(C⊥),其中C⊥是C的共軛碼.

令C是一個[N,k]線性碼,當C的最小距離達到上界d(C)=N?k+1[28]時,我們稱其為一個MDS 線性碼.若生成矩陣是(Ik|LT)的線性碼CL是一個MDS 線性碼,則稱矩陣L是MDS矩陣.MDS矩陣的差分分支數和線性分支數同時達到上界[29],即Bl(L)=d(CL)=N?k+1.

MDS矩陣分支數達到最大,能實現最好的擴散效果,但是由于MDS矩陣的每一個元素均為非零,在硬件應用時耗能較大,效率較低.為折衷考慮安全性與效率的問題,本文主要研究非MDS矩陣中分支數達到最大的矩陣,下面我們給出near-MDS矩陣的定義.

定義2當Bd(L)=Bl(L)=d(CL)=n時,上的n×n矩陣L是near-MDS矩陣.

在文獻[29]中,一個[n,k]線性碼C滿足條件d(C)=n?k,d(C⊥)=k.那么根據定理1,若一個n×n矩陣L滿足Bd(L)=Bl(L)=n,那么矩陣(In|LT)是一個[2n,n,n]near-MDS 線性碼的生成矩陣.由此我們給出定理2.

定理2[30]L是一個n維的非MDS矩陣,n是一個正整數且n≥2.則L是一個near-MDS矩陣的充要條件是:對任意的1≤g≤n?1,矩陣L的每一個g×(g+1)子矩陣和(g+1)×g子矩陣都至少有一個非奇異的g×g子矩陣.

由定理2 可知,當n較大時,為驗證near-MDS矩陣的性質,計算量會相當復雜.因此本文重點研究4×4 矩陣,這是在密碼算法中被廣泛使用的矩陣大小.本文利用循環矩陣來構造輕量級near-MDS矩陣,循環矩陣可以用第一行的元素來定義,因此可以重復利用元件,提高硬件應用效率.

定理3[11]對任意置換矩陣P1和P2,矩陣L和P1LP2有相同的差分和線性分支數.

由定理3 可得,當循環矩陣Circ(A,B,C,D)的第一行元素發生位置改變時,矩陣的分支數保持不變.

2.2.2 XOR 數

a,b∈F2,a+b被稱為比特XOR 運算.對于A∈GF(m,F2),#A表示A·x所需的XOR 操作次數,其中表示矩陣A中第i行非零元素的個數.例如為方便描述,本文用矩陣每一行非零元素的位置給出一個矩陣的簡單表達式,例如[2,3,4,[1,4]]是矩陣A的簡單表達式.

對之前給出的矩陣L=令X=(x1,··· ,xn)∈我們給出所需要的異或操作數,其中Li,j(xj)=以矩陣L的第一行為例,所需的異或操作數為#L1,1+#L1,2+···+#L1,n+(l?1)·m,l為第一行中非零Li,j的個數.

2.2.3 循環矩陣

特殊矩陣具有特殊的結構特點,其特點在應用過程中可能有利于降低硬件耗能,因此考慮借助特殊矩陣形式來構造擴散矩陣.本小節給出本文所用特殊矩陣的定義.

定義3一個矩陣被稱為循環矩陣當且僅當它的每一行都是前一行向右(向左)循環一個元素的位置.

例如對一個4×4 的循環矩陣我們表示為:Circ(A,B,C,D)=循環矩陣每一行的元素均與第一行相同,在硬件應用時可以重復利用乘法元件,進而大大提高硬件應用效率,因此被很多輕量級密碼算法所采用.

3 輕量級循環near-MDS矩陣

本節研究輕量級循環對合near-MDS矩陣的構造方法,證明矩陣元素滿足循環對合性質所必須遵循的性質引理,根據引理,給出了搜索算法的約束條件條件,借助Matlab 尋找滿足條件的異或數最少的矩陣.本文搜索到了48 個滿足條件的循環對合near-MDS矩陣,較之前搜索結果更多,并且減少了搜索的時間復雜度,在Windows 10 系統、i5-6200U CPU 處理器、4 G 內存的機器條件下需要大概6 分鐘.

3.1 Near-MDS矩陣的元素限制條件

near-MDS矩陣的分支數達到次優,其矩陣元素有如下特點:

引理1假設循環矩陣Circ(A,B,C,D)是一個near-MDS矩陣,則矩陣元素A,B,C,D中至多有一個為零矩陣O.

證明:若A,B,C,D中有兩個元素為O,假設為A,B.根據定理2,當g=1時矩陣Circ(A,B,C,D)有一個1×2 的子矩陣不滿足至少有一個1×1 的子矩陣是非奇異的,與定理2 給出的near-MDS 性質矛盾.所以矩陣元素A,B,C,D中至多有一個為零矩陣O.

本文的主要目標是減少搜索范圍,尋找 XORs 最少的 near-MDS矩陣.根據引理1,假設Circ(A,B,C,D)中一直存在一個零矩陣O,根據定理3,循環矩陣第一行元素位置發生變化時,矩陣的分支數保持不變,因此本文重點研究Circ(O,A,B,C)這種形式的矩陣.

3.2 構造循環對合矩陣

循環矩陣元素排列有很明顯的特點,若要一個循環矩陣Circ(O,A,B,C)同時滿足對合性,其元素相互之間也存在一定的約束條件,對此本文有如下結果:

引理2L=Circ(O,A,B,C)是一個循環矩陣,其中A,B,C∈GL(m,F2).矩陣L滿足對合性當且僅當下列等式同時滿足:AB=BA,BC=CB,A2=C2,AC+CA+B2=I.

證明:通過矩陣乘法,可以得到

若矩陣L具有對合性,則滿足條件L2=Circ(I,0,0,0),因此L是一個對合矩陣當且僅當下列條件同時滿足:AB=BA,BC=CB,A2=C2,AC+CA+B2=I.

由引理2 給出的矩陣Circ(O,A,B,C)滿足對合性其元素之間具有的約束條件,下面給出循環對合矩陣的一般構造方法.首先我們給出乘法階的定義:對于矩陣A∈GL(m,F2),滿足等式Ad=I的最小正整數d稱為A的乘法階.

引理3假設A,C∈GL(m,F2)且滿足條件A2=C2=I,I+A+C的乘法階為4k?2,其中k≥1.令B=(I+A+C)2k,則矩陣Circ(O,A,B,C)是一個對合矩陣.

證明:令B=(I+A+C)2k,因為A和C滿足條件A2=C2=I,根據引理2,我們只需證明下面等式即可:

首先容易證明

然后可得B=(I+A+C)2k=(I+AC+CA)k.因此

同理我們可以證得BC=CB.因為(I+A+C)4k?2=I,因此我們可以得到

根據引理3,我們得到了矩陣Circ(O,A,(I+A+C)2k,C)是對合矩陣.

注意:當A=C時,(I+A+C)的乘法階為1,不滿足4k?2 的條件.這種情況下L=Circ(O,A,B,C)=Circ(O,A,B,A)仍為一個循環矩陣,若要滿足對合性應同時滿足條件B2=I,AB=BA,根據條件仍可尋找循環對合矩陣.

由引理2、引理3,我們給出要使矩陣滿足循環對合性,矩陣元素所需滿足的條件,利用引理給出自動搜索算法的約束條件,進而可以很大程度減小搜索范圍.再利用定理2 給出的near-MDS矩陣的特性,借助Matlab,進一步搜索循環對合near-MDS矩陣.下面給出算法介紹以及搜索結果.

3.3 自動化搜索算法及結果

在上一節中我們推導出滿足循環對合條件的矩陣元素之間所需滿足的條件

(1)A=C時,A2=C2=I,(I+A+C)4k?2=I,k≥1,B=(I+A+C)2k.

(2)A=C時,B2=I,AB=BA.

將矩陣元素所滿足的式子轉化為算法中的約束條件,縮小搜索范圍,在得到循環對合矩陣之后進一步檢驗其是否具有near-MDS矩陣的性質,最終獲得循環對合near-MDS矩陣.構造算法步驟如下:

首先獲得一個集合S,其中包含所有滿足對合性的矩陣.然后分以下兩種情況討論:

(1)A=C時,我們選取矩陣對(A,C)∈S×S,計算I+A+C的乘法階d,若dmod 4=2,則是循環對合矩陣.

(2)A=C時,選取B∈S,若滿足AB=BA,則Circ(O,A,B,A)是循環對合矩陣.

本文借助Matlab 計算機程序,通過添加對矩陣元素的限制條件縮小搜索范圍,對滿足條件的循環對合near-MDS矩陣進行算法搜索.為尋找異或數最少的矩陣,矩陣元素集S的選擇在搜索算法中起到了關鍵的作用,一般來說,元素的XORs 越少,矩陣的XORs 也會相應較少,因此在選擇矩陣元素集時,首先從XORs 最少的矩陣集S開始搜索.因為XORs 最少為0,所以本文首先尋找滿足對合性且XORs 為0即非零元素個數為4 的矩陣,將其作為矩陣集S,在S中搜索是否存在滿足上述兩種情況之一(A,B,C).若不存在,則擴大矩陣集S的范圍,尋找滿足對合性且XORs 為0 或者XORs 為1 的矩陣,將其作為矩陣集S進行搜索.以此類推,直到找到滿足條件的(A,B,C).

其次,在得到循環對合矩陣后我們要驗證其是否為near-MDS矩陣,根據定理2 給出的near-MDS 性質,對任意的1≤g≤n?1,矩陣L的每一個g×(g+1)子矩陣和(g+1)×g子矩陣都至少有一個非奇異的g×g子矩陣.若一個矩陣為非奇異矩陣,則其行列式一定不為0.為驗證near-MDS 性質,對于一個g×(g+1)子矩陣或者(g+1)×g子矩陣,我們需要計算其所有的g×g子矩陣行列式的絕對值,為保證至少有一個非奇異的g×g子矩陣,應滿足所有的g×g子矩陣的行列式絕對值之和大于0.由此,為驗證所構造循環對合矩陣是否為near-MDS矩陣,本節給出如下引理及證明.

引理4令d1,d2,··· ,dk≥0 代表k個正數值,其中k是一個正整數,若d1,d2,··· ,dk中至少有一個非零值當且僅當d1+d2+···+dk>0.

證明:因為d1,d2,··· ,dk≥0,要滿足d1+d2 +···+dk=0,當且僅當d1=d2=···=dk=0,與所給條件矛盾.因此應滿足d1+d2+···+dk>0.

綜合考慮之前給出的元素約束條件以及near-MDS矩陣性質驗證方法,利用Matlab 計算機程序,給出的具體搜索算法.見算法1.

算法1 構造循環對合矩陣并檢驗near-MDS矩陣的性質Input:矩陣元素限制條件; 4×4 循環矩陣Circ(O,A,B,C);Output:循環對合near-MDS矩陣Circ(O,A,B,C)1 S ←?;2 if N2=I & & #N=4 then 24 for g ∈[1,n?1]do 25 for 矩陣T 所有g×(g+1)和(g+1)×g 子矩陣M do 3 N ∈S;4 end 5 for A=C do 26 p ←0;27 for 矩陣M 的所有g×g 子矩陣N do 6(A,C)∈S×S;7 計算I +A+C 的乘法階d ;8 if d mod 4=2 then 28 計算行列式det(N)的絕對值q;29 p ←p+q;30 if p=0 then 9 B=(I +A+C)d2+1;10 end 11 end 12 for A=C do 31 return false;32 end 33 else 13 B ∈S;14 if AB=BA then 15 T=Circ(O,A,B,C);16 end 17 end 18 if 不存在(A,B,C)滿足條件then 34 T=Circ(O,A,B,C)是一個循環對合35 near-MDS矩陣36 end 37 end 38 end 39 end 40 return T 19 重新選擇矩陣集S;20 if N2=I & & #N=4+1=5 then 21 N ∈S;22 end 23 end

搜索結果如下:

m=4時,本文選取S∈GL(4,F2).首先搜索XORs 為0 的矩陣集S,在S中搜索到了滿足Circ(O,A,B,C)是near-MDS矩陣的(A,B,C),并且#A+#B+#C=0,達到了矩陣第一行元素異或操作數之和的最小值.利用上述算法我們找到了48 組滿足條件的(A,B,C),其中有36 組滿足A=C,12 組滿足A=C.

實例:

(1)m=4 且A=C時,A=[4,2,3,1],C=[4,2,3,1],B=[1,3,2,4].

(2)m=4 且A=C時,A=[3,4,1,2],C=[4,3,2,1],B=[1,2,3,4].

m=8時,因為已經構造出m=4時滿足#A+#B+#C=0 的循環對合near-MDS矩陣,根據文獻[9,14,26]中提到的子域構造方法,我們很容易在GL(8,F2)中構造出滿足#A+#B+#C=0 的循環對合near-MDS矩陣.舉例介紹子域構造方法,令X,Y,Z∈GL(4,F2),#X=#Y=#Z=0 并且Circ(O,X,Y,Z)是一個循環對合near-MDS矩陣,則對A,B,C∈GL(8,F2),Circ(O,A,B,C)也是一個循環對合near-MDS矩陣,其中

實例:

(1)m=8 且A=C時,A=[4,2,3,1,8,6,7,5],C=[4,2,3,1,8,6,7,5],B=[1,3,2,4,5,7,6,8].

(2)m=8 且A=C時,A=[3,4,1,2,7,8,5,6],C=[4,3,2,1,8,7,6,5],B=[1,2,3,4,5,6,7,8].

表1 給出了用本文方法構造的滿足條件的矩陣數與已知的用有限域內元素乘法問題構造的矩陣數的比較,可以看出本文構造出了較之前結果更多的滿足條件的矩陣,這對算法的設計具有一定的借鑒意義.所有的構造算法結果見附錄.

表1 本文結果與文獻[22]結果對比Table 1 Compare results of proposed method and Ref.[22]

4 總結

在資源受限的環境下,輕量級密碼算法擴散層的設計更加注重硬件效率.隨著輕量級密碼的快速發展,構造分支數較大,硬件效率高的輕量級擴散層是一個亟需解決的問題.

本文主要探索了用F2上的m×m矩陣來構造4×4 輕量級near-MDS矩陣的方法,理論上證明了如何判斷循環對合的性質引理,在此基礎上,將引理條件轉化為自動搜索算法的約束條件,給出了Matlab程序編譯算法,實現了對滿足條件矩陣的算法搜索.利用循環矩陣和對合矩陣的特性推導出矩陣元素之間的關系,在Matlab 算法搜索過程中添加矩陣元素的約束條件,縮小搜索范圍,降低復雜度.同時選擇XORs 較少的矩陣元素,以獲得硬件效率高的擴散矩陣.本文對F2上的4×4 循環對合near-MDS矩陣進行了搜索,找到了48 個XORs 最少的矩陣,較之前利用有限域內元素乘法構造的滿足條件的10 個矩陣,不僅給出滿足條件的矩陣數量更多,而且降低了搜索的時間復雜度.如何利用其它類型特殊矩陣的性質獲得矩陣元素約束條件以及構造更大維度的輕量級near-MDS矩陣還需要進一步的研究與實驗.

附錄

(1)A=C,m=4時,滿足B2=I、AB=BA,Circ(O,A,B,C)是上的循環對合near-MDS矩陣.我們找到了36 組滿足條件的[A,B].

1.A=[4,3,2,1]B=[4,3,2,1]

2.A=[4,3,2,1]B=[3,4,1,2]

3.A=[4,3,2,1]B=[2,1,4,3]

4.A=[4,3,2,1]B=[1,2,3,4]

5.A=[4,2,3,1]B=[4,2,3,1]

6.A=[4,2,3,1]B=[1,3,2,4]

7.A=[3,2,4,1]B=[1,2,3,4]

8.A=[2,4,3,1]B=[1,2,3,4]

9.A=[3,4,1,2]B=[4,3,2,1]

10.A=[3,4,1,2]B=[3,4,1,2]

11.A=[3,4,1,2]B=[2,1,4,3]

12.A=[3,4,1,2]B=[1,2,3,4]

13.A=[4,2,1,3]B=[1,2,3,4]

14.A=[3,2,1,4]B=[3,2,1,4]

15.A=[3,2,1,4]B=[1,4,3,2]

16.A=[2,3,1,4]B=[1,2,3,4]

17.A=[4,1,3,2]B=[1,2,3,4]

18.A=[3,1,2,4]B=[1,2,3,4]

19.A=[2,1,4,3]B=[4,3,2,1]

20.A=[2,1,4,3]B=[3,4,1,2]

21.A=[2,1,4,3]B=[2,1,4,3]

22.A=[2,1,4,3]B=[1,2,3,4]

23.A=[2,1,3,4]B=[2,1,3,4]

24.A=[2,1,3,4]B=[1,2,4,3]

25.A=[1,4,3,2]B=[3,2,1,4]

26.A=[1,4,3,2]B=[1,4,3,2]

27.A=[1,3,4,2]B=[1,2,3,4]

28.A=[1,4,2,3]B=[1,2,3,4]

29.A=[1,3,2,4]B=[4,2,3,1]

30.A=[1,3,2,4]B=[1,3,2,4]

31.A=[1,2,4,3]B=[2,1,3,4]

32.A=[1,2,4,3]B=[1,2,4,3]

33.A=[1,2,3,4]B=[4,3,2,1]

34.A=[1,2,3,4]B=[3,4,1,2]

35.A=[1,2,3,4]B=[2,1,4,3]

36.A=[1,2,3,4]B=[1,2,3,4]

(2)A=C,m=4時,(I+A+C)2=I,此時B=(I+A+C)2=I,Circ(O,A,B,C)是上的循環對合near-MDS矩陣.我們找到了12 組滿足條件的[A,C].

1.A=[4,3,2,1]C=[3,4,1,2]

2.A=[4,3,2,1]C=[2,1,4,3]

3.A=[4,3,2,1]C=[1,2,3,4]

4.A=[3,4,1,2]C=[4,3,2,1]

5.A=[3,4,1,2]C=[2,1,4,3]

6.A=[3,4,1,2]C=[1,2,3,4]

7.A=[2,1,4,3]C=[4,3,2,1]

8.A=[2,1,4,3]C=[3,4,1,2]

9.A=[2,1,4,3]C=[1,2,3,4]

10.A=[1,2,3,4]C=[4,3,2,1]

11.A=[1,2,3,4]C=[3,4,1,2]

12.A=[1,2,3,4]C=[2,1,4,3]