第三章-数据的完整性保护(last1)

第三章数据的完整性爱护3、1消息摘录技术

一、基本原理

消息摘录（messagedigests）：是单向的散列函数（即Hash函数），它以变长的消息为输入，把其压缩成一个定长的值输出。若输入的信息被变更了，则输出的定长值（摘录）也会相应变更。依据Hash函数（即消息摘录函数）的平安水平，人们将Hash函数分成两大类：一类是强碰撞自由的Hash函数(strongcollision-freehashfunction)；另一类是弱碰撞自由的Hash函数(weakcollision-freehashfunctions).一个强碰撞自由的Hash函数是满足下列条件的一个函数h：

（1）

h的输入可以是随意长度的任何消息或文件M；（2）h输出的长度是固定的（该长度必需足够长，以反抗所谓的生日攻击，依据今日的计算技术和实力，至少应为128比特长）；（3）给定h和m，计算h（M）是简洁的；

（4）给定h的描述，找两个不同的消息（信息）M1和M2，使得h（M1）=h（M2）是计算上不行行的。（假如这两个消息M1，M2，M1≠M2，使得h（M1）=h（M2），则称这两个消息是碰撞消息或称这两个消息碰撞。）

一个弱碰撞自由的Hash函数与一个强碰撞自由的Hash函数的前三个条件（1）-（3）完全一样，不同的只是第（4）个条件。在一个弱碰撞自由的Hash函数中。（5）给定h的描述和一个随机选择的消息M1，找另一个消息M2，M2≠M1，使得h（M1）=h（M2）是计算上不行行的。实际受到的附件附件所期望的附件如果两者一样，则认为消息是完整的产生附件消息附件产生附件消息消息接收者发送者传输的消息比较一般的封装机制二、消息摘录技术的应用

1、用于计算消息完整码

消息m附件F将F′与收到的附件F进行比较假如F′=F则认为消息是完整的，否则不是完整的消息m附件FMD（m|KAB）重新依据m,由m|KAB计算附件F´消息m密匙KAB消息m发方A收方B传输的消息2、运用MD进行双向鉴别rArBABMD(KAB│rA)MD(KAB│rA)基于的双向MD鉴别机制一、概述MD4的设计是面对32比特字的，更适合于32位计算机，效率比MD2高。MD4计算出的消息摘录长度为128比特，用4个字表示，分别记为A，B，C，D，在计算起先时被分别初始化为常数。输入信息被分成512比特的等长块，逐块处理。每块包含16个字，分别记为m0，m1，……m15。每块的处理分三遍扫描，每遍对A，B，C，D运用不同的扰乱函数。在处理前需将当前的消息摘录备份，在处理后将这个备份加到新产生的消息摘录上，并将其作为下一块处理时消息摘录的当前值。最终一块信息处理之后的消息摘录当前值，即为最终的消息摘录值。3.1.1、

MD4二、MD4信息填充

给定一个X，将X进行填充，使其成为一个512比特的倍数串M=M[0]M[1]……M[N-1]，这里每个M[i](0≤i≤N-1)是长为32比特的串，N≡0(mod16)（即N是16的倍数。）我们将每个M[i]称为一个字（32位），由X产生M的算法如下：

⑴d=447-(│x│mod512)（当d<0时，按模512处理）⑵l表示x的长度，即│x│。│l│=64（即用64比特表示x的长度）⑶M=x‖1‖0d‖l初始信息（x）100……0初始信息的比特数（l）即使原来的信息已是512比特的倍数，也要进行填充。

三、干脆构造法现在我们从M起先构造一个128比特长的消息摘录，其构造过程如下：（1）给四个寄存器A、B、C、D赋初始值（用十六进制表示）：A=67452301B=efcdab89C=98badcfeD=10325476（2）fori=0toN/16-1do；（3）forj=0to15dom[j]=M[16i+j]

（4）将四个寄存器A、B、C、D的值存储到另外四个寄存器AA，BB，CC，DD之中，AA=A；BB=B；CC=C；DD=D（5）执行第一轮；（6）执行其次轮；（7）执行第三轮；（8）A=A+AA；B=B+BB；C=C+CC；D=D+DD[X]—取整—二进制求补；x∧y—x与y按位逻辑“与（and）”；x∨y—x与y按位逻辑“或（or）”；xy—x与y按位逻辑“异或（xor）”；

x+y—二进制加运算（即整数模232加法运算）；x<<y—x循环左移y个位置（0≤y≤31）。

MD4中的三个轮是不同的。1、第一轮第一轮运用一个如下定义的函数f（x，y，z）=（x∧y）∨（x∧z）(1）fork=0to3do；（2）

A=（A+f（B，C，D））+m[4k]<<3（3）

D=（D+f（A，B，C））+m[4k+1]<<7（4）

C=（C+f（D，A，B））+m[4k+2]<<11(5)B=（B+f（C，D，A））+m[4k+3]<<152、其次轮其次轮运用一个如下定义的函数：g（x，y，z）=（x∧y）∨（x∧z）∨（y∧z）取常数C2=[2]=5a827999H

留意：在其次轮中m[i]不是依次处理的。1）A=（A+g（B，C，D）+m[0]+5a827999）<<3；2）D=（D+g（A，B，C）+m[4]+5a827999）<<5；3）C=（C+g（D，A，B）+m[8]+5a827999）<<9；4）B=（B+g（C，D，A）+m[12]+5a827999）<<13；5）A=（A+g（B，C，D）+m[1]+5a827999）<<3；

(6)D=（D+g（A，B，C）+m[5]+5a827999）<<5；(7)C=（C+g（D，A，B）+m[9]+5a827999）<<9；(8)B=（B+g（C，D，A）+m[13]+5a827999）<<13；(9)A=（A+g（B，C，D）+m[2]+5a827999）<<3；(10)D=（D+g（A，B，C）+m[6]+5a827999）<<5；(11)C=（C+g（D，A，B）+m[10]+5a827999）<<9；(12)B=（B+g（C，D，A）+m[14]+5a827999）<<13；(13)A=（A+g（B，C，D）+m[3]+5a827999）<<3；(14)D=（D+g（A，B，C）+m[7]+5a827999）<<5;(15)C=（C+g（D，A，B）+m[11]+5a827999）<<9；(16)B=（B+g（C，D，A）+m[15]+5a827999）<<13；

第三轮第三轮定义扰乱函数如下：h（X，y，Z）=xyz取常数C3=[2]=6edgebalH

与其次遍扫描类似，第三遍扫描时对Mi的处理也不是依次的，具体为:(1)A=（A+h（B，C，D）+m[0]+C3）<<3；(2)D=（D+h（A，B，C）+m[8]+C3）<<9；(3)C=（C+h（D，A，B）+m[4]+C3）<<11；(4)B=（B+h（C，D，A）+m[12]+C3）<<15；(5)A=（A+h（B，C，D）+m[2]+C3）<<3；

(6)D=（D+h（A，B，C）+m[10]+C3）<<9；(7)C=（C+h（D，A，B）+m[6]+C3）<<11；(8)B=（B+h（C，D，A）+m[14]+C3）<<15；(9)A=（A+h（B，C，D）+m[1]+C3）<<3；（10）D=（D+h（A，B，C）+m[9]+C3）<<9；（11）C=（C+h（D，A，B）+m[5]+C3）<<11；（12）B=（B+h（C，D，A）+m[13]+C3）<<15；（13）A=（A+h（B，C，D）+m[3]+C3）<<3；（14）D=（D+h（A，B，C）+m[11]+C3）<<9；（15）C=（C+h（D，A，B）+m[7]+C3）<<11；（16）B=（B+h（C，D，A）+m[15]+C3）<<15；MD5第一轮F(x,y,z)=(xΛy)V(Λz)A=B+((A+f(B,C,D)+m[0]+d7aa78)<<7)D=A+((D+f(A,B,C)+m[1]+e8c7b756)<<12)C=D+((C+f(D,A,B)+m[2]+242070db)<<17)B=C+((B+f(C,D,A)+m[3]+c1bdceee)<<22)A=B+((A+f(B,C,D)+m[4]+f57c0faf)<<7)D=A+((D+f(A,B,C)+m[5]+4787c62a)<<12)C=D+((C+f(D,A,B)+m[6]+a8304613)<<17)B=C+((B+f(C,D,A)+m[7]+fd469501)<<22)A=B+((A+f(B,C,D)+m[8]+698098db)<<7)D=A+((D+f(A,B,C)+m[9]+8b44f7af)<<12)C=D+((C+f(D,A,B)+m[10]+ffff5bb1)<<17)B=C+((B+f(C,D,A)+m[11]+895cd7be)<<22)A=B+((A+f(B,C,D)+m[12]+6b901122)<<7)D=A+((D+f(A,B,C)+m[13]+fd987193)<<12)C=D+((C+f(D,A,B)+m[14]+a679438e)<<17)B=C+((B+f(C,D,A)+m[15]+49b40821)<<22)其次轮g(x,y,z)=(xΛz)V(yΛ)A=B+((A+g(B,C,D)+m[1]+f61e2562)<<5)D=A+((D+g(A,B,C)+m[6]+c04ob34o)<<9)C=D+((C+g(D,A,B)+m[11]+265e5a51)<<14)B=C+((B+g(C,D,A)+m[0]+egb6c7aa)<<20)A=B+((A+g(B,C,D)+m[5]+d62f105d)<<5)D=A+((D+g(A,B,C)+m[10]+02441453)<<9)C=D+((C+g(D,A,B)+m[15]+d8a1e681)<<14)B=C+((B+g(C,D,A)+m[4]+e7d3fbc8)<<20)A=B+((A+g(B,C,D)+m[9]+21e1cde6)<<5)D=A+((D+g(A,B,C)+m[14]+c33707d6)<<9)C=D+((C+g(D,A,B)+m[3]+f4d5od87)<<14)B=C+((B+g(C,D,A)+m[8]+455a14ed)<<20)A=B+((A+g(B,C,D)+m[13]+a9e3e9o5)<<5)D=A+((D+g(A,B,C)+m[2]+fcefa3f8)<<9)C=D+((C+g(D,A,B)+m[7]+676fo2d9)<<14)B=C+((B+g(C,D,A)+m[12]+8d2a4c8a)<<20)第三轮h(x,y,z)=x⊕y⊕zA=B+((A+h(B,C,D)+m[5]+fffa3942)<<4)D=A+((D+h(A,B,C)+m[8]+8771f681)<<11)C=D+((C+h(D,A,B)+m[11]+6d9d6122)<<16)B=C+((B+h(C,D,A)+m[14]+fde5380c)<<23)A=B+((A+h(B,C,D)+m[1]+a4beea44)<<4)D=A+((D+h(A,B,C)+m[4]+4dbecfa9)<<11)C=D+((C+h(D,A,B)+m[7]+f6b46bo)<<16)B=C+((B+h(C,D,A)+m[10]+bebfbc70)<<23)A=B+((A+h(B,C,D)+m[13]+289b7ecb)<<4)D=A+((D+h(A,B,C)+m[0]+eaa127fa)<<11)C=D+((C+h(D,A,B)+m[3]+d4ef3085)<<16)B=C+((B+h(C,D,A)+m[6]+04881d05)<<23)A=B+((A+h(B,C,D)+m[9]+d9d4d039)<<4)D=A+((D+h(A,B,C)+m[12]+e6db99e5)<<11)C=D+((C+h(D,A,B)+m[15]+1fa27cf8)<<16)B=C+((B+h(C,D,A)+m[2]+c4ac5665)<<23)第四轮I(x,y,z)=y⊕(xV)A=B+((A+I(B,C,D)+m[0]+f4292244)<<6)D=A+((D+I(A,B,C)+m[7]+432aff97)<<10)C=D+((C+I(D,A,B)+m[14]+ab9423a7)<<15)B=C+((B+I(C,D,A)+m[5]+fc93a039)<<21)A=B+((A+I(B,C,D)+m[12]+655b59c3)<<6)D=A+((D+I(A,B,C)+m[3]+8foccc92)<<10)C=D+((C+I(D,A,B)+m[10]+ffeff47d)<<15)B=C+((B+I(C,D,A)+m[1]+85845dd1)<<21)A=B+((A+I(B,C,D)+m[8]+6fa87e4f)<<6)D=A+((D+I(A,B,C)+m[15]+fe2ce6e0)<<10)C=D+((C+I(D,A,B)+m[6]+a3014314)<<15)B=C+((B+I(C,D,A)+m[13]+4e0811a1)<<21)A=B+((A+I(B,C,D)+m[4]+f7537e82)<<6)D=A+((D+I(A,B,C)+m[11]+bd3af235)<<10)C=D+((C+I(D,A,B)+m[2]+2ad7d2bb)<<15)B=C+((B+I(C,D,A)+m[9]+eb86d391)<<21)

常数可以如下选择:在第i步中,是×|sin(i)|的整数部分，i的单位是弧度。全部这些完成之后，将A,B,C,D分别加上AA,BB,CC,DD，然后用下一组数据接着运行算法，最终的输出是A,B,C和D的级联，即128位长的字。对单轮的MD5已有攻击结果，但对4轮MD5则还没有有效的方法。即使接受生日攻击，找寻具有相同Hash值的两个信息须要试验个信息，而差分攻击也对MD5的平安性步构成威逼。MD5与MD4相比较,主要作了以下六点改进:

(1)增加了第四轮，第四轮所运用的函数为Ⅰ（x，y，z）=（x∨）y；(2)其次轮的函数g变为g（x，y，z）=（x∧z）∨（y∧），以减弱它的对称性；(3)进入其次轮和第三轮的输入字的次序被改变；(4)每一轮中的移位数已变更，并且各轮中的移位数互不相同；(5)每一步有一个唯一的加法常数；(6)每一步加上了上一步的结果，这样会产生更好的“雪崩效应”。3.1.2Hash函数的攻击方法

生日攻击生日攻击这个术语来自于所谓的生日问题：在一个教室中最少应有多少学生,才使得至少有两个学生的生日在同一天的概率不小于？设h∶x→y是一个Hash函数，x和y都是有限的集合，并且│x│=m，│y│=n。明显至少有个碰撞，问题是如何去找这些碰撞。一个很自然的方法是随机选择k个不同的元素x1，x2，…，xk∈x，计算yi=h(xi)，1≤i≤k，然后确定是否有一个碰撞发生。

这表明，仅杂凑（随机拼凑）个x的随机的元素就能以50%的概率产生一个碰撞。留意:的不同选择将导致一个不同的常数因子，但k与仍成正比例。如前面的例子，x是一个教室中全部学生的集合，y是一个非润年的365天的集合，h(x)表示学生x的生日，现在我们类处理生日问题。这时n=365,=,由k≈1.17,=1.17,≈22.3，知教室中至少要有23名学生。生日攻击隐含着消息摘要的长度的一个下界。3．2数字签名技术一、数字签名为了具有通常手书签名的功效，数字签名应满足以下条件：（1）收方能够鉴别其收到的报文的确是发方发送来的，其内容是真实的；（2）发方事后不能依据自己的利益来否认他所发送过的报文；（3）包括收方在内的任何人都不能伪造报文或签名。二、利用公钥密码体制实现的数字签名1、在公钥密码系统的通信中，实现数据的保密性和真实性。(1)数据的保密性设用户A要发送消息M给用户B，AB,为了使M在传送过程中不被泄露，A可用B的公开密钥PKB对M加密，将密文传送给B。

M→→DSKB（EPKB（M））=M↑↑A方PKBSKBB方ED用公钥体制实现数据的保密性。

(2)数据的真实性条件：该公钥密码体制的公开密钥既能作加密密钥，又能作解密密钥运用，即DSK（EPK（M））=EPK（DSK（M））=MM→→M=EPKA（DSKA（M））↑↑A方SKAPKAB方ED公钥密码体制实现真实性。（丢失了保密性）

(3)既实现数据的保密性又实现数据的真实性

数据M→→→→M↑↑↑↑A方SKAPKBSKBPKAB方

DEDE用公钥密码体制实现数据的保密性和真实性

2、用公钥密码体制实现的数字签名

设A要向B发送一份报文M，该报文由两部分组成：一部分称作报头H，它包括发方的身份，收方的身份及发送序号等。即H=〈发方的ID〉，〈收方的ID〉，〈发送序号〉；另一部分是要发送的报文数据M，若须要可附上时间T。签名者用他的隐私密钥SKA对M或（M，T）进行变换（解密运算）得S=DSKA（M）或S=DSKA（M，T），实现对报文的签名，然后用收方B的公开密钥PKB对MS=（H，S）进行加密运算，并将结果EPKB（MS）发送给B，实现保密通信。M→→→M↑↑↑↑A方SKAPKBSKBPKAB方

DEDDHH签名保密通信加密脱密

验证签名

B收到报文后操作：

（1）B用自己的隐私密钥SKB先对收到的报文解密，得MS，依据H中的信息识别动身送者的身份是A。（2）在公开的签名信息簿中查出A用于签名验证的公开密钥PKA。（3）用PKA对S进行变换EPKA（S）=EPKA（DSKA（M′））=M。

（4）检查M′是否正确。

三、基于对称密码体制的数字签名L—D方法利用一组密钥，其个数由报文的长度确定，对报文进行逐位的签名。L—D方法分为准备、签名和验证三部分。准备的内容为：（1）若报文长度为n，则设置由发方A隐私保存的2n个签名密钥，记为λ1，μ1，λ2，μ2，……，λn，μn；（2）A随机地选择2n个数：u1，u2，……，un

U1，U2，……，Un

并分别用第一步产生的密钥对这2n个数据加密，得到2n个密文：vi=Eλi(ui)i=1,2,……，nvi=Eμi(ui)i=1,2,……，n

A将u1,u2,u3,……,unu1,u2,u3,……,un这2n个数据和2n个密文v1,v2,v3,……,vnv1,v2,v3,……,vn作密文验证信息公开交给B和仲裁者。(3)若报文M=m1m2……mn的第i位mi为1，则签名的第i位取μi，否则取λi，最终构成一个元素个数与报文长度相同的密钥序列。SA=K1K2……Kn。

Ki=μimi=1λimi=0i=1,2,……n其中A将A将SA留底后，发送给B.B收B收到签名数据后，验证签名的方法为：依据报文的内容确定密钥的内容，然后按报文的各位依据预先计算好的那两组数来验证收到的签名是否正确；（4）B用Ki分别对vi和Vi解密，若解得明文为ui，则断定mi=0；若为Ui，则断定mi=1。否则说明签名有错误或有篡改伪造行为。

0Dki(vi)=ui1Dki(Vi)=UiMi=B将收到的SA留底。

该方法存在两个严峻缺陷：

（1）签名比报文长的多，例如若运用DES作为加密算法，则每个密钥有56位，即签名的长度是报文长度的56倍。（2）签名密钥若不接受一次一密方式，则每次签名都会把n个密钥泄露出去，重复运用相同的签名密钥是很担忧全的；而一次一密的密钥管理负担很重。

四、仲裁者签名

通过第三者介入的传统密码数字签名（仲裁签名）

通信的双方A，B把各自的隐私密钥交给可信的第三者了，通信过程如图所示，设发方A要将信息M发送给B。S方仲裁者M→A方↑KAEM=DKA(C)C’=EKB(M)C’=EKB(M)D←KBB方3.3数字签名标准一.素根离散对数是很多公开密钥算法，包括Diffie-Klellman密钥交换算法及数字签名（DSA）的基础。本节对离散对数做一个简洁的概述。欧拉定理1modn现在考虑更一般的表达式：假如（a,n）=1，那么至少有一个整数m满足公式（*），即m=。满足公式（*）的最小指数m又称为以下几种方式：（1）a(modn)的阶。（2）a属于(modn)的指数。（3）a的生成周期长度。(*)1modn表7.6一般地，使1modn成立的最小正整数m，最高可能指数是，假如是a(modn)的阶，则a就是n的一个素根。这个概念的重要性是假如a是n的一个素根，则它的指数a,是（modn）各不相同的且均与n互素。特殊地，对一个素数p，假如a是p的一个素根，那么a,是（modp）各不相同的。对素数19，它的素根是2,3,10,13,14和15。指数及离散对数对于底数x和一个值y，有于是

对数包括如下性质：考虑某个素数p（也可运用非素数）的一个素根a,那么a从1到p-1的幂将产生从表面上1到p-1的一个置换（排列）。此外，依据模运算的定义，任何整数均能表示为：br(modp)于是对任何整数b和素数p的素根a，总可以找到唯一的指数使得b其中指数i称为数b以a（modp）为底数的指数，记为留意因为=[]归纳可得[]这说明真正的对数与指数很类似。正是由于这个缘由，后者常被成为离散对数（discretelegarithms）。表7.7模19的离散对数（a）以2为底模19的离散对数A123456789101112131415161718181132161463817121557114109

(b)以3为底模19的离散对数表A123456789101112131415161718187114486321112151713510169

数字签名标准DSS数据签名标准（DigitalSignatureStandard--DSS）是美国NIST（美国国家标准技术探讨所）于己于1991年8月建议的一种基于非对称加密体制的数据签名实现方法。DSS的平安性表现在：（1）对报文的签名不会引起密钥的泄漏；（2）若不知系统的私钥x，无人能够对给定的报文产生签名；（3）无人能够产生匹配给定签名的报文；（4）无人能够修改报文而还使原有的签名照旧有效。DSS算法包括下列内容：（1）选择p和q（公开的信息）q是160位的素数，p是512位—1024位的一个素数，(其中，且L为64的倍数：即比特长度在512到1024之间，长度增量为64bit。)且有p=kq+1（）。q和p的选择是很花费时间的，因此可运用标准中建议的数据。但是由于公布的质数有可能是陷门数据（即不是真的质数），所以在实现DSS算法时可考虑自己选择适应的数据。（2）产生g（公开的信息）找寻整数g（不应为1），使得1modp

g的计算可接受如下步骤：1取一随机数，令g;2依据费马定理（1modp）(或由Eular定理p是素数，故1modp即1modp）modp留意（p,q,g）称为全局公开密钥重量。

选择公开/私有密钥对<y,x>1随机选取1<x<q,将x作为私钥；

2公开密钥y由y=计算得出。

（4）计算消息M的签名附件（r,s）1用户随机地选取一个整数k(0<k<q);2计算r=()modq;3利用Eclid算法，顺便计算，这里表示kmodq的乘法逆，即4计算报文M的消息摘要H(M)；5计算报文的签名于是构成了消息H(M)的签名附件（r,s）

（5）向接受方B传送报文M，H(M)和（r,s）；（6）接收方用如下步骤验证签名：1接收者首先检测收到的消息的签名（）

若中有一个不成立，则拒绝接收该签名。2否则，接收者由和计算出v值，计算过程如下：

3比较v和，若则认为签名是有效的，否则认为是无效签名。在DSS算法中当v=r时，签名验证的有效性证明如下。引理1对任何整数t,若则