第7章序列密码 序列密码又称流密码。它是将明文消息字符 串逐位地加密成密文字符
第7章 序列密码 序列密码又称流密码。它是将明文消息字符 串逐位地加密成密文字符
7.1布尔函数 7.1.1布尔函数的表示 口真值表 口小项表示 口多项式表示 口Wash谱表示
7.1 布尔函数 7.1.1 布尔函数的表示 真值表 小项表示 多项式表示 Walsh谱表示
口定义71设x=(x2…x)=(mn…,n)∈GF(),X 与W的点积定义为xw=x1+…+xnn∈GF(2) ,n元布尔函数f(x)的 Walsh变换定义为 S(m)=2"∑(-1y“f(x),其逆变换为(x)=2-2s;(mx-D x w)w∈GF(2))称为的第一种谱或 Walsh谱 口定义72定义S(m)=2"(-)(-)为f(x)的 第二种谱或循环谱
定义7.1 设 , ,x 与w的点积定义为 ，n元布尔函数f(x)的Walsh变换定义为 ，其逆变换为 。 称为的第一种谱或Walsh谱。 定义7.2 定义 为f(x)的 第二种谱或循环谱。 ( , , ) 1 n x = x x n w (w , ,wn ) GF(2) = 1 (2) x w = x1 w1 ++ xn wn GF − = − = − 2 1 0 ( ) 2 ( 1) ( ) n x n w x f S w f x − = − = − 2 1 0 ( ) 2 ( )( 1) n w w x f n f x S w ( )( (2) ) n S f w wGF − = − = − − 2 1 0 ( ) ( ) ( ) 2 ( 1) ( 1) n x n f x w x S f w
口定理71S(m)与S/(m)关系如下: 2S/()2W≠0 ()()= 2S,(v),w=0 是n元布尔函数,则P(w、1+Sm(x) 口定理72设x=(x12…,x),=(m"…m)∈GF(2), 2 P(f(x)≠wx)= So(w) 2,这里P()表示概率
定理7.1 与 关系如下： 定理7.2 设 ， ，f(x) 是n元布尔函数，则 ，这里P(.)表示概率。 ( ) S( f ) w S (w) f − = − = 1 2 ( ), 0 2 ( ), 0 ( ) ( ) S w w S w w S w f f f ( , , ) 1 n x = x x n w (w , ,wn ) GF(2) = 1 2 1 ( ) ( ( ) ) S( ) w P f x wx + f = = 2 1 ( ) ( ( ) ) S( ) w P f x wx − f =
7.1.2布尔函数的非线性 口定义73设f(x)是一个n元布尔函数,记L 为所有n元线性函数(包括仿射函数)之集。 f(x)的非线性度定义为 min d(, 7) min w(f+ D) leLn{x1∈Lnx 记为N,即f(X)的非线性度为其与所有线性 函数之最短距离,于是线性函数的非线性度 为0。称为f()的线性度,记为C。即 的线性度是f(X)与所有线性函数的最大距离 口定义74若|(x)使得,则称|(x)为 f(x)的最佳线性逼近=N
7.1.2 布尔函数的非线性 定义 7.3 设f(x)是一个n元布尔函数，记 为所有n元线性函数（包括仿射函数）之集。 f(x)的非线性度定义为 记为Nf，即f(x)的非线性度为其与所有线性 函数之最短距离，于是线性函数的非线性度 为0。称 为f(x)的线性度，记为Cf。即 的线性度是f(x)与所有线性函数的最大距离。 定义 7.4 若l(x)使得 ，则称l(x)为 f(x)的最佳线性逼近。 L [x] n min ( , ) min ( ) [ ] [ ] d f l w f l l L x l L x n n = + max ( , ) [ ] d f l l L x n N f d( f ,l) =
口定理73任意n元布尔函数f(x)的非线性度满 足N≤2n1-23,使等式成立(即非线性度最高)的 函数定义为Ben函数。 口定义75若对任意e=(e1;…c)∈GF(2)",w(c)=1,有 W((x)+f(x+c)=2",即f(x)+f(x+c)是平衡函数,则 称f(×)满足严格雪崩准则。若将f(×)的任意k个分 量固定为常数,得到n-k的元函数均满足严格雪崩 准则,则f(x)称满足k(0≤k≤n2)阶雪崩准则。严 格雪崩准则记为SAC,k阶雪崩准则记为SAC(k) 满足严格雪崩准则的函数称为SAC函数
定理7.3 任意n元布尔函数f(x)的非线性度满 足 ，使等式成立（即非线性度最高）的 函数定义为Bent函数。 定义7.5 若对任意 ，有 ，即 是平衡函数，则 称f(x)满足严格雪崩准则。若将f(x)的任意k个分 量固定为常数，得到n-k的元函数均满足严格雪崩 准则，则f(x)称满足k(0≤k≤n-2)阶雪崩准则。严 格雪崩准则记为SAC，k阶雪崩准则记为SAC(k)。 满足严格雪崩准则的函数称为SAC函数。 1 1 2 2 2 − − − n n N f c = (c1 , ,c ) GF(2) ,w(c) = 1 n n 1 ( ( ) ( )) 2 − + + = n w f x f x c f (x) + f (x + c)
口定义76设a∈GF(2),a≠0,若f(x)+f(x+a)是 平衡函数,即w(f(x)+f(x+a)=2n 则称f(x)关于α满足扩散准则。若对任意 满足1≤w(a)≤k的α,f(x)关于α满足扩 散准则,则称f(ⅹ)满足k次扩散准则
定义7.6 设 ，若 是 平衡函数，即 ，则称f(x)关于α满足扩散准则。若对任意 满足1≤w(α)≤k的α ，f(x)关于α满足扩 散准则，则称f(x)满足k次扩散准则。 (2) , 0 n GF f (x) + f (x +) 1 ( ( ) ( )) 2 − + + = n w f x f x
7.1.3布尔函数的相关免疫性 口定义77设:=f(x12…,x,是n个彼此独立,对称的二 元随札变量的布尔函数,称f(X)是m阶相关免疫的, 当且仅当z与中的任m个随机变量 统 计独立,或者,当且仅当互信息 (z;x,2,x,)=0 对任一组 成立 口当m=1时,称(x)是阶相类免疫函数,或一般地 称为相关免疫函数;当m≥2时,亦称f(X)为高阶 免疫函数。 口一个函数f(x)是相关免疫的,也说f()具有相关免一 疫性,或说f(x)满足相关免疫准则
7.1.3 布尔函数的相关免疫性 定义7.7 设 是n个彼此独立，对称的二 元随机变量的布尔函数，称f(x)是m阶相关免疫的， 当且仅当z与 中的任m个随机变量 统 计独立，或者，当且仅当互信息 ， 对任一组 成立。 当m=1时，称f(x)是1阶相关免疫函数，或一般地 称为相关免疫函数；当m≥2时，亦称f(x)为高阶 免疫函数。 一个函数f(x)是相关免疫的，也说f(x)具有相关免 疫性，或说f(x)满足相关免疫准则。 ( , , ) 1 n z = f x x n x , , x 1 i im x , , x 1 ( ; , , ) 0 1 = i im I z x x xi xi i i m n m , , ,1 1 1
7.1.4布尔函数不同性质之间的关系 口一种性质表示了函数在某一应用中的性能, 其量化便是这种性能的衡量指标,如非线性 是密码系统中为抵抗线性攻击而提出的性能, 非线性度则是衡量其非线性性能强弱的指标。 若从这个意义上讲,非线性度越高越好,但 非线性度达到最高的函数,其他性能将变弱。 如当非线性度达到最高时,将失去相关免疫 性。因此,研究不同性质之间的关系,特别 是不同性能指标之间的数量关系是布尔函数 研究中的一个重要课题
7.1.4 布尔函数不同性质之间的关系 一种性质表示了函数在某一应用中的性能， 其量化便是这种性能的衡量指标，如非线性 是密码系统中为抵抗线性攻击而提出的性能， 非线性度则是衡量其非线性性能强弱的指标。 若从这个意义上讲，非线性度越高越好，但 非线性度达到最高的函数，其他性能将变弱。 如当非线性度达到最高时，将失去相关免疫 性。因此，研究不同性质之间的关系，特别 是不同性能指标之间的数量关系是布尔函数 研究中的一个重要课题
7.1.5多输出布尔函数 口定义78设F(x)=(1(x)…fn(x)是GF(2到F(2)"的 多输出布尔函数,令 D(F)=mim{egB,F|B≠0B∈GF2y = min deg(∑b(x)1(n…,bn)=B≠0.(b…bn)∈GF(2y 则称D(F为F(x)的代数次数。这里f(x)≤ism) 是n元布尔函数,deg(.)表示布尔函数的 代数次数。当D(F)=k时,称F(x)为k次函 数
7.1.5 多输出布尔函数 定义7.8 设 是 到 的 多输出布尔函数，令 则称D(F)为F(x)的代数次数。这里 是n元布尔函数，deg( ．)表示布尔函数的 代数次数。当D(F)=k时，称F(x)为k次函 数。 ( ) ( ( ), , ( )) 1 F x f x f x = m n GF(2) m GF(2) min{deg( ( )) | ( , , ) 0,( , , ) (2) } ( ) min deg( | 0, (2) 1 1 1 = = = = m i m i i m m m b f x b b b b G F D F F G F f (x)(1 i m) i