董新鋒,周 宇,張文政

(保密通信重點(diǎn)實(shí)驗(yàn)室,四川成都610041)

一類(lèi)非線(xiàn)性度較高的拉丁方陣*

董新鋒,周 宇,張文政

(保密通信重點(diǎn)實(shí)驗(yàn)室,四川成都610041)

拉丁方變換是一類(lèi)非常重要的變換,在密碼算法設(shè)計(jì)、組合設(shè)計(jì)等領(lǐng)域具有廣泛的應(yīng)用,目前對(duì)密碼性質(zhì)好的拉丁方陣的構(gòu)造方法研究較少。通過(guò)研究基于可逆方陣的多輸出Bent函數(shù)的構(gòu)造方法,提出了一種利用本原多項(xiàng)式來(lái)構(gòu)造非線(xiàn)性度高的拉丁方陣的算法,并對(duì)這類(lèi)拉丁方陣的密碼性質(zhì)進(jìn)行了分析和測(cè)試,結(jié)果表明這類(lèi)拉丁方陣具有較高的非線(xiàn)性度和較高的代數(shù)次數(shù),能夠用于實(shí)際應(yīng)用中密碼算法的設(shè)計(jì)。

拉丁方 多輸出Bent函數(shù) 非線(xiàn)性度

0 引 言

拉丁方變換是一類(lèi)非常重要的變換,在密碼算法的設(shè)計(jì)、組合設(shè)計(jì)等領(lǐng)域中有廣泛的應(yīng)用。例如, 4×4拉丁方變換經(jīng)常被用于序列密碼的設(shè)計(jì)[1-2]。密碼算法設(shè)計(jì)中使用的拉丁方變換一般要求具有良好的密碼學(xué)性質(zhì),例如高的代數(shù)次數(shù)、高的非線(xiàn)性度、較小的差分概率等。構(gòu)造密碼學(xué)性質(zhì)好的拉丁方變換以及分析拉丁方變換的密碼學(xué)性質(zhì),對(duì)于利用拉丁方變換構(gòu)造安全高效的密碼算法具有重要意義。目前這方面公開(kāi)的研究成果較少,文獻(xiàn)[3]研究了2n階拉丁方的差分密碼特性,考察了差分的概率分布和均值,以及差分表中各種值的平均數(shù),并探討了這些指標(biāo)的近似計(jì)算問(wèn)題。文獻(xiàn)[4]從多輸出布爾函數(shù)的給出了拉丁方變換的幾個(gè)等價(jià)刻畫(huà)描述,并詳細(xì)討論了拉丁方變換的Walsh譜特征和差分特征。

本文從多輸出布爾函數(shù)[5-7]的角度,給出了一種利用2n入n出Bent函數(shù)構(gòu)造n階拉丁方陣的方法,并給出了測(cè)試實(shí)例。相關(guān)的測(cè)試結(jié)果表明,這種方法得到的拉丁方陣具有較高的非線(xiàn)性度和較高的代數(shù)次數(shù)。這種構(gòu)造方法結(jié)構(gòu)簡(jiǎn)單,并且能夠快速實(shí)現(xiàn),可以用于實(shí)際應(yīng)用中密碼算法及協(xié)議的設(shè)計(jì)。

1 準(zhǔn)備知識(shí)

定義1設(shè)f:→,如果對(duì)?a∈都有f(a)∈,則稱(chēng)f是n入m出的多輸出布爾函數(shù)。

定義2設(shè)S:{0,1,…,n-1}→{0,1,…,n-1},如果S恰好是一個(gè)置換,則稱(chēng)S是n階置換。

定義3設(shè)L:{0,1,…,2n-1}×{0,1,…,2n-1}→{0,1,…,2n-1},如果?a∈{0,1,…,2n-1},以x為變量的函數(shù)L(a,x)和L(x,a)都是置換函數(shù),則稱(chēng)L是n階拉丁方變換,相應(yīng)的2n×2n階矩陣稱(chēng)為n階拉丁方陣。

n階拉丁方變換,等價(jià)于2n入n出的多輸出布爾函數(shù)。因此可以通過(guò)研究多輸出布爾函數(shù)的相關(guān)工具來(lái)研究拉丁方陣的性質(zhì),如通過(guò)Walsh譜等工具來(lái)刻畫(huà)拉丁方陣的非線(xiàn)性度、代數(shù)次數(shù)、相關(guān)免疫性質(zhì)、擴(kuò)散性質(zhì)、差分概率等[4]。

n階拉丁方變換具有以下性質(zhì):

性質(zhì)1：n階拉丁方變換L具有1階相關(guān)免疫性質(zhì)。

性質(zhì)2：對(duì)n階拉丁方陣的所有行進(jìn)行2n階置換,得到的矩陣仍然是n階拉丁方陣。

性質(zhì)3：對(duì)n階拉丁方陣的所有列進(jìn)行2n階置換,得到的矩陣仍然是n階拉丁方陣。

2 2n入n出Bent函數(shù)

根據(jù)文獻(xiàn)[5]中關(guān)于嚴(yán)格M-M類(lèi)Bent函數(shù)的構(gòu)造方法和結(jié)論,容易得到下述引理1～引理3。詳細(xì)證明過(guò)程可參考文獻(xiàn)[5],本文不再贅述。

引理1對(duì)任意正整數(shù)n,存在F2上的n×n階方陣A,使得{A,A2,A3,…,An}中任何若干個(gè)方陣的和矩陣都是可逆方陣。

特別地,對(duì)任意正整數(shù)n,在F2上有φ(2n-1)/ n個(gè)n次本原多項(xiàng)式,此處φ(·)表示歐拉函數(shù)。取任意n次本原多項(xiàng)式1+a1X+a2X2+…+an-1Xn-1+Xn,則下面的矩陣A滿(mǎn)足引理1中的要求。

引理2設(shè)A是F2上的n×n階可逆方陣,則y=xA是→的置換函數(shù),其中x=(x1,x2,…,xn)∈。

引理3設(shè)A是F2上的n×n階方陣,且滿(mǎn)足{A,A2,A3,…,An}中任何若干個(gè)方陣的和矩陣都是可逆方陣,則{g1(x)=xA,g2(x)=xA2,…,gn(x)= xAn}中任何若干個(gè)函數(shù)的和函數(shù)都是置換函數(shù)。

由引理1～引理3,容易得到下面2n入n出Bent函數(shù)的構(gòu)造方法。

構(gòu)造方法1:設(shè)A是F2上的n×n階方陣,且滿(mǎn)足{A,A2,A3,…,An}中任何若干個(gè)方陣的和矩陣都是可逆方陣,則可定義2n入n出Bent函數(shù)h(x,y)形式如下:

3 n階拉丁方陣

定理1：設(shè)h(x,y)為構(gòu)造方法1中構(gòu)造的2n入n出的Bent函數(shù),且滿(mǎn)足h(x,x)是n入n出的置換函數(shù),則可通過(guò)h(x,y)構(gòu)造高非線(xiàn)性度的拉丁方陣L。

證明:能夠通過(guò)n階高非線(xiàn)性度拉丁方陣的構(gòu)造算法Alg_construct_Latin(n)來(lái)證明該定理,即給出了定理1的構(gòu)造性證明。

算法Alg_construct_Latin(n):

輸入:任意正整數(shù)n,n次本原多項(xiàng)式1+a1X+a2X2+…+an-1Xn-1+Xn。

輸出:n階拉丁方陣L。

具體步驟如下:

Step1對(duì)任意正整數(shù)n,取定一個(gè)n次本原多項(xiàng)式1+a1X+a2X2+…+an-1Xn-1+Xn,生成對(duì)應(yīng)的特征矩陣

Step2基于n階矩陣A構(gòu)造{A,A2,A3,…,An},進(jìn)而構(gòu)造{g1(x)=xA,g2(x)=xA2,…,gn(x)= xAn},其中x∈,gj(x)∈,j∈{1,2,…,n};

Step3構(gòu)造2n入n出Bent函數(shù)h(x,y)= g1(x)y1+g2(x)y2+…+gn(x)yn,其中y=(y1,y2,…,yn)∈,并將h(x,y)表示成2n×2n階矩陣

Step4將2n階矩陣h對(duì)角線(xiàn)上的元素h(x,x)與第一行的對(duì)應(yīng)元素h(0,x)和第一列的對(duì)應(yīng)元素h(x,0)交換得到拉丁方陣

Step5對(duì)L″的所有行進(jìn)行2n階置換S1得到拉丁方陣L′,對(duì)L′的所有列進(jìn)行2n階置換S2得到拉丁方陣L。

注:步驟Step3中取定h(x,y)中的分量x=m≠0或y=m≠0時(shí),h(m,y)或h(x,m)均為置換函數(shù);當(dāng)m=0時(shí)有h(x,0)=h(0,x)=0。由于h(x,x)是n入n出的置換函數(shù),因此步驟step4中交換元素后能得到拉丁方陣L″。

推論1：算法Alg_construct_Latin(n)中構(gòu)造的n階拉丁方陣L″的非線(xiàn)性度滿(mǎn)足

證明:2n入n出Bent函數(shù)的非線(xiàn)性度為22n-1-2n-1。算法Alg_construct_Latin(n)的步驟Step4中總共改變了Bent函數(shù)h(x,y)的3×(2n-1)個(gè)值,且相應(yīng)的分量函數(shù)在第1行、第1列及對(duì)角線(xiàn)上分別改變了2n-1個(gè)值。根據(jù)非線(xiàn)性度的定義,nl(L″)與Bent函數(shù)h(x,y)的非線(xiàn)性度22n-1-2n-1相比至多下降3×2n-1,即得到n階拉丁方陣L″的非線(xiàn)性度下界22n-1-2n-1-3×2n-1=22n-1-2n+1。

推論2：算法Alg_construct_Latin(n)構(gòu)造的n階拉丁方陣至少有φ(2n-1)/n個(gè)。

證明:由算法Alg_construct_Latin(n)的步驟Step1易知構(gòu)造的n階拉丁方陣個(gè)數(shù)至少與n次本原多項(xiàng)式的個(gè)數(shù)相同,即φ(2n-1)/n。

下面我們給出具體的構(gòu)造實(shí)例和測(cè)試結(jié)果。

例設(shè)n=4,構(gòu)造4階拉丁方陣L。

Step1 選擇的4次本原多項(xiàng)式為1+X3+X4,對(duì)應(yīng)的特征矩陣

得到的8入4出Bent函數(shù)h(x0x1x2x3,x4x5x6x7)的16×16階真值表矩陣h為(十六進(jìn)制):

Step4 將矩陣h對(duì)角線(xiàn)上的元素與第一行和第一列的對(duì)應(yīng)元素交換得到4階拉丁方陣L″為(十六進(jìn)制):

Step5 對(duì)L″的所有行進(jìn)行16階置換S1得到拉丁方L′,對(duì)L′的所有列進(jìn)行16階置換S2得到拉丁方陣L:

對(duì)上述的Bent函數(shù)h、拉丁方陣L″、拉丁方陣L分別進(jìn)行整體非線(xiàn)性度、代數(shù)式次數(shù)、最大差分概率等密碼性質(zhì)的測(cè)試。

詳細(xì)測(cè)試結(jié)果見(jiàn)表1。

表1 矩陣的密碼性質(zhì)Table 1 Cryptographic properties of matrix

表1中的測(cè)試結(jié)果表明:通過(guò)算法Alg_construct_Latin(n)得到的4階拉丁方L具有良好的密碼性能,L的整體非線(xiàn)性度為96,代數(shù)式次數(shù)為6,能夠被用于實(shí)際密碼算法的設(shè)計(jì)。

4 結(jié) 語(yǔ)

本文通過(guò)研究多輸出Bent函數(shù),給出了一種構(gòu)造非線(xiàn)性度較高的拉丁方陣的算法,并對(duì)實(shí)例的主要密碼性能進(jìn)行了測(cè)試,相關(guān)測(cè)試結(jié)果表明,該類(lèi)拉丁方具有良好的密碼性能,如高的非線(xiàn)性度、高的代數(shù)式次數(shù)等,能夠被應(yīng)用于實(shí)際密碼算法的設(shè)計(jì)。

如何設(shè)計(jì)其他密碼性質(zhì)好的拉丁方陣以及如何通過(guò)更一般的多輸出布爾函數(shù)來(lái)構(gòu)造拉丁方變換是需要繼續(xù)深入研究的問(wèn)題,對(duì)設(shè)計(jì)密碼性質(zhì)好的拉丁方陣具有重要意義。

[1] 陶仁驥.(4,4)拉丁陣在密碼設(shè)計(jì)上的一種應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào),1991(14):423-451.

TAO Ren-ji.An Application Of(4,4)-Latin Arrays To Cryptography[J].Chinese Journal Of Computers,1991, (14):423-451.

[2] 熊玲,申兵,王金波.有限域小波變換的密碼學(xué)性質(zhì)簡(jiǎn)評(píng)[J].通信技術(shù),2013,46(12):58-61.

XIONG Ling,SHEN Bing,WANG Jin-bo.Review on Cryptographic Property of Finite-Field Wavelet Transform [J].Communications Technology,2013,46(12):58-61.

[3] 曾國(guó)平.拉丁方的差分分布特性研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(06):1376-1378.

ZENG Guo-ping.Differential Distributions of Latin Squares.Computer Engineering And Design,2009,30 (6):1376-1378.

[4] 金晨輝.拉丁方變換的幾個(gè)等價(jià)刻劃[J].通信學(xué)報(bào), 2003,24(06):139-132.

JIN Chen-hui.Equivalent Characteristics For Latin Square Transformations[J].Journal Of China Institute Of Communication,2003,24(6):139-132.

[5] Takashi Satoh,Tetsu Iwata,Kaoru Kurosawa.On Cryptographically Secure Vectorial Boolean Functions[C]// International Conference on the Theory and Applications of Cryptology and Information Security,Singapore,Proceedings of Advances in Cryptology-ASIACRYPT'99. [s.l.]:Springer,1999:20-28.

[6] CESMELIOGLU A,MEIDL W.A Construction of Bent Functions from Plateaued Functions[J].Designs,Codes and Cryptography,2013,66(1-3):231-242.

[7] STANICA P,MARTINSEN T,GANGOPADHYAY S,et al.Bent and Generalized Bent Boolean Functions[J].Designs,Codes and Cryptography,2013,69(01):77-94.

DONG Xin-feng(1985-),male,M.Sci., engineer,mainly working at cryptology.

周 宇(1980—),男,博士,高級(jí)工程師,主要研究方向?yàn)槊艽a學(xué);

ZHOU Yu(1980-),male,Ph.D.,senior engineer,mainly working at cryptology.

張文政(1966—),男,碩士,研究員,主要研究方向?yàn)槊艽a學(xué)。

ZHANG Wen-zheng(1966-),male,M.Sci.,research fellow,mainly working at cryptology.

A Class of Latin Square with Higher Nonlinearity

DONG Xin-feng,ZHOU Yu,ZHANG Wen-zheng
(Key Laboratory of Privacy Communication,Chengdu Sichuan 610041,China)

Latin square,as an important transformation,is widely used in some applications,including cryptographic algorithm design and combinational design.At present,less study is done on the methods to construct Latin squares with good cryptographic properties.By studying the construction method of vectorial bent function based on invertible square and with primitive polynomial,a method to construct Latin squares with high nonlinearity is proposed.Meanwhile these Latin squares are analyzed and the primary cryptographic properties tested,including nonlinearity and algebraic degree.The experiment results show that the Latin square is of good nonlinearity and high algebraic degree,and could be used to design cryptographic algorithm with many applications.

latin square;vectorial bent function;nonlinearity

TN 918.1

A

1002-0802(2014)09-1058-04

10.3969/j.issn.1002-0802.2014.09.016

董新鋒(1985—),男,碩士,工程師,主要研究方向?yàn)槊艽a學(xué);

2014-05-15;

2014-07-16 Received date：2014-05-15;Revised date：2014-07-16

國(guó)家自然科學(xué)基金(No.61309034)

Foundation Item：National Science Foundation of China(No.61309034)