深入理解SHA系列加密算法

原创
2018/08/26 22:15
阅读数 374

介绍

SHA是一系列的加密算法,有SHA-1、SHA-2、SHA-3三大类,而SHA-1已经被破解,SHA-3应用较少,目前应用广泛相对安全的是SHA-2算法,这也是本篇文章重点讲述的算法。

 

算法核心思想和特点

该算法的思想是接收一段明文,然后以一种不可逆的方式将它转换成一段密文,也可以简单的理解为取一串输入码,并把它们转化为长度较短、位数固定的输出序列即散列值的过程。

 

单向性

单向散列函数的安全性在于其产生散列值的操作过程具有较强的单向性。如果在输入序列中嵌入密码,那么任何人在不知道密码的情况下都不能产生正确的散列值,从而保证了其安全性。SHA将输入流按照每块512位进行分块,并产生160位的被称为信息认证代码或信息摘要的输出。

 

 

数字签名

通过散列算法可实现数字签名,数字签名的原理是将要传送的明文通过一种函数运算(Hash)转换成报文摘要,报文摘要加密后与明文一起传送给接受方,接受方将接受的明文产生新的报文摘要与发送方的发来报文摘要比较,比较结果一致表示明文未被改动,如果不一致表示明文已被篡改。

 

 

什么是碰撞

哈希算法的一个重要功能是产生独特的散列,当两个不同的值或文件可以产生相同的散列,则称碰撞。保证数字签名的安全性,就是在不发生碰撞时才行。碰撞对于哈希算法来说是极其危险的,因为碰撞允许两个文件产生相同的签名。当计算机检查签名时,即使该文件未真正签署,也会被计算机识别为有效的。

一个哈希位有0和1两个可能值。则每一个独立的哈希值通过位的可能值的数量对于SHA-256,有2的256次方种组合,这是一个庞大的数值。哈希值越大,碰撞的机率就越小。每个散列算法,包括安全算法,都会发生碰撞。而SHA-1的大小结构发生碰撞的机率比较大,所以SHA-1被认为是不安全的。

 

 

SHA256算法原理解析

上篇文章介绍了MD5的算法,和SHA有相似的地方,主流程分三大模块:常量的初始化、信息预处理、使用到的逻辑运算。

 

常量的初始化:

这些常量的作用是和数据源进行计算,增加数据的加密性,那么同学可以想一下,如果常量是一些如:1,2,3之类的整数,是不是就没什么加密可言了,所以需要这些常量很复杂,生成的规则是:对自然数中前8个(或64个)质数(2,3,5,7,11,13,17,19)的平方根的小数部分取前32bit。(在后面的映射的过程中会用到这些常量)

例如:,2的平方根的小数部分约为0.414213562373095048,然后0.414213562373095048≈6∗16^−1+a∗16^−2+0∗16^−3+...

所以2的平方根的小数部分取前32bit就得到:0x6a09e667

 

SHA256中用到两种常量:

  1. 8个哈希初值=>自然数中前8个质数(2,3,5,7,11,13,17,19)的平方根的小数部分取前32bit :

h0 := 0x6a09e667 h1 := 0xbb67ae85 h2 := 0x3c6ef372 h3 := 0xa54ff53a h4 := 0x510e527f h5 := 0x9b05688c h6 := 0x1f83d9ab h7 := 0x5be0cd19

  1. 64个哈希常量=>自然数中前64个质数(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97…)的立方根的小数部分取前32bit :

428a2f98 71374491 b5c0fbcf e9b5dba5 3956c25b 59f111f1 923f82a4 ab1c5ed5 d807aa98 12835b01 243185be 550c7dc3 72be5d74 80deb1fe 9bdc06a7 c19bf174 e49b69c1 efbe4786 0fc19dc6 240ca1cc 2de92c6f 4a7484aa 5cb0a9dc 76f988da 983e5152 a831c66d b00327c8 bf597fc7 c6e00bf3 d5a79147 06ca6351 14292967 27b70a85 2e1b2138 4d2c6dfc 53380d13 650a7354 766a0abb 81c2c92e 92722c85 a2bfe8a1 a81a664b c24b8b70 c76c51a3 d192e819 d6990624 f40e3585 106aa070 19a4c116 1e376c08 2748774c 34b0bcb5 391c0cb3 4ed8aa4a 5b9cca4f 682e6ff3 748f82ee 78a5636f 84c87814 8cc70208 90befffa a4506ceb bef9a3f7 c67178f2

 

 

信息预处理:

预处理分两部分,第一部分是附加填充比特,第二部分是附加长度。目的是让整个消息满足指定的结构,从而处理起来可以统一化,格式化,这个也是计算机的基本思维方式,就是把复杂的数据转化为特定的格式,化繁为简,“去伪存真”。

 

附加填充比特

在报文末尾进行填充,使报文长度在对512取模以后的余数是448。具体是:先补第一个比特为1,然后都补0,直到长度满足对512取模后余数是448。需要注意即使长度已经满足对512取模后余数是448,补位也必须要进行,这时要填充512个比特。所以,填充是至少补一位,最多补512位。例如:“abc”补位的过程。

  1. a,b,c对应的ASCII码分别是97,98,99,
  2. 对应的二进制编码为:01100001 01100010 01100011;
  3. 首先补一个“1” : 0110000101100010 01100011 1;
  4. 然后补423个“0”:01100001 01100010 01100011 10000000 00000000 … 00000000;
  5. 补位完成后的数据如下:

61626380 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

 

附加长度值

是将原始数据的长度信息补到已经进行了填充操作的消息后面(就是第一步预处理后的信息),SHA256用一个64位的数据来表示原始消息的长度。所以SHA256加密的原始信息长度最大是2^64。

用上面的消息“abc”来操作,3个字符,占用24个bit,在进行了补长度的操作以后,整个消息就变成:

61626380 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000018

 

 

逻辑运算

 

∧ => 按位“与”

¬ => 按位“补”

⊕ => 按位“异或”

Sn => 右移n个bit

Rn => 循环右移n个bit

 

 

核心算法

准备工作做好了,下面开始进入算法阶段。

数据分解:将原始数据分解成512-bit大小的块,例如消息M可以被分解为n个块,于是整个算法需要做的就是完成n次迭代,n次迭代的结果就是最终的哈希值,即256bit的数字摘要。

每次迭代进行的映射用Map(Hi−1)=Hi表示,摘要的初始值H0,经过第一个映射后,得到H1,即完成了第一次迭代,H1经过第二次映射得到H2,……,依次处理,最后得到Hn,Hn即为最终的256-bit消息摘要。

 

在SHA256算法中的最小运算单元称为“字”(Word),一个字是32位(byte),就是4个字节(bit),256个字节(bit)就是64个字(word)。

 

映射 Map(Hi−1)=Hi 包含了64次加密循环,即进行64次加密循环即可完成一次迭代,通过维基百科上的流程图来看更直观一些:

说明:

  1. 深蓝色方块是事先定义好的非线性函数,里面是逻辑运算。
  2. ABCDEFGH一开始分别是八个初始值,就是预处理中第一部分的8个常量。
  3. Kt是第t个密钥,密钥从预处理中第二部分64个常量里取。
  4. Wt是本区块产生第t个word

原消息被切成固定长度的区块,对每一个区块,产生n个word,透过重复运作循环n次对ABCDEFGH这八个工作区块循环加密。最后一次循环所产生的八段字符串合起来即是此区块对应到的散列字符串。若原消息包含数个区块,则最后还要将这些区块产生的散列字符串加以混合才能产生最后的散列字符串。

 

总结

本文介绍了SHA256算法的基本组成和算法原理,主流程分三大模块:常量的初始化、信息预处理、使用到的逻辑运算;核心算法分两步:拆分原数据,循环加密。

 

如果对密码学感兴趣的同学,可以订阅我的课程 https://gitbook.cn/gitchat/column/5b6c49d99f4dd1284bf83bda

或者扫描二维码:

 

 

 

参考文献:

https://zh.wikipedia.org/wiki/SHA-1

https://zh.wikipedia.org/wiki/SHA-2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部