輕量級分組密碼S盒的優(yōu)化設(shè)計案例輕量級分組密碼S盒的優(yōu)化設(shè)計案例 1 11.2啟發(fā)式算法介紹 2 31.4S盒實現(xiàn)及優(yōu)化結(jié)果 4線性函數(shù)電路的門優(yōu)化已經(jīng)得到了廣泛的研究。結(jié)果表明，線性電路優(yōu)化問中取值，1和W是變量。為給定的函數(shù)f構(gòu)造一個線性)路等價于在GF(2上構(gòu)造一個計算f的線性直)程序(注意，在GF(2上，λ和μ總是1,因此)不顯示地寫入)。抵消變量，那么線性直線程序被認為是無取消的)以前關(guān)于S盒電路最小化的工作。只考慮在GF(2)上生成一組線性形式的無取消直線程)。一些研究者似乎提出了錯誤的假設(shè)，即總是存在G不難發(fā)現(xiàn)，反例中最優(yōu)無取消直線程序的長度為5。而還存在長度為4的解決2方案：在之后的優(yōu)化工作我們也將利用引入中間變量的方式，力求降低異或門數(shù)，以求獲得異或門數(shù)上的優(yōu)化，而啟發(fā)式算法是我們找到最小化異或門數(shù)的一個很1.2啟發(fā)式算法介紹定義M為二元域上m×n的常數(shù)矩陣，定義x為二元域上n個變量的常數(shù)向量。SLP的問題是找到行數(shù)最少的方式來計算Mx。在這里，程序在二元域中解決上述SLP等效于找到最短電路以僅使用XOR門來計算函數(shù)。因此，優(yōu)化S盒的線性部分的操作可以等同于上述SLP問題。因此，優(yōu)化S盒的啟發(fā)式算法可以解決如下問題：是中的每一行到的最小漢明距離，即D[i]=δ(S,f:l,其重減1。然后，我們執(zhí)行以下循環(huán)：3.重復(fù)過程1、2,直到所有的D[i]=0為止。這個啟發(fā)式方法中的距離向量是通過窮舉搜索來計算的。因此它適用于中等大小的矩陣，距離只能減小，并且實際上只能減少1。因此選擇新基礎(chǔ)元素的標準是選擇一個使新距離之和最小的元素。如果兩對基本此啟發(fā)式方法的距離向量是通過窮舉來實現(xiàn)的。因此，它適用于中型大小的矩陣。3之后，我們將以LED算法4×4S盒的優(yōu)化為例，敘述啟發(fā)式算法的優(yōu)化過程及其原理。1.3LED算法S盒優(yōu)化過程及原理1.將算法S盒優(yōu)化問題轉(zhuǎn)化成SLP問題實例。將SAT求解器求出的.solution文件里面涉及到的x的異或轉(zhuǎn)換成一個矩陣M,s代表X?,X2,X2,X△的集合。Ms則代表整個涉及x的solution算式。初始距離向量0b0011,program=(Cx{}’.format(i),")foriinrange(S[0].bit_length())]LED算法S盒優(yōu)化SLP實例轉(zhuǎn)化2.調(diào)用啟發(fā)式算法程序。算法要幫助我們從中找兩個基本向量，將這兩個向量之和添加到基本向量中時，會得到一個新的最小的距離向量。接下來就一直以這種思路進行。我們將列舉優(yōu)化的全過程。第一步：Wo=xn+x?,D=[1,0,1,1,0,1,1,3,1,1,2];第二步：W?=xo+x?,D=[1,0,1,0,0,1,0,2,1第三步：W?=x?+x?,D=[0,0,0,0,0,0,0,1,第四步：W?=x?+W?,D=[0,0,0,0,0,0,0,0,1第五步：Wa=x?+W?,D=[0,0,0,0,0,0,0,0,1第六步：W?=x?+x?,D=[04生成結(jié)果如圖1.3.2。[0b1000°,'0b100,'0b10’,'0b1’,'0b1010','0b1001',’06110','0b1110','0b1101’,'0b11’,'0b1012y7=xly6圖1.3.2LED算法S盒優(yōu)化變量x優(yōu)化結(jié)果3.將優(yōu)化結(jié)果代入初始算式中，并用同樣的方式優(yōu)化變量t,最后從圖4.3.2中31個異或門優(yōu)化得到圖1.3.3中24個異或門的如下結(jié)果。t3=96^q7