学习目标与要求 1.理解数字认证过程本质是一个交互证明过程这一概念。 2.掌握交互证明过程需要满足的两个属性：完整性和完备性。 3.理解在交互证明过程中证明者与验证者之间计算能力的差异。 3.1引言 本章从复杂性理论与交互证明（ interactive proof）的角度来阐述数字认证的理论基 础。尽管后续将介绍各种消息认证、身份认证及不同种类的数字签名方案或系统，但是 无论这些方案之间的区别多大，其本质都是交互证明系统，都需要符合交互证明系统 （interactive proof system，简称证明系统）规定的基本特征和安全要求。通过学习本章， 读者将了解一个重要的事实：对于一个设计合理的数字认证协议而言，即使在使用一个 计算能力非常有限的设备去执行它时，也能充分防范足够聪明或具有较强计算能力的敌 手对该设备进行欺骗。此外，读者也能了解到制约数字认证协议的各种因素以及数学基 本模型，为学习后续内容打好基础。 3.2交互证明系统 在通常情况下数字认证过程被认为是一个交互证明过程。在这个交互过程中包括两 个实体：证明者（ Prover，P）和验证者（ Verifier，V），认证过程就是证明者期望通过 信息交互使验证者能够接受他的某种宣称的过程。在计算机理论中这个交互证明过程可 由交互证明系统所描述。交互证明系统是一类计算模型，像其他计算模型一样，其目标 是对一个语言类 L和一个给定的输入 x进行验证，判断 x是否在 L中。在上述证明 过程中，两个实体（验证者和证明者）都被看作是某种类型的计算机（也被称为图灵机， Turing Machine）。它的交互证明过程为： 给定输入 x，通过验证者和证明者之间交换信息，最终由验证者根据证明者给 出的信息（或证据）判断输入 x是不是在语言 L中。 2828 为了从数字认证系统的角度更好地理解这一抽象模型，不妨将语言类 L比做所有 授权标识字符串构成的集合，输入 x是任何标识字符串，交互证明过程就是判定关系 x ∈ L是否成立。如果关系成立，则验证者 V输出为真（ True或 1），否则为假（ False 或 0）。再如，对于一个指纹身份认证系统，语言类 L可以理解为所有授权用户指纹特 征信息构成的集合，输入 x是任何采集到的指纹特征，认证系统就是判定该指纹特征 是否存在于集合 L中。 为了达到上述证明之目的，也可将交互证明视为二人博弈的过程。在博弈过程中， 首先要求证明者满足“忠诚性假定”，即证明者愿意向验证者进行其所宣称的证明，并 能够遵循交互证明的相关规定。也就是说，即便证明者有能力在博弈中获胜（去证明某 种宣称），但他不尽力导致输掉博弈通常是非常容易的，因此需要在博弈中排除掉这种 情况。除此之外，证明者与验证者之间也需要满足下面规定。 1 .能力假设：验证者具有多项式时间确定图灵机的计算机能力，但是证明者具有 强大的计算能力； 2，且由验证者（或 .运行规则：博弈双方共走 m步（保证在有限时间内终止博弈） 证明者）先行等规定； 3 .胜负规则：当且仅当 x属于 L，证明者在以 x为输入的对局中有必胜策略。 此处可以通过棋类系统更好地理解上述证明系统的规定。例如，围棋的运行规则是 黑棋先行，黑先白后，交替下子，但白棋多占 3又 3/4棋子来弥补黑棋的先行优势。另 一个例子是五子棋中先行的一方优势很大，有研究表明在双方都不犯错误情况下谁先下 子谁就会赢。由此可知，运行规则中约定的先行方在博弈中占有优势。胜负规则用于规 定博弈中如何确定获胜方，例如围棋按照所占空间多者为胜。 在此基础上，可以采用具有交互带的图灵机模型来描述上述系统，图 3.1便对上述 模型进行了描述：证明者和验证者分别用一台图灵机表示，每个图灵机具有一个工作带； 其次，两台图灵机之间共享一条交互带，证明者可以向其中写入或读取信息，验证者也 可以读写信息，通常是由一方写入而由另一方读出；进而，此处假设证明者和验证者之 图 3.1交互证明系统的图灵机表示 29 间共享一个随机输入带，两者都可以从该带中读取随机字符串用于概率选择。随机输入 带的引入是为了在交互证明中引入“随机数发生器”，从而使得证明过程存在不确定性 的猜测，这样的模型也被称为概率交互证明系统。 上述图灵机模型的优点就在于其可以用来衡量交互证明系统的性能，评估证明者 和验证者的计算性质。在交互过程中，证明者和验证者双方每次送给对方的符号被表示 为 y1,y2,···6,ym，其中， yi可依赖于 x和 y1,···6,yi.1来确定。此处将其关系表示为 yi = R(x,y1,···6,yi.1)，其中， R(·)为有效可计算函数。如果经过 m步后，验证者能 够证明所有交互符号 x,y1,y2,···6,ym均满足某种预定的条件 R(x,y1,y2,···6,ym)，则 证明者获胜，否则验证者获胜。这个过程可表示为： x ∈6L .6(.y1,.y2,···6,.ym.1,.ym,R(x,y1,y2,···6,ym)) 上述模型是建立在计算模型上的，对于一个安全协议设计而言，更需要关注的是协 议的安全性。如果说对于一个有效的输入 x ∈6L，存在一个忠诚的证明者 P能证明它属 于 L，则这将被认为是交互证明系统的应有功能。而用于认证的交互证明系统更关心无 效输入下的证明者行为，显然，对于无效输入 x6∈6L，一般希望证明者即便具有很强乃 至无限的计算能力也不能对验证者进行欺骗，即向验证者 V证明错误的结果 x ∈6L。 3.3模型与计算能力假设 数字认证研究的对象是各种安全协议，评价安全协议的标准就是看协议是否能够抵 抗敌手的各种攻击。敌手攻击的种类是繁多的，但对认证协议而言，最重要的是保证敌 手无法对其进行欺骗性的宣称。 根据交互证明系统的定义，协议中的敌手显然就是证明者，他要向验证者证明某种 虚假的宣称。以一个简单门禁系统为例，它由进门读卡器、门禁控制器、控制门开关的 电路以及射频 IC卡构成。其中，门禁控制器由一台用于 IC卡认证功能的小型计算机 或单片机构成，而射频 IC卡内部则集成了一个小型集成电路。可以看出这样一个门禁 系统成本不高，作为验证者的门禁控制器和作为证明者的射频 IC卡的计算能力都非常 有限。此处便需要思考这样一个问题，当攻击者采用一个后端为大型机（或未来量子计 算机）的设备进行攻击，这样的门禁系统是否就是不堪一击的？显然，需要设计一个好 的认证协议，使拥有合法射频 IC卡的授权用户可以快速实现身份认证，而使具有较强 计算能力的攻击者通过认证变为困难的。 因此，依据证明者与验证者的计算能力对比，可以发现一个根本性的问题：　 敌手（证明者）的能力越强，他是否就越可能进行欺骗？或者说，是否在认证 协议中要求验证者的能力一定具有与证明者对等或更强的计算能力？ 3030 这是个比较有意思的问题，其内涵可以看成是：证明者的能力是否决定命题的证明 结果或命题的正确与否？命题的证明是否与验证者的能力有关？证明命题与证明者和验 证者之间的计算能力相关吗？是不是一个非常“弱智力”的验证者能被“强智力”的证 明者所欺骗？如果一个“聪明”的证明者能够将“假命题”证明为真的，命题的证明是 “绝对”还是“相对”的？等等。 令 L .{0,1}.是一个语言类，可以将它理解为某种宣称的集合。根据上述胜负规 则和对证明者不可欺骗性的要求，交互证明系统定义如下： 定义 3.1由证明者与验证者 (P, V)构成的一个交互证明系统，如果它满足下面 两个条件，则有以下结果。 1。如果 x ∈6L，则存在诚实的证明者 P，使得 V与 P的 .完整性（ completeness） 交互之后，以绝对优势（或接近概率 1）接受 x并输出“x ∈6L”如下： Pr[(P,V)(x)=1|x ∈6L]=1 (3.1) 2 .完备性（ Soundness）。如果 x6∈6L，则对任意的证明者 P.，V与 P.交互之后， 仅以较小（可忽略）概率 ε输出“x ∈6L”如下： Pr[(P. ,V)(x)=1|x6∈6L]<ε (3.2) 上述定义中，完整性用于表明对于真命题 x ∈6L，证明系统存在一个有效的交互过 程以接近 1的概率通过证明；反之，对于一个伪命题 x6∈6L，那么任何的攻击者 P.想 通过交互证明的概率都是足够小（可忽略的）。因此，完整性被用于定义证明系统的正 确性，而完备性则被用于定义证明系统的不可欺骗性。注意，由于在完整性与完备性定 义中的前提假设不同（分别为 x ∈6L和 x6∈6L），因此这两个概率相互之间无关。 下面将给一个简单例子来验证交互证明系统的存在。假设存在一个山洞，如图 3.2所 示，进入洞穴后有两条道路，但是不知道这两条路径是否相通。 图 3.2交互证明洞穴 31 假设证明者 P是个探险家，他知道是否两条路径连通，并想向验证者 V证明这一 事实，但是验证者 V担心证明者 P欺骗他，因此设计了下面的游戏流程： 1 . P走进洞穴，可以选择一条路径到达 C或者 D点，V站在 A点，但看不到 P 选择了哪个路径； 2 .在 P进入洞穴后，V走进 B并向 P喊话，让 P从左通道或者右通道出来； 3 . P答应了，并从指定通道走出； 4 .如果 P从指定的通道走出， V认可道路连通（输出 1）；否则，否认这一结论 （输出 0）。 下面将分析上面游戏的有效性。上述游戏中的命题 x为：洞穴两条路径是连通的， L表示事实。此处分两种情况进行讨论。 1 .完整性：如果洞穴两条路径是连通的，即 x ∈6L，那么对于一个忠诚的证明者 P 来说，他总能按照 V的要求走出，因此，这种情况的交互游戏获胜（输出 1）的概率为 1，即 Pr[(P,V)(x)=1|x ∈6L]=1。 2 .完备性：如果洞穴两条路径是不连通的，那么对于任何证明者而言，他都可以事 先猜测验证者的喊话，从而在第一步中选择验证者要求的方向进入通道，如果这种猜测 是正确的，那么他就能获得成功；否则由于岩石的阻挡，他只能验证失败。因此，这一 验证结果取决于对验证者的猜测，如果验证者的喊话是完全随机的，即发出指令“由左 通道（或右通道）出来”的概率各为 1/2，即 Pr[(P,V)(x)=1|x6∈6L]= 1/2。 注意，在交互证明系统中，哪一方先行选择是很重要的。上例中是证明者先行，即 证明者先选择一条路径，但验证者不知道，因而可获得至少 1/2的成功概率。但是，如 果验证者可以先为证明进行选择，那么他可以直接指定证明者进入通道的方向，验证过 程将会更为简单，且不含有随机性。 3.4交互证明系统举例 下面将以平方剩余（也称二次剩余）的判定问题为例讨论一个实际的交互证明协议。 首先，回忆二次剩余问题，二次非剩余类定义如下： 2 定义 3.2（二次非剩余类）令 x和 n为正整数，如果存在整数 y，使得 y≡6x (mod n)，则称 x是在模 n下的二次剩余，记 x ∈6QRn，而 QNRn = {x|x6∈6QRn}则 被称为二次非剩余类。 例如，令 n = 13，当 x =4时，可以计算 22 ≡64(mod 13)和 112 = 121 ≡64 (mod 13)。因此， 4属于二次剩余类（ 4 ∈6QR13）。但是，当 x =5时，找不到一个 数的平方模 13后等于 5，因此 5属于二次非剩余类（ 5 ∈6QNR13）。如表 3.1所示， 此处列出了所有模 13的二次剩余关系。因此，可知 QR13 = {0,1,3,4,9,10,12}和 3232 QNR13 = {2,5,6,7,8,11}。 表 3.1二次剩余表（模 13） x y x y 1 1,12 4 2,11 9 3,10 3 4,9 12 5,8 10 6,7 需要说明的是，当 n为素数时，二次剩余的判定是容易的，但是当 n为合数时，二 次剩余的判定依赖于 n分解后的素因子。如果 n的分解未知时，二次剩余的判定是困 难的。 下面将给出一个二次剩余判定的证明系统。这个交互证明协议被描述在表 3.2中。 在这个协议中，给定 n和一个自然数 x，希望证明证明者 P具有对任意给定数 x进行 二次剩余判定的能力。 表 3.2基于二次非剩余判定的交互证明协议 步骤证明者验证者 验证者随机选择整数 b ∈{0, 1}，以及一个自然 数 z ∈ Z . ，然后计算数值 w如下： n . 第一步 . z 2 (mod n) b =1 w ≡ . x · z 2 (mod n) b =0 并将其送给证明者 证明者判定 w是否属于 QRn，如果是，则 第二步令 b ′ =1；否则，令 b ′ =0。并将所得结果 b ′ ∈{0,1}传送给验证者 验证者检测是否 b = b ′，如果是，输出 1，否则 第三步 输出 0 在表 3.2中，协议由验证者 V开始，他选择一个随机比特 b以及一个自然数 z，然 后依据 b生成挑战问题 w，并将其发送给证明者 P；证明者 P只需要通过对 w的二次 剩余判定即可对 b给出一个猜测 b ′；最后，验证者 V检查是否 b = b ′，如果等式成立， 则输出 1；否则，输出 0。因此，最终输出结果给出了证明者 P是否具有对给定数 x进 行二次非剩余判定能力的判定。 定理 3.1上述二次非剩余判定的交互协议是一个交互证明系统。 证明根据交互证明系统的定义，可证明该协议满足下面性质： 12 .完整性：如果 x ∈ QNRn，那么对任何数 z ∈ Z. n，挑战 w = x · z(mod n)也 33 属于平方非剩余类。根据这一性质，当验证者选择 b =1时，挑战 w属于平方剩余类； 但 b =0时，挑战 w属于平方非剩余类。如果证明者能够判定 w是否属于平方剩余类， 则可根据 w正确猜测出 b，因此，证明者能以概率 1使得 b = b ′，也就意味着验证者将 以概率 1接受证明者的证明，成功概率计算如下： Pr[(P,V)(x)=1|x ∈ QNRn] = Pr[b = b ′ |x ∈ QNRn] = Pr[b ′ =1|b =1,x ∈ QNRn]· Pr[b =1|x ∈ QNRn]+ Pr[b ′ =0|b =0,x ∈ QNRn]· Pr[b =0|x ∈ QNRn] = Pr[w ∈ QRn|w ≡ z 2 (mod n),x ∈ QNRn]· Pr[b = 1]+ Pr[w ∈ QNRn|w ≡ xz 2 (mod n),x ∈ QNRn]· Pr[b = 0] =1 · Pr[b = 1]+1 · Pr[b =0] =1 2 .完备性：如果 x是二次剩余类，那么无论验证者选择何种 b，所发送的 w都是 二次剩余的，因此，证明者将无法进行判定 b，因此他只能以概率 1/2猜测 b。因此， V 将以概率 1/2接受证明者的证明。上述性质可由下面等式证明： Pr[(P. ,V)(x)=1|x ∈ QRn] = Pr[b = b ′ |x ∈ QRn] = Pr[b ′ =1|b =1,x ∈ QRn]· Pr[b =1|x ∈ QRn]+ Pr[b ′ =0|b =0,x ∈ QRn]· Pr[b =0|x ∈ QRn] = Pr[w ∈ QRn|w ≡ z 2 (mod n),x ∈ QRn]· Pr[b = 1]+ Pr[w ∈ QNRn|w ≡ xz 2 (mod n),.y,y 2 = x (mod n)]· Pr[b = 0] = Pr[w ∈ QRn|w ≡ z 2 (mod n)]· Pr[b = 1]+ Pr[w ∈ QNRn|w ≡ (yz)2 (mod n)]· Pr[b = 0] =1 · Pr[b = 1]+0 · Pr[b =0] = Pr[b = 1] = 1/2 为了将验证者的欺骗成功概率降低到任意小的 ε，可采用 k次协议执行的方式，直到完 备性概率满足 1/2k <ε。令 (P. ,V)(i)表示第 i次协议执行，则上面完备性概率要求每 次证明都是成功的，也就是满足如下等式： Pr[(P. ,V)(x)=1|x ∈ QRn] k Π 1 = Pr[(P. ,V)(i)(x)=1|x ∈ QRn]= 2k i=1 因此，协议满足完整性和完备性，问题得证。 ■ 3434 例 3.1在上例中，首先来看完整性例子：令 n = 13且 x =2， 1 .如果 V选择 b =1且 z =5，那么 w = 12是二次剩余类。 2=5，那么 w = 11是二次非剩余类。 .如果 V选择 b 0且 z = 再来看完备性的例子：令 n = 13且 x =3， 1=5，那么 w = 12是二次剩余类； .如果 V选择 b 1且 z = 2 .如果 V选择 b =0且 z =5，那么 w = 10也是二次剩余类。 注意，上述证明过程对 n没有任何前提假设，也无须采用 RSA密码中大整数 N = p· q的条件。原因在于， x的二次剩余性质决定了协议结果的概率，这个概率是与 证明者的猜测无关的，或者说 1/2的猜测成功概率是仅由验证者对 b的选择概率决定 的；因此，只要 x属于二次剩余类，证明者无论具有怎样（无穷）的计算能力都无法进 行欺骗（改变成功概率 1/2k）。 3.5协议信息泄露 在设计证明协议时，证明者 P所具有的计算能力有可能会被验证者 V利用，实现 对某些问题的计算或泄露出某些秘密信息。为了说明这一问题存在，下面仍然以二次剩 余问题的求解为例，证明协议中的信息泄露问题。 令 N = p· q，不妨假设 p和 q是两个大素数，保证 N的分解是计算上困难的，且 p ≡ q ≡ 3(mod 4)，然后将 N作为公共参数发送给协议双方。表 3.3给出了一个交互协 议，协议中证明者宣称：他能够有效地判定任意给定 ZN中的数是否在平方剩余类中。 该协议只需要两次交互过程：验证者 V传送给 P值 y，它是一个随机选择的模 N的二 2 次剩余；然后， P计算 y的二次方根 x，并传送给 V；最后， V验证 y ≡ x(mod N) 是否成立。其中，p ≡ q ≡ 3(mod 4)是保证证明者能够有效计算 y的二次方根。. 表 3.3具有信息泄露的二次剩余判定交互证明协议 步骤证明者验证者 随机选择一个正整数 z ∈ ZN . ，然后计算数值 2 第一步 y ≡ z (mod N)，并将 y送给证明者 判定 y是否属于 QRN，如果是，则计算 x， 第二步 使得 y ≡ x 2 mod N，传送 x给验证者 检测是否 y ≡ x 2 mod N？如果是，输出 1，否 第三步 则输出 0 .令 p ≡ q ≡ 3(mod 4)是素数，那么 N = p· q被称为 Blum整数，且 (q + 1)/4和 (p+ 1)/4均为整数。在 已知 p和 q时，可以通过中国剩余定理计算出平方剩余数的四个平方根。 35 不难证明上述协议能够对证明者是否具有平方剩余判定和求根能力进行有效判定。 但是协议也存在着证明者对 N分解的泄露： 定理 3.2（信息泄露）如果上述协议输出 1，那么验证者能够通过该协议以 1/2 概率获得 N的分解。 2 证明在一次成功的协议执行过程中，第一步 V先选择 z，使得 y ≡6zmod N；第 二步中，P返回 x，6z且 y ≡6x2(mod N)。显然，有相等关系 y ≡6x2 ≡6z 如果 x= 2(mod N) 存在。因而， N|(z2 .x也就是 pq|(z.x)(z+x)。由于 x,z ∈6Z. ，故有 0 < 2)，Nz+x< 2N 且 .Nk，一个函数 h : {0,1}l →{0,1}k被称为 密码学 Hash函数。如果它满足下面属性： 1 .有效计算：给定 x，可在多项式时间内计算 y ←6h(x)。 .2单向性：已知 y，找出 x，使得 h(x)= y困难。 .3弱碰撞：已知 x，找出 x ′且 x ′6= x，使得 h(x ′ )= h(x)困难。 上述定义中，也可省略对单向性的要求，因为如下定理存在： 定理 4.2弱碰撞性预示着单向性。 证明假设存在一个有限时间内解决 Hash函数 h中单向性问题的预言机（ Oracle）， 即， Oracle(h,y)= x，使得 h(x)= y成立。那么给定一个 x，并提交 y = h(x)给 该 Oracle，如果 Oracle返回 x ′，如果 x = x ′，那么重复上面过程；否则，输出 x ′作为弱 碰撞问题的结果。在上述过程中，重复运行次数与 Hash函数在原像集合 {x : h(x)= y} ′ 大小相关。如果存在 Hash碰撞，则 Pr[x 6x] 1 。.弱碰撞问题得到解决的概率 = . 2 ′ Pr[Oracle(h,y)= x ∨6x= x ′ ]= Pr[Oracle(h,y)= x ′ ]· Pr[x6x ′ ]. Pr[Oracle(h,y)= 6= x ′ ]/2，因此，如果预言机解决 Hash函数的单向性问题的概率 Pr[Oracle(h,y)= x ′ ]足 够大，则上述碰撞问题求解概率也足够大，此时弱碰撞性不再成立。因而，逆反命题成 立，问题得证。 ■ 由于上述定理中的蕴含关系，在密码学 Hash函数定义中可以去掉单向性的要求， ′ 1 m . 1 11 .当存在 Hash碰撞时，m = |{x : h(x)= y}|. 2，进而 Pr[x =.x] . = =1 . . 。 2 mm 2 4444 而仅保留弱碰撞性。上述 Hash函数的定义满足了密码学的较低安全性，但有些情况下 需要密码学 Hash函数具有如下更强的安全性。 定义 4.3（抗碰撞 Hash函数）令 l>k，如果一个函数 h : {0,1}l →{0,1}k满 足下面属性，便可被称为抗碰撞 Hash函数。 1 . h是一个密码学 Hash函数； 2= .强碰撞：找出任意 x ′6x，使得 h(x)= h(x ′ )困难。 显然，强碰撞性要比弱碰撞性更加严格，此处给出如下简单证明： 定理 4.3强碰撞性预示着弱碰撞性。 ′ 证明假设存在一个解决 h中弱碰撞问题的预言机 Oracle，即， Oracle(h,x)= x ， 使得 h(x ′ )= h(x)成立。那么对一个给定的抗碰撞 Hash函数而言，只需要随机选择 ′′ 一个 x，并提交给该 Oracle，如果 Oracle返回 x 且 x=6x ，那么输出 (x,x ′ )。显然， (x,x ′ )使得强碰撞性不再成立。因而，逆反命题成立，问题得证。 ■ 上述定义并没有涉及密钥，也就是说 Hash函数的安全性不是基于某种秘密的私密 性，而是 Hash函数的数学属性本身决定的。从广义上讲，给定密钥空间 K，密码学 Hash 函数 H : K×{0,1}. →{0,1}k是一个能将任意长度消息压缩到固定长度比特串的函数。 但在实际系统中，通常会限制每一次 Hash函数的输入长度，再通过递归多次调用实现 无限长输入的输出。因此，密码学 Hash函数被进一步定义为 H : K×{0,1}l →{0,1}k， 这里仅定义了 Hash函数的压缩性质，其他性质与前述定义一致。 4.4基于分组密码的 Hash构造 采用分组密码构造是目前设计 Hash函数最经常被使用的方法，典型的标准包括 MD4、MD5、SHA-1、SHA-2等，其中，SHA是标准 Hash算法（Standard Hash Algorithm） 的缩写，SHA-2是第二代标准，它由 6个函数构成，包括 SHA-224、SHA-256、SHA-384、 SHA-512、SHA-512/224、SHA-512/256等，后面的数字表示输出的长度，可根据不同 应用需要选择使用。 分组密码是指一种将数据分解为若干分组，并以分组为单位循环进行处理的密码设 计技术。通常情况下，一轮数据处理并不足以达到数据混淆的目的，因此需要采用多轮 处理的方式获得最后的结果。但是与分组加密不同， Hash函数的设计要更加简单，原 因在于加密需要考虑信息加密后的恢复，因此每次运算都需要设计成为密钥下的随机置 换（可理解为符号之间的换位）；而 Hash函数只要保证输出结果的随机性，不需要考虑 消息的恢复。 分组 Hash函数的构造结构可被描述如下：假设输入数据 W可被分解为 l个分组， 即 W =(w1,w2,···6,wl)，且 wi ∈W（对于 i ∈6[1,l]），每次由函数 f : K×W×Mk →M6 4545 处理一个分组，其中， K、W、M∈{0,1}s分别为 s比特长的密钥、数据（也被视为 “填料”）和状态分组。 Hash函数操作是一个迭代过程，第 i次处理为 Mi+k ← fKi ,wi (Mi,··· ,Mi+k.1),i =1,··· ,n (4.1) 其中，Ki为第 i次迭代所使用的密钥，n>k且 f是一个非线性函数。通常情况下， k 是每次处理中的分组数目，n是 k的倍数，也被称为 Hash函数的轮数。 如果把这一过程看成一个“搅拌机”，那么 Hash函数的输入数据作为“填料”将 不断地被加入到迭代过程中。由于输入数据是有限的，在这些数据输入完后，通过对其 简单组合将形成新的“填料”。因此，分组 Hash构造与通常理解的函数处理不同，后者 是对输入数据进行变换，而分组 Hash函数则是由输入数据控制对系统状态的变换，这 是一种设计上的显著不同。此外，上述系统状态的变换要求是非线性的（也就是无法由 线性方程对该变换进行表示，进而对上述迭代过程也不能进行表示），其通常依靠 f中 存在的一个“非线性盒”来实现。 在给定初始的 k个状态 M1,··· ,Mk后，n次处理可表示为： . . ← (M1,M2,··· ,Mk) . Mk+1 fK1 ,w1 . . . . . Mk+2 ← fK2 ,w2 (M2,M3,··· ,Mk+1) . . .. ..(4.2) .. . . . . . Mn+k.1 ← fKn.1 ,wn.1 (Mn.1,Mn,··· ,Mn+k.2) . . . . Mn+k ← fKn ,wn (Mn,Mn+1,··· ,Mn+k.1) 最终， Hash函数的输出为最后 k个状态，即 (Mn+1,Mn+2,··· ,Mn+k) ← Hash(W )。 令每个分组长度为 |Mi| = s比特，则函数 f每次只处理 k · s比特。 如果每个分组占用一个寄存器，那么硬件设计仅需要 k个寄存器，并用新产生的分 组替代序号最小的分组，其他分组顺序右移，上述设计的好处是易于硬件实现。 下面针对上述 Hash函数构造模型，简要分析 Hash函数破解的难度。如图 4.2显 示了基于分组技术的 Hash函数构造框图。不难看出，上述 Hash函数可以被看成由初 始状态 (M1,M2,··· ,Mk)到最终状态 (Mn+1,Mn+2,··· ,Mn+k)的过程，期间经过了由 消息 (w1,w2,··· ,wl)控制的 n次状态转换。这一过程可转化为如下问题： 图 4.2基于分组技术的 Hash函数构造框图 4646 定义 4.4（分组 Hash函数求逆问题）给定一个 Hash函数输出 (Mn+1,Mn+2, ··· ,Mn+k)和初始状态 (M1,M2,··· ,Mk)，则分组 Hash函数求逆（或碰撞）过程也就 是在已知最终状态 (Mn+1,Mn+2,··· ,Mn+k)的情况下找到一组消息 (w1,w2,··· ,wl)， 使其控制一个函数将输出数据由终止状态还原到初始状态 (M1,M2,··· ,Mk)的过程。 不难发现随着轮数 n的增大，分组 Hash函数求逆问题难度也逐渐增大。在没有任 何先验知识的情况下，只要轮数足够多，由结束状态反推结果与初始状态相同的概率等 于 1/2ks。 4.4.1 SHA-1算法构造 SHA-1是一个输入为 512比特、输出为 160比特的压缩函数，其定义如下： SHA . 1 : {0,1}128 ×{0,1}32.16 →{0,1}160 (4.3) 第一个输入参数是 128比特的密钥 K，该密钥被定义为常数，第二个输入参数是 32*16=512比特的输入消息。 SHA-1面向字进行处理，字长度为 32比特，在 SHA-1中状态分组为 M，初始状 态由 5个字组成。初始的五个状态分别为 M1 = C3D2E1F0,M2 = 10325476,M3 = 98BADCFE, (4.4) M4 = EFCDAB89,M5 = 67452301 如图 4.3所示，给定初始的五个状态 M1,··· ,M5后，SHA-1处理要进行 n = 80 轮迭代。对于第 i =1,··· ,80次迭代的过程采用了反馈移位寄存器方式，表示为 Mi+5 = ROTL5(Mi+4)+fi(Mi+3,Mi+2,Mi+1)+Mi + wi + Ki (4.5) Mi+3 = ROTL30(Mi+3) 其中，ROTLj表示循环左移 j位，+表示模 232整数加运算。 关于输入数据（填料），512比特的输入 W需要被进一步划分成 16个 32比特的 字，即 Wi =(w1,w2,··· ,w16)。这 16组输入只能完成前 16次迭代，第 16次迭代之后 用到的所有填料 wi由之前的填料组合产生，表示如下： wi = ROTL1(wi.3 ⊕ wi.8 ⊕ wi.14 ⊕ wi.16),i = 17,··· ,80 (4.6) 每次迭代都使用一个非线性函数 ft，每个函数 ft（1 . t . 80）操作三个 32位字 (X,Y,Z),并产生一个 32位字作为输出。函数定义如下： . . . (X ∧ Y)∨ ((.X)∧ Z), 1 . t . 20 . . . ft(X,Y,Z)= . X ⊕ Y ⊕ Z, 21 . t . 40 (4.7) . . (X ∧ Y)∨ (X ∧ Z)∨ (Y ∧ Z), 41 . t . 60 . . . . X ⊕ Y ⊕ Z, 61 . t . 80