布尔函数的密码学性质(上)

布尔函数的密码学性质(上)

1流密码加密的方式n元布尔函数映射。其中F保密通信最简单的数学模型如图1所示。发方把明文x传到收方,为防止第三方截取需要加密。为此,发方和收方约定一对互逆的运算:加密运算E和去密运算D,ED=DE=I(恒等运算)。发方把明文x加密成密文y=Ex,然后把密文y传给收方。收方收到y之后,去密Dy=x恢复成明文x。密钥对{E,D}由收发方约定并严格保密。希望第三方在信道中截取到密文y之后很难恢复成明文x,更不能猜出密钥对{E,D}。自20世纪中期以来,加密的方式有很大的进步。随着密码攻击和破译方法不断被研究出来(线性攻击、相关攻击、代数攻击等),加密方法也需要不断改进,以抵抗各种攻击方式。但是,如图2所示的加密方式至今仍然是流密码体制中采用的基本方式。f把明文a加密成密文b=(b要选取n元布尔函数f,使得第三方在收到密文序列b之后,很难破译出明文a,即使收到多个密文也很难破译出密钥f。为此,需要f有许多特别的性质,以抵抗研制出来的各种攻击方式。这些性质叫做布尔函数的密码学性质(cryptographicproperties)。用Bn元布尔函数共有22定义、属性的界定以及密码学的相互联系本节介绍布尔函数各种密码学性质的数学定义、性质好坏的判别标准以及这些密码学性质的相互联系。关于这些密码学性质的详细论述可见文献[1,2]。2.1平衡n元布尔函数f=f(x平衡性是f作为密钥的一个基本要求。2.2代代相传数每个布尔函数f=f(x这个多项式的次数叫做布尔函数f的代数次数,表示成degf。degf≤1的布尔函数f(x2.3nlf大的培养函数作为密钥,人们希望布尔函数f与所有仿射函数的距离都愈“远”愈好。这里,可以定义两个n元布尔函数f,g∈Bf的非线性度nl(f)(nonlinearity)定义为f和所有仿射函数的距离的最小值,即特别地,nl(f)=0当且仅当f是仿射函数。希望nl(f)愈大愈好。nl(f)大的布尔函数用来抵抗线性攻击。问题是:n元布尔函数f的非线性度可能的最大值是多少?为了解决此问题,需要用数学工具:布尔函数的Walsh变换。这里x·y是y和x=(xWalsh变换是通信中的重要数学工具。比如说:对于f∈B所以f是平衡的当且仅当W对于每个f∈B即|W再由(1)式可知2.4多发性免疫度对于f∈B下面是AI(f)达到最大值的第一个例子。对于每个向量x=(x则n元布尔函数F:F达到最大代数免疫度:2.5密码学中的应用n元布尔函数f∈B以上介绍了布尔函数的一些重要的密码学性质和这些性质的最佳值。迄今为止,人们对每个个别的密码学性质,基本都已构作出该密码学性质达到最佳的许多布尔函数。而当前密码学中一个挑战性问题是构作具有多种良好密码学性质的布尔函数,以同时抵抗多种攻击方式。特别地,是否存在布尔函数,使得它的某些密码学性质同时达到各自的最佳值?研究布尔函数各种密码学性能之间的相互制约关系,也是密码学的一个重要数学问题。以下是这方面的一些基本结果。1)n元平衡布尔函数的代数次数≤n-1,即不可能达到最大次数n。2)AI(f)≤degf。这是一个乐观性的结果,即代数免疫度大的布尔函数,其代数次数也很大。证明是简单的:由于(f+1)f=f3)是否存在n元布尔函数f,它的非线性度和代数免疫度同时达到最佳值2008年以前,人们已构作了许多代数免疫度最优的n元布尔函数参见文献[4-8],并且对其中的某些函数可计算出它们的非线性度,结果为或者稍好一些。由斯特林公式可知,当疫度最优的布尔函数当中,还没有找到非线性度良好的函数。在下节介绍这方面研究工作的一个突破。3有限域f的及其限制2008年,Carlet和冯克勤则1)f是平衡的,并且代数次数degf=n-1(在平衡函数中次数达到最大);这是首次发现的一类平衡布尔函数,其代数免疫度和代数次数均达到最佳,同时非线性又优于前人的下界2关于定理1的证明:1)由f的构作方式知它是平衡的,对于以(3)式的方式给出的布尔函数,其代数次数为其中s(i)是i的二进制展开式的数字和,即对于i=a对于由(4)式给出的布尔函数,可以用拉格朗日插值公式给出形如(3)式的f的具体表达式。由于f平衡,必然c利用有限域F2010年,涂自然和邓映蒲猜想1(TD(k)猜想)设k≥2,1≤t≤2S定理2设n=2k,k≥2,0≤s≤2而f=f(x,y):F则f为Bent函数,并且当猜想TD(k)成立时,AI(f)=k。Bent函数的非线性达到最佳,但它不是平衡的,并且次数计算数据表明,Tu-Deng函数f′的非线性度(对于n为偶数情形)均比Carlet-Feng函数要好。但是Carlet420cb的k值Carlet-Feng1)阚海斌等人2)唐小虎等3)唐小虎等猜想2(TCT(k)猜想)设k≥2,1≤t≤2这里s(a)由(6)式定义,则对每个t(1≤t≤2定理4f(x,y)=g(xy),3)若TCT(k)猜想成立,则AI(f)=k。此外,对于2≤k≤8的情形,文献[16]还分析了f抵抗快速代数攻击的能力。定理5定义F(x,y):F1)F为n元平衡的布尔函数,degF=n-1;3)当猜想TCT(k)成立时,AI(F)=k。此外,文献[16]中还对较小的k值分析了F抵抗快速代数攻击的能力。注记:1)满足定理5中条件的函数u是存在的,见文献[18]或[19]。2)在估计nl(F)的下界时,文献[16]中用了更精细的计算方法,并且对于小的偶次数n作了计算,结果表明,nl(F)的确切值有一些优于前人。3)文