具有最大代数免疫阶弹性函数的构造

具有最大代数免疫阶弹性函数的构造 1 2 3曹 浩 ,魏仕民 ,焦胜军 ( 235000; 1. 安徽科技学院 理学院 , 安徽 凤阳 233100; 2. 淮北师范大学 , 安徽 淮北 )233000 3. 海军蚌埠士官学校 基础部 ,安徽 蚌埠 摘 要 :针对密码学中布尔函数的构造需求 ,利用布尔函数的谱示 ,分析了其在可逆变换下的不变性质 , 探讨了如何将布尔函数的多种性质需求达到最优 ,给出了一种构造具有最大代数免疫阶的弹性函数的构 造方法 。 关键词 :布尔函数 ;弹性函数 ;代数免疫阶 ( ) 中图分类号 : O 174. 4文献标识码 : A 文章编号 : 1673 - 8772 2010 06 - 0048 - 05 Con struction of Resilien t Boolean Function w ith M ax im um A lgebra ic Imm un ity 1 2 2CAO H ao, W E I Sh i - m in, J IAO Sheng - jun ( 1. Co llege of Sc ience, A nhu i Sc ience and Techno logy U n ive rsity, Fengyang 233100 , Ch ina; 2. H ua ibe i No r2 m a l U n ive rsity, H ua ibe i 235000 , Ch ina; 3. D ep a rtm en t of B a sic Cou rse s, B engbu N ava l Pe tty O ffice r A cadem y, )B engbu 233000 , Ch ina A b stra c t: The good cha rac te ristic s of Boo lean func tion dec ide the secu rity of c ryp tograp hy to a ce rta in exten t. Fo2 cu sing on con struc tion requ irem en ts of Boo lean func tion, h igh non linea ritie s, h igh a lgeb ra ic imm un ity and h igh re siliency o rde rs, comp rom ising of the se p rop e rtie s is exp lo red. U sing the sp ec tra l rep re sen ta tion of Boo lean func tion s, a con struc tion of re silien t Boo lean func tion s w ith m axim um a lgeb ra ic imm un ity is p ropo sed ba sed on stud ie s of c ryp tograp h p rop e rtie s inva riance unde r reve rsib le tran sfo rm a tion. Key word s:Boo lean func tion; R e silien t Boo lean Func tion; A lgeb ra ic Imm un ity 序列密码的安全性主要取决于密钥流生成器的设计 ,而密钥流生成器的输出通常由一个组合布尔函 数控制 ,因此 ,布尔 函 数 的 性 能 在 一 定 程 度 决 定 着 密 码 体 制 的 安 全 性 。近 年 来 , 一 种 新 的 密 码 攻 击 方 [ 1 ] 法 ———代数攻击通过构造并求解超定多元非线性方程组来求取初始密钥 ,对一些传统的密码体制构成 [ 2 , 3 ] 了很大的威胁 。作为一种新型有效的密码分析方法 ,代数攻击对布尔函数的设计也提出了新的标准 ,[ 4 ] 即代数免疫性 ,衡量布尔函数抵抗代数攻击的能力 ,它被定义为布尔函数 f或 f + 1 的最低次数的零化 () 函数的次数 ,而零化函数总是存在的 布尔函数的固有性质 。给定一个 n元布尔函数 f,分析者的目标就 [ 5 ] 是找到 f或 f + 1 的低次零化函数 。为抵抗代数攻击 ,函数的代数免疫阶不能太低 。研究代数免疫性与 其它密码学性质之间的关系 ,特别是它们之间相互制约的关系 ,对于全面把握布尔函数的密码学性质 ,提 高抵抗各种已知攻击的能力 ,具有重要的理论意义和应用价值 。 1 布尔函数的密码学性质n 记二元有限域 F= { 0 , 1 } , n元布尔函数 f是一个从 F到 F的映射 , n元布尔函数的全体记为 B。 n 2 2 2 n 收稿日期 : 2010 - 06 - 12 ( ) ( ) 基金项目 : 国家自然科学基金资助项目 60573026 ;安徽省教育厅自然科学研究项目 KJ2010B059 ; 安徽科技学院引进人才资助项目( ) ( ) ZRC2008169 ; 安徽科技学院安徽省自然科学基金项目预研项目 ZRC2011274 。 ( ) 作者简介 : 曹浩 1981 - ,男 ,安徽省宿州市人 ,硕士 ,讲师 ,主要从事信息安全研究 。 第 25卷第 1期曹 浩 ,等 具有最大代数免疫阶的一阶弹性函数的构造49 ( )F上的多项式唯一地表示为 : 元布尔函数 f x可以用 2 ) + ρ ax+ ρ( axx++ axxxf x, x, K, x= a i i i, j i j 1 , 2 , , n 1 2n1 2 n 01 ? i?n 1 ? i < j?n ( )( )F内求和 , a, a, a,, a这里 ?是在 ?F,称为 f x的代数标准型 , f x的代数标准型中非 2 0 1 i, j 1 , 2 ,, n 2 ( )( ) ( ) ( )零最高次项的次数称为 f x的次数 ,记为 deg f。如果 deg f= 1 ,称 f x为仿射函数 ,所有仿射函数的 ( ) 全体记为 L。 f x的非线性度定义为n ( ( ) ( ) ) ( ) N= m in{ d f x, l x| l x?L}f n n ( ( ) ( ) ) ( ) ( ) ( ( ) ( ) ) 这里 d f x, l x= { x?{ 0 , 1 }| f x? l x} = w t f x+ l x 布尔函数的许多密码学性质通常用循环普研究 , f的循环谱定义为( ) - n n f x+ w x () ( )() - 1 Sw = 2 ρ w ?{ 0 , 1 } f nx?{ 0 , 1 } 布尔函数的非线性度和循环谱之间有如下重要关系 : n - 1 n () ( )N= 2 1 - m ax{ | Sw | , w ?{ 0 , 1 } } f f n () ) (() 如果 Sw = 0对所有 w = w, w, , w?{ 0 , 1 } 且 1 ?w t w ?m 都成立 ,则称 f是 m 阶相关免 f 1 2 n (), w中 1出现的个数 ,即 w 的重量 。平衡 m 阶相关免疫函数 f称为 m疫函数 ,这里 w t w 是指 w, w, n 1 2 阶弹性函数 。n ( ) ( ) 设 f, g?B, g称为 f的零化多项式 ,如果对任意的 x?{ 0 , 1 } 都有 f x〃g x= 0成立 。 f的零化多 n ( ) 项式的集合记为 A nn f, f的代数免疫阶定义为 : ( ) ( ) ( ) ( ) A If= m in{ deg g| g?A nn f? A nn 1 + f且 g?0 } 流密码设计中 ,为了抵抗各种攻击 ,密码学家在设计密钥流生成器时用到的组合布尔函数必须具备良 好的密码学性质 ,如高相关免疫阶 、高非线性度以及高代数免疫阶等 。然而 ,这些性质之间可能是相互制 () 约的 ,因此 ,设计具有良好密码学性质 取得这些性质的折中 的布尔函数 ,是密码设计者们最为关心的 。 2 布尔函数在可逆变换下的不变性质 定义 1 设 A = { 1 , 2 ,, n} ,一一映射 p: A ?A 称为集合 A 上的一个置换 。如果存在 a, b?A ,满足 ( ) ( )( ) p a= b 和 p b = a, 而 A 中其它任何元素 c在 p 下保持不变 ,即 p c= c,则称 p 是 A 上的一个 n ( ) )( x,对换 。如果 x, , x?{ 0 , 1 } 且 p 是 A = { 1 , 2 , , n}上的一个置换 ,定义 p x, x, , x 2 1 n 1 2 n ( )( )= x, x, , x ,称 p 是 x, x, , x上的一个置换函数 。 ( ) ( ) ( ) p 1 p 2 p n1 2 n )( , 容易证明 , x, x, x上的任一个置换都可以写成对换的乘积 。关于置换函数有如下性质 : 1 2 n ) ( )( ( 定理 1 令 f x, x, , x?B, 且 p 是 x, x, , x上的任意一个置换函数 。那么 deg f 1 2 n n 1 2 n ) ( ( ( ) ) ) ) ( x, x, , x= deg f p x, x, , x。 1 2 n 1 2 n ( ) ( ) ( ) ππ 证明 首先 ,令 是 x, x, , x的一个对换且满足 x, x, , x= x, x, x, , x,下 1 2 n 1 2 n 2 1 3 n ) ) ) )( (π ( ) ) ) ( ( ( ( ,, x。记x面说明 deg f x, x, , x = deg f x, , x= deg f x, x, x, 2 n 1 2 n 1 n 2 1 3 ( ( ) ) ) ( , deg f x, x, x= m , 那么在 f x, x, , x的代数标准型中存在一个次数为 m 的项 xx 1 2 n 1 2 n i i1 2 ( } = < ,那么 x, x,) , x, x也是 f < , x1 ?i< i< i?n。?如果 { x, x} ? = { x, x, i i i i i 1 2m 1 2 i i m 1 2 m 1 2 m ) ( , x} = x, x, x, , x的代数标准型中存在一个次数为 m 的项 ; ?如果 { x, x} = ? { x, x, i 2 1 3 n 1 2 i i 1 2 m ) ( { x} ,那么 i= 1而且 x, x,, x是 f x, x, x,, x的代数标准型中存在一个次数为 m 的项 ; ? 1 1 ii i2 1 3 n 1 2 m ) ( 如果 { x, x} ? = { x, x, , x} = { x} ,那么 i= 2 且是 f x, x, x, , x的代数标准型中存在一1 2 iii2 1 2 1 3 n 1 2 m 个次数为 m 的项 ; ?如果 { x, x} ? = { x, x,, x} = { x, x} ,那么 i= 1 , i= 2 , 而且 x, x, x,1 2 iii1 2 1 2 1 2 i 1 2 m 3 ) )( ( ) ( 的代数标准型中存在一个次数为 m 的项 。因此 deg f x, x, , x , x, x是 f x, x, x,n 1 2 n i1 2 3 m ( (π ( = deg f x, x, ) ) ) , x. 1 2 n ( ) ) ) ( π( ( 类似地 ,可以证明 :对 x, x, , x上的每个对换 ′都有 deg f x, x, , x= deg f 1 2 n 1 2 n (π( ) ) ) ( ) ( x,′x, , , x。由于 x, , x上的每个置换 p 都可以写成对换的乘积 。因此 , deg f x 2 1 2 n 1 n ) ( ( ( ) ) ) ) ( , x。x, x, , x= deg f p x, x, n 1 2 n 1 2 ) ( ) ( ) ( )( , g x, x,, x定理 2 设 f x, x, , x?Bn > 1 且 p 是 x, x, , x上的任意一个 n 1 2 1 2 n n 1 2 n 安徽科技学院学报2011年50 ( )( )( ( ,x 置换函数 。那么 g x, 是 f x, x, , x的零化多项式的充分必要条件是 g p x, x, , x2 1 n 1 2 n 1 2 ) )) )( ( , x是 f p x, x,, x的零化多项式 。n 1 2 n ) ( ) ( ) ( ππ , , x证明 首先 ,令 是 x, x, , x的一个对换且满足 x, x, , x= x, x, x, n 1 2 n 1 2 n 2 1 3 ( ))π ( ) )( (,x, x 下面说明 g x, 是 f x, x, , x的零化多项式的充分必要条件是 g x, x, , x2 n 1 n 1 2 n 1 2 ) ( ) )( π ( ( , 是 f x, x,= xf+ xf+ xxf+ f和 g x, x, , xx的零化多项式 。令 f x, x, 1 2 n 1 1 2 2 1 2 3 41 2 n 1 2 ))( = xg+ xg+ xxg , x = 1 , 2 , 3 , 4 是 x, , x上的布尔函数 。那么 , 这里 f和 g i, j + g1 12 2 1 2 3n 3 n 4 i j ( ))) ( ) ( ( g x, x, , x是 f x, x, , x的零化多项式当且仅当 f x, x, , xg x, x, , x= 0 , 1 2 n 1 2 n 1 2 n 1 2 n ( ) ( ) ( 当且仅当 xf+ xf+ xxf+ fxg+ xg+ xxg+ g= 0 ,当且仅当 xfg+ xfg+ xxfg+ 1 1 2 2 1 2 3 4 1 1 2 2 1 2 3 4 1 1 1 2 2 2 1 2 1 2 ) fg+ fg+ fg+ fg+ fg+ fg+ fg+ fg= 0 ,当且仅当 fg= 0 , fg= 0 , fg+ fg+ fg+ fg+ 1 3 2 1 2 3 3 1 3 2 3 3 4 3 4 4 1 1 2 2 1 2 1 3 2 1 2 3 ( fg+ fg+ fg+ fg= 0 , fg= 0 ,当且仅当 xfg+ xfg+ xxfg+ fg+ fg+ fg+ fg+ fg+ fg3 1 3 2 3 3 4 3 4 4 2 1 1 1 2 2 2 1 1 2 1 3 2 1 2 3 3 1 3 2 3 3) ( ) () ( + fg+ fg= 0 ,当且仅当 xf+ xf+ xxf+ f xg+ xg+ xxg+ g= 0 当且仅当 f x, x, 4 3 4 4 2 11 2 2 1 3 4 2 1 1 2 2 1 3 4 2 1 ) ( )( ( ) )( ( ) ), x, , xg x, x, x, , x = 0 ,即 g p x, x, x是 f p x, x, , x的零化子 。 3 n 2 1 3 n 1 2 n 1 2 n ( ) π( )( , , x是 f x, x,类似地 ,可以证明 :对 x, x, , x上的每个对换 ′都有 , g x, x, n 1 2 1 2 n 1 2 )π( ) )π( ) )((x的零化多项式的充分必要条件是 g ′x, x, , x是 f ′x, x, , x的零化多项式 。由 n 1 2 n 1 2 n ( ) ( 于 x, x, , x上的每个置换 p 都可以写成对换的乘积 。因此 ,对每一个置换 p ,都有 , g x, x, 1 2 n 1 2 ))) )( ( ( ( ( , , x是 f x, x, , x的零化多项式的充分必要条件是 g p x, x, , x是 f p x, x, n 1 2 n 1 2 n 1 2 ) ) x的零化多项式 。n 由定理 1和定理 2立即可得 )) ( ( x,, , x上的任意一个置换函数 。那么 x定理 3 令 f x, ?B, p 是 x, , x2 2 n 1 n n 1 )) ) )) ( ( , x ( ( ( A If x, x, = A If p x, x, , x n 1 2 1 2 n ( ( ) ππ )( )π , 如果 是 x, ,= x和 x= x。设矩阵 M是由 Fxx上的一个对换函数 ,且满足 x 1 2 j j i π 2n i ( π ) ( ) ( 上的 n阶单位矩阵, xM。如果 x,, I经过交换第 i, j行得到 ,那么 x, x, x= x, x, π n 1 n 1 2 n 1 2 )πππx, , x上的任一个置换函数 p 可以写成对换的乘积 : p =, 记 M= MMM, 那么 p π ππ 2 n 12 t p 1 2 t ( ) ( ) x, x, , x= x, x, , xM。容易证明 ,置换函数 p 和矩阵 M是一一对应的 ,称 M是 F上 1 2 n 1 2 n p p p 2 的 n阶置换矩阵 ,特别地 ,如果置换函数 p 是一个对换 ,称 M是 F上的 n 阶对换矩阵 。那么上述定理可 p 2 以分别叙述为 : ) )) ( ( ( ,x , x定理 1 ′ 令 f x, , x?B,如果 M 是 F上的 n阶置换矩阵 ,那么 deg f x, x, 2 n 1 n n 2 1 2 ( ( ( ) ) ) , = deg f x, x, xM 。 1 2 n ) ( ) ( ) ( x,定理 2 ′ 设 f x, , x, g x, x, , x?Bn > 1 且 M 是 F上的 n阶置换矩阵 。那 2 1 n 1 2 n n 2 ))) )( ( ( ( 么 g x, , , x是 f x, x, , x的零化多项式的充分必要条件是 g x, x, , xM 是 f x1 2 n 1 2 n 1 2 n ) ) ( ( , xM 的零化多项式 。x, x, n 1 2 ) ( F上的 n阶置换矩阵 。那么 定理 3 ′ 令 f x, x, , x?B, M 是 2 1 2 n n ) ) ) ( ( ( ) )( ( A If x, x, , x= A If x, x, , xM 1 2 n 1 2 n 布尔函数不仅对置换变换保持代数免疫阶的不变性 ,在许多其他可逆变换下也保持相同的性质 。 ) ) ) ( ( ( , x= 定理 4令 f x, x, , x?B,且 M 是 F上的 n阶可逆矩阵 。那么 deg f x, x, n 1 2 n n 2 1 2 ( ( ( ) ) ) deg f x, x, , xM 。 1 2 n (证明 设 M 是把 F上的 n阶单位矩阵 I的第 i行加上第 j行 ,其他行不变得到的矩阵 本文称 M 为 ij2 n ij ) ) )( ) ( ( ( , x+ x, x,, x行加矩阵 ,那么 f x, x, , xM = f x, x, , x,下面证明 deg f i - 1 ij i + 1 1 2 n ij 1 2 n ( ) ) ( ( ( ) ) ) ) ) ( ( ( ,, x,xx, = deg f x, x, , xxM 。记 deg f x, , x= m , 那么在 f x, 2 2 1 n 1 2 n ij 1 n 1 ) ) ( x, , , x的代数标准型中存在一个次数为 m 的项 。如果 f x, x, x的代数标准型中存在一个 2 n 1 2 n ( ),,xx次数为 m 的项 x,, x1 ?i< i< < i?n且 { x, x} ?{ x, , x} Α { x} ,那么 x, x, i2 i i1 im 1 2 m i j i i j i i 1 2 m 1 2 ( ( ) ) ) ( , x仍是 f x,, x的代 x, ,x , xM 的代数标准型中的一个次数为 m 的项 ;否则 , f x, i1 n 2 2 n ij 1 m 数标准型中所有次数为 m 的项都含有因子 x,不妨设其中一个次数为 m 的项为 x, x,, x,那么在 fi ii i 1 2 m - 1 第 25卷第 1期曹 浩 ,等 具有最大代数免疫阶的一阶弹性函数的构造51 ( ( ) ) ( ( ) ) x, x, , xM 的代数标准型中出现 ,从而仍是 f x, x, , xM 的代数标准型中的一个 1 2 n ij 1 2 n ij ) ) ) ( ( ( 次数为 m 的项 ,因此 deg f x, x, , xM = m。 1 2 n ij 由线性代数的知识知道 ,任何一个 F上的 n阶可逆矩阵 M 都可以由单位矩阵 I,经过有限次两行互 2 n 换位置以及一行加上另一行来得到 ,即 M 可以写成对换矩阵和行加矩阵的乘积 : M = MMM ,因此 1 2 t ) )( ( ( ) ) ) ( ( ( ) ) ) ( ( ( = deg f deg f x, x,, x = deg f x, x, , xMdeg f x, x, , xMM= 1 2 n 1 2 n 1 1 2 n 1 2 ( ( ) ) ) ( ( ( ) ) ) x, x, , xMM= deg f x, M , , xM 。 x1 2 n 1 2t 1 2 n ( ) ( ) ) ( 定理 5 设 f x, x, , x, g x, x, , x?Bn > 1 且 M 是 F上的 n阶可逆矩阵 。那么1 2 n 1 2 n n 2 ( ))) )( ( ( (g x, x, ,x, x是 f x, , x的零化多项式的充分必要条件是 g x, x, , xM 是 f 1 2 2 n 1 n 1 2 n ( ) )x, x, , xM 的零化多项式 。 1 2 n )( ( ) ) ( ( ) ) ( ( )( 证明g x, x, 的零化多项式 Ζ f x1 Α g x,下面证明 f , x, x是 f x, x, 1 2 n 0 n 1 2 ( ) ) ( ( ) ) ( ( ) ) ( ( ) ) x1 Α g x0 Ζ f xM Α g xM 。 1 0 ( ( ) ) ( ( ) ) ( ( ) ) α( ( ) ) ( ( ) ) α() αα 假若 f xΑ g x,对任意 ? f xM ,有 f M = 1 ] M ? f x] M ? g x] g1 0 1 1 0 (α( ( ) ) ( ( ) ) ( ( ) ) ( ( ) ) ( ( ) ) ( ) ) α M = 0 ] ? g xM ] f xM Α g xM 。反之 ,假如 f xM Α g xM ,记 fx= f0 1 0 1 0 1 - 1 - 1 ( ) ( )( ) ( ( ) ) ( ( ) ) ( ( ) ) ( ( ) ) ( ( ( ) ) xM 和 gx = g xM ,那么 fxΑ gx] fxM Α gxM ] f x M M Α g 1 1 1 1 0 1 1 1 0 - 1 1 - 1 ( ) ) ( ( ) ) ( ( ) ) ( ( ) ) ( ( ) ) ( ( ) ) ( ( ) ) ( ( ) ) x M M ] f xΑ g xΖ f xM Α g xM 。因此 , f xΑ g xΖ f xM Α 0 1 0 1 0 1 0 1 ( ( ) ) ))( ( ( ( , ,xg xM ,即 g x, , x是 f x, x, , x的零化多项式的充分必要条件是 g x, x, 2 0 1 n 1 2 n 1 2 ) )) )( ( xM 是 f x, x, , xM 的零化多项式 。 n 1 2 n 由定理 4、定理 5 立即可得 : ) ( ,F上的 n阶置换矩阵 。那么x 定理 6令 f x, , x?B n , 且 M 是 2 2 1 n ) ( ( ( ) )) ) ( ( A If x, x, , x= A If x, x, , xM 1 2 n 1 2 n 具有最大代数免疫阶的 m 阶弹性函数的构造3 首先我们探讨一下第 3节中出现的可逆变换对布尔函数的非线性性和相关免疫性的影响 。由于布尔函数的弹性阶与循环谱有密切的关系 ,下面首先讨论循环谱在该可逆变换下受到的影响 。 ) )( ( ) ( 设 f x, x, ?B n n > 1 且 M 是 F上的 n阶可逆矩阵 ,那么布尔函数 h x, x, , x, x1 2 n 2 1 2 n ) ) ( ( , xM 的循环谱为 := f x, x, n 1 2 ( ) ( ) h x+ wx f xM + wx - n - n = 2 ρ( )( )S= 2 ρ - 1 - 1 h (w )nnx?{ 0 , 1 } x?{ 0 , 1 } - 1) ( ) (- n f xM + wM M x - 1 n ( ) ) () = 2 - 1 = S ( wM ρ w ?{ 0 , 1 } f n x?{ 0 , 1 } n - 1 n 由于 M 是 F上的 n阶可逆矩阵 ,当 w 跑遍整个集合 { 0 , 1 } 时 , wM 也跑遍整个集合 { 0 , 1 } 。因此 , 2 )( ( ) ))( ( x,总体上来说 ,布尔函数 h x, x, , x = f x, , xM 和 f x, x, , x的循环谱值没有 2 1 2 n 1 n 1 2 n n - 1 n () ( ) 变化 ,只是在分布上不同 。由于 N= 2 1 - m ax{ | Sw | , w ?{ 0 , 1 } } ,所以上述可逆变换并不改变 f f 原函数的非线性度 。然而 ,由于谱值在分布上的变化 ,引起了相关免疫性的变化 ,因此 ,可以适当选择可逆 矩阵 ,构造一个非线性度和代数免疫阶不变 、而相关免疫性比原函数好的布尔函数 。 [ 6 ]( )引理 1 下述 n元布尔函数 f x具有最大代数免疫阶 : ( ) 1 如果n 是奇数 , ) ) ( ) ( ( f x, , x= 0 如果 w t x, , x? n - 1 /2 1 n 1 n ( ) ( ) = 1 如果 w t x,? n + 1 /2 , x 1 n ( ) 2 如果 n 是偶数 , ( ) )( < n /2 f x, , x= 0 如果 w t x, , x1 n 1 n ( ) > n /2 = 1 , x 如果 w t x,n 1 ( 如果 w t x,)( ) , x = n /2 , 这里 b?GF 2 = b 1 n ( )( ) ( ) ( )如果将 2 中构造增加两个新条件 : f x= f x+ 1和 f x是平衡布尔函数 ,利用该函数可以构造弹 性函数 。下面分析上述函数的循环谱性质 。 安徽科技学院学报2011年52 ( ) an是奇数 , w x 1 + w x ( ) - n - n f x+ wx ( )( )ρ - 1 +ρ - 1 () = 2 Sw = 2 ρ f ( ) ( ) ( ) ( ) w t x? n - 1 / 2 w t x? n + 1 / 2 nx?{ 0 , 1 } w x wx ( ) () () ( ) 如果 w t w = k是偶数 ,则 wx?w x mod2 ,即 - 1 = - 1 ,所以 w x 1 + w x w x 1 + w x - n - n ( )( )ρ - 1 +ρ - 1 ( )) ( )ρ - 1 +ρ - 1 () = 2 Sw = 2 f ( ) ( ) ( ) ( ) w t x? n - 1 / 2 w t x? n + 1 / 2 ( ) ( ) ( ) ( ) w t x? n - 1 / 2 w t x? n - 1 / 2 wx w x w x w x - n - n ( ) ( )( )) ( ) ρ - 1 -ρ - 1 -- 1 ρ - 1 = 2 = 2 = 0 ( ) ( ) ( ) ( ) w t x? n - 1 / 2 w t x? n - 1 / 2 ( ) ( ) w t x? n - 1 / 2 ( ) bn是偶数 , ( ) f x+ wx w x 1 + w x ( ) f x+ w x - n - n ( ) ( ) ( ) - 1 ρ - 1 + ρ - 1 + ρ () ( )= 2 - 1 Sw = 2 ρ f ( ) ( ) ( ) w t x< n / 2 w t x> n / 2 w t x= n / 2 nx?{ 0 , 1 } w x w x ( )( ) () () ( ) ( ) ( )如果 w t w = k是偶数 ,则 wx = w x mod2 ,即 - 1 = - 1 ,又因为 f x= f x + 1且 f x是平 衡布尔函数 ,所以 wx 1 + wx 1 + wx wx( ) ( ) ( ) ( ) - n ρ - 1 + ρ - 1 + ρ - 1 + ρ - 1 ( ) ( ) ( ) () w t x> n / 2 w t x= n / 2 w t x< n / 2 w t ( x) < n / 2Sw = 2 f ( ) ( ) f x= 1 f x= 0 wx 1 + wx 1 + wx wx ( ) ( ) ( ) ( )- n ρ - 1 + ρ - 1 + ρ - 1 + ρ - 1 ( ) ( ) ( ) ( ) w t x< n / 2 w t x< n / 2 w t x= n / 2 w t x< n / 2 = 2 ( ) ( ) f x= 1 f x= 1 wx wx w x w x ( ) ( ) ( ) ( )- n ρ - 1 - ρ - 1 - ρ - 1 + ρ - 1 ( ) ( ) ( ) ( ) = 2 w t x< n / 2 w t x> n / 2 w t x= n / 2 w t x< n / 2 = 0 ( ) ( ) f x= 1 f x= 1 因此 ,引理 1中的函数在重量为偶数的向量处 ,循环谱的值为 0。根据这一性质 ,适当选取一个可逆 矩阵 ,可以将引理 1中改进的布尔函数变换为弹性函数 。 - 1 ()定理 7 设 M 是 F上的 n阶可逆矩阵 。如果对任意重量为 1的 n元向量 w ,都有 w t wM 为偶数 , 2 ( ) ( ( ) ) ()) ( 那么函数 h x, x,x,, x= f x, x, , xM 这里 f x, , x是引理 1中的布尔函数 1 2 2 n 1 2 n 1 n 是弹性函数 。- 1 - 1 () () ()()w = Sw M ,w 证明 对任意重量为 1的 n元向量 w ,都有 S由于 w t wM 为偶数 ,所以 Sh f h - 1 ) ) ( ( ) )(( ) ( ) ( , x= f x, x, , xM 是一阶 = SwM = 0。又因为 S0 = S0 = 0 ,所以函数 h x, x, n 1 2 n f h f 1 2 弹性函数 。 参考文献 : [ 1 ]N ICOLA S Cou rto is, AL EXAND ER Klimov, JACQU ES Pa ta rin ec a l. Effic ien t a lgo rithm s fo r so lving ove rdefined system s of m u l2 tiva ria te po lynom ia l equa tion s. B a rt P renee l . Eu ro2000 [ C ]. B ruge s: Sp ringe r, 2000 , 392 - 407. [ 2 ] N ICOLA S Cou rto is. H ighe r o rde r co rre la tion a ttack s: XL a lgo rithm and c ryp tana lysis of Toyoc ryp t[ EB /OL ]. A va ilab le on h t2 tp: / / ep rin t. iac r. o rg /2002 /087. p df. [ 3 ] FR ED ER IK A rm knech t. A linea riza tion a ttack on the B lue too th keystream gene ra to r[ EB /OL ]. A va ilab le on h ttp: / / ep rin t. ia2 c r. o rg /2002 /191. p df. [ 4 ] N ICOLA S Cou rto is, W ILL IM e ie r. A lgeb ra ic a ttack s on stream c ip he rs w ith linea r feedback. D an Boneh. A dvance s in C ryp to lo2 gy Eu roc ryp t 2003 [ C ]. B e rlin: Sp ringe r - V e rlag, 2003, 345 - 359. [ 5 ] W ILL IM e ie r, EN ES Pa sa lic, CLAUD E Ca rle t. A lgeb ra ic a ttack s and decompo sition of boo lean func tion s. In te rlaken. A dvance s in C ryp to logyEu roc ryp t 2004 [ C ]. B e rlin: Sp ringe r - V e rlag, 2004, 474 - 491. [ 6 ] D eep ak Kum a r D a la i, Subhamoy M a itra, Sum an ta Sa rka r. B a sic Theo ry in Con struc tion of Boo lean Func tion s w ith M axim um Po ssib le A nn iha to r Imm un ity[ EB /OL ]. ava iab le from h ttp: / / ep rin t. iac r. o rg /2005 /229. p df. () 责任编辑 :窦 鹏