股票跟单网站开发,海林建设局网站,福建省建设法制协会网站,素材库大全高清素材免费下载SHA 算法的原理及实现 章节目录
简介算法描述 2.1 数据准备 2.1.1 数据填充 2.1.2 数据分块 2.1.3 设置初始 Hash 值 2.2 Hash 计算 2.2.1 SHA-1 2.2.2 SHA-256 2.2.3 SHA-512实现 作者能力有限, 如果您在阅读过程中发现任何错误, 还请您务必联系本人,指出错误, 避免后来读者… SHA 算法的原理及实现 章节目录
简介算法描述 2.1 数据准备 2.1.1 数据填充 2.1.2 数据分块 2.1.3 设置初始 Hash 值 2.2 Hash 计算 2.2.1 SHA-1 2.2.2 SHA-256 2.2.3 SHA-512实现 作者能力有限, 如果您在阅读过程中发现任何错误, 还请您务必联系本人,指出错误, 避免后来读者再学习错误的知识.谢谢! 简介##
SHA 算法英语Secure Hash Algorithm缩写为SHA是一个密码散列函数家族是FIPS所认证的安全散列算法。能计算出一个数字消息所对应到的长度固定的字符串又称消息摘要的算法。且若输入的消息不同它们对应到不同字符串的机率很高。
本文我们将介绍以下 SHA 算法: SHA-1, SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256.
其中 SHA-224 和 SHA-256 使用相同的算法, 区别在于初始 Hash 值不同, 最终结果只使用算法输出的数据中的前224/256 bit. SHA-384, SHA-512, SHA-512/224, SHA-512/256 使用相同的算法, 区别在于初始 Hash 值不同, 最终结果只使用算法输出的数据中的前384/512/224/256 bit. 而 SHA-2* 和 SHA-384,SHA-5* 算法也非常类似, 区别在于采用的字(Word) 长度不同, SHA-2*使用 32-bit 的字, 而 其他算法使用 64-bit 的字. 算法的迭代次数也不一样.
算法描述##
本文中将介绍的 SHA 算法的计算步骤从大体上可以分为两步: 数据准备 和 Hash 计算.
数据准备###
在数据准备阶段, 我们也像 MD5 那样, 需要先将数据填充到特定长度,同时将原始数据长度填充进去,然后对数据进行分块, 因为我们的算法是基于块进行的. SHA 家族中的具体算法的实现大体相同, 只是填充长度的bit数,分块大小略有不同而已.
在数据准备阶段我们需要进行三个操作: 数据填充, 数据分块, 设置初始 Hash 值.
数据填充####
我们使用 MMM 表示数据数据, 它的长度使用 lll 表示.
对于算法 SHA-1, SHA-224, SHA-256, 数据填充方法如下: 先填充 1 bit 的 ‘1’ 到数据末尾, 然后紧接着填充 k 个 ‘0’, 这里 k 需要时最小的非负数且满足 l1k≡448mod512l1k\equiv448mod512l1k≡448mod512, 也即是说需要将原始数据长度填充到差64位就是512的整数倍. 上述操作结束后, 将 lll 表示为 64 bit 的bit数组填充到上述步骤所得的数据之后, 此时我们得到一个长度为512整数倍的数据.
举个例子: 假设我们的数据数据为abc, 它的长度为24(bit). 我们通过计算得到 k 应该是 423(448 - 1 - 24). 此时填充之后的数据应该如下: 01100001⎵a01100010⎵b01100011⎵c100...00⏞42300...011000⎵t24⏞64\underbrace{01100001}_{a}\quad \underbrace{01100010}_{b}\quad \underbrace{01100011}_{c}\quad 1 \quad \overbrace{00...00}^{423}\quad \overbrace{00...0\underbrace{11000}_{t24}}^{64}a01100001b01100010c01100011100...0042300...0t241100064 填充完成之后的长度是512(bit).
对于算法 SHA-384, SHA-512, SHA-512/224, SHA-512/256, 数据填充方法如下: 先填充 1 bit 的 ‘1’ 到数据末尾, 然后紧接着填充 k 个 ‘0’, 这里 k 需要时最小的非负数且满足 l1k≡896mod1024l1k\equiv896mod1024l1k≡896mod1024, 也即是说需要将原始数据长度填充到差128位就是1024的整数倍. 上述操作结束后, 将 lll 表示为 128 bit 的bit数组填充到上述步骤所得的数据之后, 此时我们得到一个长度为1024整数倍的数据.
以上述的例子为例: 假设我们的数据数据为abc, 它的长度为24(bit). 我们通过计算得到 k 应该是 871(896 - 1 - 24). 此时填充之后的数据应该如下: 01100001⎵a01100010⎵b01100011⎵c100...00⏞87100...011000⎵t24⏞128\underbrace{01100001}_{a}\quad \underbrace{01100010}_{b}\quad \underbrace{01100011}_{c}\quad 1 \quad \overbrace{00...00}^{871}\quad \overbrace{00...0\underbrace{11000}_{t24}}^{128}a01100001b01100010c01100011100...0087100...0t2411000128 填充完成之后的长度是1024(bit).
数据分块####
填充后的数据需要被分块.
对于算法 SHA-1, SHA-224, SHA-256, 我们将数据分为 NNN 个 521-bit 的块, 分别表示为 M(1),M(2),...,M(N)M^{(1)}, M^{(2)}, ..., M^{(N)}M(1),M(2),...,M(N) 512-bit 的块又可以被划分为 16 个字(32-bit Word), 分别表示为 M0(i),M1(i),...,M15(i)M^{(i)}_{0}, M^{(i)}_{1}, ..., M^{(i)}_{15}M0(i),M1(i),...,M15(i)
对于算法 SHA-384, SHA-512, SHA-512/224, SHA-512/256 我们将数据分为 NNN 个 1024-bit 的块, 分别表示为 M(1),M(2),...,M(N)M^{(1)}, M^{(2)}, ..., M^{(N)}M(1),M(2),...,M(N) 1024-bit 的块又可以被划分为 16 个字(64-bit Word), 分别表示为 M0(i),M1(i),...,M15(i)M^{(i)}_{0}, M^{(i)}_{1}, ..., M^{(i)}_{15}M0(i),M1(i),...,M15(i)
设置初始 Hash 值####
每个特定的 SHA 算法, 都有相应的初始 Hash 值. 在计算 Hash 之前, 我们需要先将初始值准备好.
为了减少文章篇幅, 这里我们不列出这些初始值和 Hash 计算过程中使用到的常量KKK,后边算法实现中会给出相应数据.
Hash 计算###
SHA-1####
SHA-1 算法要求输入数据的长度不能大于 2642^64264, 最小长度为0.
伪代码如下:
ROTLn(x)(xlt;lt;n)∪(xgt;gt;w−n)ROTL^n(x)(x lt;lt; n) \cup (x gt;gt; w - n)ROTLn(x)(xn)∪(xw−n)
ft(x,y,z)f_t(x,y,z)ft(x,y,z) {Ch(x,y,z)(x∩y)⨁(¬x∩z),0≤t≤19Parity(x,y,z)x⨁y⨁z,20≤t≤39Maj(x,y,z)(x∩y)⨁(x∩z)⨁(y∩z),40≤t≤59Parity(x,y,z)x⨁y⨁z,60≤t≤79\begin{cases} Ch(x,y,z)(x\cap y)\bigoplus (¬x\cap z), \qquad 0\leq t\leq19\\ \quad \\ Parity(x,y,z)x\bigoplus y\bigoplus z, \qquad 20\leq t\leq39\\ \quad \\ Maj(x,y,z)(x\cap y)\bigoplus (x\cap z)\bigoplus (y\cap z), \qquad 40\leq t\leq59\\ \quad \\ Parity(x,y,z)x\bigoplus y\bigoplus z, \qquad 60\leq t\leq79\\ \quad \\ \end{cases}⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧Ch(x,y,z)(x∩y)⨁(¬x∩z),0≤t≤19Parity(x,y,z)x⨁y⨁z,20≤t≤39Maj(x,y,z)(x∩y)⨁(x∩z)⨁(y∩z),40≤t≤59Parity(x,y,z)x⨁y⨁z,60≤t≤79
For i1 to N: { //1. 计算 WtW_tWt Wt\quad W_tWt {Mt(0),0≤t≤15ROTL1(Wt−3⨁Wt−8⨁Wt−14⨁Wt−16),16≤t≤79\begin{cases} M^{(0)}_t, \qquad 0\leq t\leq15\\ \quad \\ ROTL^1(W_{t-3}\bigoplus W_{t-8}\bigoplus W_{t-14}\bigoplus W_{t-16}), \qquad 16\leq t\leq79\\ \end{cases}⎩⎪⎨⎪⎧Mt(0),0≤t≤15ROTL1(Wt−3⨁Wt−8⨁Wt−14⨁Wt−16),16≤t≤79 //2. 初始化工作变量 a, b, c, d, e. 他们用来存储在第 i-1 次迭代式的 Hash 值 // 他们的初始值就是我们在设置初始 Hash 值小节中所说的值. aH0i−1bH1i−1cH2i−1dH3i−1eH4i−1\quad aH^{i-1}_0 \\ \quad bH^{i-1}_1 \\ \quad cH^{i-1}_2 \\ \quad dH^{i-1}_3 \\ \quad eH^{i-1}_4 \\ aH0i−1bH1i−1cH2i−1dH3i−1eH4i−1 // 3 For t0 to 79: { TROTL5(a)ft(b,c,d)eKtWteddccROTL30(b)baaT\qquad TROTL^5(a)f_t(b,c,d)eK_tW_t \\ \qquad ed \\ \qquad dc \\ \qquad cROTL^30(b) \\ \qquad ba \\ \qquad aT \\ TROTL5(a)ft(b,c,d)eKtWteddccROTL30(b)baaT } //4. 计算第 ithi^{th}ith 中间 hash 值HiH^iHi H0(i)aH0(i−1)H1(i)bH1(i−1)H2(i)cH2(i−1)H3(i)dH3(i−1)H4(i)eH4(i−1)\quad H^{(i)}_0aH^{(i-1)}_0 \\ \quad H^{(i)}_1bH^{(i-1)}_1 \\ \quad H^{(i)}_2cH^{(i-1)}_2 \\ \quad H^{(i)}_3dH^{(i-1)}_3 \\ \quad H^{(i)}_4eH^{(i-1)}_4 \\ H0(i)aH0(i−1)H1(i)bH1(i−1)H2(i)cH2(i−1)H3(i)dH3(i−1)H4(i)eH4(i−1) }
在经过 N 次迭代之后, 最终结果为 H0(N),H1(N),H2(N),H3(N),H4(N)H^{(N)}_0, H^{(N)}_1, H^{(N)}_2, H^{(N)}_3, H^{(N)}_4H0(N),H1(N),H2(N),H3(N),H4(N) 的字节表示依次连接所组成的字节数组.
SHA-256####
SHA-256 算法要求输入数据的长度不能大于 2642^64264, 最小长度为0.
SHA-224 算法的计算过程与 SHA-256 相同, 却别在于使用的初始化 Hash 值不同, 且 SHA-224 算法的最终结果是取 SHA-256 算法结果的前 224 bit.
伪代码如下:
SHRn(x)xgt;gt;nSHR^n(x)x gt;gt; nSHRn(x)xn ROTRn(x)(xgt;gt;n)∪(xlt;lt;w−n)ROTR^n(x)(x gt;gt; n)\cup (x lt;lt; w - n)ROTRn(x)(xn)∪(xw−n) Σ0{256}(x)ROTR2(x)⨁ROTR13(x)⨁ROTR22(x)\Sigma^{\{256\}}_0(x)ROTR^2(x)\bigoplus ROTR^{13}(x)\bigoplus ROTR^{22}(x)Σ0{256}(x)ROTR2(x)⨁ROTR13(x)⨁ROTR22(x) Σ1{256}(x)ROTR6(x)⨁ROTR11(x)⨁ROTR25(x)\Sigma^{\{256\}}_1(x)ROTR^6(x)\bigoplus ROTR^{11}(x)\bigoplus ROTR^{25}(x)Σ1{256}(x)ROTR6(x)⨁ROTR11(x)⨁ROTR25(x) σ0{256}(x)ROTR7(x)⨁ROTR18(x)⨁SHR3(x)\sigma^{\{256\}}_0(x)ROTR^7(x)\bigoplus ROTR^{18}(x)\bigoplus SHR^3(x)σ0{256}(x)ROTR7(x)⨁ROTR18(x)⨁SHR3(x) σ1{256}(x)ROTR17(x)⨁ROTR19(x)⨁SHR10(x)\sigma^{\{256\}}_1(x)ROTR^{17}(x)\bigoplus ROTR^{19}(x)\bigoplus SHR^{10}(x)σ1{256}(x)ROTR17(x)⨁ROTR19(x)⨁SHR10(x)
For i1 to N: { //1. 计算 WtW_tWt Wt\quad W_tWt {Mt(0),0≤t≤15σ1{256}(Wt−2)Wt−7σ0{256}(Wt−15)Wt−16,16≤t≤63\begin{cases} M^{(0)}_t, \qquad 0\leq t\leq15\\ \quad \\ \sigma^{\{256\}}_1(W_{t-2})W_{t-7}\sigma^{\{256\}}_0(W_{t-15})W_{t-16}, \qquad 16\leq t\leq63\\ \end{cases}⎩⎪⎨⎪⎧Mt(0),0≤t≤15σ1{256}(Wt−2)Wt−7σ0{256}(Wt−15)Wt−16,16≤t≤63 //2. 初始化工作变量 a, b, c, d, e, f, g, h. 他们用来存储在第 i-1 次迭代式的 Hash 值 // 他们的初始值就是我们在设置初始 Hash 值小节中所说的值. aH0i−1bH1i−1cH2i−1dH3i−1eH4i−1fH5i−1gH6i−1hH7i−1\quad aH^{i-1}_0 \\ \quad bH^{i-1}_1 \\ \quad cH^{i-1}_2 \\ \quad dH^{i-1}_3 \\ \quad eH^{i-1}_4 \\ \quad fH^{i-1}_5 \\ \quad gH^{i-1}_6 \\ \quad hH^{i-1}_7 \\ aH0i−1bH1i−1cH2i−1dH3i−1eH4i−1fH5i−1gH6i−1hH7i−1 // 3 For t0 to 63: { T1hΣ1{256}(e)Ch(e,f,g)K{256}tWtT2Σ0{256}(a)Maj(a,b,c)hggffeedT1dccbbaaT1T2\qquad T_1h\Sigma^{\{256\}}_1(e)Ch(e,f,g)K^{\{256\}_t}W_t \\ \qquad T_2\Sigma^{\{256\}}_0(a)Maj(a,b,c) \\ \qquad hg \\ \qquad gf \\ \qquad fe \\ \qquad edT_1 \\ \qquad dc \\ \qquad cb \\ \qquad ba \\ \qquad aT_1T_2 \\ T1hΣ1{256}(e)Ch(e,f,g)K{256}tWtT2Σ0{256}(a)Maj(a,b,c)hggffeedT1dccbbaaT1T2 } //4. 计算第 ithi^{th}ith 中间 hash 值HiH^iHi H0(i)aH0(i−1)H1(i)bH1(i−1)H2(i)cH2(i−1)H3(i)dH3(i−1)H4(i)eH4(i−1)H5(i)bH5(i−1)H6(i)cH6(i−1)H7(i)dH7(i−1)\quad H^{(i)}_0aH^{(i-1)}_0 \\ \quad H^{(i)}_1bH^{(i-1)}_1 \\ \quad H^{(i)}_2cH^{(i-1)}_2 \\ \quad H^{(i)}_3dH^{(i-1)}_3 \\ \quad H^{(i)}_4eH^{(i-1)}_4 \\ \quad H^{(i)}_5bH^{(i-1)}_5 \\ \quad H^{(i)}_6cH^{(i-1)}_6 \\ \quad H^{(i)}_7dH^{(i-1)}_7 \\ H0(i)aH0(i−1)H1(i)bH1(i−1)H2(i)cH2(i−1)H3(i)dH3(i−1)H4(i)eH4(i−1)H5(i)bH5(i−1)H6(i)cH6(i−1)H7(i)dH7(i−1) }
在经过 N 次迭代之后, 最终结果为 H0(N),H1(N),H2(N),H3(N),H4(N),H5(N),H6(N),H7(N)H^{(N)}_0, H^{(N)}_1, H^{(N)}_2, H^{(N)}_3, H^{(N)}_4, H^{(N)}_5, H^{(N)}_6, H^{(N)}_7H0(N),H1(N),H2(N),H3(N),H4(N),H5(N),H6(N),H7(N) 的字节表示依次连接所组成的字节数组.
SHA-512####
SHA-512 算法要求输入数据的长度不能大于 21282^1282128, 最小长度为0.
SHA-384 算法的计算过程与 SHA-512 相同, 却别在于使用的初始化 Hash 值不同, 且 SHA-384 算法的最终结果是取 SHA-512 算法结果的前 384 bit.
SHA-512/224 算法的计算过程与 SHA-512 相同, 却别在于使用的初始化 Hash 值不同, 且 SHA-512/224 算法的最终结果是取 SHA-512 算法结果的前 224 bit.
SHA-512/256 算法的计算过程与 SHA-512 相同, 却别在于使用的初始化 Hash 值不同, 且 SHA-512/256 算法的最终结果是取 SHA-512 算法结果的前 256 bit.
伪代码如下:
Σ0{512}(x)ROTR28(x)⨁ROTR34(x)⨁ROTR39(x)\Sigma^{\{512\}}_0(x)ROTR^{28}(x)\bigoplus ROTR^{34}(x)\bigoplus ROTR^{39}(x)Σ0{512}(x)ROTR28(x)⨁ROTR34(x)⨁ROTR39(x) Σ1{512}(x)ROTR14(x)⨁ROTR18(x)⨁ROTR41(x)\Sigma^{\{512\}}_1(x)ROTR^{14}(x)\bigoplus ROTR^{18}(x)\bigoplus ROTR^{41}(x)Σ1{512}(x)ROTR14(x)⨁ROTR18(x)⨁ROTR41(x) σ0{512}(x)ROTR1(x)⨁ROTR8(x)⨁SHR7(x)\sigma^{\{512\}}_0(x)ROTR^1(x)\bigoplus ROTR^8(x)\bigoplus SHR^7(x)σ0{512}(x)ROTR1(x)⨁ROTR8(x)⨁SHR7(x) σ1{512}(x)ROTR19(x)⨁ROTR61(x)⨁SHR6(x)\sigma^{\{512\}}_1(x)ROTR^{19}(x)\bigoplus ROTR^{61}(x)\bigoplus SHR^6(x)σ1{512}(x)ROTR19(x)⨁ROTR61(x)⨁SHR6(x)
For i1 to N: { //1. 计算 WtW_tWt Wt\quad W_tWt {Mt(0),0≤t≤15σ1{512}(Wt−2)Wt−7σ0{512}(Wt−15)Wt−16,16≤t≤79\begin{cases} M^{(0)}_t, \qquad 0\leq t\leq15\\ \quad \\ \sigma^{\{512\}}_1(W_{t-2})W_{t-7}\sigma^{\{512\}}_0(W_{t-15})W_{t-16}, \qquad 16\leq t\leq79\\ \end{cases}⎩⎪⎨⎪⎧Mt(0),0≤t≤15σ1{512}(Wt−2)Wt−7σ0{512}(Wt−15)Wt−16,16≤t≤79 //2. 初始化工作变量 a, b, c, d, e, f, g, h. 他们用来存储在第 i-1 次迭代式的 Hash 值 // 他们的初始值就是我们在设置初始 Hash 值小节中所说的值. aH0i−1bH1i−1cH2i−1dH3i−1eH4i−1fH5i−1gH6i−1hH7i−1\quad aH^{i-1}_0 \\ \quad bH^{i-1}_1 \\ \quad cH^{i-1}_2 \\ \quad dH^{i-1}_3 \\ \quad eH^{i-1}_4 \\ \quad fH^{i-1}_5 \\ \quad gH^{i-1}_6 \\ \quad hH^{i-1}_7 \\ aH0i−1bH1i−1cH2i−1dH3i−1eH4i−1fH5i−1gH6i−1hH7i−1 // 3 For t0 to 79: { T1hΣ1{512}(e)Ch(e,f,g)K{512}tWtT2Σ0{512}(a)Maj(a,b,c)hggffeedT1dccbbaaT1T2\qquad T_1h\Sigma^{\{512\}}_1(e)Ch(e,f,g)K^{\{512\}_t}W_t \\ \qquad T_2\Sigma^{\{512\}}_0(a)Maj(a,b,c) \\ \qquad hg \\ \qquad gf \\ \qquad fe \\ \qquad edT_1 \\ \qquad dc \\ \qquad cb \\ \qquad ba \\ \qquad aT_1T_2 \\ T1hΣ1{512}(e)Ch(e,f,g)K{512}tWtT2Σ0{512}(a)Maj(a,b,c)hggffeedT1dccbbaaT1T2 } //4. 计算第 ithi^{th}ith 中间 hash 值HiH^iHi H0(i)aH0(i−1)H1(i)bH1(i−1)H2(i)cH2(i−1)H3(i)dH3(i−1)H4(i)eH4(i−1)H5(i)bH5(i−1)H6(i)cH6(i−1)H7(i)dH7(i−1)\quad H^{(i)}_0aH^{(i-1)}_0 \\ \quad H^{(i)}_1bH^{(i-1)}_1 \\ \quad H^{(i)}_2cH^{(i-1)}_2 \\ \quad H^{(i)}_3dH^{(i-1)}_3 \\ \quad H^{(i)}_4eH^{(i-1)}_4 \\ \quad H^{(i)}_5bH^{(i-1)}_5 \\ \quad H^{(i)}_6cH^{(i-1)}_6 \\ \quad H^{(i)}_7dH^{(i-1)}_7 \\ H0(i)aH0(i−1)H1(i)bH1(i−1)H2(i)cH2(i−1)H3(i)dH3(i−1)H4(i)eH4(i−1)H5(i)bH5(i−1)H6(i)cH6(i−1)H7(i)dH7(i−1) }
在经过 N 次迭代之后, 最终结果为 H0(N),H1(N),H2(N),H3(N),H4(N),H5(N),H6(N),H7(N)H^{(N)}_0, H^{(N)}_1, H^{(N)}_2, H^{(N)}_3, H^{(N)}_4, H^{(N)}_5, H^{(N)}_6, H^{(N)}_7H0(N),H1(N),H2(N),H3(N),H4(N),H5(N),H6(N),H7(N) 的字节表示依次连接所组成的字节数组.
算法实现##
本人使用 go 语言实现了该算法. github:https://github.com/UselezzProgrammer/mycrypto
END!
