信息认证技术.ppt
信息认证技术,Hash函数,单向函数 定义：函数f：A-B 若满足如下两个条件，则称为单向函数。（1）对任意xA，计算y=f(x)是容易的，yB；（2）对yB，求xA，满足f(x)=y是计算上不可能的。Hash函数 定义:函数H：A*-An 若满足以下三个性质，则称H是安全保密中的Hash函数。A*：任意长度0,1字符串构成的集合；An：固定长度为n的0,1字符串,Hash函数,Hash函数（1）H是单向函数；（2）已知xA*，找出x*A*，使H(x)=H(x*)在计算上是不可能的；（3）找出一对x和x*A*，xx*，使得H(x)=H(x*)在计算上不可能。（防碰撞性）,Hash函数,信息认证码 与密钥相关的Hash函数值称为消息鉴别码（Message Authentication Code,MAC)，也叫信息认证码。信息认证码附在消息m的后面，作为认证用。信息认证码的应用模式 表示含有参数k的Hash函数，k通常是密钥。(1)A向B送去信息m的同时，附上他们之间通信用的密钥k产生的.B收到后，利用他们共享的密钥k，B计算得,若,则m得到确认(A寄来的无篡改的消息)，否则拒绝。,Hash函数,(2)A向B送去(m,),即将H(m)(散列值)用密钥k加密后得 附在m的后面寄给B。B收到后首先用k解密得H(m),再计算H*(m),与(1)中相同的步骤检验是否接受m。(3)A向B送去(m,),其中 是A对H(m)利用公钥密码系统中A的私钥进行数字签名。B收到后，利用A的公钥 做 然后计算H*(m),看是否相同进行检验。,MD5算法,(1)MD5简介 MD5算法是R.Rivest在MIT开发设计的散列函数，MD表示消息摘要(Message Digest)。对于输入的任意长的消息，通过MD5算法输出是128bit的0，1字符串，我们称为消息摘要，又叫散列值。算法设计的目标：安全性 直接安全性 速度 简单性和紧凑性 有利于微处理器运行,MD5算法,(2)MD5算法描述初始化(1)首先填充消息m使其长度比特数b满足 b448 mod 512即补充上去的比特，使之m的长度比512的倍数仅少64bit。补充的比特除第一位是1外，后面全是0。(2)在(1)的基础上，再附上64bit表示原来消息的真实长度(比特数)，这样消息总长度恰好是512的整数倍。(3)将前面处理后的消息划成长度为512bit的分组,总共L个512bit分组。每个分组又划分为16个长度为32bit的子分组(4)四个32bit的变量初始化为 A=Ox01234567 B=0 x89abcdef C=0 xfedcba98 D=0 x76543210,MD5算法,主循环次数主循环的次数是消息m按512bit划分后的分组数。由图可知，MD5的每次输入，除了512bit分组外，还需要上一次循环所得的128bit的散列值。,Y0,Yk,Y1,YL-1,MD5,MD5,MD5,MD5,512,512,512,512,128,128,128,128,IV,MD5算法,主循环 在算法主循环中，将A，B，C，D复制到另外的四个变量a，b，c，d中。主循环总共四轮，每一轮的结构非常相似。每一轮进行16次操作。每次操作对a，b，c，d中的其中三个数作一个非线性运算，然后所得结果加上第四个变量，分组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,第四轮II,ABCD,消息分组,MD5算法,逻辑函数 这四轮中每轮各有一个逻辑函数，分别用FF,GG,HH,II来表示，具体如下：FF(a,b,c,d,Mj,s,ti)表示a=b+(a+F(b,c,d)+Mj+ti)s)GG(a,b,c,d,Mj,s,ti)表示a=b+(a+G(b,c,d)+Mj+ti)s)HH(a,b,c,d,Mj,s,ti)表示a=b+(a+H(b,c,d)+Mj+ti)s)II(a,b,c,d,Mj,s,ti)表示a=b+(a+I(b,c,d)+Mj+ti)s)Mj表示分组的第j个子分组(j从0到15),s 表示循环左移s位，ti是常数。,MD5算法,逻辑函数 四个逻辑函数的执行过程的示意图如下：,a,b,d,c,非线性函数,s,Mj,ti,MD5算法,逻辑函数中的非线性函数,逻辑函数中的ti是随机的32位整数,SHA算法,SHA算法是美国标准与技术国家研究所(NIST)和NSA共同开发设计的，作为美国信息压缩的标准，与数字签名标准DSS一起使用。SHA对输入长度小于264 bit的消息，产生160bit的hash值。,SHA算法描述,初始化(1)与MD5一样，首先将消息填充为512bit的整数倍。填充方法与MD5完全一样，先添加一个1，然后填充尽量多的0使其长度是512的倍数刚好减去64bit，最后64bit表示消息填充前的长度。(2)初始5个32bit的变量 A=0 x67452301 B=0 xefcdab89 C=0 x98badcfe D=0 x10325476 E=0 xc3d2e1f0 前四个值和MD5相同，但A，B，C，D，E的存储采用Big_Endian模式，即最高字节放在最低位地址。,SHA算法描述,主循环(1)循环次数：与MD5一样，每次循环处理512bit的消息分组，循环次数是512bit分组的个数。(2)变量复制 A-a B-b C-c D-d E-e(3)主循环过程 主循环有4轮，每轮有20次操作（MD5也是四轮，但每轮只有16次操作）。每次操作对a，b，c，d和e中的三个变量进行一次非线性运算，然后进行与MD5类似的移位运算和加运算。,SHA算法描述,对于512bit的消息分组分成32bit的子分组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 重新赋值,求解：令Pm为m个人在一起，不存在相同生日的概率。根据设定(m-1)个人中无相同生日的概率为Pm-1，第m个人与其他(m-1)个人无相同生日的概率是 P0=365-(m-1)/365=(366-m)/365故有递推关系 Pm=P0*Pm-1=,生日问题和生日攻击,I型生日问题:有多少人在一起，至少有1/2的概率存在两个人有相同的生日？,生日问题和生日攻击,当m23时，Pm1/2,即23个人在一起时，没有两个人具有相同生日的概率小于1/2，即有相同生日的概率大于1/2。,生日问题和生日攻击,II型生日问题 已知某人A的生日日期，问有多少人在一起时，至少有1/2的概率使得其中一人和A的生日相同？假定所有人的生日都均匀分布于一年的365天。,生日问题和生日攻击,求解：一个人和A有相同生日的概率是1/365，有不同生日的概率则为(1-1/365)=364/365，那么k个人与A生日都不同的概率为：,K个人中至少有一人与A的生日相同的概率是：当k253时，P1/2。即在253人中至少有一人与A的生日相同的概率大于1/2。,生日问题和生日攻击,对单向散列函数的生日攻击 与生日问题类似，若一文件m的H(m)为32bit。问有多少文件放在一起，其中有两个文件的H(m)值相同的概率大于1/2。类比 可能的birthday=365 可能的H(m)值=232设Pm是m个长度为32bit的散列值串不存在两个相等的概率若Pm217 即m217 时有两个相同H(m)串的概率大于1/2。,Fiat-Shamir签名方案,FS方案的密钥选择:CA给每个用户产生公开密钥和私人密钥 n=p*q p和q是两个大素数 公开密钥：v1,v2,.,vk 0vin 私人密钥：s1,s2,sk 上述密钥满足：,2 A计算由消息m连接xj的Hash函数值H(mxj)对每一个散列值取前面kbit,得eij,i=1,2,k,j=1,2,t 3 A计算 A送给B的关于m的签名是xj和eij,Fiat-Shamir签名方案,签名过程 1 A取t个小于n的随机整数 r1,r2,rt,A计算,Fiat-Shamir签名方案,鉴别过程 B收到(m,yj,eij)后 1 B利用A的公钥计算 2 B计算收到消息m连接zj的Hash函数值H(m zj)取前面k比特,得e*ij i=1,2,k,j=1,2,t 3 B比较e*ij=？eij 若等式全部成立，则通过认证B接受消息m，否则拒绝接受消息m。即m可能不是A发出的，可能在中途被篡改。,Fiat-Shamir签名方案,小结:1 Hash函数2 MD5算法3 安全散列算法4 生日问题和生日攻击5 Fiat-Shamir签名方案,
