• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看

      ?

      構(gòu)造分支數(shù)為4的對合線性變換

      2010-09-25 05:55:38李瑞林
      通信技術(shù) 2010年8期
      關(guān)鍵詞:構(gòu)造方法分支移位

      李 平, 孫 兵, 李瑞林, 李 超

      (國防科技大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)系,湖南 長沙 410073)

      0 引言

      分組密碼的設(shè)計(jì)主要關(guān)注兩方面的性能,第一是算法本身的安全性,第二是算法的軟硬件實(shí)現(xiàn)效率。大多數(shù)分組密碼均采用SP輪函數(shù)的結(jié)構(gòu),文獻(xiàn)[1]研究了分組密碼S盒輸出分量函數(shù)的密碼學(xué)性質(zhì),文獻(xiàn)[2]研究了一類P置換的設(shè)計(jì)方法。P置換要實(shí)現(xiàn)盡可能高的擴(kuò)散性以抵抗差分線性等密碼攻擊手段,需要線性變換的分支數(shù)盡可能高。對合性質(zhì)能夠使得加解密完全一致,達(dá)到節(jié)省資源提高效率的目的。目前 AES,Camellia,F(xiàn)OX,SMS4等算法都使用了達(dá)到最優(yōu)分支數(shù)的線性變換,分支數(shù)均為5,但都不是對合的。為了能夠像Feistel型分組密碼一樣做到加解密一致,在擴(kuò)散層中采用對合型線性變換就非常必要,目前韓國密碼標(biāo)準(zhǔn)ARIA算法就采用了一個(gè)對合的線性變換作為其擴(kuò)散層,并且分支數(shù)達(dá)到了最優(yōu)。

      基于以上優(yōu)點(diǎn),設(shè)計(jì)盡可能好的分支數(shù)以及對合的線性變換是近來的熱點(diǎn)問題。由于異或運(yùn)算和循環(huán)移位易于實(shí)現(xiàn),結(jié)合這兩種技巧來設(shè)計(jì)線性變換的方法逐漸得到廣泛的應(yīng)用。中國設(shè)計(jì)的無線局域網(wǎng)中使用的SMS4算法就是采用這種方法設(shè)計(jì)的擴(kuò)散層[3]?,F(xiàn)在已有的研究基礎(chǔ)上,給出了三類達(dá)到次最優(yōu)分支數(shù)的對合型線性變換的構(gòu)造。

      1 基礎(chǔ)知識

      下面給出給出線性變換分支數(shù)以及對合的定義:

      B(L)=mX≠in0(W (X ) + W(L ( X)))。

      根據(jù)分支數(shù)的定義,可知, B (L)≤ m+1。特別地,當(dāng)B ( L ) = m+1時(shí),稱該線性變換為最優(yōu)線性變換;當(dāng) B ( L) = m時(shí),稱該線性變換為次最優(yōu)線性變換。

      現(xiàn)有的構(gòu)造最優(yōu)線性變換的方法包括如下一些方法:

      ①循環(huán)矩陣構(gòu)造[4],AES算法擴(kuò)散層基于該方法設(shè)計(jì)。文獻(xiàn)[4]指出,與一般的隨機(jī)矩陣相比,循環(huán)矩陣所對應(yīng)的線性變換達(dá)到最優(yōu)的概率更大。文獻(xiàn)[2]進(jìn)一步指出,如果還要求變換為對合變換,則這樣的對合型線性變換的分支數(shù)最大只能達(dá)到4;

      ②組合方法構(gòu)造[5],F(xiàn)OX算法擴(kuò)散層基于該方法設(shè)計(jì);

      ③Hadamard矩陣構(gòu)造,NESSIE計(jì)劃中提交的分組密碼算法Khazad[6]與Anubis[7]的擴(kuò)散層基于該方法設(shè)計(jì);

      ④Cauchy矩陣構(gòu)造[8]。

      除這幾種常見的構(gòu)造方法之外,利用循環(huán)移位和異或運(yùn)算也可以構(gòu)造分支數(shù)達(dá)到最優(yōu)的線性變換。假設(shè),用Xi表示將X循環(huán)左移i位,其中0 ≤ i≤ n m-1,則利用循環(huán)移位和異或運(yùn)算可以表示從的一類線性變換。文獻(xiàn)[9]給出了利用循環(huán)移位和異或運(yùn)算設(shè)計(jì)最優(yōu)線性變換時(shí)的一些條件這種方法特別適合于軟硬件的實(shí)現(xiàn),效率高。但是,已有的基于該構(gòu)造方法給出的最優(yōu)線性變換均不是對合變換。

      2 三種構(gòu)造次最優(yōu)對合線性變換的方法

      上一節(jié)中基于循環(huán)移位結(jié)合異或運(yùn)算的方法均是將X視為整體進(jìn)行循環(huán)移位和異或運(yùn)算,對X的分量進(jìn)行考慮,當(dāng) 4m= 時(shí),給出分支數(shù)達(dá)到4時(shí)的對合線性變換的三種構(gòu)造方法。

      證明:根據(jù)分支數(shù)的定義,必要性顯然。

      下面證明充分性,根據(jù)分支數(shù)的定義,只需按輸入X的重量來分別討論:

      首先根據(jù)條件輸入向量滿足 W (X)= 1,則輸出向量滿足W(Y)≥ 3 ;

      當(dāng)輸入向量滿足 W (X) = 2 時(shí),假設(shè)此時(shí)輸出 Y =L(X)的重量 W (Y)= 1 。由于L是對合的,可考慮其逆變換L-1=L,由已知條件可知 X =L-1(Y)的重量 W (X)≥ 3。與W(X) = 2 矛盾,故輸出 Y =L( X)的重量 W (Y)≥ 2 ;

      當(dāng)輸入向量滿足 W (X) = 3 時(shí),由于輸出是非零的,那么必有 W (Y)≥ 1。

      綜合以上3種情況,可知 B (L)≥ 4。

      則線性變換L滿足對合性質(zhì)且分支數(shù)為 B ( L ) = 4。

      證明:首先證明L的對合性,由L的定義:Y0⊕Y1⊕Y2⊕ Y3=X0⊕X1⊕X2⊕ X3, 故 T = ( X0⊕ X1⊕X2⊕ X3)i = (Y0⊕Y1⊕Y2⊕Y3)i ,又易知:

      從而L為對合變換。

      下面證明L的分支數(shù)為4,不妨設(shè)輸入 X = ( X0,0,0,0),X0≠ 0 ,則容易計(jì)算:

      可知, Y1≠0, Y2≠0, Y3≠ 0 ,故 W (Y)≥ 3;又由于L是對合的,由定理 1可知 B (L)≥ 4。另一方面,可設(shè)輸入X=(X0,0,0,0)中的 X0為全1向量,將其代入L的定義驗(yàn)證可知,輸出 Y =L( X)的重量 W (Y)= 3 ,由分支數(shù)定義,取所有可能的輸入輸出重量之和的最小值,故分支數(shù)為4。

      則線性變換L滿足對合性質(zhì)且分支數(shù)為 B ( L) = 4。

      證明:首先證明L的對合性,由L的定義,可做如下循環(huán)移位:并計(jì)算 Y0⊕(Y1i1) ⊕(Y2i2) ⊕ (Y3i3) ⊕ (Y0i4)可得:

      X0= Y0⊕ ( Y1i1) ⊕ ( Y2i2) ⊕ ( Y33) ⊕ (Y0i4),同理可得:

      從而L為對合變換。類似構(gòu)造1的證明可知L的分支數(shù)為4。

      則線性變換L的分支數(shù)為 B ( L) = 4,進(jìn)一步,當(dāng)n為偶數(shù)且i = n /2時(shí),L是對合變換。

      證明:首先證明L分支數(shù)為4,根據(jù)分支數(shù)的定義,只需按輸入X的重量來分別討論:

      (1)當(dāng)輸入X的重量 W (X)= 1時(shí),輸出 Y =L ( X)的重量 W (Y)≥ 3;

      不妨設(shè)輸入 X = ( X0,0,0,0), X0≠ 0 ,則容易計(jì)算:

      可知, Y1≠ 0 , Y2≠0, Y3≠ 0 ,故 W (Y)≥ 3 。

      (2)當(dāng)輸入X的重量 W (X) = 2 時(shí),輸出 Y =L ( X)的重量 W (Y)≥ 2 ;

      不妨設(shè)輸入 X = ( X0, X1,0,0), X0≠0, X1≠0,則容易計(jì)算:

      若 X0⊕X1=0,則Y0≠0, Y1≠0,此時(shí)W(Y)= 2 ;若X0⊕X1≠0,則Y2≠0, Y3≠0,此時(shí)W(Y)≥ 2 。從而當(dāng)W(X) = 2 時(shí), W (Y)≥ 2 。

      當(dāng)輸入X的重量 W (X)= 3 時(shí),輸出非零,所以必有W(Y)≥ 1;綜上并且注意到(2)中存在輸出 W (Y)=2的情況,由于分支數(shù)的定義,故 B ( L ) = 4。

      下面證明當(dāng)n為偶數(shù)且 i = n /2時(shí),L是對合的:由Y0⊕Y1⊕Y2⊕ Y3= ( X0⊕X1⊕ X2⊕X3)i ,故 T = X0⊕ X1⊕X2⊕ X3=( Y0⊕Y1⊕Y2⊕Y3)■ i ,則:

      令T'= Y0⊕Y1⊕Y2⊕Y3,則 Ti =T '2 i,從而:

      當(dāng)n為偶數(shù)且 /2i n= 時(shí),有2i n= ,此時(shí):

      故:

      這表明L為對合變換。

      3 結(jié)語

      介紹了分支數(shù)較好的對合型線性變換在密碼算法中的重要作用,以及主要的構(gòu)造方法。研究了如何利用循環(huán)移位和異或運(yùn)算構(gòu)造從的線性變換,使得分支數(shù)達(dá)到次最優(yōu),并且是對合的。給出了三種具體的構(gòu)造方法,并分別給出了證明。進(jìn)一步需要研究,在利用這幾類線性變換作為擴(kuò)散層組件時(shí),密碼算法是否能夠有效地抵抗各種密碼分析方法,尤其是截?cái)嗖罘置艽a分析。同時(shí),利用提出的設(shè)計(jì)方法能否找到分支數(shù)達(dá)到最優(yōu)的線性變換也是下一步繼續(xù)研究的課題。

      [1] 李強(qiáng),李超.Camellia算法中S盒輸出分量函數(shù)的等價(jià)表示[J].通信技術(shù),2008,41(11):126-128.

      [2] 王念平,金晨輝,余昭平.對合型列混合變換的研究[J].電子學(xué)報(bào),2005,33(10):1917-1920.

      [3] 國家商用密碼管理辦公室.無線局域網(wǎng)產(chǎn)品使用的 SMS4密碼算法[EB/OL].(2005-02-05).[2010-01-10].http://www.oscca.gov.cn/UpFile/200621016423197990.pdf.

      [4] DAEMEN J, KNUDSEN L R, RIJMEN V. The Block Cipher Square[C]//FSE 1997, LNCS 1267. Springer-Verlag, Berlin, 1997: 149-165.

      [5] PASCAL J, SERGE V. Pergect Diffusion Primitives for Block Ciphers Building Efficient MDS Matrices[C]// SAC 2004, LNCS 3357. Berlin:Springer-Verlag,2005: 84-99.

      [6] BARRETO P, RIJMEN V. The Khazad Legacy-level Block Cipher[EB/OL]. (2000-11-13) [2010-01-10]. http://www.crypt onessie.org.

      [7] BARRETO P, RIJMEN V.The Anubis Block Cipher[EB/OL].(2000-11-13).[2010-01-10]. http://www.cryptonessie.org.

      [8] WILLIAMS F M, SLOANE N. The Theory of Error-Correcting Codes[M].Holland:North-Holland Pub. Co.,1977.

      [9] 王金波.基于循環(huán)移位構(gòu)造最優(yōu)線性變換[C]//密碼學(xué)進(jìn)展——中國密碼學(xué)會 2007年會論文集.成都:西南交通大學(xué)出版社,2007:306-307.

      猜你喜歡
      構(gòu)造方法分支移位
      DC-DC變換器分層級構(gòu)造方法
      再生核移位勒讓德基函數(shù)法求解分?jǐn)?shù)階微分方程
      巧分支與枝
      大型總段船塢建造、移位、定位工藝技術(shù)
      Σ(X)上權(quán)移位算子的不變分布混沌性
      一類擬齊次多項(xiàng)式中心的極限環(huán)分支
      《夢溪筆談》“甲子納音”構(gòu)造方法的數(shù)學(xué)分析
      幾乎最佳屏蔽二進(jìn)序列偶構(gòu)造方法
      多指離斷手指移位再植拇指25例
      生成分支q-矩陣的零流出性
      巴楚县| 潢川县| 固始县| 呼伦贝尔市| 噶尔县| 班戈县| 古田县| 新密市| 潮州市| 通渭县| 环江| 安顺市| 乌鲁木齐市| 康平县| 巧家县| 保靖县| 静乐县| 西盟| 犍为县| 江达县| 广丰县| 济宁市| 吉林省| 长垣县| 桂东县| 建德市| 佛冈县| 平潭县| 清远市| 拜城县| 聂拉木县| 焦作市| 新河县| 孟津县| 重庆市| 宜兴市| 塘沽区| 贵州省| 抚顺市| 神池县| 海伦市|