《浅谈辅助函数的构造方法.doc》由会员分享，可在线阅读，更多相关《浅谈辅助函数的构造方法.doc（144页珍藏版）》请在金锄头文库上搜索。
1、浅谈辅助函数的构造方法1、相关定义1.1、弹性函数的定义和性质 日本学者 Siegenthaler 在 1985 年对非线性组合流密码系统提出了一种称为”分 别征服”(Divide-and-conquer)的攻击方法53,即后来所称的相关攻击。相关攻 击的基本思想是考察密钥流序列和原驱动序列之间的相关性,两者相关性越强, 就越容易实施攻击53。为了抵抗相关攻击,非线性组合流密码系统中的非线性函 数应当具有一定的相关免疫性。为此,Siegenthaler 给出了相关免疫函数的定义: 定义 2.333 设f( x1 , x 2 ,? , xn ) 是一个n 元布尔函数,其中 x1, x2 , ?,
2、 xn 是 ?2 上 均匀分布的独立随机变量,如果 f 与 x1, x2 , ? , xn m 1 , , 中任意的 个变元xi? xim 统计独 立,即对于任意的(a1 , a 2 ,?,am ) ? ? 2m 及a? ?2 ,均有 1 2 ( |i1 , i 2, , m ) p f? a x ? a x?a? xim ? a ? p ( f? a ), 称 f 是m 阶相关免疫函数。 下面的定理 2.9 给出了判别相关免疫函数的等价条件: 定理 2.933 设f( x )? f( x1 , x 2 ,? , x n ) 为n 元布尔函数,其中 x1, x2 ,? , xn 是 ?2 上
3、均匀分布的独立随机变量,则下列三个条件等价: (1) f ( x ) 是m 阶相关免疫函数; (2) 对任意的w?2n ,1 ?wt ( w) ? m ,f ( x ) 与 w? x 统计独立; (3) 对任意的w?2n ,1 ?wt ( w) ? m , f ( x )? w ? x 是平衡函数。 定理 2.1033 设f( x )? f( x1 , x2 , ?, xn ) 为n 元布尔函数,其中 x1, x2 , ?, xn 是 ?2 上 国防科学技术大学研究生院硕士学位论文 均匀分布的独立随机变量,则f ( x ) 0 是 阶相关免疫函数当且仅当对任意的 , 均有 m a ? ?2n
4、, 1?wt (a ) ? mWf ( a ) ? 。 定理 2.10 通常称为 Xiao-Massey 定理,该定理刻画了 阶相关免疫函数的谱 特征。由于密码系统中所使用的布尔函数通常需要满足平衡条件,后来给出了如 下弹性函数的定义: m 定义 2.433 设f( x)? f( x 1 , x2, ?, x n ) 是一个n 元布尔函数,如果f ( x ) 既是 阶 相关免疫函数又是平衡函数,则称 m 第 11 页 f( x) 是m 阶弹性函数。 注意到布尔函数f ( x ) 是平衡函数当且仅当Wf ( x ) ? 0 ,于是 定理 2.1133 布尔函数f ( x ) 0 n 是 阶弹性函
5、数当且仅当对于任意 , ,有 。 2 ma ? ?n 0?wt (a) ? mW f( a ) ? 弹性函数既具有相关免疫性,又具有平衡性,给定一个布尔函数,我们希望 弹性阶越大越好,但弹性阶与代数次数,非线性度等其它密码学指标存在一定的 制约关系。下面的定理说明了布尔函数的相关免疫阶或者弹性阶与代数次数的相 互关系: 定理 2.1233 给定一个 元布尔函数f( x )? f ( x1 , x 2 ,? , xn ) ,若f ( x ) 是 m(1? m ?n ? 1)阶弹性函数,则degf? n ? m ? 1 ;若 f 是m (1? m ?n ? 1) 阶相关免 疫函数,则deg f?
6、n ? m 。 定理 2.12 给出了弹性函数的代数次数的上界,这个上界最早由 Siegenthaler 给出,所以被称为 Siegenthaler 界。 利用 McEliece 定理,Carlet 给出了次数为 的 阶相关免疫函数或者弹性函 数的 Walsh 变换性质。 d m 定理 2.1333 设f ( x ) 是n 元布尔函数,并且 degf? d ? 1 ,若f ( x ) 是 阶相关 免疫函数, ,则 m m? n ?1 11 Wf( a )? 0 mod2m? ?n? dm ? ? , ? a ? ? 2n ; 若f( x ) 是m 阶弹性函数,m? n ?2 ,则 22 2m
7、2 od , 2 . n m ? ?d ? ? ? a ? ?n 1 Wf( a ) 0 m NL( f ) 注意到对于任意的布尔函数都有?n ?1 ?2 n/ 2? ,再利用定理 2.3,可以得到 代数次数为d 的m 阶弹性函数非线性度的上界。 定理 2.1433 设f ( x ) 是代数次数为d 的n元m 阶弹性布尔函数, , 是使得 m? n ?2 k k 2m?1 ? ( n ?m ?2)/ d ?2n ?1 ? 2 n/2 ? 1 国防科学技术大学研究生院硕士学位论文 成立的最大整数,则 11 ( 2)/ 1 ( 2)/ 2 2 ( 2) / 2 2 2 ( 2) / 2 . , 2
8、 , nm n m d f mn m d m n m dn Nk m n m dn ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 时 时 当 当 ; 若不考虑代数次数,则由定理 2.14 可以直接得到如下定理: 定理 2.1533 设f ( x ) 是n 元 m 阶弹性函数, k 是使得 k 2m?1? 2 n ?1 ? 2 n/ 2 ?1 成立的最大整数,则 1 1 1 2 2 2 2 2 2 . , , 2 n m m f mn Nk mn ? ? ? ? ? ? ? ? ? ? ? ? ? ? 当 时 当时 ; 定理
9、2.15 的上界最早由 Sarkar 等人在文49中给出,所以这个界称为 Sarkar 界,显然若一个弹性函数达到 Sarkar 界,则它的代数次数也达到 Siegenthaler 界。 关于相关免疫度与代数免疫度之间的联系,目前还没有一个好的结果,但利 用代数次数, 可以给出二者之间一个简单的联系。由于AI ( f )? deg( f ) ,结合定理 2.12,有: 定理 2.1633 设函数f ?n ,且为 m 阶相关免疫函数,则AI ( f )? n ? m ;特别 地,若 f 为平衡函数,则AI ( f )?n ? m ? 1 。 利用非线性度,也可以给出相关免疫度与代数免疫度之间的一
10、个联系。由于 1 1 1/ 2 1 2 m f n n i N n ? ?i ? ? ? ? ? ,再由定理 2.8,有: 定理 2. 1733 设f ?n ,AI ( f )? k ,若 f 为m 阶相关免疫函数,则 2 2 0 1 11 1/ 2 1 2 k m n n i i n n i i ? ? ? ? ? ? ? ? ? ? ? ; 若 f 为m 阶弹性函数,则 2 2 0 0 11 1/ 2 1 2 k m n n i i n n i i ? ? ? ? ? ? ? ? ? ? ? 。 最后需要说明的与代数免疫度、代数次数、非线性度等密码学指标不同,这 些密码学指标都是在仿射变换
11、下的不变量,而相关免疫度则不是仿射不变量。 第 12 页 国防科学技术大学研究生院硕士学位论文 1.2、布尔函数的基本概念 设?2 是二元有限域,是 ?2 上的n维向量空间,用 ? 表示 上的加法。对于向 量 , ?2 x?( x1, x2 , ? ?, xn ) ? ?2n , y ? ( y1 , y2 ,? ?, yn ) ? ? 2n x 和y 的点乘定义为 x? y ? x1 y1 ? x 2 y 2 ? xn y n . x 的支撑集是supp(x)? i | xi ? 0 , x 的支撑集的基数称为 x 的重量,记为 。 规定 wt( x ) x 的补元素是x?( x1 ? 1,
12、 x 2 ? 1,?, xn ? 1) . 一个n元布尔函数f ( x ) ( 是从 到 上的一个映射。 元布尔函数的全体记作 ,一个 元布尔函数 ?2n ?2 n ?n nf x ) 可以唯一地表示为: 1 1 1 1 0 , , , 1, , 1 2 1 1 1 ( , ,) , d d d n n i i i j i j i i i i n i i j n i i n f x x a a x a x x a x x a? x x xn ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? a0, ai , ai , j ,? , a1 , ?, n
13、? ?2 ? 其中 。 f 的这种表示形式称之为 f 的代数正规型(Algebraic Normal Form,ANF),其系数非零项所含有的最多的变元个数称为代数次数,记为 deg(f ) 。代数次数小于等于 1 的布尔函数称为仿射函数,记 为全体 元仿射布 尔函数的集合。 ?n n 每一个布尔函数都可以用它的真值表唯一表示,布尔函数的真值表是长为 、 包含该函数所有值的一个向量。满足 2n f( x ) ? 1 且x ? ?2n 的全体元素的集合称之为 f 的支撑,记为1f (也可以记为supp(f ) );满足f ( x )? 0 且 的全体元素的集 合记为0 2 x ? ?n f 。支
14、撑集 supp(f ) 所含元素的个数称为 f 的Hamming重量,记为 。 若 ,则称n元布尔函数 wt(f ) wt(f ) ? 2n ?1 f 是平衡的,即意味着 1 #x?2n | f ( x) ? 1 ? # x ? ? 2n | f (x ) ? 0( ? 2n ? ) 。 布尔函数f ( x ) 与g( x ) 的 Hamming 距离d ( f , g ) 是指集合x | f ( x )? g ( x) 的基 数,显然d( f ,g )? wt ( f ? g ) 。 性质 1:wt ( f? g ) ? wt ( f ) ? wt ( g ) ? 2wt ( f ? g)
15、。 第 5 页 国防科学技术大学研究生院硕士学位论文 性质 2:设l( x ) 是一个平衡的布尔函数,则 2 ( 1)( ) 0 n l x x? ? ? 。 布尔函数的 Walsh 变换,也称 Walsh 谱,是研究布尔函数密码学性质最重要 的数学工具之一。Walsh 谱是?2n 上的一个实值函数, 其定义为: 2 ( ) ( 1)( ) n f x x f x F W? ? ? ? ? ? , 其逆变换为: 2 ( 1)( ) 1 ( )( 1) 2 n f x x nf F W ? ? ? ? ? ? ? ? 。 布尔函数的 Walsh 谱有一些基本性质: 定理 2.160 Wf (?)
16、?2 n ? 2w t( f ? ? ? x ) 。 定理 2.2 15 给定n 元布尔函数f ( x ) 与g( x ) ,对于? ? ?2n 有下面结果成立: 2 2 ( ) ( ) ( n n Wf g W f W g ? ? ? ? ?). ? ? ? ? 如果令定理 2.2 中 f? g 以及? ? 0 ,可得到著名的 Parseval 恒等式。 定理 2.315 (Parseval 等式) 2 2( )2 2 n n F Wf ? ? ? ? 。 从实际应用出发,为了使设计出的密码算法抵抗各类已知攻击,对算法中使 用的布尔函数提出了各种密码学指标,以此来衡量其抵抗各类攻击的强弱程度。 非线性度是用来衡量抵抗线性攻击能力而提出的一个重要概念,它是衡量布尔函 数密码学性质好坏的一个重要指标。 定义 2.160
