1
单圈 T-函数的线性复杂度及 k-错线性复杂度
1
赵璐, 温巧燕
北京邮电大学理学院,北京(100876)
zhaolu.nan@gmail.com
摘要:根据单圈 T-函数的基本性质,研究了基于单圈 T-函数的流密码的一些性质,得到单
字的单圈 T-函数前
t
2
位所构成序列的周期、线性复杂度及 k-错线性复杂度。对某类含有
p
2
个字的单圈 T-函数,给出了连续输出状态中的任一固定位所构成的序列以及前
t
2
位所构成
序列的周期、线性复杂度及 k-错线性复杂度,结果表明由 T-函数输出序列具有良好性质。
关键词:流密码,单圈 T-函数,周期,线性复杂度,k-错线性复杂度
中图分类号:TN911.22
1. 引 言
2002 年,Klimov 和 Shamir 在研究分组密码时发现了一类新的可逆函数 T-函数[11],随
后提出了 T-函数理论。T-函数由于具有计算速度快、密码学性质良好等特点而得到广泛应用,
先后被用于构造分组密码[8]、Hash 函数[8]、流密码[5]。T-函数结合了代数运算(加法、乘
法、减法、求相反数)、逻辑运算(与、或、非、异或)和左移位运算,增加了其抵抗代数
攻击的能力[9]。
字长为
m 的单圈 T-函数输出序列周期为 2
m
,可以用来代替流密码中的线性反馈移位寄
存器,于是单圈 T-函数输出序列的安全性成为了研究的重点。安全性强的序列不仅要有较
大的线性复杂度,还要有较好的稳定性,即要求在序列改变某些比特以后,不会引起序列线
性复杂度的大幅度下降。k-错线性复杂度可以理解为序列发生 k 个或更少的错误时,线性复
杂度最坏情况的度量。如果一个序列的安全性较好,则其 k-错线性复杂度应较大。本文主要
关心的是序列每个周期改变 k 个比特之后,使得新序列的线性复杂度严格小于原序列的线性
复杂度的最小 k 值(记为
()minerror
),以及此时的 k-错线性复杂度。
[6]中作者给出了单字的单圈 T-函数连续输出状态中的任一固定位所构成的序列以及某
类多字单圈 T-函数连续输出状态中任意固定变量的固定位所构成序列的线性复杂度。文献[7]
给出了任意单字单圈 T-函数按状态输出序列的线性复杂度和
minerror -错线性复杂度。我们
研究了任意单字单圈 T-函数按位输出的二元序列的线性复杂度与
minerror -错线性复杂度,
1
本课题得到教育部高校博士点基金项目资助(20040013007)
http://www.paper.edu.cn
评论0
最新资源