在诸多密码攻击方法中有一种差分方法, 是以输入的改变导致输出有相对较大改变为基础的一种攻击方法, 针对此种攻击, Webster和Tavares定义了布尔函数的严格雪崩准则 (SAC) 的概念:如果一个函数满足严格雪崩准则, 那么当输入只有1 b改变时, 输出改变的概率将是1/2
[1 ] , 故以这样的布尔函数为非线性组合器产生的密钥流能够抗针对输入只改变1 b时的差分攻击。基于此, 人们对满足严格雪崩准则的布尔函数的性质和构造等进行了一系列研究
[2 ,3 ,4 ,5 ] , 文献[2 ] 得到了布尔函数满足严格雪崩准则的谱判别条件。
然而在选择性明文攻击中, 密码破译者们又可以通过固定某些输入比特为常值后再作差分攻击, 为此, Forre'对布尔函数的严格雪崩准则概念进行了拓展, 给出了布尔函数满足k 阶严格雪崩准则的定义, 并得到了布尔函数满足k 阶严格雪崩准则的谱判别条件
[2 ] 。以上工作对密码的设计者和分析者无疑都是有意义的。
依据实际应用的需要, 近年来人们在密码学中对多值逻辑函数的有关性质和构造给予了更多的关注, 将布尔函数的许多研究成果都拓广到了多值逻辑函数中, 也特别给出了多值逻辑函数的严格雪崩准则的概念
[6 ] , 有不少成果问世 (参见文献[6 ,7 ] ) 。但是, 多值逻辑函数满足高阶严格雪崩准则的定义迄今尚未见到。笔者给出了剩余类环Z m 上逻辑函数满足k 阶严格雪崩准则的定义, 证明了m 值逻辑函数满足高阶严格雪崩准则时一定满足低阶严格雪崩准则, 考虑到谱在逻辑函数密码学性质研究中所发挥的作用, 肖国镇、冯登国教授等在这方面做了很出色的工作
[6 ] , 笔者还利用反演公式得到了谱的一个分解公式, 据此给出了m 值逻辑函数满足k 阶严格雪崩准则的一个谱判别条件, 将文献[2 ] 中的结果推广到了一般的m 值逻辑函数。为记号简便, 只就k =1的情况给出m 值逻辑函数满足k 阶严格雪崩准则的主要结论的证明。
《1 基本概念和预备知识》
1 基本概念和预备知识
以下m ≥2是任一取定的正整数, 且以Z m 记整数模m 的剩余类环, 又对任一取定的正整数n , 以Z n m m n 表示n 个Z m 的笛卡尔积。当w = (w 1 , w 2 , …, w n ) ∈Z n m 时, 称w 的不为0元的分量个数为其汉明重量, 且记为W (w ) 。
定义1
[7 ] Z n m m n →Z m 的任一映射f 都为Z n m m n 上的n 个变元的m 值逻辑函数, 即若x = (x 1 , x 2 , …, x n ) ∈Z n m m n , 则f (x ) =f (x 1 , x 2 , …, x n ) ∈Z m 。
定义2
[7 ] 设x = (x 1 , x 2 , …, x n ) ∈Z n m m n , w = (w 1 , w 2 , …, w n ) ∈Z n m m n , 则x 和w 的点积定义为w ·x =w 1 x 1 +w 2 x 2 +…+w n x n (mod m ) , 则n 元m 值逻辑函数f (x ) , x ∈Z n m m n 的第二种Chrestenson变换定义为
S ( f ) ( w ) = 1 m n ∑ x ∈ Z n m u f ( x ) − w \ 5 x , w ∈ Z n m ‚ S ( f ) ( w ) = 1 m n ∑ x ∈ Ζ m n u f ( x ) - w \ 5 x , w ∈ Ζ m n ‚
称S (f ) (w ) , w ∈Z n m m n 为f (x ) 的Chrestenson循环谱。
定义3
[6 ] 设f (x ) , x ∈Z n m m n 是m 值逻辑函数, 对x = (x 1 , x 2 , …, x n ) ∈Z n m m n , s = (s 1 , s 2 , …, s n ) ∈Z n m m n 记x +s = (x 1 +s 1 , x 2 +s 2 , …, x n +s n ) , 称
r f ( s ) = 1 m n ∑ x ∈ Z n m u f ( x + s ) − f ( x ) r f ( s ) = 1 m n ∑ x ∈ Ζ m n u f ( x + s ) - f ( x )
定义4
[7 ] 称m 值逻辑函数f (x ) , x ∈Z n m m n 是满足严格雪崩准则的, 若f (x ) 的自相关函数r f 满足r f (s ) =0, s ∈Z n m m n , W (s ) =1。
定义5 设n ≥2, 1≤k <n , 称n 元m 值逻辑函数f (x 1 , x 2 , …, x n ) 是满足k 阶严格雪崩准则的, 如果取定f (x 1 , x 2 , …, x n ) 的n 个变元x 1 , x 2 , …, x n 中的任意k 个后, 所得n -k 元的m 值逻辑函数都是满足严格雪崩准则的。
下设X = (X 1 , X 2 , …, X n ) 中的X 1 , X 2 , …, X n 是定义在同一概率空间 (Ω , F , P ) 上相互独立且都具有均匀分布的m 值随机变量, 即对任意的 (a 1 , a 2 , …, a n ) ∈Z n m , 都有
P { X 1 = a 1 , X 2 = a 2 , ⋯ , X n = a n } = P { X 1 = a 1 } ⋅ P { X 2 = a 2 } ⋅ ⋯ ⋅ P { X n = a n } , Ρ { X 1 = a 1 , X 2 = a 2 , ⋯ , X n = a n } = Ρ { X 1 = a 1 } ⋅ Ρ { X 2 = a 2 } ⋅ ⋯ ⋅ Ρ { X n = a n } ,
和P {X i =a } =1/m , a ∈Z m , 1≤i ≤n , 则易知对任一m 值逻辑函数f (x 1 , …, x n ) , f (X 1 , …, X n ) 也为 (Ω , F , P ) 上的m 值随机变量。
在上述记号的意义下, 关于m 值逻辑函数的自相关函数的概率表示式已有下面的结果:
定理1
[7 ] 对任一m 值逻辑函数f (x ) , x ∈Z n m m n , 都有
r f ( s ) = ∑ r ∈ Z m u r P { f ( X + s ) − f ( X ) = r } , s ∈ Z n m 。 r f ( s ) = ∑ r ∈ Ζ m u r Ρ { f ( X + s ) - f ( X ) = r } , s ∈ Ζ m n 。
定理2
[8 ] (反演公式) 对任一m 值逻辑函数f (x ) 与其Chrestenson循环谱的关系为
u f ( x ) = ∑ w ∈ Z n m S ( f ) ( w ) \ 5 u w \ 5 x , x ∈ Z n m 。 u f ( x ) = ∑ w ∈ Ζ m n S ( f ) ( w ) \ 5 u w \ 5 x , x ∈ Ζ m n 。
关于m 值逻辑函数满足严格雪崩准则的Chrestenson谱判别条件, 又已有下面的结果:
定理3
[7 ] m 值逻辑函数f (x ) , x ∈Z n m m n 满足严格雪崩准则的充分必要条件是对所有的1≤j ≤n , 只要s j ∈Z m 0}, 就都成立
∑ w ∈ Z n m | S ( f ) ( w ) | 2 \ 5 u w j \ 5 s j = 0 。 ∑ w ∈ Ζ m n | S ( f ) ( w ) | 2 \ 5 u w j \ 5 s j = 0 。
《2 主要结果》
2 主要结果
定理4 如果m 值逻辑函数f (x ) , x ∈Z n m m n 满足k 阶严格雪崩准则, 那么f (x ) 必定满足k -1阶严格雪崩准则 (0阶严格雪崩准则即原来意义下的严格雪崩准则) 。
证明 为记号简单, 只给出满足1阶严格雪崩准则必定满足严格雪崩准则的证明。
设m 值逻辑函数f (x 1 , x 2 , …, x n ) 满足1阶严格雪崩准则, 根据定义知, 此时对任意的1≤i ≤n 和a ∈Z m , n -1元m 值逻辑函数
f i : a ( x ( i ) ) = f ( x 1 , ⋯ , x i − 1 , a , x i + 1 , ⋯ , x n ) f i : a ( x ( i ) ) = f ( x 1 , ⋯ , x i - 1 , a , x i + 1 , ⋯ , x n )
都要满足严格雪崩准则, 再根据定理1, 即知对任意的a ∈Z m 和
s ∗ = ( s 1 , ⋯ , s i − 1 , s i + 1 , ⋯ , s n ) ∈ Z n − 1 m 且 W ( s ∗ ) = 1 ‚ r f i : a ( s 1 , ⋯ , s i − 1 , s i + 1 , ⋯ , s n ) = ∑ r ∈ Z m u r P { f ( X 1 + s 1 , ⋯ , X i − 1 + s i − 1 , a , X i + 1 + s i + 1 , ⋯ , X n + s n ) − f ( X 1 , ⋯ , X i − 1 , a , X i + 1 , ⋯ , X n + s n ) = r } = 0 s * = ( s 1 , ⋯ , s i - 1 , s i + 1 , ⋯ , s n ) ∈ Ζ m n - 1 且 W ( s * ) = 1 ‚ r f i : a ( s 1 , ⋯ , s i - 1 , s i + 1 , ⋯ , s n ) = ∑ r ∈ Ζ m u r Ρ { f ( X 1 + s 1 , ⋯ , X i - 1 + s i - 1 , a , X i + 1 + s i + 1 , ⋯ , X n + s n ) - f ( X 1 , ⋯ , X i - 1 , a , X i + 1 , ⋯ , X n + s n ) = r } = 0
今设s = (s 1 , …, s n ) ∈Z n m m n 且W (s ) =1, 即s 中仅有一个分量不为0, 不妨设
s 1 ≠ 0 , 即 s = ( s 1 , 0 , ⋯ , 0 ) , s 1 ≠ 0 , 即 s = ( s 1 , 0 , ⋯ , 0 ) ,
r f ( s 1 , 0 , ⋯ , 0 ) = ∑ r ∈ Z m u r P { f ( X 1 + s 1 , X 2 , X 3 , ⋯ , X n ) − f ( X 1 , X 2 , X 3 , ⋯ , X n ) = r } = ∑ r ∈ Z m ∑ a ∈ Z m u r P { f ( X 1 + s 1 , a , X 3 , ⋯ , X n ) − f ( X 1 , a , X 3 , ⋯ , X n ) = r , X 2 = a } = 0 ∑ r ∈ Z m ∑ a ∈ Z m u r P { f ( X 1 + s 1 , a , X 3 , ⋯ , X n ) − f ( X 1 , a , X 3 , ⋯ , X n ) = r } P { X 2 = a } = 1 m ∑ r ∈ Z m [ ∑ a ∈ Z m u r P { f ( X 1 + s 1 , a , X 3 , ⋯ , X n ) − f ( X 1 , a , X 3 , ⋯ , X n ) = r } ] = 0 ‚ r f ( s 1 , 0 , ⋯ , 0 ) = ∑ r ∈ Ζ m u r Ρ { f ( X 1 + s 1 , X 2 , X 3 , ⋯ , X n ) - f ( X 1 , X 2 , X 3 , ⋯ , X n ) = r } = ∑ r ∈ Ζ m ∑ a ∈ Ζ m u r Ρ { f ( X 1 + s 1 , a , X 3 , ⋯ , X n ) - f ( X 1 , a , X 3 , ⋯ , X n ) = r , X 2 = a } = 0 ∑ r ∈ Ζ m ∑ a ∈ Ζ m u r Ρ { f ( X 1 + s 1 , a , X 3 , ⋯ , X n ) - f ( X 1 , a , X 3 , ⋯ , X n ) = r } Ρ { X 2 = a } = 1 m ∑ r ∈ Ζ m [ ∑ a ∈ Ζ m u r Ρ { f ( X 1 + s 1 , a , X 3 , ⋯ , X n ) - f ( X 1 , a , X 3 , ⋯ , X n ) = r } ] = 0 ‚
定理4告知, m 值逻辑函数满足k (≥1) 阶严格雪崩准则的一个必要条件是它必须满足通常意义下的严格雪崩准则。
根据m 值逻辑函数满足k (≥1) 阶严格雪崩准则的定义不难得到如下引理:
引理1 m 值逻辑函数f (x ) , x ∈Z n m m n 满足k 阶严格雪崩准则的充分必要条件是对所有的正整数1≤i ≤n 和a ∈Z m , 取定x i =a 后所得n -1元函数f (x 1 , …, x i -1 , a , x i +1 , …, x n ) 满足k -1阶严格雪崩准则。
注意: 对任意的1≤i ≤n , n 元m 值逻辑函数f (x ) , x ∈Z n m m n 都可表示为
f ( x 1 , ⋯ , x i − 1 , x i , x i + 1 , ⋯ , x n ) = ∑ r ∈ Z m I { a } ( x i ) f i : a ( x ( i ) ) , ( x 1 , x 2 , ⋯ , x n ) ∈ Z n m , f ( x 1 , ⋯ , x i - 1 , x i , x i + 1 , ⋯ , x n ) = ∑ r ∈ Ζ m Ι { a } ( x i ) f i : a ( x ( i ) ) , ( x 1 , x 2 , ⋯ , x n ) ∈ Ζ m n ,
f i :a (x (i ) ) =f (x 1 , …, x i -1 , a , x i +1 , …, x n ) ,
I { a } ( x i ) = { 1 , x i = a ‚ 0 , x i ≠ a , x i ∈ Z m , a ∈ Z m 。 Ι { a } ( x i ) = { 1 , x i = a ‚ 0 , x i ≠ a , x i ∈ Ζ m , a ∈ Ζ m 。
w = ( w 1 , ⋯ , w i − 1 , k , w i + 1 , ⋯ , w n ) ∈ Z n m w = ( w 1 , ⋯ , w i - 1 , k , w i + 1 , ⋯ , w n ) ∈ Ζ m n
w ( i ) = ( w 1 , ⋯ , w i − 1 , w i + 1 , ⋯ , w n ) , X ( i ) = ( X 1 , ⋯ , X i − 1 , X i + 1 , ⋯ , X n ) 。 w ( i ) = ( w 1 , ⋯ , w i - 1 , w i + 1 , ⋯ , w n ) , X ( i ) = ( X 1 , ⋯ , X i - 1 , X i + 1 , ⋯ , X n ) 。
定理5 设f (x 1 , …, x n ) 是任一m 值逻辑函数, 则对任意的1≤i ≤n , 当f 表示为
f ( x 1 , ⋯ , x i − 1 , a , x i + 1 , ⋯ , x n ) = ∑ r ∈ Z m I { a } ( x i ) f i : a ( x ( i ) ) f ( x 1 , ⋯ , x i - 1 , a , x i + 1 , ⋯ , x n ) = ∑ r ∈ Ζ m Ι { a } ( x i ) f i : a ( x ( i ) )
S ( f i : a ) ( w ( i ) ) = ∑ k ∈ Z m u a k S ( f ) ( k , w ( i ) ) , a ∈ Z m ( 1 ) S ( f i : a ) ( w ( i ) ) = ∑ k ∈ Ζ m u a k S ( f ) ( k , w ( i ) ) , a ∈ Ζ m ( 1 )
证明 根据m 值逻辑函数Chrestenson谱定义式和反演公式可知, 对任意取定的a ∈Z m 和 (k , w (i ) ) ∈Z n m m n 都有
S ( f i : a ) ( w ( i ) ) = 1 m n − 1 ∑ x ′′ ∈ Z n − 1 m u f i : a ( x ( i ) ) u − w ( i ) \ 5 x ′′ = 1 m n − 1 ∑ x ′′ ∈ Z n − 1 m ∑ k ∈ z m , v ( i ) ∈ Z n − 1 m S ( f ) ( k , v ( i ) ) u k a + v ( i ) \ 5 x ′′ ⋅ u − w ( i ) \ 5 x ′′ = 1 m n − 1 ∑ k ∈ z m , v ( i ) ∈ Z n − 1 m u k a S ( f ) ( k , v ( i ) ) ⋅ ∑ x ′′ ∈ Z n − 1 m u [ v ( i ) − w ( i ) ] x ′′ = ∑ k ∈ Z m u k a S ( f ) ( k , w ( i ) ) 。 S ( f i : a ) ( w ( i ) ) = 1 m n - 1 ∑ x ″ ∈ Ζ m n - 1 u f i : a ( x ( i ) ) u - w ( i ) \ 5 x ″ = 1 m n - 1 ∑ x ″ ∈ Ζ m n - 1 ∑ k ∈ z m , v ( i ) ∈ Ζ m n - 1 S ( f ) ( k , v ( i ) ) u k a + v ( i ) \ 5 x ″ ⋅ u - w ( i ) \ 5 x ″ = 1 m n - 1 ∑ k ∈ z m , v ( i ) ∈ Ζ m n - 1 u k a S ( f ) ( k , v ( i ) ) ⋅ ∑ x ″ ∈ Ζ m n - 1 u [ v ( i ) - w ( i ) ] x ″ = ∑ k ∈ Ζ m u k a S ( f ) ( k , w ( i ) ) 。
特别在m =2, i =n 时, 注意到u =-1, 定理5中的式 (1) 即是布尔函数性质研究中发挥了重要作用的那个著名公式
S f i : 1 ( w ( n ) ) = S ( f ) ( 0 , w ( n ) ) − S ( f ) ( 1 , w ( n ) ) , S f i : 0 ( w ( n ) ) = S ( f ) ( 0 , w ( n ) ) + S ( f ) ( 1 , w ( n ) ) 。 S f i : 1 ( w ( n ) ) = S ( f ) ( 0 , w ( n ) ) - S ( f ) ( 1 , w ( n ) ) , S f i : 0 ( w ( n ) ) = S ( f ) ( 0 , w ( n ) ) + S ( f ) ( 1 , w ( n ) ) 。
对任一w = (w 1 , …, w i -1 , w i , w i +1 , …, w n ) ∈Z n m m n 再记
w i 1 , a 1 , ⋯ , i k , a k = ( w 1 , ⋯ , w i 1 − 1 , w i 1 + a 1 , w i 1 + 1 , ⋯ , w i k − 1 , w i k + a k , w i k + 1 , ⋯ , w n ) ∈ Z n m 。 w i 1 , a 1 , ⋯ , i k , a k = ( w 1 , ⋯ , w i 1 - 1 , w i 1 + a 1 , w i 1 + 1 , ⋯ , w i k - 1 , w i k + a k , w i k + 1 , ⋯ , w n ) ∈ Ζ m n 。
根据定理5和引理1, 可以得到m 值逻辑函数满足k 阶严格雪崩准则的如下谱判别条件:
定理6 m 值逻辑函数f (x ) , x ∈Z n m m n 满足k 阶严格雪崩准则的充分必要条件是对所有的1≤i 1 <…<i k ≤n , 1≤j ≤n 且{j }⊂{1, 2, …, n }i 1 , …, i k }, s j ∈Z m 0}和对任意的 (a 1 , …, a k ) ∈Z k m m k ,
∑ w ∈ Z n m [ S ( f ) ( w ) S ¯ ¯ ( f ) ( w i 1 , a 1 , ⋯ , i k , a k ) ] u w j s j = 0 ∑ w ∈ Ζ m n [ S ( f ) ( w ) S ¯ ( f ) ( w i 1 , a 1 , ⋯ , i k , a k ) ] u w j s j = 0
特别当k =1时, m 值逻辑函数f (x ) , x ∈Z n m m n 满足1阶严格雪崩准则的充分必要条件是对所有的i , j ∈{1, 2, …, n }且i ≠ j , s j ∈Z m 0}和对任意的a ∈Z m ,
∑ w ∈ Z n m S ( f ) ( w ) S ¯ ¯ ( f ) ( w i , a ) u w j s j = 0 ∑ w ∈ Ζ m n S ( f ) ( w ) S ¯ ( f ) ( w i , a ) u w j s j = 0
证明 为记号简单, 只就k =1的情况给出m 值逻辑函数满足k 阶严格雪崩准则的主要证明, 一般结论可再根据引理1由数学归纳法得到。
由定义5和定理3可知, f (x ) 满足1阶严格雪崩准则的充分必要条件, 是对所有的i , j ∈{1, 2, …, n }且i ≠j , s j ∈Z m 0}和对任意的a ∈Z m , 都有
∑ w ( i ) ∈ Z n − 1 m | S ( f i : a ) ( w ( i ) ) | 2 u w j s j = 0 。 ∑ w ( i ) ∈ Ζ m n - 1 | S ( f i : a ) ( w ( i ) ) | 2 u w j s j = 0 。
而根据定理5, 在上述记号的意义下, 对所有的a ∈Z m , 就有
∑ w ( i ) ∈ Z n − 1 m | S ( f i : a ) ( w ( i ) ) | 2 u w j s j = S 0 + u a S 1 + ⋯ + u a ( m − 1 ) S m − 1 ( 3 ) ∑ w ( i ) ∈ Ζ m n - 1 | S ( f i : a ) ( w ( i ) ) | 2 u w j s j = S 0 + u a S 1 + ⋯ + u a ( m - 1 ) S m - 1 ( 3 )
因而, 若S 0 =S 1 =…=S m -1 =0, 则由式 (3) 即知对所有的a ∈Z m , 都有
∑ w ( i ) ∈ Z n − 1 m | S ( f i : a ) ( w ( i ) ) | 2 \ 5 u w j s j = 0 。 ∑ w ( i ) ∈ Ζ m n - 1 | S ( f i : a ) ( w ( i ) ) | 2 \ 5 u w j s j = 0 。
反之, 若对所有的a ∈Z m , 式 (3) 都成立, 则在式 (3) 中取遍a ∈Z m , 就得到关于S 0 , S 1 , …, S m -1 的方程组
⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ S 0 + S 1 + ⋯ + S m − 1 = 0 , S 0 + u S 1 + ⋯ u m − 1 S m − 1 = 0 , ⋮ S 0 + u m − 1 S 1 + ⋯ + u ( m − 1 ) ( m − 1 ) S m − 1 = 0 , { S 0 + S 1 + ⋯ + S m - 1 = 0 , S 0 + u S 1 + ⋯ u m - 1 S m - 1 = 0 , ⋮ S 0 + u m - 1 S 1 + ⋯ + u ( m - 1 ) ( m - 1 ) S m - 1 = 0 ,
S 0 = S 1 = ⋯ = S m − 1 = 0 。 S 0 = S 1 = ⋯ = S m - 1 = 0 。
特别在m =2时, 注意到u =1及对任意的w ∈Z n 2 2 n , S (f ) (w ) 都为实数, 定理6中结论为: 布尔函数f (x ) , x ∈Z n 2 2 n 满足k 阶严格雪崩准则的充分必要条件, 是对所有的1≤i 1 <…<i k ≤n , 1≤j ≤n 且{j }⊂{1, 2, …, n }i 1 , …, i k }, s j ∈Z 2 0}和对任意的( a 1 , ⋯ , a k ) ∈ Z k 2 , ∑ w ∈ Z n 2 [ S ( f ) ( w ) S ( f ) ( w i 1 , a 1 , ⋯ , i k , a k ) ] \ 5 ( − 1 ) w j = 0 ( a 1 , ⋯ , a k ) ∈ Ζ 2 k , ∑ w ∈ Ζ 2 n [ S ( f ) ( w ) S ( f ) ( w i 1 , a 1 , ⋯ , i k , a k ) ] \ 5 ( - 1 ) w j = 0 都成立。这是文献[2 ] 中的主要结果。
《3 结语》
3 结语
在剩余类环Z m 上给出了m 值逻辑函数的k 阶严格雪崩准则 (SAC) 的概念, 并借助Chrestenson谱给出了m 值逻辑函数满足k 阶严格雪崩准则的一个充分必要条件, 此外, 依据定理6的结论, 还可以给出满足k 阶严格雪崩准则的m 值逻辑函数的更多的递归构造方法, 用变元个数少的逻辑函数构造变元个数多且满足k 阶严格雪崩准则的逻辑函数, 更好地在密码设计中使用逻辑函数的资源, 因而是有实际意义的。