信息认证技术.ppt

《信息认证技术.ppt》由会员分享，可在线阅读，更多相关《信息认证技术.ppt（26页珍藏版）》请在优知文库上搜索。

1、信息认证技术Hash函数v单向函数v 定义：函数f：A- B 若满足如下两个条件，则称为单向函数。v （1）对任意xA ，计算y=f(x)是容易的，yB；v （2）对yB ，求xA ，满足f(x)=y是计算上不可能的。 v Hash函数v 定义:函数H：A*-An 若满足以下三个性质，则称H是安全保密中的Hash函数。vA*：任意长度0,1字符串构成的集合；vAn：固定长度为n的0,1字符串Hash函数vHash函数v （1）H是单向函数；v （2）已知xA*，找出x*A*，使H(x)=H(x*)在计算上是不可能的；v （3）找出一对x和x*A*，xx*，使得H(x)=H(x*)在计算上不可能

2、。（防碰撞性）Hash函数v信息认证码v 与密钥相关的Hash函数值称为消息鉴别码（Message Authentication Code ,MAC)，也叫信息认证码。信息认证码附在消息m的后面，作为认证用。v 信息认证码的应用模式 v 表示含有参数k的Hash函数，k通常是密钥。 v (1)A向B送去信息m的同时，附上他们之间通信用的密钥k产生的 .B收到后，利用他们共享的密钥k，B计算得 ,若 ,则m得到确认(A寄来的无篡改的消息)，否则拒绝。( )kHm*( )kHm*( )( )kkHmHm( )kHmHash函数v(2)A向B送去(m, ),即将H(m)(散列值)用密钥k加密后得 附

3、在m的后面寄给B。B收到后首先用k解密得H(m),再计算H*(m),与(1)中相同的步骤检验是否接受m。v(3)A向B送去(m, ) ,其中 是A对H(m)利用公钥密码系统中A的私钥进行数字签名。B收到后，利用A的公钥 做v 然后计算H*(m),看是否相同进行检验。( )kEH m( )kEH m( )ADH m( )ADH mAE( )( )AAEDH mH mMD5算法v(1)MD5简介v MD5算法是R.Rivest在MIT开发设计的散列函数，MD表示消息摘要(Message Digest)。对于输入的任意长的消息，通过MD5算法输出是128bit的0，1字符串，我们称为消息摘要，又叫散

4、列值。v 算法设计的目标： 安全性 直接安全性 速度 简单性和紧凑性 有利于微处理器运行MD5算法v(2)MD5算法描述v初始化v (1)首先填充消息m使其长度比特数b满足 b448 mod 512v即补充上去的比特，使之m的长度比512的倍数仅少64bit。补充的比特除第一位是1外，后面全是0。v (2)在(1)的基础上，再附上64bit表示原来消息的真实长度(比特数)，这样消息总长度恰好是512的整数倍。v(3)将前面处理后的消息划成长度为512bit的分组v ,总共L个512bit分组。v每个分组又划分为16个长度为32bit的子分组v v(4)四个32bit的变量初始化为v A=Ox0

5、1234567 B=0 x89abcdefv C=0 xfedcba98 D=0 x76543210121,LY YY1216,M MMMD5算法主循环次数主循环的次数是消息m按512bit划分后的分组数。由图可知，MD5的每次输入，除了512bit分组外，还需要上一次循环所得的128bit的散列值。Y0YkY1YL-1MD5MD5MD5MD5512512512512128128128128IVMD5算法 主循环 在算法主循环中，将A，B，C，D复制到另外的四个变量a，b，c，d中。 主循环总共四轮，每一轮的结构非常相似。每一轮进行16次操作。每次操作对a，b，c，d中的其中三个数作一个非线性

6、运算，然后所得结果加上第四个变量，分组Y的一个子分组M和一个常数，并加上a，b，c，d之一。最后用该结果代替a，b，c，d之一。 所有这些完成之后，将A，B，C，D分别加上a,b,c,d。然后用下一分组继续运行算法，最后输出是A，B，C，D的级联。MD5算法主循环第一轮FF第二轮GG第三轮HH第四轮IIABCD消息分组MD5算法v逻辑函数v 这四轮中每轮各有一个逻辑函数，分别用FF,GG,HH,II来表示，具体如下： vFF(a,b,c,d,Mj,s,ti)表示a=b+(a+F(b,c,d)+Mj+ti)s)vGG(a,b,c,d,Mj,s,ti)表示a=b+(a+G(b,c,d)+Mj+ti

7、)s)vHH(a,b,c,d, Mj,s, ti)表示a=b+(a+H(b,c,d)+Mj+ti)s)vII(a,b,c,d, Mj,s, ti)表示a=b+(a+I(b,c,d)+Mj+ti)s)vMj表示分组的第j个子分组(j从0到15),s 表示循环左移s位， ti是常数。MD5算法逻辑函数 四个逻辑函数的执行过程的示意图如下：abdc非线性函数sMjtiMD5算法l 逻辑函数中的非线性函数( , , )()()( , , )()()( , , )( , , )()F b c dbcbdG b c dbdcdH b c dbcdI b c dcbd 逻辑函数中的ti是随机的32位整数32

8、2( )1,2,.,64itSin iiSHA算法 SHA算法是美国标准与技术国家研究所(NIST)和NSA共同开发设计的，作为美国信息压缩的标准，与数字签名标准DSS一起使用。SHA对输入长度小于264 bit的消息，产生160bit的hash值。SHA算法描述v初始化v (1)与MD5一样，首先将消息填充为512bit的整数倍。填充方法与MD5完全一样，先添加一个1，然后填充尽量多的0使其长度是512的倍数刚好减去64bit，最后64bit表示消息填充前的长度。v (2)初始5个32bit的变量v A=0 x67452301 B=0 xefcdab89 C=0 x98badcfe v D=

9、0 x10325476 E=0 xc3d2e1f0 v前四个值和MD5相同，但A，B，C，D，E的存储采用Big_Endian模式，即最高字节放在最低位地址。SHA算法描述v主循环v (1)循环次数：与MD5一样，每次循环处理512bit的消息分组，循环次数是512bit分组的个数。v (2)变量复制v A-a B-b C-c D-d E-e v (3)主循环过程 主循环有4轮，每轮有20次操作（MD5也是四轮，但每轮只有16次操作）。每次操作对a，b，c，d和e中的三个变量进行一次非线性运算，然后进行与MD5类似的移位运算和加运算。SHA算法描述对于512bit的消息分组分成32bit的子分

10、组M0，M1，M15 然后通过如下算法将其扩展为80个32bit的子分组（W0，W1,W79) 设t是操作序号（0t79) 则主循环中四轮80次操作的计算过程可如下表示：temp=(a5)+ft(b,c,d)+e+Wt+Kt ; e=d ; d=c; c=b30; b=a; a=temp; 四轮迭代后，对A B C D E 重新赋值t381416WM01511679tttttttWMMMMt 求解：令Pm为m个人在一起，不存在相同生日的概率。根据设定(m-1)个人中无相同生日的概率为Pm-1，第m个人与其他(m-1)个人无相同生日的概率是 P0=365-(m-1)/365=(366-m)/36

11、5故有递推关系 Pm=P0*Pm-1=生日问题和生日攻击I型生日问题:有多少人在一起，至少有1/2的概率存在两个人有相同的生日？m13 6 6mP3 6 5mm113 6 4 !P3 6 5(3 6 5m ) !生日问题和生日攻击当m23时，Pm1/2。即在253人中至少有一人与A的生日相同的概率大于1/2。k364P1365 生日问题和生日攻击v对单向散列函数的生日攻击v 与生日问题类似，若一文件m的H(m)为32bit。问有多少文件放在一起，其中有两个文件的H(m)值相同的概率大于1/2。v类比 v可能的birthday=365 可能的H(m)值=232v设Pm是m个长度为32bit的散列

12、值串不存在两个相等的概率v若Pm217 即m217 时有两个相同H(m)串的概率大于1/2。Fiat-Shamir签名方案FS方案的密钥选择: CA给每个用户产生公开密钥和私人密钥 n=p*q p和q是两个大素数 公开密钥：v1,v2,.,vk 0vin 私人密钥：s1,s2,sk 上述密钥满足：21(mod )iiv sn2 A计算由消息m连接xj的Hash函数值H(mxj) 对每一个散列值取前面kbit,得eij,i=1,2,k,j=1,2,t 3 A计算 A送给B的关于m的签名是xj和eijFiat-Shamir签名方案签名过程 1 A取t个小于n的随机整数 r1,r2,rt ,A计算2

13、(mod)1,2,.,jjxrnjt11,2,.,ijjjieyrsjtFiat-Shamir签名方案v鉴别过程v B收到(m,yj,eij)后v 1 B利用A的公钥计算v 2 B计算收到消息m连接zj的Hash函数值H(m zj) 取前面k比特,得e*ij i=1,2,k,j=1,2,tv 3 B比较e*ij=？eij v 若等式全部成立，则通过认证B接受消息m，否则拒绝接受消息m。即m可能不是A发出的，可能在中途被篡改。21z(mod )1,2,.,ijjjieyvn jtFiat-Shamir签名方案v小结:v1 Hash函数v2 MD5算法v3 安全散列算法v4 生日问题和生日攻击v5 Fiat-Shamir签名方案