亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        SPECK算法的不可能差分分析*

        2019-04-24 08:24:38李明明郭建勝
        關(guān)鍵詞:明文區(qū)分復(fù)雜度

        李明明,何 駿,郭建勝

        (1.信息工程大學(xué),河南 鄭州 450001;2.鄭州信大捷安移動(dòng)信息安全關(guān)鍵技術(shù)國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室,河南 鄭州 450004)

        0 引言

        2013年美國(guó)提出SPECK和SIMON兩類超輕量分組密碼算法[1]。其中SPECK算法整體采用變形Feistel結(jié)構(gòu),有著突出的軟件實(shí)現(xiàn)性能。SPECK算法輪函數(shù)采用ARX模塊,由循環(huán)移位、異或、模整數(shù)加法運(yùn)算,其中模整數(shù)加法是主要非線性運(yùn)算。SPECK算法自從提出以來(lái),就受到密碼學(xué)界的廣泛關(guān)注,對(duì)于SPECK系列算法目前有多個(gè)安全性分析結(jié)果[2-10]。

        不可能差分分析由KNUDSEN L[11]和BIHAM F[12]兩人分別獨(dú)立提出,是目前最常用的密碼分析方法之一。對(duì)一個(gè)密碼算法進(jìn)行不可能差分的首要任務(wù)在于尋找概率為0的差分路徑,即不可能差分區(qū)分器。其次,基于得到的不可能差分區(qū)分器,篩去錯(cuò)誤密鑰,進(jìn)而確定正確密鑰。

        LEE H等人[13]利用MILP搜索技術(shù),對(duì)輸入差分和輸出差分僅含一個(gè)非零比特的情況進(jìn)行搜索,找到了SPECK64算法的一些6輪不可能差分區(qū)分器。徐洪[14]等人通過分析模加法運(yùn)算的差分?jǐn)U散性質(zhì),找到了SPECK32/64和SPECK48/96算法的一些6輪不可能差分區(qū)分器,并給出SPECK32/64和SPECK48/96算法的10輪不可能差分分析。李明明等人[15]利用徐洪等人給出的模整數(shù)加法差分?jǐn)U散性質(zhì),分析SPECK系列算法的加密方向與解密方向的差分?jǐn)U散規(guī)律,從而證明了在該性質(zhì)下SPECK系列算法的不可能差分區(qū)分器至多6輪,并給出了所有6輪不可能差分區(qū)分器;此外,Li Mingming等[16]進(jìn)一步給出模整數(shù)加法差分?jǐn)U散的補(bǔ)充性質(zhì),構(gòu)造了SPECK32/64和SPECK48/96算法7輪不可能差分區(qū)分器,并給出了它們的11輪不可能差分分析。但到目前為止,還沒有SPECK2n(2n=64,96,128)算法的不可能差分分析結(jié)果。如果能夠給出SPECK2n(2n=64,96,128)算法的不可能差分分析,則對(duì)于完善該算法的安全性分析理論具有重要的意義。

        本文分析了SPECK2n(2n=64,96,128)算法在不可能差分分析下的安全性。首先通過分析模加法差分的擴(kuò)散性質(zhì),找到了SPECK2n(2n=64,96,128)算法的7輪不可能差分區(qū)分器。其次,基于找到的7輪不可能差分區(qū)分器,給出了SPECK64/128算法和SPECK128/256算法的11輪不可能差分分析,以及SPECK 96/144算法的10輪不可能差分分析,恢復(fù)了全部主密鑰。

        1 SPECK算法介紹

        本節(jié)主要對(duì)文章里出現(xiàn)的符號(hào)進(jìn)行說(shuō)明及介紹SPECK算法的基本知識(shí)。首先給出符號(hào)說(shuō)明如下。

        xi:第i輪輸入的左半分組;

        yi:第i輪輸入的右半分組;

        Δxi[j]:Δxi的第j比特;

        >>>α:循環(huán)右移α比特;

        <<<β:循環(huán)左移β比特;

        Ki:第i輪子密鑰;

        +:模2n加;

        *:不確定的比特差分。

        SPECK算法是美國(guó)于2013年提出的輕量級(jí)分組密碼算法,采用變形Feistel結(jié)構(gòu)。該算法輪函數(shù)由循環(huán)移位、異或、模2n整數(shù)加法運(yùn)算組成,即ARX模塊。其輪函數(shù)如圖1所示。

        圖1 SPECK系列算法輪函數(shù)

        用SPECK 2n/mn來(lái)表示分組長(zhǎng)度為2nbit,密鑰長(zhǎng)度為mnbit的SPECK算法,其中n∈{16,24,32,48,64},m∈{2,3,4}。其密鑰擴(kuò)展算法如下。

        密鑰擴(kuò)展算法記算法主密鑰K=(Lm-2,Lm-3,…,L0,K0),其中K0,Li∈{0,1}n,m為各算法密鑰塊的數(shù)量,m∈{2,3,4},如SPECK128/128算法中m=2,SPECK128/192算法中m=3,SPECK128/256算法中m=4。擴(kuò)展算法為:

        輸出N個(gè)子密鑰K0,K1,…,Kn-1。若已知任意個(gè)相鄰的輪密鑰Ki,…,Ki-m+1,便可恢復(fù)主密鑰。SPECK算法各版本及相關(guān)參數(shù)值如表1所示。

        表1 SPECK系列算法版本

        2 SPECK2n(2n=64,96,128)算法的7輪不可能差分區(qū)分器

        首先,介紹徐洪等人給出的模整數(shù)加法的差分?jǐn)U散性質(zhì),如性質(zhì)1所示。

        性質(zhì)1[14]z=x+y(mod2n)為n比特?cái)?shù)的模加法運(yùn)算,令Δx=x⊕x′=(Δx[n-1],Δx[n-2],…,Δx[0]),Δy=y⊕y′=(Δy[n-1],Δy[n-2],…,Δy[0])分別為輸入x,y的異或差分,Δz=z⊕z′=(x+y)mod2n⊕(x′+y′)mod2n=(Δz[n-1],Δz[n-2],…,Δz[0])為輸出z的差分,設(shè)l1=min{k|Δx[k]=1},l2=min{k|Δy[k]=1},l=min{l1,l2},則:

        (1)若l1=l2=l,則Δz[l]=Δz[l-1]=…=Δz[0]=0,而當(dāng)l+1≤i≤n-1時(shí),Δz[i]=*。

        (2)若l1≠l2,則Δz[l]=1,Δz[l-1]=…=Δz[0]=0,而當(dāng)l+1≤i≤n-1時(shí),Δz[i]=*。

        李明明等利用徐洪等人給出的模整數(shù)加法的差分?jǐn)U散性質(zhì),通過分析SPECK2n(2n=64,96,128)算法的加密方向與解密方向的差分?jǐn)U散規(guī)律,證明了在該性質(zhì)下SPECK系列算法的不可能差分區(qū)分器至多6輪,給出了許多SPECK2n(2n=64,96,128)的6輪不可能差分區(qū)分器,如式(1)~式(4)所示。

        (1)

        (2)

        (3)

        (4)

        但徐洪等人給出的模整數(shù)加法差分?jǐn)U散性質(zhì)是一個(gè)必要不充分命題,Li Mingming等[16]進(jìn)一步給出模整數(shù)加法差分?jǐn)U散的補(bǔ)充性質(zhì),如性質(zhì)2所示。

        證明設(shè)x=(x[n-1],x[n-2],…,x[0]),y=(y[n-1],y[n-2],…,y[0]),輸出z=(z[n-1],z[n-2],…,z[0]),進(jìn)位c=(c[n-1],c[n-2],…,c[0]),則有

        z[i]=x[i]⊕y[i]⊕c[i-1],c[i]=x[i]y[i]⊕x[i]c[i-1]⊕y[i]c[i-1],1≤i≤n-1

        其中z[0]=x[0]⊕y[0],c[0]=x[0]y[0]。所以第i比特的輸出差分值Δz[i]=Δx[i]⊕Δy[i]⊕Δc[i-1]。

        證畢。

        利用性質(zhì)1和性質(zhì)2,可構(gòu)造SPECK2n(2n=64,96,128)算法的7輪不可能差分區(qū)分器。如定理1所示。

        定理1當(dāng)初始輸入狀態(tài)差分滿足(Δx1,Δy1)=(0000000000000010,0000010000000000)且x1[1]≠y1[10]時(shí),經(jīng)7輪SPECK32算法加密后輸出狀態(tài)差分滿足(Δx8,Δy8)=(10000000 00000000,1000000000000010)是不可能的。

        證明因?yàn)閤1[1]≠y1[10],令r1=x1>>>7,則r1[10]≠y1[10]。又因?yàn)閤2=((x1>>>7)+y1)⊕K1,則x2=(r1+y1)⊕K1,由性質(zhì)2可知初始輸入狀態(tài)(x1,y1)經(jīng)1輪SPECK32/64算法加密后輸出差分Δx2=(0000000000000000),故Δy2=Δx2⊕(Δy1<<<2)=(0001000000000000);再由性質(zhì)1可知,(x2,y2)再經(jīng)過2輪SPECK32算法加密后輸出狀態(tài)差分滿足Δz4[5]=1。

        而差分滿足(Δx8,Δy8)=(1000000000000000,1000000000000010)的狀態(tài)(x8,y8)經(jīng)4輪SPECK32算法解密后輸出狀態(tài)Δz4[5]=0。故矛盾。

        證畢。

        以SPECK64算法為例,選取其中一條7輪不可能差分區(qū)分器給出具體形式,如圖2所示。

        3 SPECK2n算法的11輪不可能差分分析

        本節(jié)首先詳細(xì)給出SPECK64/128算法的11輪不可能差分攻擊過程;其次,利用相同的方法簡(jiǎn)要給出SPECK96/144算法的10輪不可能差分分析結(jié)果以及SPECK128/256算法的11輪不可能差分分析結(jié)果。

        3.1 SPECK64/128算法的11輪不可能差分分析

        利用圖2給出的SPECK64算法7輪不可能差分區(qū)分器,向上擴(kuò)展1輪,向下擴(kuò)展3輪可得其11輪不可能差分路徑,如圖3所示。并結(jié)合密鑰分割攻擊及時(shí)空折中技術(shù)給出SPECK64/128算法的11輪不可能差分攻擊如下。

        (1)選擇2n個(gè)明文結(jié)構(gòu),其中的明文滿足x0[8,9],y0取定值,其余比特取任意值,故一個(gè)明文結(jié)構(gòu)包含230個(gè)明文,可以構(gòu)造259個(gè)明文對(duì)。因此攻擊的選擇明文量為2n+30,其中包含2n+59個(gè)明文對(duì)。

        圖2 SPECK64算法的7輪不可能差分區(qū)分器

        (3)猜測(cè)第11輪子密鑰K10。對(duì)于剩余的明文對(duì),篩選出差分(Δx10,Δy10)滿足Δt9[3,4,5]=(000)的數(shù)據(jù)對(duì),其中Δt9=Δx10⊕Δy10,y10=(x11⊕y11)>>>3,x10=((x11⊕K10)+y10)<<<8,經(jīng)這一步過濾大約

        圖3 SPECK64算法的11輪不可能差分路徑

        定理2若并行利用15條7輪不可能差分區(qū)分器對(duì)10輪SPECK64/128算法進(jìn)行不可能差分分析,恢復(fù)128比特主密鑰,其時(shí)間復(fù)雜度為2127.65次10輪SPECK64算法加密,數(shù)據(jù)復(fù)雜度為264個(gè)選擇明文,存儲(chǔ)復(fù)雜度為2116個(gè)SPECK64狀態(tài)。

        證明上述攻擊過程中,時(shí)間復(fù)雜度主要由第6步?jīng)Q定。經(jīng)第6步排除錯(cuò)誤密鑰后大約剩余ε=296×(1-2-29)2n-7個(gè)候選密鑰,再對(duì)候選密鑰和剩余32比特密鑰進(jìn)行窮舉恢復(fù)密鑰的時(shí)間復(fù)雜度為ε×232。當(dāng)n=34時(shí),11輪SPECK64算法不可能差分分析總時(shí)間復(fù)雜度為2n+90/11+ε×232=2n+90/11+296×(1-2-29)2n-7×232≈2127.65次11輪SPECK64算法加密,數(shù)據(jù)復(fù)雜度為250.89個(gè)選擇明文。此外,存儲(chǔ)復(fù)雜度主要由第4步?jīng)Q定,大約為232×227×2n+22×2≈2116個(gè)SPECK64狀態(tài)。

        若同時(shí)使用定理1給出的全部15條SPECK64算法的7輪不可能差分區(qū)分器,總時(shí)間復(fù)雜度可進(jìn)一步降低。使用264個(gè)選擇明文,此時(shí)錯(cuò)誤率降為(1-2-29)227×15,總的時(shí)間復(fù)雜度約為15×2124/11+2128×(1-2-29)227×15≈2124.80次11輪SPECK 64算法加密,存儲(chǔ)復(fù)雜度約為2116×15=2119.91個(gè)SPECK64狀態(tài)。

        證畢。

        3.2 SPECK96/144算法的10輪不可能差分分析

        利用定理1給出的SPECK2n(2n=64,96,128)算法的7輪不可能差分區(qū)分器,任選其中一條作為SPECK96的不可能差分區(qū)分器。在該區(qū)分器基礎(chǔ)上向上擴(kuò)展1輪,向下擴(kuò)展2輪得到10輪不可能差分路徑,并結(jié)合密鑰分割攻擊及時(shí)空折中技術(shù)可以給出SPECK96/192算法的10輪不可能差分攻擊,攻擊過程中需要猜測(cè)96比特密鑰,選擇明文數(shù)量為296,時(shí)間復(fù)雜度約為2143.66次10輪加密,存儲(chǔ)復(fù)雜度約為2133個(gè)SPECK96狀態(tài)。

        若同時(shí)使用定理1中給出的其中15條SPECK96算法7輪不可能差分區(qū)分器,總時(shí)間復(fù)雜度可進(jìn)一步降低。使用296個(gè)選擇明文,此時(shí)錯(cuò)誤率降為(1-2-45)243×15,總的時(shí)間復(fù)雜度約為15×2140/11+2144×(1-2-45)243×15≈2140.91次10輪SPECK96算法加密,存儲(chǔ)復(fù)雜度約為2133×15=2136.91個(gè)SPECK96狀態(tài)。

        3.3 SPECK128/256算法的11輪不可能差分分析

        利用定理1給出的SPECK2n(2n=64,96,128)算法的7輪區(qū)分器,任選其中一條作為SPECK128算法的不可能差分區(qū)分器。在該區(qū)分器基礎(chǔ)上向上擴(kuò)展1輪,向下擴(kuò)展3輪得到11輪不可能差分路徑,并結(jié)合密鑰分割攻擊及時(shí)空折中技術(shù)可以給出SPECK128/256算法的11輪不可能差分攻擊,攻擊過程中需要猜測(cè)192比特密鑰,選擇明文數(shù)量為2128,時(shí)間復(fù)雜度約為2192×259×2/11+2192×(1-2-61)259×264≈2192×259×2/11+2192×e-2-2×264≈2255.65次11輪加密,存儲(chǔ)復(fù)雜度約為2244個(gè)SPECK128狀態(tài)。

        若同時(shí)使用16條SPECK128算法7輪不可能差分區(qū)分器,總時(shí)間復(fù)雜度可進(jìn)一步降低。使用2128個(gè)選擇明文,此時(shí)錯(cuò)誤率降為(1-2-61)259×16,總的時(shí)間復(fù)雜度約為16×2252/11+2256×(1-2-61)259×16≈16×2252/11+2256×e-4≈2252.81次11輪SPECK128算法加密,存儲(chǔ)復(fù)雜度約為2244×16=2248個(gè)SPECK128狀態(tài)。

        4 結(jié)論

        本文通過分析模加法差分的擴(kuò)散性質(zhì),找到了SPECK2n(2n=64,96,128)算法的7輪不可能差分區(qū)分器。并基于該區(qū)分器,給出了SPECK64/128算法和SPECK128/256算法的11輪不可能差分分析,以及SPECK 96/144算法的10輪不可能差分分析,恢復(fù)了全部主密鑰。這些分析結(jié)果表明,SPECK算法具有較強(qiáng)抵抗不可能差分攻擊的能力。下一步將對(duì)其他ARX結(jié)構(gòu)分組密碼算法的不可能差分分析進(jìn)行研究。

        猜你喜歡
        明文區(qū)分復(fù)雜度
        區(qū)分“旁”“榜”“傍”
        你能區(qū)分平衡力與相互作用力嗎
        一種低復(fù)雜度的慣性/GNSS矢量深組合方法
        奇怪的處罰
        教你區(qū)分功和功率
        求圖上廣探樹的時(shí)間復(fù)雜度
        奇怪的處罰
        某雷達(dá)導(dǎo)51 頭中心控制軟件圈復(fù)雜度分析與改進(jìn)
        四部委明文反對(duì)垃圾焚燒低價(jià)競(jìng)爭(zhēng)
        一区二区三区精彩视频在线观看| 麻豆国产人妻欲求不满谁演的| 欧美人与物videos另类xxxxx| 高清高速无码一区二区| 日本一区二区视频免费在线观看| 欧美群妇大交群| 亚洲一本到无码av中文字幕| 亚洲欧洲精品国产二码| 亚洲综合网中文字幕在线| 男女交射视频免费观看网站| 无人高清电视剧在线观看| 久久久男人天堂| 成人精品国产亚洲av久久| 青青草国产手机观看视频| 天天综合网在线观看视频| 国产成人精品午夜福利在线| 国产免费人成网站在线播放| 蜜臀av一区二区三区免费观看 | 18禁黄久久久aaa片| 亚洲最大成av人网站| 一本久道在线视频播放| 人妖一区二区三区四区| 在线亚洲+欧美+日本专区| 啪啪视频一区二区三区入囗| 亚洲av色香蕉一区二区三区软件| 国产大屁股视频免费区| 亚洲精品久久国产高清情趣图文| 天堂69亚洲精品中文字幕| 国产夫妻精品自拍视频| 一本精品99久久精品77| 国内露脸中年夫妇交换| 国产一区二区三区亚洲精品| 中文字幕一区二区三区的| 天天综合网天天综合色| 超碰日韩AV在线| 亚洲肥婆一区二区三区| 中文字幕一精品亚洲无线一区| 亚洲日韩乱码中文无码蜜桃臀| 亚洲乱码中文字幕综合| 蜜桃视频免费进入观看| 亚洲国产长腿丝袜av天堂 |