《现代密码学》课件第3章_第1页
《现代密码学》课件第3章_第2页
《现代密码学》课件第3章_第3页
《现代密码学》课件第3章_第4页
《现代密码学》课件第3章_第5页
已阅读5页,还剩97页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

3.1频谱理论简介

3.2布尔函数的非线性准则

3.3相关免疫函数

3.4Bent函数及其性质第3章密码函数3.1频谱理论简介频谱理论被广泛地应用于数字信号处理、逻辑设计、模式识别、编码理论以及生物医学等领域。20世纪80年代,肖国镇和Massey首先将频谱技术应用于密码学的研究中[1],证明了布尔函数的相关免疫性的特征化定理;Rupple利用Walsh谱给出了最佳仿射逼近的方法,并用该方法分析了DES密码中的S盒[2];Blahut利用有限域上的离散傅立叶变换(DFT)证明了周期序列的线性复杂度等于它的一个周期的DFT的汉明重量[3],该定理在分析码的最小重量和码的最小距离限时起重要作用。20世纪80年代末,肖国镇和丁存生等系统地提出了基于频谱技术的序列密码的稳定性理论,对序列密码的分析与设计提出了一系列全新的概念[4]。冯登国的博士论文《频谱理论及其在通信保密技术中的应用》较全面地探讨了频谱理论在密码学中的应用[6]。近年来,国内外不少学者在频谱理论及其应用方面做了大量研究工作,从单输出函数到多输出函数,从布尔函数到多值函数,从线性逼近到高阶逼近等方面都有很好的成果。频谱技术在对密码函数的特征刻画以及密码分析方面显示出了独特的优越性。3.1.1布尔函数

n个变元的布尔函数f(x)是从GF(2)n到GF(2)的一个函数或映射,记作f(x):GF(2)n→GF(2)。由于此函数的输出只有两种取值,因此又被称为开关函数。

通常意义上的密码函数有多个取值,因此又称为多输出函数f(x):GF(2)n→GF(2)m,m∈Z+。它可以用一组布尔函数来表示,即

f(x)=(f1(x),f2(x),…,fm(x))

其中,每个fi(x)(i=1,2,…,m)是一个n元布尔函数。

布尔函数有多种表示形式,本节主要介绍真值表表示、小项表示和多项式表示。

1.真值表表示

n元函数的取值由自变量x=(x1,x2,…,xn)唯一确定。函数的真值表是指由函数自变量所有可能的取值及其对应的函数值所构成的表格。习惯上将自变量用二进制表示,并由小到大排列。此时将所有函数值构成的向量记作f,称为函数值矢量。f中1的个数称为函数f的汉明重量(HammingWeight),记作WH(f)。如果自变量取遍所有可能的2n个输入时,函数输出0与1的个数相等,即WH(f)=2n-1,则称f为平衡函数。

【例3-1】设f(x):GF(2)3→GF(2),其真值表如表3-1所示。表3-1中所表示的三元函数的函数值矢量为f=(01010110),重量WH(f)=4,是一个平衡函数。

2.小项表示对于xi,ci∈GF(2),定义

,则有

设整数c(0≤c≤2n-1)的二进制表示为c1c2…cn,约定

,则xc具有“正交性”,即:

因而有

(3-1)

式(3-1)称为函数f的小项表示,其中每一项f(c1,c2,…,cn)称为一个小项,这里的加指模2加。

【例3-2】表3-1中的布尔函数f(x)的小项表示为

(3-2)

3.多项式表示除了真值表表示和小项表示之外,布尔函数更为常见的表示方法是多项式表示。我们给n个变元所有可能的乘积项乘以GF(2)上的系数并相加,再按变元的升幂及下标的词典序写出,便可得到布尔函数多项式表示的一般形式如下:

(3-3)

式(3-3)称为f(x)的代数正规型,任一确定的布尔函数的代数正规型是唯一的。其中,乘积项

的次数为r,非零常数项的次数定义为0,而常数项0的次数定义为-∞。布尔函数f(x)的次数定义为f(x)的代数正规型中非零项的最大次数,记作f或deg(f)。当f=1时,称f为线性布尔函数;当f≥2时,称f为非线性布尔函数。在n元布尔函数f(x)的代数正规型的每一项中,变量xi(1≤i≤n)可能出现,也可能不出现,因而总共有2n种可能的项,而每一项的系数可以取值0或1,所以,n个变元的布尔函数共有个。

【例3-3】如果将代入式(3-2),则可将例3-2中的函数f(x)变形为GF(2)上的多项式。

3.1.2Walsh变换

1.Walsh变换的定义

定义3-1(Walsh变换)

设f(x):GF(2)n→GF(2),x=(x1,x2,…,xn),ω=(ω1,ω2,…,ωn)∈GF(2n),x与ω的点积定义为x·ω=ω1x1+ω2x2+…+ωnxn,简记作ω·x。则n个变元的布尔函数f(x)在点ω的第一种Walsh变换(线性Walsh谱)定义为

第二种Walsh变换(循环Walsh谱)定义为

定理3-1(反演公式)

两种Walsh变换的逆变换分别为

根据两种谱的定义以及(-1)f(x)=1-2f(x),易证明两种Walsh谱之间存在定理3-2所述的关系。

定理3-2

两种Walsh谱值之间满足:

2.Walsh谱的性质

1)平移性设f(x):GF(2)n→GF(2),对α∈GF(2)n,有

2)线性性设f(x):GF(2)n→GF(2),g(x):GF(2)n→GF(2),则

3)Parseval公式设f(x)是n元布尔函数,则

这个公式有时又被称为能量守恒定理。证明:

4)Plancheral公式

其中,WH(f)表示f的汉明重量,即集合{x∈GF(2)n|f(x)=1}中元素的个数。证明:

5)卷积性质设f(x):GF(2)n→GF(2),g(x):GF(2)n→GF(2),则

(3-4)

根据式(3-4)以及反演公式,可以得到如下的卷积定理。定理3-3

其中,f*f表示f与自身的卷积,即。

6)Wiener-Khinchin公式定义3-2设f(x):GF(2)n→GF(2),则称为函数f(x)的自相关函数。函数的Walsh谱值与自相关函数间存在如下关系:

(3-5)式(3-5)又被称为Wiener-Khinchin公式。以上结论的证明是比较容易的,这里只给出了Parseval公式和Plancheral公式的证明,其余留给读者作为练习。设f(x):GF(2)n→GF(2)在点ω的循环谱为S〈f〉(ω),则根据定义,有

从而

(3-6)

(3-7)这里,形式|{A}|表示集合A中的元素个数;P(f(x)=ω·x)表示f(x)与ω·x相等的概率。式(3-6)及(3-7)表明,Walsh谱本质上反映了布尔函数与线性函数之间的相关程度。

3.Walsh函数系

定义3-3(特征函数)

设G为有限Abel群,I为其单位元,U是所有模数为1的复数构成的乘法群。函数Φ:G→U,如果对g1,g2∈G,Φ满足则称Φ是G的一个特征函数。定义函数的乘法运算“·”为

(Φ1·Φ2)(g)=Φ1(g)Φ2(g)易验证G的所有特征函数的集合在函数的乘法运算下构成另一个Abel群,且。如果G=(g)为n阶循环群,则由下列函数组成:其中,,k=0,1,…,n-1,0≤j≤n-1。定义3-4(Walsh函数系)

设x=(x1,x2,…,xn),ω=(ω1,ω2,…,ωn)∈GF(2)n,x与ω的点积为ω·x,则函数系

Qω(x)=(-1)ω·x构成向量空间GF(2)n上的特征函数系,称为Walsh函数系。

Walsh函数系具有如下性质:

(1)对称性:Qω(x)=Qx(ω)(2)正交性:

上节介绍的反演公式实际上是将函数用Walsh函数系展开的结果。事实上,可以将函数的线性Walsh谱和循环Walsh谱用Walsh函数系分别表示为相应的反演公式分别为

(3-8)和

由式(3-8)可导出下列矩阵方程:矩阵方程右边的2n×2n阶矩阵称为n阶Hadamard矩阵,记作H(n)。它表示当x与ω取遍GF(2)n中的所有值时,Qω(x)的所有取值排列成的矩阵。

【例3-4】设,

则Hadamard矩阵可以用矩阵的Kronecher积“”迭代地定义为

Hadamard矩阵具有如下性质:

(1)根据Walsh函数系的对称性易知,H(n)是2n×2n阶对称矩阵。

(2)引入Hadamard矩阵后,Walsh函数系的正交性可表示为其中,为2n×2n阶单位阵。

(3)H(n)-1=2-nH(n)。3.1.3Chrestenson谱简介上节中介绍的Walsh谱是对布尔函数进行Walsh变换的结果,如果将函数的定义域和值域扩展到整数剩余类环,则需要引入Walsh的推广形式,即Chrestenson谱,简称柯氏谱。

定义3-5

设f(x):是从到ZN的多值逻辑函数,则f(x)在ω点的第一种柯氏谱(线性谱)定义为

(3-9)第二种柯氏谱(循环谱)定义为

(3-10)其中,ω,x∈

;ω·x表示ω与x的点积;

的共轭。式(3-9)和式(3-10)的反演公式分别为和

Walsh变换是柯氏变换的特殊情形,事实上,当N=2时,Chrestenson谱就是Walsh谱。柯氏谱具有与Walsh谱类似的性质:

(1)设f(x):,则这里|S〈f〉(ω)|表示复数S〈f〉(ω)的模。

(2)设V是的一个子空间,则其中,。

(3)设f1,f2:,f1*f2表示f1和f2的卷积,则

(4)设f1,f2:,则对任意的

,当且仅当f1=f2时,;当且仅当f1=f2时,。3.2布尔函数的非线性准则

研究并设计具有较好密码学性质的逻辑函数是对称密码学研究中的重要问题。序列密码设计的关键是利用非线性组合部分生成满足某些要求的好的密钥流序列,为了能使密钥流生成器抵抗已知的攻击方法,必须对非线性组合部分提出一些明确的安全性要求。非线性组合部分可以用逻辑函数实现,因此,序列密码的研究可以归结为逻辑函数的研究。在分组密码中,非线性部件S盒的设计是算法中最重要的部分。S盒本质上是一个非线性的代替表,也可以表示为非线性的逻辑函数。逻辑函数的密码学性质主要包括:非线性次数、非线性度(或相干度)、线性结构及退化性、相关免疫性、严格雪崩准则和扩散准则等几个方面。这些准则统称为函数的非线性准则。本节重点介绍非线性度、线性结构和严格雪崩准则,下一节详细讨论函数的相关免疫性。3.2.1函数的非线性度

定义3-6

设f(x):GF(2)n→GF(2),表示GF(2)上的所有线性布尔函数所组成的集合,布尔函数的非线性度定义为一个非负整数Nf:相应地,函数的线性度(或相关度)定义为非负整数Cf:其中,dH(f(x),l(x))表示f(x)与l(x)的汉明距离,在二元域中,有dH(f(x),l(x))=WH(f(x)+l(x))

由定义易知Nf+Cf=2n。函数的非线性度可以用其Walsh谱表示。定理3-4设f(x):GF(2)n→GF(2)的非线性度为Nf,则证明:设v∈GF(2),由于因此因而

推论3-1定理3-5任意n元布尔函数f(x)的非线性度Nf满足

。证明:由Parseval公式有

,从而,所以。当取最小值时,Nf达到最大值,此时对任意ω∈GF(2)n,均有,这类函数的非线性度最大,称为Bent函数。

定义3-7

设f(x):GF(2)n→GF(2),如果存在线性函数ω·x+v,ω∈GF(2)n,v∈GF(2),使得

取得最小值,则称ω·x+v是f(x)的一个最佳线性逼近。布尔函数的最佳线性逼近可能不是唯一的,在密码分析中人们需要的是汉明重量尽可能小的线性逼近。

Walsh谱值为函数的非线性度量提供了依据,利用Walsh谱也可以计算出布尔函数的最佳线性逼近,从而为密码分析提供帮助。Rueppel用信息论的方法推导出了用Walsh谱值描述的最佳逼近定理[2]。参考文献[7]中给出了用循环谱描述的逼近定理,并提出了利用循环谱求最佳线性逼近的方法。

定理3-6

令Pf(ω·x)为函数f(x)与线性函数ω·x相等的概率,则有

(3-11)

(3-12)

证明:根据循环Walsh谱的定义,有从而得到式(3-11),再由两种谱值的关系,可证明式(3-12)成立。由定理3-6易得到如下结论。

定理3-7

令则有:

(1)如果S〈f〉(ω)≥0,则ω·x为f(x)的最佳线性逼近,且符合(与f(x)相等)的概率为

(2)如果S〈f〉(ω)<0,则ω·x+1为f(x)的最佳线性逼近,且符合的概率为定理3-7事实上给出了求最佳线性逼近的算法。3.2.2线性结构与函数的退化性非线性度描述了布尔函数与线性函数的相似程度,线性函数是密码学意义上较弱的一类函数。另一类密码学意义上较弱的函数是具有线性结构的函数。

定义3-8

设f(x):GF(2)n→GF(2),α∈GF(2)n,如果对任意x∈GF(2)n,均有f(x+α)+f(x)=f(α)+f(0)则称α是f(x)的一个线性结构。当f(α)+f(0)=0时,称α为不变线性结构;当f(α)+f(0)=1时,称α为恒变线性结构。设f(x)的全体线性结构集为Uf,

表示不变线性结构全体,

表示恒变线性结构全体,则,且易验证Uf构成GF(2)n的一个线性子空间,而

构成Uf的线性子空间。对,有f(x+α+β)+f(x)=f(x+α+β)+1+f(x+α)=1所以

,从而有

。定理3-8

设α∈GF(2)n,则(i=0或1)当且仅当对任意ω∈GF(2)n且ω·α=i+1,有S〈f〉(ω)=0。证明:设,则由定义f(x+α)=f(x)+i,有当ω·α+i≠0,即ω·α=i+1时,有S〈f〉(ω)=0。反之,对任意α∈GF(2)n,由Walsh谱值的平移性,有S〈f(x+α)〉(ω)=(-1)ω·αS〈f〉(ω),而S〈f+i〉(ω)=(-1)iS〈f〉(ω)。当ω·α=i时,有S〈f(x+α)〉(ω)=S〈f+i〉(ω)。当ω·α≠i,即ω·α=i+1时,如果S〈f〉(ω)=0,则有S〈f(x+α)〉(ω)=S〈f+i〉(ω)=0,因此对一切ω∈GF(2)n,有S〈f(x+α)〉(ω)=S〈f+i〉(ω)。根据Walsh谱值的反演公式知,对任意x∈GF(2)n,f(x+α)=f(x)+i,所以。以下定理描述了

的结构,这里用〈A〉表示由集合A生成的线性子空间,〈A〉⊥表示A的正交子空间。

定理3-9

是由GF(2)n中循环Walsh谱值非零的元素构成的线性子空间的正交空间,即

证明:设,对ω∈GF(2)n,如果ω·α=1,则由定理3-8和S〈f〉(ω)=0,故对任意ω∈{ω∈GF(2)n|S〈f〉(ω)≠0},均有ω·α=0,所以α∈〈{ω∈GF(2)n|S〈f〉(ω)≠0}〉⊥由α的任意性知:反之,设α∈〈{ω∈GF(2)n|S〈f〉(ω)≠0}〉⊥,则对,均有ω·α=0,从而所以,对,即ω·α≠0,有而所以

,即S〈f〉(ω)=0,由定理3-8可知

引理3-1

设f(x):GF(2)n→GF(2)的非线性度为Nf,记NS(f)=|{ω∈GF(2)n|S〈f〉(ω)=0}|则证明:根据Parseval公式,有因而变形得由定理3-4知,,故

引理3-1表明,Nf越大,则非零谱值个数2n-NS(f)越多,因此从密码学意义上讲,应该尽量选择非线性度较大,或者非零谱值数目较多的函数。

定理3-10

设f(x):GF(2)n→GF(2)的线性结构集

,非线性度为Nf,记dimUf=k,则其中,dimUf表示向量空间Uf的维数。证明:由引理3-1知,证明上式等价于证明2n-NS(f)≤2n-k。由于

是k维线性子空间,若

,则

是一个k-1维线性子空间。在

中取线性无关的向量β1,β2,…,βk-1,再取

,易验证β1,β2,…,βk-1,βk在GF(2)上线性无关。又f(x)=f(x+β1)=f(x+β2)=…=f(x+βk-1)=1+f(x+βk)则因此,如果S〈f〉(ω)≠0,则β1·ω=…=βk-1·ω=1+βk·ω=0。由于β1,β2,…,βk-1,βk线性无关,因而此方程组有2n-k个解,从而|{ω∈GF(2)n|S〈f〉(ω)≠0}|=2n-NS(f)≤2n-k若

,则

。用类似方法可证明2n-NS(f)≤2n-k。定理3-10表明了线性结构和非线性度之间存在着一种制约关系。在密码函数的设计中,常常会考虑到函数与其变元之间的代数无关性,对于布尔函数f(x):GF(2)n→GF(2),若存在变元

,使得对一切α1,α2,…,αr∈GF(2),有则称f(x)与变元

代数无关,此时可以认为一个n元函数退化成为n-r元函数。函数退化性的精确定义如定义3-9。

定义3-9

设f(x):GF(2)n→GF(2),如果存在GF(2)上的一个k×n(k<n)阶矩阵D和GF(2)k到GF(2)上的一个函数g(y),使得f(x)=g(Dx)=g(y),则称f(x)是退化的,其中y=Dx。布尔函数的退化性对密码分析有着重要意义,可以减少密码分析的难度。下面是关于退化性的一些结论。

引理3-2

设f(x):GF(2)n→GF(2),若,则f(x)能退化为n-r元函数。证明:由于

是GF(2)n的线性子空间,进而是GF(2)n的加法子群,故GF(2)n可分解为其中,S为代表元集,|S|=2n-r。直接可验证f(x)在

的每个陪集上取值为常数。定义映射φ:S→GF(2)n-r,φ(β)=Dβ,其中D是由

的正交空间的一组基所构成的(n-k)×n阶矩阵,设β1,β2∈S,若φ(β1)=φ(β2),则D(β1-β2)=0,即,说明β1=β2,从而φ是单射,又|S|=2n-r=|GF(2)n-r|,故φ是双射。定义函数g(y):GF(2)n-r→GF(2),g(y)=f(φ-1(y)),则对任意的β∈S,有g(Dβ)=f(φ-1(Dβ))=f(β)。对任意的x∈GF(2)n,存在β∈S和使x=β+d,因此Dx=D(β+d)=Dβ。又f(x)在的每个陪集上取值为常数,所以f(x)=f(β)=g(Dβ)=g(Dx),即f(x)能退化为n-r元函数。

定理3-11

设f(x):GF(2)n→GF(2),f(x)的线性结构集为

,则

当且仅当f(x)能且至多能退化为n-k元函数。证明:设f(x)能且至多能退化为n-k元函数,则由定义3-9知,存在(n-k)×n阶矩阵D和函数g(y):GF(2)n-k→GF(2),使得对一切x∈GF(2)n,f(x)=g(Dx)=g(y),D的秩为n-k。令kerD={x∈GF(2)n|Dx=0},显然kerD是GF(2)n的一个线性子空间,且dim(kerD)=k。下证

。设

,则对任意的x∈GF(2)n,有f(x+α)=f(x),又f(x+α)=g(D(x+α))=g(y+Dα),f(x)=g(y)所以g(y+Dα)=g(y)。由于g(y)不能再退化,因此由引理3-2得Dα=0,即α∈kerD,故

反之,设,则由引理3-2知f(x)能退化为n-k元函数。再由充分性知,f(x)能且至多能退化为n-k元函数。定理3-11表明,布尔函数的退化性与线性结构有关。事实上,退化性的研究可以归结为线性结构的研究。3.2.3严格雪崩准则及扩散准则定义3-10设f(x):GF(2)n→GF(2),对于α∈GF(2)n,f(x)在α点的差分函数定义为Δf(x,α)=f(x+α)-f(x)其中,Δf(x,α)的取值分布称为f(x)在α点的差分分布;f(x)在所有点的差分函数值的分布统称为f(x)的差分分布。为了抵御差分分析,要求差分函数在其值域中取每个值的概率相等,对于布尔函数,即要求对任意的α∈GF(2)n,有或Δf(x,α)为平衡函数。这称为差分分布的均匀性。满足差分均匀性的函数又被称为完全非线性函数。

例3-5

设f(x):GF(2)3→GF(2),f(x)=x1x2+x3,令α=(011),则Δf(x,α)=x1+1是平衡函数,故f(x)在α点的差分分布是均匀的。差分分布的均匀性是一个过于强的性质,对于较复杂的函数,常常难以满足。下面我们对这一概念稍作弱化,考虑一类特殊差分分布的均匀性,称为雪崩与扩散。

定义3-11

设f(x):GF(2)n→GF(2),如果对任意e∈GF(2)n,且WH(e)=1,Δf(x,e)=f(x+e)+f(x)均为平衡布尔函数,则称f(x)满足严格雪崩准则SAC(StrictAvalancheCriterion)。如果一个函数满足严格雪崩准则,则当其输入改变一比特时,输出将有一半发生变化,这正是分组密码中S盒的设计准则之一。由定义知,函数f(x)满足严格雪崩准则,当且仅当对

e∈GF(2)n,WH(e)=1,自相关函数Rf(e)=0,又根据式(3-5),当且仅当。

定义3-12

设f(x):GF(2)n→GF(2),如果存在α∈GF(2)n,使得Δf(x,α)=f(x+α)-f(x)是一个平衡布尔函数,则称f(x)关于α满足扩散准则。如果对α∈GF(2)n,1≤WH(α)≤k,f(x)关于α满足扩散准则,则称f(x)满足k次扩散准则。

f(x)关于α满足扩散准则当且仅当Rf(α)=0或。

f(x)满足k次扩散准则当且仅当对任意的α∈GF(2)n,1≤WH(α)≤k,有Rf(α)=0或。由上述定义可见,差分均匀性是最强的条件,严格雪崩准则和扩散准则分别对差分函数Δf(x,α)中的α进行了不同程度的限制。严格雪崩准则实际上就是1次扩散准则,而满足k+1次扩散准则的函数一定满足k次扩散准则。若一个n元函数满足n次扩散准则,则它就是差分均匀函数,或完全非线性函数。下面的定理给出了函数满足严格雪崩准则的判别方法及构造方法。

定理3-12

设f(x):GF(2)n→GF(2),f(x)满足严格雪崩准则当且仅当对任意j∈{1,2,…,n},如果可将f(x)表示为其中,gj:GF(2)n-1→GF(2),hj:GF(2)n-1→GF(2)为n-1元布尔函数,则hj,j∈{1,2,…,n}都是平衡函数。证明:由于f(x)满足严格雪崩准则当且仅当对任意j∈{1,2,…,n},是平衡函数,故定理成立。

定理3-13

若f(x)满足严格雪崩准则(或k次扩散准则),l(x)为仿射函数,则f(x)+l(x)也满足严格雪崩准则(或k次扩散准则)。有关严格雪崩准则和扩散准则的进一步研究请参阅参考文献[10]和[11]。3.3相关免疫函数3.3.1定义定义3-13设f(x):GF(2)n→GF(2),x1,x2,…,xn是取值在GF(2)上的独立、均匀分布的随机变量,如果对(a1,a2,…,am)∈GF(2)m,m≤n及a∈GF(2),均有则称f(x)与变元

统计无关。如果f(x)与x1,x2,…,xn中的任意m个都统计无关,则称f(x)是m阶相关免疫函数。如果f(x)是t阶相关免疫函数,但不是t+1阶相关免疫函数,则称f(x)的相关免疫阶为t。研究相关免疫函数的方法主要有三种:频谱方法[1]、代数方法[12]和重量分析法[13]。本节介绍频谱方法的主要结论。以下定理给出了函数f(x)与其变元

统计无关的一些等价条件。

定理3-14

设f(x)如定义3-13中所述,则下列三个条件等价:

(1)f(x)与

统计无关;

(2)

,1≤WH(ω)≤m,f(x)与ω·x统计无关;

(3)

,1≤WH(ω)≤m,f(x)+ω·x是平衡函数。证明:

(1)→(2),由相关免疫函数的定义直接可证。

(2)→(3),设对

,1≤WH(ω)≤m,f(x)与ω·x统计无关,则对i∈GF(2),从而故f(x)+ω·x是平衡函数。

(3)→(1),设对

,1≤WH(ω)≤m,f(x)+ω·x是平衡函数,对a,a1,a2,…,am∈GF(2),记因为由假设条件知,对于y∈GF(2)m+1,当y≠(0,0,…,0)或y≠(1,0,…,0)时,有所以又因而由上述两式得NA×2m=Na,即因此,f(x)与变元

统计无关。

定理3-15

设f(x)如定义3-13中所述,1≤m<n,则f(x)与变元

统计无关当且仅当对任意的

,1≤WH(ω)≤m,S〈f〉(ω)=0。

证明:由定理3-14知,f(x)与变元

统计无关当且仅当对任意

,1≤WH(ω)≤m,f(x)+ω·x是平衡函数,而f(x)+ω·x是平衡函数当且仅当S〈f〉(ω)=0,从而证明了定理。由以上两定理直接可得到如下结论。

定理3-16

设f(x)如定义3-13中所述,则下列三个条件等价:

(1)f(x)是m阶相关免疫函数;

(2)对任意的ω∈GF(2)n,1≤WH(ω)≤m,f(x)与ω·x统计无关;

(3)对任意的ω∈GF(2)n,1≤WH(ω)≤m,f(x)+ω·x是平衡函数。

定理3-17

设f(x)如定义3-13中所述,则f(x)是m阶相关免疫函数当且仅当对任意的ω∈GF(2)n,1≤WH(ω)≤m,S〈f〉(ω)=0。由定理3-17及两种谱值的关系易证得以下定理[1]。

定理3-18(Xiao-Massey)

设f(x)如定义3-13中所述,则f(x)是m阶相关免疫函数当且仅当对任意的ω∈GF(2)n,1≤WH(ω)≤m,Sf(ω)=0。

定理3-19

设f(x):GF(2)n→GF(2),f(x)=k,如果f(x)是m阶相关免疫的,则k+m≤n。定理3-19表明函数的相关免疫阶与其代数次数之间存在相互制约的关系。此外,相关免疫阶与函数的非线性度间也存在着制约关系,如下述定理。

定理3-20

设f(x):GF(2)n→GF(2),f(x)的相关免疫阶为m,非线性度为Nf,f(x)的汉明重量为WH(f(x))=2mk0(k0为非负整数),则存在正整数a,使得当k0为偶数时,a可取为偶数;k0为奇数时,a可取为奇数。3.3.2相关免疫函数的构造相关免疫函数主要有两种构造方法:频谱方法和代数方法。本节只讨论一阶相关免疫布尔函数的构造方法,主要内容来自单炜娟用代数方法研究相关免疫函数的结论[7]。

定理3-21

设f(x):GF(2)n→GF(2)和g(x):GF(2)n→GF(2)均为m阶相关免疫函数,且g(x)f(x)=0,则f(x)+g(x)也是m阶相关免疫的。证明:利用Walsh谱值的线性性和Xiao-Massey定理易证。以下将布尔函数用小项表示。设c∈GF(2)n,如果x=c,则xc=1,否则xc=0。如果n元布尔函数f(x)的重量为w,f-1(1)={c1,c2,…,cw},ci∈GF(2)n,i=1,2,…,w,则f(x)的小项表示如下:此时称w个向量c1,c2,…,cw为f(x)的特征向量,称w×n阶矩阵为f(x)的特征矩阵。

定理3-22

设f(x):GF(2)n→GF(2),则f(x)为m阶相关免疫函数的必要条件是WH(f)=2mkk≥0

证明:设WH(f)=w,f(x)的小项表示为其中,x=x1x2…xn;ci=ci1ci2…cin,i=1,2,…,w。

令y=x1…xm,z=xm+1…xn,则可将f(x)的小项表示按y合并同类项,得到f(x)的另一种表示:其中,d∈GF(2)m,ei(d)∈GF(2)n-m。由于如果f(x)是m阶相关免疫的,那么对任一d∈GF(2)m,都有P(f=1)=P(f=1|y=d),即,这等价于WH(f)=2mh(d)。令h(d)=k为常函数,则定理得证。由定理3-22易得以下结论。引理3-3n元函数f(x)是一阶相关免疫函数的充要条件是:WH(f)=2k且f(x)的特征矩阵C(f)的每个列向量中0和1各占一半。引理3-4f(x)是重量为2的一阶相关免疫函数当且仅当f(x)可表示为

,其中c∈GF(2)n,,1≤i≤n,即是c的共轭向量。

定理3-23

重量为2的n元一阶相关免疫函数共有2n-1个,且都可表示为

。由定理3-21和定理3-23知,如果从GF(2)n-1中取出所有互不共轭的2n-1个向量,再从这些向量中任取k个,设其为c1,c2,…,ck,那么函数是一阶相关免疫的,且重量为2k。由于f=0也是一阶相关免疫的,因此用这种方法可以构造出个一阶相关免疫函数。其中重量为2k的有个。定理3-24n元一阶相关免疫函数至少有2n-1个。3.4Bent函数及其性质

Bent函数由Rothaus于1976年提出[14],最初被用于扩频通信中的信息保护。由于Bent函数具有较好的密码学性质,如差分均匀性、最大非线性度等,因此在密码领域得到了较为深入的研究,并在密码设计和信号检测等领域有广泛的应用。3.4.1定义及性质定义3-14设f(x):GF(2)n→GF(2),如果对任意ω∈GF(2)n,均有,则称f(x)为Bent函数。显然,只有当n为偶数时,f(x)才能成为Bent函数。根据3.2.1节的讨论知,n个变元的Bent函数的非线性度为。

定理3-25

设f(x):GF(2)n→GF(2),Rf(τ)为f(x)的自相关函数,则f(x)是Bent函数当且仅当由于Rf(τ)=0当且仅当f(x+τ)+f(x)是一个平衡函数,因此由定理3-25易得定理3-26。

定理3-26

设f(x):GF(2)n→GF(2),则f(x)是Bent函数当且仅当对所有的τ∈GF(2)n,τ≠0,f(x+τ)+f(x)是平衡函数。下面是Bent函数研究中常用到的一个基本结论。

定理3-27

设f(x):GF(2)n→GF(2),Ln为所有GF(2)n→GF(2)的线性函数集合,则f(x)是Bent函数当且仅当对任意l(x)∈Ln,f(x)+l(x)是Bent函数。证明比较简单,留给读者练习。3.4.2Bent函数的构造

定理3-28(MaioranaMcFarland构造)[15]设n为偶数,则f(x)=x1x2+x3x4+…+xn-1xn是n个变元的Bent函数。

定理3-29

设f(x):GF(2)n→GF(2),A是GF(2)上的n×n阶可逆矩阵,b∈GF(2)n,令g(x)=f(xA+b),则g(x)也是n个变元的Bent函数。

证明:因为所以g(x)是Bent函数。定理3-29中的f(x)和g(x)称为相互等价的Bent函数。

定理3-30

设f(x)是任意n元布尔函数,则是2n元Bent函数。证明:由于因此这就证明了g(x)是2n元Bent函数。定理3-30实际上给出了一大类Bent函数,有较强的实际意义。

定理3-31

,设Γ

{1,2,…

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论