郭 瑞金晨輝

(解放軍信息工程大學(xué) 鄭州 450004)

1 引言

1990年，Lai和Massey利用一類(lèi)與Feistel模型，廣義Feistel模型，SP網(wǎng)絡(luò)以及其各種變型和組合等都不相同的模型設(shè)計(jì)了國(guó)際數(shù)據(jù)加密標(biāo)準(zhǔn)算法IDEA[1]。1999年，Vaudenay研究了IDEA算法采用的密碼模型的一般化問(wèn)題，提出了Lai-Massey結(jié)構(gòu)[2]，其輪函數(shù)是，這里+表示某個(gè)群運(yùn)算，雙射σ是該群上的正形置換(即雙射σ使仍是雙射)或α幾乎正形置換(使至多只有α個(gè)元素沒(méi)有原象)。實(shí)現(xiàn)速度快是該結(jié)構(gòu)的主要特點(diǎn)。2004年，文獻(xiàn)[3,4]將Lai-Massey結(jié)構(gòu)中的群運(yùn)算具體為逐位模 2加，將雙射變換σ具體為正形置換具體為SPS模型，設(shè)計(jì)了FOX系列分組密碼算法(即 IDEA NXT)，從而給出了以 Lai-Massey結(jié)構(gòu)為密碼模型的一個(gè)分組密碼實(shí)例。在對(duì)FOX算法的安全性分析方面，文獻(xiàn)[5,6]構(gòu)造了FOX算法的3輪積分區(qū)分器，并給出了迄今最優(yōu)的積分分析的結(jié)果，證明了4輪FOX64/64, 5輪FOX64/128, 6輪FOX64/192, 7輪FOX64/256對(duì)碰撞-積分攻擊不免疫；文獻(xiàn)[7,8]先后給出了FOX算法的4輪不可能差分區(qū)分器，并給出了相應(yīng)的不可能差分分析結(jié)果；文獻(xiàn)[9]等則分析了FOX算法抗差錯(cuò)攻擊的能力。此外，文獻(xiàn)[10]給出了FOX算法的差分碰撞攻擊。上述結(jié)果表明，在傳統(tǒng)分析方法下，F(xiàn)OX系列算法展現(xiàn)了充分的安全性冗余。由此可得Lai-Massey結(jié)構(gòu)是一類(lèi)安全性較高的密碼模型，值得進(jìn)一步深入研究。

偽隨機(jī)特性是設(shè)計(jì)密碼模型需要滿(mǎn)足的基本條件。在雙射σ為正形置換的條件下，文獻(xiàn)[2]和文獻(xiàn)[11]使用不同的方法證明了Lai-Massey結(jié)構(gòu)3輪復(fù)合可達(dá)偽隨機(jī)條件，4輪復(fù)合可達(dá)超偽隨機(jī)條件。針對(duì)不是任意群(如2mZ )上都存在正形置換的問(wèn)題，文獻(xiàn)[2]指出可以利用該群上的幾乎正形置換設(shè)計(jì)雙射σ，且證明了此時(shí)Lai-Massey結(jié)構(gòu)的偽隨機(jī)特性保持一致，從而推廣了Lai-Massey結(jié)構(gòu)的應(yīng)用范圍。然而，本文利用Lai-Massey結(jié)構(gòu)的差分特性，證明了當(dāng)雙射σ為仿射幾乎正形置換時(shí)，3輪Lai-Massey結(jié)構(gòu)并不具有偽隨機(jī)特性。

此外，2009年Luo等人[12]將Lai-Massey結(jié)構(gòu)的群運(yùn)算具體為異或運(yùn)算，雙射變換σ具體為線性正形置換，證明了Lai-Massey結(jié)構(gòu)至少3輪復(fù)合達(dá)到偽隨機(jī)性，至少4輪復(fù)合達(dá)到超偽隨機(jī)性。但是，并未探討Lai-Massey結(jié)構(gòu)中不同正形置換和群運(yùn)算對(duì)其偽隨機(jī)特性的影響。因此，本文從Lai-Massey結(jié)構(gòu)設(shè)計(jì)的角度出發(fā)，分析是否存在特定的群運(yùn)算和正形置換使得Lai-Massey結(jié)構(gòu)具有更好的偽隨機(jī)特性。為此，本文利用構(gòu)造區(qū)分器的方法證明了雙射σ為任意正形置換時(shí)，3輪Lai-Massey結(jié)構(gòu)具有偽隨機(jī)特性的必要性；證明了雙射σ為仿射正形置換時(shí)，3輪的Lai-Massey結(jié)構(gòu)一定不具有超偽隨機(jī)特性。結(jié)論表明，基于非線性雙射σ設(shè)計(jì)的Lai-Massey結(jié)構(gòu)可能具有更好的偽隨機(jī)特性。

2 基礎(chǔ)知識(shí)

本節(jié)首先給出偽隨機(jī)置換和超偽隨機(jī)置換的定義，然后介紹Lai-Massey結(jié)構(gòu)及其偽隨機(jī)特性。

2.1 偽隨機(jī)和超偽隨機(jī)置換

定義 1[2]令 :F為以密鑰為索引的置換。如果對(duì)于任意概率多項(xiàng)式時(shí)間的攻擊者 A，都存在一個(gè)可忽略函數(shù)，使得

則稱(chēng)F是偽隨機(jī)置換。其中密鑰k在密鑰空間中隨機(jī)均勻選取，置換P從群G到G上構(gòu)成的所有置換集合中隨機(jī)選取。

定義 2[2]令 :F為以密鑰為索引的置換。如果對(duì)于任意概率多項(xiàng)式時(shí)間的攻擊者 A，都存在一個(gè)可忽略函數(shù)()nε，使得

則稱(chēng)F是超偽隨機(jī)置換。其中密鑰k在密鑰空間中隨機(jī)均勻選取，置換P從群G到G上構(gòu)成的所有置換集合中隨機(jī)選取。

與定義1中的攻擊者只具有選擇明文的權(quán)利相比，定義2的攻擊者A同時(shí)具有選擇明文和選擇密文的權(quán)利。

2.2 Lai-Massey結(jié)構(gòu)及其偽隨機(jī)特性[1317]-

定義 3[2]設(shè)kF和σ是群G到自身的映射且σ是雙射，為交換群，k是圈密鑰，則稱(chēng)以

為圈函數(shù)的分組密碼為 Lai-Massey結(jié)構(gòu)，并稱(chēng)kF是圈函數(shù)kQ的F函數(shù)，稱(chēng)σ是圈函數(shù)kQ的σ函數(shù)。

為保證Lai-Massey結(jié)構(gòu)的加解密的相似性，最后一圈的圈函數(shù)一般設(shè)置為。

引理1[2]設(shè)σ是群G上的α幾乎正形置換，如果攻擊者A具有選擇明文的權(quán)利，且詢(xún)問(wèn)預(yù)言機(jī)的能力限定為概率多項(xiàng)式時(shí)間，則有

引理2[2]設(shè)σ是群G上的α幾乎正形置換，如果攻擊者A同時(shí)具有選擇明文和選擇密文的權(quán)利，且詢(xún)問(wèn)預(yù)言機(jī)的能力限定為概率多項(xiàng)式時(shí)間，則有

3 雙射σ為仿射幾乎正形置換時(shí)，3輪Lai-Massey結(jié)構(gòu)的區(qū)分器

特別地，在文獻(xiàn)[17]中，給出了幾乎正形置換的構(gòu)造方法。

引理 3[17]設(shè)雙射函數(shù)σ是群G上的置換。如果存在2λ≥，對(duì)于任意的LG∈，等式()xxL σ - =在群G上最多有λ個(gè)解，則此σ置換即為幾乎正形置換，特別地，如果σ為仿射變換，則稱(chēng)σ為仿射幾乎正形置換。

所以，當(dāng)σ是仿射函數(shù)時(shí)，有

證畢

利用引理3給出的仿射幾乎正形置換的構(gòu)造方法，再結(jié)合引理5，則3輪Lai-Massey結(jié)構(gòu)3LM 與隨機(jī)置換P的區(qū)分器具體構(gòu)造方法如下：

定理 1 設(shè)雙射σ是群G上的仿射幾乎正形置換。則攻擊者A進(jìn)行2次加密詢(xún)問(wèn)，可以的優(yōu)勢(shì)區(qū)分3輪Lai-Massey結(jié)構(gòu)3LM 與隨機(jī)置換P。

當(dāng)攻擊者A詢(xún)問(wèn)加密預(yù)言機(jī)O為3LM 時(shí)。由引理5可知區(qū)分算法輸出為1的概率為1。

所以，該區(qū)分算法的區(qū)分優(yōu)勢(shì)為

證畢

文獻(xiàn)[2]證明了基于幾乎正形置換設(shè)計(jì)的 3輪Lai-Massey模型具有偽隨機(jī)特性，而定理1說(shuō)明當(dāng)雙射σ是群G上的仿射幾乎正形置換時(shí)，3輪的Lai-Massey模型與隨機(jī)置換是可區(qū)分的，從而給出一個(gè)反例。結(jié)論表明，基于仿射幾乎正形置換設(shè)計(jì)的Lai-Massey模型并不具有特別好的偽隨機(jī)性。即對(duì)于基于引理3構(gòu)造的仿射幾乎正形置換不適用于Lai-Massey模型的設(shè)計(jì)。因?yàn)榇嬖谑沟?，此時(shí)作為選擇的消息，可以用于定理1中區(qū)分器的構(gòu)造。

此外，Lai等人將Lai-Massey結(jié)構(gòu)的群運(yùn)算具體為異或運(yùn)算，雙射變換σ具體為線性正形置換，證明了Lai-Massey結(jié)構(gòu)至少3輪復(fù)合達(dá)到偽隨機(jī)性，至少4輪復(fù)合達(dá)到超偽隨機(jī)性[11]。但是，并未探討Lai-Massey結(jié)構(gòu)中不同正形置換和群運(yùn)算對(duì)其偽隨機(jī)特性的影響。下面進(jìn)一步研究基于一般的群運(yùn)算和正形置換設(shè)計(jì)的 Lai-Massey結(jié)構(gòu)的偽隨機(jī)特性。

4 雙射σ為正形置換時(shí)，2輪Lai-Massey結(jié)構(gòu)不具有偽隨機(jī)特性

引理6 對(duì)于2輪Lai-Massey結(jié)構(gòu)(第2輪無(wú)σ變換)2LM ，選擇兩個(gè)不同的消息,進(jìn)行加密，其中，則得到的輸出必然滿(mǎn)足等式，其中雙射, 0表示加法群G中的單位元。

證畢

定理 2 設(shè)σ是群G上的任意正形置換。則攻擊者A進(jìn)行 2次加密詢(xún)問(wèn)，可以的優(yōu)勢(shì)區(qū)分2輪Lai-Massey結(jié)構(gòu)2LM 與隨機(jī)置換P。

證明 攻擊者A具有詢(xún)問(wèn)加密預(yù)言機(jī)O的能力，其中O為2LM 或隨機(jī)置換P，攻擊者A構(gòu)造可區(qū)分2輪Lai-Massey置換和均勻隨機(jī)置換的算法如下：

所以，該區(qū)分算法的區(qū)分優(yōu)勢(shì)為

證畢

5 雙射σ為仿射正形置換時(shí)，3輪 Lai-Massey結(jié)構(gòu)不具有超偽隨機(jī)特性

下面，利用同時(shí)進(jìn)行選擇明文和選擇密文的方式，構(gòu)造3輪Lai-Massey結(jié)構(gòu)與隨機(jī)置換的區(qū)分器。進(jìn)而說(shuō)明，當(dāng)σ為仿射正形置換時(shí)，Lai-Massey結(jié)構(gòu)至少4輪復(fù)合才具有超偽隨機(jī)特性。

引理7 對(duì)于3輪Lai-Massey結(jié)構(gòu)3LM ，設(shè)σ是群G上的仿射正形置換。選擇兩個(gè)不同的消息進(jìn)行加密，其中，得到輸出，再對(duì)進(jìn)行解密，得到消息，其中要求2δ滿(mǎn)足等式。則必有等式成立。其中由仿射正形置換決定的唯一常數(shù)。

進(jìn)而得到等式：

及等式：

證畢

證畢

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

本文深入研究了 Lai-Massey結(jié)構(gòu)的偽隨機(jī)特性。首先，證明了基于仿射幾乎正形置換設(shè)計(jì)的 3輪Lai-Massey模型并不具有偽隨機(jī)特性，給出了設(shè)計(jì)者所得結(jié)論的一個(gè)反例。其次，證明了雙射σ為任意正形置換時(shí)，至少3輪Lai-Massey結(jié)構(gòu)才具有偽隨機(jī)特性；證明了雙射σ為仿射正形置換時(shí)，至少4輪的Lai-Massey結(jié)構(gòu)才具有超偽隨機(jī)特性。結(jié)論表明，構(gòu)造偽隨機(jī)特性更好的Lai-Massey結(jié)構(gòu)實(shí)例，雙射σ最好設(shè)計(jì)為非線性的正形置換或幾乎正形置換。因此，分析是否存在非線性的正形置換σ使得3輪的Lai-Massey結(jié)構(gòu)具有超偽隨機(jī)特性，或者直接證明Lai-Massey結(jié)構(gòu)是否至少4輪達(dá)到超偽隨機(jī)特性，是值得進(jìn)一步研究的問(wèn)題。

[1] Lai X and Massey J. A proposal for a new block encryption standard[J]. LNCS, 1990, 473: 389-404.

[2] Vaudenay S. On the Lai-Massey scheme[J]. LNCS, 1999, 1716:8-19.

[3] Junod P and Vaudenay S. FOX: a new family of block ciphers[J]. LNCS, 2005, 3357: 114-129.

[4] Nakahara J. An analysis of FOX[J]. LNCS, 2009, 2010:236-249.

[5] Wu Wen-ling, Zhang Wen-tao, and Feng Deng-guo. Integral cryptanalysis of reduced FOX block cipher[J]. LNCS, 2005,3935: 229-241.

[6] 吳文玲, 衛(wèi)宏儒. 低圈FOX分組密碼的碰撞-積分攻擊[J]. 電子學(xué)報(bào), 2005, 33(7): 1307-1310.Wu Wen-ling and Wei Hong-ru. Collision-integral attack of reduced-round FOX[J]. Acta Electronica Sinica, 2005, 33(7):1307-1310.

[7] Wu Zhong-ming, Lai Xue-jia, Zhu Bo, et al.. Impossible differential cryptanalysis of FOX[J]. LNCS, 2010, 6163:236-249.

[8] 魏悅川, 孫兵, 李超. FOX密碼的不可能差分分析[J]. 通信學(xué)報(bào), 2010, 31(9): 24-29.Wei Yue-chuan, Sun Bing, and Li Chao. Impossible differential attacks on FOX[J]. Journal on Communications,2010, 31(9): 24-29.

[9] Li Rui-lin, You Jian-xiong, Sun Bing, et al.. Fault analysis study of the block cipher FOX64[J]. Multimedia Tools and Applications, 2013, 63(3): 691-708.

[10] Chen Jie, Hu Yu-pu, Zhang Yue-yu, et al.. Differential collision attack on reduced FOX block cipher[J]. China Communications, 2012, 9(7): 71-76.

[11] Yun Aaram, Park Je Hong, and Lee Jooyoung. On Lai-Massey and quasi-Feistel ciphers[J]. Design Codes Cryptography, 2011, 58: 45-72.

[12] Luo Yi-yuan, Lai Xue-jia, and Gong Zheng.Pseudorandomness analysis of the (extended) Lai-Massey scheme[J]. Information Processing Letters, 2010, 111(2):90-96.

[13] Yu Yu. Pseudorandom generators from regular one-way functions: new constructions with improved parameters[OL].http://eprint.iacr.org/2013/270. 2013.

[14] Alexandra Boldyreva and Virendra Kumar. A new pseudorandom generator from Collision-Resistant hash functions[J]. LNCS, 2012, 7178: 187-202.

[15] Andrej Bogdanov, Zeev Dvir, Elad Verbin, et al..Pseudorandomness for width-2 branching programs[J].Theory of Computing, 2013, (9): 283-293.

[16] Luca Trevisan. Pseudorandomness and derandomization[J].Association for Computing Machinery, 2012, 18(3): 27-31.[17] Jacques Patarin. How to construct pseudorandom and super pseudorandom permutations from one single pseudorandom function[J]. LNCS, 1992, 658: 256-266.