流密码中的单圈T-函数

何元禹

0 引言

密码学已经成为能通过其技术提供安全电子商务和电子交易、安全通信、安全支付和保护市民秘密的关键[1]。可逆映射在密码学中应用广泛，如：用作分组密码的轮函数；帮助流密码[2]减少熵漏；为杂凑函数提供扩散与碰撞的生成器[3]等。2002年，Klimov和Shamir[4]提出了一类新的可逆映射，即可逆的 T-函数。T-函数最初应用在分组密码[5-6]，后来应用于流密码[7-8]和Hash函数[6]。Klimov和Shamir[4-6]认为T-函数还可以应用于伪随机数产生器、拉丁方和MDS映射的构造。特别地，他们指出单圈T-函数将取代流密码体制中的线性反馈移位寄存器（LFSR）。

单圈函数在流密码中非常重要。流密码主要由一个状态转移函数和一个非线性滤波器组成。状态转移函数的周期越大越好，所以理想的状态转移函数应是单圈函数。基于LFSR的流密码包括若干LFSR和一个非线性滤波器。

其中，LFSR生成具有最大周期的m序列。LFSR在硬件中运算快，但在软件中运算慢。并且，由于 LFSR具有线性结构，LFSR很容易受到攻击。尤其是Courtois[9-10]等提出代数攻击后，基于 LFSR的流密码体制受到了极大的威胁。文献[11-13]研究了单圈 T-函数的线性复杂度、K-错线性复杂度等密码学性质，表明单圈T-函数生成的序列具有周期大、线性复杂度高以及稳定性好等特点。

ECRYPT(European Network of Excellence for Cryptology)流密码计划eSTREAM提交的流密码abc[14]、TSC[15]以及Mir-1[8]采用了单圈T-函数作为状态转移函数。这三个流密码使用了不同的单圈 T-函数。目前已知的长周期单圈 T-函数也仅这三种。一旦发现新的长周期单圈T-函数，就可以构造新的流密码。

1 单圈T-函数的研究现状

Klimov和Shamir[4-7]深入研究T-函数的性质及其在密码学中的应用。2005年，Klimov[5]在他的博士论文中详述了T-函数的性质，提出了T-函数是可逆函数、单圈函数的等价条件，给出了两种形式的单圈T-函数。

称 f为T-函数(T-function)。f是T-函数，即 f (x)的第i列[f(x) ]i仅依赖于x的前i列 [ x]1,2,…,i。

定义 2 文献[4]参数函数是形如 g (x1,x2, …,xa;α1,α2,…,αb)的函数，g的自变量分为输入变量和参数变量，用分号隔开。如果一个参数函数与输入变量无关，则称其为参数。

定义3 文献[4]g为参数函数，若∀α：g(x;α)=g(y ; α )⇔ x = y ，称g为参数可逆函数。

定理 1 文献[4]T-函数 f = ( f1, f2,… , fn)可逆当且仅当fi(1 ≤ i≤n)都是参数可逆函数。

定义 4 文献[6]若一个函数的导出图同构于一个单圈，称该函数为单圈函数。

在实际应用中，变量x的长度n不宜超过处理器的字长。因此，上述单圈T-函数所生成的序列的周期受到了限制。单圈T-函数能否像LFSR一样，通过组合几个不同周期的单圈 T-函数来增大整个生成器所产生的序列的周期。单圈 T-函数通过这种方式得到的周期等于其中最大的一个，并不能增大周期。目前，主要有三种方法增大T-函数的周期，分别由定理5、定理6和定理7给出。

定理5 文献[6]序列 { (x(i), k(i))} 的定义如下：

fi

其中iα是奇参数，即：

则 f是单圈函数。

Klimov[5]证明了如果将偶参数添加到if中，定理6中的T-函数仍是单圈函数。abc[14]采用了定理 5中的 T-函数，Mir-1[8]采用了定理6中的多变量单圈T-函数。2005年，J.Hong等[15]发现了第三种长周期的单圈 T-函数，并且用它设计了流密码TSC。

如果 S0是S的奇数次复合， Se是S的偶数次复合，那么f(x) = ( α(x) ⋅ So( x) ) ⊕ ( (～ α (x) )⋅ Se( x ))，是单圈T-函数。

2 单圈的广义T-函数

3 结语

本文介绍了单圈 T-函数的性质，概括了长周期单圈 T-函数已知的三种类型，推广了 T-函数的定义，有利构造新的长周期单圈 T-函数。关于单圈 T-函数以下几个问题值得进一步研究：如何构造更多的长周期单圈T-函数；如何将单变量 T-函数转化为多变量 T-函数。虽然 Klimov和 Shamir认为单圈 T-函数将取代流密码体制中的 LFSR，但采用单圈T-函数作为状态转移函数的流密码 abc、TSC和Mir-1均未进入eSTREAM第三阶段，单圈T-函数是否究竟将取代LFSR。

[1] 冯登国. NESSIE工程简介[J].信息安全与通信保密,2003(03)：1-4.

[2] 冯登国,裴定一.密码学导引[M].北京：科学出版社,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-函数输出序列的线性复杂度及稳定性[J].北京邮电大学学报， 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.