第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) =