《应用密码学-Python版》课件 第3章 哈希算法概述

《应用密码学—Python版》第三章哈希算法概述课程背景

哈希算法也叫Hash函数、散列函数、哈希函数、杂凑函数，通常记为H，用于将任意长的消息M映射为较短的、固定长度的一个值作为认证符，记为哈希值H(M)。哈希函数是一种单向密码体制，即它是一个从明文到密文的不可逆映射，只有加密过程，不能解密。目录contents01哈希算法基础02常用哈希算法MD503哈希算法应用哈希算法基础3.11.哈希算法基础基本概念哈希函数H是一个公开函数，不需要密钥，用于将任意长的消息M映射为较短的、固定长度的值H(M)。哈希函数的操作过程：输入首先被填充到某个固定长度（如1024位）的整数倍，填充的内容包括原始信息的长度信息。哈希函数的操作过程1.哈希算法基础哈希函数的安全要求输入长度可变：H适用于任意长度的数据分组输出长度固定：H生成一个定长的输出，数据压缩功能效率：给定消息M，可计算H(M)抗原像攻击（单向性）：给定H(M)，不可计算M抗第二原像攻击（抗弱碰撞性）：给定M及H(M)，要找到另一个M不同且哈希值相同的M'是不可能的抗碰撞攻击（抗强碰撞性）：对于任意两个不同的M和M'，它们的哈希值不可能相同伪随机性：H的输出满足伪随机性测试标准1.哈希算法基础哈希函数性质之间的关系满足前5条性质被称为弱哈希函数或称哈希函数为弱无碰撞的；还满足第6条性质，那么就称为强哈希函数，或称哈希函数为强碰撞的。哈希函数性质关系图抗强碰撞攻击

抗弱碰撞攻击抗强碰撞攻击

抗原像攻击抗弱碰撞攻击

抗原像攻击1.哈希算法基础分类MD系列：单向哈希函数，将任意长度输入转化为固定长度的报文摘要，具有单向不可逆、唯一性常见：MD2、MD4、MD5SHA系列：能将任意长度的输入数据转换为固定长度的哈希值，用于产生消息摘要，保障数据完整性常见：SHA-1、SHA-2其他哈希算法：BLAKE2、RIPEMD、Whirlpool、Skein1.哈希算法基础哈希函数为每个消息产生独一无二的哈希值，并且这个过程是不可逆的。哈希值是一种将任意长度的输入数据（称为消息或明文）映射为固定长度的输出数据（称为哈希值或密文）的函数，通常用一个短的随机字母和数字组成的字符串来表示。计算哈希值（消息摘要）的过程1.哈希算法基础哈希值特性确定性：使用同一哈希函数计算，得到的哈希值必然相同；唯一性：每个不同的数据都对应唯一的哈希值；单向性：从哈希值反向推导出原始数据是不可能的；敏感性：输入数据不同，得到的哈希值一定不同。生成选择哈希算法处理输入数据计算哈希值验证获取原始哈希值和待验证数据重新计算哈希值比较哈希值常用哈希算法MD53.22.常用哈希算法MD5MD5算法是由RSA的创始人Rivest设计开发的，能接收任意长度的消息作为输入，并生成128比特散列值。MD5散列算法总体结构共有两组输入：512比特明文分块、上一组128比特的输出块（或IV初始变量）。输入的128比特分别存储在四个缓存：A、B、C、D，每个分块总共四个步骤，每步骤计算16次，合计64轮次。2.常用哈希算法MD5MD5散列函数的具体逻辑MD5散列算法详细结构填充消息填充之后消息的长度满足模512为448bit。如果数据长度是模448bit，则增加512bit填充位，也就是说填充的个数至少为1个512bit。填充方法：第一个比特位为1，其余全部为0。补零的个数d=(447-|x|)mod512（|x|为原始消息长度值）。2.常用哈希算法MD5例3.1：（1）原始消息由704bit二进制组成，那么在其末尾添加256bit(255≡(447−704)mod512，即1个“1”后面255个“0”)，消息扩展到960bit(960mod512=448)。（2）原始消息由448bit二进制组成，那么末尾添加512bit(512≡(447−448)mod512，即1个“1”后面511个“0”)，消息扩展到960bit(960mod512=448)。2.常用哈希算法MD5补足长度在填充的消息的末尾添加64bit的块，该64bit是原始消息长度（二进制位表示）。如果长度超过64bit所能表示的数据长度的范围，则仅取最低64bit，即mod264，增加到前面填充的数据后面，使得最后的数据为512bit的整数倍。到此为止，经过填充数据和补足长度两步操作，可得到一个512bit的整数倍长度的新的消息。可以表示为L个512比特的数据块：其长度为L×512bit。令N=L×16，则长度为N个32bit的字。令M[0…N-1]表示以字为单位的消息。2.常用哈希算法MD5例3.2：原始消息长度由704bit二进制组成，则长度704变换为二进制为1011000000，则需要在左边补54个0，达到64bit，并把它添加到消息的末尾，其结果是最后原始消息扩充到一个1024bit的消息。MD5算法中，无论原始消息多长，补足长度之后的消息扩展为至少2个分组，即扩展后消息块的长度至少是512bit的2倍。2.常用哈希算法MD5初始化变量初始化MD缓冲区：128bit的MD缓冲区用以保存中间和最终哈希函数的结果。它可以表示为4个32bit的寄存器(A、B、C、D)。寄存器初始化为以下的十六进制值：A=67452301；B=EFCDAB89；C=98BADCFE；D=10325476。2.常用哈希算法MD5数据处理每个消息块可分为16个字，记为M[0]，M[1]，…，M[15]。在MD5算法中四轮循环，每一轮访问数据的次序有所变动。MD5每轮访问消息处理块的次序如下：第一轮：M[0]为初始值，依次访问下标k等于加1模16的值第二轮：M[1]为初始值，依次访问下标k等于加5模16的值第三轮：M[5]为初始值，依次访问下标k等于加3模16的值第四轮：M[0]为初始值，依次访问下标k等于加7模16的值2.常用哈希算法MD5每个512bit消息块和MD5初始变量IV作为初始输入，进入四轮循环。MD5单个512bit分组包括4轮处理，4轮处理结构相似，但每次使用不同的基本逻辑函数，记为F，G，H，I。每一轮以当前的512bit数据块(Pq)和128bit缓冲值ABCD作为输入，修改缓冲值内容。输出结果所有L个512bit数据块处理完毕后，最后的结果就是128bit的哈希值。2.常用哈希算法MD5每次使用64元素表T[1…64]中的一个。T表由sin函数构造，第i个元素（i是弧度），T的每个元素是32比特整数。计算t[1]：x=sin(1)=0.8414709848078965066525023216303y=232=4294967296z=x*y=232*sin(1)=3614090360.288283386251439079649int(z)=3614090360=0xD76AA4782.常用哈希算法MD5T[1]=0xd76aa478T[17]=0xf61e2562T[33]=0xfffa3942T[49]=0xf4292244T[2]=0xe8c7b756T[18]=0xc040b340T[34]=0x8771f681T[50]=0x432aff97T[3]=0x242070dbT[19]=0x265e5a51T[35]=0x6a9d6122T[51]=0xab9423a7T[4]=0xc1bdceeeT[20]=0xe9b6c7aaT[36]=0xfde5380cT[52]=0xfc93a039T[5]=0xf57c0fafT[21]=0xd62f105dT[37]=0xa4beea44T[53]=0x655b59c3T[6]=0x4787c62aT[22]=0x02441453T[38]=0x4bdecfa9T[54]=0x8f0ccc92T[7]=0xa8304613T[23]=0xd8a1e681T[39]=0xf6bb4b60T[55]=0xffeff47dT[8]=0xfd469501T[24]=0xe7d3fbc8T[40]=0xbebfbc70T[56]=0x85845dd1T[9]=0x698098d8T[25]=0x21e1cde6T[41]=0x289b7ec6T[57]=0x6fa87e4fT[10]=0x8b44f7afT[26]=0xc33707d6T[42]=0xeaa127faT[58]=0xfe2ce6e0T[11]=0xffff5bb1T[27]=0xf4d50d87T[43]=0xd4ef3085T[59]=0xa30143314T[12]=0x895cd7beT[28]=0x455a14edT[44]=0x04881d05T[60]=0x4e0811a1T[13]=0x6b901122T[29]=0xa9e3e905T[45]=0xd9d4d039T[61]=0xf7537e82T[14]=0xfd987193T[30]=0xfcefa3f8T[46]=0xe6db99e5T[62]=0xbd3af235T[15]=0xa679438eT[31]=0x676f02d9T[47]=0x1fa27cf8T[63]=0x2ad7d2bbT[16]=0x49b40821T[32]=0x8d2a4c8aT[48]=0xc4ac5665T[64]=0xeb86d391T数值中的MD5常量值2.常用哈希算法MD5MD5压缩函数压缩函数是MD5算法的核心，它是处理一个512bit分组的四次循环中每一循环的逻辑结构。每一轮包含对缓冲区ABCD的16回合操作所组成的一个序列。T数值中的MD5常量值2.常用哈希算法MD5A、B、C、D为缓冲区的四个字，以一个给定的次序排列；g为基本逻辑函数F、G、H、I之一；<<<s为对32位字循环左移s位；M[k]为在512比特数据块中的第k个32位字；T[i]为表T中的第i个32位字；＋表示模2³²的加。（1）每个回合缓冲区A、B、C、D的计算为：A=DB=B＋((A＋g(B，C，D)＋M[k]＋T[i])<<<s)C=BD=C2.常用哈希算法MD5（2）每个回合的基本逻辑函数g(b，c，d)如下定义：F(B,C,D)=(B∧C)∨(¬B∧D)G(B,C,D)=(B∧D)∨(C∧¬D)H(B,C,D)=B⊕C⊕DI(B,C,D)=C⊕(B∨¬D)（3）在MD5中循环移位s位在轮与轮之间和回合与回合之间是变化的，每一回合的每一轮的循环移位如表所示。2.常用哈希算法MD5轮次回

合12345678910111213141516171217227121722712172271217222591420591420591420591420348162348162348162348162345101521610152161015216101521MD5中位数循环移位量2.常用哈希算法MD5MD5安全性分析与现状碰撞攻击：在理想情况下，哈希函数应该具有很强的抗碰撞性。然而，已有研究人员成功地找到了MD5的碰撞实例。伪造签名：攻击者可以找到两个内容不同但MD5哈希值相同的文件，然后用合法文件的签名来替代恶意文件的签名，从而绕过签名验证机制，达到欺骗目的。彩虹表攻击：彩虹表是一种用于破解哈希密码的技术，它是一个预先计算好的哈希值和对应的原始数据的对照表。攻击者可以利用彩虹表来快速查找与给定MD5哈希值对应的原始数据，从而破解密码。哈希算法应用3.33.哈希算法应用数学签名发送方：首先对发送文件采用哈希算法，得到一个固定长度的消息摘要，再用自己的私钥对消息摘要进行签名，形成发送方的数字签名，数字签名将作为附件和原文一起发送给接收方；接收方：首先用发送方的公钥对数字签名进行解密得到发送方的数字摘要，然后用相同的哈希函数对原文进行哈希计算，得到一个新的消息摘要，最后将摘要与收到的消息摘要做比较。3.哈希算法应用基于哈希函数的数字签名，其优点：（1）对哈希值进行签名可以取得更短的签名，节省存储空间与传输带宽，加快处理速度；（2）计算上更快，降低资源消耗