董新鋒,周 宇,張文政

(保密通信重點實驗室,四川成都610041)

一類非線性度較高的拉丁方陣*

董新鋒,周 宇,張文政

(保密通信重點實驗室,四川成都610041)

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

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

0 引 言

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

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

1 準(zhǔn)備知識

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

定義2設(shè)S:{0,1,…,n-1}→{0,1,…,n-1},如果S恰好是一個置換,則稱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ù),則稱L是n階拉丁方變換,相應(yīng)的2n×2n階矩陣稱為n階拉丁方陣。

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

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

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

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

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

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

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

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

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

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

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

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

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

3 n階拉丁方陣

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

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

算法Alg_construct_Latin(n):

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

輸出:n階拉丁方陣L。

具體步驟如下:

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

Step2基于n階矩陣A構(gòu)造{A,A2,A3,…,An},進而構(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對角線上的元素h(x,x)與第一行的對應(yīng)元素h(0,x)和第一列的對應(yīng)元素h(x,0)交換得到拉丁方陣

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

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

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

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

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

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

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

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

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

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

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

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

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

詳細測試結(jié)果見表1。

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

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

4 結(jié) 語

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

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

[1] 陶仁驥.(4,4)拉丁陣在密碼設(shè)計上的一種應(yīng)用[J].計算機學(xué)報,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ì)簡評[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] 曾國平.拉丁方的差分分布特性研究[J].計算機工程與設(shè)計,2009,30(06):1376-1378.

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

[4] 金晨輝.拉丁方變換的幾個等價刻劃[J].通信學(xué)報, 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—),男,博士,高級工程師,主要研究方向為密碼學(xué);

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

張文政(1966—),男,碩士,研究員,主要研究方向為密碼學(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—),男,碩士,工程師,主要研究方向為密碼學(xué);

2014-05-15;

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

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

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