一致可微T函數(shù)性質(zhì)研究

王森鵬,劉 燕,胡 斌

(解放軍信息工程大學(xué),河南鄭州 450001)

?

一致可微T函數(shù)性質(zhì)研究

王森鵬,劉 燕,胡 斌

(解放軍信息工程大學(xué),河南鄭州 450001)

本文結(jié)合傳統(tǒng)T函數(shù)理論與非阿基米德T函數(shù)理論,深入研究T函數(shù)的性質(zhì)特點(diǎn),重點(diǎn)討論一致可微T函數(shù)的單圈性及最高位序列的保熵性.首次利用參數(shù)的概念建立傳統(tǒng)T函數(shù)理論中單字T函數(shù)單圈性判定條件與非阿基米德T函數(shù)理論中單圈性判定條件的聯(lián)系,說明了兩類判定條件的適用范圍.定義了對(duì)T函數(shù)生成序列進(jìn)行壓縮變換的保熵性概念,討論了一致可微T函數(shù)最高位序列的保熵性,說明了一致可微的T函數(shù)保熵性具有傳遞性,給出了T函數(shù)最高位序列保熵性的判定條件.

T函數(shù);一致可微;參數(shù);保熵性

1 引言

T函數(shù)是2002年由Klimov和Shamir在文獻(xiàn)[1]中提出的一類非線性函數(shù).由于具有計(jì)算速度快、密碼學(xué)性質(zhì)好、易于軟硬件實(shí)現(xiàn)等特點(diǎn),T函數(shù)被廣泛應(yīng)用于序列密碼、分組密碼等領(lǐng)域.特別是在流密碼設(shè)計(jì)中,T函數(shù)能代替線性移位寄存器(LFSR)作為初始亂源,從而克服了LFSR生成序列周期無法達(dá)到最大的缺陷.Klimov和Shamir在文獻(xiàn)[1～3]中利用參數(shù)的概念給出了T函數(shù)單圈性的判定條件,并提出基于T函數(shù)的流密碼設(shè)計(jì)方案.2004后,大量基于T函數(shù)設(shè)計(jì)的密碼算法開始涌現(xiàn),如eSTREAM計(jì)劃中提交的TSC[4],ABC[5],Mir[6]等密碼算法均采用T函數(shù),同時(shí)針對(duì)這些算法的攻擊方法也成為研究的熱點(diǎn).文獻(xiàn)[7～10]對(duì)T函數(shù)輸出序列的密碼學(xué)性質(zhì)進(jìn)行了深入研究,包括線性復(fù)雜度、k-錯(cuò)線性復(fù)雜度、自相關(guān)性和非線性度等安全性指標(biāo),研究表明T函數(shù)具有較好的安全性.

研究T函數(shù)的另一重要途徑是非阿基米德理論,Anashin在2-adic整數(shù)環(huán)中,定義了2-adic距離、范數(shù)、測(cè)度等概念,闡述了T函數(shù)即1-Lipchis函數(shù)(或稱為完備函數(shù)),而可逆T函數(shù)即可測(cè)函數(shù),單圈T函數(shù)即保測(cè)函數(shù)[11].同時(shí),分別利用一致可微性、馬勒插值級(jí)數(shù)和van der put級(jí)數(shù),給出了可逆T函數(shù)以及單圈T函數(shù)的的判定定理[12～15].2012年,Tao Shi,Anashin和DongDai Lin等人在該理論的基礎(chǔ)上,發(fā)現(xiàn)一致可微T函數(shù)的特定分位序列之間存在線性弱點(diǎn),并提出攻擊方法[16].2013年,他們又利用van der put級(jí)數(shù)作為工具,借鑒時(shí)間存儲(chǔ)折中的思想提出了兩類快速計(jì)算T函數(shù)的算法[17].

近年來,在T函數(shù)的單圈性判定方面,傳統(tǒng)T函數(shù)理論與非阿基米德理論均取得了豐富的成果,其中傳統(tǒng)理論主要是利用參數(shù)作為工具對(duì)T函數(shù)進(jìn)行研究,而非阿基米德理論則是借助T函數(shù)一致可微的性質(zhì)進(jìn)行研究,兩種理論各有特點(diǎn)、各有優(yōu)勢(shì).如果能將兩種理論結(jié)合起來對(duì)T函數(shù)的性質(zhì)進(jìn)行研究是非常有意義的,本文從這方面出發(fā)建立起兩種理論之間的聯(lián)系,為T函數(shù)的研究提供了新的思路.

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

首先,給出傳統(tǒng)意義下T函數(shù)的相關(guān)定義:

本文的研究重點(diǎn)為單字T函數(shù),故下文在不加說明的情況下,T函數(shù)均指單字T函數(shù).

另外,距離度量滿足強(qiáng)三角不等式:任意a,b∈Z2,有|a+b|2≤max{|a|2,|b|2},滿足這一特性的度量又被稱為超度量空間或非阿基米德度量空間.在該度量空間中,可以討論可微性,可導(dǎo)性,連續(xù)性,極限等性質(zhì).此時(shí),可以利用度量的概念給出1-Lipschitz函數(shù)的定義,即為單字T函數(shù)的定義.

定義5[11]若Z2→Z2上的函數(shù)f(x)對(duì)于任意u,v∈Z2,都有|f(u)-f(v)|2≤|u-v|2成立,則稱f(x)為2-adic整數(shù)環(huán)上的1-Lipschitz函數(shù).

f(x+h)≡f(x)+f′(x)·h(mod2ord2h+M)

具有上述特性的K=K(M)的最小值記為NM(f).

f(x+h)≡f(x)+f′(x)·h(mod2ord2h+M)

給定M,具有上述特性的K=K(M)的最小值記為NM(f),這里NM(f)的含義與定義7中的一致.

3 參數(shù)與一致可微

下面利用非阿基米德理論,對(duì)傳統(tǒng)T函數(shù)中的參數(shù)概念進(jìn)行深入研究,建立起非阿基米德理論中單圈性判定條件與傳統(tǒng)T函數(shù)理論中單圈性判定條件之間的聯(lián)系,首先,給出相關(guān)引理.

引理1[11]設(shè)f:Z2→Z2是模2一致可微T函數(shù),則其是可逆的當(dāng)且僅當(dāng)f模2NM(f)+1是可逆的.

引理2[11]設(shè)f:Z2→Z2是模4一致可微T函數(shù),則其是單圈的當(dāng)且僅當(dāng)f模2NM(f)+2是單圈的.

引理3[11]設(shè)f:Z2→Z2是模4一致可微單圈T函數(shù),則對(duì)任意x∈Z2,其導(dǎo)數(shù)滿足f′(x)≡1(mod2).

上述引理中,引理2基于非阿基米德理論給出了判定一類T函數(shù)是否為單圈T函數(shù)的方法,引理6基于傳統(tǒng)T函數(shù)理論給出了判定所有T函數(shù)是否為單圈T函數(shù)的方法.引理2的條件易于判定,但只對(duì)特殊的T函數(shù)成立;引理6的判定條件對(duì)所有的T函數(shù)成立,但考查其充要條件存在一定的困難.所以為了尋找更好的判定方法,我們通過研究傳統(tǒng)理論中參數(shù)的概念在非阿基米德理論中的含義,找出不同判定條件之間的聯(lián)系,給出不同判定條件的適用范圍.

定理1 T函數(shù)f(x)為Z2→Z2上的參數(shù)當(dāng)且僅當(dāng)f(x)模2一致可微,且對(duì)任意x∈Z2,滿足f′(x)≡0(mod2).

證明 充分性:由于f(x)模2一致可微,則存在正整數(shù)K,使得當(dāng)|h|2≤2-K(即h≡0mod2K)時(shí),對(duì)任意x∈Z2,滿足f(x+h)≡f(x)+f′(x)·h(mod2ord2h+1),又因?yàn)閷?duì)任意x∈Z2,有f′(x)≡0(mod2),則當(dāng)k≥K時(shí),令h=2k,得到f(x+2k)≡f(x)(mod2k+1),根據(jù)參數(shù)的定義知f(x)為參數(shù).

必要性:由于f(x)為參數(shù),則存在整數(shù)K,當(dāng)k≥K時(shí),有f(x+2k)≡f(x)(mod2k+1)成立,即對(duì)任意h≡0mod2K,有f(x+h)≡f(x)+0×h(mod2k+1)成立.則由一致可微的定義得,f為模2一致可微的,且對(duì)任意x∈Z2,f′(x)≡0(mod2).

定理1給出了參數(shù)在非阿基米德理論中的描述,建立了兩種理論之間的聯(lián)系,在此基礎(chǔ)上,我們將討論奇參數(shù)與偶參數(shù)的性質(zhì),并給出它們?cè)诜前⒒椎吕碚撝械拿枋?

定理2 若f:Z2→Z2是模4一致可微T函數(shù),且對(duì)任意x∈Z2,有f′(x)≡0(mod2)成立,則當(dāng)k≥N2(f)+2時(shí),f為偶參數(shù).

由偶參數(shù)的定義得,當(dāng)k≥N2(f)+2時(shí),f為偶參數(shù).

推論1 若T函數(shù)f:Z2→Z2為奇參數(shù),則f一定不是模4一致可微的.

定理1和定理2說明模4一致可微的參數(shù)一定是偶參數(shù),但偶參數(shù)不一定是模4一致可微的.推論1表明奇參數(shù)一定不是模4一致可微的,根據(jù)奇偶參數(shù)與一致可微性的關(guān)系,結(jié)合單圈T函數(shù)的判定定理,得到以下結(jié)論:

推論2 若存在正整數(shù)K,使得T函數(shù)g(x)=x+f(x)mod2K為單圈函數(shù),則g(x)是單圈T函數(shù)當(dāng)且僅當(dāng)f(x)是模4一致可微的,且對(duì)任意x∈Z2,有f′(x)≡0(mod2),同時(shí)滿足N2(f)≤K.

定理3 若單圈T函數(shù)f(x):Z2→Z2是模4一致可微的,則f(x)可以表示成f(x)=x+r(x)的形式,其中當(dāng)k≥N2(f)+2時(shí),r(x)為偶參數(shù).

證明 由于單圈T函數(shù)f(x):Z2→Z2是模4一致可微的,由引理3得f′(x)≡1(mod2),且當(dāng)|h|2≤2-N2(f)時(shí),對(duì)任意x∈Z2,下式成立:

f(x+h)≡f(x)+f′(x)·h(mod2ord2h+2)

令r(x)=f(x)-x,任取|h|2≤2-N2(f)(即h≡0mod2N2(f)),對(duì)任意x∈Z2,有:

r(x+h)≡f(x+h)-(x+h)≡f(x)+h·f′(x)-(x+h)

≡r(x)+h·(f′(x)-1)≡r(x)+h·r′(x)(mod2ord2h+2)

由f′(x)≡1(mod2),得到r′(x)≡0(mod2),且由一致可微的定義知r(x)為模4一致可微的.根據(jù)定理2,則當(dāng)k≥N2(f)+2時(shí),r(x)為偶參數(shù),得證.

定理1、定理2及推論1描述了傳統(tǒng)T函數(shù)理論中參數(shù)、奇參數(shù)和偶參數(shù)等概念與非阿基米德理論中一致可微性的關(guān)系,說明了參數(shù)均是模2一致可微的、模4一致可微的參數(shù)一定是偶參數(shù)、奇參數(shù)一定不具有模4一致可微性,這為進(jìn)一步研究T函數(shù)的性質(zhì)提供了理論支撐.同時(shí),結(jié)合已有的T函數(shù)單圈性判定方法,發(fā)現(xiàn)非阿基米德理論中利用一致可微性判定T函數(shù)單圈性的方法,部分適用于傳統(tǒng)理論中通過偶參數(shù)構(gòu)造的T函數(shù),而對(duì)基于奇參數(shù)構(gòu)造的T函數(shù),該判定方法不再適用,這為研究T函數(shù)的判定方法提供了新的工具.

4 T函數(shù)最高分位序列保熵性研究

由于T函數(shù)第i路輸出只與第0,…,i路輸入有關(guān),因此T函數(shù)所有輸出分位序列中最高分位序列包含的輸入信息最多.本節(jié)考察單圈T函數(shù)輸出的最高分位序列是否具有保熵性.

根據(jù)T函數(shù)的構(gòu)造方法和結(jié)構(gòu)特點(diǎn),不難發(fā)現(xiàn)任意單圈T函數(shù)輸出序列的最高分位序列可由多個(gè)不同的單圈T函數(shù)生成,故任意單圈T函數(shù)輸出序列的最高分位序列不具有保熵性.因此,我們將考察的范圍限制到具有某一特性的單圈T函數(shù).

引理7[15]設(shè)f(x):Z2→Z2是模4一致可微的T函數(shù),則其導(dǎo)數(shù)模4是周期函數(shù),且周期是2N2(f)的因子,即per{f′(x)(mod4)}|2N2(f).

xi+2j-1,j=xi,j?x2j-1,j?xi,j-1?x0,j?x0,j-1?y(i)(mod2)

從引理8的證明過程中,可以得到以下結(jié)論:

xi+2j-1,j=xi,j?xk+2j-1,j?xi,j-1?xk,j?xk,j-1?y(i)(mod2)

xi+2k-2,k-1=xi,k-1?xt+2k-2,k-1?xi,k-2

?xt,k-1?xt,k-2?α(i)(mod2)

yi+2k-2,k-1=yi,k-1?yt+2k-2,k-1?yi,k-2

?yt,k-1?yt,k-2?β(i)(mod2)

進(jìn)一步地,當(dāng)n=k+1時(shí),任意時(shí)刻i由推論3,有

xi+2k-1,k=xi,k?xt+2k-1,k?xi,k-1?xt,k

?xt,k-1?α(i)(mod2)

=yi+2k-1,k=yi,k?yt+2k-1,k?yi,k-1?yt,k

?yt,k-1?β(i)(mod2)

xi+2k-1+1=f(xi+2k-1)=f(xi+(xi+2k-1-xi))

=f(xi)+(xi+2k-1-xi)f′(xi)(mod2k)

yi+2k-1+1=g(yi+2k-1)=g(yi+(yi+2k-1-yi))

=g(yi)+(yi+2k-1-yi)g′(yi)(mod2k)

定理4說明對(duì)于一類模4一致可微且具有相似結(jié)構(gòu)(即相近的N2(f)值)的單圈T函數(shù),考察其中任意兩個(gè)不同的T函數(shù)能否生成相同的最高分位輸出序列只需考察當(dāng)輸入規(guī)模較小時(shí)(n=N2(f)+2),結(jié)論是否成立.

5 小結(jié)

本文研究了一致可微的單圈T函數(shù)的性質(zhì),首先通過討論參數(shù)概念在非阿基米德理論中的含義,給出了兩種理論中單圈T函數(shù)判定條件的聯(lián)系,說明了非阿基米德理論中的判定條件適用于部分由偶參數(shù)構(gòu)造的T函數(shù).另一方面,考察了單圈T函數(shù)最高分位輸出序列的保熵性,說明了一般T函數(shù)不具有保熵性,而對(duì)于模4一致可微且具有相似結(jié)構(gòu)的單圈T函數(shù),其最高分位序列保熵性等價(jià)于當(dāng)輸入規(guī)模較小時(shí)最高分位序列的保熵性,為研究具有相似結(jié)構(gòu)T函數(shù)的多樣性提供了理論基礎(chǔ).

[1]A Klimov,A Shamir.A new class of invertible mappings[A].CHES 2002[C].Berlin:Springer-Verlag,LNCS 2523,2003.470-483.

[2]A Klimov,A Shamir.Cryptographic applications of T-functions[A].SAC 2003[C].Berlin:Springer-Verlag,LNCS 3006,2003.248-261.

[3]A Klimov,A Shamir.New cryptographic primitives based on multiword T-functions[A].FSE 2004[C].Berlin:Springer-Verlag,LNCS 3017,2004.1-15.

[4]J Hong,D Lee,Y Yeom,D Han.A new class of single cycle t-functions[A].FSE 2005[C].Berlin:Springer,LNCS 3557,2005.68-82.

[5]V Anashin,A Bogdanov,I Kizhvtov,S Kumar.ABC:A new fast flexible stream cipher [EB/OL].http://www.ecrypt.eu.org/ stream,2005.

[6]A Maximov.A new stream cipher “Mir-1” [EB/OL].http://www.ecrypt.eu.org/stream,2005.

[7]N Kolokotronis.Cryptographic properties of nonlinear pseudorandom number generators[J].Designs Codes & Cryptography,2008,46:353-363.

[8]N Kolokotronis.Cryptographic properties of stream ciphers based on t-functions[A].ISIT 2006[C].USA:IEEE,2006.1604-1608.

[9]W Y Zhang,C K Wu.The Algebraic normal form,linear complexity and k-error linear complexity of single-cycle t-fFunction[A].SETA 2006[C].Berlin:Springer,LNCS 4086,2006.391-401.

[10]游偉,戚文峰.單圈T函數(shù)的2-adic復(fù)雜度及1-錯(cuò)2-adic復(fù)雜度[J].通信學(xué)報(bào),2014,35(3):135-139.

You Wei,Qi Wen-feng.The 2-adic complexity and the 1-error 2-adic complexity of single cycle T-functions[J].Journal on Communications,2014,35(3):135-139.(in Chinese)

[11]V Anashin.Non-Archimedean analysis,T-functions,and cryptography[EB/OL].http://arxiv.org/abs/cs/0612038,2006.

[12]V Anashin.Uniformly distributed sequences of p-adic integers[J].Mathematical Notes,1994,55(2):109-133.

[13]V Anashin.Uniformly distributed sequences of p-adic integers,II[J].Discrete Math Appl,2002,12(6):527-590.

[14]V Anashin.Pseudorandom number generation by p-adic ergodic transformations[EB/OL].http://arxiv.org/abs/cs.CR/0401030,January 2004.

[15]V Anashin,A Khrennikov,E Yurova.T-functions revisited:New criteria for bijectivity/transitivity[J].Designs Codes & Cryptography,2014,71(3):383-407.

[16]T Shi,V Anashin,D D Lin.Linear Weaknesses in T-functions[A].SETA 2012[C].Berlin:Springer-Verlag,LNCS 7280,2012.279-290.

[17]T Shi,V Anashin,D D Lin.Fast Evaluation of T-functions via Time-Memory Trade-Offs[A].Informations Security and Cryptology 2012[C].Berlin:Springer,LNCS 7763,2013.263-275.

[18]Huang M Q.Analysis and cryptological evaluation of primitive sequences over an integer residue ring[D].Beijing:Graduate School of USTC,1988.

[19]Dai Z D.Binary sequences derived from ML-sequences over rings I:periods and minimal polynomials[J].Journal of Cryptology,1992,5(3):193-207.

[20]Huang M Q,Dai Z D.Projective maps of linear recurring sequences with maximal p-adic periods[J].Fibonacci Quart,1992,30(2):139-143.

[21]A S Kuzmin,A A Nechaev.Linear recurring sequences over Galois rings[J].Algebra & Logic,1995,34(2):87-100.

王森鵬 男,1990年出生,河南商丘人.解放軍信息工程大學(xué)碩士生,主要研究方向:密碼學(xué)與信息安全.

E-mail:wsp2110@126.com

劉 燕(通信作者) 女,1990年出生,江蘇無錫人,解放軍信息工程大學(xué)碩士生,主要研究方向:密碼學(xué)與信息安全.

E-mail:awhxxsbb@126.com

On the Properties of T-functions with Uniform Differentiability

WANG Sen-peng,LIU Yan,HU Bin

(ThePLAInformationEngineeringUniversity,Zhengzhou,Henan450001,China)

Combining conventional theory with non-Archimedean theory,we study the properties of T-functions.We focus on the criteria of single cycle T-functions and entropy preservability of the most significant bit output sequence generated by T-functions.Utilizing the parameters,the connection between criteria of single cycle T-functions in two different theories is established.The situation each criterion is suited for is cleared.On the other hand,we define the notion of entropy preservability of T-functions.We talk about the entropy preservability of most significant bit output sequences generated by T-functions with uniform differentiability.We present the condition for entropy preservability of most significant bit output sequences and show the transitivity.

T-functions;uniform differentiability;parameter;entropy preservability

2015-03-12;

2016-02-01；責(zé)任編輯：馬蘭英

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

TN918.1

A

0372-2112 (2016)11-2676-06

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.11.016