SHA256算法介绍

扒一扒密码学的前世今生

二战结束以后，密码学在相当长的一段时间内都像军火一样被各国政府严密看管。美国国家安全局（NSA）雇佣了一大批密码学家在五角大楼内研究最前沿的密码学，严令禁止技术出口及民用。

1972年，IBM研制出了对称密码体制加密算法。

1975年美国国家标准局将对称密码体制加密算法颁布为国家标准，称为数据加密标准DES。DES的公布，也促使了大量封禁已久的密码学著作流入民间。

1976年，W.Diffie和M.Hellman发表了《密码学的新方向》一文，文中首次提出了适应网络保密通信需求的公钥密码思想，掀起了公钥密码学的序幕。

次年，美国的Ronald Rivest、Adi Shamir和Len Adleman提出了第一个建立在大数因子分解基础上的公钥密码算法，即著名的RSA算法。

为了寻找破解RSA的方法，1985年，英国牛津大学物理学家David Deutsch提出了量子计算机的初步设想。

同年,美国科学家 Bennet 根据关于量子密码学的协议，在实验室首次实现了量子密码加密信息的通信。尽管通信距离只有30厘米，但已经足以证明量子加密的可用性。

同样是这一年，Victor Miller和Neal Koblitz分别提出了如今家喻户晓的椭圆曲线密码学（ECC）。使用ECC加密的256位密钥所提供的安全性，与使用RSA或DSA加密的3072位密钥相当。这意味着ECC算法所要求的带宽更低、存储空间更小。

步入90年代初，麻省理工学院教授Ronald Rivest提出了MD4信息摘要算法，它是一种用来测试信息完整性的哈希函数。MD4的实现，旋即开启了哈希函数的大门，包括后来Ronald Rivest重新提出的安全性更优的MD5，由NSA和NIST提出的SHA函数家族以及Hans Dobbertin,Antoon Bosselaers 和 Bart Prenee提出的RIPEMD。在这一时期，密码学家来学嘉和JamesMasseey还提出了在软硬件实现上比DES更优的国际数据加密算法，即IDEA。

随着计算机能力的不断提高，不少密码体系比如主流的DES正逐步面临淘汰。1998年，电子边境基金会（EFF）利用耗资25万美元打造的专用计算机，仅用56个小时就成功破解了DES密钥。随后在1999年，EFF仅用了22小时15分就完成了破解工作。此后，美国国家安全局宣布弃用DES，转而启用由比利时密码学家Joan Daemen和Vincent Rijmen所提出的Rijndael加密算法，即高级加密标准AES。

进入千禧年以后，MD4、MD5、RIPEMD（RIPEMD-160仍然安全）、SHA1以及RSA-768的强抗碰撞性相继被攻破，RSA-1024业已在2012年前后被停用。随着区块链技术的兴起，ECC俨然成为密码学殿堂最亮眼的新星，但依旧难逃量子计算技术的威胁。

SM2算法全称为SM2椭圆曲线公钥密码算法,是国家密码管理局2010年12月发布的第21号公告中公布的密码行业标准。SM2算法属于非对称密钥算法,使用公钥进行加密,私钥进行解密,已知公钥求私钥在计算上不可行。发送者用接收者的公钥将消息加密成密文,接收者用自已的私钥对收到的密文进行解密还原成原始消息。

SM2算法相比较其他非对称公钥算法如RSA而言使用更短的密钥串就能实现比较牢固的加密强度,同时由于其良好的数学设计结构,加密速度也比RSA算法快。

SM4算法全称为SM4分组密码算法,是国家密码管理局2012年3月发布的第23号公告中公布的密码行业标准。SM4算法是一个分组对称密钥算法,明文、密钥、密文都是16字节,加密和解密密钥相同。加密算法与密钥扩展算法都采用32轮非线性迭代结构。解密过程与加密过程的结构相似,只是轮密钥的使用顺序相反。

SHA256的家族史

SHA0函数是由NIST设计并于1993年发表，发布之后很快被破解（天灰灰累不累），1995年发表了SHA1，but，SHA-1和SHA-0的算法只在压缩函数的讯息转换部分差了一个位元的循环位移，他们可将一个最大2的64次方位元的讯息，转换成一串160位元的讯息摘要；其设计原理相似于MIT教授Ronald L. Rivest所设计的密码学杂凑算法MD4和MD5，然鹅相继被攻破。

So，NIST发布了SHA的其他三个变体，256/384/512，这三个函数都将讯息对应到更长的讯息摘要。2004年2月，发布了一次FIPS PUB 180-2的变更通知，加入了一个额外的变种SHA-224″，这是为了符合双金钥3DES所需的金钥长度而定义。这些算法标准的区别除了生成摘要的长度，循环运行次数等有一些微小的差异之外，基本结构大致相同。

散列函数是把消息压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫散列值的指纹。

散列值通常用一个短的随机字母和数字组成的字符串代表。

对于任意长度的消息，SHA256都会产生一个256bit长度的散列值，称为消息摘要，可以用一个长度为64的十六进制字符串表示。

Download file – your conversion was successful (online-convert.com) 在线测试区

SHA256算法流程

信息预处理


1、填充比特

在报文末尾进行填充，使报文长度= 448 （mod 512），规则为先补第一个比特为1，然后都补0

若长度刚好为448也必须填充，此时需要增加512位，即填充的位数[1，512]

2、附加长度值

附加长度值就是将原始数据的长度信息（无符号整数64bit）附加到已经填充消息的后面。

前两个附加长度就构成了一个长度为512整数倍的消息结构。

3、初始化数据

SHA256中用到了8个散列初始值

h0 := 0x6a09e667            h1 := 0xbb67ae85

h2 := 0x3c6ef372             h3 := 0xa54ff53a

h4 := 0x510e527f             h5 := 0x9b05688c

h6 := 0x1f83d9ab             h7 := 0x5be0cd19

这些初值是对自然数中前8个质数（2,3,5,7,11,13,17,19）的平方根的小数部分取前32bit而来

根号2 = 0.414213562373095048 = 6*16^-1+a*16^-2+0*16^-3+……

于是，质数2的平方根的小数部分取前32bit就对应出了0x6a09e667

64个常量如下：

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

这些常量是对自然数中前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而来。

SHA256算法流程步骤呐

将消息M分解成n个512-bit大小的块

一个256-bit的摘要的初始值H₀，经过第一个数据块进行运算，得到H₁，即完成了第一次迭代H₁经过第二个数据块得到H₂，……，依次处理，最后得到H_n。H_i是第i个消息分组处理的最后一轮的输出。

H₀[8]=[h₀,h₁,h₂,h₃,h₄,h₅,h₆,h₇]。H_i被描述8个小块，这是因为SHA256算法中的最小运算单元称为“字”（Word），一个字是32位。

1）构造64个字，对于每一个512bit的块，将其分解为16个32bit的（big-endian）字，记为w[0],w[1],……,w[15]

其余的字由如下迭代公式得到：W_t = σ₁( W _{t − 2} ) + W _{t − 7} + σ ₀ ( W _{t − 15} ) + W _{t − 16} 

2）进行64次加密循环，H_i按照一定规则不断更新

参考：大话密码学史：过去、现在和未来 – 知乎 (zhihu.com)

           密码发展史之近现代密码_国家密码管理局门户 (sca.gov.cn)

           (17条消息) SHA256算法原理详解_随煜而安的专栏-CSDN博客_sha256

            SHA算法 – block2016 – 博客园 (cnblogs.com)

补充SHA512的算法介绍，因和SHA256很相似，所以简单改改256的。

信息预处理


1、填充比特

在报文末尾进行填充，使报文长度= 896 （mod 1024），规则为先补第一个比特为1，然后都补0

若长度刚好为896也必须填充，此时需要增加1024位，即填充的位数[1，1024]

 

2、附加长度值

附加长度值就是将原始数据的长度信息（无符号整数128bit）附加到已经填充消息的后面。

前两个附加长度就构成了一个长度为1024整数倍的消息结构。

3、初始化数据

SHA256中用到了8个散列初始值

h0 := 0x6a09e667f3bcc908             h1 := 0xbb67ae8584caa73b

h2 := 0x3c6ef372fe94f82b               h3 := 0xa54ff53a5f1d36f1

h4 := 0x510e527fade682d1             h5 := 0x9b05688c2b3e6c1f

h6 := 0x1f83d9abfb41bd6b              h7 := 0x5be0cd19137e2179

这些初值是对自然数中前8个质数（2,3,5,7,11,13,17,19）的平方根的小数部分取前64bit而来

根号2 = 0.414213562373095048 = 6*16^-1+a*16^-2+0*16^-3+……

于是，质数2的平方根的小数部分取前32bit就对应出了0x6a09e667f3bcc908 

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…)的立方根的小数部分取前64bit而来。

SHA512算法流程步骤呐

将消息M分解成n个1024-bit大小的块

一个512-bit的摘要的初始值H₀，经过第一个数据块进行运算，得到H₁，即完成了第一次迭代H₁经过第二个数据块得到H₂，……，依次处理，最后得到H_n。H_i是第i个消息分组处理的最后一轮的输出。

H₀[8]=[h₀,h₁,h₂,h₃,h₄,h₅,h₆,h₇]。H_i被描述8个小块，这是因为SHA512算法中的最小运算单元称为“字”（Word），一个字是64位。

1）构造64个字，对于每一个1024bit的块，将其分解为16个64bit的（big-endian）字，记为w[0],w[1],……,w[15]

其余的字由如下迭代公式得到：W_t = σ₁( W _{t − 2} ) + W _{t − 7} + σ ₀ ( W _{t − 15} ) + W _{t − 16} 

σ₁（x）=R¹（x）⊕R⁸（x）⊕S⁷（x）

σ₀（x）=R¹⁹（x）⊕R⁶¹（x）⊕S⁶（x）

Rⁿ（x）对变量x循环右移nbit

Sⁿ（x）对变量x左移nbit，右边填充0

2）进行80次轮函数循环，H_i按照一定规则不断更新

H_i=H_i-1+F(H_i-1,M_i)

其中F为轮函数，轮函数要进行80轮运算