第 3 章　相关分析方 法 本章内容提要 相关分析从对基于LFSR 的序列密码的分析起步,最早是由Blaser等[1]提出的,但真 正有价值的工作是由Siegenthaler[2]提出的非线性组合生成器的分别征服相关分析,其基本 思想是利用组合函数的输出与输入分量或某些输入分量子集之和的相关性,穷举搜索某个 特定LFSR 的初始状态或者某几个LFSR 的初始状态,而各个LFSR 的初始状态就是非线 性组合生成器的子密钥,这就是最早的相关分析。分别征服(divideandconquer)来源于一 种图论算法,体现了“分而治之”的思想(因此也译为分治),意为将一个待求解的问题分成许 多子问题,然后对每个子问题求解,最后再综合求解。随后,Meier等[3]给出了加速上述分 别征服相关分析的两个算法,即算法 A 和算法B,称为快速相关分析,其出发点是上述相关 分析的复杂度与LFSR 的长度成指数关系,因此,这种相关分析只适用于长度较短的 LFSR 。针对此问题,他们对LFSR 的抽头数较少的非线性组合序列密码提出了一种使用 概率迭代译码算法的快速相关分析方法,不需要搜索整个LFSR 的所有可能初始状态,就能 找出正确的初始状态,这个方法是相关分析发展的里程碑。之后,又陆续出现了一系列对相 关分析核心思想的改进方法。例如,Zhang等[4]提出了多步快速相关分析方法,他们指出 , 以前的工作主要是把LFSR 的初始状态看成一个整体,并且仅仅使用一种校验等式来进行 译码,但实际上可以充分利用不同种类的校验等式,在不增加渐近复杂度的情况下,逐个部 分地恢复初始状态,这种方法对反馈多项式的汉明重量没有要求和限制;Le 等[5]基于 Anderson[6]对于采用满足某些密码学性质的滤波生成器的条件相关分析思想提出了条件 相关分析的框架,其核心思想是考察增量函数在特定输出情况下输入变量的相关性。条件 相关分析又被扩展到两种类型的分析,即混成相关攻击(hybirdcorelationatack)和集中 攻击(concentrationatack)[7],这两种分析的目标都是通过条件相关分析和快速相关分析 恢复LFSR 未知的初始状态。Lu等[8]把条件相关分析扩展为在猜测部分未知输入的情况 下考察向量函数输出的相关性,这里假定部分输入信息服从随机均匀分布,特别地,这个方 法在分析蓝牙二级E0算法时被证明非常有效。在此基础上,Zhang等人[9]发展并提出了基 于条件掩码的条件相关分析方法。 本章主要介绍分别征服相关分析、快速相关分析、多步快速相关分析、条件相关分析和 熵漏分析5种方法。 本章重点 ● 分别征服相关分析方法的基本原理。 ● 快速相关分析方法的适用范围和基本原理。 ● 多步快速相关分析方法的基本思想。 ● 条件相关分析方法的基本思想。 ● 熵漏分析方法的基本思想。 ● 相关免疫阶的发展背景、基本概念和特征。 第 3 章　相关分析方法 47 3. 1. 1 1.3 分别征服相关分析方法 本节主要介绍分别征服相关分析方法的统计模型、基本原理、应用实例和应对措施。 二元加法非线性组合序列密码模型 二元非线性组合生成器由 s 个线性反馈移位寄存器(LFSR)和一个非线性组合函数组 成。 s 个LFSR 为非线性组合函数提供随机性较好的序列,通常为最大长度序列,即m-序 列;非线性组合函数主要用来提高密钥序列的线性复杂度。所谓二元加法非线性组合序列 密码是指将二元非线性组合生成器的输出序列作为密钥流或密钥序列,将密钥序列与明文 序列进行逐位模2加后所得的序列作为密文序列的密码,见图3.1。 1. 图3.1 二元加法非线性组合序列密码 1. 一个密码的密钥量是一个相对的概念,它依赖于密码设计者假定密码分析者知道该密 码的参数的多少。对图3.1所示的密码而言,一般假定密码分析者仅知道如下参数: 1. (1)足够长的密文序列(使用唯密文攻击方法)。 (2)非线性组合函数f(x)。 (3)所有LFSR 的级数ri(1≤i≤s)。 (4)语言编码及语言统计特性。 假定密码分析者不知道所有LFSR 的初始状态及其联结多项式。如果以Ri 记F2[x] 中所有次数为ri 的本原多项式,那么对密码分析者来说,第 i 个LFSR 的未知参数有 Ri(2r1)个(要去除每个LFSR 的全零初始状态,因为全零初始状态产生全零序列), 这部 i s 分密钥称为LFSRi 的子密钥。因此,1.Ri(2ri-1)。如果 图3.1所示的密码的密钥量为Π i= 1 s 使用穷举搜索密钥攻击方法,那么在最坏的情况下所有ΠRi(2ri-1)个密钥都需要尝试 一 i=1 次。如果r足够大,那么穷举搜索方法所需计算是无法实现的。 这里最关(i) 键的问题是理论上需要多长的密文才能破译这个密码。 2. 1. 分别征服相关分析方法的基本原理 分别征服相关分析是一种唯密文攻击方法。因为Cn 与Zn 和Yn 有关,而Zn 又与Xin 序列密码分析方法 有关,因而Cn 间接地与Xi 有关。这表明在一般情况下Cn 中必定包含Xi 的信息,从而含 有LFSRi 的子密钥的信息。现在有两个问题:一个是密文C1C2…CN 中含LFSRi 的子密 钥的信息量由什么参数确定,另一个是如何提取或间接地利用这些信息。 分别征服相关分析方法是利用某些输入xi 与输出 z 之间的相关性逐步确定每个 LFSR的子密钥。为此,首先需要根据最大长度序列的统计特性建立一个统计模型,见图3.(i) 2。设函数 f 的输入xi (是由一些相互独立且服从同一分布的随机变量Xi nn 1. n 1≤i≤s) n 所产生的,且对所有的 i 和 n 都有P( n =0)=P( n =1)=1/2。函数 f 生成相互独立且 Xi Xi 服从同一分布的随机变量Zn = f ( n , n ,…, n ),且对所有的 n 都有 P (Zn =0)= X1 X2 Xs 1/2。置 P (=Xi )。再假定明文是一个二元无记忆信源(B P(Zn =1)=Zn n =qinary 的输出,且P((i) p0。 MemorylesSource,BMS) Yn =0)= 图3.2 1.分别征服相关分析的统计模型 其次,定义Cn 与Xi 之间的相关性的一个估计———相关度。 n 定义3.1 N 个密文符号C1C2…CN 1XiLFSR的输出序列,=s) 1.与Xi2…XiN (ii1,2,…, 之间的相关度(又称符合度)是一个随机变量α,其定义如下: α=(|{ j ,1, N }||{ j ,1,2,…, N }|)/N j|Cj =Xi j=2,…,-j|Cj ≠Xi j= Σ(N) (1-2(Cn ..Xin))/N = n=1N=1-2Σ Cn n )/N (..Xi n=1 α 就是Cn 与Xin之间的相关性的一个估计 。 Cn 与Xin之间的符合率 为 Cn =Xi )n= pe=P( n =P(Cn ..Xi 0) =P(Zn=Xi P(0)+P( n Yn= n )Yn=Zn ≠Xi )P(1) i1-1-p0)1-(i+p0)+2p0i 因此, =qp0+ (qi)(=qq P(Cn ≠Xi )=P(..Xi 1)1-pe n Cn n== 显然,是关于q和p0 的对称函数。pe 越大,说明Cn 与Xi 之间的符合率就越大, 从而密文序列段中含有(i) LFSRi 的子密钥的信息量就越大。当pe 接近于1时,密文序列段 与对应的LFSRi 的输出段近似相同,从而说明该密码是极不安全的。从pe 和 α 的定义和 表达式可以看到,密文序列段C1C2…CN 中所含LFSRi 的子密钥的信息量由明文特性p0、 Zn 和Xi 的符合率q以及密文长度 N 所决定。这就回答了本节开头提出的第一个问题。 现在(n) 来讨论随机变(i) 量 α 的分布。对任意给定的i(1≤i≤s),可将Cn ..Xi (2, pe n nn=1, 第 3 章　相关分析方法 49 3,…) 视作一些相互独立且服从同一分布的二元随机变量。因而,随机变量β= (Cn .. n=1 Xi )服从二项分布,其均值(也称期望值或数学期望)和方差σ2 分别为Σ(N) n mβ mβ = N (1-peβ =Npe1-pe ),σ2 ()(β) 因此,随机变量 α 的均值mα 和方差σ2 分别 为 α mα =1-2()2peα=()/N 1-pe=-1,σ24pe1-pen ni=1,s) n =0)= 设X0 是一个独立于Xi (2,…,的随机变量,且相互独立同分布,即P(X0 P(X0 1)1/2。由于Zn 与X0 统计独立,所以q0=P(X0)1/2,从而pe=1/2,此 时mα =0, α =1/ N 。 n == n Zn = n = σ2 由中心极限定理可知,当 N 足够大时,随机变量 α 服从均值为mα 、方差为σ2 的正态 α 分布。 在分别征服相关分析中,首先需要确定LFSRi 的子密钥。为此,对一个级数为ri 的 LFSR0(用于检测), 任选一个初态,从Ri 个可能的反馈多项式中任选一个,由该LFSR0 产 生 N 个符号,再用这 N 个符号与 N 个密文符号一起计算出相关度 α 的一个确切值α0,它 表现出以下两种情形的假设: H1:LFSR0 的这 N (>ri)个符号与LFSRi 所对应的 N 个符号一致,这种情形对应的 α0 表现的是Cn 和Xi (1≤i≤s)的相关性。 H0:LFSR0 的这(n) N (>ri)个符号与LFSRi 所对应的 N 个符号不一致(至少有一个不 同), 这种情形对应的α0 表现的是Cn 和X0 的相关性。 n 为了对假设进行检验,必须利用相关度α0 的值。为了对检验结果给出一个判决,必须 对两个假设H0 和H1 设定一个判决门限值T,使得当α0< T 时,接受H0;当α0≥ T 时,接 受H1。设H0 所对应的概率密度分布函数为pα|H0(x),H1 所对应的概率密度分布函数为 pα|H1(x), 由中心极限定理可知,当 N 足够大时,pα|H0是均值为m0=0、方差为σ02=1/ N 的正态分布函数,即 1 -(2/2σ2 ex-m0)0 pα|H0 = 2πσ0 pα|H12pe-1=4pe1-pe 是均值为m1=1、方差为σ2()/ N 的正态分布函数,即 1 -(2/2σ2 ex-m1)1 pα|H1 = 2πσ1 当qi =1/2或p0=1/2时,pe=1/2。此时,pα|H0=pα|H1,在这种情形下,无法进行 判决。 假设检验的计算工作量依赖于错误判决的数目。错误判决分为两类:一类是由事件 α≥T|H0所引起的,称它为假真错误,即把假的参数判决为真的;另一类是由事件αN1一般不能降低需要的检测次数。 可证明,Q(x)满足如下关系: ( 2πx ) -1e-x2 2 (1-x2)n- m 时,0。当r= m 时,若 2..i1i2…nk0 为奇数,则所有的n- m 次项都出现;若k0 为偶数,则所有的n- m 次项都不出现。 当 W H(f)=2n-1,m≤n-2时,可知k0 为偶数,于是对于r≥n- m 都有ai1i2…ir =0。 Fn 综上所述,如果f(x):2→F2 是非线性次数为 k 的 m 阶相关免疫函数,则k+ m ≤n。 特别地,当 f 是平衡布尔函数且m≤n-2时,则k+m≤n-1。这表明 f 的非线性次数k= .0f 和其相关免疫阶数 m 之间存在着某种制约关系,因此,在具体构造相关免疫函数时必 须适当折中考虑。目前,消除这种制约关系的办法主要有两种:一种是引进记忆;另一种是 使用广义相关免疫函数。 3.快速相关分析方法 在非线性组合生成器中,当组合函数的输出与某些输入变量的符合率 p 达到0. 75 时, 从计算量的角度来说,利用分别征服相关分析方法可破译每个LFSR 的长度 k 不超过50 的 2 非线性组合生成器。本节主要介绍两个参数适用范围更广的关于非线性组合生成器的相关 分析方法,即文献[3]中所称的算法A和算法B z。 n },an }假定非线性组合生成器的输出序列为z={ z 与其中一个LFSR 序列a={的相 关概率p=P(5,则算法A和算法B的目的都是用来确定 a 的初态。这两个算 n =)>0.法都要求反馈的(z) 抽头(a) 数(n) t 较小。特别地,当p≤0.75 时,要求t<10 。算法A是一个有效的 2c(<1) 指数时间分析方法,其计算复杂度为O(ck ), 其中 k 表示LFSR 的长度,依赖于攻击 的输入参数。算法B是一个多项式时间分析方法,其计算复杂度是LFSR 的长度 k 的多项 式。这两个算法实质上比穷举搜索整个初始状态更快,而且适用于相当长的LFSR(如k= 1000 或更长)。然而,通过比较可知, 75 左右时, 而当 p 在 当c.1 且 p 在0.算法A更好; 0.5左右时,算法B更有效。这两个算法可应用于已知明文攻击和唯密文攻击。已证明,当 p≤0.75 时,如果较长的LFSR 的抽头数较大( t≥10), 大约k≥100,则这两个算法都是不可 行的。 1. 2. 3 快速相关分析的统计模型 假定一个二元密钥流生成器的输出序列 z 与一个LFSR 序列 a 的相关概率 p = P( n = n )>0. za5。LFSR 序列 a 可通过如下形式的线性递归关系式给出: an =c1an-1+c2an-2+ …+cn-(3.1) a2. 其中c(x)xk (1)是这个关系(k) 式的(k) 反馈多项式。反馈多项式 =c0+c1x+c2x2+…+ckc0= k }2. 的抽头数 t 等于{c2,…,的非零项的个数。因此,式(1)可表示成如下含t+1 项 的等式: c1,cΣ an-103.2.=(3.2) {i:0≤i≤k,i≠0} 通过移位序列a,可以观测到,每一个固(c) 定的数字a在式(3.2)的t+1 个位置都出 现,也就是说它同时满足形式为式(3.2)的t+1 个等式。(n) 2. 2. 58 序列密码分析方法 另外,c(x)的每一个多项式倍式都定义了a 的一个线性递归关系式,特别地,对j=2i, c(x)j 就是a 的一个线性递归关系式,此时c(x)j=c(xj)。这样就比单纯通过移位能获得 更多的线性关系式,而且这些关系式的抽头数都是t。这一特性很重要,因为算法A 和算法 B的可行性依赖于抽头数。事实上,对于给定的序列z,快速相关分析需要测试所有这些线 性关系式来确定对于给定的n 是否zn 与an 一致。 假定an 是固定的,那么按上述方式获得的线性关系式可写成如下形式: L1 =an +b1 L2 =an +b2 . Lm =an +bm ì . í ... .. . (3.2.3) 这里bi(i=1,2,…,m )恰好是序列a 的t 个不同项的和,m 是获得的线性关系式的个数,其 值在后面确定。 在式(3.2.3)中,对同一下标位置,用序列z 来代替序列a,可得到如下表达式: Li =z +yi, i=1,2,…,m (3.2.4) 这里Li 未必为0。 通过以上分析和相关事实,可以引入一个一般的统计模型。用二元随机变量集{a,b11, b12,…,b1t,b21,b22,…,b2t,…,bm1,bm2,…,bmt}代替式(3.2.3)中序列a 的数字,并满足如下 相应的等式: a +b11 +b12 + … +b1t =0 a +b21 +b22 + … +b2t =0 . a +bm1 +bm2 + … +bmt =0 ì . í ... .. . (3.2.5) 类似地,用二元随机变量集{z,y11,y12,…,y1t,y21,y22,…,y2t,…,ym1,ym2,…,ymt}表 示式(3.2.4)中序列z 的数字。 两个随机变量集有如下关系: P(z =a)=p, P(yij =bij)=p (3.2.6) 除了式(3.2.5)和式(3.2.6)外,这里假定这些二元随机变量都是相互独立且同分布的,它们 是1或0的概率等于0.5。 对i=1,2,…,m ,可导出如下随机变量: bi =bi1 +bi2 + … +bit yi =yi1 +yi2 + … +yit Li =z +yi ì . í .. .. (3.2.7) 设bi 和yi 相等的概率是s,即 s=P(yi =bi) (3.2.8) 显然,s 独立于i 且是p 和t 的函数,即s=s(p,t)。 s 可通过如下递归关系式来计算: s(p,t)=ps(p,t-1)+ (1-p)(1-s(p,t-1)) s(p,1)=p (3.2.9) 第3 章　相关分析方法 59 接下来,考虑随机变量L1,L2,…,Lm 。 由于Li=0暗含着z=a,yi=b 或z≠a,yi≠bi,因此,对给定的h(0≤h≤m )个下标 集合{i1,i2,…,ih},恰好在这h 个对应位置的随机变量等于0(也称满足关系式或关系式成 立)、其他对应位置的随机变量等于1的概率为 P(L1 =1,…,Li1 =0,…,Li2 =0,…,Lih =0,…,Lm =1) =psh(1-s)m-h + (1-p)(1-s)hsm-h (3.2.10) 不失一般性,假定L1=0,L2=0,…,Lh =0,Lh+1=1,Lh+2=1,…,Lm =1,则由贝叶斯 公式可知,下列结论成立: P(z =a|L1 =L2 =… =Lh =0,Lh+1 =Lh+2 =… =Lm =1) = psh(1-s)m-h psh(1-s)m-h + (1-p)(1-s)hsm-h (3.2.11) P(z ≠a|L1 =L2 =… =Lh =0,Lh+1 =Lh+2 =… =Lm =1) = (1-p)(1-s)h s m-h psh(1-s)m-h + (1-p)(1-s)hsm-h (3.2.12) 实际上,式(3.2.11)给出了当m 个关系式中的h 个关系式成立时,zn =an 的概率,将这 个概率记为p* 。 根据上面介绍的统计模型以及一些事实,考虑一个随机实验。可访问z 和yij 的输出, 因此,可得到Li=z+yi,而不能访问a 和bij的输出,这是因为在我们的应用中z 和yij对应 给定序列的某些数字,而a 和bij 是指未知的LFSR 序列。特别地,当z 对应固定数字zn 时,我们希望确定a 对应的固定数字an 。从一个先验概率p=P(z=a)>0.5开始,记h 是 使得Li=0的下标i 的个数。然后根据式(3.2.11)把这个先验概率p=P (z=a)更新为新 的概率p* 。直观上,我们期望p* 在z=a 的情况下增加,而在z≠a 的情况下降低。为了 证实这个观点,对这两种情况分别计算p* 的期望值。 情况1:z=a。 E0[p* ]=E[p* |z =a] =Σm h=0Ch m psh(1-s)m-h psh(1-s)m-h + (1-p)(1-s)hsm-hsh(1-s)m-h (3.2.13) 情况2:z≠a。 E1[p* ]=E[p* |z ≠a] =Σm h=0Ch m psh(1-s)m-h psh(1-s)m-h + (1-p)(1-s)hsm-hsm-h(1-s)h (3.2.14) 值得一提的是,由式(3.2.13)和式(3.2.14)可知: E[p* ]=pE0[p* ]+ (1-p)E1[p* ]=p 这暗含着,尽管我们期望这个新的概率p* 在z=a 的情况下增加,而在z≠a 的情况下降 低,但总的期望值是不变的。另外,这里计算的是p* 的均值,因此,式(3.2.14)是正确的。 例3.2.1 设先验概率p =P (z=a)=0.75,t=2,m =20,则可得到E0[p* ]=0.9, E1[p* ]=0.3。 事实上,新的概率p* 是h 的一个函数,并且可使得在两种情况下的概率分布有明显的 区别,这将给我们提供了确定z=a 或z≠a 的一个主要准则。 序列密码分析方法 上述统计模型可以推广到非线性关系式的情况,从而可以将非线性关系式扩展到下面 介绍的分析方法中。关键点不是线性而是只有一些数字包括在这些关系式中这一事实。线 性本质的优点是产生的许多关系式(通过移位或迭代平方)的概率对同一数字成立。 本节最后介绍一个常用的、比较典型的统计模型。大多数基于LFSR 的序列密码的分 析往往涉及解决下面这样一个问题:假设攻击者收到了序列z=a.. x 的一个适当长的截 取段,其中: (1) a 是一个m-序列,其反馈本原多项式f(x)是已知的。 (2)序列 x 的代数结构不明,但已知数字0在这个序列中占某种优势(当数字1在这个 序列中占某种优势时,令z'1..zxn =则z'= ' ,在x'中0占某种优势), 即 n = n ,'1..xn , a.. x 有P(xn = 5- =5+ε,xn ==5ε, 0)0.P(1)0.-ε>0 。称 ε 为序列 a 的数字在序列 z 中所占的 优势,称0. ε 为 a 在 z 中的失真率。 现在要做的事情是:设法根据上述两点知识还原序 列a,主要是确定其初态。 因此,如果一个二元密钥流生成器的输出序列 z 与 一个LFSR 序列 a 的相关概率p=P(zn = n 5, 则 可将这种情况一般化为图3.1的统计模型 a 。 )>0. 2. 2. 其中zn =an ..xn ,BAS 表示二元非对称信源图3.1 一个常用的统计模型 (BinaryAsymmetricSource), P (xn =0)= P (zn =an )=p。 a 是一个二元随机序列且 P( n =0)P( n ==5。这样, =1)0.将要介绍的快速相关分析方法实际上是对这种模型的一种(a) 分析方法。此(a) 外,这种模型也可以用其他分析方法进行分析,如线性校验子分析方法 (见4.可参阅文献[16 2节), 18 ]。 算法A的基本思想及其描述 假定已给定了序列 z 的长度为 N 的一个截取段,LFSR 的反馈多项式、长度 k 和抽头 数t,以及LFSR 的输出序列 a 与给定序列 z 的相关概率p=P( n = n )。现在要解决的问 za 题是:找到未知的LFSR 序列a。基本上,这个序列可通过求解由它的任何 k 个数字构建 的关于初始状态的线性方程组被恢复出来。如果这些方程是线性依赖的,可以选择一些附 加的数字获得一个线性独立的方程组。因此,为了得到序列 a 的一个估计,我们实际上以 最高的概率 p *选择 z 的 k 个数字,这等价于选择满足式(3.3)的最多关系式的 k 个数字。 2. 算法A的基本思想是:通过测试找出正确的数字,即z= a 的数字z。具体测试办法是 选择满足更多等式的数字。用这种办法可获得序列 a 的相应位置的一个估计。在一定的 条件下,这些数字是正确的概率很高,亦即只要对这些数字稍作修改即可。实际上,我们是 利用LFSR 序列 a 的线性关系式找出正确的数字,即使得z= a 的数字。线性关系式可由 反馈多项式来描述。通过对反馈多项式进行迭代平方,对每个数字 a 可获得一组线性关系 式,每个线性关系式涉及 a 的 t 个其他数字。用这种办法获得的关系式的平均数 m 可由后 面要介绍的式(3.17)计算。 2. 一个固定的数字 z 至少满足 m 个关系式中的 h 个关系式的概率可通过下式来计算: 2. 2. 3 m i m-im- Q(p,m, = Cm (psi(1-s)i+ (1-p)(1-si) (3.15) h)Σ s)2. i= h 第3 章　相关分析方法 61 式(3.2.15)可由式(3.2.10)推出。设R(p,m ,h)表示z=a 且m 个关系式中至少有h 个关 系式成立的概率,则有: R(p,m ,h)=Σm i=hCi mpsi(1-s)m-i (3.2.16) 这样,在给定的m 个关系式中至少有h 个关系式成立的条件下,z=a 的概率为 T(p,m ,h)=R(p,m ,h) Q(p,m ,h) 因此,有Q(p,m ,h)·N 个数字满足至少h 个关系式且正确的概率是T(p,m ,h)。对 固定的p、m ,T(p,m ,h)是h 的递增函数。这样,为了最大可能地找到充分多的(至少k 个)数字,需要确定使得Q(p,m ,h)·N ≥k 的最大值h。 选择z 中至少满足h 个关系式的数字,并使用这些数字作为a 在相应下标位置的参考 猜测I0,则(1-T(p,m ,h))·Q(p,m ,h)·N 是I0 中被期望的错误数字数。如果这个数 很小,则对I0 稍作修改即可找到a。测试修改I0 时利用了LFSR序列a 相应的段(phase) 和给定序列z 的相关性。如果其相关性超过了一个适当的门限值,则接受这个状态。 下面来估计可获得的关系式的平均数m ,它是N 、k 和t 的函数。i(i≥0)次迭代平方 操作获得的线性关系式(3.2.3)的长度为2ik,可建立N -2ik 个线性关系式。但必须有 N -2ik≥0,因此i≤log2(N/k)。因为i 是整数,所以i 不能大于log2(N/k)的整数部分。 用[log2(N/k)]表示log2(N/k)的整数部分。因此,可按下列办法估计线性关系式的总量: T = Σ [log2(N/k)] i=0 (N -2ik)=N ([log2(N/k)]+1)- Σ [log2(N/k)] i=0 2ik =N ([log2(N/k)]+1)- (2[log2(N/k)]+1 -1)k ≈N ([log2(N/k)]+1)- (2N/k -1)k =N ([log2(N/k)]-1)+k 因为每一个关系式需要z 的t+1个数字,因此,每个数字的关系式的平均数m 是 T ·t+1 N =([log2(N/k)]-1)(t+1)+k N (t+1) 在我们的应用中k N (t+1).1,因此,上式可简化为 m =m (N ,k,t)≈ log2 N 2k . è . . . ÷ (t+1) (3.2.17) 算法3.2.1 算法A 第1步:根据式(3.2.17)确定m 。 第2步:寻找使得Q(p,m ,h)·N ≥k 的最大值h。 第3步:对z 中至少满足h 个关系式的数字进行搜索,并使用这些数字作为a 在相应 下标位置的一个参考猜测I0。 第4步:利用相应的LFSR序列a 与序列z 的相关性,通过测试修改I0,找到正确的 猜测。值 得注意的是,在第1步确定的m 仅仅是一个平均值。一般地,在z 的给定部分中,靠 近中间的数字比靠近边界的数字满足更多的关系式。因此,在中间部分,在正确和不正确的 数字之间有明显的区别是可能的。这就导致了算法3.2.1的一个改进,用下面的第3'步替 62 序列密码分析方法 换第3步。 第3'步:根据式(3.2.11)对z 的给定的数字计算新的概率p* ,并选择k 个具有最高概 率p* 的数字。 在第3步,I0 中错误数字的平均数r-=(1-T(p,m ,h))·k。在合适的条件下(如r-. 1),第4步是不必要的。 例3.2.2 假定z 的截断长度N =5000,p=0.75,k=100,t=2,则可由式(3.2.17)得到 测试z 的数字的关系式个数m =12。通过计算函数Q (p,m ,h)和T (p,m ,h)可知:要使 Q(p,m ,h)·N =0.02189×5000≈109成立,期望有h≥11个关系式。此时,(1-T (p,m , h))×109=0.001855×109≈0.2<1,这说明在这些数字中期望不正确的数字个数小于1,这 样在第3步选择的数字是正确的概率很高。第4步是不必要的。 下面讨论算法3.2.1的计算复杂度。因为第1步至第3步的计算时间是可忽略的,所以 仅仅估计在第4步需要尝试的平均数。假定在第3步找到的数字中恰好有r 个是不正确 的,那么在第4步需要尝试的最大次数为 A(k,r)=Σr i=0Ci k 对这个公式,存在一个使用二元熵函数的著名估计。二元熵函数的定义如下: H (x)= 0, x =0,1 -xlog2x - (1-x)log2(1-x), 00.67时,所有的c 都小于0.0005。当 t<10时,随着d=N/k 的增加,算法3.2.1有一个实质性的改进。例如,当d=N/k=109, p>0.57,t=2时,c=0.408,H (0.57)=0.986。当t≥10,p ≤0.75时,c 十分接近渐近值 H (p),算法3.2.1与(修改的)穷举搜索攻击相比没有本质上的优势,这一事实对可能发生 在实际应用中的所有d=N/k 都成立。 3.2.3 算法B的基本思想及其描述 提出算法B 的动因是如下这样一个事实:如果一个数字仅满足较少的关系式,则条件 概率p* 是很小的。这就导致了修正(也称校正)满足不超过一定数量关系式的数字的方 法。在合适的条件下,可以期望“正确的”的序列是与LFSR 序列a 有较少不同数字的序 列,重复这个过程直到恢复LFSR序列a。 算法B的基本思想是:考虑所有的数字以及它们是正确的数字的概率。开始时我们已 经知道z 与a 对应的数字相等的概率是p,通过考察等式成立的个数,给z 的每个数字赋予 一个新的概率p* ,即zn =an 的概率。实质上,p* 是p 和等式的个数的函数。可以将新的 可变的概率p* 作为每一轮的输入,迭代地进行上述过程。经过若干轮后,z 的所有具有比 某一门限值低的概率p* 的数字都被修正了。在适当的条件下,我们期望不正确的数字的个 数能降低。在这种情况下,重做整个过程若干次后,用新的序列代替z,直到找到LFSR 序 列a 为止。 m 个关系式中至多有h 个关系式成立的概率可按如下公式计算: U(p,m ,h)=Σh i=0Ci m (psi(1-s)m-i + (1-p)(1-s)sm-1) (3.2.19) 再者,zn =an 且m 个关系式中至多有h 个关系式成立的概率可由如下公式给出: V(p,m ,h)=Σh i=0Ci mpsi(1-s)m-i (3.2.20) 类似地,zn ≠an 且m 个关系式中至多有h 个关系式成立的概率为 W (p,m ,h)=Σh i=0Ci m (1-p)(1-s)ism-i (3.2.21) 因此,U(p,m ,h)·N 是满足至多h 个关系式的z 中数字的期望数。如果这些数字被修 正,则W (p,m ,h)·N 是被正确地改变的数字的个数,V(p,m ,h)·N 是被错误地改变的 数字的个数。正确数字的增量是W (p,m ,h)·N -V(p,m ,h)·N 。定义相对增量如下: I(p,m ,h)=W (p,m ,h)-V(p,m ,h) (3.2.22) 这样,对给定的p 和m ,最佳方式是选择使得I(p,m ,h)达到最大值的hmax作为h。 为了达到最大的修正效果(correctioneffect,也称校正作用),取门限值Pthr为 64 序列密码分析方法 Pthr=12 (p* (p,m ,hmax)+p* (p,m ,hmax +1)) (3.2.23) 因此,概率为p* 0,则根据式(3.2.23)和式(3.2.24)计算 Pthr和Nthr。 第3步:初始化迭代计数器i=0。 第4步:对z 的每个数字,利用其所满足的关系式的个数计算新的概率p* (计算阶段, 利用一般化了的式(3.2.11)和式(3.2.25))。确定概率为p*