王念平，殷勍

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

0 引言

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

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

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

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

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

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

1 預(yù)備知識

1.1 基本概念

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

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

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

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

定義4r(r≥1) 輪差分特征中活動輪函數(shù)的個數(shù)稱為該差分特征的活動指標。

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

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個m×m雙射S 盒（n為偶數(shù)且nm=t，t為輸入塊X i(i=0,1,2,3)的比特數(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 個條件的置換。

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

形象地說，滿足條件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的σ

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

圖5 滿足條件2的σ

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

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

2 類Piccolo 結(jié)構(gòu)的活動輪函數(shù)和活動S 盒個數(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)的差分對應(yīng)的結(jié)構(gòu)形式。

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

證畢。

由定理1，可得以下事實。

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

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

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

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

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

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

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

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

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

接下來，設(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為活動輪函數(shù)當且僅當左起第1、2 位不全為零，f1為活動輪函數(shù)當且僅當左起第5、6 位不全為零。

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

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

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

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

性質(zhì)3 表示當輪函數(shù)的輸入差分非零時，有a+b+c+d≥ 3（因為輸入差分和輸出差分滿足性質(zhì)1）；當輪函數(shù)的輸入差分為零時，輸出差分也為零。

根據(jù)性質(zhì)2 和性質(zhì)3，借助計算機，可以完成以下3 個實驗。

實驗1計算機搜索32 個σ-Piccolo 結(jié)構(gòu)，給出所有第一輪的活動指標為0、第2 輪的活動指標為1、第3 輪的活動指標為1的3 輪差分特征的尾輪輸出差分（二進制）。

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

表2 實驗1的具體結(jié)果

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

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

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

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

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

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

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

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

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

此時，由引理3，又可分為3 種情形。

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

實驗2計算機搜索32 個σ-Piccolo 結(jié)構(gòu)，給出6 輪Piccolo 結(jié)構(gòu)的活動指標的最小值。

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

表3 實驗2的結(jié)果

實驗2 結(jié)果表明，有以下結(jié)論成立。

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

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

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

表4 實驗3的具體結(jié)果

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

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

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

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

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

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

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

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

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

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

情形2前6n輪Piccolo 結(jié)構(gòu)的活動指標恰為6n時。

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

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

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

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

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

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

3 結(jié)束語

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