分组密码的分区线性分析法

分组密码的分区线性分析法 Vol . 18 No . 3 18 卷第 3 期中 国 计 量 学 院 学 报第 J o ur nal of Chi na J iliang U niver sit y Sep . 2007 2007 年 9 月 () 【文章编号】 100421540 20070320181205 分组密码的分区线性分析法 侯 宇 ,闫勇 ,苏开宇 () 中国计量学院 网络中心 ,浙江 杭州 310018 【摘 要】 提出了用于分组密码分析的分区线性分析法. 以 SA F ER + + 为例 ,通过基础模块的密码特性分析 ,建立密码分析的线性逼近式. 该逼近式的特点是把密钥的比特位分区出现在逼近式的任选项中 ,这样不仅 可以攻击密钥的所有比特位 ,而且大大降低了攻击的复杂度 ,并从理论上证明了逼近式的优势与任何子密钥 的最低有效位无关. 迄今为止有关文献都认为相关子密钥最低有效位等于 0 是逼近优势非零的前提条件. 【关键词】 密码分析 ;分区线性分析法 ;线性逼近 ;最低有效位 ;分组密码 【中图分类号】 T P309 . 7【文献标识码】 A Part it ion l inear cryptanal ysis f or bl ock c ipher HO U Yu , YA N Yo ng , SU Kai2yu ( )Newwo r k Cent er , Chi na J ilia ng U niver sit y , Hangzho u 310018 , Chi na Abstract : A cryp tanalysi s met ho d called p a rt i t i on l i ne a r c r y p t an al y s is fo r block cip her s i s p resented in t hi s paper . Wit h t he ca se of SA F ER + + a s an exa mple , t he special linea r app ro xi matio ns were o btained by a naly2 zing t he ba sic mo dules. In t hse s app ro ximatio ns , t he bit s of a ma ster key were divided into several p art s a nd co uld be a r bit rarily selected to at tack SA F ER + + . It i s po ssible t hat all of t he key bit s ca n be deter mined a nd t he at tack co mplexit y i s greatly reduced at t he same time . It i s al so t heo retically p ro ved t hat t he bia s of linear app ro ximatio ns have no relatio n wit h t he lea st significa nt bit of ever y subkey. Thi s i s a new co ncl usio n. Ma ny paper s so f ar have repo rted t hat t he lea st significa nt bit of co r relative subkeys sho uld be 0 fo r t he bia s hol ding. Key words : cr yp ta nalysi s ; p artitio n linea r cr yp ta nalysi s ; linear app ro xi matio n ; t he lea st significant bit ; block cip her [ 1 ,2 ] 线性密码分析是一种常用的已知明文攻线性密码分析的基本思想是寻找给定密码算 击方法 ,由 Mat sui 和 Ya ma gi shi 发明 ,被广泛用 法的有效线性逼近来破译密码系统. 线性逼近仅 21 于分组密码系统的分析. 这种方法可用 2个已知 涉及明文 P 、密文 C 和密钥 K , 且成立的概率 p ? 47 明文破译 8 轮 D ES ,可用 2个已知明文破译 16 1/ 2 , 用| p - 1/ 2| 来刻画线性逼近的有效性 , 称之 轮 D ES. 抗线性分析已成为分组密码设计的重要 为线性逼近的逼近优势. 在实际中对 n 轮迭代密 指标之一. ( ) 码进行线性密码分析时 , 常使用 n - 1轮密码的 【收稿日期】 2007206208 ( ) 【作者简介】 侯 宇1958 ,男 ,浙江温州人 ,教授 ,主要研究方向为信息安全理论与技术研究. 线性逼近; 也就是说 , 假定已知最后一轮子密钥 1 SAFER + + 分组密码K, 构造如下线性逼近 :n [ 3 ] SA F ER + + 的整体结构是 SP 网络 , 分组( ) , e] P[ i, , i] C[ j, , j] GC , K[ e,σ σ d 1 a 1 b n 1 长度为 128 比特 ,密钥长度为 128 或 256 比特. 本 ( )= K[ k, 1 1 , k]c 文采用 128 比特的密钥. ( ) σ A 式 1中 A [ i , j ,, k ] = A [ i ] A [ j ] σ σ[ 4 ] 令密文 X 和子密钥 K 为i [ k ] , A [ i ] 是 A 的第 i 比特;“σ ”是异或运算符. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ( X = X X X X X X X X X X X X X X X X )( ) 式 1的有效性与 G 函数及K 有关. 如果在式n 8 16( ) ?F2 ( ) 1中代入一个不正确的候选者 K, 那么这个等n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ( K= KKKKKKKKKKKKK K K K i i i i i i i i i i i i i i i i i 式的有效性显然就降低了. 因此 , 文献[ 2 ] 给出如 8 16( ) ?F2 ] , k下算法预测 K和 K [ k,c n 1 子密钥“加”( )i ( 第 1 步 对 Kn 的每一个候选者 K n i = 1 ,8 16 8 16 σ ( ( )σ: ) ( ) X ?XF?FK2 2 K i i ) () , 设 T是使得式1左边等于 0 的明文个数.i 2 , 当 i 为奇数时 , 有 T= max{ T} , T= min{ T} . 1第 2 步1 2 2 3 3 4 max i i ?1 min i i ?1 σ ( ) ( X = X K, X + σ K, X + i i Ki , KK i- T- T N / 2| > | 如果|max min N / 2| , 那么将T所max 4 5 5 15 15 16 16 σ σ , X σ , X K, KK) K, X + i i ii 对应的密钥候选者作为 K, 并猜定 K[ k,n 1 , k]c 当 i 为偶数时 , 有 1 1 2 2 3 3 4 ( ) ( K[ k, , k] = 1 当 p < 1/= 0 当 p > 1/ 2 时或1 c σ ( ) ( X= X+ , X σ K, X σ K, XKi i i K i15 15 16 16 5 5 4 ) 2 时. 如果| T- N / 2 | < | T- N / 2 | , 那么将max min + , X + , X K, X +σ i K, K) K i i iT所对应的密钥候选者作为 K, 并猜定 K [ k,min n 1 这里“ ”是异或运算“; + ”是模 256 加运算. σ ( ) ( ] = 1 当 p > 1/ 2 时或 K[ k,, k] = 0 当, kc 1 c 两个 S 盒 : 88 45 ) p < 1/ 2 时. 其中 N 是给定的随机明文的个数.( ) ( ) Y ?SY= Y mo d257 , 约定 S 128= 0 S : F?F1 1 1 2 2 88 ( ) 逼近式 1通常只能分析密钥的若干比特位 ,S : F( ) ( ) ( ) 2 Y ?SY= lo gY, 约定 S 0= 128?F2 45 2 2 2 而不能破译密钥的所有比特位; 而且密码分析的 混淆层 : 8 16816 复杂度随子密钥 K所取比特位数的增加而呈几n ( ) ( ) ( ) S : F ? FX ?S2 2 X 1 2 3 4 何增长. 本文将以 SA F ER + + 为例寻找如下形式( ) ( ( ) ( ) ( ) ( ) S X= SX, SX, SX, SX,1 2 2 1 5 15 16 的线性逼近式 :( ) ( ) ( ) )SX,, S X, S X1 2 1 ) ( C[ j, α ][ eα , , k, j ] G P , K [ kα ,σ 1 b 扩散层 :1 l 1 8 16 8 16( ) ) ( , eα ] σ〈0 , G P , K[ kβ , ( ) , kβ ][ eβ ,, eβ ] , ) ( ) ( 2 2 X ?P X= P2 PP 1 P : F?F2 P X1 p 1 m 1 q ( )2 ( ) GP , K[ kγ , , kγ ][ eγ , γ ] , 〉= 0其中, e1 n 1 r 89 6 3 16 8 16( ) ( ) ( ) ( : F P其中括号“〈〉”内是任选项; { kα ,, kα } , { kβ , X ?PX= XXX, 1 2 ? F2 1 1 l 1 16 1 14 11 8 5 2 15 12 13 10 7 4 ) XXXXXXXXXXXXXkβ } , { kγ , kγ } , 是密钥比特位的子集 , 而它1 m n 8 16 8 16 ) ( ) ( ) ( ( P: F?们的并集等于密钥比特位的全集. 利用上式我们FX ?P2 X = P H T2 2 2 1 2 3 4 5 6 7 8 9 10可以将密钥按比特位划分子集进行攻击 , 这样既 ( ) ( ) ( XXXX, P H T XXXX, P H T XX 降低了攻击的复杂度 , 又能分析密钥的所有比特 11 12 13 14 15 16 ) ( ) )XX, P H T XXXX 位. 由此 , 本文称之为分区线性分析法. 84 8 4( P H T : F ) ?( F ) X Y ZW ?P H T ( X Y ZW) 2 2 在线性密码分析中有一个非常有用的堆积引 ( = 2 X + Y + Z + W , X + 2 Y + Z + W , X + Y + 2 Z () 理 pili ng2up le mma: )+ W , X + Y + Z + W ( ) 堆积引理 :设 X 1 ?i ?n是独立的随机变 i 子密钥的生成算法比较冗长 , 详见文献[ 3 ] , 此处 ( ) ( ) 量 , p X = 0= p, p X = 1= 1 - p, 则i i i i 不赘述. n n 轮 SA F ER + + 加密算法为n - 1 ) ( )( p Xσ Xσ σ X = 0= 1/ 2 + 2 p- 1/ 21 2 n i ?σ( ) σσσσσ σ i = 1 E X=PPS PPS SKKK K K KK2 n - 12 n + 1 2 n 4 3 2 1 ( )3 ( )X 第 3 期侯 宇 ,等 :分组密码的分区线性分析法183 10 11 12 16 1 3 8 Y[ 0 ] Y[ 0 ] Y[ 0 ] Y[ 0 ] , Y [ 0 ] Y [ 0 ] Y [ 0 ] 2 基础模块的密码特性10 12 2 4 7 11 13 Y[ 0 ] Y[ 0 ] , Y [ 0 ] Y [ 0 ] Y [ 0 ] Y [ 0 ] Y [ 0 ] [ 5]15 - 42 . 1 模 256 加运算 ) ( )[ 0 ]} = 2 Y11 2 3 9 11 14 15 ( 设字节 A 的比特位为 A = a,7 ( bia s Z [ 1 ] Z [ 1 ] Z [ 0 ] Z [ 1 ] Z [ 1 ] Z [ 1 ] ) , a, a, 对1 0 2 3 11 14 15 σ A r b{ 0 , Z[ 0 ] , Z[ 0 ] , Z[ 0 ] , Z[ 0 ] , Z[ 0 ]} 于模 256 加运算 Z = X + Y mo d 256 , 有如下的线2 3 6 8 2 3 = Y [ 1 ] Y [ 1 ] Y [ 1 ] Y [ 1 ] σ Ar b{ 0 , Y [ 0 ] , Y [ 0 ] , 性逼近及其优势 :6 8 11 14 4 7 - 1[ 0 ] , Y [ 0 ]} σ O ne} Y [ 0 ] Y [ 0 ] , Y [ 0 ] Y [ 0 ] Y ( bia s Z[ 0 ] = X [ 0 ] σ Y [ 0 ] = 2 10 1 9 14 16 5 11 Y [ 0 ] , Y [ 0 ] Y [ 0 ] Y [ 0 ] Y [ 0 ] , Y [ 0 ] Y [ 0 ] ( bia s Z[ 1 ] = X [ 1 ] Y [ 1 ] σ〈0 , X [ 0 ] , Y [ 0 ] ,σ 13 14 1 5 11 12 15 - 2)Y [ 0 ] Y [ 0 ] , Y [ 0 ] Y [ 0 ] Y [ 0 ] Y [ 0 ] Y [ 0 ]} ) ( ) 4 X [ 0 ] Y [ 0 ]〉= 2 σ - 5 ( )12 = 2 ( ) 这里用 bia s L 表示线性逼近式 L 的逼近优 { . . } 前的关键词称之为“异以上诸式中集合势. 为了书写简洁 , 在不引起歧义的前提下 , 将略 或操作符”, 其中 A r b{}表示对集合中的任意多个 去逼近式中的异或运算符“σ ”. 元素做异或运算 ; O dd { } 表示对集合中任意奇数 当模 256 加运算中的一个变量为常数时 , 比 个元素做异或运算 ; O ne { } 表示任选集合中的一 3 9 14 如 Y 等于常数 K , 则有 个元素进行异或运算. 例如 Y[ 1 ] Y[ 1 ] Y [ 1 ] σ 3 9 9 14 - 1( ) A r b{ 0 , Y[ 0 ] Y [ 0 ] , Y[ 0 ] Y[ 0 ]} 等价于以下任 bia s Z[ 0 ] = X [ 0 ]= 2 ( )5 - 1 一式 : ( ( ) ) ( ) bia s Z[ 1 ] = X [ 0 ] ?K[ 0 ]X [ 1 ]= 2 6 [ 5 ] 2 . 2 S和 S的密码特性1 2 3 9 14 Y [ 1 ] Y [ 1 ] Y [ 1 ] ( ) ( ) 对于 Y = SX 和 Z = S X, 有如下的线性 1 2 3 9 14 3 9 逼近及其逼近优势 : Y [ 1 ] Y [ 1 ] Y [ 1 ] Y [ 0 ] Y [ 0 ] - 4 - 53 9 14 9 14 ( ( bias Y [ 1 ] = X [ 0 ] = 2 , bias Y [ 1 ] = X [ 1 ] = 2 Y [ 1 ] Y [ 1 ] Y [ 1 ] Y [ 0 ] Y [ 0 ] 3 9 14 3 14 - 4 - 5 ( )( ( Y [ 1 ] Y [ 1 ] Y [ 1 ] Y [ 0 ] Y [ 0 ] 13 bias Z[ 0 ] = X [ 1 ] = 2 , bias Z[ 1 ] = X [ 1 ] = 2 , 3 9 14 3 9 14 - 5而 Y [ 1 ] Y [ 1 ] Y [ 1 ] O dd{ Y [ 0 ] , Y [ 0 ] , Y σ ( ) bias Z[ 0 ] Z[ 1 ] = X [1 ]= 2 ( )7 [ 0 ]} 等价于以下任一式 : 2 . 3 P 变换的密码特性3 9 14 3 Y [ 1 ] Y [ 1 ] Y [ 1 ] Y [ 0 ] 根据模 256 加运算的密码特性以及字节移位变 3 9 14 9 Y [ 1 ] Y [ 1 ] Y [ 1 ] Y [ 0 ] ( ) 换的特点 , Z = PY有如下的线性逼近及其优势 : 3 9 14 14 2 3 13 14 16 Y [ 1 ] Y [ 1 ] Y [ 1 ] Y [ 0 ] ( ) bia s Z[ 0 ] Z[ 0 ] Z[ 0 ] Z[ 0 ] Z[ 0 ]= 3 9 14 3 9 14 ( )3 11 14 - 1Y [ 1 ] Y [ 1 ] Y [ 1 ] Y [ 0 ] Y [ 0 ] Y [ 0 ] 14 ) Y[ 0 ] Y [ 0 ] Y[ 0 ]= 2 ( )8 3 11 14 3 2 . 4 单轮加密特性( bia s Z[ 1 ] Z[ 1 ] Z[ 1 ] σ A r b { 0 , Z[ 0 ] , 11 14 2 3 5 6 7 σσ( ) 设 C =PS W 为 SA F ER + + 的一轮K K 2 r + 1 2 r Z[ 0 ] , Z[ 0 ]} = Y[ 0 ] Y[ 0 ] Y[ 1 ] Y [ 1 ] Y[ 0 ] 8 13 5 8 13 σ( ) σ( ( ) ) 加密 , 而且 C =Z, Z = P Y , Y =X , )KK Y[ 1 ] Y[ 1 ] σ A r b { 0 , Y[ 0 ] , Y[ 0 ] , Y[ 0 ]} 2 r + 1 24 - 4 ( ) X = S W , 利用上述基础模块密码特性和堆积引( )= 2 9 2 3 5 6 7 8 13 ( 理 , 得到以下逼近式及其优势 :bia s Z[ 1 ] Z[ 1 ] Z[ 0 ] Z[ 1 ] Z[ 1 ] Z[ 1 ] Z[ 0 ] 2 3 2 6 2 7 2 3 13 14 16 σ Ar b{ 0 , Z[ 0 ] Z[ 0 ] , Z[ 0 ] Z[ 0 ] , Z[ 0 ] Z[ 0 ]} = ( ) bia s C[ 0 ] C[ 0 ] C[ 0 ] C[ 0 ] C[ 0 ]= 3 9 14 3 9 9 3 11 14 - 10Y[ 1 ] Y [ 1 ] Y[ 1 ] σ A r b{ 0 , Y [ 0 ] Y[ 0 ] , Y[ 0 ] ) W [ 1 ] W [ 1 ] W [ 1 ]= 2 ( )15 14 2 11 15 5 11 3 11 14 2 3 Y[ 0 ]} σ O ne{ Y[ 0 ] Y[ 0 ] Y[ 0 ] , Y[ 0 ] Y[ 0 ] ( bia s C[ 1 ] C[ 1 ] C[ 1 ] = W [ 1 ] W [ 1 ] 12 15 6 10 11 12 16 5 6 7 8 13 - 27) Y[ 0 ] Y [ 0 ] , Y[ 0 ] Y [ 0 ] Y[ 0 ] Y[ 0 ] Y[ 0 ] , W [ 0 ] W [ 1 ] W [ 1 ] W [ 1 ] W [ 0 ]= 2 ( )16 1 3 8 10 12 2 4 2 3 5 6 7 8 ( Y[ 0 ] Y[ 0 ] Y[ 0 ] Y[ 0 ] Y[ 0 ] , Y[ 0 ] Y[ 0 ] bia s C[ 1 ] C[ 1 ] C[ 0 ] C[ 1 ] C[ 1 ] C[ 1 ] 7 11 13 15 - 413 2 3 9 11 14 ) Y[ 0 ] Y [ 0 ] Y[ 0 ] Y[ 0 ]} = 2 C[ 0 ] = W [ 1 ] W [ 1 ] W [ 0 ] W [ 1 ] W [ 1 ] ( )10 2 3 5 6 7 8 13 15 - 24( ) bia s Z[ 1 ] Z[ 1 ] Z[ 0 ] Z[ 1 ] Z[ 1 ] Z[ 1 ] Z[ 0 ] W [ 1 ]= 2 ( )17 2 3 6 7 3 9 2 3 5 6 7 8 13 σ Odd{ Z[ 0 ] , Z[ 0 ] , Z[ 0 ] , Z[ 0 ]} = Y [ 1 ] Y [ 1 ] ( bia s C[ 1 ] C[ 1 ] C[ 0 ] C[ 1 ] C[ 1 ] C[ 1 ] C[ 0 ] 14 3 9 14 2 3 9 14 2 11 15 Y [ 1 ] Odd{ Y [ 0 ] , Y [ 0 ] , Y [ 0 ]} One{ Y [ 0 ] σ σ = X[ 1 ] X[ 1 ] X [ 1 ] σ One{ X[ 0 ] X[ 0 ] X[ 0 ] , 11 15 5 11 12 15 6 5 11 12 15 6 10 11 Y[ 0 ] Y[ 0 ] , Y[ 0 ] Y[ 0 ] Y[ 0 ] Y[ 0 ] , Y[ 0 ] X[ 0 ] X[ 0 ] X[ 0 ] X[ 0 ] , X[ 0 ] X[ 0 ] X[ 0 ] 12 16 1 3 8 10 12 ( ) X[ 0 ] X[ 0 ] , X[ 0 ] X[ 0 ] X[ 0 ] X[ 0 ] X[ 0 ] , 变换特性 10得到P 2 4 7 11 13 15 - 42 2 2 3 3 ) ( ) ( X[ 0 ] X[ 0 ] X[ 0 ] X[ 0 ] X[ 0 ] X[ 0 ]} = 2 bia s Z[ 0 ] ?K[ 0 ]Z[ 1 ] Z[ 0 ] ?K2 2 r + 1 r + 1 6 3 5 6 6 ( )18 ( ) ) [ 1 ] Z[ 0 ]Z[ 1 ] Z[ 0 ] ] Z[ 0 ] ? K[ 0 ]2 r + 1 2 3 9 11 14 15 7 7 7 8 13 2 ( bia s C[ 1 ] C[ 1 ] C[ 0 ] C[ 1 ] C[ 1 ] C[ 1 ] ( ) Z[ 0 ] ?K[ 0 ]Z[ 1 ] Z[ 1 ] Z[ 0 ] = Y[ 0 ]2 r + 1 2 3 6 8 11 14 3 9 11 14 15 3 = X[ 1 ] X[ 1 ] X[ 1 ] X[ 1 ] σ One{ X[ 0 ] X[ 0 ] , Y[ 1 ] Y[ 1 ] Y [ 0 ] Y [ 1 ] Y[ 0 ] A r b{ 0 , Y[ 0 ] σ 4 7 10 1 9 14 16 9 9 14 - 4X[ 0 ] X[ 0 ] X[ 0 ] , X[ 0 ] X[ 0 ] X[ 0 ] X[ 0 ] , ) ( )Y[ 0 ] , Y[ 0 ] Y[ 0 ]} = 2 25 5 11 13 14 1 5 11 2 3 6 7 X[ 0 ] X[ 0 ] X[ 0 ] X[ 0 ] , X[ 0 ] X[ 0 ] X[ 0 ] 当2 2 2 2 K[ 0 ] K[ 0 ] K[ 0 ] K[ 0 ] = 1 时 , 则r + 1 r + 1 r + 1 r + 1 12 15 - 5由 ) ( )X[ 0 ] X[ 0 ]} = 2 ( ) 19 P 变换特性 11得到 2 2 2 3 3 ( ) ( 以上各个逼近式的优势与任何子密钥的最低2 2 bia s Z[ 0 ] ?K[ 0 ]Z[ 1 ] Z[ 0 ] ?Kr + 1 r + 16 j 3 5 6 6 ( ) [ 1 ] Z有效位 Ki [ 0 ]无关 ! 这是本文研究的重要结论之Z[ 1 ] Z[ 0 ] Z[ 0 ] ? K[ 0 ])2 r [ 0 ] + 1 7 7 7 8 13 2 ( ) 一 , 现证明如下.Z[ 0 ] ?K[ 0 ]Z[ 1 ] Z[ 1 ] Z[ 0 ] = Y[ 0 ]2 r + 1 3 9 11 14 15 3 ( ) ( ) ( ) 由密码特性 578三式及堆积引理可以 Y[ 1 ] Y[ 1 ] Y[ 0 ] Y[ 1 ] Y[ 0 ] σ O dd{ Y[ 0 ] ? 9 14 - 4( ) ( ) ) ( )直接证明式 15 成立. 对于式 16 , 由密码特性 Y[ 0 ] , Y[ 0 ]} = 2 26 ( ) ( ) 6, 得到 利用密码特性 6和操作符 A r b{ } 、O dd{ } 的 3 11 14 3 3 - 1 ( ( bia s C[ 1 ] C[ 1 ] C[ 1 ] = Z[ 0 ] ?K2 r + 1特性 , 以下逼近式的优势为 2 2 3 9 11 14 15 3 11 11 11 14 Y[ 0 ] Y[ 1 ] Y[ 1 ] Y[ 0 ] Y[ 1 ] Y[ 0 ] σ ) ( ) ( [ 0 ]Z[ 1 ] Z[ 0 ] ?K2 r [ 0 ]Z[ 1 ] Z[ 0 ] ?+ 1 3 9 9 14 2 14 14 - 1 ) ) A r b{ 0 , Y[ 0 ] Y[ 0 ] , Y[ 0 ] Y[ 0 ]} = X[ 0 ] [ 0 ]Z [ 1 ]= 2 ( ) 20 K2 r + 1 9 11 14 3 9 9 ( ) X[ 1 ] X[ 0 ] X[ 1 ] ( ) X[ 1 ] X[ 0 ] ? K[ 0 ]2 r 由 P 变换的密码特性 9以及操作符 A r b{ }15 3 9 9 14 3 11 14 [ 0 ] , X [ 0 ] X [ 0 ]} X [ 0 ] A r b{ 0 , X [ 0 ] X σ 2 2 r 2 r 的特性 , 不管 K[ 0 ] 、K[ 0 ] 、K[ 0 ] 是何r + 1 + 1 + 1 2 3 9 11 14 15 X[ 0 ] X[ 1 ] X[ 1 ] X[ 0 ] X[ 1 ] X[ 0 ] 值 , 均有 9 3 3 3 11 ( ( K[ 0 ] = 0 ) ( a s bia s Z[ 0 ] ?K[ 0 ]Z[ 1 ] Z[ 0 ] ?2 r 2 r + 1 = 11 14 14 14 2 3 9 11 14 15 3 11 ) ( ) ) [ 0 ]Z [ 1 ] Z [ 0 ] ?K[ 0 ]Z [ 1 ]=X [ 0 ] X [ 1 ] X [ 1 ] X [ 0 ] X [1 ] X [0 ] X [0 ] K2 r + 1 2 r + 1 2 3 5 6 7 8 13 9 Y[ 0 ] Y[ 0 ] Y[ 1 ] Y[ 1 ] Y[ 0 ] Y[ 1 ] Y[ 1 ] σ a s K2 [ 0 ] = 1r 5 8 13 - 4) ( )A r b{ 0 , Y[ 0 ] , Y[ 0 ] , Y[ 0 ]} = 2 21 ( )27 - 1 2 3 9 11 14 15 同理 , 以下逼近式成立且优势为 2 :Y [ 0 ] Y[ 1 ] Y[ 1 ] Y [ 0 ] Y[ 1 ] Y[ 0 ] σ 2 3 5 6 7 8 13 3 9 14 2 3 Y[ 0 ] Y[ 0 ] Y[ 1 ] Y[ 1 ] Y[ 0 ] Y [ 1 ] Y[ 1 ] O dd { Y[ 0 ] , Y[ 0 ] , Y[ 0 ]} = X[ 0 ] X[ 1 ] 5 8 13 2 3 9 9 9 11 14 15 ( ) σ A r b{ 0 , Y[ 0 ] , Y[ 0 ] , Y[ 0 ]} = X[ 0 ] X[ 0 ] X[ 0 ] ?K2 r [ 0 ]X[ 1 ] X[ 0 ] X[ 1 ] X[ 0 ] σ5 5 5 6 7 8 3 9 14 ( ) ( X[ 0 ] ?K2 [ 0 ]X[ 1 ] X[ 1 ] X[ 0 ] X[ 0 ] ?O dd{ X[ 0 ] , X[ 0 ] , X[ 0 ]} r 8 13 13 13 8 2 3 9 11 14 15 3 ) ( ) 2 r [ 0 ]X [ 1 ] X [ 0 ] ?K2 r [ 0 ]X [ 1 ] σ A r bKX [ 0 ] X [ 1 ] X [ 1 ] X [ 0 ] X [1 ] X [0 ] X [0 ] 5 8 13 2 3 5 9 { 0 , X[ 0 ] , X[ 0 ] , X[ 0 ]} = X[ 0 ] X[ 0 ] X[ 1 ] a s K2 r [ 0 ] = 0 = 6 7 8 13 2 3 9 11 14 15 X[ 1 ] X[ 0 ] X[ 1 ] X[ 1 ] ( )22 X[ 0 ] X[ 1 ] X[ 1 ] X[ 0 ] X[ 1 ] X[ 0 ] 9 ( ) 利用 S 盒的密码特性 7, 有a s [ 0 ] = 1 K2 2 3 5 6 7 8 ( bia s X[ 0 ] X[ 0 ] X[ 1 ] X[ 1 ] X[ 0 ] X[ 1 ] ( )28 13 2 3 5 6 7 8 X[ 1 ] = W [ 1 ] W [ 1 ] W [ 0 ] W [ 1 ] W [ 1 ] W [ 1 ] ( ) 根据 S 盒的密码特性 7, 我们有13 - 242 3 9 11 14 15 ( )[ 0 ] = 2 W 23 ( bia s X[ 0 ] X[ 1 ] X[ 1 ] X[ 0 ] X[ 1 ] X[ 0 ] σ 3 2 3 9 11 14 ( ) ( ) ( ) 综合式 20—23并由堆积引理 , 式 16得证.( ) Ar b 0 , X[ 0 ]= W [ 1 ] W [ 1 ] W [ 0 ] W [ 1 ] W [ 1 ] 15 - 21 ( ) 类似的 , 对于式 17, 有( )) 29 [ 1 ]= 2 W 2 3 5 6 7 8 13 ( bia s C[ 1 ] C[ 1 ] C[ 0 ] C[ 1 ] C[ 1 ] C[ 1 ] C[ 0 ] ( ) ( ) ( ) 综合式 24—29并由堆积引理 , 式 17成立.2 2 2 3 3 ( ) ( ) = Z[ 0 ] ?K[ 0 ]Z[ 1 ] Z[ 0 ] ?K[ 0 ]2 2 r + 1 r + 1 ( ) ( ) 类似地 , 可证明式 18 19 成立 , 并且与子密3 5 6 6 6 7 ( ) ( Z[ 1 ] Z[ 0 ] Z[ 0 ] ?K[ 0 ]Z[ 1 ] Z[ 0 ] ? 2 r + 1 钥最低有效位无关.7 8 13 - 1 7 ) [ 0 ]Z [ 1 ] Z [ 1 ] Z ( ) [ 0 ] = 2 24 K2 r + 1 在[ 4 ] [ 6 ]等文献中 , 由于未注意到类似于式2 3 6 7 当( ) ( ) K[ 0 ] K[ 0 ] K[ 0 ] K[ 0 ] = 0 时 , 由2 2 2 2 9—12的密码特性 , 构造线性逼近式及其优势r + 1 r + 1 r + 1 r + 1 第 3 期侯 宇 ,等 :分组密码的分区线性分析法185 时附加了相关子密钥最低有效位必须等于 0 的要此 , 攻击 3 轮 SA F ER + + 所有 16 字节密钥的复 6 ?8 - 1 2 ?8 - 2 3 ?8 - 1 2 ?8 - 2 ( 求 , 实际上是不必要的. 杂度 为 2+ 2+ 2+ 2+ 2 ?8 - 2 79 ) 2?2. 攻击 4 轮 SA F ER + + 所有 16 字节3 分区线性分析法6 ?8 - 1 3 ?8 - 1 3 ?8 - 3 2 ?8 - 2( 密钥的复杂度为 2+ 2+ 2+ 2 2 ?8 - 1 129 () () 利用式15—19,建立分区线性分析法攻击 ) + 2?2. 复杂度都小于直接攻击 7 个字 12 ( 节密钥的复杂度. 完整的 3 轮和 4 轮 SA F ER + + . 设 P = PP 2 16 8 1616 8 16 1) ( ) ) ( ) ( CC?FP?F2 和 C = C2 4 结论 是系统的明文和密文 , 分析 3 轮 SA F ER + + 的线 性逼近式为 :本文通过对 SA F ER + + 的基础模块密码特2 3 13 14 16 3 ( C[ 0 ] C[ 0 ] C[ 0 ] C[ 0 ] C[ 0 ] = S P+性的分析 ,建立了分区密码线性分析的逼近式. 该 2 3 9 9 11 11 K) ( ) ( ) 逼近式的特点是把密钥的比特位分区块出现在逼 [ 1 ] σ S Pσ K[ 1 ] σ SP + K[ 1 ]1 1 1 2 1 2 2 11 11 ( ) 近式的任选项中 ,然后进行分区攻击. 这样不仅可 σ O ne{ S P+) ( KSP+ K 2 [ 0 ] σ 1 [ 0 ] σ 21 15 11 15 5 5 以分析密钥的所有比特位 ,而且大大降低了分析 ( ) ( ) ( SP+ [ 0 ] , Sσ [ 0 ] σP+2 K1 1 PK1 S 2 12 12 15 15 11 的复杂度. 文章从理论上证明了逼近式及其优势 )) ( ) ( + K K[ 0 ] SP K[ 0 ] SPσ σ σ 1 1 1 1 2 6 10 10 6 与任何子密钥的最低有效位无关 ,纠正了有关文 ( ) ( [ 0 ] , S P+ K[ 0 ] P+ KσS) 2 [ 0 ] σ S21 2 1 11 12 12 16 11 献要求子密钥最低有效位等于 0 的错误结论 ,使 ( ) ( ) ( P+ K[ 0 ] σ SPσ K[ 0 ] σ S P σ1 1 1 1 1 1 3 3 16 得密码分析不受密钥最低有效位的取值限制 ,更 ) ( ) ( ) [ 0 ] , SP σ K[ 0 ] σ SP + K[ 0 ] σK1 1 1 2 1 79 8 10 10 12 8 具通用性. 攻击带输出变换的 3 轮加密需要 2 个( ) ( ) [ 0 ] σ ( SPσ K[ 0 ] σP+ KPS S 1 1 21 147 24 79 12 2 2 4 4 ( ) 已知明文 ,复杂度小于 2+ 2?2. 攻击带输) ) ( ) ( K[ 0 ] , SP + K[ 0 ] S P σσ σK1 [ 0 ]1 2 1 1 129 7 7 11 11 13 出变换的 4 轮加密需要 2 个已知明文 , 复杂度( ) ) ( ( SP+ K[ 0 ] Sσ σ P+ K[ 0 ] σ S2 1 2 1 P1 47 24 129 13 15 15 () 小于 2+ 2?2.( )K) ( ) 30 [ 0 ] S P + K[ 0 ]}σσ 1 2 1 - 38 对于其它分组密码系统 ,只要其基础模块具 其优势为 2 . 为了使攻击有高成功率 , 根据文献 - 38 - 2 79 有本文所述的密钥分区任选特性 ,都可以利用本 ( ) [ 2 ]需要 N = 8 ?2 = 2个已知明文. 4 轮 文方法进行密码攻击. SA F ER + + 的线性逼近式为 : 2 3 13 14 16 2 ( C[ 0 ] C[ 0 ] C[ 0 ] C[ 0 ] C[ 0 ] = S P+2 【参 考 文 献】2 3 3 6 6 ) K) ( ) ( [ 1 ] σ S P + K[ 1 ] σ SP +K1 [ 1 ] +1 2 1 2 [ 1 ] MA TSU I M , YA MA GIS H I A . A new met ho d fo r kno wn 8 8 11 11 ( SPσ [ 1 ] σ O ne { SKP+ K1 ) 2 ( ) [ 0 ] σ S2 1 1 plai nt ext at t ack o n F EAL cip her [ A ] ?A dva nce s i n Cr yp tol2 14 4 4 7 7 14 o gy , Preceedi ngs Eurocr yp t ’92 [ C ] . L N CS 658 , R A ( ) ( ) ( ) P+ [ 0 ] , S Pσ K[ 0 ] σ SP +KK1 1 1 2 1 Ruepp el , Ed , Sp ri nger2Verlag ,1993 : 81291 . 10 10 1 1 ( [ 0 ] σ SP+) ( ) KPK2 [ 0 ] , S σ [ 0 ] σ S11 1 1 MA TSU I M . Li nea r cr yp t a nal ysi s met ho d fo r D ES cip her [ 2 ] 9 9 14 16 14 ( ) ) ( ( [ 0 ] σ S PK1 [ 0 ] σ σSP+K1 Pσ1 [ A ] ?Adva nce s i n Cr yp tolo gy , Preceedi ngs Eurocr yp t ’93 2 16 5 5 11 11 [ C ] . L N CS 658 , R A Rueppel , Ed , Sp ri nger2Verlag , K) ( ) ( ) [ 0 ] , SP σ K[ 0 ] σ S P + K[ 0 ] σ1 1 1 2 1 1994 :3862397 . 14 14 13 1 13 ) ( ) ( ( [ 0 ] σ SP+ K[ 0 ] , SσSPσKP1 2 1 1 1 MA SSE Y J L , KH A C HA TR IA N G H , KU R E GIA N M . [ 3 ] 1 5 5 11 11 ) ) ( ) ( The SA F ER + + Block Encr yp tio n Al go rit hm [ EB/ OL ] . K[ 0 ] S P K[ 0 ] SP +σ σ σ K1 [ 0 ]1 1 1 2 12 15 15 12 ) ( ) ( 2000211213 ) [ 2007205230 ] . Cyli n k Co rpo ratio n , availa ble ( ) ( SPKP+ K[ 0 ]} 31 σ σ1 1 1 [ 0 ] σ S2 - 63 - 63 - 2 129o n ht tp :/ / www . cr yp to ne ssie . o r g. ( ) 其优势为 2 , 攻击需要 N = 8 ?2 = 2[ 4 ] 吴文玲 , 马恒太 , 唐柳英 , 等. 5 轮 SA F ER + + 的非线性密 个已知明文.( ) 码分析[J ] . 电子学报 ,2003 ,31 7:9612965 . j [ 5 ] 侯 宇. SA F ER264 的弱密钥 [ J ] . 中国计量学院学报 , 在以上两式的右边 , 16 个字节的主密钥K1 ( ) 2007 ,17 1:2007 :54258 . 被分属于不同的选择项. 利用 O ne{ } 的特性 , 我们N A KA HA RA J , PR EN E EL B , V A ND EWALL E J . Li nea r [ 6 ] 依次选用集合中的一个选项作为逼近式 , 用前文 Cr yp t a nal ysi s of Reduced2Ro und SA F ER + + [ EB/ OL ] . ( ) 2001208231 [ 2007206201 ] . ht tp : / / www . cr yp to ne ssie . 的方法进行攻击. 这样 , 每次攻击所涉及的最多只 o r g . 有 6 个字节的密钥 , 大大降低了攻击的复杂度. 由