文档介绍：第7章序列密码
序列密码又称流密码。它是将明文消息字符串逐位地加密成密文字符。
布尔函数
布尔函数的表示
真值表
小项表示
多项式表示
Walsh谱表示
设, ,x与w的点积定义为
,n元布尔函数f(x)的Walsh变换定义为
,其逆变换为
。称为的第一种谱或Walsh谱。
定义为f(x)的第二种谱或循环谱。
与关系如下:
设, ,f(x)是n元布尔函数,则
,这里P(.)表示概率。
布尔函数的非线性
定义 设f(x)是一个n元布尔函数,记为所有n元线性函数(包括仿射函数)之集。f(x)的非线性度定义为
记为Nf,即f(x)的非线性度为其与所有线性函数之最短距离,于是线性函数的非线性度为0。称为f(x)的线性度,记为Cf。即的线性度是f(x)与所有线性函数的最大距离。
定义 若l(x)使得,则称l(x)为f(x)的最佳线性逼近。
任意n元布尔函数f(x)的非线性度满足,使等式成立(即非线性度最高)的函数定义为Bent函数。
若对任意,有
,即是平衡函数,则称f(x)满足严格雪崩准则。若将f(x)的任意k个分量固定为常数,得到n-k的元函数均满足严格雪崩准则,则f(x)称满足k(0≤k≤n-2)阶雪崩准则。严格雪崩准则记为SAC,k阶雪崩准则记为SAC(k)。满足严格雪崩准则的函数称为SAC函数。
设,若是平衡函数,即
,则称f(x)关于α满足扩散准则。若对任意满足1≤w(α)≤k的α,f(x)关于α满足扩散准则,则称f(x)满足k次扩散准则。
布尔函数的相关免疫性
设是n个彼此独立,对称的二元随机变量的布尔函数,称f(x)是m阶相关免疫的,当且仅当z与中的任m个随机变量统计独立,或者,当且仅当互信息,
对任一组成立。
当m=1时,称f(x)是1阶相关免疫函数,或一般地称为相关免疫函数;当m≥2时,亦称f(x)为高阶免疫函数。
一个函数f(x)是相关免疫的,也说f(x)具有相关免疫性,或说f(x)满足相关免疫准则。
布尔函数不同性质之间的关系
一种性质表示了函数在某一应用中的性能,其量化便是这种性能的衡量指标,如非线性是密码系统中为抵抗线性攻击而提出的性能,非线性度则是衡量其非线性性能强弱的指标。若从这个意义上讲,非线性度越高越好,但非线性度达到最高的函数,其他性能将变弱。如当非线性度达到最高时,将失去相关免疫性。因此,研究不同性质之间的关系,特别是不同性能指标之间的数量关系是布尔函数研究中的一个重要课题。
多输出布尔函数
设是到的多输出布尔函数,令
则称D(F)为F(x)的代数次数。这里是n元布尔函数,deg( .)表示布尔函数的代数次数。当D(F)=k时,称F(x)为k次函数。