類Piccolo 結(jié)構(gòu)的差分安全性評(píng)估

王念平，殷勍

（1.信息工程大學(xué)密碼工程學(xué)院，河南 鄭州 450004；2.航天工程大學(xué)，北京 101416）

0 引言

分組密碼作為現(xiàn)代密碼學(xué)的重要組成部分，在信息安全領(lǐng)域有著廣泛的應(yīng)用。分組密碼具有易于標(biāo)準(zhǔn)化、便于軟硬件實(shí)現(xiàn)和容易同步等優(yōu)點(diǎn)[1-2]，但也有一定的缺陷。例如，分組密碼不能隱蔽數(shù)據(jù)模式，即相同的密文蘊(yùn)含著相同的明文組，這是因?yàn)榉纸M密碼使用的是一個(gè)不隨時(shí)間變化的固定變換。同時(shí)，分組密碼不能抵抗組的重放、嵌入和刪除等攻擊。但上述的缺陷可以通過(guò)在加密過(guò)程中引入少量記憶加以克服，例如，可以通過(guò)密碼分組鏈接（CBC,cipher block chaining）方式來(lái)克服[2-3]。另外，分組密碼的安全性很難被證明。盡管“可證明安全性”的研究發(fā)展很快，但目前的分組密碼大多是“看起來(lái)安全”的，還沒(méi)有哪一個(gè)著名的分組密碼真正被證明是安全的，至多證明了局部安全性。

對(duì)于分組密碼，目前還存在一些問(wèn)題值得考慮。一是分組密碼算法的標(biāo)準(zhǔn)化。分組密碼的大量社會(huì)化應(yīng)用呼喚密碼算法的標(biāo)準(zhǔn)化。二是分組密碼設(shè)計(jì)和分析理論的研究。作為分組密碼的研究者，總是希望從理論上解釋一些設(shè)計(jì)方法的合理性，并將一些分析方法理論化，而不僅僅是停留在設(shè)計(jì)經(jīng)驗(yàn)和直觀分析的層次上。例如在一定假設(shè)條件下的可證明安全性和偽隨機(jī)性常常是研究者追求的一個(gè)目標(biāo)。三是分組密碼安全性分析的自動(dòng)化。這是計(jì)算機(jī)技術(shù)與密碼分析的有機(jī)結(jié)合。將一些密碼分析方法程序化，往往可以提升分析的深度，彌補(bǔ)手工分析的不足。四是分組密碼算法評(píng)估的實(shí)用化。算法的評(píng)估不僅要考慮在傳統(tǒng)數(shù)學(xué)模型下的安全性，還應(yīng)結(jié)合實(shí)現(xiàn)和應(yīng)用環(huán)境評(píng)估算法的安全性，例如在側(cè)信道模型下的安全性。本文的研究屬于第二項(xiàng)內(nèi)容。事實(shí)上，分組密碼的整體結(jié)構(gòu)對(duì)分組密碼的安全性有很大影響。因此，研究分組密碼結(jié)構(gòu)的安全性一直是分組密碼研究領(lǐng)域的重要內(nèi)容。

差分密碼分析[4]是一種典型的分組密碼分析方法。差分密碼分析能否成功主要取決于所利用的差分特征概率的大小。文獻(xiàn)[5]指出，在最大差分特征概率足夠小的情況下，就認(rèn)為該密碼算法對(duì)差分密碼分析是免疫的。但在現(xiàn)實(shí)中，計(jì)算最大差分特征概率有一定的困難，且較難實(shí)現(xiàn)，所以就退而求其次——計(jì)算最大差分特征概率的上界，而最大差分特征概率的上界的計(jì)算取決于活動(dòng)輪函數(shù)或活動(dòng)S盒個(gè)數(shù)的下界。需要指出的是，在計(jì)算差分特征的活動(dòng)輪函數(shù)或活動(dòng)S 盒個(gè)數(shù)的下界時(shí)，一般并不考慮輪函數(shù)和S 盒的具體細(xì)化結(jié)構(gòu)，而只是假設(shè)它們是雙射的即可，從而所得的結(jié)果更具普遍性。文獻(xiàn)[6-9]就是基于這樣的思路進(jìn)行分析的。

Piccolo 結(jié)構(gòu)[10-11]是從Piccolo 算法[12]中歸結(jié)出來(lái)的一種密碼結(jié)構(gòu)，如圖1 所示。其設(shè)計(jì)特點(diǎn)在于塊移位變換RP 不直接對(duì)4 個(gè)分塊Y0、Y1、Y2、Y3進(jìn)行移位，而是對(duì)平均分成的8 個(gè)子分塊進(jìn)行移位。文獻(xiàn)[10]研究了Piccolo結(jié)構(gòu)抵抗差分密碼分析的能力，證明了k(k≥ 1)輪差分特征至少有k-1個(gè)活動(dòng)輪函數(shù)和(n+1)(k-1)個(gè)活動(dòng)S 盒（n+1是輪函數(shù)中P 變換的差分分支數(shù)）。文獻(xiàn)[11]改進(jìn)了文獻(xiàn)[10]中的結(jié)果，證明了k(k≥ 6)輪差分特征至少有k個(gè)活動(dòng)輪函數(shù)和(n+1)k個(gè)活動(dòng)S 盒，并指出活動(dòng)輪函數(shù)個(gè)數(shù)的下界結(jié)果是不可改進(jìn)的，所謂不可改進(jìn)，是指確實(shí)存在一類差分特征，其活動(dòng)輪函數(shù)的個(gè)數(shù)恰好達(dá)到了給出的下界。本文在此基礎(chǔ)上，提出32 種類Piccolo 結(jié)構(gòu)（包括文獻(xiàn)[10-11]中的Piccolo 結(jié)構(gòu)），并對(duì)這些類Piccolo 結(jié)構(gòu)進(jìn)行了差分密碼分析，給出了活動(dòng)輪函數(shù)和活動(dòng)S 盒個(gè)數(shù)的一個(gè)下界。

圖1 Piccolo 結(jié)構(gòu)

本文的結(jié)果與文獻(xiàn)[10-11]相比，改進(jìn)之處在于文獻(xiàn)[10-11]只是針對(duì)Piccolo 結(jié)構(gòu)這一種密碼結(jié)構(gòu)進(jìn)行分析的，而本文是針對(duì)提出的32 種類Piccolo結(jié)構(gòu)進(jìn)行分析的。本文的結(jié)果比文獻(xiàn)[10]中的結(jié)果要好，比文獻(xiàn)[11]中的結(jié)果更具一般性。

1 預(yù)備知識(shí)

1.1 基本概念

定義1[13]設(shè)(X,+)和(Y,+)都是有限交換群，f:X→Y,α∈X,β∈Y，差分概率p f(α→β)定義為

其中，“| · |”和“#{·} ”表示集合的基數(shù)。

定義2[1]r(r≥ 1)輪差分特征Ω是一個(gè)差分序列α0,α1,…,α r，其中α0是明文對(duì)Y0和的差分，αi(1≤i≤r)是第i輪輸出Yi和的差分。

定義3[14]輸入差分非零的輪函數(shù)（S 盒），稱為活動(dòng)輪函數(shù)（S 盒）。

定義4r(r≥1) 輪差分特征中活動(dòng)輪函數(shù)的個(gè)數(shù)稱為該差分特征的活動(dòng)指標(biāo)。

本文稱r(r≥1) 輪差分特征的活動(dòng)指標(biāo)為r(r≥1) 輪Piccolo 結(jié)構(gòu)的活動(dòng)指標(biāo)。本文中，將n元塊移位變換簡(jiǎn)記為 (i0i1···in-1)，它表示按從左到右的順序?qū)⒃瓉?lái)第ij個(gè)分塊aij移動(dòng)到第j(j=0,1,…,n-1)個(gè)分塊的位置，即

1.2 類Piccolo 結(jié)構(gòu)描述

圖2 類Piccolo 結(jié)構(gòu)

表1 集合A

表1 中，8 元塊移位變換 (i0i1···i7)表示移位變換（下同）。

1) 輪函數(shù)f0,1f

如圖3 所示，輪函數(shù)f0,1f都采用SPS 結(jié)構(gòu)，這里S 表示n個(gè)m×m雙射S 盒（n為偶數(shù)且nm=t，t為輸入塊X i(i=0,1,2,3)的比特?cái)?shù)），P 表示的線性變換x→Mx，M表示有限域GF(2m) 上的n階MDS 矩陣。易知，P 變換的分支數(shù)（包括差分分支數(shù)和線性分支數(shù)[13]）為(n+1)，且輪函數(shù)f0,1f都是雙射。

圖3 輪函數(shù)

2) 塊移位變換σ

集合A中的8 元塊移位變換是滿足以下2 個(gè)條件的置換。

條件1ij∈{2,3,6,7},j=0,1,4,5；ik∈{0,1,4,5},k=2,3,6,7。

形象地說(shuō)，滿足條件1的σ如圖4 所示，即i j(j=0,1,4,5)只能從 {2,3,6,7} 中選取，ik(k=2,3,6,7)只能從{0,1,4,5}中選取。

圖4 滿足條件1的σ

形象地說(shuō)，滿足條件2的σ如圖5 所示，即將每個(gè)大塊2i2i+1 中的2 個(gè)小塊2i和2i+1 分別移位到不同的大塊中去。

圖5 滿足條件2的σ

條件1 和條件2 共同保證了類Piccolo 結(jié)構(gòu)的擴(kuò)散效果。

備注1為了敘述方便，將塊移位變換是σ的類Piccolo 結(jié)構(gòu)稱為σ-Piccolo 結(jié)構(gòu)。

2 類Piccolo 結(jié)構(gòu)的活動(dòng)輪函數(shù)和活動(dòng)S 盒個(gè)數(shù)的下界

為了分析方便，將X i(i=0,1,2,3)看成由左右規(guī)模相等的兩部分x2i和x2i+1連接而成，即X0=x0||x1,X1=x2||x3,X2=x4||x5,X3=x6||x7，其中“||”表示比特塊的連接。那么，類Piccolo 結(jié)構(gòu)的輸入就可表示為(x0||x1,x2||x3,x4||x5,，一輪類Piccolo 結(jié)構(gòu)（略去子密鑰）的輸入和輸出關(guān)系式就可表示為

首先，給出σ-Piccolo 結(jié)構(gòu)的差分對(duì)應(yīng)的結(jié)構(gòu)形式。

定理1對(duì)任一σ-Piccolo 結(jié)構(gòu)，設(shè)具有非零概率的一輪差分對(duì)應(yīng)都具有如下形式

證畢。

由定理1，可得以下事實(shí)。

引理2對(duì)于任一σ-Piccolo 結(jié)構(gòu)，以下3 個(gè)結(jié)論成立。

結(jié)論1一輪Piccolo 結(jié)構(gòu)的活動(dòng)指標(biāo)大于或等于0。

結(jié)論22 輪Piccolo 結(jié)構(gòu)的活動(dòng)指標(biāo)大于或等于1。

結(jié)論33 輪Piccolo 結(jié)構(gòu)的活動(dòng)指標(biāo)大于或等于2。

證明1) 結(jié)論1 顯然成立，只證結(jié)論2 和結(jié)論3。

由備注2 知，活動(dòng)指標(biāo)與最后一輪輸出差分無(wú)關(guān)，從而為書寫方便，有時(shí)將差分特征的最后一輪輸出差分記為(* || *,* || *,* || *,* || *) 。

2) 由定理1，設(shè)σ-Piccolo 結(jié)構(gòu)的2 輪差分特征為

3) 由定理1，設(shè)σ-Piccolo 結(jié)構(gòu)的3 輪差分特征為

綜合情形1 和情形2，引理2 成立。證畢。

接下來(lái)，設(shè)(α0||α1,α2||α3,α4||α5,α6||α7)是σ-Piccolo 結(jié)構(gòu)的輸入差分。若差分塊αi為非零差分塊，則用“1”表示；若差分塊αi為零差分塊，則用“0”表示，其中i=0,1,2,…,7。那么，σ-Piccolo結(jié)構(gòu)的非零輸入差分恰好有28-1=255 種表示，即Δ1=(10000000),Δ2=(01000000),…,Δ255=(11111111)（這種表示方法不妨稱為“0”“1”表示）。易知，f0為活動(dòng)輪函數(shù)當(dāng)且僅當(dāng)左起第1、2 位不全為零，f1為活動(dòng)輪函數(shù)當(dāng)且僅當(dāng)左起第5、6 位不全為零。

首先，給出輸入輸出差分塊“0”“1”進(jìn)行XOR運(yùn)算需要滿足的運(yùn)算規(guī)則：設(shè)a,b,c,d∈{0,1}分別是按照上述方法的“0”“1”表示，且設(shè)“∧”是按位與，“∨”是按位或。

性質(zhì)2差分經(jīng)過(guò)XOR 運(yùn)算需要滿足以下條件：設(shè)α⊕β=γ，則

性質(zhì)2 表示對(duì)于α⊕β=γ，當(dāng)α,β至少有一個(gè)為零時(shí)，有c=a+b；當(dāng)α,β都非零時(shí)，α⊕β=γ的值可能為零，也可能不為零，所以c=0或1。

性質(zhì)3差分經(jīng)過(guò)輪函數(shù)需要滿足以下條件：設(shè)f(α||β)=γ||δ，則

性質(zhì)3 表示當(dāng)輪函數(shù)的輸入差分非零時(shí)，有a+b+c+d≥ 3（因?yàn)檩斎氩罘趾洼敵霾罘譂M足性質(zhì)1）；當(dāng)輪函數(shù)的輸入差分為零時(shí)，輸出差分也為零。

根據(jù)性質(zhì)2 和性質(zhì)3，借助計(jì)算機(jī)，可以完成以下3 個(gè)實(shí)驗(yàn)。

實(shí)驗(yàn)1計(jì)算機(jī)搜索32 個(gè)σ-Piccolo 結(jié)構(gòu)，給出所有第一輪的活動(dòng)指標(biāo)為0、第2 輪的活動(dòng)指標(biāo)為1、第3 輪的活動(dòng)指標(biāo)為1的3 輪差分特征的尾輪輸出差分（二進(jìn)制）。

實(shí)驗(yàn)1的具體結(jié)果如表2 所示。通過(guò)表2 發(fā)現(xiàn)，對(duì)于任一滿足條件的3 輪差分特征的尾輪輸出差分x0和x1至少有一個(gè)為“1”，和5x至少有一個(gè)為“1”，故可得以下結(jié)論。

表2 實(shí)驗(yàn)1的具體結(jié)果

命題1對(duì)于任一σ-Piccolo 結(jié)構(gòu)，設(shè)4 輪差分特征滿足第一輪的活動(dòng)指標(biāo)為0，第2 輪的活動(dòng)指標(biāo)為1，第3 輪的活動(dòng)指標(biāo)為1，則第4 輪的活動(dòng)指標(biāo)必為2。

引理3對(duì)于任一σ-Piccolo 結(jié)構(gòu)，當(dāng)輸入差分具有(0||0,α2||α3,0||0,α6||α7)形式時(shí)，以下3 個(gè)結(jié)論至少有一個(gè)成立。

結(jié)論1前2 輪Piccolo 結(jié)構(gòu)的活動(dòng)指標(biāo)大于或等于2。

結(jié)論2前3 輪Piccolo 結(jié)構(gòu)的活動(dòng)指標(biāo)大于或等于3。

結(jié)論34 輪Piccolo結(jié)構(gòu)的活動(dòng)指標(biāo)恰為4。其中，α2||α3,α6||α7不全為零。

證明只需證明結(jié)論1 和結(jié)論2 都不成立時(shí)，必有結(jié)論3 成立即可。由引理2 知，2 輪Piccolo 結(jié)構(gòu)的活動(dòng)指標(biāo)大于或等于1，3 輪Piccolo 結(jié)構(gòu)的活動(dòng)指標(biāo)大于或等于2，從而只需證明前2 輪Piccolo結(jié)構(gòu)的活動(dòng)指標(biāo)為1，且前3 輪Piccolo 結(jié)構(gòu)的活動(dòng)指標(biāo)為2時(shí)，必有結(jié)論3成立即可。

定理2對(duì)于任一σ-Piccolo 結(jié)構(gòu)，k(k≥ 1)輪Piccolo 結(jié)構(gòu)的活動(dòng)指標(biāo)大于或等于k-1。

證明（數(shù)學(xué)歸納法）當(dāng)k=1,2,3時(shí)，由引理2知，定理2 成立。

假設(shè)k＜l(l≥ 4)時(shí)定理2 成立，以下證明k=l時(shí)定理2 成立。

此時(shí)，由引理3，又可分為3 種情形。

綜合情形1 和情形2，定理2 成立。證畢。

實(shí)驗(yàn)2計(jì)算機(jī)搜索32 個(gè)σ-Piccolo 結(jié)構(gòu)，給出6 輪Piccolo 結(jié)構(gòu)的活動(dòng)指標(biāo)的最小值。

因篇幅所限，這里只以塊移位變換σ=(72503614)為例給出實(shí)驗(yàn)2的結(jié)果，具體如表3所示。其中第x（十六進(jìn)制）行第y（十六進(jìn)制）列交叉處的數(shù)值表示以(x y)為首輪輸入差分的6 輪Piccolo 結(jié)構(gòu)的活動(dòng)指標(biāo)的最小值。例如，第3 行第e 列交叉處的數(shù)值為6，就表示以為首輪輸入差分的6 輪Piccolo 結(jié)構(gòu)的活動(dòng)指標(biāo)的最小值為6。這里，行數(shù)和列數(shù)都從0 開(kāi)始計(jì)算，另外，實(shí)驗(yàn)結(jié)果表明，使活動(dòng)指標(biāo)的最小值為6的6 輪Piccolo 結(jié)構(gòu)的非零輸入差分共有67個(gè)，使活動(dòng)指標(biāo)的最小值為7的6 輪Piccolo 結(jié)構(gòu)的非零輸入差分共有164 個(gè)，使活動(dòng)指標(biāo)的最小值為8的6 輪Piccolo 結(jié)構(gòu)的非零輸入差分共有24 個(gè)。

表3 實(shí)驗(yàn)2的結(jié)果

實(shí)驗(yàn)2 結(jié)果表明，有以下結(jié)論成立。

命題2 對(duì)于任一σ-Piccolo 結(jié)構(gòu)，6 輪Piccolo結(jié)構(gòu)的活動(dòng)指標(biāo)大于或等于6。

實(shí)驗(yàn)3對(duì)于任一σ-Piccolo 結(jié)構(gòu)，利用計(jì)算機(jī)篩選出活動(dòng)指標(biāo)為6的6 輪差分特征的尾輪輸出差分（十六進(jìn)制），篩選出活動(dòng)指標(biāo)恰為k-1(k=1,2,3,4,5)的k輪差分特征的首輪輸入差分（十六進(jìn)制）。

實(shí)驗(yàn)3的具體結(jié)果如表4 所示。通過(guò)觀察表4發(fā)現(xiàn)，對(duì)于任一σ-Piccolo 結(jié)構(gòu)，實(shí)驗(yàn)3 中所求的尾輪輸出差分和首輪輸入差分沒(méi)有重合，故可得以下結(jié)論。

表4 實(shí)驗(yàn)3的具體結(jié)果

命題3對(duì)于任一σ-Piccolo 結(jié)構(gòu)，若6 輪Piccolo 結(jié)構(gòu)的活動(dòng)指標(biāo)為6，則它的后面不可能“聯(lián)接”活動(dòng)指標(biāo)為k-1(k=1,2,3,4,5)的k輪差分特征。

引理4對(duì)于任一σ-Piccolo 結(jié)構(gòu)，設(shè)為任一活動(dòng)指標(biāo)為6n的6n輪差分特征，則最后6 輪差分特征的活動(dòng)指標(biāo)必為6。

證明根據(jù)命題 2 可知，6 輪差分特征α(6n-6)→…→α(6n)的 活動(dòng)指標(biāo)≥ 6。若α(6n-6)→…→α(6n)的活動(dòng)指標(biāo)大于6，則6(n-1)輪差分特征α(0)→α(1)→ …→α(6)→ …→α(6n-6)的活動(dòng)指標(biāo)必小于6(n-1)，這與命題2 矛盾，故α(6n-6)→ …→α(6n)的活動(dòng)指標(biāo)必為6，引理4 成立。證畢。

定理3對(duì)于任一σ-Piccolo 結(jié)構(gòu)，以下2 個(gè)結(jié)論成立。

結(jié)論1k(1≤k≤ 5)輪Piccolo 結(jié)構(gòu)的活動(dòng)指標(biāo)大于或等于k-1。

結(jié)論2k(k≥ 6)輪Piccolo 結(jié)構(gòu)的活動(dòng)指標(biāo)大于或等于k。

證明1) 結(jié)論1 由定理2 即可證明。

2) 當(dāng)k=6n(n≥ 1)時(shí)，由命題2 可知，結(jié)論2成立。當(dāng)k=6n+m(n≥ 1,1≤m≤ 5)時(shí)，分以下2 種情形進(jìn)行討論。

情形1前6n輪Piccolo 結(jié)構(gòu)的活動(dòng)指標(biāo)大于或等于6n+1。

此時(shí)，由定理 2 可知，后m輪差分特征α(6n)→…→α(6n+m)的活動(dòng)指標(biāo)大于或等于m-1，所以6n+m輪Piccolo 結(jié)構(gòu)的活動(dòng)指標(biāo)大于或等于(6n+1)+(m-1)=6n+m。

情形2前6n輪Piccolo 結(jié)構(gòu)的活動(dòng)指標(biāo)恰為6n時(shí)。

此時(shí)，設(shè)α(0)→ …→α(6n)→ …→α(6n+m)為任一6n+m輪差分特征，且6n輪差分特征α(0)→…→α(6n)的活動(dòng)指標(biāo)為6n。由引理4 知，α(6n-6)→ …→α(6n)的活動(dòng)指標(biāo)為6，再由命題3 和定理2可知，后m輪差分特征α(6n)→ …→α(6n+m)的活動(dòng)指標(biāo)大于或等于m，所以6n+m輪Piccolo結(jié)構(gòu)的活動(dòng)指標(biāo)大于或等于6n+m。

綜合情形1 和情形2，定理3 成立。證畢。

由定理3 可得以下推論（注意：輪函數(shù)中的P變換的差分分支數(shù)為n+1 ）。

推論1對(duì)于任一σ-Piccolo 結(jié)構(gòu)，以下2 個(gè)結(jié)論成立。

結(jié)論1k(1≤k≤ 5)輪差分特征中活動(dòng)S盒的個(gè)數(shù)大于或等于(n+1)(k-1)。

結(jié)論2k(k≥ 6)輪差分特征中活動(dòng)S 盒的個(gè)數(shù)大于或等于(n+1)k。

3 結(jié)束語(yǔ)

本文提出了類Piccolo 結(jié)構(gòu)，并通過(guò)對(duì)差分傳遞規(guī)律的分析，得到了多輪類Piccolo 結(jié)構(gòu)的活動(dòng)輪函數(shù)和活動(dòng)S 盒個(gè)數(shù)的一個(gè)下界。利用這些結(jié)果，結(jié)合輪函數(shù)或S 盒的最大差分概率，給出類Piccolo 結(jié)構(gòu)的最大差分特征概率的上界。本文的研究結(jié)果對(duì)分組密碼的設(shè)計(jì)與分析具有較大的指導(dǎo)意義，但類Piccolo結(jié)構(gòu)抵抗其他攻擊的能力如何值得進(jìn)一步研究。