零化多项式与仿射空间关系研究

计 算 机 工 程 第 35 卷 第20期

Vol.35 No.20 Computer Engineering · 安全技术 ·

文章编号：1000—3428(2009)20—0137—03

文献标识码：A

2009年10月

October 2009

中图分类号：TP311.52

零化多项式与仿射空间关系研究

曹 浩1，魏仕民2，徐精明1

(1. 安徽科技学院理学院，凤阳 233001；2. 淮北煤炭师范学院计算机科学与技术系，淮北 235000)

摘 要：为把流密码的代数攻击问题转化为求解布尔函数的低次数零化多项式问题，讨论布尔函数的性质，介绍{0,1}上矩阵的特殊结构，研究两者间的关系，在此基础上探讨n 元布尔函数f 的零化多项式次数与f 的支撑点集之间的关系，实验结果表明，寻找布尔函数零化多项式等价于在布尔函数的零点集合中寻找最大的仿射空间。 关键词：布尔函数；支撑点集；零化多项式；仿射空间

Research on Relations Between Annihilators and Affine Spaces

CAO Hao1, WEI Shi-min2, XU Jing-ming1

(1. College of Science, Anhui Science & Technology University, Fengyang 233001;

2. Dept. of Computer Science & Technique, Huaibei Coal Industry Teachers College, Huaibei 235000)

【Abstract 】In order to transfer the stream ciphers algebraic attacks problems into low-degree annihilators of Boolean function problem, the characters of Boolean function is discussed. The special structure of matrix on {0,1} is introduced. The relations between them are researched. On this basis, the relations between the annihilator polynomial power number of n -variant Boolean function and their support points sets are studied. Experimental results show the problem of searching annihilators for Boolean function is the same as searching the maximum affine space in zero points sets of it.

【Key words】Boolean function; support point set; annihilator; affine space

1 概述

基于线性反馈移位寄存器的流密码的代数攻击对流密码

体制构成巨大威胁，利用代数攻击已成功破译了可抵抗所有已知攻击的Toyocrypt 和LILI 128。代数攻击的思想是：构造初始密钥和输出密钥流之间的超定义低次代数关系，攻击者将观察到的密钥流比特代入该代数关系，获得关于初始密钥k 的超定义代数方程，然后利用线性化算法或XL 算法及其变形算法求解该方程组，从而重构密钥。在代数攻击中，最关键的是构造关于初始密钥k 的超定义低次数代数方程，文 献[1-2]将该问题转化为寻找布尔函数的低次代数关系，文 献[3]进一步将其转化为寻找布尔函数的低次数零化多项式的问题。研究密码学中布尔函数的零化多项式的次数，在密码学上有重要的理论和实际意义。

(2)如果|1f |=22，则deg (f )=n –1或deg (f )=n –2，且deg (f )=n –2当且仅当1f 是个2维仿射空间；

(3)如果|1f |=23，则deg (f )=n –3，且deg (f )=n –3当且仅当1f 是个3维仿射空间。

证明：这里仅证明(3)。由|1f |=23可设1f ={s 1, s 2, …,s 8}= {(a 11, a 12, …, a 1n ),(a 21, a 22, …, a 2n ), …,(a 81, a 82, …, a 8n )}，令b ij =a ij + a 8j ，记

⎡b 11b 12⎢b

⎢21b 22

M 3=⎢

⎢

⎢b 71b 72⎢b b

82⎣81

b 1n ⎤

⎛β1⎞

b 2n ⎥⎜⎟⎥β

⎥=(α1, α2, , αn ) =⎜2⎟

⎜ ⎟⎥

b 7n ⎥⎜⎜β⎟⎟

8⎠⎝⎥ b 8n ⎦

其中，αi =(b 1i , b 2i , , b 8i ) T , βj =(b j 1, b j 2, , b jn ) , i =1,2,…, n , j =1,2,…,8, β8=(0,0, ,0) ，则β1, β2, …, β8互不相等。f (x ) 表示为f (x 1, x 2, , x n ) =∑∏(x i +a ji +1) ，用y i 替换x i +a 8i +1，得：

j =1i =18

n 8

n

2 零化多项式与仿射空间关系探究

定义1 S ⊂{0,1}是个非空集合，任意取定v ∈{0,1}，记

S v ={x +v |x ∈S }。如果存在v ∈{0,1}n 使S v 是个向量空间，则称S 是个仿射空间。

引理1[4] 设f (x ):{0,1}n →{0,1}是n 元布尔函数。如果0f 中包含一个k 维仿射空间，那么有一个次数为n-k 的零化多项式。

引理2 设f (x ) 是次数为d (d >0)的n 元布尔函数，则 n-d

2≤wt (f ) ≤2n -2n-d 。特别地，deg (f ) ≥max{n –lbwt (1+f ), n – lb wt (f )}。

定理1 设f (x ):{0,1}n →{0,1}是n 元布尔函数，记 0f ={x ∈{0,1}n |f (x )=0}和1f ={x ∈{0,1}n |f (x )=1}，分别称为f (x ) 的零点集和支撑点集，则有：

(1)如果|1f |=2，则deg (f )=n –1；

n

n

g (y 1, y 2, , y n ) =∑∏(y i +b ji ) =

j =1i =1n

∑(∑b i j b i j b i j ) y j y j y j

l =0i =1

l +1

l +2

n

1

2

1

2

l

8

l

显然deg (f )=deg (g ) ，则y j y j y j (l ≤n ) 的系数等于M 3的第j l +1, j l +2, …, j n 列中位于同一行元素的乘积之和。下证

基金项目：国家自然科学基金资助项目(60573026)；安徽科技学院引进人才基金资助项目(ZRC2008169)

作者简介：曹 浩(1981－) ，男，硕士研究生，主研方向：密码学，信息安全；魏仕民，教授、博士；徐精明，教授

收稿日期：2009-06-10 E-mail ：[email protected]

—137—

deg (g ) ≥n –3，且deg (g )=n –3⇔{β1, β2, …, β8}是一个3维线性空间。

(1)由M 3有8行知，y 1y 2…y n 的系数为0。

(2)如果g 中某n -1次项y 8

j 1

y j 2

y j n −1

的系数∑b i =1

i j n

(mod2) 为

0，命题已证。否则g 中任一n -1次项y j 1

y j 2

y j n −1

系数

∑8

b i =1

i j n

(mod2) 都等于0，即M 3的每一列中所有元素之和都等

于0，即

β1+β2+…+β8=0 (1) 所以，M 3的每一列向量αi 的重量都是偶数。这种情况下，如果g 中某一n -2次项y 8

j 1

y j 2

y j n −2

的系数∑b i =1

i j n −1b i j n

(mod2) 不

为0，则命题已证。否则，

∑8

b i =1

i j n −1

b i j n

(mod2) =0 (2)

对任意{j n-1, j n }⊆{1, 2,…, n }都成立，即α1, α2, …, αn 两两正交。

显然，rank(M 3) ≥3(否则，β1, β2, …, β8至少有2个向量相等) ，下面证明rank(M 3)=3。假设rank(M 3)=4，不妨设α1, α2, α3, α4线性无关，由上述讨论知，α1, α2, α3, α4重量都是偶数且不为0。

如果wt (α1)=2，不妨设α1=(1,1,0,0,0,0,0,0)T ，由式(2)知α2, α3, α4与α1正交，则α2, α3, α4中第1、第2个分量要么全为1，要么全为0，由α5, α6, …, αn 是α1, α2, α3, α4的线性组合知，β1= β2，矛盾，所以，wt (α1) ≠2，类似地，可以证明wt (α1) ≠6，因此，wt (α1)=4。同理，wt (α2)=wt (α3)=wt (α4)=4。

不妨设α1=(1,1,1,1,0,0,0,0)T ，又因为α2, α3, α4与α1正交，所以α2, α3, α4的前4个分量中有含有2个1，后4个分量中也含有2个1，可设α2=(1,1,0,0,1,1,0,0)T ，讨论如下：由α1, α2和α3, α4正交且wt (α3)=wt (α4)=4知，α3, α4在第1、第2个分量中含有一个1，在第3、第4个分量中含有一个1，在 第5、第6个分量中含有一个1，第7个分量都为1，第8个分量都为0。设α3在第i 1, i 2, i 3, 7个分量为1，其余分量为0，α4在第j 1, j 2, j 3, 7个分量为1，其余分量为0，且i 1, j 1∈{1,2}, i 2, j 2∈{3,4}, i 3, j 3∈{5,6}，由α3和α4正交且α3≠α4知，|{i 1, i 2, i 3}∩{j 1, j 2, j 3}|=1。

如果i 1=j 1，那么{i 2, i 3, j 2, j 3}={3,4,5,6}，所以，α3+α4= (0,0,1,1,1,1,0,0)T =α1+α2，这与α1, α2, α3, α4线性无关矛盾。同理，可证i 2=j 2或i 3=j 3也不成立。从而{i 1, i 2, i 3}∩{j 1, j 2, j 3}=∅，与|{i 1, i 2, i 3}∩{j 1, j 2, j 3}|=1矛盾，所以，假设rank(M 3)=4错误。同理可证，rank(M 3) ≠5, 6，所以，rank(M 3)=3，而M 3行数为8，且每2行互不相同，因此，{β1, β2, …, β8}是个3维线性空间，即1f 是个3维仿射空间。此时，deg (f )=deg (g )=n –3。

定理2 互不相等的2k 个二元向量β1, β2, …, βt ∈{0, 1}n ，这

里，βi =(b j 1, b j 2, …, b jn ) ，j =1,2,…, t , βt =(0, 0,…, 0), t =2k

。如果

t

i ∑b =1

i j

n −s +1

b i j n −1

b i j n

(mod2) =0对任意1≤s ≤k 都成立，那么

{β1, β2, …, βt }是个k 维线性空间。

证明：令

⎡

⎢b 11

b 12b 1n ⎤

⎢b 21

b 22

b ⎥⎛β1⎞

2n M k =⎢⎢

⎥⎜⎥=(α) =⎜β⎟21, α2, , αn ⎢b t −1,1b t b ⎥

⎜⎟⎜ ⎟

t ⎢−1,2−1, n ⎥⎣b t 1

b t 2 b tn ⎥⎜⎦

⎝β⎟t ⎟

⎠—138

— 其中，αi =(b 1i , b 2i , …, b ti ), βi =(b j 1, b j 2, …, b jn), i =1,2,…, n ,

j =1,2,…, t , βt =(0, 0,…, 0)，且β1, β2, …, βt 互不相等。要证明{β1, β2, …, βt }是个k 维线性空间，只需证rank(M k )=k 。显然，rank(M k ) ≥k ，令rank(M k )=r (r ≥k ) ，不妨设α1, α2, …, αr 是α1, α2, …, αn 一个极大线性无关组。

首先证明wt (α1)=wt (α2)=…=wt (αk +1)=2k -1。

(1)如果wt (α1)=2(k >2)，不妨设α1=(1,1,0,0,…, 0,0)T ，由题设知α2, …, αr 与α1正交，则α2, …, αr 中第1、第2个分量要么全为1，要么全为0，由αr +1, …, αn 是α1, α2, …, αr 的线性组合知β1=β2，矛盾，所以，wt (α1) ≠2。

(2)如果wt (α1)=4(k >3)，不妨设α1=(1,1,1,1,0,0,…,0,0) T ，由题设知α2, …, αr 与α1正交，且α1, α2, …, αr 互不相等，则α2, …, αr 的前4个分量有偶数个为1。

1) 假如α2, …, αr 的前4个分量都是0或者都是1，由αr +1, …, αn 是α1, α2, …, αr 的线性组合知β1=β2=β3=β4，矛盾；否则，

2) 可设α2中第1, 2, i 2, j 2个分量为1，其他分量全为0，若α3, …, αr 的前2个分量全为1或0，则β1=β2，矛盾，因此，可设α3中第1, 3, i 3, j 3个分量为1，其他分量全为0，且|{i 2, j 2}∩{i 3, j 3}|=1，不妨设i 2=i 3，假如α4, …, αr 的前2个分量全为1或0，则α4, …, αr 中第3、第4个分量全为0或1，第i 2, j 2个分量为0，第j 3个分量为1，且在除第1,2,3,4, i2, j 2, j3个分量外某个分量为1，那么以α1, α2, …, αr 为列的矩阵[α1, α2, …, αr ]中有r +4个非0行且r -33矛盾。同理，“α4, …, αr 的第3、第4个分量全为1或0”不成立。

由上述可设α4的前2个分量为10，又α4和α1正交，α4的第3、第4个分量分别为1和0或者分别为0和1。前一种情况中，由α4和α2, α3正交知，α4的第j 2个分量为1，另外还有一个分量为1；后一种情况中，由α4和α2, α3正交知，α4的第i 2个分量为1，另外还有1个分量为1。易见α5, …, αr 具有α4的类似性质，即除第1,2,3,4, i2, j 2, j3个分量外某个分量为1，wt (α1) ≠4。那么以α1, α2, …, αr 为列的矩阵[α1, α2, …, αr ]中有r +4个非0行且r -33矛盾。同理，“α4的前2个分量为10”也不成立。因此，wt (α1) ≠4。

(3)如果wt (α1)=6，不妨设α1=(1,1,1,1,1,1,0,0,…,0,0) T ，由题设知α2, …, αr 与α1正交，且α1, α2, …, αr 互不相等，则α2, …, αr 的前6个分量有偶数个为1。

1) 假如α2, …, αk +1的前6个分量都是0或者都是1，由αr +1, …, αn 是α1, α2, …, αr 的线性组合知β1=β2=…=β6，矛盾；

2) 由1) 讨论知，可设α2第1,2,3,4, j 1, j 2个分量为1，其他分量全为0，这里j 1, j 2∈{7,8,…, t }。如果α3, …, αr 中前4个分量全为1或0，由αr +1, …, αn 是α1, α2, …, αr 的线性组合知βt

1=β2=β3=β4，矛盾；由题设“∑b i =1i j

n −s +1

b i j n −1

b i j n

(mod2) =0对任

意1≤s ≤k 都成立”可推导出α3的前4个分量中有偶数个1(因为α1, α2, α3对应分量乘积之和为偶数) ，同理α4, …, αr 的前4个分量中有偶数个1。不妨设α3的第1,2, j 3, j 4, j 5, j 6个分量为1，其他分量全为0，由α3与α2正交知，|{j 3, j 4, j 5, j 6}∩{3, 4}|=0

或2，|{j 3, j 4, j 5, j 6}∩{5,6}|=0或2。若|{j 3, j 4, j 5, j 6}∩{3,4}|=0且|{j t

3, j 4, j 5, j 6}∩{5,6}|=0，由题设“∑b i =1i j

n −s +1

b i j n −1

b i j n

(mod2) =0对

任意1≤s ≤k 都成立”可推导出α4的前2个分量相同(因为α1, α3, α4对应分量乘积之和为偶数) ，同理α4, …, αr 的前2个分量相同，则由αr +1, …, αn 是α1, α2, …, αr 的线性组合知β1=β2，矛盾。如果|{j 3, j 4, j 5, j 6}∩{3,4}|=2且|{j 3, j 4, j 5, j 6}∩{5,6}|=2，则α1=α3，矛盾。如果|{j 3, j 4, j 5, j 6}∩{3,4}|=0且|{j 3, j 4, j 5, j 6}∩ {5,6}|=2，由题设α1, α3, α4对应分量乘积之和为偶数且α1, α2, α4对应分量乘积之和为偶数得：α4的第1、第2个分量为1，第3~第6个分量为0，同理α5, …, αr 的第1、第2个分量为1，第3~第6个分量为0。由αr +1, …, αn 是α1, α2, …, αr 的线性组合知β1=β2，矛盾。由1),2) 讨论知wt (α1) ≠6。

重复上述过程会得到wt (α1)=2k -1，同理，wt (α2)=…= wt (αk +1)=2k -1。

其次证明{β1, β2, …, βt }是个k 维线性空间。 因为wt (α1)=wt (α2)=…=wt (αk +1)=2k -1，可令α1=(1,1,…,1,1,

0,0, …,0,0) T

，

且α1中1和0的个数相等，都为2k -1个。记αi =(αi 1T , αi 2T ) T ，其中，αi 1T 是αi 前2k -1个分量；αi 2T 是αi 后2k -1个分量，i =1,2,…, n 。下面对k 用归纳法证明{β1, β2, …, βt }是个k 维线性空间。k =1, 2, 3时，定理1已证，假设k =m –1(m ≥4) 时命题已证，下证k =m 时命题也成立。

由于α1的前2m -1个分量为1，后2m -1个分量为0，因此由题设“∑t

b i =1i j

n −s +1

b i j n −1

b i j n

(mod2) =0对任意1≤s ≤m 都成立”

可推导出：

(1)“t ∑/2

b i =1i j

n −s +1

b i j n −1

b i j n

(mod2)=0对任意1≤s ≤m -1都成立”

继而又可以推出：

(2)“∑t

b i j b i j 1

b i j n

(mod2)=0对任意1≤s ≤m -1都成立”

i =t /2−1

n −s +1

n −由归纳假设和(2)以及βt =(0, 0,…, 0)得{βt /2+1, βt /2+2, …, βt }是个m -1维线性空间。

⎡ ⎢b 11b 12b 1n ⎤

b 22 b ⎥⎛β1⎞

2n 对⎢b 21

M m =⎢⎢

⎥⎜⎥=(αβ⎟21, α2, , αn ) =⎜⎢b t −1,1b t b ⎥

⎜⎟

⎜ ⎟t ⎢−1,2−1, n ⎥⎜⎣b t 1

b t 2

b ⎝β⎟t ⎟

⎠tn ⎥⎦

做如下初等行变换：将M m 的第1, 2, t -1, t 行加上β1得到一个

新的矩阵M m ′

：

⎡ ⎢0

00⎤

⎢b 11+b

21b 12+b 22 b ⎥1n +b 2n ⎛⎢b 31 b ⎥

β′n ⎥

⎜1⎞3⎟M ′⎢b 32m =⎢ ⎥

′⎜⎢⎥=(α′β′⎟1, α2, , α′n ) =⎜2 b ⎜ ⎟⎟

⎢b t −2, 1

b t −2,2t −2, n ⎥⎜⎢ ⎢b 11+b t −2, 1b 12+b t −2,2b ⎥⎜1n +b t −2, n ⎥⎝β′t ⎟⎟⎠

⎣b 11

b 12 b ⎥1n ⎦

注意到α1=(1,1,…,1,1,0,0, …,0,0) T ，可以知道M m ′的

第1行为全零行，即β1′=(0,0,…,0), α1′=(0,0,1,…,1,0, …,0,1,1) T ，而且β1′, β2′, …, βt ′ 满足题中β1, β2, …, βt 具有的性质，类似前述证明，可得{β1′, β2′, βt /2+1′, βt /2+2′, …, βt -2′}作成一个k -1维线

性空间，由此β2′可由βt /2+1′, βt /2+2′, …, βt -2′线性表出，即β1+β2

可由βt /2+1, βt /2+2, …, βt -2线性表出，从而β1+β2可以由βt /2+1, βt /2+2, …, βt 线性表出。同理可以证明β1+β3, β1+β4, …, β1+βt /2可以由βt /2+1, βt /2+2, …, βt 线性表出，所以，rank{β1, β2, …, βt }≤rank{βt /2+1, βt /2+2, …, βt }+1。显然，β1∉{βt /2+1, βt /2+2, …, βt }，所以，rank{β1, β2, …, βt }=rank{βt /2+1, βt /2+2, …, βt }+1=k +1。而M m 行数为t =2m ，且每2行互不相同，因此，{β1, β2, …, βt }是个m 维线性空间。

利用定理2，容易得到定理1推广定理：

定理3 设f (x ):{0,1}n →{0,1}是n 元布尔函数，如果|1f |=2k (k ≥1) ，则deg(f)≥n –k ，且如果deg (f )=n –k ，那么1f 是个k 维仿射空间。

由引理2易得：

命题1 设f (x ):{0,1}n →{0,1}是n 元布尔函数，且1f 是维数为k 的仿射空间。S ⊂{0,1}n ，S ∩1f =∅且|S|

根据引理1、引理2、定理1、定理2以及命题1，猜测： 猜想1 设f (x ):{0,1}n →{0,1}是n 元布尔函数。如果0f 中

包含的最大的仿射空间的维数为k ，

则f 的次数最低的零化多项式的次数为n-k 。

猜想2 设S ⊆{0,1}n ，S 中最大的仿射空间的维数为k ，则以S 的子集为支撑的n 元布尔函数的次数≥n-k 。

容易看出，猜想1和猜想2是等价的。如果上述猜想都成立，会得到如下命题：

命题2 设f (x ):{0,1}n →{0,1}是n 元布尔函数。则f 含有次数为n-k 的零化多项式当且仅当0f 中包含维数为k 的仿射空间。

这样就可以将求给定布尔函数的零化子问题转化为在给定向量集合中寻找最大仿射空间的问题。

3 结束语

本文根据流密码的代数攻击问题可转化为求解布尔函数的低次数零化多项式问题，利用布尔函数的特殊性质和{0, 1}矩阵上的特殊结构，深入分析n 元布尔函数f 的零化多项式次数与f 的支撑点集之间的关系，并得到求给定布尔函数的零化多项式问题可以转化为在布尔函数的零点集合中寻找最大仿射空间的代数问题的结论。

参考文献

[1] Courtois N, Meier W. Algebraic Attacks on Stream Ciphers with

Linear Feedback[C]//Proc. of the Int’l Conf. on the Theory and Applications of Cryptographic Techniques. Warsaw, Poland: [s. n.], 2003.

[2] Courtois N. Algebraic Attacks on Combiners with Memory[C]//Proc.

of the 7th Int’l Conf. on Information Security and Cryptology. Seoul, Korea: [s. n.], 2004.

[3] Meier W. Algebraic Attacks and Decomposition of Boolean

Functions[M]. [S. l.]: Springer Berlin/Heidelberg, 2004.

[4] 张文英. 密码学中布尔函数的零化子[J]. 电子学报, 2006, 34(1):

51-54.

编辑 陈 文

—139—