The Characteristic of Spectrum and Self-correlation of Some Boolean Fuctions Linearly Equivalent to Specific Cryptographic Functions

Abstract

The paper made an analysis of the similarities and differences about the cryptographic properties of two Boolean functions in the sense of linearly equivalence, and obtained a sufficient and necessary condition about a Boolean function linearly equivalent to some m order correlation-immune Boolean function. It also obtained a sufficient and necessary condition about a Boolean function linearly equivalent to some Boolean function satisfying the k order propagation criterion. Moreover, it showed an example,in which a given Boolean function, that is not correlation-immuned and does not satisfy the propagation criterion can be constructed into a correlation-immuned Boolean function that can satisfy the propagation criterion and is linearly equivalent to the former one.

Content

《1 引言》

1 引言

线性等价的定义是由文献[1]给出的。随后, 构造线性等价意义下的满足一定密码学性质的布尔函数受到了广大学者的关注, 如在文献[2]中直接分析了线性等价意义下布尔函数某些密码学性质的变化, 指出了在变量的可逆线性变换的作用下 (即线性等价意义下) , 函数的代数次数、平衡性、非线性度及满足扩散准则的点个数保持不变 (即不变性) , 同时给出了线性等价意义下构造平衡的、满足高次扩散准则的布尔函数的方法。后来在文献[3]中给出了从一个不具有相关免疫性的平衡布尔函数出发, 构造线性等价意义下一阶弹性函数的方法, 此方法也正是文献[4]中所提到的LT方法。温巧燕、钮心忻、杨义先教授指出, 非线性、平衡性、相关免疫性和扩散性是衡量密码函数性能优劣的重要指标, 构造平衡、满足扩散准则且具有足够高非线性度的相关免疫函数是一个重要的研究课题 ^[5]。基于此, 特别是注意到密钥流非线性组合器的设计需综合考虑各种优良性的发展趋势, 笔者首先用概率方法给出了线性等价的两个布尔函数的Walsh循环谱及自相关函数之间的关系, 由此得到了一个布尔函数线性等价于某个具有m阶相关免疫性的布尔函数的充分必要条件和线性等价于某个满足k次扩散准则的布尔函数的充分必要条件, 也就给出了一个布尔函数线性等价于某个既具有m阶相关免疫性且满足k次扩散准则的布尔函数的充分必要条件和相应的构造方法。作为应用, 笔者由既不具有相关免疫性、也不满足SAC的5元布尔函数出发, 构造了与其线性等价的既具有相关免疫性、也满足SAC的五元布尔函数。而文献[2,3]中的有关分析结果只是笔者的有关定理的特殊情况, 且文献[2]中的构造仅是针对扩散准则, 文献[3]中的构造仅是针对一阶相关免疫性的, 在一定意义上, 笔者对以往的有关分析工作做了理论升华, 并进一步考虑了用于密钥流非线性组合生成器的布尔函数的综合优良性问题。

《2 基本概念》

2 基本概念

凡x都表示

$x = (x_{1}, x_{2}, \dots, x_{n}) \in G F^{n} (2) ‚$ $x = (x_{1}, x_{2}, \dots, x_{n}) \in G F^{n} (2) ‚$

凡X都表示

$X = (X_{1}, X_{2}, \dots, X_{n}) ‚$ $X = (X_{1}, X_{2}, \dots, X_{n}) ‚$

其中X₁, X₂, …, X_n是定义在某概率空间 (Ω, F, P) 上相互独立的n个布尔随机变量, 且分布均匀:

$Ρ {X_{i} = 0} = Ρ {X_{i} = 1} = 1 / 2 ‚ 1 \leq i \leq n 。$ $Ρ {X_{i} = 0} = Ρ {X_{i} = 1} = 1 / 2 ‚ 1 \leq i \leq n 。$

记二元域为GF (2) , 布尔函数、点积w·x、汉明重量为W (w) 、Walsh循环谱S_(f) (w) 、自相关函数r_f (s) 、布尔函数相关免疫、扩散准则的定义见文献[6]。

定义1 ^[1] 称n元布尔函数g (x) 和f (x) 在线性变换意义下是等价的——简称为线性等价, 如果存在GF (2) 上的n×n可逆矩阵A和a, b∈GFⁿ (2) 及c∈GF (2) , 使得

$g (x) = f (x A + a) + b \cdot x + c ‚ x \in G F^{n} (2) (1)$ $g (x) = f (x A + a) + b \cdot x + c ‚ x \in G F^{n} (2) (1)$

定义2 ^[7] 称布尔函数f (x) , x∈GFⁿ (2) 是满足k (k≥1为正整数) 次扩散准则的, 若对所有的s∈GFⁿ (2) , 1≤W (s) ≤k, 其自相关函数r_f满足

$r_{f} (s) = 0 。$ $r_{f} (s) = 0 。$

特别称满足1次扩散准则的布尔函数是满足SAC的。

引理1 ^[8] 设f (x) , x∈GFⁿ (2) 是任一布尔函数, 则有

$\begin{array}{l} S_{(f)} (w) = 2 Ρ {f (X) + w \cdot X = 0} - 1 ‚ \\ w \in G F^{n} (2) 。 \end{array}$ $\begin{array}{l} S_{(f)} (w) = 2 Ρ {f (X) + w \cdot X = 0} - 1 ‚ \\ w \in G F^{n} (2) 。 \end{array}$

引理2 ^[6] 设f (x) , x∈GFⁿ (2) 是任一布尔函数, 则有

$\begin{array}{l} r_{f} (s) = 2 Ρ {f (X + s) + f (X) = 0} - 1 ‚ \\ s \in G F^{n} (2) 。 \end{array}$ $\begin{array}{l} r_{f} (s) = 2 Ρ {f (X + s) + f (X) = 0} - 1 ‚ \\ s \in G F^{n} (2) 。 \end{array}$

引理3 ^[9] 布尔函数f (x) , x∈GFⁿ (2) 是m阶相关免疫的充分必要条件是对所有的w∈GFⁿ (2) , 1≤W (w) ≤m, 都有S_(f) (w) =0。

引理1和引理2分别是布尔函数Walsh循环谱和自相关函数的概率表示式, 引理3是著名的Xiao-massey定理。

《3 主要结果》

3 主要结果

《3.1线性等价的两个布尔函数的Walsh循环谱之间的关系和自相关函数之间的关系》

3.1线性等价的两个布尔函数的Walsh循环谱之间的关系和自相关函数之间的关系

引理4 设n元布尔函数g (x) 和f (x) 线性等价, 即存在GF (2) 上的n×n可逆矩阵A和a, b∈GFⁿ (2) 及c∈GF (2) , 使g (x) =f (xA+a) +b·x+c, x∈GFⁿ (2) , 则g (x) 的Walsh循环谱S_(g) (·) 和f (x) 的Walsh循环谱S_(f) (·) 有下述关系:

$\begin{array}{l} S_{(g)} (w) = (- 1)^{c + a A^{- 1} (w + b)^{Τ}} \cdot \\ S_{(f)} ((w + b) (A^{- 1})^{Τ}) ‚ w \in G F^{n} (2) (2) \end{array}$ $\begin{array}{l} S_{(g)} (w) = (- 1)^{c + a A^{- 1} (w + b)^{Τ}} \cdot \\ S_{(f)} ((w + b) (A^{- 1})^{Τ}) ‚ w \in G F^{n} (2) (2) \end{array}$

证明根据引理1和点积的定义, 并注意到Y=XA+a仍是相互独立且都具有均匀分布的n维布尔随机向量, 即知

S_(g) (w) =2P{g (X) =w·X}-1=

2P{f (XA+a) +b·X+c=w·X}-1=

2P{f (Y) +c=X (AA^-1) (w+b) ^T}-1=

2P{f (Y) +c=[ (XA+a+a) A^-1 (w+b) ^T]}-

1=2P{f (Y) +c=[ (XA+a) A^-1 (w+b) ^T+

aA^-1 (w+b) ^T]}-1=2P{f (Y) +c=

[YA^-1 (w+b) ^T+aA^-1 (w+b) ^T]}-1=

2P{f (Y) +c=[ (w+b) (A^-1) ^T]Y^T+

aA^-1 (w+b) ^T}-1=2P{f (X) =

[ (w+b) (A^-1) ^T]·X+aA^-1 (w+b) ^T+c}-

1= (-1) ^{c+aA^-1 (w+b) ^T}S_(f) ( (w+b) (A^-1) ^T) ,

w∈GFⁿ (2) ,

因而式 (2) 成立。

特别取b=0∈GFⁿ (2) , c=1, 上述引理4的结论即为文献[8,10]中的相关结论。

引理5 设n元布尔函数g (x) 和f (x) 线性等价, 即存在GF (2) 上的n×n可逆矩阵A和a, b∈GFⁿ (2) 及c∈GF (2) , 使有g (x) =f (xA+a) +b·x+c, x∈GFⁿ (2) , 则g (x) 的自相关函数r_g (·) 和f (x) 的自相关函数r_f (·) 有下述关系:

$r_{g} (s) = (- 1)^{b \cdot s} r_{f} (s A) ‚ s \in G F^{n} (2) (3)$ $r_{g} (s) = (- 1)^{b \cdot s} r_{f} (s A) ‚ s \in G F^{n} (2) (3)$

证明根据引理2同样可知

$\begin{array}{l} r_{g} (s) = 2 Ρ {g (X + s) + g (X) = 0} - 1 = \\ 2 Ρ {f ((X + s) A + a) + b \cdot (X + s) + c + \\ f (X A + a) + b \cdot X + c = 0} - 1 = \\ 2 Ρ {f ((X A + a) + s A) + b \cdot s + f (X A + a) = \\ 0} - 1 = 2 Ρ {f (Y + s A) + f (Y) = b \cdot s} - \\ 1 = 2 Ρ {f (X + s A) + f (X) = b \cdot s} - 1 = \\ (- 1)^{b \cdot s} r_{f} (s A) ‚ s \in G F^{n} (2) ‚ \end{array}$ $\begin{array}{l} r_{g} (s) = 2 Ρ {g (X + s) + g (X) = 0} - 1 = \\ 2 Ρ {f ((X + s) A + a) + b \cdot (X + s) + c + \\ f (X A + a) + b \cdot X + c = 0} - 1 = \\ 2 Ρ {f ((X A + a) + s A) + b \cdot s + f (X A + a) = \\ 0} - 1 = 2 Ρ {f (Y + s A) + f (Y) = b \cdot s} - \\ 1 = 2 Ρ {f (X + s A) + f (X) = b \cdot s} - 1 = \\ (- 1)^{b \cdot s} r_{f} (s A) ‚ s \in G F^{n} (2) ‚ \end{array}$

因而式 (3) 成立。

《3.2线性等价意义下布尔函数性质的异同分析》

3.2线性等价意义下布尔函数性质的异同分析

根据上述引理4引理5, 可以清晰地分析线性等价的2个布尔函数有关性质的异同之处。

定理1 设n元布尔函数g (x) 和f (x) 线性等价, 即存在GF (2) 上的n×n可逆矩阵A和a, b∈GFⁿ (2) 及c∈GF (2) , 使有g (x) =f (xA+a) +b·x+c, x∈GFⁿ (2) , 记

$\begin{array}{l} S_{f 0} = {w : w \in G F^{n} (2), S_{(f)} (w) = 0}, \\ S_{g 0} = {w : w \in G F^{n} (2), S_{(g)} (w) = 0} ‚ \end{array}$ $\begin{array}{l} S_{f 0} = {w : w \in G F^{n} (2), S_{(f)} (w) = 0}, \\ S_{g 0} = {w : w \in G F^{n} (2), S_{(g)} (w) = 0} ‚ \end{array}$

则对w∈GFⁿ (2) , 有

$S_{(g)} (w) = 0 \Leftrightarrow S_{(f)} ((w + b) (A^{- 1})^{Τ}) = 0 (4)$ $S_{(g)} (w) = 0 \Leftrightarrow S_{(f)} ((w + b) (A^{- 1})^{Τ}) = 0 (4)$

因而成立|S_f0|=|S_g0|。

证明根据引理4中式 (2) , 并注意到矩阵A可逆即得。

定理2 设n元布尔函数g (x) 和f (x) 线性等价, 即存在GF (2) 上的n×n可逆矩阵A和a, b∈GFⁿ (2) 及c∈GF (2) , 使有g (x) =f (xA+a) +b·x+c, x∈GFⁿ (2) , 记f (x) 的全体线性结构之集 ^[7]为U_f, g (x) 的全体线性结构之集为U_g, 又记

$\begin{array}{l} R_{f 0} = {s ∶ s \in G F^{n} (2) ‚ r_{f} (s) = 0} ‚ \\ R_{g 0} = {s ∶ s \in G F^{n} (2) ‚ r_{g} (s) = 0} ‚ \end{array}$ $\begin{array}{l} R_{f 0} = {s ∶ s \in G F^{n} (2) ‚ r_{f} (s) = 0} ‚ \\ R_{g 0} = {s ∶ s \in G F^{n} (2) ‚ r_{g} (s) = 0} ‚ \end{array}$

则对s∈GFⁿ (2) , 有

$\begin{array}{l} | r_{g} (s A^{- 1}) | = 1 \Leftrightarrow | r_{f} (s) | = 1, \\ r_{g} (s A^{- 1}) = 0 \Leftrightarrow r_{f} (s) = 0 ‚ \end{array}$ $\begin{array}{l} | r_{g} (s A^{- 1}) | = 1 \Leftrightarrow | r_{f} (s) | = 1, \\ r_{g} (s A^{- 1}) = 0 \Leftrightarrow r_{f} (s) = 0 ‚ \end{array}$

因而成立

$U_{g} = {s A^{- 1} ∶ s \in U_{f}} ‚ R_{g 0} = {s A^{- 1} ∶ s \in R_{f 0}} ‚$ $U_{g} = {s A^{- 1} ∶ s \in U_{f}} ‚ R_{g 0} = {s A^{- 1} ∶ s \in R_{f 0}} ‚$

于是还有|U_g|=|U_f|, |R_g0|=|R_f0|。

证明根据引理5中式 (3) , 并注意到矩阵A可逆, 即得

$\begin{array}{l} r_{g} (s A^{- 1}) = (- 1)^{b \ 5 s A^{- 1}} r_{f} (s A^{- 1} A) = \\ (- 1)^{b \ 5 s A^{- 1}} r_{f} (s) 。 \end{array}$ $\begin{array}{l} r_{g} (s A^{- 1}) = (- 1)^{b \ 5 s A^{- 1}} r_{f} (s A^{- 1} A) = \\ (- 1)^{b \ 5 s A^{- 1}} r_{f} (s) 。 \end{array}$

定理1和定理2的结论告知, 2个线性等价的布尔函数Walsh循环谱的零点个数相同、线性结构点的个数相同、扩散点——自相关函数取值为零的点个数也相同, 但是它们Walsh循环谱的零点、线性结构点、扩散点又都可能不相同。

《3.3应用》

3.3应用

根据定理1和定理2的结论易知, 若取A为换位矩阵 (每一行的汉明重量都为1的可逆矩阵) , 则对任意的a∈GFⁿ (2) 及c∈GF (2) , 布尔函数f (x) 和与其线性等价的布尔函数g (x) =f (xA+a) +c有完全相同的相关免疫性——都不具有或同为m阶相关免疫的和完全相同的扩散特性——都不具有或同满足k次扩散准则。不仅如此, 应用前面的分析结果, 可以将某些不具有相关免疫性但满足适定条件的布尔函数线性变换为相关免疫的布尔函数, 且可将某些不具有扩散性但满足适定条件的布尔函数线性变换为满足扩散准则的布尔函数, 还可将某些既不具有相关免疫性也不满足扩散准则的布尔函数线性变换为既具有某阶相关免疫性、也满足某次扩散准则的布尔函数。为此, 再给出有关条件:

以w (i) ∈GFⁿ (2) 表示只有第i个分量取值为1的n维布尔向量, 1≤i≤n, …。一般地, 以w (i₁, …, i_k) ∈GFⁿ (2) 表示只有第i₁个分量、……、第i_k个分量取值为1的n维布尔向量, 1≤i₁<…<i_k≤n, 1≤k≤n-1, 则有

定理3 设f (x) , x∈GFⁿ (2) 是n元布尔函数, S_(f) (w) , w∈GFⁿ (2) 是其Walsh循环谱, 记

$S_{f 0} = {w ∶ w \in G F^{n} (2) ‚ S_{(f)} (w) = 0} ‚$ $S_{f 0} = {w ∶ w \in G F^{n} (2) ‚ S_{(f)} (w) = 0} ‚$

则f (x) , x∈GFⁿ (2) 线性等价于某m阶相关免疫的布尔函数的充分必要条件是存在GF (2) 上的n×n可逆矩阵B及b∈GFⁿ (2) , 使得

$\begin{array}{l} (w (i_{1}, \dots, i_{k}) + b) B \in S_{f 0}, \\ 1 \leq i_{1} ＜ \dots ＜ i_{k} \leq n ‚ 1 \leq k \leq m 。 \end{array}$ $\begin{array}{l} (w (i_{1}, \dots, i_{k}) + b) B \in S_{f 0}, \\ 1 \leq i_{1} ＜ \dots ＜ i_{k} \leq n ‚ 1 \leq k \leq m 。 \end{array}$

证明以B取代式 (4) 中的 (A^-1) ^T, 根据Xiao-massey定理即得。

定理4 设f (x) , x∈GFⁿ (2) 是n元布尔函数, S_(f) (w) , w∈GFⁿ (2) 是其Walsh循环谱, 记

$S_{f 0} = {w ∶ w \in G F^{n} (2) ‚ S_{(f)} (w) = 0} ‚$ $S_{f 0} = {w ∶ w \in G F^{n} (2) ‚ S_{(f)} (w) = 0} ‚$

那么, 若S_f0中存在n个线性无关的向量v⁽¹⁾, …, v⁽ⁿ⁾, 且

$\begin{array}{l} v^{(i_{1})} + \dots + v^{(i_{k})} \in S_{f 0}, \\ 1 \leq i_{1} ＜ \dots ＜ i_{k} \leq n ‚ 1 \leq k \leq m ‚ \end{array}$ $\begin{array}{l} v^{(i_{1})} + \dots + v^{(i_{k})} \in S_{f 0}, \\ 1 \leq i_{1} ＜ \dots ＜ i_{k} \leq n ‚ 1 \leq k \leq m ‚ \end{array}$

则f (x) , x∈GFⁿ (2) 线性等价于具有m阶相关免疫性的布尔函数

$g (x) = f (x A + a) + c ‚ x \in G F^{n} (2) ‚$ $g (x) = f (x A + a) + c ‚ x \in G F^{n} (2) ‚$

其中A是GF (2) 上的n×n可逆矩阵, 使得 (A^-1) ^T正是以S_f0中上述v⁽¹⁾, …, v⁽ⁿ⁾为行所得到的矩阵, 而a∈GFⁿ (2) 和c∈GF (2) 任意取定。

证明在定理3中取b=0∈GFⁿ (2) 即得。

注:文献[4]中所提到的LT方法的理论本质上就是定理4中的m=1的情况。

再以s (i) ∈GFⁿ (2) 表示只有第i个分量取值为1的n维布尔向量, 1≤i≤n, …。一般地, 以s (i₁, …, i_k) ∈GFⁿ (2) 表示只有第i₁个分量、……、第i_k个分量取值为1的n维布尔向量, 1≤i₁<…<i_k≤n, 1≤k≤n-1, 则有

定理5 设f (x) , x∈GFⁿ (2) 是n元布尔函数, r_f (s) , s∈GFⁿ (2) 是其自相关函数, 记

$R_{f 0} = {s ∶ s \in G F^{n} (2) ‚ r_{f} (s) = 0} ‚$ $R_{f 0} = {s ∶ s \in G F^{n} (2) ‚ r_{f} (s) = 0} ‚$

则f (x) , x∈GFⁿ (2) 线性等价于某满足k次扩散准则的布尔函数的充分必要条件是R_f0中存在n个线性无关的向量τ⁽¹⁾, …, τ⁽ⁿ⁾, 且

$\begin{array}{l} τ^{(i_{1})} + \dots + τ^{(i_{h})} \in R_{f 0}, \\ 1 \leq i_{1} ＜ \dots ＜ i_{h} \leq n ‚ 1 \leq h \leq k 。 \end{array}$ $\begin{array}{l} τ^{(i_{1})} + \dots + τ^{(i_{h})} \in R_{f 0}, \\ 1 \leq i_{1} ＜ \dots ＜ i_{h} \leq n ‚ 1 \leq h \leq k 。 \end{array}$

证明首先考虑k=1的情况:

必要性设与f (x) , x∈GFⁿ (2) 线性等价的g (x) =f (xA+a) +b·x+c满足严格雪崩准则, 即有r_g (s (i) ) =0, 1≤i≤n, 记矩阵A的第i行为τ⁽ⁱ⁾, 1≤i≤n, 而根据式 (3) 知

$r_{f} (s (i) A) = r_{g} (s (i)) = 0 ‚ 1 \leq i \leq n ‚$ $r_{f} (s (i) A) = r_{g} (s (i)) = 0 ‚ 1 \leq i \leq n ‚$

就是说

$τ^{(i)} = s (i) A \in R_{f 0} ‚ 1 \leq i \leq n ‚$ $τ^{(i)} = s (i) A \in R_{f 0} ‚ 1 \leq i \leq n ‚$

且由矩阵A可逆还知τ⁽ⁱ⁾, 1≤i≤n线性无关。

充分性若R_f0中存在n个线性无关的向量τ⁽¹⁾, …, τ⁽ⁿ⁾, 记以τ⁽¹⁾, …, τ⁽ⁿ⁾为行的矩阵为A, 则对任意的a, b∈GFⁿ (2) 及c∈GF (2) , 根据式 (3) 知与f (x) 线性等价的

$g (x) = f (x A + a) + b \cdot x + c$ $g (x) = f (x A + a) + b \cdot x + c$

的自相关函数都满足

$\begin{array}{l} r_{g} (s (i)) = (- 1)^{b \cdot s (i)} r_{f} (s (i) A) = \\ (- 1)^{b \cdot s (i)} r_{f} (τ^{(i)}) ‚ 1 \leq i \leq n ‚ \end{array}$ $\begin{array}{l} r_{g} (s (i)) = (- 1)^{b \cdot s (i)} r_{f} (s (i) A) = \\ (- 1)^{b \cdot s (i)} r_{f} (τ^{(i)}) ‚ 1 \leq i \leq n ‚ \end{array}$

可见g (x) =f (xA+a) + b·x +c都满足严格雪崩准则。

又注意到

$s (i_{1}, \dots, i_{h}) = s (i_{1}) + \dots + s (i_{h}) ‚ 1 \leq h \leq k ‚$ $s (i_{1}, \dots, i_{h}) = s (i_{1}) + \dots + s (i_{h}) ‚ 1 \leq h \leq k ‚$

同理可知定理5成立。

注:显然, 综合定理3或定理4与定理5的条件, 即可得到一个布尔函数线性等价于一个既具有某阶相关免疫性、也满足某次扩散准则的布尔函数的条件, 也同时提供了一种构造既具有相关免疫性、也满足扩散准则的布尔函数的方法。

例1 设5元布尔函数

$\begin{array}{l} f (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = \\ x_{1} x_{2} x_{3} + x_{2} x_{3} x_{4} + x_{1} x_{2} + x_{1} x_{3} + x_{1} x_{4} + \\ x_{1} x_{5} + x_{2} x_{5} + x_{3} x_{4} + x_{4} x_{5} + x_{1} + x_{2} ‚ \end{array}$ $\begin{array}{l} f (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = \\ x_{1} x_{2} x_{3} + x_{2} x_{3} x_{4} + x_{1} x_{2} + x_{1} x_{3} + x_{1} x_{4} + \\ x_{1} x_{5} + x_{2} x_{5} + x_{3} x_{4} + x_{4} x_{5} + x_{1} + x_{2} ‚ \end{array}$

其中 (x₁, x₂, x₃, x₄, x₅) ∈GF⁵ (2) 。算得

S_f0={ (0, 0, 0, 0, 0) , (0, 0, 0, 0, 1) , (0, 0, 0, 1, 0) , (0, 0, 1, 0, 0) , (1, 0, 0, 0, 0) , (1, 1, 0, 0, 0) , (1, 0, 1, 0, 0) , (0, 0, 1, 0, 1) , (0, 0, 1, 1, 0) , (0, 1, 0, 0, 1) , (0, 1, 0, 1, 0) , (0, 1, 1, 0, 0) , (1, 1, 1, 0, 0) , (1, 1, 0, 1, 0) , (0, 1, 1, 0, 1) , (0, 1, 1, 1, 0) , (1, 0, 0, 1, 1) , (1, 0, 1, 1, 0) , (1, 1, 1, 1, 0) , (1, 1, 0, 1, 1) , (1, 0, 1, 1, 1) , (1, 1, 1, 1, 1) },

R_f0={ (0, 0, 0, 0, 1) , (0, 0, 0, 1, 0) , (0, 1, 0, 0, 0) , (1, 0, 0, 0, 0) , (0, 0, 0, 1, 1) , (0, 1, 0, 0, 1) , (0, 0, 1, 1, 0) , (0, 1, 1, 0, 0) , (1, 0, 0, 0, 1) , (1, 0, 0, 1, 0) , (1, 0, 1, 0, 0) , (0, 0, 1, 1, 1) , (0, 1, 1, 0, 1) , (1, 0, 1, 0, 1) , (1, 1, 0, 1, 0) , (1, 1, 0, 1, 1) , (1, 1, 1, 1, 0) , (1, 1, 1, 1, 1) },

易知f平衡。因为 (0, 1, 0, 0, 0) ∈/S_f0, (0, 0, 1, 0, 0) ∈/R_f0, 所以由定义2和引理3还知f不具有相关免疫性且不满足SAC。在S_f0中取5个线性无关的向量构成矩阵 (A^-1) ^T:

$\begin{array}{l} (A^{- 1})^{Τ} = (\begin{matrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}), \\ 得 A = (\begin{matrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}) 。 \end{array}$ $\begin{array}{l} (A^{- 1})^{Τ} = (\begin{matrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}), \\ 得 A = (\begin{matrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}) 。 \end{array}$

由于A的5个行向量正好都在R_f0中, 所以根据可逆线性变换的不变性及定理4和定理5知, 与f线性等价的布尔函数

$g (x) = f (x A + a) + c ‚ x \in G F^{5} (2)$ $g (x) = f (x A + a) + c ‚ x \in G F^{5} (2)$

平衡、具有相关免疫性并且满足SAC, 其中a∈GF⁵ (2) 和c∈GF (2) 任意取定。如取

$(0, 0, 0, 0, 0) = 0 = a ‚ c = 0 ‚$ $(0, 0, 0, 0, 0) = 0 = a ‚ c = 0 ‚$

则布尔函数

$\begin{array}{l} g (x) = f (x A) = f (x_{1}, x_{2} + x_{3}, x_{3}, x_{4}, x_{5}) = \\ (x_{1} + x_{2} + x_{3} + x_{4}) x_{5} + x_{1} + x_{2} + x_{3} + \\ x_{1} x_{2} + x_{1} x_{3} + x_{1} x_{4} + x_{1} x_{2} x_{3} + x_{2} x_{3} x_{4} = \\ x_{1} x_{2} x_{3} + x_{2} x_{3} x_{4} + x_{1} x_{2} + x_{1} x_{3} + x_{1} x_{4} + \\ x_{1} x_{5} + x_{2} x_{5} + x_{3} x_{5} + x_{4} x_{5} + x_{1} + x_{2} + x_{3} \end{array}$ $\begin{array}{l} g (x) = f (x A) = f (x_{1}, x_{2} + x_{3}, x_{3}, x_{4}, x_{5}) = \\ (x_{1} + x_{2} + x_{3} + x_{4}) x_{5} + x_{1} + x_{2} + x_{3} + \\ x_{1} x_{2} + x_{1} x_{3} + x_{1} x_{4} + x_{1} x_{2} x_{3} + x_{2} x_{3} x_{4} = \\ x_{1} x_{2} x_{3} + x_{2} x_{3} x_{4} + x_{1} x_{2} + x_{1} x_{3} + x_{1} x_{4} + \\ x_{1} x_{5} + x_{2} x_{5} + x_{3} x_{5} + x_{4} x_{5} + x_{1} + x_{2} + x_{3} \end{array}$

平衡、具有相关免疫性且满足SAC, 而直接由定义容易验证g (x) 确实是平衡、具有相关免疫性且满足SAC的。

例2 设5元布尔函数

$\begin{array}{l} f (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = x_{1} x_{2} + x_{3} x_{4} + x_{5} ‚ \\ (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) \in G F^{5} (2) ‚ \end{array}$ $\begin{array}{l} f (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = x_{1} x_{2} + x_{3} x_{4} + x_{5} ‚ \\ (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) \in G F^{5} (2) ‚ \end{array}$

得到

$\begin{array}{l} S_{f 0} = {(w_{1}, w_{2}, w_{3}, w_{4}, 0) ∶ \\ (w_{1}, w_{2}, w_{3}, w_{4}) \in G F^{4} (2)} ‚ \\ R_{f 0} = G F^{5} (2) \ \\ {(0, 0, 0, 0, 0), (0, 0, 0, 0, 1)} ‚ \end{array}$ $\begin{array}{l} S_{f 0} = {(w_{1}, w_{2}, w_{3}, w_{4}, 0) ∶ \\ (w_{1}, w_{2}, w_{3}, w_{4}) \in G F^{4} (2)} ‚ \\ R_{f 0} = G F^{5} (2) \ \\ {(0, 0, 0, 0, 0), (0, 0, 0, 0, 1)} ‚ \end{array}$

因为 (0, 0, 0, 0, 1) ∈/S_f0, (0, 0, 0, 0, 1) ∈/R_f0, 由定义2和引理3知f不具有相关免疫性且不满足SAC。取可逆矩阵

$\begin{array}{l} (A^{- 1})^{Τ} = B = (\begin{matrix} 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 \end{matrix}) ‚ \\ 得 A = (\begin{matrix} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \end{matrix}) ‚ \end{array}$ $\begin{array}{l} (A^{- 1})^{Τ} = B = (\begin{matrix} 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 \end{matrix}) ‚ \\ 得 A = (\begin{matrix} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \end{matrix}) ‚ \end{array}$

又取b= (0, 0, 0, 0, 1) , 因为 (w (i) +b) B∈S_f0, 1≤i≤5, 且A的5个行向量正好都在R_f0中, 所以根据定理3和定理5知, 与f线性等价的布尔函数

$g (x) = f (x A + a) + b \cdot x + c ‚ x \in G F^{5} (2) ‚$ $g (x) = f (x A + a) + b \cdot x + c ‚ x \in G F^{5} (2) ‚$

具有相关免疫性且满足SAC, 其中a∈GF⁵ (2) 和c∈GF (2) 任意取定。如取

$(0, 0, 0, 0, 0) = 0 = a ‚ c = 0 ‚$ $(0, 0, 0, 0, 0) = 0 = a ‚ c = 0 ‚$

则布尔函数

g (x) =f (xA) +b·x=f (x₂+x₅, x₁+x₅, x₁+x₂+x₃+x₅, x₁+x₂+x₄+x₅, x₁+x₂+x₅) +x₅= (x₂+x5) (x₁+x₅) + (x₁+x₂+x₃+x₅) (x₁+x₂+x₄+x₅) + (x₁+x₂+x₅) +x₅=x₁x₂+x₁x₃+x₁x₄+x₁x₅+x₂x₃+x₂x₄+x₂x₅+x₃x₄+x₃x₅+x₄x₅

具有相关免疫性且满足SAC, 而直接由定义容易验证g (x) 确实是具有相关免疫性且满足SAC的。

不难知, 在例1和例2中还能构造别的与题设5元布尔函数f线性等价的、既具有相关免疫性也满足SAC的布尔函数。

《4 结语》

4 结语

笔者利用概率方法得到了线性等价的2个布尔函数的Walsh循环谱及自相关函数之间的关系, 由此给出了一个布尔函数线性等价于m阶相关免疫函数的Walsh循环谱刻画和线性等价于k次扩散准则函数的自相关刻画, 并给出了利用线性等价性构造同时具有相关免疫性和扩散性的布尔函数的方法和实例, 为在密码设计中将某些不满足相关免疫要求和扩散要求 (但满足适定条件) 的布尔函数线性变换为满足要求的函数提供了一种方法, 同时也为设计密钥流非线性组合生成器时综合各种优良性的需求提供了可行性。

Show More