遵义市建设厅网站,能建商城,如何seo网站,百度首页排名优化价格1. SHA256简介
SHA256是SHA-2下细分出的一种算法
SHA-2#xff0c;名称来自于安全散列算法2#xff08;英语#xff1a;Secure Hash Algorithm 2#xff09;的缩写#xff0c;一种密码散列函数算法标准#xff0c;由美国国家安全局研发#xff0c;属于SHA算法之一名称来自于安全散列算法2英语Secure Hash Algorithm 2的缩写一种密码散列函数算法标准由美国国家安全局研发属于SHA算法之一是SHA-1的后继者。
SHA-2下又可再分为六个不同的算法标准
包括了SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。
这些变体除了生成摘要的长度 、循环运行的次数等一些微小差异外算法的基本结构是一致的。
回到SHA256上说白了它就是一个哈希函数。
哈希函数又称散列算法是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要使得数据量变小将数据的格式固定下来。该函数将数据打乱混合重新创建一个叫做散列值或哈希值的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。
对于任意长度的消息SHA256都会产生一个256bit长的哈希值称作消息摘要。
这个摘要相当于是个长度为32个字节的数组通常用一个长度为64的十六进制字符串来表示
来看一个例子
干他100天成为区块链程序员红军大叔带领着我们fighting!
这句话经过哈希函数SHA256后得到的哈希值为
A7FCFC6B5269BDCCE571798D618EA219A68B96CB87A0E21080C2E758D23E4CE9
这里找到了一个SHA256在线验证工具可以用来进行SHA256哈希结果的验证后面也可以用来检验自己的SHA256代码是否正确。用起来很方便不妨感受下。 2. SHA256原理详解
为了更好的理解SHA256的原理这里首先将算法中可以单独抽出的模块包括常量的初始化、信息预处理、使用到的逻辑运算分别进行介绍甩开这些理解上的障碍后一起来探索SHA256算法的主体部分即消息摘要是如何计算的。
2.1 常量初始化
SHA256算法中用到了8个哈希初值以及64个哈希常量
其中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而来
举个例子来说$ \sqrt{2} $小数部分约为0.414213562373095048而 0.414213562373095048≈6∗16−1a∗16−20∗16−3...0.414213562373095048 \approx 6*16^{-1} a*16^{-2} 0*16^{-3} ... 0.414213562373095048≈6∗16−1a∗16−20∗16−3... 于是质数2的平方根的小数部分取前32bit就对应出了0x6a09e667
在SHA256算法中用到的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和8个哈希初值类似这些常量是对自然数中前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而来。
2.2 信息预处理(pre-processing)
SHA256算法中的预处理就是在想要Hash的消息后面补充需要的信息使整个消息满足指定的结构。
信息的预处理分为两个步骤附加填充比特和附加长度
STEP1附加填充比特
在报文末尾进行填充使报文长度在对512取模以后的余数是448
填充是这样进行的先补第一个比特为1然后都补0直到长度满足对512取模后余数是448。
需要注意的是信息必须进行填充也就是说即使长度已经满足对512取模后余数是448补位也必须要进行这时要填充512个比特。
因此填充是至少补一位最多补512位。
例以信息“abc”为例显示补位的过程。
a,b,c对应的ASCII码分别是97,98,99
于是原始信息的二进制编码为01100001 01100010 01100011
补位第一步首先补一个“1” 0110000101100010 01100011 1
补位第二步,补423个“0”01100001 01100010 01100011 10000000 00000000 … 00000000
补位完成后的数据如下为了简介用16进制表示
61626380 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000为什么是448?
因为在第一步的预处理后第二步会再附加上一个64bit的数据用来表示原始报文的长度信息。而44864512正好拼成了一个完整的结构。
STEP2附加长度值
附加长度值就是将原始数据第一步填充前的消息的长度信息补到已经进行了填充操作的消息后面。
wiki百科中给出的原文是append length of message (before pre-processing), in bits, as 64-bit big-endian integer
SHA256用一个64位的数据来表示原始消息的长度。
因此通过SHA256计算的消息长度必须要小于$ 2^64 $当然绝大多数情况这足够大了。
长度信息的编码方式为64-bit big-endian integer
关于Big endian的含义文末给出了补充
回到刚刚的例子消息“abc”3个字符占用24个bit
因此在进行了补长度的操作以后整个消息就变成下面这样了16进制格式
61626380 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 000000182.3 逻辑运算
SHA256散列函数中涉及的操作全部是逻辑的位运算
包括如下的逻辑函数
Ch(x,y,z)(x∧y)⊕(¬x∧z)Ch(x,y,z) (x \land y) \oplus (\neg x \land z) Ch(x,y,z)(x∧y)⊕(¬x∧z) Ma(x,y,z)(x∧y)⊕(x∧z)⊕(y∧z)Ma(x,y,z) (x \land y) \oplus (x \land z) \oplus (y \land z) Ma(x,y,z)(x∧y)⊕(x∧z)⊕(y∧z) Σ0(x)S2(x)⊕S13(x)⊕S22(x)\Sigma_{0}(x) S^{2}(x) \oplus S^{13}(x) \oplus S^{22}(x) Σ0(x)S2(x)⊕S13(x)⊕S22(x) Σ1(x)S6(x)⊕S11(x)⊕S25(x)\Sigma_{1}(x) S^{6}(x) \oplus S^{11}(x) \oplus S^{25}(x) Σ1(x)S6(x)⊕S11(x)⊕S25(x) σ0(x)S7(x)⊕S18(x)⊕R3(x)\sigma_{0}(x) S^{7}(x) \oplus S^{18}(x) \oplus R^{3}(x) σ0(x)S7(x)⊕S18(x)⊕R3(x) σ1(x)S17(x)⊕S19(x)⊕R10(x)\sigma_{1}(x) S^{17}(x) \oplus S^{19}(x) \oplus R^{10}(x) σ1(x)S17(x)⊕S19(x)⊕R10(x) 其中
逻辑运算含义∧\land ∧按位“与”¬\neg ¬按位“补”⊕\oplus ⊕按位“异或”SnS^{n} Sn循环右移n个bitRnR^{n} Rn右移n个bit
2.4 计算消息摘要
现在来介绍SHA256算法的主体部分即消息摘要是如何计算的。
首先将消息分解成512-bit大小的块
(break message into 512-bit chunks) 假设消息M可以被分解为n个块于是整个算法需要做的就是完成n次迭代n次迭代的结果就是最终的哈希值即256bit的数字摘要。
一个256-bit的摘要的初始值H0经过第一个数据块进行运算得到H1即完成了第一次迭代
H1经过第二个数据块得到H2……依次处理最后得到HnHn即为最终的256-bit消息摘要
将每次迭代进行的映射用$ Map(H_{i-1}) H_{i} $表示于是迭代可以更形象的展示为 图中256-bit的Hi被描述8个小块这是因为SHA256算法中的最小运算单元称为“字”Word一个字是32位。
此外第一次迭代中映射的初值设置为前面介绍的8个哈希初值如下图所示 下面开始介绍每一次迭代的内容即映射$ Map(H_{i-1}) H_{i} $的具体算法
STEP1构造64个字word
break chunk into sixteen 32-bit big-endian words w[0], …, w[15]
对于每一块将块分解为16个32-bit的big-endian的字记为w[0], …, w[15]
也就是说前16个字直接由消息的第i个块分解得到
其余的字由如下迭代公式得到
Wtσ1(Wt−2)Wt−7σ0(Wt−15)Wt−16W_{t} \sigma_{1}(W_{t-2}) W_{t-7} \sigma_{0}(W_{t-15}) W_{t-16}Wtσ1(Wt−2)Wt−7σ0(Wt−15)Wt−16
STEP2进行64次循环
映射 $ Map(H_{i-1}) H_{i} $ 包含了64次加密循环
即进行64次加密循环即可完成一次迭代
每次加密循环可以由下图描述 图中ABCDEFGH这8个字word在按照一定的规则进行更新其中
深蓝色方块是事先定义好的非线性逻辑函数上文已经做过铺垫
红色田字方块代表 mod $ 2^{32} $ addition即将两个数字加在一起如果结果大于$ 2^{32} 你必须除以你必须除以你必须除以 2^{32} $并找到余数。
ABCDEFGH一开始的初始值分别为$ H_{i-1}(0),H_{i-1}(1),…,H_{i-1}(7) $
Kt是第t个密钥对应我们上文提到的64个常量
Wt是本区块产生第t个word。原消息被切成固定长度512-bit的区块对每一个区块产生64个word通过重复运行循环n次对ABCDEFGH这八个字循环加密。
最后一次循环所产生的八个字合起来即是第i个块对应到的散列字符串$ H_{i} $
由此变完成了SHA256算法的所有介绍 3. SHA256算法伪代码
现在我们可以结合SHA256算法的伪代码,将上述的所有步骤进行梳理整合
Note: All variables are unsigned 32 bits and wrap modulo 232 when calculatingInitialize variables
(first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19):
h0 : 0x6a09e667
h1 : 0xbb67ae85
h2 : 0x3c6ef372
h3 : 0xa54ff53a
h4 : 0x510e527f
h5 : 0x9b05688c
h6 : 0x1f83d9ab
h7 : 0x5be0cd19Initialize table of round constants
(first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311):
k[0..63] :0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2Pre-processing:
append the bit 1 to the message
append k bits 0, where k is the minimum number 0 such that the resulting messagelength (in bits) is congruent to 448(mod 512)
append length of message (before pre-processing), in bits, as 64-bit big-endian integerProcess the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunkbreak chunk into sixteen 32-bit big-endian words w[0..15]Extend the sixteen 32-bit words into sixty-four 32-bit words:for i from 16 to 63s0 : (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor(w[i-15] rightshift 3)s1 : (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor(w[i-2] rightshift 10)w[i] : w[i-16] s0 w[i-7] s1Initialize hash value for this chunk:a : h0b : h1c : h2d : h3e : h4f : h5g : h6h : h7Main loop:for i from 0 to 63s0 : (a rightrotate 2) xor (a rightrotate 13) xor(a rightrotate 22)maj : (a and b) xor (a and c) xor(b and c)t2 : s0 majs1 : (e rightrotate 6) xor (e rightrotate 11) xor(e rightrotate 25)ch : (e and f) xor ((not e) and g)t1 : h s1 ch k[i] w[i]h : gg : ff : ee : d t1d : cc : bb : aa : t1 t2Add this chunks hash to result so far:h0 : h0 ah1 : h1 bh2 : h2 ch3 : h3 dh4 : h4 eh5 : h5 fh6 : h6 gh7 : h7 hProduce the final hash value (big-endian):
digest hash h0 append h1 append h2 append h3 append h4 append h5 append h6 append h74. 参考文献
本篇笔记主要参考整合的资料如下
SHA-2 wiki
比特币算法——SHA256算法介绍
SHA-256算法实现
操作指南验证SHA256 知识填补
大端和小端Big endian and Little endian 对于整型、长整型等数据类型都存在字节排列的高低位顺序问题。
Big endian 认为第一个字节是最高位字节按照从低地址到高地址的顺序存放数据的高位字节到低位字节
而 Little endian 则相反它认为第一个字节是最低位字节按照从低地址到高地址的顺序存放据的低位字节到高位字节。
例如假设从内存地址 0x0000 开始有以下数据
地址数据……0x00000x120x00010x340x00020xab0x00030xcd……
假设我们去读取一个地址为 0x0000 的四个字节变量
若字节序为big-endian则读出结果为0x1234abcd
若字节序为little-endian则读出结果为0xcdab3412。
如果我们将0x1234abcd 写入到以 0x0000 开始的内存中则Little endian 和 Big endian 模式的存放结果如下
地址0x00000x00010x00020x0003big-Big_endian0x120x340xab0xcdlittle-endian0xcd0xab0x340x12
参考文献
点击返回正文
