实验六 SHA-1算法+MD5算法+哈希碰撞

Author Avatar
Euan 11月 18, 2019
  • 在其它设备中阅读本文章

实验六 SHA-1算法+MD5算法+哈希碰撞

SHA-1算法+MD5算法

SHA-1算法

【实验目的】

1） 学习SHA-1密码算法的原理
2） 学习SHA-1密码算法的编程实现

【实验原理】

算法原理
安全散列算法（SHA，Secure Hash Algorithm）是一种常用的数据加密算法，1993年美国国家标准技术研究所（NIST）公布了SHA-0作为联邦信息处理标准，1995年4月17日公布了安全性更高的改进版本SHA-1。SHA-1在设计上很大程度模仿MD4，该算法对长度不超过264的消息产生160 bit的消息摘要输出，输入消息以512 bit分组为单位处理。
SHA-1有5个参与运算的32位寄存器字，消息分组和填充方式与MD5相同，主循环也同样是4轮，但每轮进行20词操作，非线性运算、移位和加法运算与MD5类似，但非线性函数、加法常数和循环左移操作的设计有一些区别。
1）附加填充位
填充一个“1”和若干个“0”使其长度模512与448同余，然后在消息后附加64 bit的无符号整数，其值为原始消息的长度。产生长度为512整数倍的消息串，把消息分成长度为512 bit的消息块M1,M2,…, MN因此填充后的消息程度为512Nbit。
2）初始化链接变量
和MD5相似，将5个32 bit 的固定值赋予5个32位的寄存器（A，B，C，D，E）作为第一次迭代的链接变量输入如表1：

3）以512 bit 分组处理消息
此算法的核心就是称为压缩函数（compression function）的模块，这个模块包括4次循环，每次循环又包含20个处理步骤。每个循环使用的步函数相同，不同的循环中步函数包含不同的非线性函数（Ch、Parity、Maj、Parity），每一步函数的输入也不同，除了寄存器外，还有额外函数Ki和消息分组相关的Wi（0≤i≤79）。
4）输出散列值
每一次循环以当前正在处理的512 bit 和160bit的缓存值A、B、C、D、E为输入，然后更新缓存的内容。最后一步的输出模232加上上一循环的输入CVj产生CVj+1。全部512 bit 数据块处理完毕后，最后输出160 bit的消息摘要。


图1 SHA-1对单个512 bit 分组的处理流程

SHA-1压缩函数
SHA-1的压缩函数是最关键的部分，其中每一步Stepi(ABCDE,Yi,Ki)的计算(i=0,2,..,79)如下图所示：


图2单轮SHA-1的运算

SHA-1压缩函数的每一循环的形式为:





其中，i是步数，（0≤i≤79）；ROTLn(x)=(x<<n)< span=""></n)<>表示对32 bit的变量x循环左移n bit。
图中非线性函数均对3个32 bit的变量B、C、D进行操作，结果是产生一个32 bit 的输出；Ki是循环中使用的额外常数，根据步数不同分别取4个不同的值。非线性函数和Ki定义如下表2：

32bit的字Wi是从512 bit 的消息分组中导出的，其映射过程如下图所示：



图3 SHA-1处理单个分组而产生的80个输入序列

在前16步中Wi值等于消息分组中的相应字，在剩余的64步中，其值是由前面的4个值相异或得到的，上述操作增加了压缩分组的冗余性和相互依赖性，故对于相同分组的消息找出具有相同压缩结果的消息是困难的。

算法流程


图4 SHA-1的算法流程图

【实验环境】

Windows Server 2012 R2
实验工具在【C:\tools\密码学课程\01密码学算法\06 hash算法\03 SHA-1算法】

【实验步骤】

1.运行程序。如图5所示


图5

2.源码如下

  1.   int main()
  2. {
  3. SHA1Context sha;
  4. int i, err;
  5. uint8_t Message_Digest[20];
  7. // testing SHA1
  8. char  *test = "信息    2013-4-10    15:59:14    b57w2k    无    11    N/A    XP-201207101943";
  10. printf( "\n测试值:\t“%s”\n",test);
  11. err = SHA1Reset(&sha);    //erro and return 0
  13. if (err)
  14. {
  15.     fprintf(stderr, "SHA1重置错误 %d.\n", err );
  16.     return 0;
  17. }
  19. err = ISD_SHA1Input(&sha, (unsigned char *)test, strlen(test));
  21. if (err)
  22. {
  23.     fprintf(stderr, "SHA1输入错误 %d.\n", err );
  24.     return 0;
  25. }
  27. err = ISD_SHA1Result(&sha, Message_Digest);
  29. if (err)
  30. {
  31.     fprintf(stderr,
  32.     "SHA1结果错误 %d, 不能计算摘要值.\n",
  33.     err );
  34. }
  35. else
  36. {
  37.     printf("摘要值:\t");
  38.     for(i = 0; i < 20 ; ++i)
  39.     {
  40.         printf("%02X ", Message_Digest[i]);
  41.     }
  42.     printf("\n");
  43. }
  45. return 0;
  46. }

【实验思考】

2.SAH-1密码算法与MD5算法有什么不同？

SHA-1是一种数据加密算法，该算法的思想是接收一段明文，然后以一种不可逆的方式将它转换成一段（通常更小）密文，也可以简单的理解为取一串输入码（称为预映射或信息），并把它们转化为长度较短、位数固定的输出序列即散列值（也称为信息摘要或信息认证代码）的过程。
单向散列函数的安全性在于其产生散列值的操作过程具有较强的单向性。如果在输入序列中嵌入密码，那么任何人在不知道密码的情况下都不能产生正确的散列值，从而保证了其安全性。SHA将输入流按照每块512位（64个字节）进行分块，并产生20个字节的被称为信息认证代码或信息摘要的输出。
该算法输入报文的长度不限，产生的输出是一个160位的报文摘要。输入是按512 位的分组进行处理的。SHA-1是不可逆的、防冲突，并具有良好的雪崩效应。
通过散列算法可实现数字签名实现，数字签名的原理是将要传送的明文通过一种函数运算（Hash）转换成报文摘要（不同的明文对应不同的报文摘要），报文摘要加密后与明文一起传送给接受方，接受方将接受的明文产生新的报文摘要与发送方的发来报文摘要解密比较，比较结果一致表示明文未被改动，如果不一致表示明文已被篡改。
MAC （信息认证代码）就是一个散列结果，其中部分输入信息是密码，只有知道这个密码的参与者才能再次计算和验证MAC码的合法性。

因为二者均由MD4导出，SHA-1和MD5彼此很相似。有以下几点不同：

  1. 对强行攻击的安全性：最显著和最重要的区别是SHA-1摘要比MD5摘要长32 位。使用强行技术，产生任何一个报文使其摘要等于给定报摘要的难度对MD5是2^128数量级的操作，而对SHA-1则是2^160数量级的操作。这样，SHA-1对强行攻击有更大的强度。
  2. 对密码分析的安全性：由于MD5的设计，易受密码分析的攻击，SHA-1显得不易受这样的攻击。
  3. 速度：在相同的硬件上，SHA-1的运行速度比MD5慢。

哈希碰撞

一开始还是一脸懵，只能上网查了。

碰撞的意思是计算得到的Hash值相同，需要放到同一个bucket中。Hashmap里面的bucket出现了单链表的形式，散列表要解决的一个问题就是散列值的冲突问题，通常是两种方法：链表法和开放地址法。

bucket 类似为存储空间

  • HashMap是一个散列桶（数组和链表），它存储的内容是键值对(key-value)映射
  • HashMap采用了数组和链表的数据结构，能在查询和修改方便继承了数组的线性查找和链表的寻址修改
  • HashMap是非synchronized，所以HashMap很快
  • HashMap可以接受null键和值，而Hashtable则不能（原因就是equlas()方法需要对象，因为HashMap是后出的API经过处理才可以）

1.开放地址法

开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)

其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1，称线性探测再散列。

如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…kk,-kk(k<=m/2)，称二次探测再散列。

如果di取值可能为伪随机数列。称伪随机探测再散列。

2.再哈希法

当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。

比如上面第一次按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突为止

3.链地址法（拉链法）

将所有关键字为同义词的记录存储在同一线性链表中。如下：

a

因此这种方法，可以近似的认为是筒子里面套筒子

4.建立一个公共溢出区

假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。

拉链法的优缺点

优点：

  • 拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
  • 由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
  • 开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
  • 在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

缺点：

指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。

本文使用 CC BY-NC-SA 3.0 中国大陆 协议许可
具体请参见 知识共享协议
本文链接：https://zyhang8.github.io/2019/11/18/cipher-exp6/