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

第三章数据的完整性保护,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，M1M2，使得h（M1）=h（M2），则称这两个消息是碰撞消息或称这两个消息碰撞。）,一个弱碰撞自由的Hash函数与一个强碰撞自由的Hash函数的前三个条件（1）-（3）完全一样，不同的只是第（4）个条件。在一个弱碰撞自由的Hash函数中。,（5）给定h的描述和一个随机选择的消息M1，找另一个消息M2，M2M1，使得h（M1）=h（M2）是计算上不可行的。,二、消息摘录技术的应用1、用于计算消息完整码,将F与收到的附件F进行比较,如果F=F则认为消息是完整的，否则不是完整的,MD（m|KAB）,重新根据m,由m|KAB计算附件F,消息m,2、使用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=M0M1MN-1，这里每个Mi(0iN-1)是长为32比特的串，N0(mod16)（即N是16的倍数。）我们将每个Mi称为一个字（32位），由X产生M的算法如下：,d=447-(xmod512)（当d0时，按模512处理）l表示x的长度，即x。l=64（即用64比特表示x的长度）M=x10dl,即使原来的信息已是512比特的倍数，也要进行填充。,三、直接构造法,现在我们从M开始构造一个128比特长的消息摘录，其构造过程如下：,（1）给四个寄存器A、B、C、D赋初始值（用十六进制表示）：A=67452301B=efcdab89C=98badcfeD=10325476,（2）fori=0toN/16-1do；,（3）forj=0to15domj=M16i+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取整,二进制求补；,xyx与y按位逻辑“与（and）”；,xyx与y按位逻辑“或（or）”；,xyx与y按位逻辑“异或（xor）”；,x+y二进制加运算（即整数模232加法运算）；,xyx循环左移y个位置（0y31）。,MD4中的三个轮是不同的。1、第一轮第一轮使用一个如下定义的函数f（x，y，z）=（xy）（xz）(1）fork=0to3do；（2）A=（A+f（B，C，D）+m4k3（3）D=（D+f（A，B，C）+m4k+17（4）C=（C+f（D，A，B）+m4k+211(5)B=（B+f（C，D，A）+m4k+315,2、第二轮第二轮使用一个如下定义的函数：g（x，y，z）=（xy）（xz）（yz）取常数C2=2=5a827999H注意：在第二轮中mi不是顺序处理的。1）A=（A+g（B，C，D）+m0+5a827999）3；2）D=（D+g（A，B，C）+m4+5a827999）5；3）C=（C+g（D，A，B）+m8+5a827999）9；4）B=（B+g（C，D，A）+m12+5a827999）13；5）A=（A+g（B，C，D）+m1+5a827999）3；,(6)D=（D+g（A，B，C）+m5+5a827999）5；(7)C=（C+g（D，A，B）+m9+5a827999）9；(8)B=（B+g（C，D，A）+m13+5a827999）13；(9)A=（A+g（B，C，D）+m2+5a827999）3；(10)D=（D+g（A，B，C）+m6+5a827999）5；(11)C=（C+g（D，A，B）+m10+5a827999）9；(12)B=（B+g（C，D，A）+m14+5a827999）13；(13)A=（A+g（B，C，D）+m3+5a827999）3；(14)D=（D+g（A，B，C）+m7+5a827999）5;(15)C=（C+g（D，A，B）+m11+5a827999）9；(16)B=（B+g（C，D，A）+m15+5a827999）13；,第三轮,第三轮定义扰乱函数如下：h（X，y，Z）=xyz,取常数C3=2=6edgebalH,与第二遍扫描类似，第三遍扫描时对Mi的处理也不是顺序的，具体为:,(1)A=（A+h（B，C，D）+m0+C3）3；,(2)D=（D+h（A，B，C）+m8+C3）9；,(3)C=（C+h（D，A，B）+m4+C3）11；,(4)B=（B+h（C，D，A）+m12+C3）15；,(5)A=（A+h（B，C，D）+m2+C3）3；,(6)D=（D+h（A，B，C）+m10+C3）9；(7)C=（C+h（D，A，B）+m6+C3）11；(8)B=（B+h（C，D，A）+m14+C3）15；(9)A=（A+h（B，C，D）+m1+C3）3；（10）D=（D+h（A，B，C）+m9+C3）9；（11）C=（C+h（D，A，B）+m5+C3）11；（12）B=（B+h（C，D，A）+m13+C3）15；（13）A=（A+h（B，C，D）+m3+C3）3；（14）D=（D+h（A，B，C）+m11+C3）9；（15）C=（C+h（D，A，B）+m7+C3）11；（16）B=（B+h（C，D，A）+m15+C3）15；,MD5,第一轮F(x,y,z)=(xy)V(z)A=B+(A+f(B,C,D)+m0+d7aa78)7)D=A+(D+f(A,B,C)+m1+e8c7b756)12)C=D+(C+f(D,A,B)+m2+242070db)17)B=C+(B+f(C,D,A)+m3+c1bdceee)22)A=B+(A+f(B,C,D)+m4+f57c0faf)7)D=A+(D+f(A,B,C)+m5+4787c62a)12)C=D+(C+f(D,A,B)+m6+a8304613)17),B=C+(B+f(C,D,A)+m7+fd469501)22)A=B+(A+f(B,C,D)+m8+698098db)7)D=A+(D+f(A,B,C)+m9+8b44f7af)12)C=D+(C+f(D,A,B)+m10+ffff5bb1)17)B=C+(B+f(C,D,A)+m11+895cd7be)22)A=B+(A+f(B,C,D)+m12+6b901122)7)D=A+(D+f(A,B,C)+m13+fd987193)12)C=D+(C+f(D,A,B)+m14+a679438e)17)B=C+(B+f(C,D,A)+m15+49b40821)22),第二轮g(x,y,z)=(xz)V(y)A=B+(A+g(B,C,D)+m1+f61e2562)5)D=A+(D+g(A,B,C)+m6+c04ob34o)9)C=D+(C+g(D,A,B)+m11+265e5a51)14)B=C+(B+g(C,D,A)+m0+egb6c7aa)20)A=B+(A+g(B,C,D)+m5+d62f105d)5)D=A+(D+g(A,B,C)+m10+02441453)9)C=D+(C+g(D,A,B)+m15+d8a1e681)14)B=C+(B+g(C,D,A)+m4+e7d3fbc8)20)A=B+(A+g(B,C,D)+m9+21e1cde6)5),D=A+(D+g(A,B,C)+m14+c33707d6)9)C=D+(C+g(D,A,B)+m3+f4d5od87)14)B=C+(B+g(C,D,A)+m8+455a14ed)20)A=B+(A+g(B,C,D)+m13+a9e3e9o5)5)D=A+(D+g(A,B,C)+m2+fcefa3f8)9)C=D+(C+g(D,A,B)+m7+676fo2d9)14)B=C+(B+g(C,D,A)+m12+8d2a4c8a)20),第三轮h(x,y,z)=xyz,A=B+(A+h(B,C,D)+m5+fffa3942)4)D=A+(D+h(A,B,C)+m8+8771f681)11)C=D+(C+h(D,A,B)+m11+6d9d6122)16)B=C+(B+h(C,D,A)+m14+fde5380c)23)A=B+(A+h(B,C,D)+m1+a4beea44)4)D=A+(D+h(A,B,C)+m4+4dbecfa9)11)C=D+(C+h(D,A,B)+m7+f6b46bo)16)B=C+(B+h(C,D,A)+m10+bebfbc70)23),A=B+(A+h(B,C,D)+m13+289b7ecb)4)D=A+(D+h(A,B,C)+m0+eaa127fa)11)C=D+(C+h(D,A,B)+m3+d4ef3085)16)B=C+(B+h(C,D,A)+m6+04881d05)23)A=B+(A+h(B,C,D)+m9+d9d4d039)4)D=A+(D+h(A,B,C)+m12+e6db99e5)11)C=D+(C+h(D,A,B)+m15+1fa27cf8)16)B=C+(B+h(C,D,A)+m2+c4ac5665)23),第四轮I(x,y,z)=y(xV),A=B+(A+I(B,C,D)+m0+f4292244)6)D=A+(D+I(A,B,C)+m7+432aff97)10)C=D+(C+I(D,A,B)+m14+ab9423a7)15)B=C+(B+I(C,D,A)+m5+fc93a039)21)A=B+(A+I(B,C,D)+m12+655b59c3)6)D=A+(D+I(A,B,C)+m3+8foccc92)10)C=D+(C+I(D,A,B)+m10+ffeff47d)15)B=C+(B+I(C,D,A)+m1+85845dd1)21),A=B+(A+I(B,C,D)+m8+6fa87e4f)6)D=A+(D+I(A,B,C)+m15+fe2ce6e0)10)C=D+(C+I(D,A,B)+m6+a3014314)15)B=C+(B+I(C,D,A)+m13+4e0811a1)21)A=B+(A+I(B,C,D)+m4+f7537e82)6)D=A+(D+I(A,B,C)+m11+bd3af235)10)C=D+(C+I(D,A,B)+m2+2ad7d2bb)15)B=C+(B+I(C,D,A)+m9+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）=（xz）（y），以减弱它的对称性；,(3)进入第二轮和第三轮的输入字的次序被改变；,(4)每一轮中的移位数已改变，并且各轮中的移位数互不相同；,(5)每一步有一个唯一的加法常数；,(6)每一步加上了上一步的结果，这样会产生更好的“雪崩效应”。,3.1.2Hash函数的攻击方法生日攻击,生日攻击这个术语来自于所谓的生日问题：在一个教室中最少应有多少学生,才使得至少有两个学生的生日在同一天的概率不小于？,设hxy是一个Hash函数，x和y都是有限的集合，并且x=m，y=n。显然至少有个碰撞，问题是如何去找这些碰撞。,一个很自然的方法是随机选择k个不同的元素x1，x2，xkx，计算yi=h(xi)，1ik，然后确定是否有一个碰撞发生。,这表明，仅杂凑（随机拼凑）个x的随机的元素就能以50%的概率产生一个碰撞。,注意:的不同选择将导致一个不同的常数因子，但k与仍成正比例。,如前面的例子，x是一个教室中所有学生的集合，y是一个非润年的365天的集合，h(x)表示学生x的生日，现在我们类处理生日问题。这时n=365,=,由k1.17,=1.17,22.3，知教室中至少要有23名学生。,生日攻击隐含着消息摘要的长度的一个下界。,32数字签名技术,一、数字签名为了具有通常手书签名的功效，数字签名应满足以下条件：（1）收方能够鉴别其收到的报文确实是发方发送来的，其内容是真实的；（2）发方事后不能根据自己的利益来否认他所发送过的报文；（3）包括收方在内的任何人都不能伪造报文或签名。,二、利用公钥密码体制实现的数字签名,1、在公钥密码系统的通信中，实现数据的保密性和真实性。,(1)数据的保密性,设用户A要发送消息M给用户B，AB,为了使M在传送过程中不被泄露，A可用B的公开密钥PKB对M加密，将密文传送给B。,MDSKB（EPKB（M）=MA方PKBSKBB方,E,D,用公钥体制实现数据的保密性。,(2)数据的真实性,条件：该公钥密码体制的公开密钥既能作加密密钥，又能作解密密钥使用，即DSK（EPK（M）=EPK（DSK（M）=M,MM=EPKA（DSKA（M）A方SKAPKAB方,E,D,公钥密码体制实现真实性。（丧失了保密性）,(3)既实现数据的保密性又实现数据的真实性,数据MMA方SKAPKBSKBPKAB方,D,E,D,E,用公钥密码体制实现数据的保密性和真实性,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，实现保密通信。,B收到报文后操作：,（1）B用自己的秘密密钥SKB先对收到的报文解密，得MS，根据H中的信息识别出发送者的身份是A。,（2）在公开的签名信息簿中查出A用于签名验证的公开密钥PKA。,（3）用PKA对S进行变换EPKA（S）=EPKA（DSKA（M）=M。,（4）检查M是否正确。,三、基于对称密码体制的数字签名,LD方法利用一组密钥，其个数由报文的长度决定，对报文进行逐位的签名。LD方法分为准备、签名和验证三部分。,准备的内容为：,（1）若报文长度为n，则设置由发方A秘密保存的2n个签名密钥，记为1，1，2，2，n，n；,（2）A随机地选择2n个数：u1，u2，unU1，U2，Un并分别用第一步产生的密钥对这2n个数据加密，得到2n个密文：vi=Ei(ui)i=1,2,，nvi=Ei(ui)i=1,2,，nA将u1,u2,u3,unu1,u2,u3,un这2n个数据和2n个密文v1,v2,v3,vnv1,v2,v3,vn作密文验证信息公开交给B和仲裁者。,(3)若报文M=m1m2mn的第i位mi为1，则签名的第i位取i，否则取i，最终构成一个元素个数与报文长度相同的密钥序列。SA=K1K2Kn。,其中,A将A将SA留底后，发送给B.B收B收到签名数据后，验证签名的方法为：根据报文的内容确定密钥的内容，然后按报文的各位根据预先计算好的那两组数来验证收到的签名是否正确；,（4）B用Ki分别对vi和Vi解密，若解得明文为ui，则断定mi=0；若为Ui，则断定mi=1。否则说明签名有错误或有篡改伪造行为。,B将收到的SA留底。,该方法存在两个严重缺陷：,（1）签名比报文长的多，例如若使用DES作为加密算法，则每个密钥有56位，即签名的长度是报文长度的56倍。,（2）签名密钥若不采用一次一密方式，则每次签名都会把n个密钥泄露出去，重复使用相同的签名密钥是很不安全的；而一次一密的密钥管理负担很重。,四、仲裁者签名,通过第三者介入的传统密码数字签名（仲裁签名）,通信的双方A，B把各自的秘密密钥交给可信的第三者了，通信过程如图所示，设发方A要将信息M发送给B。,S方仲裁者,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）称为全局公开密钥分量。,选择公开/私有密钥对1随机选取1xq,将x作为私钥；2公开密钥y由y=计算得出。,（4）计算消息M的签名附件（r,s）1用户随机地选取一个整数k(0kq);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