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

董新鋒,周 宇,張文政

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

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

董新鋒,周 宇,張文政

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

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

拉丁方 多輸出Bent函數 非線性度

0 引 言

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

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

1 準備知識

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

定義2設S:{0,1,…,n-1}→{0,1,…,n-1},如果S恰好是一個置換,則稱S是n階置換。

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

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

n階拉丁方變換具有以下性質:

性質1：n階拉丁方變換L具有1階相關免疫性質。

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

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

2 2n入n出Bent函數

根據文獻[5]中關于嚴格M-M類Bent函數的構造方法和結論,容易得到下述引理1～引理3。詳細證明過程可參考文獻[5],本文不再贅述。

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

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

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

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

由引理1～引理3,容易得到下面2n入n出Bent函數的構造方法。

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

3 n階拉丁方陣

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

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

算法Alg_construct_Latin(n):

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

輸出:n階拉丁方陣L。

具體步驟如下:

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

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

Step3構造2n入n出Bent函數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)與第一行的對應元素h(0,x)和第一列的對應元素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)均為置換函數;當m=0時有h(x,0)=h(0,x)=0。由于h(x,x)是n入n出的置換函數,因此步驟step4中交換元素后能得到拉丁方陣L″。

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

證明:2n入n出Bent函數的非線性度為22n-1-2n-1。算法Alg_construct_Latin(n)的步驟Step4中總共改變了Bent函數h(x,y)的3×(2n-1)個值,且相應的分量函數在第1行、第1列及對角線上分別改變了2n-1個值。根據非線性度的定義,nl(L″)與Bent函數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)構造的n階拉丁方陣至少有φ(2n-1)/n個。

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

下面我們給出具體的構造實例和測試結果。

例設n=4,構造4階拉丁方陣L。

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

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

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

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

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

詳細測試結果見表1。

表1 矩陣的密碼性質Table 1 Cryptographic properties of matrix

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

4 結 語

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

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

[1] 陶仁驥.(4,4)拉丁陣在密碼設計上的一種應用[J].計算機學報,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] 熊玲,申兵,王金波.有限域小波變換的密碼學性質簡評[J].通信技術,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].計算機工程與設計,2009,30(06):1376-1378.

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

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

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

張文政(1966—),男,碩士,研究員,主要研究方向為密碼學。

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—),男,碩士,工程師,主要研究方向為密碼學;

2014-05-15;

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

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

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