流密碼中的單圈T-函數(shù)

何元禹

0 引言

密碼學(xué)已經(jīng)成為能通過(guò)其技術(shù)提供安全電子商務(wù)和電子交易、安全通信、安全支付和保護(hù)市民秘密的關(guān)鍵[1]。可逆映射在密碼學(xué)中應(yīng)用廣泛，如：用作分組密碼的輪函數(shù)；幫助流密碼[2]減少熵漏；為雜湊函數(shù)提供擴(kuò)散與碰撞的生成器[3]等。2002年，Klimov和Shamir[4]提出了一類新的可逆映射，即可逆的 T-函數(shù)。T-函數(shù)最初應(yīng)用在分組密碼[5-6]，后來(lái)應(yīng)用于流密碼[7-8]和Hash函數(shù)[6]。Klimov和Shamir[4-6]認(rèn)為T-函數(shù)還可以應(yīng)用于偽隨機(jī)數(shù)產(chǎn)生器、拉丁方和MDS映射的構(gòu)造。特別地，他們指出單圈T-函數(shù)將取代流密碼體制中的線性反饋移位寄存器（LFSR）。

單圈函數(shù)在流密碼中非常重要。流密碼主要由一個(gè)狀態(tài)轉(zhuǎn)移函數(shù)和一個(gè)非線性濾波器組成。狀態(tài)轉(zhuǎn)移函數(shù)的周期越大越好，所以理想的狀態(tài)轉(zhuǎn)移函數(shù)應(yīng)是單圈函數(shù)。基于LFSR的流密碼包括若干LFSR和一個(gè)非線性濾波器。

其中，LFSR生成具有最大周期的m序列。LFSR在硬件中運(yùn)算快，但在軟件中運(yùn)算慢。并且，由于 LFSR具有線性結(jié)構(gòu)，LFSR很容易受到攻擊。尤其是Courtois[9-10]等提出代數(shù)攻擊后，基于 LFSR的流密碼體制受到了極大的威脅。文獻(xiàn)[11-13]研究了單圈 T-函數(shù)的線性復(fù)雜度、K-錯(cuò)線性復(fù)雜度等密碼學(xué)性質(zhì)，表明單圈T-函數(shù)生成的序列具有周期大、線性復(fù)雜度高以及穩(wěn)定性好等特點(diǎn)。

ECRYPT(European Network of Excellence for Cryptology)流密碼計(jì)劃eSTREAM提交的流密碼abc[14]、TSC[15]以及Mir-1[8]采用了單圈T-函數(shù)作為狀態(tài)轉(zhuǎn)移函數(shù)。這三個(gè)流密碼使用了不同的單圈 T-函數(shù)。目前已知的長(zhǎng)周期單圈 T-函數(shù)也僅這三種。一旦發(fā)現(xiàn)新的長(zhǎng)周期單圈T-函數(shù)，就可以構(gòu)造新的流密碼。

1 單圈T-函數(shù)的研究現(xiàn)狀

Klimov和Shamir[4-7]深入研究T-函數(shù)的性質(zhì)及其在密碼學(xué)中的應(yīng)用。2005年，Klimov[5]在他的博士論文中詳述了T-函數(shù)的性質(zhì)，提出了T-函數(shù)是可逆函數(shù)、單圈函數(shù)的等價(jià)條件，給出了兩種形式的單圈T-函數(shù)。

稱 f為T-函數(shù)(T-function)。f是T-函數(shù)，即 f (x)的第i列[f(x) ]i僅依賴于x的前i列 [ x]1,2,…,i。

定義 2 文獻(xiàn)[4]參數(shù)函數(shù)是形如 g (x1,x2, …,xa;α1,α2,…,αb)的函數(shù)，g的自變量分為輸入變量和參數(shù)變量，用分號(hào)隔開。如果一個(gè)參數(shù)函數(shù)與輸入變量無(wú)關(guān)，則稱其為參數(shù)。

定義3 文獻(xiàn)[4]g為參數(shù)函數(shù)，若?α：g(x;α)=g(y ; α )? x = y ，稱g為參數(shù)可逆函數(shù)。

定理 1 文獻(xiàn)[4]T-函數(shù) f = ( f1, f2,… , fn)可逆當(dāng)且僅當(dāng)fi(1 ≤ i≤n)都是參數(shù)可逆函數(shù)。

定義 4 文獻(xiàn)[6]若一個(gè)函數(shù)的導(dǎo)出圖同構(gòu)于一個(gè)單圈，稱該函數(shù)為單圈函數(shù)。

在實(shí)際應(yīng)用中，變量x的長(zhǎng)度n不宜超過(guò)處理器的字長(zhǎng)。因此，上述單圈T-函數(shù)所生成的序列的周期受到了限制。單圈T-函數(shù)能否像LFSR一樣，通過(guò)組合幾個(gè)不同周期的單圈 T-函數(shù)來(lái)增大整個(gè)生成器所產(chǎn)生的序列的周期。單圈 T-函數(shù)通過(guò)這種方式得到的周期等于其中最大的一個(gè)，并不能增大周期。目前，主要有三種方法增大T-函數(shù)的周期，分別由定理5、定理6和定理7給出。

定理5 文獻(xiàn)[6]序列 { (x(i), k(i))} 的定義如下：

fi

其中iα是奇參數(shù)，即：

則 f是單圈函數(shù)。

Klimov[5]證明了如果將偶參數(shù)添加到if中，定理6中的T-函數(shù)仍是單圈函數(shù)。abc[14]采用了定理 5中的 T-函數(shù)，Mir-1[8]采用了定理6中的多變量單圈T-函數(shù)。2005年，J.Hong等[15]發(fā)現(xiàn)了第三種長(zhǎng)周期的單圈 T-函數(shù)，并且用它設(shè)計(jì)了流密碼TSC。

如果 S0是S的奇數(shù)次復(fù)合， Se是S的偶數(shù)次復(fù)合，那么f(x) = ( α(x) ? So( x) ) ⊕ ( (～ α (x) )? Se( x ))，是單圈T-函數(shù)。

2 單圈的廣義T-函數(shù)

3 結(jié)語(yǔ)

本文介紹了單圈 T-函數(shù)的性質(zhì)，概括了長(zhǎng)周期單圈 T-函數(shù)已知的三種類型，推廣了 T-函數(shù)的定義，有利構(gòu)造新的長(zhǎng)周期單圈 T-函數(shù)。關(guān)于單圈 T-函數(shù)以下幾個(gè)問(wèn)題值得進(jìn)一步研究：如何構(gòu)造更多的長(zhǎng)周期單圈T-函數(shù)；如何將單變量 T-函數(shù)轉(zhuǎn)化為多變量 T-函數(shù)。雖然 Klimov和 Shamir認(rèn)為單圈 T-函數(shù)將取代流密碼體制中的 LFSR，但采用單圈T-函數(shù)作為狀態(tài)轉(zhuǎn)移函數(shù)的流密碼 abc、TSC和Mir-1均未進(jìn)入eSTREAM第三階段，單圈T-函數(shù)是否究竟將取代LFSR。

[1] 馮登國(guó). NESSIE工程簡(jiǎn)介[J].信息安全與通信保密,2003(03)：1-4.

[2] 馮登國(guó),裴定一.密碼學(xué)導(dǎo)引[M].北京：科學(xué)出版社,2001.

[3] Schnorr C P, Vaudenay S. Black Box Cryptanalysis of Hash Networks Based on Multipermutations[J].Eurocrypt, 1994(950)：94-94.

[4] Klimov A, Shamir A. A New Class of Invertible Mappings[J].LNCS,2002(2523)：470-483.

[5] Klimov A. Applications of T-functions in Cryptography[D].The State of Israel：Weizmann Institute of Science,2005.

[6] Klimov A,Shamir A.Cryptographic Applications of T-functions[J].LNCS,2003(3006)：248-261.

[7] Alexander Klimov, Adi Shamir. New Cryptographic Primitives Based on Multiword T-Functions[J]. LNCS,2004(3017)：1-15.

[8] Maximov A. A New Stream Cipher： Mir-1[DB/OL].[2005-01-10][2008-04-20] .http：//www.ecrypt.eu.org/stream.

[9] Courtois N, Meier W. Algebraic Attacks on Stream Ciphers with Linear Feedback[J]. Advances in Cryptology-Eurocrypt,2003(2656)：345-359.

[10] Courtois N. Fast Algebraic Attacks on Stream Ciphers with Linear Feedback[J]. LNCS ,2003(2729)：176-194.

[11] Nicholas Kolokotronis. Cryptographic Properties of Stream Ciphers based on T-functions [J].IEEE.ISIT 2006,9(14) ：1604-1608.

[12] Zhang Wenying, Wu ChuanKun. The Algebraic Normal form, Linear Complexity and K-error Linear Complexity of Single Cycle T-function[J].LNCS，2006，4086（2006）： 391-401.

[13] 趙璐,溫巧燕.單圈 T-函數(shù)輸出序列的線性復(fù)雜度及穩(wěn)定性[J].北京郵電大學(xué)學(xué)報(bào)， 2008,31(04)：62-65.

[14] Vladimir Anashin, Andrey Bogdanov, Ilya Kizhvatov, et al. ABC：A New Fast Flexible Stream Cipher[DB/OL].[2005-01-10][2008-04-20].http：//www.ecrypt.eu.org/stream.

[15] Hong J, Lee D H, Yeom Y, et al.A New Class of Single Cycle T-functions[J].LNCS,2005(3557)：68-82.